llvm / llvm/llvm-project

[InstCombine] Add folds like UCmp(a ±ⁿᵘʷ n, b ±ⁿᵘʷ n) → UCmp(a, b)

Open
#216,127 4 comments 0 reactions 0 assignees View on GitHub
good first issue llvm:instcombine missed-optimization
Dominant language
LLVM
Stars
40.5k
Forks
18.7k
PR merge metrics
PR metrics pending

Description

So long as no overflow happens, `llvm.[su]cmp` are scale- and translation-invariant, but those folds seem to be missing.

For example, these two currently don't fold:
```llvm
define noundef i8 @demo_addu(i12 noundef %a, i12 noundef %b, i12 noundef %n) unnamed_addr #0 {
start:
%an = add nuw i12 %a, %n
%bn = add nuw i12 %b, %n
%_0 = call i8 @llvm.ucmp.i8.i12(i12 %an, i12 %bn)
ret i8 %_0
}

define noundef i8 @demo_mulu(i12 noundef %a, i12 noundef %b, i12 noundef range(i12 1, 0) %n) unnamed_addr #0 {
start:
%an = mul nuw i12 %a, %n
%bn = mul nuw i12 %b, %n
%_0 = call i8 @llvm.ucmp.i8.i12(i12 %an, i12 %bn)
ret i8 %_0
}
```

But Alive2 confirms that they should collapse, like
```llvm
define i8 @src(i12 noundef %a, i12 noundef %b, i12 noundef %n) noundef {
start:
%an = add nuw i12 noundef %a, noundef %n
%bn = add nuw i12 noundef %b, noundef %n
%_0 = ucmp i8 i12 %an, %bn
%#range_0_%_0 = !range i8 %_0, i8 255, i8 2
ret i8 %#range_0_%_0
}
=>
define i8 @tgt(i12 noundef %a, i12 noundef %b, i12 noundef %n) noundef {
start:
%_0 = ucmp i8 i12 noundef %a, noundef %b
%#range_0_%_0 = !range i8 %_0, i8 255, i8 2
ret i8 %#range_0_%_0
}
Transformation seems to be correct!
```

And
```llvm
define i8 @src(i12 noundef %a, i12 noundef %b, i12 noundef %n) noundef {
init:
%#range_0_%n = !range i12 noundef %n, i12 1, i12 0, welldefined
br label %start

start:
%an = mul nuw i12 noundef %a, %#range_0_%n
%bn = mul nuw i12 noundef %b, %#range_0_%n
%_0 = ucmp i8 i12 %an, %bn
%#range_1_%_0 = !range i8 %_0, i8 255, i8 2
ret i8 %#range_1_%_0
}
=>
define i8 @tgt(i12 noundef %a, i12 noundef %b, i12 noundef %n) noundef {
start:
%_0 = ucmp i8 i12 noundef %a, noundef %b
%#range_0_%_0 = !range i8 %_0, i8 255, i8 2
ret i8 %#range_0_%_0
}
Transformation seems to be correct!
```

But also loads of other things too, like
- `udiv exact` https://alive2.llvm.org/ce/z/uqFhT2
- `sub nuw` https://alive2.llvm.org/ce/z/sxqeFt
- `shl nuw` https://alive2.llvm.org/ce/z/Ec5gUr
- `lshr exact` https://alive2.llvm.org/ce/z/i3_7s5
- And of course all the `nsw`+`llvm.scmp` equivalents
- Easy for `add nsw` https://alive2.llvm.org/ce/z/v3NT4u and `sub nsw` https://alive2.llvm.org/ce/z/4o8aZu
- More care needed for `mul nsw` because the naïve one has sign problems
- But SCmp(a ×ⁿˢʷ POS, b ×ⁿˢʷ POS) → SCmp(a, b) works https://alive2.llvm.org/ce/z/9Z5H6z
- As does SCmp(a ×ⁿˢʷ NEG, b ×ⁿˢʷ NEG) → SCmp(b, a) https://alive2.llvm.org/ce/z/ESq3VL

---

TL/DR: All these folds that exist for `icmp` should be added to `ucmp` & `scmp` as well.

Contributor guide

Open the contributing guide

Research direction

Start in InstCombine by locating the existing icmp folds referenced in the issue, then compare their applicability to llvm.ucmp and llvm.scmp. Done means the listed arithmetic and shift cases fold while preserving the stated overflow, exactness, range, and sign conditions.

Written by the indexing model from the issue text.

Assessment

Domain
compilers
Issue type
Feature
Difficulty
4/5
Estimated time
3-5 days
Activity status
Quiet
Clarity
Mostly clear
Newbie friendliness
48/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.