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

    <tr>
        <th>Summary</th>
        <td>
            [ADCE] Dead-code elimination fails when increasing loop count beyond threshold
        </td>
    </tr>

    <tr>
      <th>Labels</th>
      <td>
            backend:X86,
            loopoptim,
            missed-optimization
      </td>
    </tr>

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

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

<pre>
    There is a missed opportunity to remove the following dead code on latest Clang when restraining optimizations to `O2`, that GCC seems to catch via CDDCE (Godbolt [here](https://godbolt.org/z/97aqvfaqY)).
```c
#define SIZE 100

void square(float x[SIZE], const float A[SIZE][SIZE], const int b[SIZE]) {
    float y[SIZE];

    for (int i = 0; i < SIZE; ++i)
        for (int j = 0; j < SIZE; ++j)
            y[j] += A[j][i] * b[i];
}
```
Dumping the LLVM IR at the different stages seems to reveal that the cause may stem from the current tradeoff on the threshold of loop unrolling. With `O2` and `--unroll-threshold=13000`, the optimization is accomplished by BDCE. Indeed when `SIZE` is relatively small (< 40, different between `O2` and `O3`) the optimization succeeds.

Yet, while adjusting `--unroll-threshold-aggressive` option might provide a more balanced tradeoff in `O3` scenario, I believe this would be an orthogonal solution, as the core issue seems to lie within ADCE (which does some control dependence analysis).

Very minor, but I'm tagging x86-64-backend as well, since, for some reason, only on x86_64 the above seems to be lowered into a dead loop that increments [`rax` till reaching zero](https://godbolt.org/z/xKjeE51Es) on small sizes (though this would likely be solved if it were DCE'd).
</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJyMVU2P4jgT_jXmUgIFh_Bx4NCQZtR659VIu6vZnb2snLiSmHFcjO1A079-VU4LmI_DtlqA7SrXU089VVYhmNYhbkWxE0U5UUPsyG-Vi-QMNd60HcZIk4r0dftHhx7BBFDQmxBQA51O5OPgTLxCJPDY0xkhdggNWUsX41rQqDTUpBHIgVURQ4S9Va6FS4cOPIbolXFsSqdoevOmoiEX-EKxzD5JscyE3EPsVIQP-z0ExD6d1irWHZyNgn1Z7p9ByPUH0hXZCKLYMVhRlEKuuxhPQeRPQh6EPLSjyYx8K-ThTcjDZqW-nRv17YuQGyE3M5GVInvisOm_fl_LXGNjHMLvL38_wzzL3vfT55mMhvBtUB6FXDeWVIRXUezYNqHYQ00uRBiPnh6OfmFkXITq8WADYrUbIwHA-yXXB4t894gm2ZBnRvgqAyIvIRP5Lv3cpwx4JeROyJ3hvG9-P_ge777HX_gef_LlP0Z2FEWZjPIypXscczXj9lPKz3wHfVX-wPy4LIf-xOpgWX38-Pn_8PIbqJiW2jQNenQRQlQthrs2PJ5R2VE0bFmrISD06gohYg-Np37cH3zyj15ppKZhkfJ-7DyGjqwGasASnWBwnqw1rp3BnyZ2N22CcpoX0-loMb25iryc51mW3QSM3yk8dVJdU3-yJnSoobrCrtw_z-DFaUQ99odYZonxZcb2Hq2K5oz2CqFX1nKVuCiLFOFOR4XxgqP3dyA_5QnM5mcwYahrRB1mjzr6gpHvvXTGIih9HELkSvwy26lqW48hmDNyQL6cHPSm7SKcPJ2NRh4c5BEqZZWrUd9ZN-6GDkKNTnlDHPkFKrQG01AxAS40WA0VgnJAPnbUklMWAtmBo7GHCmNdKY2qMOBdE9YgXEzsjIOn93lx6UzdgSaWDvXs5qInCxpP6DS6mkMpew0mPEyG9PkZ_RV648hz2GqI8CLkqoeo2pZJel0vp8vFtFL1V3SacV3QWrYNxtXIP7jNUliPKozwydkra_B1vfxnuUipqIqH6i2LCsHSBT1qHhMEapywSaNJ7sbVHnt0MfAYFMvMq1fmNRprOVLdMbw39PTfxuPr_474XMyfmQGGNgovmDcMTGHsaGi7x_pY85UFWiEX5sw4GzARGDOU-2chV5rJnOhtrjf5Rk1wO1-uV4VcrfNi0m03daEWWVZUq4UsmqZo5oVWi6ba1Cu1mFdqYrYyk3m2lPk8X-RFMVvkq3Vd4GpVVNV6vtiIRYa9MnZm7bnnVCZJCttlvljlE6sqtCE9eVK-10fkT3-tl0JKIfdCSmYztcdtZ3zxpo89w2dFOfFbjjKthjaIRWZNiOEeN5po0-vKiuPRV6LS0_QcojW9cWP3NcrYMDZ8Kp8KXKNU05qG1NBXcvo-liaDt9sfKmdiN1SzmnohDwzg_Wt68nTEOgp5SCwEIQ-JiH8DAAD__2mthuQ">