[ValueTracking] A strict range on x - y does not establish x != y
- Dominant language
- LLVM
- Stars
- 40.5k
- Forks
- 18.7k
- PR merge metrics
- PR metrics pending
Description
LLVM already folds `x == y` to false when an assumption establishes that `x - y` equals a nonzero constant. A range constraint on the same subtraction can also exclude zero, but that information does not establish that the operands are unequal.
For the following LLVM IR:
```llvm
define i1 @src(i64 %x, i64 %y) {
entry:
%diff = sub i64 %x, %y
%cond = icmp ugt i64 %diff, 1
call void @llvm.assume(i1 %cond)
%r = icmp eq i64 %x, %y
ret i1 %r
}
```
`opt -O3` leaves the final comparison and drops the assumption (Godbolt: https://godbolt.org/z/fM6bxKMY5):
```llvm
define i1 @src(i64 %x, i64 %y) {
entry:
%r = icmp eq i64 %x, %y
ret i1 %r
}
```
The range condition `%diff >u 1` excludes zero. `x - y == 0` if and only if `x == y`; no `nsw` or `nuw` assumption is needed. The expected result for the range constrained function is therefore a constant return (alive2: https://alive2.llvm.org/ce/z/r_x-R-):
```llvm
define i1 @src(i64 %x, i64 %y) {
entry:
ret i1 false
}
```
`ValueTracking.cpp::isImpliedCondICmps()` already has the rule `(x-y) == C, C != 0 => x != y`. This case needs the same conclusion from `(x-y) >u 1`, which also excludes a zero difference. A possible fix is to generalize the rule to `(x-y) Pred C => x != y` whenever `0 Pred C` is false, and extend `findValuesAffectedByCondition()` to associate ordered comparisons on the subtraction with both `%x` and `%y`, as it already does for equality comparisons.
Contributor guide
Research direction
Reproduce the LLVM IR example with opt -O3, then inspect ValueTracking.cpp, especially isImpliedCondICmps() and findValuesAffectedByCondition(). Compare the existing nonzero-constant subtraction rule with the ordered range case. Done means the range-constrained function returns constant false and the behavior has regression coverage.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- cpp
- Domain
- compilers
- Issue type
- Bug
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Active
- Clarity
- Mostly clear
- Newbie friendliness
- 55/100