X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FTransforms%2FScalar%2FSimplifyCFGPass.cpp;h=8371f6d35279ebd05879b4b0f2688266090e311d;hb=3e033f29239e48c190f29cdf3a02cdfbaf2fe72b;hp=97441008c46c74c408a1ec4d43311f0435f99d41;hpb=c7d7e0cbe0a83881e4a01b0be745e169bd1baea0;p=oota-llvm.git diff --git a/lib/Transforms/Scalar/SimplifyCFGPass.cpp b/lib/Transforms/Scalar/SimplifyCFGPass.cpp index 97441008c46..8371f6d3527 100644 --- a/lib/Transforms/Scalar/SimplifyCFGPass.cpp +++ b/lib/Transforms/Scalar/SimplifyCFGPass.cpp @@ -23,196 +23,64 @@ #define DEBUG_TYPE "simplifycfg" #include "llvm/Transforms/Scalar.h" -#include "llvm/Transforms/Utils/Local.h" -#include "llvm/Constants.h" -#include "llvm/Instructions.h" -#include "llvm/IntrinsicInst.h" -#include "llvm/Module.h" -#include "llvm/Attributes.h" -#include "llvm/Support/CFG.h" -#include "llvm/Pass.h" -#include "llvm/Target/TargetData.h" -#include "llvm/ADT/SmallVector.h" #include "llvm/ADT/SmallPtrSet.h" +#include "llvm/ADT/SmallVector.h" #include "llvm/ADT/Statistic.h" +#include "llvm/Analysis/TargetTransformInfo.h" +#include "llvm/IR/Attributes.h" +#include "llvm/IR/Constants.h" +#include "llvm/IR/DataLayout.h" +#include "llvm/IR/Instructions.h" +#include "llvm/IR/IntrinsicInst.h" +#include "llvm/IR/Module.h" +#include "llvm/Pass.h" +#include "llvm/Support/CFG.h" +#include "llvm/Transforms/Utils/Local.h" using namespace llvm; STATISTIC(NumSimpl, "Number of blocks simplified"); namespace { - struct CFGSimplifyPass : public FunctionPass { - static char ID; // Pass identification, replacement for typeid - CFGSimplifyPass() : FunctionPass(&ID) {} +struct CFGSimplifyPass : public FunctionPass { + static char ID; // Pass identification, replacement for typeid + CFGSimplifyPass() : FunctionPass(ID) { + initializeCFGSimplifyPassPass(*PassRegistry::getPassRegistry()); + } + virtual bool runOnFunction(Function &F); - virtual bool runOnFunction(Function &F); - }; + virtual void getAnalysisUsage(AnalysisUsage &AU) const { + AU.addRequired(); + } +}; } char CFGSimplifyPass::ID = 0; -static RegisterPass X("simplifycfg", "Simplify the CFG"); +INITIALIZE_PASS_BEGIN(CFGSimplifyPass, "simplifycfg", "Simplify the CFG", false, + false) +INITIALIZE_AG_DEPENDENCY(TargetTransformInfo) +INITIALIZE_PASS_END(CFGSimplifyPass, "simplifycfg", "Simplify the CFG", false, + false) // Public interface to the CFGSimplification pass FunctionPass *llvm::createCFGSimplificationPass() { return new CFGSimplifyPass(); } -/// ChangeToUnreachable - Insert an unreachable instruction before the specified -/// instruction, making it and the rest of the code in the block dead. -static void ChangeToUnreachable(Instruction *I, bool UseLLVMTrap) { - BasicBlock *BB = I->getParent(); - // Loop over all of the successors, removing BB's entry from any PHI - // nodes. - for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); SI != SE; ++SI) - (*SI)->removePredecessor(BB); - - // Insert a call to llvm.trap right before this. This turns the undefined - // behavior into a hard fail instead of falling through into random code. - if (UseLLVMTrap) { - Function *TrapFn = - Intrinsic::getDeclaration(BB->getParent()->getParent(), Intrinsic::trap); - CallInst::Create(TrapFn, "", I); - } - new UnreachableInst(I->getContext(), I); - - // All instructions after this are dead. - BasicBlock::iterator BBI = I, BBE = BB->end(); - while (BBI != BBE) { - if (!BBI->use_empty()) - BBI->replaceAllUsesWith(UndefValue::get(BBI->getType())); - BB->getInstList().erase(BBI++); - } -} - -/// ChangeToCall - Convert the specified invoke into a normal call. -static void ChangeToCall(InvokeInst *II) { - BasicBlock *BB = II->getParent(); - SmallVector Args(II->op_begin(), II->op_end() - 3); - CallInst *NewCall = CallInst::Create(II->getCalledValue(), Args.begin(), - Args.end(), "", II); - NewCall->takeName(II); - NewCall->setCallingConv(II->getCallingConv()); - NewCall->setAttributes(II->getAttributes()); - II->replaceAllUsesWith(NewCall); - - // Follow the call by a branch to the normal destination. - BranchInst::Create(II->getNormalDest(), II); - - // Update PHI nodes in the unwind destination - II->getUnwindDest()->removePredecessor(BB); - BB->getInstList().erase(II); -} - -static bool MarkAliveBlocks(BasicBlock *BB, - SmallPtrSet &Reachable) { - - SmallVector Worklist; - Worklist.push_back(BB); - bool Changed = false; - do { - BB = Worklist.pop_back_val(); - - if (!Reachable.insert(BB)) - continue; - - // Do a quick scan of the basic block, turning any obviously unreachable - // instructions into LLVM unreachable insts. The instruction combining pass - // canonicalizes unreachable insts into stores to null or undef. - for (BasicBlock::iterator BBI = BB->begin(), E = BB->end(); BBI != E;++BBI){ - if (CallInst *CI = dyn_cast(BBI)) { - if (CI->doesNotReturn()) { - // If we found a call to a no-return function, insert an unreachable - // instruction after it. Make sure there isn't *already* one there - // though. - ++BBI; - if (!isa(BBI)) { - // Don't insert a call to llvm.trap right before the unreachable. - ChangeToUnreachable(BBI, false); - Changed = true; - } - break; - } - } - - // Store to undef and store to null are undefined and used to signal that - // they should be changed to unreachable by passes that can't modify the - // CFG. - if (StoreInst *SI = dyn_cast(BBI)) { - Value *Ptr = SI->getOperand(1); - - if (isa(Ptr) || - (isa(Ptr) && - SI->getPointerAddressSpace() == 0)) { - ChangeToUnreachable(SI, true); - Changed = true; - break; - } - } - } - - // Turn invokes that call 'nounwind' functions into ordinary calls. - if (InvokeInst *II = dyn_cast(BB->getTerminator())) - if (II->doesNotThrow()) { - ChangeToCall(II); - Changed = true; - } - - Changed |= ConstantFoldTerminator(BB); - for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); SI != SE; ++SI) - Worklist.push_back(*SI); - } while (!Worklist.empty()); - return Changed; -} - -/// RemoveUnreachableBlocksFromFn - 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 RemoveUnreachableBlocksFromFn(Function &F) { - SmallPtrSet Reachable; - bool Changed = MarkAliveBlocks(F.begin(), Reachable); - - // If there are unreachable blocks in the CFG... - 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)) - continue; - - 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; -} - -/// MergeEmptyReturnBlocks - If we have more than one empty (other than phi +/// mergeEmptyReturnBlocks - If we have more than one empty (other than phi /// node) return blocks, merge them together to promote recursive block merging. -static bool MergeEmptyReturnBlocks(Function &F) { +static bool mergeEmptyReturnBlocks(Function &F) { bool Changed = false; - + BasicBlock *RetBlock = 0; - + // Scan all the blocks in the function, looking for empty return blocks. for (Function::iterator BBI = F.begin(), E = F.end(); BBI != E; ) { BasicBlock &BB = *BBI++; - + // Only look at return blocks. ReturnInst *Ret = dyn_cast(BB.getTerminator()); if (Ret == 0) continue; - + // Only look at the block if it is empty or the only other thing in it is a // single PHI node that is the operand to the return. if (Ret != &BB.front()) { @@ -234,34 +102,35 @@ static bool MergeEmptyReturnBlocks(Function &F) { RetBlock = &BB; continue; } - + // Otherwise, we found a duplicate return block. Merge the two. Changed = true; - + // Case when there is no input to the return or when the returned values // agree is trivial. Note that they can't agree if there are phis in the // blocks. if (Ret->getNumOperands() == 0 || - Ret->getOperand(0) == + Ret->getOperand(0) == cast(RetBlock->getTerminator())->getOperand(0)) { BB.replaceAllUsesWith(RetBlock); BB.eraseFromParent(); continue; } - + // If the canonical return block has no PHI node, create one now. PHINode *RetBlockPHI = dyn_cast(RetBlock->begin()); if (RetBlockPHI == 0) { Value *InVal = cast(RetBlock->getTerminator())->getOperand(0); - RetBlockPHI = PHINode::Create(Ret->getOperand(0)->getType(), "merge", + pred_iterator PB = pred_begin(RetBlock), PE = pred_end(RetBlock); + RetBlockPHI = PHINode::Create(Ret->getOperand(0)->getType(), + std::distance(PB, PE), "merge", &RetBlock->front()); - - for (pred_iterator PI = pred_begin(RetBlock), E = pred_end(RetBlock); - PI != E; ++PI) + + for (pred_iterator PI = PB; PI != PE; ++PI) RetBlockPHI->addIncoming(InVal, *PI); RetBlock->getTerminator()->setOperand(0, RetBlockPHI); } - + // Turn BB into a block that just unconditionally branches to the return // block. This handles the case when the two return blocks have a common // predecessor but that return different things. @@ -269,23 +138,23 @@ static bool MergeEmptyReturnBlocks(Function &F) { BB.getTerminator()->eraseFromParent(); BranchInst::Create(RetBlock, &BB); } - + return Changed; } -/// IterativeSimplifyCFG - Call SimplifyCFG on all the blocks in the function, +/// iterativelySimplifyCFG - Call SimplifyCFG on all the blocks in the function, /// iterating until no more changes are made. -static bool IterativeSimplifyCFG(Function &F, const TargetData *TD) { +static bool iterativelySimplifyCFG(Function &F, const TargetTransformInfo &TTI, + const DataLayout *TD) { 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... + + // Loop over all of the basic blocks and remove them if they are unneeded... // - for (Function::iterator BBIt = ++F.begin(); BBIt != F.end(); ) { - if (SimplifyCFG(BBIt++, TD)) { + for (Function::iterator BBIt = F.begin(); BBIt != F.end(); ) { + if (SimplifyCFG(BBIt++, TTI, TD)) { LocalChange = true; ++NumSimpl; } @@ -299,25 +168,26 @@ static bool IterativeSimplifyCFG(Function &F, const TargetData *TD) { // simplify the CFG. // bool CFGSimplifyPass::runOnFunction(Function &F) { - const TargetData *TD = getAnalysisIfAvailable(); - bool EverChanged = RemoveUnreachableBlocksFromFn(F); - EverChanged |= MergeEmptyReturnBlocks(F); - EverChanged |= IterativeSimplifyCFG(F, TD); + const TargetTransformInfo &TTI = getAnalysis(); + const DataLayout *TD = getAnalysisIfAvailable(); + bool EverChanged = removeUnreachableBlocks(F); + EverChanged |= mergeEmptyReturnBlocks(F); + EverChanged |= iterativelySimplifyCFG(F, TTI, TD); // If neither pass changed anything, we're done. if (!EverChanged) return false; - // IterativeSimplifyCFG can (rarely) make some loops dead. If this happens, - // RemoveUnreachableBlocksFromFn is needed to nuke them, which means we should + // iterativelySimplifyCFG 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 - // RemoveUnreachableBlocksFromFn doesn't do anything. - if (!RemoveUnreachableBlocksFromFn(F)) + // avoid reruning iterativelySimplifyCFG if the second pass of + // removeUnreachableBlocks doesn't do anything. + if (!removeUnreachableBlocks(F)) return true; do { - EverChanged = IterativeSimplifyCFG(F, TD); - EverChanged |= RemoveUnreachableBlocksFromFn(F); + EverChanged = iterativelySimplifyCFG(F, TTI, TD); + EverChanged |= removeUnreachableBlocks(F); } while (EverChanged); return true;