llvm / llvm/llvm-project

[ValueTracking] Dead branch on smin(a,b) > K not eliminated under bounded operand guards

Open
#207,131 0 comments 0 reactions 0 assignees View on GitHub
llvm:analysis missed-optimization
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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.