llvm / llvm/llvm-project

[InstCombine] Fold icmp ult (uadd.sat X, C), C2 to icmp ult X, (C2 - C)

Open
#169,763 2 comments 0 reactions 1 assignee Claimed by @dongwooklee96 View on GitHub
llvm:instcombine missed-optimization
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

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.