Missed Dead Branch due to Ignored Induction Variable Bounds
- Dominant language
- LLVM
- Stars
- 40.5k
- Forks
- 18.7k
- PR merge metrics
- PR metrics pending
Description
The following reduced IR is derived from https://github.com/openssl/openssl/blob/5f447011a4c42b1b4b6fd9266385b6a61961a9ef/providers/implementations/macs/kmac_prov.c#L259
https://godbolt.org/z/18fzxadzq
alive2: https://alive2.llvm.org/ce/z/o3dWC6
In the reduced IR, the call to `ERR_new()` is unreachable, so the function can be simplified to `ret i32 0`.
The entry branch guarantees `%0 < 513` on the only path that reaches the loop. Therefore, `%3 = shl nuw nsw i64 %0, 1` is bounded by 1024. The loop repeatedly performs `lshr ... , 8`, so starting from any value in [0, 1024], the induction variable `%.03.i.i.i` can become zero after at most two shifts, and the loop exits on the following iteration.
As a result, the loop executes at most three iterations in total, meaning the exit PHI value `%.052.i.i.i` is at most 2. Consequently, the condition `% .not.i.i = icmp samesign ult i32 %.052.i.i.i, 515` is always true, and the branch to block %6 is dead.
```llvm
define noundef i32 @kmac_setkey(i64 %0) local_unnamed_addr {
%or.cond = icmp uge i64 %0, 513
br i1 %or.cond, label %common.ret, label %.lr.ph.i.i.i.preheader
.lr.ph.i.i.i.preheader:
%3 = shl nuw nsw i64 %0, 1
br label %.lr.ph.i.i.i
common.ret:
ret i32 0
.lr.ph.i.i.i:
%.03.i.i.i = phi i64 [ %5, %.lr.ph.i.i.i ], [ %3, %.lr.ph.i.i.i.preheader ]
%.052.i.i.i = phi i32 [ %4, %.lr.ph.i.i.i ], [ 0, %.lr.ph.i.i.i.preheader ]
%4 = add nuw nsw i32 %.052.i.i.i, 1
%5 = lshr i64 %.03.i.i.i, 8
%.not.i.i.i = icmp eq i64 %.03.i.i.i, 0
br i1 %.not.i.i.i, label %get_encode_size.exit.i.i, label %.lr.ph.i.i.i
get_encode_size.exit.i.i:
%.not.i.i = icmp samesign ult i32 %.052.i.i.i, 515
br i1 %.not.i.i, label %common.ret, label %6
6:
tail call void @ERR_new()
br label %common.ret
}
declare void @ERR_new() local_unnamed_addr
```
Expected:
```llvm
define noundef i32 @tgt(i64 %0) local_unnamed_addr {
ret i32 0
}
```
Contributor guide
Assessment
This issue has not been assessed yet.