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

    <tr>
        <th>Summary</th>
        <td>
            Rewrite divisions of small constants to lookup tables
        </td>
    </tr>

    <tr>
      <th>Labels</th>
      <td>
            llvm:optimizations,
            missed-optimization
      </td>
    </tr>

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

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

<pre>
    Division, `x / y` where `x` is a constant can be rewritten to a switch-statement/lookup table. The size of the lookup table is directly proportional to `x`, so will need some sensible upper bound to prevent code bloat, or some smarter switch-statement translation that groups together divisors that give the same result into a single table entry.

# Examples
Unsigned division ([godbolt](https://godbolt.org/z/sbdvzscnj), [alive](https://alive2.llvm.org/ce/z/uHi3j-))
```c
#define CASE(y) case y: return x / y;

static uint8_t x = 10;

uint8_t src(uint8_t y) { return x / y; }

uint8_t tgt(uint8_t y) {
    switch (y) {
        CASE(1)
        CASE(2)
        CASE(3)
        CASE(4)
        CASE(5)
        CASE(6)
        CASE(7)
        CASE(8)
        CASE(9)
        CASE(10)
        default:
            return 0;
    }
}
```

Signed division ([godbolt](https://godbolt.org/z/8T43z9a73), [alive](https://alive2.llvm.org/ce/z/rW2Gic))
```c
#define CASE(y) case y: return x / y;

static int8_t x = 10;

int8_t src(int8_t y) { return x / y; }

int8_t tgt(int8_t y) {
    switch (y) {
        CASE(-10)
        CASE(-9)
        CASE(-8)
        CASE(-7)
        CASE(-6)
        CASE(-5)
        CASE(-4)
        CASE(-3)
        CASE(-2)
        CASE(-1)
        CASE(1)
        CASE(2)
        CASE(3)
        CASE(4)
        CASE(5)
        CASE(6)
        CASE(7)
        CASE(8)
        CASE(9)
        CASE(10)
        default:
            return 0;
    }
}
```
</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJztVkuP2jAQ_jXhYgUFm_A45ADLbiv11m3VY-UkQ_CuY0e2Awu_vuMQWKC4UrXqrRGP2J9nPI9v7Ml1uc9WYius0CqiDySaJG8kok9kj29ktwED3ZwfCUs4KbSyjitHCq5IDsTAzgjnQBGnEbY74YpNjEsc1KAcqpJav7YNcTyXMCTfNkCsOADRa-Lw_RL1O5TCQOHknjRGN9o4tItLr7u3whtpNdkJKYkCKHFQo0ZQVngNbdOAIbluVemFGgNb8MbqEkguNXdeXptequbG4fJbo4kzXFnJ_eZoJHekMrptLGqsAI02aCWGTBvbo2ILnTOW1z4itpWOCHUMiFAV2nX0D3Wb_TBKVlGy6H8pI49vvG4k2OPMd_SkUuhY2acF0zGL0mWly1xLF6UrHG-ca2zEUPwJPz001KbC0QG_Ni-3B1uol4jOu7SmSy7RynvSHUCHUm7rXkMBvZr2s2Avcadj3tuLGeg-xdn-EtZCAXlYPD-i7j0uRW5YQAaxBQbDtUaRE6fY8tJ5H3BRkBZDNfvp_CK2IqPkZtUJtqZA_adRt080Xf6-A86u7sm7yt2RP64h-BxZQE4-XGH-6R0cnWNxA9AQwELAOASkIWASAqYhYBYC5iEAE3CLYIo5ctpT5mreP33837PmJ99TcH45EecyNc8fZ_rs25gd5nzKPsZ084N-EsW_ZvqfiX7F87-m-RXLP0ry-A4JTlCQOHGQa3GQnnGQ0XGwCOJg3cTBUouD1RkHC_p_pX-s0gdlxso5m_OBE05C9rVrFeBc7tb3AHgH401-6ir8FXvVEthBa2R2cwgIt2nzYaFr311gMfd_MbYML9g84FBY2-KFSp_SdDqaDTYZZ3kyYSNaztaUJeW6TEZTYJyO8mK-Tid0IHkO0mZ4fESUdkrZQjdO1OLQ9QGojHbnC6U1aocyvkQ9mK4GIqMJpUlKJ6M0TUbJkE7zMc-TsmDFOE_HRTROoOZCns-ggck60_O2sghKYZ19B7ntegHozEL9vHUbbbIvNfBXoQadl1nn4i_aKKWJ">