[InstCombine] Missed fold: unsigned icmp (add nuw X, C1), (add nuw Y, C2)
- Dominant language
- LLVM
- Stars
- 40.5k
- Forks
- 18.7k
- PR merge metrics
- PR metrics pending
Description
The `foldICmpBinOp` can subtract a constant from both sides of an `icmp` between two `add`s, and combined with the existing `icmp (A+B), (A+D) -> icmp B, D` fold that cancels a common operand out of a comparison of two sums. However this is not working for the unsigned case.
Reproducer:
`opt -passes=instcombine`
```llvm
declare void @use(i32)
define i1 @unsigned_nuw(i32 %base, i32 %off) {
%a = add nuw i32 %base, %off
%b = add nuw i32 %a, 4
%c = add nuw i32 %base, 62
%r = icmp ule i32 %b, %c
call void @use(i32 %a) ; the inner add is live, e.g. as an address
ret i1 %r
}
define i1 @signed_nsw(i32 %base, i32 %off) {
%a = add nsw i32 %base, %off
%b = add nsw i32 %a, 4
%c = add nsw i32 %base, 62
%r = icmp sle i32 %b, %c
ret i1 %r
}
```
This result in `@unsigned_nuw` is returned unchanged, while `@signed_nsw` becomes `%r = icmp slt i32 %off, 59`. The icmp eq version folds too, without needing any no-wrap flags.
Instead it should be possible for `@unsigned_nuw` to become `%r = icmp ult i32 %off, 59`, with the add nuw for the address left in place for its other use.
Alive2: https://alive2.llvm.org/ce/z/bcHMdf
The reduction happens in two steps, and only the first one is missing. Feeding the intermediate form to InstCombine gives the final result today:
```llvm
define i1 @after_the_missing_step(i32 %base, i32 %off) {
%a = add nuw i32 %base, %off
%c = add nuw i32 %base, 58 ; 62 - 4
%r = icmp ule i32 %a, %c ; -> icmp ult i32 %off, 59
ret i1 %r
}
```
In llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp, in
InstCombinerImpl::foldICmpBinOp:
```C++
// if C1 has greater magnitude than C2:
// icmp (A + C1), (C + C2) -> icmp (A + C3), C
// s.t. C3 = C1 - C2
...
if (A && C && NoOp0WrapProblem && NoOp1WrapProblem &&
(BO0->hasOneUse() || BO1->hasOneUse()) && !I.isUnsigned()) {
```
The guard `!I.isUnsigned()` has been there since the fold was added in b81cd63c4b7d (2013), whose commit message only discusses signed examples.
This was found with an out of tree frontend. This is the shape this frontend emits for a bounds check on an address formed as base plus a running offset: the address is materialised once because the memory access needs it, and the length is added on top for the check, while the limit is another offset from the same base. The base then appears on both sides of the comparison and nothing cancels it, so the comparison stays symbolic and range information about the offset cannot be used.
Contributor guide
Research direction
Start in llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp at InstCombinerImpl::foldICmpBinOp, and run opt -passes=instcombine on the supplied LLVM reproducer. Inspect the unsigned guard and verify that the unsigned_nuw comparison folds to icmp ult i32 %off, 59 while the live nuw address add remains in place.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- cpp
- Domain
- compilers
- Issue type
- Bug
- Difficulty
- 3/5
- Estimated time
- 1-2 days
- Activity status
- Active
- Clarity
- Clearly specified
- Newbie friendliness
- 76/100