llvm / llvm/llvm-project

[ValueTracking] Fails to fold a == b under assume(a == b + C) for nonzero constant C

Open
#219,147 1 comment 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 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

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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.