From b42c8f71017f29d006741f0fa4ce8de227e7226f Mon Sep 17 00:00:00 2001 From: Chris Lattner Date: Tue, 13 Nov 2007 07:32:38 +0000 Subject: [PATCH] Implement PR1786 by iterating between dead cycle elimination and simplifycfg in the rare cases when it is needed. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@44044 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Transforms/Scalar/SimplifyCFG.cpp | 96 +++++++++++------ .../SimplifyCFG/iterative-simplify.ll | 100 ++++++++++++++++++ 2 files changed, 163 insertions(+), 33 deletions(-) create mode 100644 test/Transforms/SimplifyCFG/iterative-simplify.ll diff --git a/lib/Transforms/Scalar/SimplifyCFG.cpp b/lib/Transforms/Scalar/SimplifyCFG.cpp index 5f0ab19b5e2..200264e9174 100644 --- a/lib/Transforms/Scalar/SimplifyCFG.cpp +++ b/lib/Transforms/Scalar/SimplifyCFG.cpp @@ -27,6 +27,7 @@ #include "llvm/Support/CFG.h" #include "llvm/Support/Compiler.h" #include "llvm/Pass.h" +#include "llvm/ADT/SmallVector.h" #include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/Statistic.h" using namespace llvm; @@ -50,9 +51,9 @@ FunctionPass *llvm::createCFGSimplificationPass() { } static bool MarkAliveBlocks(BasicBlock *BB, - SmallPtrSet &Reachable) { + SmallPtrSet &Reachable) { - std::vector Worklist; + SmallVector Worklist; Worklist.push_back(BB); bool Changed = false; while (!Worklist.empty()) { @@ -93,42 +94,46 @@ static bool MarkAliveBlocks(BasicBlock *BB, return Changed; } - -// It is possible that we may require multiple passes over the code to fully -// simplify the CFG. -// -bool CFGSimplifyPass::runOnFunction(Function &F) { - SmallPtrSet Reachable; +/// RemoveUnreachableBlocks - Remove blocks that are not reachable, even if they +/// are in a dead cycle. Return true if a change was made, false otherwise. +static bool RemoveUnreachableBlocks(Function &F) { + SmallPtrSet Reachable; bool Changed = MarkAliveBlocks(F.begin(), Reachable); - + // If there are unreachable blocks in the CFG... - if (Reachable.size() != F.size()) { - assert(Reachable.size() < F.size()); - NumSimpl += F.size()-Reachable.size(); - - // Loop over all of the basic blocks that are not reachable, dropping all of - // their internal references... - for (Function::iterator BB = ++F.begin(), E = F.end(); BB != E; ++BB) - if (!Reachable.count(BB)) { - for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); SI!=SE; ++SI) - if (Reachable.count(*SI)) - (*SI)->removePredecessor(BB); - BB->dropAllReferences(); - } - - for (Function::iterator I = ++F.begin(); I != F.end();) - if (!Reachable.count(I)) - I = F.getBasicBlockList().erase(I); - else - ++I; - - Changed = true; - } + if (Reachable.size() == F.size()) + return Changed; + + assert(Reachable.size() < F.size()); + NumSimpl += F.size()-Reachable.size(); + + // Loop over all of the basic blocks that are not reachable, dropping all of + // their internal references... + for (Function::iterator BB = ++F.begin(), E = F.end(); BB != E; ++BB) + if (!Reachable.count(BB)) { + for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); SI!=SE; ++SI) + if (Reachable.count(*SI)) + (*SI)->removePredecessor(BB); + BB->dropAllReferences(); + } + + for (Function::iterator I = ++F.begin(); I != F.end();) + if (!Reachable.count(I)) + I = F.getBasicBlockList().erase(I); + else + ++I; + + return true; +} +/// IterativeSimplifyCFG - Call SimplifyCFG on all the blocks in the function, +/// iterating until no more changes are made. +static bool IterativeSimplifyCFG(Function &F) { + bool Changed = false; bool LocalChange = true; while (LocalChange) { LocalChange = false; - + // Loop over all of the basic blocks (except the first one) and remove them // if they are unneeded... // @@ -140,6 +145,31 @@ bool CFGSimplifyPass::runOnFunction(Function &F) { } Changed |= LocalChange; } - return Changed; } + +// It is possible that we may require multiple passes over the code to fully +// simplify the CFG. +// +bool CFGSimplifyPass::runOnFunction(Function &F) { + bool EverChanged = RemoveUnreachableBlocks(F); + EverChanged |= IterativeSimplifyCFG(F); + + // If neither pass changed anything, we're done. + if (!EverChanged) return false; + + // IterativeSimplifyCFG can (rarely) make some loops dead. If this happens, + // RemoveUnreachableBlocks is needed to nuke them, which means we should + // iterate between the two optimizations. We structure the code like this to + // avoid reruning IterativeSimplifyCFG if the second pass of + // RemoveUnreachableBlocks doesn't do anything. + if (!RemoveUnreachableBlocks(F)) + return true; + + do { + EverChanged = IterativeSimplifyCFG(F); + EverChanged |= RemoveUnreachableBlocks(F); + } while (EverChanged); + + return true; +} diff --git a/test/Transforms/SimplifyCFG/iterative-simplify.ll b/test/Transforms/SimplifyCFG/iterative-simplify.ll new file mode 100644 index 00000000000..9081b01b20a --- /dev/null +++ b/test/Transforms/SimplifyCFG/iterative-simplify.ll @@ -0,0 +1,100 @@ +; RUN: llvm-as < %s | opt -simplifycfg | llvm-dis | not grep bb17 +; PR1786 + +define i32 @main() { +entry: + %retval = alloca i32, align 4 ; [#uses=1] + %i = alloca i32, align 4 ; [#uses=7] + %z = alloca i32, align 4 ; [#uses=4] + %z16 = alloca i32, align 4 ; [#uses=4] + %"alloca point" = bitcast i32 0 to i32 ; [#uses=0] + store i32 0, i32* %i + %toBool = icmp ne i8 1, 0 ; [#uses=1] + br i1 %toBool, label %cond_true, label %cond_false + +cond_true: ; preds = %entry + store i32 0, i32* %z + br label %bb + +bb: ; preds = %cond_next, %cond_true + %tmp = load i32* %z ; [#uses=1] + %tmp1 = sub i32 %tmp, 16384 ; [#uses=1] + store i32 %tmp1, i32* %z + %tmp2 = load i32* %i ; [#uses=1] + %tmp3 = add i32 %tmp2, 1 ; [#uses=1] + store i32 %tmp3, i32* %i + %tmp4 = load i32* %i ; [#uses=1] + %tmp5 = icmp sgt i32 %tmp4, 262144 ; [#uses=1] + %tmp56 = zext i1 %tmp5 to i8 ; [#uses=1] + %toBool7 = icmp ne i8 %tmp56, 0 ; [#uses=1] + br i1 %toBool7, label %cond_true8, label %cond_next + +cond_true8: ; preds = %bb + call void @abort( ) + unreachable + +cond_next: ; preds = %bb + %tmp9 = load i32* %z ; [#uses=1] + %tmp10 = icmp ne i32 %tmp9, 0 ; [#uses=1] + %tmp1011 = zext i1 %tmp10 to i8 ; [#uses=1] + %toBool12 = icmp ne i8 %tmp1011, 0 ; [#uses=1] + br i1 %toBool12, label %bb, label %bb13 + +bb13: ; preds = %cond_next + call void @exit( i32 0 ) + unreachable + +cond_false: ; preds = %entry + %toBool14 = icmp ne i8 1, 0 ; [#uses=1] + br i1 %toBool14, label %cond_true15, label %cond_false33 + +cond_true15: ; preds = %cond_false + store i32 0, i32* %z16 + br label %bb17 + +bb17: ; preds = %cond_next27, %cond_true15 + %tmp18 = load i32* %z16 ; [#uses=1] + %tmp19 = sub i32 %tmp18, 16384 ; [#uses=1] + store i32 %tmp19, i32* %z16 + %tmp20 = load i32* %i ; [#uses=1] + %tmp21 = add i32 %tmp20, 1 ; [#uses=1] + store i32 %tmp21, i32* %i + %tmp22 = load i32* %i ; [#uses=1] + %tmp23 = icmp sgt i32 %tmp22, 262144 ; [#uses=1] + %tmp2324 = zext i1 %tmp23 to i8 ; [#uses=1] + %toBool25 = icmp ne i8 %tmp2324, 0 ; [#uses=1] + br i1 %toBool25, label %cond_true26, label %cond_next27 + +cond_true26: ; preds = %bb17 + call void @abort( ) + unreachable + +cond_next27: ; preds = %bb17 + %tmp28 = load i32* %z16 ; [#uses=1] + %tmp29 = icmp ne i32 %tmp28, 0 ; [#uses=1] + %tmp2930 = zext i1 %tmp29 to i8 ; [#uses=1] + %toBool31 = icmp ne i8 %tmp2930, 0 ; [#uses=1] + br i1 %toBool31, label %bb17, label %bb32 + +bb32: ; preds = %cond_next27 + call void @exit( i32 0 ) + unreachable + +cond_false33: ; preds = %cond_false + call void @exit( i32 0 ) + unreachable + +cond_next34: ; No predecessors! + br label %cond_next35 + +cond_next35: ; preds = %cond_next34 + br label %return + +return: ; preds = %cond_next35 + %retval36 = load i32* %retval ; [#uses=1] + ret i32 %retval36 +} + +declare void @abort() + +declare void @exit(i32) -- 2.34.1