[ValueTracking] Dead branch on smin(a,b) > K not eliminated under bounded operand guards
- Dominant language
- LLVM
- Stars
- 40.5k
- Forks
- 18.7k
- PR merge metrics
- PR metrics pending
Description
For the following C snippet, -O3 does not eliminate the dead branch:
```c
void use(void);
void f(int a, int b) {
int m = a < b ? a : b;
if (a >= 0 && a <= 15 && b >= 0 && b <= 15) {
if (m > 15) use(); // dead
}
}
```
It gives:
```llvm
define dso_local void @f(i32 noundef %a, i32 noundef %b) local_unnamed_addr {
entry:
%cond = tail call i32 @llvm.smin.i32(i32 %a, i32 %b)
%0 = or i32 %b, %a
%or.cond11 = icmp ult i32 %0, 16
%cmp7 = icmp sgt i32 %cond, 15
%or.cond12 = and i1 %or.cond11, %cmp7
br i1 %or.cond12, label %if.then8, label %if.end9
if.then8:
tail call void @use()
br label %if.end9
if.end9:
ret void
}
```
The function body is dead and could reduce to `ret void`.
If we rewrite the integer comparison in bit operations, or we add a redundant assume(), the dead branch could be eliminated away flawlessly, like the below two cases:
```c
// clang -O3: entire function is `ret void`.
void f_mask(int a, int b) {
int m = a < b ? a : b;
if ((a & ~15) == 0 && (b & ~15) == 0) {
if (m > 15) use(); // removed
}
}
// clang -O3: fires; assume bundle adds a fact already implied by the guard.
void f_range_assume(int a, int b) {
int m = a < b ? a : b;
if (a >= 0 && a <= 15 && b >= 0 && b <= 15) {
__builtin_assume(a <= 15); // redundant
if (m > 15) use(); // removed
}
}
```
Godbolt for all above cases: https://godbolt.org/z/Tv7r1fnfj
The problem seems to be `computeConstantRange` checks assume but ignores dominating conditions, while knownbits does both. Thus, `computeConstantRange` returns `getFull()` under the range guard, and the compare at `m > 15` doesn't fold.
Contributor guide
Research direction
Start with ValueTracking's computeConstantRange and compare how dominating conditions and assume facts are handled, then reproduce the C examples from the Godbolt link at -O3. The fix is complete when the bounded-operand guard eliminates the m > 15 branch without a redundant assume, with coverage for the reported case.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- c
- Domain
- compilers
- Issue type
- Bug
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Quiet
- Clarity
- Mostly clear
- Newbie friendliness
- 52/100