summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorDale Johannesen <dalej@apple.com>2008-05-13 20:06:43 +0000
committerDale Johannesen <dalej@apple.com>2008-05-13 20:06:43 +0000
commit72997fedab2cac75e783e3507c9ac0a6af567569 (patch)
treeac840347e8c334616bd84ab6bfbbe4f0fe855ec6
parent3b34e1e9e8af6d173699fd2de937fc609752a048 (diff)
downloadllvm-72997fedab2cac75e783e3507c9ac0a6af567569.tar.gz
llvm-72997fedab2cac75e783e3507c9ac0a6af567569.tar.bz2
llvm-72997fedab2cac75e783e3507c9ac0a6af567569.tar.xz
Fix for PR 2323, infinite loop in tail dup.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@51063 91177308-0d34-0410-b5e6-96231b3b80d8
-rw-r--r--lib/Transforms/Scalar/TailDuplication.cpp19
-rw-r--r--test/Transforms/TailDup/2008-05-13-InfiniteLoop.ll26
2 files changed, 41 insertions, 4 deletions
diff --git a/lib/Transforms/Scalar/TailDuplication.cpp b/lib/Transforms/Scalar/TailDuplication.cpp
index 40da808f67..c8493b6a5f 100644
--- a/lib/Transforms/Scalar/TailDuplication.cpp
+++ b/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 @@ namespace {
private:
inline bool shouldEliminateUnconditionalBranch(TerminatorInst *TI);
inline void eliminateUnconditionalBranch(BranchInst *BI);
+ SmallPtrSet<BasicBlock*, 4> CycleDetector;
};
}
@@ -61,17 +63,21 @@ static RegisterPass<TailDup> X("tailduplicate", "Tail Duplication");
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 @@ bool TailDup::shouldEliminateUnconditionalBranch(TerminatorInst *TI) {
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 @@ bool TailDup::shouldEliminateUnconditionalBranch(TerminatorInst *TI) {
}
}
+ // 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;
}
diff --git a/test/Transforms/TailDup/2008-05-13-InfiniteLoop.ll b/test/Transforms/TailDup/2008-05-13-InfiniteLoop.ll
new file mode 100644
index 0000000000..a67e8cdd0c
--- /dev/null
+++ b/test/Transforms/TailDup/2008-05-13-InfiniteLoop.ll
@@ -0,0 +1,26 @@
+; RUN: llvm-as < %s | opt -tailduplicate | llc
+; PR2323
+
+define i32 @func_27(i32 %p_28) nounwind {
+entry:
+ %tmp125 = trunc i32 %p_28 to i8 ; <i8> [#uses=1]
+ %tmp5.i = icmp eq i8 %tmp125, 0 ; <i1> [#uses=1]
+ br i1 %tmp5.i, label %bb8.i, label %bb.i
+
+bb.i: ; preds = %entry
+ br label %bb39.i
+
+bb8.i: ; preds = %entry
+ br label %bb11.i
+
+bb11.i: ; preds = %bb39.i, %bb8.i
+ %tmp126 = trunc i32 %p_28 to i8 ; <i8> [#uses=1]
+ br label %bb39.i
+
+bb39.i: ; preds = %bb11.i, %bb.i
+ %tmp127 = trunc i32 %p_28 to i8 ; <i8> [#uses=1]
+ br label %bb11.i
+
+func_29.exit: ; No predecessors!
+ ret i32 undef
+}