X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FTransforms%2FScalar%2FSimplifyCFGPass.cpp;h=8371f6d35279ebd05879b4b0f2688266090e311d;hb=3e033f29239e48c190f29cdf3a02cdfbaf2fe72b;hp=f6cffdd0ef49fb838b82dd1a4e6d012685adacfa;hpb=fa196e34b0676a48d824c8feb29c6ca016667025;p=oota-llvm.git diff --git a/lib/Transforms/Scalar/SimplifyCFGPass.cpp b/lib/Transforms/Scalar/SimplifyCFGPass.cpp index f6cffdd0ef4..8371f6d3527 100644 --- a/lib/Transforms/Scalar/SimplifyCFGPass.cpp +++ b/lib/Transforms/Scalar/SimplifyCFGPass.cpp @@ -23,185 +23,138 @@ #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/LLVMContext.h" -#include "llvm/Module.h" -#include "llvm/Attributes.h" -#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/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 VISIBILITY_HIDDEN 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, LLVMContext *Context) { - 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); - - new UnreachableInst(I); - - // All instructions after this are dead. - BasicBlock::iterator BBI = I, BBE = BB->end(); - while (BBI != BBE) { - if (!BBI->use_empty()) - BBI->replaceAllUsesWith(Context->getUndef(BBI->getType())); - BB->getInstList().erase(BBI++); - } -} +/// 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) { + bool Changed = false; -/// ChangeToCall - Convert the specified invoke into a normal call. -static void ChangeToCall(InvokeInst *II) { - BasicBlock *BB = II->getParent(); - SmallVector Args(II->op_begin()+3, II->op_end()); - 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); -} + 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()) { + // Check for something else in the block. + BasicBlock::iterator I = Ret; + --I; + // Skip over debug info. + while (isa(I) && I != BB.begin()) + --I; + if (!isa(I) && + (!isa(I) || I != BB.begin() || + Ret->getNumOperands() == 0 || + Ret->getOperand(0) != I)) + continue; + } -static bool MarkAliveBlocks(BasicBlock *BB, - SmallPtrSet &Reachable, - LLVMContext *Context) { - - SmallVector Worklist; - Worklist.push_back(BB); - bool Changed = false; - while (!Worklist.empty()) { - BB = Worklist.back(); - Worklist.pop_back(); - - if (!Reachable.insert(BB)) + // If this is the first returning block, remember it and keep going. + if (RetBlock == 0) { + RetBlock = &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)) { - ChangeToUnreachable(BBI, Context); - Changed = true; - } - break; - } - } - - if (StoreInst *SI = dyn_cast(BBI)) { - Value *Ptr = SI->getOperand(1); - - if (isa(Ptr) || - (isa(Ptr) && - cast(Ptr->getType())->getAddressSpace() == 0)) { - ChangeToUnreachable(SI, Context); - Changed = true; - break; - } - } + // 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) == + cast(RetBlock->getTerminator())->getOperand(0)) { + BB.replaceAllUsesWith(RetBlock); + BB.eraseFromParent(); + continue; } - // Turn invokes that call 'nounwind' functions into ordinary calls. - if (InvokeInst *II = dyn_cast(BB->getTerminator())) - if (II->doesNotThrow()) { - ChangeToCall(II); - Changed = true; - } + // 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); + 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 = PB; PI != PE; ++PI) + RetBlockPHI->addIncoming(InVal, *PI); + RetBlock->getTerminator()->setOperand(0, RetBlockPHI); + } - Changed |= ConstantFoldTerminator(BB); - for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); SI != SE; ++SI) - Worklist.push_back(*SI); + // 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. + RetBlockPHI->addIncoming(Ret->getOperand(0), &BB); + BB.getTerminator()->eraseFromParent(); + BranchInst::Create(RetBlock, &BB); } - 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, F.getContext()); - - // 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; + 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) { +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++)) { + for (Function::iterator BBIt = F.begin(); BBIt != F.end(); ) { + if (SimplifyCFG(BBIt++, TTI, TD)) { LocalChange = true; ++NumSimpl; } @@ -215,24 +168,27 @@ static bool IterativeSimplifyCFG(Function &F) { // simplify the CFG. // bool CFGSimplifyPass::runOnFunction(Function &F) { - bool EverChanged = RemoveUnreachableBlocksFromFn(F); - EverChanged |= IterativeSimplifyCFG(F); - + 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); - EverChanged |= RemoveUnreachableBlocksFromFn(F); + EverChanged = iterativelySimplifyCFG(F, TTI, TD); + EverChanged |= removeUnreachableBlocks(F); } while (EverChanged); - + return true; }