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

    <tr>
        <th>Summary</th>
        <td>
            Loop reroll creates incorrect IV increment
        </td>
    </tr>

    <tr>
      <th>Labels</th>
      <td>
            miscompilation,
            loopoptim
      </td>
    </tr>

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

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

<pre>
    The test below doesn't use contiguous IV increments, so it can't be rerolled that easily. Source iteration uses iv, iv+1, +2, +4, +5, +4 (skips + 3).
Plus the IV multiplication by 3 isn't taken into account.

Alive2 output:
```llvm
; Transforms/LoopReroll/extra_instr.ll
define void @rerollable2() {
%entry:
  br label %loop

%loop:
  %iv = phi i32 [ 0, %entry ], [ %iv.next, %loop ]
  %iv.mul3 = mul nsw nuw i32 %iv, 3
  %iv.scaled = add nsw nuw i32 %iv.mul3, 20
  %iv.scaled.div5 = udiv i32 %iv.scaled, 5
  call void @bar(i32 %iv.scaled.div5)
 %iv.scaled.add1 = add nsw nuw i32 %iv.scaled, 1
  %iv.scaled.add1.div5 = udiv i32 %iv.scaled.add1, 5
  call void @bar(i32 %iv.scaled.add1.div5)
 %iv.scaled.add2 = add nsw nuw i32 %iv.scaled, 2
  %iv.scaled.add2.div5 = udiv i32 %iv.scaled.add2, 5
  call void @bar(i32 %iv.scaled.add2.div5)
 %iv.scaled.add4 = add nsw nuw i32 %iv.scaled, 4
  %iv.scaled.add4.div5 = udiv i32 %iv.scaled.add4, 5
  call void @bar(i32 %iv.scaled.add4.div5)
 %iv.scaled.add5 = add nsw nuw i32 %iv.scaled, 5
  %iv.scaled.add5.div5 = udiv i32 %iv.scaled.add5, 5
  call void @bar(i32 %iv.scaled.add5.div5)
 %iv.scaled.add6 = add nsw nuw i32 %iv.scaled, 6
  %iv.scaled.add6.div5 = udiv i32 %iv.scaled.add6, 5
  call void @bar(i32 %iv.scaled.add6.div5)
 %iv.next = add nsw nuw i32 %iv, 1
  %cmp = icmp ult i32 %iv.next, 3
 br i1 %cmp, label #sink, label %exit

%exit:
  ret void
}
=>
define void @rerollable2() {
%entry:
  br label %loop

%loop:
  %iv = phi i32 [ 0, %entry ], [ %iv.next, %loop ]
 %0 = add i32 %iv, 24
  %1 = add i32 %iv, 20
  %iv.scaled.div5 = udiv i32 %1, 5
  call void @bar(i32 %iv.scaled.div5)
  %iv.scaled.add4.div5 = udiv i32 %0, 5
  call void @bar(i32 %iv.scaled.add4.div5)
  %iv.next = add nsw nuw i32 %iv, 1
  %exitcond = icmp eq i32 %iv, 8
  br i1 %exitcond, label %exit, label %loop#2

%loop#2:
  %iv#2 = phi i32 [ %iv.next, %loop ]
  %0#2 = add i32 %iv#2, 24
  %1#2 = add i32 %iv#2, 20
  %iv.scaled.div5#2 = udiv i32 %1#2, 5
  call void @bar(i32 %iv.scaled.div5#2)
  %iv.scaled.add4.div5#2 = udiv i32 %0#2, 5
  call void @bar(i32 %iv.scaled.add4.div5#2)
  %iv.next#2 = add nsw nuw i32 %iv#2, 1
  %exitcond#2 = icmp eq i32 %iv#2, 8
  br i1 %exitcond#2, label %exit, label #sink

%exit:
  ret void
}
Transformation doesn't verify! (unsound)
ERROR: Source is more defined than target

Example:

Source:
  >> Jump to %loop
i32 %iv = #x00000000 (0)
i32 %iv.mul3 = #x00000000 (0)
i32 %iv.scaled = #x00000014 (20)
i32 %iv.scaled.div5 = #x00000004 (4)
Function @bar returned
i32 %iv.scaled.add1 = #x00000015 (21)
i32 %iv.scaled.add1.div5 = #x00000004 (4)
Function @bar returned
i32 %iv.scaled.add2 = #x00000016 (22)
i32 %iv.scaled.add2.div5 = #x00000004 (4)
Function @bar returned
i32 %iv.scaled.add4 = #x00000018 (24)
i32 %iv.scaled.add4.div5 = #x00000004 (4)
Function @bar returned
i32 %iv.scaled.add5 = #x00000019 (25)
i32 %iv.scaled.add5.div5 = #x00000005 (5)
Function @bar returned
i32 %iv.scaled.add6 = #x0000001a (26)
i32 %iv.scaled.add6.div5 = #x00000005 (5)
...


Target:
  >> Jump to %loop
i32 %iv = #x00000000 (0)
i32 %0 = #x00000018 (24)
i32 %1 = #x00000014 (20)
i32 %iv.scaled.div5 = #x00000004 (4)
Function @bar returned
i32 %iv.scaled.add4.div5 = #x00000004 (4)
Function @bar returned
i32 %iv.next = #x00000001 (1)
i1 %exitcond = #x0 (0)
  >> Jump to %loop#2
i32 %iv#2 = #x00000001 (1)
i32 %0#2 = #x00000019 (25)
i32 %1#2 = #x00000015 (21)
i32 %iv.scaled.div5#2 = #x00000004 (4)
Function @bar returned
i32 %iv.scaled.add4.div5#2 = #x00000005 (5)
Function @bar triggered UB
i32 %iv.next#2 = UB triggered!
```
</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJzUmF1vozgXxz-Nc2NNBAdMk4tcTCaN9DwaaVfdmb1dGXAT7xib9Uum_fYrG0IgDQ3NtlptVSXBnHP8w_77-BhqDN9JxlaIrBHZzKize6VX0klVC1UzM8tV-bz6tmfYMmNxzoT6iUvFjERwZ7EzDBdKWr5zyhn8v98xl4VmFZPWIPiCjcLc4oI21jnDmmklBCux3VOLGTVcPM_xb8rpgmFumaaWK-njGswPPoT_XMf-F4I1tN9p-02O1xjBwvzgtfFXOEGwnKNog6LPvwpnsN0zz1Y5YXkteNF0kj_jBPP2SSz9wSTm0ipMi0I5adsAzednwQ8MsHK2dhYlbSvKouZfiEPVNiVr_E1TaR6VrgyC7Vel6ofw1Ai27Mlq-geXxuq5EI1HyR65ZPigeIlRGjUjRHPBAMECwRKju3UbGwiTVj93_WOcayxozgRGQIRSdZ_52HSyRkD4AaNkg-s9xzwBjMgaR80gNrExIptwTdaN-VyyJ9ta-HDBoB9vXjmRhKCVE1ian1i6n01wf9u7JkMHU1AvAe9Cy_KlS4jo_SC65Dgv-YEEb1fyQ8-tue0dydGvoEJ0Q5tTjWBxbh_CIVi2LoNbtCzjVzhPHcYXQb37Fdpg82bkLvA4N0zihjFumMANt3DDFe50Enc6xp1O4E5v4U6vcJNJ3GSMm0zgJrdwkyvc2STubIw7m8Cd3cKdXeT2yWgc-HwlFlUdjLn_4YTt0R2z2jE15RrzuPXx7cesmhguf_QbCHvi9izNhqZTmtXMhgds799tjlvDBiX3__Wkj4BE3QwMRh76izIesXlDRn97WhwqZmpuiN4jHdykT6-bQsnyJFL219B60ZvzRp9Hn5ea7DcEDUACl6Thm8_k4dteSGTK9h91nmdTncBLSVyxHZdG53gmj-TtO9Ax3FWZXOwzuqnPQcyLkhmMzAXZNJ1ekk7neUE-jddrEmosRmXUJL9bcl1XAjel9unEcGCaPz4j8CALJ41ynqMdkvuHh18eUPK5OxAYXCnNcJMtw6FBYkv1jg0y8P0TrWrBTmV5-Gxi9JWe3KPkHv_fVTW2apg8u1ELY4kgeYraP88ZdYTDGnWyca_iPZnH4dQC4_andNXrIzilnc_WySIMcSM_Px9OS1aOROwK2h4GCRjxOMawjH1PFjhnyQILvMoCH8OSnrMsAkv6Kkv6MSznEeNlYCGvspCLLGF2yT9gyc5ZaGDJXmXJprDM54Mzdps5muX9Ics2mjjFL5bIv7NS31VcXWXSCxWScG_hxy-KkmA8HMvRGenKjcEWdK3P3sY6UfTxJdurSWywp7__LF0KfWXpWc13O6ZZib-vL81WF_L7-mSLID579zQrV0m5TJZ0xlZxdgdLSBcRzParxSJ7XJKMJnHCsiXEJc2iLKV5FD1GhD7mM76CCJIojkicQBTBHJZAyiSJaQF5mS0BpRGrKBdzIQ7VXOndjBvj2IosF2k8C1WCCa8OASpuClXVXIQNH_kU_gUBeGGo2vLKt5DNTK98qE-52xmURoIba07BLbeCrb76KrM5EOFCM2qZwVwWSmtW2MErxpnTYrW3tjY-XcAWwXbH7d7l80JVCLbhrVzz9anW6k9WWATb8AgGwTY8xd8BAAD__1K6wys">