[SimplifyCFG] Switch-to-select fold ignores range from llvm.assume
- Dominant language
- LLVM
- Stars
- 40.5k
- Forks
- 18.7k
- PR merge metrics
- PR metrics pending
Description
For the following LLVM IR, the switch returns true for `%x == 1` or `%x == 3`:
```llvm
declare void @llvm.assume(i1 noundef)
define i1 @src(i8 %x) {
entry:
%bound = icmp ule i8 %x, 3
call void @llvm.assume(i1 %bound)
switch i8 %x, label %other [
i8 1, label %odd
i8 3, label %odd
]
other:
br label %exit
odd:
br label %exit
exit:
%r = phi i1 [ false, %other ], [ true, %odd ]
ret i1 %r
}
```
On current LLVM trunk, `opt -O3` keeps an add, an and, and a comparison
(Godbolt: https://godbolt.org/z/h3d7s8Ksh):
```llvm
define i1 @src(i8 %x) {
entry:
%bound = icmp ult i8 %x, 4
call void @llvm.assume(i1 %bound)
%dec = add nsw i8 %x, -1
%masked = and i8 %dec, -3
%r = icmp eq i8 %masked, 0
ret i1 %r
}
```
The assumption restricts `%x` to `[0, 4)`, where the switch result is the low bit of `%x`.
Alive2 verifies the replacement with a truncation (https://alive2.llvm.org/ce/z/YdLaeq):
```llvm
%r = trunc i8 %x to i1
ret i1 %r
```
If the same range is attached to `%x`, like the below snippet:
```llvm
define i1 @range_control(i8 range(i8 0, 4) %x) {
entry:
switch i8 %x, label %other [
i8 1, label %odd
i8 3, label %odd
]
other:
br label %exit
odd:
br label %exit
exit:
%r = phi i1 [ false, %other ], [ true, %odd ]
ret i1 %r
}
```
O3 performs the expected fold:
```llvm
define i1 @range_control(i8 range(i8 0, 4) %x) {
entry:
%r = trunc i8 %x to i1
ret i1 %r
}
```
The problem appears to be in `foldSwitchToSelect()`. Its compact bit-test path calls `computeKnownBits(Condition, DL)` without an `AssumptionCache` or a context instruction, so it sees the argument `range` attribute but not the dominating `llvm.assume` and falls back to the larger subtract-and-mask form.
A possible fix is to pass `Options.AC` and the switch context to `trySwitchToSelect()` and `foldSwitchToSelect()`, then call `computeKnownBits(Condition, DL, AC, SI)` as the preceding dead-case elimination does.
This should be a sibling issue of #220849. #220849 is in use of `computeConstantRange()`, while this issue is in use of `computeKnownBits()`.
Contributor guide
Research direction
Start in foldSwitchToSelect() and trySwitchToSelect(), comparing the existing dead-case elimination call to computeKnownBits() with the compact bit-test path. Use the supplied IR with llvm.assume and run opt -O3 to observe the current subtract-and-mask output. Done means the assumed range enables the switch to fold to the equivalent truncation, as in the range-attribute example.
Written by the indexing model from the issue text.
Assessment
- Domain
- compilers
- Issue type
- Bug
- Difficulty
- 3/5
- Estimated time
- 1-2 days
- Activity status
- Active
- Clarity
- Clearly specified
- Newbie friendliness
- 72/100