X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FTransforms%2FScalar%2FSimplifyCFGPass.cpp;h=df6ef2ee75b61860bd7f45658883b9a64222cc16;hb=9ccaf53ada99c63737547c0235baeb8454b04e80;hp=cd063079f689993e4150789cce980e492232abf9;hpb=ae73dc1448d25b02cabc7c64c86c64371453dda8;p=oota-llvm.git diff --git a/lib/Transforms/Scalar/SimplifyCFGPass.cpp b/lib/Transforms/Scalar/SimplifyCFGPass.cpp index cd063079f68..df6ef2ee75b 100644 --- a/lib/Transforms/Scalar/SimplifyCFGPass.cpp +++ b/lib/Transforms/Scalar/SimplifyCFGPass.cpp @@ -26,11 +26,12 @@ #include "llvm/Transforms/Utils/Local.h" #include "llvm/Constants.h" #include "llvm/Instructions.h" +#include "llvm/IntrinsicInst.h" #include "llvm/Module.h" -#include "llvm/ParameterAttributes.h" +#include "llvm/Attributes.h" #include "llvm/Support/CFG.h" -#include "llvm/Support/Compiler.h" #include "llvm/Pass.h" +#include "llvm/Target/TargetData.h" #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/Statistic.h" @@ -39,16 +40,17 @@ using namespace llvm; STATISTIC(NumSimpl, "Number of blocks simplified"); namespace { - struct VISIBILITY_HIDDEN CFGSimplifyPass : public FunctionPass { + struct CFGSimplifyPass : public FunctionPass { static char ID; // Pass identification, replacement for typeid - CFGSimplifyPass() : FunctionPass(&ID) {} + CFGSimplifyPass() : FunctionPass(ID) {} virtual bool runOnFunction(Function &F); }; } char CFGSimplifyPass::ID = 0; -static RegisterPass X("simplifycfg", "Simplify the CFG"); +INITIALIZE_PASS(CFGSimplifyPass, "simplifycfg", + "Simplify the CFG", false, false); // Public interface to the CFGSimplification pass FunctionPass *llvm::createCFGSimplificationPass() { @@ -57,14 +59,21 @@ FunctionPass *llvm::createCFGSimplificationPass() { /// 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) { +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); - new UnreachableInst(I); + // 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(); @@ -78,12 +87,12 @@ static void ChangeToUnreachable(Instruction *I) { /// 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()); + 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->setParamAttrs(II->getParamAttrs()); + NewCall->setAttributes(II->getAttributes()); II->replaceAllUsesWith(NewCall); // Follow the call by a branch to the normal destination. @@ -100,9 +109,8 @@ static bool MarkAliveBlocks(BasicBlock *BB, SmallVector Worklist; Worklist.push_back(BB); bool Changed = false; - while (!Worklist.empty()) { - BB = Worklist.back(); - Worklist.pop_back(); + do { + BB = Worklist.pop_back_val(); if (!Reachable.insert(BB)) continue; @@ -118,20 +126,31 @@ static bool MarkAliveBlocks(BasicBlock *BB, // though. ++BBI; if (!isa(BBI)) { - ChangeToUnreachable(BBI); + // Don't insert a call to llvm.trap right before the unreachable. + ChangeToUnreachable(BBI, false); Changed = true; } break; } } - if (StoreInst *SI = dyn_cast(BBI)) - if (isa(SI->getOperand(1)) || - isa(SI->getOperand(1))) { - ChangeToUnreachable(SI); + // 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)) { + // Don't touch volatile stores. + if (SI->isVolatile()) continue; + + 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. @@ -144,13 +163,14 @@ static bool MarkAliveBlocks(BasicBlock *BB, 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; } -/// 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) { +/// 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); @@ -182,9 +202,84 @@ static bool RemoveUnreachableBlocks(Function &F) { return true; } +/// 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; + + 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; + } + + // If this is the first returning block, remember it and keep going. + if (RetBlock == 0) { + 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) == + 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", + &RetBlock->front()); + + for (pred_iterator PI = pred_begin(RetBlock), E = pred_end(RetBlock); + PI != E; ++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. + RetBlockPHI->addIncoming(Ret->getOperand(0), &BB); + BB.getTerminator()->eraseFromParent(); + BranchInst::Create(RetBlock, &BB); + } + + return Changed; +} + /// IterativeSimplifyCFG - Call SimplifyCFG on all the blocks in the function, /// iterating until no more changes are made. -static bool IterativeSimplifyCFG(Function &F) { +static bool IterativeSimplifyCFG(Function &F, const TargetData *TD) { bool Changed = false; bool LocalChange = true; while (LocalChange) { @@ -194,7 +289,7 @@ static bool IterativeSimplifyCFG(Function &F) { // if they are unneeded... // for (Function::iterator BBIt = ++F.begin(); BBIt != F.end(); ) { - if (SimplifyCFG(BBIt++)) { + if (SimplifyCFG(BBIt++, TD)) { LocalChange = true; ++NumSimpl; } @@ -208,24 +303,26 @@ static bool IterativeSimplifyCFG(Function &F) { // simplify the CFG. // bool CFGSimplifyPass::runOnFunction(Function &F) { - bool EverChanged = RemoveUnreachableBlocks(F); - EverChanged |= IterativeSimplifyCFG(F); - + const TargetData *TD = getAnalysisIfAvailable(); + bool EverChanged = RemoveUnreachableBlocksFromFn(F); + EverChanged |= MergeEmptyReturnBlocks(F); + EverChanged |= IterativeSimplifyCFG(F, TD); + // 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 + // RemoveUnreachableBlocksFromFn 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)) + // RemoveUnreachableBlocksFromFn doesn't do anything. + if (!RemoveUnreachableBlocksFromFn(F)) return true; - + do { - EverChanged = IterativeSimplifyCFG(F); - EverChanged |= RemoveUnreachableBlocks(F); + EverChanged = IterativeSimplifyCFG(F, TD); + EverChanged |= RemoveUnreachableBlocksFromFn(F); } while (EverChanged); - + return true; }