PruneEH.cpp revision 355940
1//===- PruneEH.cpp - Pass which deletes unused exception handlers ---------===// 2// 3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4// See https://llvm.org/LICENSE.txt for license information. 5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6// 7//===----------------------------------------------------------------------===// 8// 9// This file implements a simple interprocedural pass which walks the 10// call-graph, turning invoke instructions into calls, iff the callee cannot 11// throw an exception, and marking functions 'nounwind' if they cannot throw. 12// It implements this as a bottom-up traversal of the call-graph. 13// 14//===----------------------------------------------------------------------===// 15 16#include "llvm/ADT/SmallPtrSet.h" 17#include "llvm/ADT/Statistic.h" 18#include "llvm/Analysis/CallGraph.h" 19#include "llvm/Analysis/CallGraphSCCPass.h" 20#include "llvm/Analysis/EHPersonalities.h" 21#include "llvm/Transforms/Utils/Local.h" 22#include "llvm/IR/CFG.h" 23#include "llvm/IR/Constants.h" 24#include "llvm/IR/Function.h" 25#include "llvm/IR/InlineAsm.h" 26#include "llvm/IR/Instructions.h" 27#include "llvm/IR/LLVMContext.h" 28#include "llvm/Support/raw_ostream.h" 29#include "llvm/Transforms/IPO.h" 30#include <algorithm> 31using namespace llvm; 32 33#define DEBUG_TYPE "prune-eh" 34 35STATISTIC(NumRemoved, "Number of invokes removed"); 36STATISTIC(NumUnreach, "Number of noreturn calls optimized"); 37 38namespace { 39 struct PruneEH : public CallGraphSCCPass { 40 static char ID; // Pass identification, replacement for typeid 41 PruneEH() : CallGraphSCCPass(ID) { 42 initializePruneEHPass(*PassRegistry::getPassRegistry()); 43 } 44 45 // runOnSCC - Analyze the SCC, performing the transformation if possible. 46 bool runOnSCC(CallGraphSCC &SCC) override; 47 48 }; 49} 50static bool SimplifyFunction(Function *F, CallGraph &CG); 51static void DeleteBasicBlock(BasicBlock *BB, CallGraph &CG); 52 53char PruneEH::ID = 0; 54INITIALIZE_PASS_BEGIN(PruneEH, "prune-eh", 55 "Remove unused exception handling info", false, false) 56INITIALIZE_PASS_DEPENDENCY(CallGraphWrapperPass) 57INITIALIZE_PASS_END(PruneEH, "prune-eh", 58 "Remove unused exception handling info", false, false) 59 60Pass *llvm::createPruneEHPass() { return new PruneEH(); } 61 62static bool runImpl(CallGraphSCC &SCC, CallGraph &CG) { 63 SmallPtrSet<CallGraphNode *, 8> SCCNodes; 64 bool MadeChange = false; 65 66 // Fill SCCNodes with the elements of the SCC. Used for quickly 67 // looking up whether a given CallGraphNode is in this SCC. 68 for (CallGraphNode *I : SCC) 69 SCCNodes.insert(I); 70 71 // First pass, scan all of the functions in the SCC, simplifying them 72 // according to what we know. 73 for (CallGraphNode *I : SCC) 74 if (Function *F = I->getFunction()) 75 MadeChange |= SimplifyFunction(F, CG); 76 77 // Next, check to see if any callees might throw or if there are any external 78 // functions in this SCC: if so, we cannot prune any functions in this SCC. 79 // Definitions that are weak and not declared non-throwing might be 80 // overridden at linktime with something that throws, so assume that. 81 // If this SCC includes the unwind instruction, we KNOW it throws, so 82 // obviously the SCC might throw. 83 // 84 bool SCCMightUnwind = false, SCCMightReturn = false; 85 for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); 86 (!SCCMightUnwind || !SCCMightReturn) && I != E; ++I) { 87 Function *F = (*I)->getFunction(); 88 if (!F) { 89 SCCMightUnwind = true; 90 SCCMightReturn = true; 91 } else if (!F->hasExactDefinition()) { 92 SCCMightUnwind |= !F->doesNotThrow(); 93 SCCMightReturn |= !F->doesNotReturn(); 94 } else { 95 bool CheckUnwind = !SCCMightUnwind && !F->doesNotThrow(); 96 bool CheckReturn = !SCCMightReturn && !F->doesNotReturn(); 97 // Determine if we should scan for InlineAsm in a naked function as it 98 // is the only way to return without a ReturnInst. Only do this for 99 // no-inline functions as functions which may be inlined cannot 100 // meaningfully return via assembly. 101 bool CheckReturnViaAsm = CheckReturn && 102 F->hasFnAttribute(Attribute::Naked) && 103 F->hasFnAttribute(Attribute::NoInline); 104 105 if (!CheckUnwind && !CheckReturn) 106 continue; 107 108 for (const BasicBlock &BB : *F) { 109 const Instruction *TI = BB.getTerminator(); 110 if (CheckUnwind && TI->mayThrow()) { 111 SCCMightUnwind = true; 112 } else if (CheckReturn && isa<ReturnInst>(TI)) { 113 SCCMightReturn = true; 114 } 115 116 for (const Instruction &I : BB) { 117 if ((!CheckUnwind || SCCMightUnwind) && 118 (!CheckReturnViaAsm || SCCMightReturn)) 119 break; 120 121 // Check to see if this function performs an unwind or calls an 122 // unwinding function. 123 if (CheckUnwind && !SCCMightUnwind && I.mayThrow()) { 124 bool InstMightUnwind = true; 125 if (const auto *CI = dyn_cast<CallInst>(&I)) { 126 if (Function *Callee = CI->getCalledFunction()) { 127 CallGraphNode *CalleeNode = CG[Callee]; 128 // If the callee is outside our current SCC then we may throw 129 // because it might. If it is inside, do nothing. 130 if (SCCNodes.count(CalleeNode) > 0) 131 InstMightUnwind = false; 132 } 133 } 134 SCCMightUnwind |= InstMightUnwind; 135 } 136 if (CheckReturnViaAsm && !SCCMightReturn) 137 if (auto ICS = ImmutableCallSite(&I)) 138 if (const auto *IA = dyn_cast<InlineAsm>(ICS.getCalledValue())) 139 if (IA->hasSideEffects()) 140 SCCMightReturn = true; 141 } 142 143 if (SCCMightUnwind && SCCMightReturn) 144 break; 145 } 146 } 147 } 148 149 // If the SCC doesn't unwind or doesn't throw, note this fact. 150 if (!SCCMightUnwind || !SCCMightReturn) 151 for (CallGraphNode *I : SCC) { 152 Function *F = I->getFunction(); 153 154 if (!SCCMightUnwind && !F->hasFnAttribute(Attribute::NoUnwind)) { 155 F->addFnAttr(Attribute::NoUnwind); 156 MadeChange = true; 157 } 158 159 if (!SCCMightReturn && !F->hasFnAttribute(Attribute::NoReturn)) { 160 F->addFnAttr(Attribute::NoReturn); 161 MadeChange = true; 162 } 163 } 164 165 for (CallGraphNode *I : SCC) { 166 // Convert any invoke instructions to non-throwing functions in this node 167 // into call instructions with a branch. This makes the exception blocks 168 // dead. 169 if (Function *F = I->getFunction()) 170 MadeChange |= SimplifyFunction(F, CG); 171 } 172 173 return MadeChange; 174} 175 176 177bool PruneEH::runOnSCC(CallGraphSCC &SCC) { 178 if (skipSCC(SCC)) 179 return false; 180 CallGraph &CG = getAnalysis<CallGraphWrapperPass>().getCallGraph(); 181 return runImpl(SCC, CG); 182} 183 184 185// SimplifyFunction - Given information about callees, simplify the specified 186// function if we have invokes to non-unwinding functions or code after calls to 187// no-return functions. 188static bool SimplifyFunction(Function *F, CallGraph &CG) { 189 bool MadeChange = false; 190 for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) { 191 if (InvokeInst *II = dyn_cast<InvokeInst>(BB->getTerminator())) 192 if (II->doesNotThrow() && canSimplifyInvokeNoUnwind(F)) { 193 BasicBlock *UnwindBlock = II->getUnwindDest(); 194 removeUnwindEdge(&*BB); 195 196 // If the unwind block is now dead, nuke it. 197 if (pred_empty(UnwindBlock)) 198 DeleteBasicBlock(UnwindBlock, CG); // Delete the new BB. 199 200 ++NumRemoved; 201 MadeChange = true; 202 } 203 204 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ) 205 if (CallInst *CI = dyn_cast<CallInst>(I++)) 206 if (CI->doesNotReturn() && !CI->isMustTailCall() && 207 !isa<UnreachableInst>(I)) { 208 // This call calls a function that cannot return. Insert an 209 // unreachable instruction after it and simplify the code. Do this 210 // by splitting the BB, adding the unreachable, then deleting the 211 // new BB. 212 BasicBlock *New = BB->splitBasicBlock(I); 213 214 // Remove the uncond branch and add an unreachable. 215 BB->getInstList().pop_back(); 216 new UnreachableInst(BB->getContext(), &*BB); 217 218 DeleteBasicBlock(New, CG); // Delete the new BB. 219 MadeChange = true; 220 ++NumUnreach; 221 break; 222 } 223 } 224 225 return MadeChange; 226} 227 228/// DeleteBasicBlock - remove the specified basic block from the program, 229/// updating the callgraph to reflect any now-obsolete edges due to calls that 230/// exist in the BB. 231static void DeleteBasicBlock(BasicBlock *BB, CallGraph &CG) { 232 assert(pred_empty(BB) && "BB is not dead!"); 233 234 Instruction *TokenInst = nullptr; 235 236 CallGraphNode *CGN = CG[BB->getParent()]; 237 for (BasicBlock::iterator I = BB->end(), E = BB->begin(); I != E; ) { 238 --I; 239 240 if (I->getType()->isTokenTy()) { 241 TokenInst = &*I; 242 break; 243 } 244 245 if (auto *Call = dyn_cast<CallBase>(&*I)) { 246 const Function *Callee = Call->getCalledFunction(); 247 if (!Callee || !Intrinsic::isLeaf(Callee->getIntrinsicID())) 248 CGN->removeCallEdgeFor(*Call); 249 else if (!Callee->isIntrinsic()) 250 CGN->removeCallEdgeFor(*Call); 251 } 252 253 if (!I->use_empty()) 254 I->replaceAllUsesWith(UndefValue::get(I->getType())); 255 } 256 257 if (TokenInst) { 258 if (!TokenInst->isTerminator()) 259 changeToUnreachable(TokenInst->getNextNode(), /*UseLLVMTrap=*/false); 260 } else { 261 // Get the list of successors of this block. 262 std::vector<BasicBlock *> Succs(succ_begin(BB), succ_end(BB)); 263 264 for (unsigned i = 0, e = Succs.size(); i != e; ++i) 265 Succs[i]->removePredecessor(BB); 266 267 BB->eraseFromParent(); 268 } 269} 270