[LoopReroll] with multiple roots incorrectly reorders instructions with side effects

[nunoplopes]

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:

; 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!

[luxufan]

I manually modified your llvm ir and the problem you said did not occur. See: https://alive2.llvm.org/ce/z/-98MkH

[nunoplopes]

It does: https://alive2.llvm.org/ce/z/rJ5o4J
You need to specify the unroll factor by hand (until we implement something more automatic).

[caojoshua]

Reduced testcase. I removed the divisions so its a little easier to read.

The increments are actually correct, but the order in which bar() is called is incorrect. Giving pseudo source:

for (int i = 0; i  < 3; ++i) {
  i1 = i * 3 + 20
  bar(i1)
  bar(i1+1)
  bar(i1+2)
  bar(i1+4) // Skipped +3. i1+4 becomes a new root
  bar(i1+5)
  bar(i1+6)
}

Pseudo code after LoopReroll:

for (int i = 0; i < 8; ++i) {
  i1 = i + 20
  i2 = i + 24
  bar(i1)
  bar(i2)
}

If we step through the first iteration of source where i=0, this is the order in which we call bar()

bar(20)
bar(21)
bar(22)
bar(24)
bar(25)
bar(26)

And if we step through the first 3 iterations (scale is 3 here), this is the order in which we call bar:

bar(20)
bar(24)
bar(21)
bar(25)
bar(22)
bar(26)

Note that that we call bar with the right parameters, which means the increments are correct. Similar exercise shows the same for further iterations. But the order is incorrect, which is why alive is complaining.

This problem seems to come from the introduction of multiple root sets. If the loops contains calls with side effects, or has dependent memory accesses, we should not reroll.

[nikic]

The LoopReroll pass has been removed by #80972.