llvm / llvm/llvm-project

InstCombine range folding gap due to non-canonical logical-and form

Open
#176,554 0 comments 0 reactions 0 assignees View on GitHub
llvm:instcombine missed-optimization
Dominant language
LLVM
Stars
40.5k
Forks
18.7k
PR merge metrics
PR metrics pending

Description

### Description

This is a missed optimization caused by a non-canonical logical-and form. InstCombine is able to fold two range comparisons when the logical-and is expressed as a chain of `select` instructions, but fails to do so once part of the expression is canonicalized to an `and`. This is not a correctness issue.

### Buggy Program

```llvm
define i1 @src(i1 %cond, i32 %y) {
%cmp1 = icmp samesign ugt i32 %y, 65535
%sel11 = and i1 %cond, %cmp1
%cmp2 = icmp samesign ult i32 %y, 1114112
%sel2 = select i1 %sel11, i1 %cmp2, i1 false
ret i1 %sel2
}
```

InstCombine does not fold the two comparisons in this form.

### Canonical form that is optimized

If the same logic is expressed using nested `select` instructions, InstCombine successfully folds the two comparisons into a single range check:

```llvm
define i1 @src(i1 %cond, i32 %y) {
%cmp1 = icmp samesign ugt i32 %y, 65535
%sel1 = select i1 %cond, i1 %cmp1, i1 false
%cmp2 = icmp samesign ult i32 %y, 1114112
%sel2 = select i1 %sel1, i1 %cmp2, i1 false
ret i1 %sel2
}
```

The program above can be folded into the following form:

```llvm
define i1 @tgt(i1 %cond, i32 %y) {
%1 = add i32 %y, -65536
%2 = icmp ult i32 %1, 1048576
%sel2 = select i1 %cond, i1 %2, i1 false
ret i1 %sel2
}
```

### Analysis

The missed optimization appears to be due to a canonicalization gap. InstCombine's range folding relies on select-based logical-and forms (`select A, B, false`). Once part of the logical-and is lowered to an `and`, the equivalent pattern is no longer recognized, even though the semantics remain the same. This suggests that either a prior canonicalization step is required, or that this limitation is intentional in the current matcher.

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.