llvm / llvm/llvm-project

[InstCombine] Fold `llvm.usub.sat` result-vs-LHS comparisons to zero/nonzero tests

Open
#213,832 1 comment 0 reactions 1 assignee Claimed by @haramj View on GitHub
llvm:instcombine missed-optimization
Dominant language
LLVM
Stars
40.5k
Forks
18.7k
PR merge metrics
PR metrics pending

Description

### Summary

LLVM misses a simple InstCombine fold for comparisons between the result of
`llvm.usub.sat` and its original left-hand side when the RHS is a nonzero
constant.

Specifically, for `C != 0`:

```llvm
%s = call iN @llvm.usub.sat.iN(iN %x, iN C)
%cmp = icmp eq iN %s, %x
```

can be folded to:

```llvm
%cmp = icmp eq iN %x, 0
```

Similarly,

```llvm
%s = call iN @llvm.usub.sat.iN(iN %x, iN C)
%cmp = icmp ult iN %s, %x
```

can be folded to:

```llvm
%cmp = icmp ne iN %x, 0
```

### Reasoning

For unsigned saturating subtraction,

```text
usub.sat(x, C) =
(x < C) ? 0 : (x - C)
```

when `C != 0`.

Therefore,

- `usub.sat(x, C) == x` iff `x == 0`
- `usub.sat(x, C) < x` iff `x != 0`

These identities hold regardless of whether the `llvm.usub.sat` result has
additional uses. If the compare is the only use, subsequent dead code
elimination may also remove the intrinsic call.

### Minimal IR

```llvm
declare i64 @llvm.usub.sat.i64(i64, i64)

define i1 @eq_fold(i64 %x) {
entry:
%sat = call i64 @llvm.usub.sat.i64(i64 %x, i64 10)
%cmp = icmp eq i64 %sat, %x
ret i1 %cmp
}

define i1 @ult_fold(i64 %x) {
entry:
%sat = call i64 @llvm.usub.sat.i64(i64 %x, i64 10)
%cmp = icmp ult i64 %sat, %x
ret i1 %cmp
}
```

### Notes

This fold is also valid when the `llvm.usub.sat` result has additional uses.
In such cases, only the comparison is canonicalized, while the intrinsic
remains live.

### Suggested initial scope

- `llvm.usub.sat`
- constant RHS
- `C != 0`
- comparisons against the original LHS
- `icmp eq`
- `icmp ult`

Other predicates (e.g. `ne` or `uge`) could potentially be derived as logical
inverses, but are outside the scope of this report.

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.