llvm / llvm/llvm-project

[SimplifyCFG] Switch-to-select fold ignores range from llvm.assume

Open
#221,695 0 comments 0 reactions 0 assignees View on GitHub
llvm:transforms missed-optimization
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

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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.