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

    <tr>
        <th>Summary</th>
        <td>
            Missed optimization with a switch with more than 64 branches
        </td>
    </tr>

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

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

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

<pre>
    I was playing with some silly code, and I was wondering why llvm can see an optimization sometimes, but not other times.

[Here](https://godbolt.org/z/eEGMsEsqK) is the code.

The first and second sources are identical except for having `if (x == 64) goto yes;` commented in the first one, while not commented in the second. That makes the first generated switch instruction in the first case as having 64 branches, while in the second it's 65 branches. I thought there was some hardcoded limit, but I could find no such thing after a quick search, so I decided to do some debugging, and I found the following:

In [DataLayout::fitsInLegalInteger](https://github.com/llvm/llvm-project/blob/916bd7d3bb42627f52e2f8ed2f87e08db4960a72/llvm/include/llvm/IR/DataLayout.h#L359) with the partial stack trace:
```cpp
clang.exe!llvm::DataLayout::fitsInLegalInteger(unsigned int Width) Line 357
clang.exe!`anonymous namespace'::SwitchLookupTable::WouldFitInRegister(const llvm::DataLayout & DL, unsigned __int64 TableSize, llvm::Type * ElementType) Line 6198
clang.exe!ShouldBuildLookupTable(llvm::SwitchInst * SI, unsigned __int64 TableSize, const llvm::TargetTransformInfo & TTI, const llvm::DataLayout & DL, const llvm::SmallDenseMap<llvm::PHINode *,llvm::Type *,4,llvm::DenseMapInfo<llvm::PHINode *,void>,llvm::detail::DenseMapPair<llvm::PHINode *,llvm::Type *>> & ResultTypes) Line 6263
clang.exe!SwitchToLookupTable(llvm::SwitchInst * SI, llvm::IRBuilder<llvm::ConstantFolder,llvm::IRBuilderDefaultInserter> & Builder, llvm::DomTreeUpdater * DTU, const llvm::DataLayout & DL, const llvm::TargetTransformInfo & TTI) Line 6490
clang.exe!`anonymous namespace'::SimplifyCFGOpt::simplifySwitch(llvm::SwitchInst * SI, llvm::IRBuilder<llvm::ConstantFolder,llvm::IRBuilderDefaultInserter> & Builder) Line 6790
clang.exe!`anonymous namespace'::SimplifyCFGOpt::simplifyOnce(llvm::BasicBlock * BB) Line 7324
clang.exe!`anonymous namespace'::SimplifyCFGOpt::run(llvm::BasicBlock * BB) Line 7346
```
(note that my llvm source is a bit older so lines might not match, but this seems to happen on the latest version as well)

The check fails when `Width=65`, because the largest `LegalIntWidths` for me is 64, and this brings everything down.

This doesn't make much sense for me, because I expected comparing the max size a register can hold, not the literal width of the register. It's quite possible that I don't understand the code around it and it might be something like a bitmap of cases (like someone on discord suggested), but either way it's a missed optimization.
</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJzMl91u6zYSx5-GuRmsYVO2ZF_4Io7jVticbXHiopfFiBxJ3FCkDknF8Xn6BSk7jpOg27PoxQJBDPNj5j8fJH9G71VjiNZssWGL7Q0OobVu_bJH0R6tuamsPK5LOKCHXuNRmQYOKrTgbUfgldZHEFYS43eARsK48mCNJJfWtkfQ-rkDgQY8EaAB2wfVqe8YlDXJTlAd-WihGgIYG8CGlhyk4Qmbbtn09vR_sfmZHLHFlvFlG0LvWXbL-I7xXWNlZXWYWNcwvvvO-I7uf_ri7_23fzK-AuUhtJSkXlnctwS1cj4k9Z6EjR92cII8oCNQkkxQAjXQi6A-QG0dtPgcg2P5VNXA-PIFWLZl2RbyeXTW2GDhSJ5lG5ZPQdiuIxNIgjJJxejQmpS1Q6s0pag_rBvlTGDfYoAOn8i_2d6QIYdxtT-oIFpQxgc3iJTVK0cCPQH6s-p8DpVDI9ox56P_K4-gAuOFh3zxunICJYTWDk0b4kJHqc6pCVp0MuZVglZd3DnWsQRhBy2hVkaCseAH0UJoowKsAzlA-DYo8QSe0Ik2bvMWSpAkVDQWLEg7epBUDU2jTHPpstoORo4xWq3tIU5mt28rWxpgi80WAz7g0Q4hTme3tQq-NA_UoC5NoIbcp82kQjtUE2E7xnexfU8f_-id_TeJwPiu0rZifLea5ZUsZFZVc57zol5w4vWSJK-XBU2Xspqv8ikW_GJHGaGHeGDOA-VXxncXnZOW8ewhW6xiJ6WjFqPs0QWFGnxA8QTBoaBLvPl0_BN9P44IjaaZ0AsxPkteUux_IRd8OZh0H8QeDPC7kqGNOh6UIcgWxUfzLJ-isebY2cGDwY58H7XxYvTxmHrzwdqnod9jpWkc_j22xk6F0nylRvmQXAtrfIDP9ALjOWwfYvlf9f3xhzIhn0Oy-qi-p8N02bw_9gSM38K9pniq4vfXSPLZavkxlMc2qtoMSsu3gvnyYnUMp4w6o-3H8r9Leh_VHl1DYe_Q-Nq6rjS1TeHt9-Vnyz9NwvtFjx1qvSXj6Qv2LLu7zPz6c_kvK1MmGL_7mB7G7-ZXE2crUdefWHq2SrLs_mqrpIBKX5v5FZX7MUHZPcvuU6xfyQ86Fc5fKsfz7JPKpbLs7Q-V7TJdfk1Fp2uldzHJaMLOpqm3Yl83bKnGQYfSeHKxiU_Kz-auvGxtt3dEv_US4_UXhWz3v_3PNf_TPjpna76a_viRVV2vVX282_30S3-6KvxpbEzk_0duzzEWf3OMvxhx3T0b9EpstBVPKcLN5tV3kfH53-LbDeYvu5zn767901e-NDYQhAQLJ-oaSSbSD0KlAqR0x3dWK0MeOhXf88geHYbxDY5Pd2iVj7DW-fgKt9j3ZMCOhKAxkA_wTM5H0IiwR1ozvnpPVaIl8QQ1Ku3h0JKJtDS-J9k2X0TZ0RsJHDydLLsmmmb59PwmpfU-MlSkri4FEhFrpIAks4qY6YGeyR1HupD2YN4xnvIgLXnDeDGCFHSRRny8pE6m36opgV56EpGthO16TCQbJXb4Al59J0Bwp3crgW1rtYwGYiZTKCqQQw2HqB9snQbPOyZQjnj1bVCBoLfeq0qfCleCtKPMISJ0PCTylVwBXcIeNdKqCqcCVjRidApfqycaq91hH31H_PORUtNMXGgNxXJK5YV1EvzQxMSTjFU8tQCphOAHPJ5hEKFT3pO8wvfJjVxncpWt8IbWs2KazxdFvixu2rVYLEVWS6QC5_kyn4lZTnKOc8KZmM043qg1n_L5dMaXs3w648UkF9Wcz1ZiOavyakHI5lPqUOlJ7OTI9TfK-4HWxapYFDcaK9I-_Wrh3NAB0iTjPP6IcetEa9XQeDafauWDv1gJKmhaf_kYzEhbeObp9K2zLlXGvMXmm8Hp9Q8TYxLoGd-lAP4TAAD__85fZrc">