Missed Branch Elimination of icmp ugt %spec.select, 8 after Prior Excluding Range [6, 8] and slt 6
- 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/3cff7c21817/test/evp_extra_test.c#L1953
Godbolt: https://godbolt.org/z/o9T76nPfn
alive2 proof: https://alive2.llvm.org/ce/z/L-_goZ
On the false edge of `icmp ult (%spec.select - 6), 3`, `%spec.select` is known not to be 6, 7, or 8. Then, on the false edge of `icmp slt %spec.select, 6`, `%spec.select >= 6` is also known. Combining these facts implies `%spec.select > 8`, so `icmp ugt %spec.select, 8` in block `%8` is always true and the branch can be folded.
```llvm
define i32 @test_EVP_DigestSignInit(i32 noundef %0) {
%2 = icmp sgt i32 %0, 14
%spec.select = select i1 %2, i32 0, i32 %0
%3 = add i32 %spec.select, -6
%or.cond = icmp ult i32 %3, 3
br i1 %or.cond, label %common.ret, label %4
common.ret: ; preds = %10, %8, %6, %1
ret i32 0
4: ; preds = %1
%5 = icmp slt i32 %spec.select, 6
br i1 %5, label %6, label %8
6: ; preds = %4
%7 = tail call i32 @EVP_DigestSignUpdate()
br label %common.ret
8: ; preds = %4
%9 = icmp ugt i32 %spec.select, 8
br i1 %9, label %10, label %common.ret
10: ; preds = %8
%11 = tail call i32 @EVP_DigestSign()
br label %common.ret
}
```
expected:
```llvm
define i32 @tgt(i32 noundef %0) {
%2 = icmp sgt i32 %0, 14
%spec.select = select i1 %2, i32 0, i32 %0
%3 = add i32 %spec.select, -6
%or.cond = icmp ult i32 %3, 3
br i1 %or.cond, label %common.ret, label %4
common.ret: ; preds = %8, %6, %1
ret i32 0
4: ; preds = %1
%5 = icmp slt i32 %spec.select, 6
br i1 %5, label %6, label %8
6: ; preds = %4
%7 = tail call i32 @EVP_DigestSignUpdate()
br label %common.ret
8: ; preds = %4
%9 = tail call i32 @EVP_DigestSign()
br label %common.ret
}
```
Contributor guide
Assessment
This issue has not been assessed yet.