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

    <tr>
        <th>Summary</th>
        <td>
            Miscompile loop-interchange pass because of GEP delinealization.
        </td>
    </tr>

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

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

    <tr>
      <th>Reporter</th>
      <td>
          sanggyu-shin
      </td>
    </tr>
</table>

<pre>
    Following code is loop interchangable but current llvm can't do it.
```
for (int i = 0; i < LEN_2D; ++i)
 for (int j = 1; j < LEN_2D; j++)
        aa[j][i] = aa[j - 1][i] + bb[j][i];
```
I found that there is a problem about delinealization after LICM pass.
Here is llvm ir after LICM pass:
```
define dso_local void @func(ptr nocapture noundef %aa, ptr nocapture noundef readonly %bb) local_unnamed_addr #0 {
entry:
  %invariant.gep = getelementptr i8, ptr %aa, i64 -8000
  br label %for.cond1.preheader

for.cond1.preheader: ; preds = %entry, %for.cond.cleanup3
  %indvars.iv31 = phi i64 [ 0, %entry ], [ %indvars.iv.next32, %for.cond.cleanup3 ]
  %invariant.gep27 = getelementptr [1000 x double], ptr %invariant.gep, i64 0, i64 %indvars.iv31
  br label %for.body4

for.cond.cleanup: ; preds = %for.cond.cleanup3
  ret void

for.cond.cleanup3:                                ; preds = %for.body4
  %indvars.iv.next32 = add nuw nsw i64 %indvars.iv31, 1
 %exitcond33 = icmp ne i64 %indvars.iv.next32, 1000
  br i1 %exitcond33, label %for.cond1.preheader, label %for.cond.cleanup

for.body4: ; preds = %for.cond1.preheader, %for.body4
 %indvars.iv = phi i64 [ 1, %for.cond1.preheader ], [ %indvars.iv.next, %for.body4 ]
  %gep28 = getelementptr [1000 x double], ptr %invariant.gep27, i64 %indvars.iv
  %0 = load double, ptr %gep28, align 8
  %arrayidx10 = getelementptr inbounds [1000 x double], ptr %bb, i64 %indvars.iv, i64 %indvars.iv31
  %1 = load double, ptr %arrayidx10, align 8
  %add = fadd double %0, %1
  %arrayidx14 = getelementptr inbounds [1000 x double], ptr %aa, i64 %indvars.iv, i64 %indvars.iv31
  store double %add, ptr %arrayidx14, align 8
  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
  %exitcond = icmp ne i64 %indvars.iv.next, 1000
  br i1 %exitcond, label %for.body4, label %for.cond.cleanup3
}
```
run commend: 
```
$ opt loop-interchange.bc -debug -passes=loop-interchange -pass-remarks-missed='loop-interchange' -o test.bc
remark: <unknown>:0:0: Cannot interchange loops due to dependences.
```
Debug print out:
```
Delinearizing:   %0 = load double, ptr %gep28, align 8
  In Loop 'for.body4', AccessFn: {{0,+,8}<nuw><nsw><%for.cond1.preheader>,+,8000}<%for.body4>
Strides:
8000
8
Terms:
 ERROR: failed to delinearize reference
```

Delinealization got faild when the source is from multiple GEP. 
For example, in ```%0 = load``` in ```for.body4```, the source is ```%gep28```.
But, the problem is that the source of ```gep28``` is also GEP(```$invariant.gep27```)
Actually, the original gep (before LICM) had two indices but gep28 has only one index after LICM.
Current delinealization can't track the recursive gep instructions. So, it can't know exact subscripts.

I would like to discuss the root cause and what part should be modified because I'm not an expert of LLVM.
I think there are two approaches to fix this problem.
1) Modify delinealization - support recursive GEP.
2) Modify LICM.

Please give me an idea if you have any suggestions.

</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJykV11z4joS_TXipQvKyIDJAw8Bkt1UZXZvzd3a1ynZahslsuTSRwj3129JtsEQJ9mdpebDtnRap093Sy1mragU4oYst2S5nzDvDtpsLFNVdfJTexBqkmt-2jxqKfVRqAoKzRGEBal1A0I5NMWBqYrlEiH3DgpvDCoHUr7VUDBFaOaAaxBuRpI9Se7JKun-xNdSGyB0LZQDASTdQ0LSbXzcwfPDP37RfXgndEvoVhB616JgAHuJsHmY9nIDe2lxF1j3Y4wsty9kuSfLrSDLfbTQfoQpzIcDdAt5fj2bpNtRV56g1F5xcAfmwB3QRKEYNEbnEmtgufYOOEqhkEnxF3NCK2ClQwPPT7sf0DBrO5X-3qGjjMLcziLp_SgFjqVQCNzqX1IXTMKbFhzIIim9KghdN86A0gVrnDcIKtDFEghdMkboDsaHDTKulTyFeXlO6B1E27-8UqxG_otxHoKRJkCyThlUzpzOJCEghXpjRjDlZhU2UfAKHUqsUbmwrlj3DM50xGoB03WSJL2Z3IBkOcowpdRmVmjF57PG4AEZR9NJ0ufVh-H0HkJWNAa5jQwIXbZM6W5oclZIZMo36RV9_saMnYm3dB6xzUFEgmS5haQzEI1BSJHwvtxeA2cK311KP1ss4j7Ri2YjipHldp4kCbwD1z6X2K3bSXiF79VM-ocbjz4TOBT_YkzWnvWopp_qaNDFjPzKYhpMfvMbXXHAFUaFb6ucc1D-CMoeR4WgO-jVCAF9Fy6QS9MIFkXdgMKPwEFo59f5KubXdsKUL3N4bPys9o1urctfheDG8ohUV358yOz5TbYO7H2d57er3WR3yOn1_5fTNBtN5sEiSVxAasZ7axdTkUB4Z1JUCtYDGDOGnQR_nydj25TKw7Zov2Ea9skxcl-XH6HL-RecL8Q-Ic55RJfhoUVHGbpYzMd8XPy-j5dN-n_x0TptcMCOcT7m4mLcxZss-76khwU9rMT_op6_reYPtdrW1VcV3G2FJNuPnt_GKyh0XaPisazH5hC6AN242IFNLx0YzvICphxzX8E09AhoSbq_ndQOTQ3WzLzaaS2sRU7SPaHZ7VRCM5hqcGjdLC86fhHX7jg7r16VPiqSPpD0Pun-wo4ppR0M1wyWLXCP4DRwbFBxVAXa8Y5wH11oTOjttHeftTr7to8y4i-hqvbM-M2Sf1LwHLpZQrNBEOPucl8UaO2jih5nW5JtQzHFlnK3DkFMd8ofowI7ZbuHT7bf9OECDVkV0VeJkz60lP50RnC8NHmXFqjj_C809WUYHn7-_OfPQLFkQiJvVe7VQTBYogmCj6fTUM1zV1ppF61xOB5QhW4WrPamiE1paXQNtZdONBLhbw9_zLpMfdQG8J3VTau7UHBZbBib89erKRchLqDdzdJDe208-w9dMm2961F93y3suSXvLenyYunaTGzZpdXBLTL4Tuji9vS5DHXXi_vCeSblqSegjaiEYhJix0vXOZZh7wtdfOiiD4yDO2oQiosCbbw-tefigVmIHbcOm5Pi-D64AHSO7rqL1u19or9zOcOK10jDYOGNFW8YeQhlnfFFmGtn8KeOgXJnWCjpEMPCgfW5LYxo3LlQu2vOUXvJQYrXtqCFLby17VJaB1PeIjAVcoc5aJhxYA8RkyPUmotSYHhuJz4RmtUQ9gymAN8bNC7E5_n5372rT-AOQr12dypmMMrGmsZoVhzQBhaleA-zbB_1DjoPQv8IS54-KDUF65tGGzdQKCRzi6QD5ED29t8_JDKLUAVIHXwFwZGBKOGkPRzYW_h2AuurCm0rdQuc8E3K79I7NsHNPJsvsvk8ydaTwyZJ2GKVc57iKqF8VSZstcQkzTBbYZrheiI2NKGLZJmkySLNlusZL--y9RxxsVyw1XK9IosEaybkLNwZZ9pUE2Gtx81dcpdmk3gi2XjRp1ThEeIgoTTc-80mYKa5ryxZJFJYZy9WnHASNz-ELXTdCIkfDp54Iz2HU5dBxFuxZxNv5ObgXBP3LfpI6GMl3MHns0LXhD6G5br_po3RL1g4Qh8jSUvoY3TiPwEAAP__Vs0HXw">