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

    <tr>
        <th>Summary</th>
        <td>
            ComplexDeinterleaving pass can be very slow on certain input
        </td>
    </tr>

    <tr>
      <th>Labels</th>
      <td>
            slow-compile
      </td>
    </tr>

    <tr>
      <th>Assignees</th>
      <td>
            igogo-x86
      </td>
    </tr>

    <tr>
      <th>Reporter</th>
      <td>
          igogo-x86
      </td>
    </tr>
</table>

<pre>
    When identifying complex deinterleaving operations, we do not cache unsuccessful results, which leads to repeatedly running the same algorithm for the same input. For example, it takes to 4 seconds to compile this code on my machine:

```C
#include <complex>

; // complex SP in C++
using namespace std;
using namespace std::complex_literals;

void func(complex<double> *__restrict__ a, complex<double> *__restrict__ b, complex<double> *__restrict__ c, complex<double> *__restrict__ u) {
#pragma clang loop vectorize(enable) unroll(disable)
      for (int i = 0; i < 100; ++i) {
           u[i] = u[i].real() + u[i].imag();
           u[i] = u[i] * (a[i] * b[i] + c[i]);
           u[i] = u[i] * (a[i] * b[i] + c[i]);
           u[i] = u[i] * (a[i] * b[i] + c[i]);
           u[i] = u[i] * (a[i] * b[i] + c[i]);
           u[i] = u[i] * (a[i] * b[i] + c[i]);
           u[i] = u[i] * (a[i] * b[i] + c[i]);
           u[i] = u[i] * (a[i] * b[i] + c[i]);
           u[i] = u[i] * (a[i] * b[i] + c[i]);
           u[i] = u[i] * (a[i] * b[i] + c[i]);
      }
}
```

And after adding one extra `u[i] = u[i] * (a[i] * b[i] + c[i]);` line it takes 23 seconds.
</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJzsVc2O4zYMfhrlQkygSEkmPvgwSTbnAj30GNASbauVJUM_2UmfvpDtSXYu7Rx6WWAFQRZp8hNF2vwwRtM5oprtjkwI0_nOv7wf9kwItjuvMKfeh_qhXjVe3-s_enJgNLlk2rtxHSg_jJbeQZNxiYIlvBW1HylgMt5FJk7wnUB7cD6BQtUTZBezUhRjmy0Eitmm2a43qgdLqCMkD4FGwkTa3iFk5wpu6gkiDgRoOx9M6gdofXiqjRtzWsPFB6B3LKEVXJMg4V80gW4hkvJuPqFEbyxB6k0E5TWBdzDcYUDVG0dMvjF-Zvxj3fN5nhZZSOOUzZqAydOSCSa_ffKRR2DiwsTlkarffwPj4MTEsczJKsdyOYcDxREVQUyayX9798bk24J3tSZRQBsfHvN680ZDm51i4vCI7aR9biwx-Q2YeLteA8UUjErXK2DJ1FcMm68aqq8aZiYqYK_HR1rHgN2AoCy6Dqz3I9xIJR_M38TEgRwWIFFBdsFby8RBm7joZgyYRvk0mDgYl8AAk2fgpRxle4IN53NtShXMpwDgOTLbHQ3bnSfvD2EdCMuhk5M4PvVmwG7WP2rxX1glFyVG_FFunsIR1CL8Qv2F-nOjstfz8oc_Nh8d9cfG9eY0YJsoAGo9kYkjoPcUENie_z9R7TlY4-jJDEJ-8MJ6pWupK1nhiurNvtrwXSUO21Vfq2a327Riq7btRu4V6harvVaKY9UqvpMrUwsuJD9wueHbjdiuqWqJy0NzINzs1UayLacBjV1bexvWPnQrE2Omer-Vr9XKYkM2Lnwcrf_-svDTQsmhLm4vTe4i23JrYopPoGSSpfo0d9vzZzYeMUZQ6KAhuFG4QwEvVKcoJDRups1VDrbuUxpj4ZeJszqT-tyslR-YuJSjlsfLGPyfpBITl-kCkYnLdId_AgAA___DjUw9">