llvm / llvm/llvm-project

[InstCombine] Missed fold: unsigned icmp (add nuw X, C1), (add nuw Y, C2)

Open
#220,238 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

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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.