InstCombine range folding gap due to non-canonical logical-and form
- 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
Assessment
This issue has not been assessed yet.