llvm / llvm/llvm-project

Missed Branch Elimination of icmp ugt %spec.select, 8 after Prior Excluding Range [6, 8] and slt 6

Open
#193,909 1 comment 0 reactions 0 assignees View on GitHub
llvm:optimizations missed-optimization
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

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.