commit e695ab227cc4cb7f825dbbe8a485f56e748211e1
author Dale Johannesen <dalej@apple.com> Tue May 13 20:06:43 2008 +0000
committer Dale Johannesen <dalej@apple.com> Tue May 13 20:06:43 2008 +0000
tree c321078e43d0f754db0827e10137ce7c2599e0f7
parent 03ce206143c56e18f3c087bb259625b770b91985

Fix for PR 2323, infinite loop in tail dup.

llvm-svn: 51063

llvm/lib/Transforms/Scalar/TailDuplication.cpp

diff --git a/llvm/lib/Transforms/Scalar/TailDuplication.cpp b/llvm/lib/Transforms/Scalar/TailDuplication.cpp
index 40da808..c8493b6 100644
--- a/llvm/lib/Transforms/Scalar/TailDuplication.cpp
+++ b/llvm/lib/Transforms/Scalar/TailDuplication.cpp
@@ -32,6 +32,7 @@
 #include "llvm/Support/Compiler.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/ADT/Statistic.h"
+#include "llvm/ADT/SmallPtrSet.h"
 #include <map>
 using namespace llvm;
 
@@ -51,6 +52,7 @@
   private:
     inline bool shouldEliminateUnconditionalBranch(TerminatorInst *TI);
     inline void eliminateUnconditionalBranch(BranchInst *BI);
+    SmallPtrSet<BasicBlock*, 4> CycleDetector;
   };
 }
 
@@ -61,17 +63,21 @@
 FunctionPass *llvm::createTailDuplicationPass() { return new TailDup(); }
 
 /// runOnFunction - Top level algorithm - Loop over each unconditional branch in
-/// the function, eliminating it if it looks attractive enough.
-///
+/// the function, eliminating it if it looks attractive enough.  CycleDetector
+/// prevents infinite loops by checking that we aren't redirecting a branch to
+/// a place it already pointed to earlier; see PR 2323.
 bool TailDup::runOnFunction(Function &F) {
   bool Changed = false;
-  for (Function::iterator I = F.begin(), E = F.end(); I != E; )
+  CycleDetector.clear();
+  for (Function::iterator I = F.begin(), E = F.end(); I != E; ) {
     if (shouldEliminateUnconditionalBranch(I->getTerminator())) {
       eliminateUnconditionalBranch(cast<BranchInst>(I->getTerminator()));
       Changed = true;
     } else {
       ++I;
+      CycleDetector.clear();
     }
+  }
   return Changed;
 }
 
@@ -140,7 +146,7 @@
       if (TooMany-- == 0) return false;
   }
   
-  // Finally, if this unconditional branch is a fall-through, be careful about
+  // If this unconditional branch is a fall-through, be careful about
   // tail duplicating it.  In particular, we don't want to taildup it if the
   // original block will still be there after taildup is completed: doing so
   // would eliminate the fall-through, requiring unconditional branches.
@@ -170,6 +176,11 @@
     }
   }
 
+  // Finally, check that we haven't redirected to this target block earlier;
+  // there are cases where we loop forever if we don't check this (PR 2323).
+  if (!CycleDetector.insert(Dest))
+    return false;
+
   return true;
 }