[LoopUnrollAndJam] Avoid repeated instructions for UAJ analysis

Avoid visiting repeated instructions for processHeaderPhiOperands as it can cause a scenario of endless loop. Test case is attached and can be ran with `opt -basic-aa -tbaa -loop-unroll-and-jam -allow-unroll-and-jam -unroll-and-jam-count=4`. Reviewed By: dmgreen Differential Revision: https://reviews.llvm.org/D97407
YuriPlyakhin · Apr 15, 2021 · 5548707 · 5548707
1 parent c8f0a7c
commit 5548707
Show file tree

Hide file tree

Showing 2 changed files with 384 additions and 1 deletion.
diff --git a/llvm/lib/Transforms/Utils/LoopUnrollAndJam.cpp b/llvm/lib/Transforms/Utils/LoopUnrollAndJam.cpp
@@ -141,6 +141,7 @@ template <typename T>
 static bool processHeaderPhiOperands(BasicBlock *Header, BasicBlock *Latch,
                                      BasicBlockSet &AftBlocks, T Visit) {
   SmallVector<Instruction *, 8> Worklist;
+  SmallPtrSet<Instruction *, 8> VisitedInstr;
   for (auto &Phi : Header->phis()) {
     Value *V = Phi.getIncomingValueForBlock(Latch);
     if (Instruction *I = dyn_cast<Instruction>(V))
@@ -151,11 +152,13 @@ static bool processHeaderPhiOperands(BasicBlock *Header, BasicBlock *Latch,
     Instruction *I = Worklist.pop_back_val();
     if (!Visit(I))
       return false;
+    VisitedInstr.insert(I);
 
     if (AftBlocks.count(I->getParent()))
       for (auto &U : I->operands())
         if (Instruction *II = dyn_cast<Instruction>(U))
-          Worklist.push_back(II);
+          if (!VisitedInstr.count(II))
+            Worklist.push_back(II);
   }
 
   return true;