[InstCombine] Fold icmp ult (uadd.sat X, C), C2 to icmp ult X, (C2 - C)
- Dominant language
- LLVM
- Stars
- 40.5k
- Forks
- 18.7k
- PR merge metrics
- PR metrics pending
Description
Description
I would like to propose a transformation that simplifies a check on the result of uadd.sat into a simple range check on the input, when the operands are constants.
If we check whether a saturated unsigned addition is strictly less than a constant C2, and we know that C2 u> C, we can elide the saturation logic entirely.
Pattern:
```llvm
%sat = call i8 @llvm.uadd.sat.i8(i8 %x, i8 %c)
%cmp = icmp ult i8 %sat, %c2
```
Preconditions:
C and C2 are constants.
X+C will not overflow
C2 u> C (Unsigned comparison).
(Note: If C2 u<= C, the result is always false because the minimum value of uadd.sat(X, C) is C.)
Reasoning
LLVM currently expands uadd.sat(X, Y) pred Z based on whether the saturation value (-1) satisfies the predicate.
Current logic for ult:
Since (-1 u< C2) is always false (because C2 <= -1 for any integer type), the expression expands to the "no saturation" check:
```
(X u< ~C) && ((X + C) u< C2)
```
Proposed Simplification:
We can simplify this conjunction based on the relationship between C2 and -1 (MAX):
The term ((X + C) u< C2) implies ((X + C) u< -1) because C2 <= -1 is always true.
The term (X u< ~C) is equivalent to (X + C) does not overflow, which effectively means (X + C) u<= -1 (and not wrapped).
Since C2 acts as a tighter upper bound than -1, the condition ((X + C) u< C2) strictly subsumes (X u< ~C).
Derivation:
```
(X u< ~C) && ((X + C) u< C2)
=> ((X + C) u< -1) && ((X + C) u< C2) ; (X u< ~C) implies sum is not overflowed/saturated
=> (X + C) u< C2 ; Intersection of (Val < MAX) and (Val < C2) is (Val < C2)
=> X u< C2 - C ; Valid because we established no overflow occurs in this range
```
Example IR
Source:
```llvm
define i1 @src(i8 %x) {
; C = 10, C2 = 30
; uadd.sat(X, 10) < 30
%add = call i8 @llvm.uadd.sat.i8(i8 %x, i8 10)
%cmp = icmp ult i8 %add, 30
ret i1 %cmp
}
```
Target:
```llvm
define i1 @tgt(i8 %x) {
; X < 30 - 10 => X < 20
%cmp = icmp ult i8 %x, 20
ret i1 %cmp
}
```
Alive proof : https://alive2.llvm.org/ce/z/P4JmoP
Contributor guide
Assessment
This issue has not been assessed yet.