From d651f441ae4c5a9e2c77a9a38604f83d0d4261ea Mon Sep 17 00:00:00 2001 From: Chris Lattner Date: Wed, 27 Apr 2005 04:52:23 +0000 Subject: detect functions that never return, and turn the instruction following a call to them into an 'unreachable' instruction. This triggers a bunch of times, particularly on gcc: gzip: 36 gcc: 601 eon: 12 bzip: 38 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@21587 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Transforms/IPO/PruneEH.cpp | 193 ++++++++++++++++++++++++++++++----------- 1 file changed, 143 insertions(+), 50 deletions(-) (limited to 'lib') diff --git a/lib/Transforms/IPO/PruneEH.cpp b/lib/Transforms/IPO/PruneEH.cpp index a31a3343e3..10242c7d91 100644 --- a/lib/Transforms/IPO/PruneEH.cpp +++ b/lib/Transforms/IPO/PruneEH.cpp @@ -16,25 +16,35 @@ #include "llvm/Transforms/IPO.h" #include "llvm/CallGraphSCCPass.h" +#include "llvm/Constants.h" #include "llvm/Function.h" #include "llvm/Intrinsics.h" #include "llvm/Instructions.h" #include "llvm/Analysis/CallGraph.h" #include "llvm/ADT/Statistic.h" +#include "llvm/Support/CFG.h" #include #include using namespace llvm; namespace { Statistic<> NumRemoved("prune-eh", "Number of invokes removed"); + Statistic<> NumUnreach("prune-eh", "Number of noreturn calls optimized"); struct PruneEH : public CallGraphSCCPass { /// DoesNotUnwind - This set contains all of the functions which we have - /// determined cannot throw exceptions. + /// determined cannot unwind. std::set DoesNotUnwind; + /// DoesNotReturn - This set contains all of the functions which we have + /// determined cannot return normally (but might unwind). + std::set DoesNotReturn; + // runOnSCC - Analyze the SCC, performing the transformation if possible. bool runOnSCC(const std::vector &SCC); + + bool SimplifyFunction(Function *F); + void DeleteBasicBlock(BasicBlock *BB); }; RegisterOpt X("prune-eh", "Remove unused exception handling info"); } @@ -44,89 +54,172 @@ ModulePass *llvm::createPruneEHPass() { return new PruneEH(); } bool PruneEH::runOnSCC(const std::vector &SCC) { CallGraph &CG = getAnalysis(); + bool MadeChange = false; + + // First pass, scan all of the functions in the SCC, simplifying them + // according to what we know. + for (unsigned i = 0, e = SCC.size(); i != e; ++i) + if (Function *F = SCC[i]->getFunction()) + MadeChange |= SimplifyFunction(F); - // First, check to see if any callees might throw or if there are any external + // Next, check to see if any callees might throw or if there are any external // functions in this SCC: if so, we cannot prune any functions in this SCC. // If this SCC includes the unwind instruction, we KNOW it throws, so // obviously the SCC might throw. // - bool SCCMightUnwind = false; - for (unsigned i = 0, e = SCC.size(); !SCCMightUnwind && i != e; ++i) { + bool SCCMightUnwind = false, SCCMightReturn = false; + for (unsigned i = 0, e = SCC.size(); + (!SCCMightUnwind || !SCCMightReturn) && i != e; ++i) { Function *F = SCC[i]->getFunction(); if (F == 0 || (F->isExternal() && !F->getIntrinsicID())) { SCCMightUnwind = true; + SCCMightReturn = true; } else { + if (F->isExternal()) + SCCMightReturn = true; + // Check to see if this function performs an unwind or calls an // unwinding function. for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) { if (isa(BB->getTerminator())) { // Uses unwind! SCCMightUnwind = true; - break; + } else if (isa(BB->getTerminator())) { + SCCMightReturn = true; } // Invoke instructions don't allow unwinding to continue, so we are // only interested in call instructions. - for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) - if (CallInst *CI = dyn_cast(I)) { - if (Function *Callee = CI->getCalledFunction()) { - CallGraphNode *CalleeNode = CG[Callee]; - // If the callee is outside our current SCC, or if it is not - // known to throw, then we might throw also. - if (std::find(SCC.begin(), SCC.end(), CalleeNode) == SCC.end()&& - !DoesNotUnwind.count(CalleeNode)) { + if (!SCCMightUnwind) + for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) + if (CallInst *CI = dyn_cast(I)) { + if (Function *Callee = CI->getCalledFunction()) { + CallGraphNode *CalleeNode = CG[Callee]; + // If the callee is outside our current SCC, or if it is not + // known to throw, then we might throw also. + if (std::find(SCC.begin(), SCC.end(), CalleeNode) == SCC.end()&& + !DoesNotUnwind.count(CalleeNode)) { + SCCMightUnwind = true; + break; + } + } else { + // Indirect call, it might throw. SCCMightUnwind = true; break; } - - } else { - // Indirect call, it might throw. - SCCMightUnwind = true; - break; } - } - if (SCCMightUnwind) break; + if (SCCMightUnwind && SCCMightReturn) break; } } } - bool MadeChange = false; - for (unsigned i = 0, e = SCC.size(); i != e; ++i) { - // If the SCC can't throw, remember this for callers... - if (!SCCMightUnwind) + // If the SCC doesn't unwind or doesn't throw, note this fact. + if (!SCCMightUnwind) + for (unsigned i = 0, e = SCC.size(); i != e; ++i) DoesNotUnwind.insert(SCC[i]); + if (!SCCMightReturn) + for (unsigned i = 0, e = SCC.size(); i != e; ++i) + DoesNotReturn.insert(SCC[i]); + for (unsigned i = 0, e = SCC.size(); i != e; ++i) { // Convert any invoke instructions to non-throwing functions in this node // into call instructions with a branch. This makes the exception blocks // dead. if (Function *F = SCC[i]->getFunction()) - for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I) - if (InvokeInst *II = dyn_cast(I->getTerminator())) - if (Function *F = II->getCalledFunction()) - if (DoesNotUnwind.count(CG[F])) { - // Insert a call instruction before the invoke... - std::string Name = II->getName(); II->setName(""); - Value *Call = new CallInst(II->getCalledValue(), - std::vector(II->op_begin()+3, - II->op_end()), - Name, II); - - // Anything that used the value produced by the invoke instruction - // now uses the value produced by the call instruction. - II->replaceAllUsesWith(Call); - II->getUnwindDest()->removePredecessor(II->getParent()); - - // Insert a branch to the normal destination right before the - // invoke. - new BranchInst(II->getNormalDest(), II); - - // Finally, delete the invoke instruction! - I->getInstList().pop_back(); - - ++NumRemoved; - MadeChange = true; - } + MadeChange |= SimplifyFunction(F); } return MadeChange; } + +// SimplifyFunction - Given information about callees, simplify the specified +// function if we have invokes to non-unwinding functions or code after calls to +// no-return functions. +bool PruneEH::SimplifyFunction(Function *F) { + CallGraph &CG = getAnalysis(); + bool MadeChange = false; + for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) { + if (InvokeInst *II = dyn_cast(BB->getTerminator())) + if (Function *F = II->getCalledFunction()) + if (DoesNotUnwind.count(CG[F])) { + // Insert a call instruction before the invoke... + std::string Name = II->getName(); II->setName(""); + Value *Call = new CallInst(II->getCalledValue(), + std::vector(II->op_begin()+3, + II->op_end()), + Name, II); + + // Anything that used the value produced by the invoke instruction + // now uses the value produced by the call instruction. + II->replaceAllUsesWith(Call); + BasicBlock *UnwindBlock = II->getUnwindDest(); + UnwindBlock->removePredecessor(II->getParent()); + + // Insert a branch to the normal destination right before the + // invoke. + new BranchInst(II->getNormalDest(), II); + + // Finally, delete the invoke instruction! + BB->getInstList().pop_back(); + + // If the unwind block is now dead, nuke it. + if (pred_begin(UnwindBlock) == pred_end(UnwindBlock)) + DeleteBasicBlock(UnwindBlock); // Delete the new BB. + + ++NumRemoved; + MadeChange = true; + } + + for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; I) + if (CallInst *CI = dyn_cast(I++)) + if (Function *Callee = CI->getCalledFunction()) + if (DoesNotReturn.count(CG[Callee]) && !isa(I)) { + // This call calls a function that cannot return. Insert an + // unreachable instruction after it and simplify the code. Do this + // by splitting the BB, adding the unreachable, then deleting the + // new BB. + BasicBlock *New = BB->splitBasicBlock(I); + + // Remove the uncond branch and add an unreachable. + BB->getInstList().pop_back(); + new UnreachableInst(BB); + + DeleteBasicBlock(New); // Delete the new BB. + MadeChange = true; + ++NumUnreach; + break; + } + + } + return MadeChange; +} + +/// DeleteBasicBlock - remove the specified basic block from the program, +/// updating the callgraph to reflect any now-obsolete edges due to calls that +/// exist in the BB. +void PruneEH::DeleteBasicBlock(BasicBlock *BB) { + assert(pred_begin(BB) == pred_end(BB) && "BB is not dead!"); + CallGraph &CG = getAnalysis(); + + CallGraphNode *CGN = CG[BB->getParent()]; + for (BasicBlock::iterator I = BB->end(), E = BB->begin(); I != E; ) { + --I; + if (CallInst *CI = dyn_cast(I)) { + if (Function *Callee = CI->getCalledFunction()) + CGN->removeCallEdgeTo(CG[Callee]); + } else if (InvokeInst *II = dyn_cast(I)) { + if (Function *Callee = II->getCalledFunction()) + CGN->removeCallEdgeTo(CG[Callee]); + } + if (!I->use_empty()) + I->replaceAllUsesWith(UndefValue::get(I->getType())); + } + + // Get the list of successors of this block. + std::vector Succs(succ_begin(BB), succ_end(BB)); + + for (unsigned i = 0, e = Succs.size(); i != e; ++i) + Succs[i]->removePredecessor(BB); + + BB->eraseFromParent(); +} -- cgit v1.2.3