<table border="1" cellspacing="0" cellpadding="8">
    <tr>
        <th>Issue</th>
        <td>
            <a href=https://github.com/llvm/llvm-project/issues/202212>202212</a>
        </td>
    </tr>

    <tr>
        <th>Summary</th>
        <td>
            Fold `switch(select(x == C, K, x))` into `switch(x)` with a remapped case
        </td>
    </tr>

    <tr>
      <th>Labels</th>
      <td>
            new issue
      </td>
    </tr>

    <tr>
      <th>Assignees</th>
      <td>
      </td>
    </tr>

    <tr>
      <th>Reporter</th>
      <td>
          ParkHanbum
      </td>
    </tr>
</table>

<pre>
    ## Summary

LLVM misses a switch simplification where the switch condition is a select that
only remaps one integer value before dispatch:

```llvm
%cmp = icmp eq T %x, C
%key = select i1 %cmp, T K, T %x
switch T %key, label %default [
  T K, label %case_k
  ...
]
```

This can be rewritten as a switch on the original value:

```llvm
switch T %x, label %default [
  T C, label %case_k
  T K, label %case_k
  ...
]
```

If `C` is already present as a switch case, that case should be retargeted to
the destination selected by `K`.  If `C` is absent and `K` maps to the default
destination, switching directly on `%x` is sufficient without adding a new
explicit case.

This removes the pre-switch compare/select remapping sequence and exposes a
cleaner switch key to later simplification and lowering.

## Missed Pattern

```llvm
declare void @case0()
declare void @case1()
declare void @case2()
declare void @case3()
declare void @default_case()

define void @src(i32 %x) {
entry:
  %is_c = icmp eq i32 %x, 3
  %key = select i1 %is_c, i32 0, i32 %x
  switch i32 %key, label %default [
    i32 0, label %case0
    i32 1, label %case1
    i32 2, label %case2
  ]

case0:
 call void @case0()
  ret void

case1:
  call void @case1()
  ret void

case2:
  call void @case2()
  ret void

default:
  call void @default_case()
  ret void
}
```

## Expected Result

```llvm
define void @tgt(i32 %x) {
entry:
  switch i32 %x, label %default [
    i32 0, label %case0
    i32 1, label %case1
    i32 2, label %case2
    i32 3, label %case0
  ]

case0:
  call void @case0()
  ret void

case1:
 call void @case1()
  ret void

case2:
  call void @case2()
  ret void

default:
  call void @default_case()
  ret void
}
```

## Correctness

For every concrete non-poison value of `%x`, the rewrite preserves the selected
destination:

- If `%x == C`, the source switch dispatches on `K`, so the target must dispatch
  `C` to the same destination as `K`.
- If `%x != C`, the source switch dispatches on `%x`, so all other switch cases
  and the default destination are unchanged.

Important legality details:

- the select condition must be an equality compare against the same SSA value
  used by the non-remapped select arm;
- the remapped select arm must be an integer constant of the switch condition
 type;
- switch, select, and compare operand types must match;
- an existing `C` case must be retargeted rather than duplicated;
- branch-weight metadata should be dropped or rebuilt because case destinations
  and case count can change.

A conservative first form would require the `select` and its equality compare
to each have one use, so the compare/select sequence is fully removed.

## Corpus Evidence

In an optimized benchmark corpus, this residual pattern still appears after the
usual optimizer pipeline:

- 161 total `select`-before-`switch` remap candidates;
- 150 candidates where the transform adds a new remapped case;
- 11 candidates where an existing case would be retargeted;
- 62 one-use add-new-case candidates;
- 34 one-use add-new-case candidates with at least three switch cases.

The higher-signal candidates appear in several independent projects, including
`typst-rs`, `libigl`, `opencv`, `ffmpeg`, `postgres`, and `clap-rs`.  Large
representative switches include 5-case, 9-case, and 12-case forms.

## Performance Notes

A sink-shaped POC was compared before and after the rewrite.  This form lets
normal cleanup merge the switch destinations into a common tail call, avoiding
artificial side effects that would otherwise distort the backend comparison.

In this representative shape, the rewritten form consistently reduces static
instructions, uOps, cycles, and estimated throughput cost across the tested x86
CPUs:

| CPU | POC | static inst | cycles | uOps | throughput |
| --- | --- | ---: | ---: | ---: | ---: |
| Haswell | i32 3-case sink | 17 -> 13 | 457 -> 358 | 1800 -> 1400 | 4.5 -> 3.5 |
| Skylake | i32 3-case sink | 17 -> 13 | 454 -> 333 | 1700 -> 1400 | 4.0 -> 2.5 |
| Alder Lake | i32 3-case sink | 17 -> 13 | 306 -> 188 | 1300 -> 1000 | 2.2 -> 1.7 |
| Zen 4 | i32 3-case sink | 17 -> 13 | 405 -> 306 | 1700 -> 1300 | 3.5 -> 3.0 |

This suggests the transform is useful, but should start with a conservative
profitability policy.  A good initial subset is one-use `icmp`/`select`,
add-new-case remaps, and switches with at least three cases.  Two-case forms and
target-sensitive cases can be broadened later with additional backend coverage.


AliveProof : https://alive2.llvm.org/ce/z/PGByK2
Compiler-explorer sample & perf : https://compiler-explorer.com/z/s6rccbeoM
RealWorld Usage : https://github.com/dtcxzyw/llvm-opt-benchmark/blob/83bfde85e2ee64eb7ef7d7532404877b5c48a875/bench/postgres/optimized/interval.ll#L204


</pre>
<img width="1" height="1" alt="" src="http://email.email.llvm.org/o/eJzUWE2P2zjS_jXsS8GGTPmrD33wOON3Bsm805hkdoG9BBRVlrhNiQpJ2e38-kWRlC13u5PMAHtYwIBFFauKrM-nJJxTVYv4wBY_scW7O9H72tiHR2GffhFt0Td3hSlPD4znjOfwsW8aYU8s27Bs8-HDP36DRjmHDgS4o_KyBqeaTqu9ksIr08KxRovgaxzo0rSlCiQVuFCj9OBr4Vm2Ma0-gcVGdA5Mi6BajxVaOAjdIxS4NxahVK4TXtYs38RzsGUWf1ofGlrzhWw6YPk7UPSAX-ATML54ZnwL27jhCU9hQ9KvZhC5aMsneB__Ak-2SScP6yc8EU2LAjWtS9yLXnsg62UbGHjPdCkcfn4KpOl0SroX78ZHjjf4VCsHUrRQIFg8WuU9tiBGZjVtMKKxqlKt0NEib1pgfOLn75x3-9Z5_95Vft0DW2ZbtsyCg7VFUZ6gs-iw9VdXInmkgHwfFuBq0-syGsELW6HHErxh2YbuXqLzqo1hFd2GJRQnUveeLbMpwAvdRVTZlsMWCIHlDURxwRIs24wE03ni8VRbQaksSq9PZH26IBkzynb9fq-kIvlH5WvTexBlSTwCWjyybIPPnVZSxZtNR2622JgDunCGzuLknBdNJywyvkshGdKgI5EOv_TYSgxXwefOhIRj2UZqFC3awaAU096AFp7eXechsWpzRKvaKp0mpfRvlMAlPArv0ba346lEqYVFOBhVAptndKeM8TXj929QZ9-k8m9S8zepyWefY-ikTWHfXrWXbc5Kxtcq5yn-74GtKNyx9fYUkwaIpNxneVUmLixbyIddN0sFsdIu4siGh1QvYHBIeve9mgEXKVfJlo2os1fU2YjKX1F5PH3M0GwTxcWbS6H1G54ESrxAu7DNBoO94pt9k4-_ycff5Bty8hbnTd9fC1jdqEcpyn9-7mLB-ANdzPqbYX4VRr7y3w-ja1d_u9j-9xwdqfkbkm-Gwd-Ng__pMNgaSyW9Refi-52xgAe0JwIm0qJHaE076Yxypk24w-xH1T92rKFNY-xsdijoQ1960VWGPj1JLYpkUU2hsrIdCXWmt_IMlQaggy41oPdpq4sdLLZIaHrnL6Ao-Ds1wdTpnGiuu6dw56b56lB89hcPNbKLM0CuMr6-NCXykwunohY0arzXJ7IIfStr0VZYpv70a9MZ60XrQWMltPInKNELpd3Inhejj5BlsEhB_RLwSx9ZU38FUQnVOn8xzMePm4Sm6JC9i6CCyBQIsQtjOSgRtmH5T2fVN8hj7QN-laZ14SZmfxMLk2p_6nAQHenBpEEuPZH5hkuYDm0w56lDFxU2ERJHfrr4syLzVudgCAhrONsIX1kR3OVr0ULZE2gRFMBJUmFFK-vJEVVVe2jQi1J4MUJqpTXBAMaCxaJXmuRL0TuMGkdevoRBoEjTtz6g3uj35PZNsBbag_DqgLBX1nnYG9vAMei0-KVXaaZgyywZaJkFwcq7Vy4n-GgAhayhFgcMg0UfoWdKpFfY64y4lIN9r-NQYg7n0LxUk6538PNBlbQ7hS2BLTCdV436SsGErawbYZ9Ahu0xrQIQdKrshYYuQi9wXmkNFE_COhB7H9xCYntH-waZFjrVoVYtjhJhtpyBN17oK6NM4sw0oXcxppZZDFoyfKlK4dENvp4tstHb0ejmrWhdcIEoSxch7iX0QyUeRMxeSxgHY3D88TXKH_iXnNwzoegRZTlp8TiJsfLqsPn8ezsDMgdB5UOEhLeIV1XpjMoRalXVaCc0Cgs9lhG9AYpGjgNaoUG1JXbYloT9O2v-jdIHn6pW6p5GgNh8_KlzfmJdKo0EMlShKn1Zmw5bebis9_umw-qy7ozzlcVBQppjpBZdFDsF-EDmY9nGYhqwYs7ES6JLZ0JYTIZh6_78RPJmPBqNfOuuY_sRLb0VlAX_bzy6ITudap8mrhbk-sfft3AUbkigchjRSfY5fodWOQUIA1AIJI2eJLakQkMYZPoOGrTV1deCcfWgampAkLKGxmGhdIAG4TLU-6PthfU09iihwakSAfd7clEcM2PohQZ1VC58S_DGxm5QCPmE5yJL_X96zuiUsNdWJhtcwwGa2sP1qIQp57H1oXaUvUQHjhglyzbUgGwvY03kW-h_78K_PEmNbnAOXb0RYQSuremruuupyTkPQlrjIuDw6GjH83rJss328c9Lb2SrLWwf_wT6Jz_RfzwBhAZI66gwPNIZwsNIGVttk6DJZAIv_lm--aHHJOEX4Y6odSAGrBojj6IpvJutYMLyn2GWh-V8kdb5Yh3p6yxLO-ZZFvdMF2nPdDHS9PHppMUT_rimeZKS54l-Q1N6w680bXSJFj78BWV5tkzrdbpWflaWJWV8ytOb6Wqk7F_YwvyHL5UNpsmWLy-VJz35xXzZoCd9o3B9VaHz7kX1V44a574PKVf0foABzgvrU7m96t4s23TW7JUXhQotuTNaydMUYAOVMSWoVvmQqX3h0JOCoaizZUZTeSh-u3FLY5xOelXz4xfDIW_O1e9W_Y-FH-DT0YxKH_ERTAjdaOKwdSqkeNg9fJgrrBEltlimLyxRfBkRnNCj-kGN4oxnqGhqdcBHa2iQyDdQe9-FPOU7xneCiHxKI-jU2IrxnSQk8pXx3eP__XR6TwPe1jSd0mgn-NxpYwldi6bTCIwvoUN7S658yTOVpkmC3dJKWaD5jWWbP1DofxqrS_jTiQpvSKqUr_sisZdePn89HRnf0YknpvOTM8JhfFdoUzC-W-fFvsT1Ajnico7FCvercrXI-Tybr1erYiHna7FeLYiDuBnfndsd353BE-M7gtD2IPSUCn3-gWfzaNO78iEv7_N7cYcPs9U6W8_Xcz67qx-W2f6-mO2F4KtiNVsv1kKuxbIU5TxfFvlK3KkHnvFltsxWs2W2ymbT1RwLWcxWC-SZlGvO5hk2QumzT-6Ucz0SG5_xuzBgu_C9nHNCQoHKOGeLd3f2IZil6CvH5plWzruLGK-8xoed0aGTDyB_PWD89Wgm5Nv49fWZBlx-Hz47Uvsb8z0nQkq8K0B211v98A03hi8eyYcJxZCx6SbkgXTVwwP_TwAAAP__zp-GRg">