llvm / llvm/llvm-project

[InstCombine][SimplifyCFG] Switch-to-lookup-table emits an unnecessary index offset after InstCombine narrows the switch to `i8`

Open
#221,426 0 comments 0 reactions 0 assignees View on GitHub
llvm:instcombine llvm:transforms missed-optimization
Dominant language
LLVM
Stars
40.5k
Forks
18.7k
PR merge metrics
PR metrics pending

Description

A `switch` whose condition is known to be in `[0, N)` with `128 <= N <= 256`, and whose arms all yield a constant (a function pointer in my case), is lowered to a lookup table indexed by `condition ^ 128` instead of by `condition`. The `xor` is one extra instruction on every execution of the switch and is the only difference from the same switch with `N < 128` or `N > 256`.

This is the dispatch step of a token-threaded interpreter, where the `switch` runs once per interpreted instruction and the surrounding handler is about ten instructions, so the extra instruction is a measurable fraction of the hot path.

Reproduction (Rust)

```rust
pub type Handler = unsafe extern "C" fn() -> u64;

macro_rules! define {
($name:ident, $select_in_place:ident, $select_copy:ident, [$($variant:ident),*]) => {
#[repr(u16)]
#[derive(Clone, Copy)]
pub enum $name { $($variant { operands: [u8; 6] }),* }

unsafe extern "C" { $(fn $variant() -> u64;)* }

// The tag is loaded in place, so it carries its value range
#[unsafe(no_mangle)]
pub fn $select_in_place(e: &$name) -> Handler {
match *e { $($name::$variant { .. } => $variant),* }
}

// The tag is extracted from a copy of the whole enum, which carries no value range
#[unsafe(no_mangle)]
pub fn $select_copy(e: &$name) -> Handler {
let copy = *e;
match copy { $($name::$variant { .. } => $variant),* }
}
};
}

define!(
E150,
select_150,
select_150_copy,
[
A0, A1, A2, A3, A4, A5, A6, A7, A8, A9, A10, A11, A12, A13, A14, A15, A16, A17, A18, A19,
A20, A21, A22, A23, A24, A25, A26, A27, A28, A29, A30, A31, A32, A33, A34, A35, A36, A37,
A38, A39, A40, A41, A42, A43, A44, A45, A46, A47, A48, A49, A50, A51, A52, A53, A54, A55,
A56, A57, A58, A59, A60, A61, A62, A63, A64, A65, A66, A67, A68, A69, A70, A71, A72, A73,
A74, A75, A76, A77, A78, A79, A80, A81, A82, A83, A84, A85, A86, A87, A88, A89, A90, A91,
A92, A93, A94, A95, A96, A97, A98, A99, A100, A101, A102, A103, A104, A105, A106, A107,
A108, A109, A110, A111, A112, A113, A114, A115, A116, A117, A118, A119, A120, A121, A122,
A123, A124, A125, A126, A127, A128, A129, A130, A131, A132, A133, A134, A135, A136, A137,
A138, A139, A140, A141, A142, A143, A144, A145, A146, A147, A148, A149
]
);

define!(
E100,
select_100,
select_100_copy,
[
B0, B1, B2, B3, B4, B5, B6, B7, B8, B9, B10, B11, B12, B13, B14, B15, B16, B17, B18, B19,
B20, B21, B22, B23, B24, B25, B26, B27, B28, B29, B30, B31, B32, B33, B34, B35, B36, B37,
B38, B39, B40, B41, B42, B43, B44, B45, B46, B47, B48, B49, B50, B51, B52, B53, B54, B55,
B56, B57, B58, B59, B60, B61, B62, B63, B64, B65, B66, B67, B68, B69, B70, B71, B72, B73,
B74, B75, B76, B77, B78, B79, B80, B81, B82, B83, B84, B85, B86, B87, B88, B89, B90, B91,
B92, B93, B94, B95, B96, B97, B98, B99
]
);
```

https://rust.godbolt.org/z/16xxsbvTe

`select_150` and `select_100` differ only in the number of variants, and `select_150_copy` is the same match on a copy of the value, which is the workaround.

Compiles to this on x86-64:

```asm
select_100:
movzx eax, word ptr [rdi]
lea rcx, [rip + .Lswitch.table.select_100_copy]
mov rax, qword ptr [rcx + 8*rax]
ret

select_100_copy:
movzx eax, word ptr [rdi]
lea rcx, [rip + .Lswitch.table.select_100_copy]
mov rax, qword ptr [rcx + 8*rax]
ret

select_150:
movzx eax, word ptr [rdi]
xor eax, 128
lea rcx, [rip + .Lswitch.table.select_150]
mov rax, qword ptr [rcx + 8*rax]
ret

select_150_copy:
movzx eax, word ptr [rdi]
lea rcx, [rip + .Lswitch.table.select_150_copy]
mov rax, qword ptr [rcx + 8*rax]
ret
```

LLVM IR shows the difference too:

```llvm
define noundef nonnull ptr @select_150(ptr noalias nofree noundef readonly align 2 captures(none) dereferenceable(8) %e) unnamed_addr {
start:
%_2 = load i16, ptr %e, align 2
%0 = xor i16 %_2, 128
%switch.tableidx = zext nneg i16 %0 to i64
%switch.gep = getelementptr inbounds nuw [8 x i8], ptr @switch.table.select_150, i64 %switch.tableidx
%switch.load = load ptr, ptr %switch.gep, align 8
ret ptr %switch.load
}

define noundef nonnull ptr @select_150_copy(ptr noalias nofree noundef readonly align 2 captures(none) dereferenceable(8) %e) unnamed_addr {
start:
%copy.sroa.0.0.copyload = load i16, ptr %e, align 2
%0 = zext nneg i16 %copy.sroa.0.0.copyload to i64
%switch.gep = getelementptr inbounds nuw [8 x i8], ptr @switch.table.select_150_copy, i64 %0
%switch.load = load ptr, ptr %switch.gep, align 8
ret ptr %switch.load
}
```

The expectation is that both `select_150` and `select_150_copy` compile to the identical machine code.

LLM-generated analysis and possible fixes

## Analysis

Two transforms that are each reasonable on their own combine badly:

1. `InstCombinerImpl::visitSwitchInst` narrows the condition to the smallest legal type that holds every case value, using `computeKnownBits` on the condition. With the `!range` of `[0, 150)` on the load there are 8 known leading zeros in the `i16`, so the switch becomes `switch i8 %trunc` with the case values truncated to `i8`. Case values 128 to 149 are now `-128` to `-107` as signed `i8`.

2. `switchToLookupTable` in SimplifyCFG picks `MinCaseVal` with signed comparison (`CaseVal->getValue().slt(MinCaseVal->getValue())`), so it is `-128` (case 128 before truncation). `shouldUseSwitchConditionAsTableIndex` then refuses the direct index because `MinCaseVal.isNegative()`, and the table index becomes `sub i8 %trunc, -128`, which InstCombine canonicalizes to `xor i8 %trunc, -128` and later widens back to `xor i16 %_2, 128`.

Neither step is wrong, but the narrowing in step 1 destroys the information that all case values are non-negative in the original type, and step 2 then pays for a "negative" minimum that does not exist. For `N < 128` no case value has its top bit set after truncation, and for `N > 256` the switch is not narrowed, which is why only the 128 to 255 range is affected.

## Possible fixes

* In `visitSwitchInst`, do not narrow to a width where the case values change sign: for non-negative case values keep `NewWidth` at least one bit wider than the widest case value, or equivalently compute the width from `ComputeNumSignBits` as the existing TODO in that function suggests. The switch would stay `i16` here, and the backend would narrow the load on its own.
* Alternatively, in `switchToLookupTable`, treat the case values as unsigned when the condition is known non-negative in a wider type (or when `!range`/known bits say the condition is below the table size), so `MinCaseVal` is `0` and the condition indexes the table directly.

The first seems more robust, since it keeps every later pass from seeing case values that only look negative because of the truncation.

Contributor guide

Open the contributing guide

Research direction

Reproduce the difference between select_150 and select_150_copy using the Rust example or the linked Godbolt case. Trace InstCombinerImpl::visitSwitchInst and SimplifyCFG's switchToLookupTable to see how the narrowed i8 cases acquire a negative minimum. Done means the unnecessary xor/index offset is absent while both switches still produce the expected lookup-table dispatch.

Written by the indexing model from the issue text.

Assessment

Tech stack
rust
Domain
compilers
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Active
Clarity
Mostly clear
Newbie friendliness
52/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.