<table border="1" cellspacing="0" cellpadding="8">
    <tr>
        <th>Issue</th>
        <td>
            <a href=http://email.email.llvm.org/c/eJztWNtu4zgS_RrnpSBBomzHfvCDLwkm6GRmMZ0Z9FtASbTNjUR6SSlx-uv3kJJlueNkp6e3d2aBNgSZFIuHdWOxiqnOX2a3Wu8sVVteUaZVxaUiI3aCVyKnXD5JK7WylL6ARJDlpaABmyitAlDbiqtqwKYNoTZk62xL3A6i1SCat-9x1D6--6TlERdIUlUAnJsBW1LbVoe26lq5W2RwuWgwCL81Vmuny0GyigbJwjWWmONbbOGf6XGG-5nBaCEHoxWmXmMWcJMWc3C5Ostv8850XeSUCuJ1pUteyYwXxQsU9WxkVQnPZyEfBb5Bj78kBO62crMVXq5Ke-WVPNtKJaDmXJD4Vy2feCHAv17_D_Ql195uiqAjGg8xuMRDOforp4no1Yw_r-X3Ne1GoW0ShRWvVyxk6qTNxSCZ42naBkuCh0FyRWtuqweIN3EiOiYcPruGKaBQI2wP4DtJ0nLwhTidF9E7buQZ8L7gfYCn-kk4k3FF3KSyMty8UCmVLOuSrPwsQAuZthrOp9fObKIQJXzGkrSUbbUVynkX917icDvpuy0JtEryQn6G12pFWNFsBc-9QmwJN8bShr9YpwaHoOoyFfBejk0vAL-riwKhQNfOUUEBAbg0frrSz5TiO6dSG4iz2xm9MxKh44Dy7PeNEgAAm9g_O5k9usBSG6k2JMtdI4_nrdN-855DA6UsuCHoRVksWDYiNJuRF9YjYtVCNvga_BvSO2E8oT2EI7CX1wXUpA5bKZWFrF6gQZE92vDURAkeWgiVbUtuHtuvyTIXiI0F1HSFjq1LDL6gkx4IyeraZI1lQQFnORK9s7-xmFRZUcNiDrfKYcFwe5zTG2assy4oGDsH0LGD9bt2H-__JAgf2dz_CH5vBr-_OMT5t3WbNyNvq8XdQ89aR1_00nwEIaLdmGzT-NJGrW2dTRAxnt0HsBVHbAjOTng5mP4PkL6lE0_7jlZUpxEsIc9BukyAHjA-7wQ6hehpwjus90-_Lv79lBBxbYOJE-d_X1o0R6gH6mjhuDBvD6nXu2dx9fPyp7v5rx8AfWKSaQAvmpsNvscsGY76a75rzYdjsvfDrO-Y9ZVWv48le-b4Dwbc_9iPB4j932ZD7r9mR3ZzH-7mNz-D7oTkbJbps49evvJO9nHFBtPVYH5Nm0bxFARIED1vnmCp1VpuaoME61lWW6fdINgZsZZ7d3ay61uZuqwVrZV4EoVLvtBeaqQ-Kr9FuXOvNbhg17U1mOpAgs1-H7Q5S5BL85VAH1cf3N8dz375-Cm0-WMDjneLiVZ2cKPrYcjCuE0okSkiPytgY2qFpDgJozBy_uO_B3ESoR-yaZhEnQfdc7MRlZN9Pxk_jIeByznBOjfPUrEYK7TqvEe2jtQa6aYoHPlOW-jJD924Desy6ZUTeE5fqTqXzkl1YsnXpkPdGWB_ZzDTSiEMPAkKVrc3i9XN7zerq4f5758Y-SAQZrsdBUg2QdiqKo4pkPbFVqKkfhJ5yC2JglsEiCvvWU_97NK1a1nkLuM1GQXFMSUOil3VqCTQXeB88OPnRQkd_Bk6FjEWRHHA4vt4DPUNESzmEbboAi-0Wv3_Wivl6oq3YDBOMLrbbGP6RGwYRXT302da_uM3sp25XW-JWl1YFyjbTX4b04pXnBJGH6SrOif7SS_EYNhZ2NSZL1HeomL0m5JrV66w0fg8SdKRxONkMuyI4o7oVkOhc3gw37hEkeJwMnIhjIXJsPkftbVB8G2_NgB15jz3u5elOPngtEd0Ux2KsP8mJ_1c5trHy-O68XhySaj5ev3k2B9G4yEbv4LpDtJuVjTtg6A_6fpjFkfxZNKB7N9mJolPeDnps3g6GePQeTuAz1GUV8Kiym9reX8_gCLdVeDuwHIH7OmdXFvtdw4b9LM3qq2wnrb7InvOiqrdrZIfAGHBMyBHVckGK-VWFO4-S6fu1rCZv-UmRwXsNmG3Hs5nf7lY7iTibwWHae48csKpWR1I23FDCIOu1seJbITaVFvC4dNw2uNqf5Sk4eaLOwJbbzbQIJhqLln60ab3vshnST5NpvwC6cNWm9lyfr3_dFGbYratqp0PAP5-aYNzq05DMIlOUTwd_nAW6n-KrHKR0tpauHA9SpKEXWxnScovh-M0h8X4ZTqNxeV4OM1Zkk7ihOXD-KLgKerAWZM3XHz7knLm4mQUw08vRxN2GebjJMnWaTKdMjYcinwwjESJrCB0OKE2mwsz85BpvbEYLCSc7jjIrZUbJcSBw0pWhZh9PLGLeH1b7DMF6l8Rt35sLjzDM8_tvwG13k9j>53332</a>
        </td>
    </tr>

    <tr>
        <th>Summary</th>
        <td>
            Strength reduce repeated division with non-constant divider
        </td>
    </tr>

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

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

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

<pre>
    Loops that contain repeated divisions by the same (non-constant) divisor such as

```
void division(int *r, int *n, int nn, int d) {
    for (int i=0; i<nn; i++)
        r[i] /= d;
}
```

could be automatically rewritten, likely at O3 or higher, to the machine code equivalent of

```
void division(int *r, int *n, int nn, int d) {
    if (nn < 64 || d == 0) {
        for (int i=0; i<nn; i++)
            r[i] /= d;
    } else {
        libdivide::divider<int> fast_d(d); // requires libdivide
        for (int i=0; i<nn; i++)
            r[i] /= fast_d;
    }
} 
```

(in the code above, an arbitrary minimum size threshold of 64 elements is chosen to avoid the libdivide divisor initialization overhead for small arrays; the number has been pulled out of thin air for now but a more appropriate number would need to be picked during implementation)

A similar transformation could also be applied to other operations such as modulo and divisibility checks.

## Benchmark
<details><summary>benchmark source code</summary>

```
#include <stdlib.h>
#include "libdivide.h"
#include <benchmark/benchmark.h>

void division(int *r, int *n, int nn, int d) {
    for (int i=0; i<nn; i++)
        r[i] /= d;
}

void xdivision(int *r, int *n, int nn, int d) {
    if (nn < 64 || d == 0) {
        for (int i=0; i<nn; i++)
            r[i] /= d;
    } else {
        libdivide::divider<int> fast_d(d);
        for (int i=0; i<nn; i++)
            r[i] /= fast_d;
    }
} 

static void BM_division(benchmark::State& state) {
    int *r = new int[1024];
    int *n = new int[1024];
    for (int i=0; i<1024; i++)
        n[i] = i;
    for (auto _ : state)
        division(r, n, 1024, state.range(0));
    delete[] r;
    delete[] n;
}
BENCHMARK(BM_division)->Arg(12345);

static void BM_division_constant(benchmark::State& state) {
    int *r = new int[1024];
    int *n = new int[1024];
    for (int i=0; i<1024; i++)
        n[i] = i;
    for (auto _ : state)
        division(r, n, 1024, 12345);
    delete[] r;
    delete[] n;
}
BENCHMARK(BM_division_constant);

static void BM_xdivision(benchmark::State& state) {
    int *r = new int[1024];
    int *n = new int[1024];
    for (int i=0; i<1024; i++)
        n[i] = i;
    for (auto _ : state)
        xdivision(r, n, 1024, state.range(0));
    delete[] r;
    delete[] n;
}
BENCHMARK(BM_xdivision)->Arg(12345);

BENCHMARK_MAIN();
```

</details>

```
❯ g++ --version
Configured with: --prefix=/Library/Developer/CommandLineTools/usr --with-gxx-include-dir=/Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/c++/4.2.1
Apple clang version 13.0.0 (clang-1300.0.29.30)
Target: x86_64-apple-darwin21.2.0
Thread model: posix
InstalledDir: /Library/Developer/CommandLineTools/usr/bin

❯ g++ -O3 -march=native -DLIBDIVIDE_AVX2 bench.cpp -std=c++11 -isystem benchmark/include   -L ~/dev/benchmark/build/src -lbenchmark -lpthread -o division_bench

❯ ./division_bench
2022-01-21T16:44:09+09:00
Running ./division_bench
Run on (16 X 2400 MHz CPU s)
CPU Caches:
  L1 Data 32 KiB (x8)
  L1 Instruction 32 KiB (x8)
  L2 Unified 256 KiB (x8)
  L3 Unified 16384 KiB (x1)
Load Average: 1.85, 2.34, 2.52
---------------------------------------------------------------
Benchmark                     Time             CPU   Iterations
---------------------------------------------------------------
BM_division/12345          1687 ns         1683 ns       406426
BM_division_constant        109 ns          108 ns      6210188
BM_xdivision/12345          317 ns          317 ns      2198624
```

All tests divide an array of 1024 ints by the same divisor:
- BM_division uses the division instruction provided by the CPU
- BM_division_constant is the baseline obtained by hardcoding the divisor at compile time, and letting the compiler perform strength reduction
- BM_xdivision is the transformation suggested above




</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJztWEtv4zgS_jXOpSBDomzZPvjgR4IJOplZTGcGfQsoiba5kUgvKSVO__r5SMmy3HGy27s7-wDaEGRSLNa7ilVMdf46v9N6b6na8YoyrSouFRmxF7wSOeXyWVqplaX0FSCCLC8FDdhUaRUA2lZcVQM2awC1IVtnO-J2EK4H4aJ9J2H7-Omzlie8wCRVBYQLM2ArasfqOFbdKHdEBpNlg4Pw24Bau10O4nU4iJdusMIeP2JL_8xOO9zPDMZLORivsfUGu4A3bnEOJuuL_DbvTNdFTqkgXle65JXMeFG8QlEvRlaV8HwW8kngG_T4S0zgbie3O-HlqrRXXsmznVQCas4Fib_V8pkXAvzrzX9AX3Lj7aYIOqJkhMUVHsoxXztNhG92_PNa_ljTbhXaJlFY8ZZiIVMnbS4G8QJPMzYgCR4G8TVtuK0eId7UieiYcPjZDUwBhRphewj-JElaDr4Rp_Mi-sCNPAPeF7wP8FQ_C2cyroibVFaGm1cqpZJlXZKVXwVgIdNOw_n0xplNFKKEz1iSlrKdtkI57-LeSxzeTvouJIGtkryQX-G1WhEomp3guVeILeHGIG34q3VqcBhUXaYC3ssR9ALo93VRIBXo2jkqICAAl8ZvV_qFUnznVGoDcfZ7o_dGInUcsbz4uFECCMAm4mcvsyeXWGoj1ZZkuW_k8bx12m_eC2iglAU3BL0oC4JlI0ITjLywHiOoFrLBr8G_Ib0XxgPaYzoCe3ldQE3qGEqpLGT1Cg2K7MkOz00U46GlUNmu5Oap_RqvcoHcWEBN15jYusTiKybpEZCsrk3WWBYQcJYT0AfxDWJSZUUNizm8VQ4LDnenPb1lxjrrAoKxSwg6dkC_G_fx_Z8k4RObhx_J793k919Ocf5tXfBm5G21vH_sWevki16azwBEtkvINoNvbdTa1tkEGePFfQBbUchG4OyMl6Pp_wHQ93TiYT_Qiuo0AhLyEkpXCdAj1hedQOcoeprwDuv909PFv98yRF7bYuPU-d-3Fs2R6oF1vHRcmPeX1NvoWV7_vPrpfvHrJ6A-M8ksgBctzBbfIxaPxn2aH1rz8VTs_TDrB2Z9o9U_x5I9c_wdAx5-xOMRxeF_JiAP3xOR3d7H-8Xtz4A7A7lYZfrqo1evfFB9XLPBbD1Y3NC2UTwFAQpEz5sHWGm1kdvaoMB6kdXOaTcI9kZs5MGdnezmTqauasVoLZ5F4YovjFcapY_K79DuPGgNLthNbQ22OiTB9nAI2polyKX5TkSf15_c3z3Pfvn8ZWjzpwY53i1OjLKjG92MhmwYtQUlKkXUZwVsTK2QFMXDcBg6__HfgygOMR-y2TAOOw964GYrKif7YZo8JqPA1ZxgnZsXqVgECq06H1Cto7RGuSkKB77XFnryS7cuYF0lvXYCL-g7VefKOanOLPnWdOg7A8R3BjOtFdLAs6BgfXe7XN_-fru-flz8_oWRTwLDbL-nAMUmAFtVRREF0r7aSpTULyKPtSVRcIcEce0967lfXbpxLYvcVbwmo6A4lcRBsa8alQS6S5yPfv2yKEOH_gIcCxkLwihg0UOUQH0jJItFiBBd4oVRq_9fa6VcX_EeGqwTjO6CLaEvxEZhSPc_faXVX34j25nbzVbo1YV1ibIN8ruI1rziFDP6JF3XOT1MeykGy87Cps58i_IeFKPflNy4doWNk8sgcQcSJfF01AFFHdCdhkIX8GC-dYUiRcPp2KUwNoxHzf-47Q2Cf-3XJqDOnJd-D7IUZx-c9ohuq2MT9u_kpF_L3Ph8eaIbJdMJoefrzePTfBQmI5a8QdMdpN2ucNZHgvm0mycsCqPptENyeJ-ZODrj5WzOotk0waHzfgJfoCmvhEWX3_by_n4ATbrrwN2B5Q7Y8zu5ttvvHDboV29UW2E9bPdF9pwVXbujkh8RwoIXkJxUJRtcKbeicPdZOnW3hs3-HTc5OmAXhB09nM_-crHcS-TfCg7T3HnkhFOzOoK264aQBl2vjxPZCLWtdoTDp-G0x9XhJEnDzTd3BLbebqFBMNVcsvSzTe99lc_jfBbP-FUlq0LMP5_RFG9vQv0pSP3rz9ZG5qo2xXxXVXufNfyl1BawdTqEZJgUxfPxDweo_qvIKpdera2Fy_HjOI7Z1W4ejxMeTpJZNsnjbCJGs1mYJOPxLBqxeJKm06uCp2ge502xcSXnLjWGEVxzMp6yyTBP4jjbpPFsxthoJPLBKBQlCoGhIzzUZntl5p6HtN5aLBYSfnZa5NbKrRLiiB9V1U6b-Wpxc_hy5Zmde07_AEjwOYY">