llvm / llvm/llvm-project

[InstCombine] Remove redundant overflow select before umin clamp

Open
#199,806 0 comments 0 reactions 1 assignee Claimed by @ParkHanbum View on GitHub
llvm:instcombine missed-optimization
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

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.