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

    <tr>
        <th>Summary</th>
        <td>
            [IndVarSimplify] Order of visiting phi nodes with common SCEV but different no-wrap flags affects dependent SCEVs
        </td>
    </tr>

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

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

    <tr>
      <th>Reporter</th>
      <td>
          aleks-tmb
      </td>
    </tr>
</table>

<pre>
    
Consider case:
```llvm
define void @test(ptr %p) {
entry:
  br label %loop

loop:
  %iv0 = phi i32 [ %iv0.next, %loop ], [ 0, %entry ]
  %iv1 = phi i32 [ %iv1.next, %loop ], [ 0, %entry ]
  %iv0.next = add nuw nsw i32 %iv0, 1  
 %iv1.next = add i32 %iv1, 1
  %shl = shl i32 %iv1, 1
  %zext = zext i32 %shl to i64
  %gep = getelementptr inbounds i8, ptr %p, i64 %zext
 %load = load i32, ptr %gep
  %ec = icmp ult i32 %load, 100
  br i1 %ec, label %loop, label %exit

exit:
  ret void
}
```
1. Let's trace the order of creating SCEVs for phi nodes and for `%shl` - the user of `%iv1`.
- IndVarSimplifier starts simplification pass with the `%iv1`. 
- ScalarEvolution computes AddRec for that phi without `nuw/nsw` flags due to lack of these flags on the backedge value `%iv1.next = add i32 %iv1, 1`:
```llvm
PHISCEV = {0,+,1}<%loop>
```
- ScalarEvolution tries to prove created AddRec's no-wrap and computes loop's backedge taken count. During that computation `%shl` is being reached and gets SCEV computed, which is effectively a muliplication of `PHISCEV` and `2`:
```llvm
shlSCEV = {0,+,2}<%loop>
```
- Finishing with `%iv1` and its users simplification IndVarSimplifier goes to `%iv0`. 
- Since that phi has backage value with `nuw/nsw` flags, ScalarEvolution  refines PHISCEV  with those flags:
```llvm
PHISCEV  = {0,+,1}<nuw><nsw><%loop>
```
- `%iv1` gets that AddRec automatically updated, since it is common for both phi nodes. 
- But shlSCEV doesn't! Because dependency between `PHISCEV` and `shlSCEV` isn't known by ScalarEvolution and it couldn't update `shlSCEV` with no-wrap flags.

As a result IndVarSimplifier is not able to widen `%shl` up to 64 bits and to eliminate `%zext`.

2. But if we only change the order of phi nodes:
```llvm
...
loop:
  %iv1 = phi i32 [ %iv1.next, %loop ], [ 0, %entry ]
  %iv0 = phi i32 [ %iv0.next, %loop ], [ 0, %entry ]
...
```
Then IndVarSimplifier will start simplification with `%iv0` and `PHISCEV` will be initially created with `nuw/nsw` flags affecting `shlSCEV` :
```llvm
shlSCEV  = 2 * PHISCEV  = {0,+,2}<nuw><%loop>
```
It allows IndVarSimplifier to widen `shl` as well as inductive variable and to eliminate `zext`:
```llvm
define void @test(ptr %p) {
entry:
  br label %loop

loop: ; preds = %loop, %entry
  %indvars.iv = phi i64 [ %indvars.iv.next, %loop ], [ 0, %entry ]
  %indvars.iv.next = add nuw i64 %indvars.iv, 1
  %0 = shl i64 %indvars.iv, 1
  %gep = getelementptr inbounds i8, ptr %p, i64 %0
  %load = load i32, ptr %gep, align 4
  %ec = icmp ult i32 %load, 100
  br i1 %ec, label %loop, label %exit

exit:                                             ; preds = %loop
  ret void
}
```

</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJzEl02P2zgPgH-NciEmsBXn65DDZD7wFniBXWwXvcsWbWtHkQxJjpv99QvRduJkZjptsYsWxcSWSEoiH1K08F5VBnHHlnu2fJyJNtTW7YTGF38XDvkst_K0Y8kjS-4frPFKooNCeGSL-36UrZL-v9bHQz8ksVQG4WiVBJYlAX1gfNMEB4wvG8a3wNb7XhRNcKezLYDcgRY56iiprW2GNegvvV9EGV-qYwJs8QhNrUAtOLDlfhieG_waGH8Y7QBbPtLrcg_JME5r08TUYvq2xfTnLfabIbNCSjBtB8Z3vXmaj9opwKA0We6sc5ZNSXZi3teapOLv-1J_j8boYZCLKsGCWmUTyQobEqwwoMYDmhDjpkxuWyM9qE00fQnlQ1QfV7gcQFshyQw9qAWfaFXYTNbDguRUcWig1ee9RT06RJJM0FBprxJnrjGZDuBXFabc0PuFG4eB0BxE1o83HPev6Rz-j4HxtYfgRIEQagTrIv62hMKhCMpU8Pnh6YuH0joixliJHoSRNBJtkZfZKoE7MtD6Xr-fioFaJfN-wTv4ZOQX4T6rQ6NVqdCBD8IFD34YKURQ1kAjvIdOhZosXlmC0dTnQmjhno5Wt6RT2EPTBvRwL-UfWND2Qi0C7Trasm2IpkzbMf5sfBe3XGpReZAtRkq0KF7izkONHocpa2gLuSheUFYIR6HbyY6-jfAq-VYJ-f1_n6JrSZut9zFFGN8z_pDGgC0exrgvnt6M3msPBKfQx4M0zh6xDyDKwR8UZmPvOicaCt_ZXz1ca385ZBAvGB3amjCHx9ZFCsiVvU4fo6vQKw85RjGHoqhR0goVBk_0jGsR7l2tijoqYFliEdQR9QkEHFqtGj0C0PMzeCguEO2xVcI_8Kmv9ds-5d_p02dllK_jSQi_KXq0BxU8Ef4K2VdkV7YPxmgiuaZXGUq4gc9a9O4XZ8TG5V_jGp14G3pwdB95GKEas8eOJH8Pie-iGDexeIoPfnj40JFXniMS6LBDcoo22IMIqhBan6BtpBjo8OQXFSIghT0crKFEzm2oL-Xn4sZ9G2CMubToDePrwHgKeyxE6xEkNmgkmuIEOYYO0bwN1mCkZ5mswIuxnYH89MrZPQcxP7TsRfsD3NihCIwZRzGYT0v2vQcBDn28EV7Bo2KuBhC5psrUKYk3Gdc2cWKVQR6RjFsKFlCrgzLDVsYb61x--798Tl5TJXQI1ugTFLUw1U31P_v6W9zM5_P325b_oMn49xqh885vuP2zxjdSuVNa9zfVbdZfFYlkwtOEMNLOEZRRQRHvY2V-P8dB9MXRVDdQfU_xIzfFm-ge3s9sfpPZHyT0pwBCa9v5196Z8jnAKTx0qHX8VUa2VOXhKJwioN-CdSD117XcwBZ7aBxK3_vq0nSN9ExZNPIonJ-r4wXJ2CMOSJ5nf5r1awtXffXQjF5Ebhvh5NIsfyT6s51wMrHxUR_MH0BoVRnIfklLDD_y720GfqipnsndQm4XWzHDXbra8u06W6bZrN5lm0LguijX6zTdbLfposwyIfIVX-a83PDlTO14whfJhi_TLEuX2Xyzlgss0s1qsVmUIitZluBBKD2POTG3rpop71vcrbLtZjsjR3j6yOXcYAc0yTiP37xuF3Xu8rbyLEu08sFfrAQVNH0dX6X2iS0f4bfxPjgqr6gcXb4BqHoNdzQVmbwNIFVZokMTrm--oZ75830c-s-KWev0rg6hoXuGPzP-XKlQt_m8sAfGnyn7-5-7xtm_sAiMP9PJPOPPdPJ_AgAA__8dyqR3">