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

    <tr>
        <th>Summary</th>
        <td>
            [LoopInterchange] Enable interchange when the outer loop header has "safe" loads
        </td>
    </tr>

    <tr>
      <th>Labels</th>
      <td>
            new issue
      </td>
    </tr>

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

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

<pre>
    The following C program is trimmed from a real workload. If we interchange the loopnest, we observe significant performance improvement. It is clear that with the loopnest interchanged, access to `res[j][i]` could be faster.

```
int* data;
int** res;
int *sum;
int maxLocal=0, max_i=0, max_j=0;
void foo() {
    for (int i = 0; i < 10000; i++) {
        if (data[i] == 1) continue;
        for (int j = 0; j < 10000; j++) {
            int cur = res[j][i] * res[j][i];
            sum[j] += cur;
            if (cur > maxLocal) {
                maxLocal = cur;
                max_i = i;
                max_j = j;
            }
        }
    }
    return;
}

int main () {
    foo();
    return 0;
}
```

However, with the current loop interchange pass, we are unable to interchange the loopnest. This is because there is load of `data[i]` in the original outer loop header. When we check whether the loopnest is tightly nested, we would bail out if we find "unsafe" instructions in the outer loop header, i.e., if `containsUnsafeInstructions(OuterLoopHeader)` returns true. Load instructions are considered unsafe.

If we would like to enable interchange for such scenarios, my general thought is that it might suffice to make sure `data[i]` does not change within the loopnest. If that is the case then we can interchange. To be a bit more specific, we could check 1) whether the array index `i` is a inner loop invariant. For instance, if what we had is `data[maxLocal]` then it would become illegal to interchange. 2) whether the array `data` itself changes within the loopnest. If the array values had changed then it would be illegal to interchange, e.g., if we had a store to `data[i+1]` inside the inner loop. This check can be done by leveraging the current dependence analysis in loop interchange, nevertheless we need to be more strict, e.g., even if we had loop independent dependence on `data[i]` we need to bail, as opposed to the fact that it is okay to have loop independent dependence within the inner loop body.
</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJx9Vstu2zoQ_Rp5Q9RQ5NquF140SYMGCHA3Le6yoKSRRIcmDZKym_v19wwpO1LiRDAs8TFnzjzJ0tYv218dicZqbU_KtOJOHJxtndwL5UVwar-nWjTO7oUUjqQWJ-uetZX1XDw24kRCmUCu6qRpSQRAaWsPhnzIijtetqUndyThVWtUoyppgjiQa6zbS1NBfA99R9qTCUAMrLXSJB2wZBAnFboJ6lhdzSpkVZEHUyuyVe7IZ8vbXba8x0vxa5WLyva6FiWMlB6y8yy_z_Lvw_8qH35xCPCs-C5qGWS2uB3P8TSjj2YF5ny_n0zt5d8nW0mdLe5zZofxHzUe7OLgLHK0Cs61Niu-ZcVGZOthXuCBh6DhG6MqASnBYvHzTtzkeOIwK27j740wP6ph-WhLcgajMNANb6-sCcr0dOFyFhvp3b3q3U317j7RG3VDuupdlH8XFHF25jRUb4nww_5NuwSrAxpQr-5M1iadP17j8BFBfs6bxGe4w8Y_KQbq0z3JX7ure7L1_XRyMjEZOAq9MxeUy9o4zZQR15NmyKUJhwQo8iuQ0_xP_z_tiY7kYgGf6w_ucSjRWIeTkj9I74dSl45Eb2Spicvxo74wF786FDl-JVWy93EVkpjgtiJsw5U8SluuYZjLGNapVhlEzPYAT2Q6kjWqWvzbkWEWVUfVszh1xLBvegf6hGq7oF8Ej1MDgcgpdQipIjCnEiYbZWr4uOiNlw3hAyR8cH0VlDX-wugtEYZUc5rHdzSFKw3x8r8j0OMIBKH6h-WfIP5zkN6wuSlg3H97mosndstEOXsasF5BBO05UZw0ttSbk2FaPceIUIrNODBc7L6vOuErrDplYyz3L6IlQw6ODp3t4bHoOm7ICsnHLoRUg24ecfcS-L4Hp_eBqy15YSy6QVLICTW47jUhQDaB-5RrMiVFCqc0Y8bIHsu9XIqSqVgo9Qeq-GQZgpnafcqC2OnGqSCdky_Aq-kvk1Uxt-BPTJlzHJU5whOSz6MHuIcdzyfVENBTPJZIdBwTP7L40nKS4ZE_KA65RZXdw_VaU8tetVObius8z-BMMnjSzeBF_4kbz7JHqXtsZJrDafmO0gd02FCat-cMHmyVwgf2djpoL1Eubm8uJcrpGBm8OnMo9hQNDiW01taQKF-E5iYjW750jDtMTQdCfPhuIFHqL17FYnvbeJidYQTIar4BgKchtjLmR8oM3F-qMLYHAmZk1AB6VjlRbs2VdB4rQbuIFxAv7OFgfZplSxpZhUu1gL19Rjyw1skjfapyFNVRPpa4pM1n9XZRbxYbOQsqaNqCE3eNx5FDcEb-eF_hJw761U4FPp4b3Lm9cff1s97pbRfCAVcdXHoe8GvBqi_nSGAMtD6eX19wcdsR-_dBeY9kw8dyuc7Xs267KVZyLddN0-R5uVjJ5XJFORXVJl_clItv-UzLkrRnM6Da0ElECHzDjJnaFnlR5MtilX_NN4vlnJZ5JVdNtZQ3uVzIdfY1J5yBes485ta1M7eNlMq-9VjUygf_uogjCrdPil5jfNmjrbntnTXtfx39lrpEGslZpLCNJvwPft2AeA">