[InstCombine] Remove redundant overflow select before umin clamp
- Dominant language
- LLVM
- Stars
- 40.5k
- Forks
- 18.7k
- PR merge metrics
- PR metrics pending
Description
InstCombine misses a fold for an unsigned growth pattern where an overflow guard is followed by a `umin` clamp.
### Reproducer
```llvm
define i8 @src(i8 %x, i8 %C, i8 %K) {
entry:
%u = call i8 @llvm.umax.i8(i8 %x, i8 %C)
%sum = add nsw i8 %u, %x
%ov = icmp ult i8 %sum, %x
%clamp = call i8 @llvm.umin.i8(i8 %sum, i8 %K)
%r = select i1 %ov, i8 %K, i8 %clamp
ret i8 %r
}
```
### Currenttly InstCombine keeps the select.
Expected result
```llvm
define i8 @tgt(i8 %x, i8 %C, i8 %K) {
entry:
%u = call i8 @llvm.umax.i8(i8 %x, i8 %C)
%sum = add nsw i8 %u, %x
%clamp = call i8 @llvm.umin.i8(i8 %sum, i8 %K)
ret i8 %clamp
}
```
### General formula
```
C <=u SignBit && K <=u SignBit
=>
select (add_nsw(umax(x, C), x) =u SignBit; otherwise x + u cannot unsigned-overflow.
So on the overflow arm:
```
x >=u SignBit
=> u = x
=> sum = add nsw x, x
```
Since the add nsw is defined, sum must remain in the signed-negative range:
```
sum >=u SignBit
Given K <=u SignBit:
K <=u sum
=> umin(sum, K) == K
```
Therefore the true arm value K is already equal to clamp, so the select is redundant.
Notes
The nsw flag is required. Without nsw, %sum may wrap to a small unsigned value, and umin(%sum, K) may differ from K.
Alive Proof : https://alive2.llvm.org/ce/z/2UEYwP
Compiler-explorer sample & perf : https://compiler-explorer.com/z/3nvj53rcv
RealWorld Usage : https://github.com/dtcxzyw/llvm-opt-benchmark-nightly/pull/379/changes
Contributor guide
Assessment
This issue has not been assessed yet.