[ValueTracking] Fails to fold a == b under assume(a == b + C) for nonzero constant C
- Dominant language
- LLVM
- Stars
- 40.5k
- Forks
- 18.7k
- PR merge metrics
- PR metrics pending
Description
For the following LLVM IR:
```llvm
define i1 @src(i8 %a, i8 %b) {
entry:
%sum = add i8 %b, 12
%fact = icmp eq i8 %a, %sum
call void @llvm.assume(i1 %fact)
%r = icmp eq i8 %a, %b
ret i1 %r
}
```
On current LLVM trunk, both `opt -O2` and `opt -O3` keep the final comparison (Godbolt: https://godbolt.org/z/fYKaTeP4W):
```llvm
define i1 @src(i8 %a, i8 %b) {
entry:
%sum = add i8 %b, 12
%fact = icmp eq i8 %a, %sum
tail call void @llvm.assume(i1 %fact)
%r = icmp eq i8 %a, %b
ret i1 %r
}
```
On every defined execution, the `%r` comparison is false. Since the arithmetic is modulo `2^8`:
```text
a == b + 12
=> a - b == 12
=> a != b
```
Therefore the expected result is (Alive2: https://alive2.llvm.org/ce/z/gwS5Mf):
```llvm
define i1 @tgt(i8 %a, i8 %b) {
entry:
ret i1 false
}
```
LLVM already handles the equivalent subtraction form in the existing `llvm/test/Transforms/InstCombine/icmp.ll` test:
```llvm
define i1 @non_zero_diff_implies_icmp_eq(i8 %p0, i8 %p1) {
entry:
%diff = sub i8 %p0, %p1
%cond = icmp eq i8 %diff, 12
call void @llvm.assume(i1 %cond)
%cmp = icmp eq i8 %p0, %p1
ret i1 %cmp
}
```
The existing test indicates that LLVM can derive `a != b` from `a - b == C` for a nonzero constant `C`. For the add form above, `ValueTracking.cpp::isImpliedCondICmps()`needs to prove that `a == b + C` implies `a != b`; after matching the shared operand `a`, the relevant remaining check is `(b + C) != b`. For `%sum = add i8 %b, 12`, the existing `isKnownNonEqual(%sum, %b)` query already returns true through `isModifyingBinopOfNonZero()`. One possible fix is to make a context-free `isKnownNonEqual(%sum, %b)` query after matching the shared operand `a`.
Contributor guide
Research direction
Start in ValueTracking.cpp at isImpliedCondICmps(), then compare the add case with the existing subtraction test in llvm/test/Transforms/InstCombine/icmp.ll. Reproduce the issue with opt -O2 or -O3; done means the final comparison folds to ret i1 false and the regression test passes.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- cpp
- Domain
- compilers
- Issue type
- Bug
- Difficulty
- 3/5
- Estimated time
- 1-2 days
- Activity status
- Active
- Clarity
- Clearly specified
- Newbie friendliness
- 76/100