[LoopReroll] Fix rerolling loop with extra instructions

[kawashima-fj]

Summary

Fixes PR47627

This fix suppresses rerolling a loop which has an unrerollable
instruction.

Sample IR for the explanation below:

define void @foo([2 x i32]* nocapture %a) {
entry:
  br label %loop

loop:
  ; base instruction
  %indvar = phi i64 [ 0, %entry ], [ %indvar.next, %loop ]

  ; unrerollable instructions
  %stptrx = getelementptr inbounds [2 x i32], [2 x i32]* %a, i64 %indvar, i64 0
  store i32 999, i32* %stptrx, align 4

  ; extra simple arithmetic operations, used by root instructions
  %plus20 = add nuw nsw i64 %indvar, 20
  %plus10 = add nuw nsw i64 %indvar, 10

  ; root instruction 0
  %ldptr0 = getelementptr inbounds [2 x i32], [2 x i32]* %a, i64 %plus20, i64 0
  %value0 = load i32, i32* %ldptr0, align 4
  %stptr0 = getelementptr inbounds [2 x i32], [2 x i32]* %a, i64 %plus10, i64 0
  store i32 %value0, i32* %stptr0, align 4

  ; root instruction 1
  %ldptr1 = getelementptr inbounds [2 x i32], [2 x i32]* %a, i64 %plus20, i64 1
  %value1 = load i32, i32* %ldptr1, align 4
  %stptr1 = getelementptr inbounds [2 x i32], [2 x i32]* %a, i64 %plus10, i64 1
  store i32 %value1, i32* %stptr1, align 4

  ; loop-increment and latch
  %indvar.next = add nuw nsw i64 %indvar, 1
  %exitcond = icmp eq i64 %indvar.next, 5
  br i1 %exitcond, label %exit, label %loop

exit:
  ret void
}

In the loop rerolling pass, %indvar and %indvar.next are appended
to the LoopIncs vector in the LoopReroll::DAGRootTracker::findRoots
function.

Before this fix, two instructions with unrerollable instructions
comment above are marked as IL_All at the end of the
LoopReroll::DAGRootTracker::collectUsedInstructions function,
as well as instructions with extra simple arithmetic operations
comment and loop-increment and latch comment. It is incorrect
because IL_All means that the instruction should be executed in all
iterations of the rerolled loop but the store instruction should
not.

This fix rejects instructions which may have side effects and don't
belong to def-use chains of any root instructions and reductions.

See https://bugs.llvm.org/show_bug.cgi?id=47627 for more information.

[kawashima-fj]

clang-format reported a format error DenseSet<Instruction*> -> DenseSet<Instruction *> (space before *). However, other three places in the same function (and many places in other functions) have the same format. Should I change all places? only my change?, or keep all them unchanged?

[kawashima-fj]

Ping.
I know many of LLVM developers are busy with the developer's meeting now. When someone has time, please review.

[kawashima-fj]

Ping.

[kawashima-fj]

Ping.

[kawashima-fj]

Ping.
Can anyone review this fix?

[kawashima-fj]

Ping.

[Meinersbur]

Thanks for all the effort you put into this and sorry you had to wait so long for somebody to look at this.

I don't think the problem here is the LoopIncs. The unrerollable instructions can as well depend on %iv.next. You patch would still reroll the following:

define void @unrerollable_simple([2 x i32]* nocapture %a) {
entry:
  br label %loop

loop:
  ; base instruction
  %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop ]

  ; unrerollable instructions
  %iv.next = add nuw nsw i64 %iv, 1
  %stptrx = getelementptr inbounds [2 x i32], [2 x i32]* %a, i64 %iv.next, i64 0
  store i32 999, i32* %stptrx, align 4

  ; extra simple arithmetic operations, used by root instructions
  %plus20 = add nuw nsw i64 %iv, 20
  %plus10 = add nuw nsw i64 %iv, 10

  ; root instruction 0
  %ldptr0 = getelementptr inbounds [2 x i32], [2 x i32]* %a, i64 %plus20, i64 0
  %value0 = load i32, i32* %ldptr0, align 4
  %stptr0 = getelementptr inbounds [2 x i32], [2 x i32]* %a, i64 %plus10, i64 0
  store i32 %value0, i32* %stptr0, align 4

  ; root instruction 1
  %ldptr1 = getelementptr inbounds [2 x i32], [2 x i32]* %a, i64 %plus20, i64 1
  %value1 = load i32, i32* %ldptr1, align 4
  %stptr1 = getelementptr inbounds [2 x i32], [2 x i32]* %a, i64 %plus10, i64 1
  store i32 %value1, i32* %stptr1, align 4

  ; loop-increment and latch
  ;%iv.next = add nuw nsw i64 %iv, 1
  %exitcond = icmp eq i64 %iv.next, 5
  br i1 %exitcond, label %exit, label %loop

exit:
  ret void
}

To me the problem looks like that the unrerollable store does not belong to any root set and is skipped during verification.

In D88395#2299624, @kawashima-fj wrote:

clang-format reported a format error DenseSet<Instruction*> -> DenseSet<Instruction *> (space before *). However, other three places in the same function (and many places in other functions) have the same format. Should I change all places? only my change?, or keep all them unchanged?

Use the clang-format suggestion. To goal is to eventually converge to a completely clang-formatted codebase.

llvm/lib/Transforms/Scalar/LoopRerollPass.cpp

1076

[style] LLVM's coding style does not make use of Almost-Always-Auto.

llvm/test/Transforms/LoopReroll/extra_instr.ll

13

[nit] There's usually a space before CHECK

[kawashima-fj]

@Meinersbur Thanks for your review. I'll update the patch.

[kawashima-fj]

@Meinersbur I'm sorry for being late. I updated the patch. Please review again.

[Meinersbur]

Looks much simpler now ;-)

I will accept after fixing the LLVM_DEBUG message.

It has a lot fewer tests now, any reason to remove some tests (to clirify: I tihnk the current 3 tests are sufficient)

After that, would you like me to push the patch to the repository's main branch? Potentially also include it in release 12.0.1?

llvm/lib/Transforms/Scalar/LoopRerollPass.cpp

1085

[typo] An instruction which does not belongs to any root must not have side effects

[kawashima-fj]

@Meinersbur Thanks for your review. I've updated the patch. Correction of LLVM_DEBUG message and adding test patterns.

I can push it to the GitHub main branch by myself. I don't know the criteria of pushing patch to the release branch. Should it be pushed?

[Meinersbur]

In D88395#2711046, @kawashima-fj wrote:

I can push it to the GitHub main branch by myself. I don't know the criteria of pushing patch to the release branch. Should it be pushed?

You don't push yourself.

The protocol is that you close the bug report and fill the "fixed by commit" field, then add the bug as a release blocker of the 12.0.1 meta-bug.

[kawashima-fj]

Pushed to the main branch. I'm sorry, I forgot to add Differential Revision: line. The commit is d9a9c992d190dd6645ea911b66cf0cadba0dadc3 .

llvm/lib/Transforms/Scalar/LoopRerollPass.cpp

for (auto &DRS : RootSets) {
     }
   }
 
   // Make sure the loop increments are also accounted for.
 
   Exclude.clear();
   for (auto &DRS : RootSets) {
     Exclude.insert(DRS.Roots.begin(), DRS.Roots.end());
     Exclude.insert(DRS.SubsumedInsts.begin(), DRS.SubsumedInsts.end());
     Exclude.insert(DRS.BaseInst);
   }
 
   DenseSet<Instruction*> V;
   collectInLoopUserSet(LoopIncs, Exclude, PossibleRedSet, V);
   for (auto *I : V) {
+    if (I->mayHaveSideEffects()) {
+      LLVM_DEBUG(dbgs() << "LRR: Aborting - "
+                        << "An instruction which does not belong to any root "
+                        << "sets must not have side effects: " << *I);
+      return false;
+    }
     Uses[I].set(IL_All);
   }
 
   return true;
 }
 
 /// Get the next instruction in "In" that is a member of set Val.
 /// Start searching from StartI, and do not return anything in Exclude.

llvm/test/Transforms/LoopReroll/extra_instr.ll

+; RUN: opt -S  -loop-reroll   %s | FileCheck %s
+target triple = "aarch64--linux-gnu"
+
+define void @rerollable1([2 x i32]* nocapture %a) {
+entry:
+  br label %loop
+
+loop:
+
+; CHECK-LABEL: loop:
+; CHECK-NEXT:    %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop ]
+; CHECK-NEXT:    [[SCEVGEP1:%.*]] = getelementptr [2 x i32], [2 x i32]* %a, i64 20, i64 %iv
+; CHECK-NEXT:    [[SCEVGEP2:%.*]] = getelementptr [2 x i32], [2 x i32]* %a, i64 10, i64 %iv
+; CHECK-NEXT:    [[VALUE:%.*]] = load i32, i32* [[SCEVGEP1]], align 4
+; CHECK-NEXT:    store i32 [[VALUE]], i32* [[SCEVGEP2]], align 4
+
+  ; base instruction
+  %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop ]
+
+  ; NO unrerollable instructions
+
+  ; extra simple arithmetic operations, used by root instructions
+  %plus20 = add nuw nsw i64 %iv, 20
+  %plus10 = add nuw nsw i64 %iv, 10
+
+  ; root instruction 0
+  %ldptr0 = getelementptr inbounds [2 x i32], [2 x i32]* %a, i64 %plus20, i64 0
+  %value0 = load i32, i32* %ldptr0, align 4
+  %stptr0 = getelementptr inbounds [2 x i32], [2 x i32]* %a, i64 %plus10, i64 0
+  store i32 %value0, i32* %stptr0, align 4
+
+  ; root instruction 1
+  %ldptr1 = getelementptr inbounds [2 x i32], [2 x i32]* %a, i64 %plus20, i64 1
+  %value1 = load i32, i32* %ldptr1, align 4
+  %stptr1 = getelementptr inbounds [2 x i32], [2 x i32]* %a, i64 %plus10, i64 1
+  store i32 %value1, i32* %stptr1, align 4
+
+  ; loop-increment
+  %iv.next = add nuw nsw i64 %iv, 1
+
+  ; latch
+  %exitcond = icmp eq i64 %iv.next, 5
+  br i1 %exitcond, label %exit, label %loop
+
+exit:
+  ret void
+}
+
+define void @unrerollable1([2 x i32]* nocapture %a) {
+entry:
+  br label %loop
+
+loop:
+
+; CHECK-LABEL: loop:
+; CHECK-NEXT:    %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop ]
+; CHECK-NEXT:    %stptrx = getelementptr inbounds [2 x i32], [2 x i32]* %a, i64 %iv, i64 0
+; CHECK-NEXT:    store i32 999, i32* %stptrx, align 4
+
+  ; base instruction
+  %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop ]
+
+  ; unrerollable instructions using %iv
+  %stptrx = getelementptr inbounds [2 x i32], [2 x i32]* %a, i64 %iv, i64 0
+  store i32 999, i32* %stptrx, align 4
+
+  ; extra simple arithmetic operations, used by root instructions
+  %plus20 = add nuw nsw i64 %iv, 20
+  %plus10 = add nuw nsw i64 %iv, 10
+
+  ; root instruction 0
+  %ldptr0 = getelementptr inbounds [2 x i32], [2 x i32]* %a, i64 %plus20, i64 0
+  %value0 = load i32, i32* %ldptr0, align 4
+  %stptr0 = getelementptr inbounds [2 x i32], [2 x i32]* %a, i64 %plus10, i64 0
+  store i32 %value0, i32* %stptr0, align 4
+
+  ; root instruction 1
+  %ldptr1 = getelementptr inbounds [2 x i32], [2 x i32]* %a, i64 %plus20, i64 1
+  %value1 = load i32, i32* %ldptr1, align 4
+  %stptr1 = getelementptr inbounds [2 x i32], [2 x i32]* %a, i64 %plus10, i64 1
+  store i32 %value1, i32* %stptr1, align 4
+
+  ; loop-increment
+  %iv.next = add nuw nsw i64 %iv, 1
+
+  ; latch
+  %exitcond = icmp eq i64 %iv.next, 5
+  br i1 %exitcond, label %exit, label %loop
+
+exit:
+  ret void
+}
+
+define void @unrerollable2([2 x i32]* nocapture %a) {
+entry:
+  br label %loop
+
+loop:
+
+; CHECK-LABEL: loop:
+; CHECK-NEXT:    %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop ]
+; CHECK-NEXT:    %iv.next = add nuw nsw i64 %iv, 1
+; CHECK-NEXT:    %stptrx = getelementptr inbounds [2 x i32], [2 x i32]* %a, i64 %iv.next, i64 0
+; CHECK-NEXT:    store i32 999, i32* %stptrx, align 4
+
+  ; base instruction
+  %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop ]
+
+  ; loop-increment
+  %iv.next = add nuw nsw i64 %iv, 1
+
+  ; unrerollable instructions using %iv.next
+  %stptrx = getelementptr inbounds [2 x i32], [2 x i32]* %a, i64 %iv.next, i64 0
+  store i32 999, i32* %stptrx, align 4
+
+  ; extra simple arithmetic operations, used by root instructions
+  %plus20 = add nuw nsw i64 %iv, 20
+  %plus10 = add nuw nsw i64 %iv, 10
+
+  ; root instruction 0
+  %ldptr0 = getelementptr inbounds [2 x i32], [2 x i32]* %a, i64 %plus20, i64 0
+  %value0 = load i32, i32* %ldptr0, align 4
+  %stptr0 = getelementptr inbounds [2 x i32], [2 x i32]* %a, i64 %plus10, i64 0
+  store i32 %value0, i32* %stptr0, align 4
+
+  ; root instruction 1
+  %ldptr1 = getelementptr inbounds [2 x i32], [2 x i32]* %a, i64 %plus20, i64 1
+  %value1 = load i32, i32* %ldptr1, align 4
+  %stptr1 = getelementptr inbounds [2 x i32], [2 x i32]* %a, i64 %plus10, i64 1
+  store i32 %value1, i32* %stptr1, align 4
+
+  ; latch
+  %exitcond = icmp eq i64 %iv.next, 5
+  br i1 %exitcond, label %exit, label %loop
+
+exit:
+  ret void
+}
+
+define dso_local void @rerollable2() {
+entry:
+  br label %loop
+
+loop:
+
+; CHECK-LABEL: loop:
+; CHECK-NEXT:    %iv = phi i32 [ 0, %entry ], [ %iv.next, %loop ]
+; CHECK-NEXT:    {{%.*}} = add i32 %iv, {{20|24}}
+; CHECK-NEXT:    {{%.*}} = add i32 %iv, {{20|24}}
+
+  ; induction variable
+  %iv = phi i32 [ 0, %entry ], [ %iv.next, %loop ]
+
+  ; scale instruction
+  %iv.mul3 = mul nuw nsw i32 %iv, 3
+
+  ; extra simple arithmetic operations, used by root instructions
+  %iv.scaled = add nuw nsw i32 %iv.mul3, 20
+
+  ; NO unrerollable instructions
+
+  ; root set 1
+
+  ; base instruction
+  %iv.scaled.div5 = udiv i32 %iv.scaled, 5
+  tail call void @bar(i32 %iv.scaled.div5)
+  ; root instruction 0
+  %iv.scaled.add1 = add nuw nsw i32 %iv.scaled, 1
+  %iv.scaled.add1.div5 = udiv i32 %iv.scaled.add1, 5
+  tail call void @bar(i32 %iv.scaled.add1.div5)
+  ; root instruction 2
+  %iv.scaled.add2 = add nuw nsw i32 %iv.scaled, 2
+  %iv.scaled.add2.div5 = udiv i32 %iv.scaled.add2, 5
+  tail call void @bar(i32 %iv.scaled.add2.div5)
+
+  ; root set 2
+
+  ; base instruction
+  %iv.scaled.add4 = add nuw nsw i32 %iv.scaled, 4
+  %iv.scaled.add4.div5 = udiv i32 %iv.scaled.add4, 5
+  tail call void @bar(i32 %iv.scaled.add4.div5)
+  ; root instruction 0
+  %iv.scaled.add5 = add nuw nsw i32 %iv.scaled, 5
+  %iv.scaled.add5.div5 = udiv i32 %iv.scaled.add5, 5
+  tail call void @bar(i32 %iv.scaled.add5.div5)
+  ; root instruction 2
+  %iv.scaled.add6 = add nuw nsw i32 %iv.scaled, 6
+  %iv.scaled.add6.div5 = udiv i32 %iv.scaled.add6, 5
+  tail call void @bar(i32 %iv.scaled.add6.div5)
+
+  ; loop-increment
+  %iv.next = add nuw nsw i32 %iv, 1
+
+  ; latch
+  %cmp = icmp ult i32 %iv.next, 3
+  br i1 %cmp, label %loop, label %exit
+
+exit:
+  ret void
+}
+
+define dso_local void @unrerollable3() {
+entry:
+  br label %loop
+
+loop:
+
+; CHECK-LABEL: loop:
+; CHECK-NEXT:    %iv = phi i32 [ 0, %entry ], [ %iv.next, %loop ]
+; CHECK-NEXT:    %iv.mul3 = mul nuw nsw i32 %iv, 3
+; CHECK-NEXT:    %iv.scaled = add nuw nsw i32 %iv.mul3, 20
+; CHECK-NEXT:    %iv.mul7 = mul nuw nsw i32 %iv, 7
+; CHECK-NEXT:    tail call void @bar(i32 %iv.mul7)
+
+  ; induction variable
+  %iv = phi i32 [ 0, %entry ], [ %iv.next, %loop ]
+
+  ; scale instruction
+  %iv.mul3 = mul nuw nsw i32 %iv, 3
+
+  ; extra simple arithmetic operations, used by root instructions
+  %iv.scaled = add nuw nsw i32 %iv.mul3, 20
+
+  ; unrerollable instructions using %iv
+  %iv.mul7 = mul nuw nsw i32 %iv, 7
+  tail call void @bar(i32 %iv.mul7)
+
+  ; root set 1
+
+  ; base instruction
+  %iv.scaled.div5 = udiv i32 %iv.scaled, 5
+  tail call void @bar(i32 %iv.scaled.div5)
+  ; root instruction 0
+  %iv.scaled.add1 = add nuw nsw i32 %iv.scaled, 1
+  %iv.scaled.add1.div5 = udiv i32 %iv.scaled.add1, 5
+  tail call void @bar(i32 %iv.scaled.add1.div5)
+  ; root instruction 2
+  %iv.scaled.add2 = add nuw nsw i32 %iv.scaled, 2
+  %iv.scaled.add2.div5 = udiv i32 %iv.scaled.add2, 5
+  tail call void @bar(i32 %iv.scaled.add2.div5)
+
+  ; root set 2
+
+  ; base instruction
+  %iv.scaled.add4 = add nuw nsw i32 %iv.scaled, 4
+  %iv.scaled.add4.div5 = udiv i32 %iv.scaled.add4, 5
+  tail call void @bar(i32 %iv.scaled.add4.div5)
+  ; root instruction 0
+  %iv.scaled.add5 = add nuw nsw i32 %iv.scaled, 5
+  %iv.scaled.add5.div5 = udiv i32 %iv.scaled.add5, 5
+  tail call void @bar(i32 %iv.scaled.add5.div5)
+  ; root instruction 2
+  %iv.scaled.add6 = add nuw nsw i32 %iv.scaled, 6
+  %iv.scaled.add6.div5 = udiv i32 %iv.scaled.add6, 5
+  tail call void @bar(i32 %iv.scaled.add6.div5)
+
+  ; loop-increment
+  %iv.next = add nuw nsw i32 %iv, 1
+
+  ; latch
+  %cmp = icmp ult i32 %iv.next, 3
+  br i1 %cmp, label %loop, label %exit
+
+exit:
+  ret void
+}
+
+declare dso_local void @bar(i32)