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

    <tr>
        <th>Summary</th>
        <td>
            Reducing switch range on powers of two
        </td>
    </tr>

    <tr>
      <th>Labels</th>
      <td>
      </td>
    </tr>

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

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

<pre>
    I recently found `FIXME`: https://github.com/llvm/llvm-project/blob/b0e00ca6a605b88e83129c8c6be4e177f93cbfea/llvm/lib/Transforms/Utils/SimplifyCFG.cpp#L6795-L6797

I decided to implement it. My Idea was, as described in FIXME, to check if switch contains only powers of two, and if so, to replace each key with `countl_zero(key)`. When I'm almost done, I ran into a problem that I also need to change the switch `condition`  to `countl_zero(condition)`. I tried to find some simple and fast algorithm to count leading zeros in runtime, but all algorithms are too slow or too complex. Should I try to implement something complicated at all, or is this optimization not worth it?

My current approach looks like that:
```c++
  SmallVector<int64_t,4> Values;
  for (const auto &Case : SI->cases())
 Values.push_back(Case.getCaseValue()->getValue().getSExtValue());
  
 if (!IsSwitchOfPowersOfTwo(Values))
    return false;


 Builder.SetInsertPoint(SI);
  auto *Ty = cast<IntegerType>(SI->getCondition()->getType());
  
 SI->replaceUsesOfWith(SI->getCondition(), /* TODO: count leading zeros of SI->getCondition() */);
  
  for (auto Case : SI->cases()) {
 auto OrigValue = Case.getCaseValue()->getValue();
    Case.setValue(
 cast<ConstantInt>(ConstantInt::get(Ty, OrigValue.countl_zero())));
 }

```
</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJyUVcGO2zYQ_Rr6MoggU7YkH3xwvOtCaIMN6k3SW0BRI4ldihTIUR3l6wtS3qy3TYIWEESBnPf4ZuaJFN6rziDu2fYt296txES9dfu7X8VcrGrbzPsKHEo0pGdo7WQaYHl6qv54d8_ylGUH6IlGz7ID4yfGT52ifqoTaQfGT1r_9Ty8GZ39EyUxfqq1rcOQYppKkYs83dZliWW25jtZyrzGDa6Lot1lsm5R3PCogHt0wvjWusEzfvpASofxrIZRq3Y-nn5J5Dgynv2WF7vtm_AuWHrH0sPyrqBBqRpsgCwEEA5oCBQl8G6GqkEBF-EZP4Lw0KCXTtXYgDKw5MyPASh7lE-gWvAXRbIHaQ0JZTxYo2cY7QWdB9sCXWykMk0Mtle4w1ELiYBC9vCEM1wU9aGu0k6G9Oev6Czj5RPOjO9YnibwqUcDFePFAEIP1hM01mCgq8AJA8qQBQGjs7XGAagXBBUI7S0YXJKVvTAdAvX4rDpuaBpFyhqWpxCi_iXiJeIqpQJyaqFslWnA2wHBx1LGRFvhCYTurFPUD3HnQAgaRaNMB4HXh4K6yZAaYhL1FCD6BeZBOASyFry2F7AufksbdvmSwLm3k26ilPl1I4Ma6sM-MVhJQdiAiPRhJ-tAeaBeebAjqUF9FSE5MJbgYh31oIhlp1vLvJtBTs4FdjGOzoamaWufPGj1hLHWwf4LIk-XRzL-NjxxFuA8CK0_oiTrWHZUhvLNZ2L8uGHZPXwUekLPsm_RrXWwlD6Ucgpt4flReITww52rNyy7l8KjZ7wMbeG7K3JhSsbJ959rIZ8YLwMs6ZDCGJcXTKDokG5mQtD5_svtVHheVF1H1UJcXVf-HH300L6Phn9oH4Pdy2s6t7oAwCFNzkArtMdvpLdveDsp3aBLzkiV8ejovVWGGC_P1Wsh14ocHmdg2R1I4Yllx8oQduge5xFZdh9h1ySPLxa-ST0G_jjNBX39Uz949A_tJ0X9T3iDveIheIDHh7uH0KrvOd-28COGkFRk-I6eZ1PE5H_qBWDFMzgGPzjVxZ7Eav1nP9xIgAXlb9aXlWvpj8GowlBlaCn9q4kDyw4dhkY-zqFG3_Qkr0-aayf-0Q9W3L3yyvMPtmr2WbPLdmKF-3W-K4t1yfN01e_bom6KTbFpt1uxabNa8FLWshU8r5uskelK7XnKs3WarVO-Xqdpgpsdb8s1breiLTetYJsUB6F0Eu6dxLpupbyfcF-kxTZfaVGj9s_3pdvH262eOs82qVae_AuMFGnc_47NJEP_r8eui-ewNa_vidXk9P5_36VRWLgAo7a_AwAA__9F024E">