llvm / llvm/llvm-project

[ValueTracking] A strict range on x - y does not establish x != y

Open
#223,345 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

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

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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.