llvm / llvm/llvm-project

[InstSimplify] Simplify same-condition select pair comparisons

Open
#202,066 1 comment 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

InstSimplify misses a fold for comparisons between two `select`s that use the same condition.

Reduced example:

```llvm
declare void @llvm.assume(i1)
declare void @use32(i32)

define i1 @same_cond_select_pair_false(i1 %c, i32 %x, i32 %y1, i32 %y2) {
entry:
%restrict = icmp ult i32 %y1, %y2
call void @llvm.assume(i1 %restrict)

%lo = select i1 %c, i32 %y1, i32 %x
%hi = select i1 %c, i32 %y2, i32 %x

call void @use32(i32 %lo)
call void @use32(i32 %hi)

%r = icmp ult i32 %hi, %lo
ret i1 %r
}

define i1 @same_cond_select_pair_true(i1 %c, i32 %x, i32 %y1, i32 %y2) {
entry:
%restrict = icmp ult i32 %y1, %y2
call void @llvm.assume(i1 %restrict)

%lo = select i1 %c, i32 %y1, i32 %x
%hi = select i1 %c, i32 %y2, i32 %x

call void @use32(i32 %lo)
call void @use32(i32 %hi)

%r = icmp ule i32 %lo, %hi
ret i1 %r
}
```
With the assumption %y1 ult %y2, the selected pair is always ordered:

when %c is true, %lo = %y1 and %hi = %y2
when %c is false, %lo = %x and %hi = %x
So %hi ult %lo is always false, and %lo ule %hi is always true.

However, running:
```
opt -passes=instsimplify -S
```
does not fold the compares when the extra @use32 calls are present.

If the extra uses of %lo and %hi are removed, the compares are folded to constants. This suggests the current fold is sensitive to whether the selects have additional uses.

Expected result:
```llvm
ret i1 false
```
for same_cond_select_pair_false, and:
```llvm
ret i1 true
```
for same_cond_select_pair_true.

AliveProof : https://alive2.llvm.org/ce/z/BvHq8a
Compiler-explorer sample & perf : https://compiler-explorer.com/z/x7vY1T6q4
RealWorld Usage : https://github.com/dtcxzyw/llvm-opt-benchmark-nightly/pull/437/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.