LLVM  12.0.0git
PruneEH.cpp
Go to the documentation of this file.
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"
21 #include "llvm/IR/CFG.h"
22 #include "llvm/IR/Constants.h"
23 #include "llvm/IR/Function.h"
24 #include "llvm/IR/InlineAsm.h"
25 #include "llvm/IR/Instructions.h"
26 #include "llvm/IR/LLVMContext.h"
27 #include "llvm/InitializePasses.h"
29 #include "llvm/Transforms/IPO.h"
31 #include <algorithm>
32 using namespace llvm;
33 
34 #define DEBUG_TYPE "prune-eh"
35 
36 STATISTIC(NumRemoved, "Number of invokes removed");
37 STATISTIC(NumUnreach, "Number of noreturn calls optimized");
38 
39 namespace {
40  struct PruneEH : public CallGraphSCCPass {
41  static char ID; // Pass identification, replacement for typeid
42  PruneEH() : CallGraphSCCPass(ID) {
44  }
45 
46  // runOnSCC - Analyze the SCC, performing the transformation if possible.
47  bool runOnSCC(CallGraphSCC &SCC) override;
48 
49  };
50 }
51 static bool SimplifyFunction(Function *F, CallGraph &CG);
52 static void DeleteBasicBlock(BasicBlock *BB, CallGraph &CG);
53 
54 char PruneEH::ID = 0;
55 INITIALIZE_PASS_BEGIN(PruneEH, "prune-eh",
56  "Remove unused exception handling info", false, false)
59  "Remove unused exception handling info", false, false)
60 
61 Pass *llvm::createPruneEHPass() { return new PruneEH(); }
62 
63 static bool runImpl(CallGraphSCC &SCC, CallGraph &CG) {
65  bool MadeChange = false;
66 
67  // Fill SCCNodes with the elements of the SCC. Used for quickly
68  // looking up whether a given CallGraphNode is in this SCC.
69  for (CallGraphNode *I : SCC)
70  SCCNodes.insert(I);
71 
72  // First pass, scan all of the functions in the SCC, simplifying them
73  // according to what we know.
74  for (CallGraphNode *I : SCC)
75  if (Function *F = I->getFunction())
76  MadeChange |= SimplifyFunction(F, CG);
77 
78  // Next, check to see if any callees might throw or if there are any external
79  // functions in this SCC: if so, we cannot prune any functions in this SCC.
80  // Definitions that are weak and not declared non-throwing might be
81  // overridden at linktime with something that throws, so assume that.
82  // If this SCC includes the unwind instruction, we KNOW it throws, so
83  // obviously the SCC might throw.
84  //
85  bool SCCMightUnwind = false, SCCMightReturn = false;
86  for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end();
87  (!SCCMightUnwind || !SCCMightReturn) && I != E; ++I) {
88  Function *F = (*I)->getFunction();
89  if (!F) {
90  SCCMightUnwind = true;
91  SCCMightReturn = true;
92  } else if (!F->hasExactDefinition()) {
93  SCCMightUnwind |= !F->doesNotThrow();
94  SCCMightReturn |= !F->doesNotReturn();
95  } else {
96  bool CheckUnwind = !SCCMightUnwind && !F->doesNotThrow();
97  bool CheckReturn = !SCCMightReturn && !F->doesNotReturn();
98  // Determine if we should scan for InlineAsm in a naked function as it
99  // is the only way to return without a ReturnInst. Only do this for
100  // no-inline functions as functions which may be inlined cannot
101  // meaningfully return via assembly.
102  bool CheckReturnViaAsm = CheckReturn &&
103  F->hasFnAttribute(Attribute::Naked) &&
104  F->hasFnAttribute(Attribute::NoInline);
105 
106  if (!CheckUnwind && !CheckReturn)
107  continue;
108 
109  for (const BasicBlock &BB : *F) {
110  const Instruction *TI = BB.getTerminator();
111  if (CheckUnwind && TI->mayThrow()) {
112  SCCMightUnwind = true;
113  } else if (CheckReturn && isa<ReturnInst>(TI)) {
114  SCCMightReturn = true;
115  }
116 
117  for (const Instruction &I : BB) {
118  if ((!CheckUnwind || SCCMightUnwind) &&
119  (!CheckReturnViaAsm || SCCMightReturn))
120  break;
121 
122  // Check to see if this function performs an unwind or calls an
123  // unwinding function.
124  if (CheckUnwind && !SCCMightUnwind && I.mayThrow()) {
125  bool InstMightUnwind = true;
126  if (const auto *CI = dyn_cast<CallInst>(&I)) {
127  if (Function *Callee = CI->getCalledFunction()) {
128  CallGraphNode *CalleeNode = CG[Callee];
129  // If the callee is outside our current SCC then we may throw
130  // because it might. If it is inside, do nothing.
131  if (SCCNodes.count(CalleeNode) > 0)
132  InstMightUnwind = false;
133  }
134  }
135  SCCMightUnwind |= InstMightUnwind;
136  }
137  if (CheckReturnViaAsm && !SCCMightReturn)
138  if (const auto *CB = dyn_cast<CallBase>(&I))
139  if (const auto *IA = dyn_cast<InlineAsm>(CB->getCalledOperand()))
140  if (IA->hasSideEffects())
141  SCCMightReturn = true;
142  }
143 
144  if (SCCMightUnwind && SCCMightReturn)
145  break;
146  }
147  }
148  }
149 
150  // If the SCC doesn't unwind or doesn't throw, note this fact.
151  if (!SCCMightUnwind || !SCCMightReturn)
152  for (CallGraphNode *I : SCC) {
153  Function *F = I->getFunction();
154 
155  if (!SCCMightUnwind && !F->hasFnAttribute(Attribute::NoUnwind)) {
156  F->addFnAttr(Attribute::NoUnwind);
157  MadeChange = true;
158  }
159 
160  if (!SCCMightReturn && !F->hasFnAttribute(Attribute::NoReturn)) {
161  F->addFnAttr(Attribute::NoReturn);
162  MadeChange = true;
163  }
164  }
165 
166  for (CallGraphNode *I : SCC) {
167  // Convert any invoke instructions to non-throwing functions in this node
168  // into call instructions with a branch. This makes the exception blocks
169  // dead.
170  if (Function *F = I->getFunction())
171  MadeChange |= SimplifyFunction(F, CG);
172  }
173 
174  return MadeChange;
175 }
176 
177 
178 bool PruneEH::runOnSCC(CallGraphSCC &SCC) {
179  if (skipSCC(SCC))
180  return false;
181  CallGraph &CG = getAnalysis<CallGraphWrapperPass>().getCallGraph();
182  return runImpl(SCC, CG);
183 }
184 
185 
186 // SimplifyFunction - Given information about callees, simplify the specified
187 // function if we have invokes to non-unwinding functions or code after calls to
188 // no-return functions.
189 static bool SimplifyFunction(Function *F, CallGraph &CG) {
190  bool MadeChange = false;
191  for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) {
192  if (InvokeInst *II = dyn_cast<InvokeInst>(BB->getTerminator()))
193  if (II->doesNotThrow() && canSimplifyInvokeNoUnwind(F)) {
194  BasicBlock *UnwindBlock = II->getUnwindDest();
195  removeUnwindEdge(&*BB);
196 
197  // If the unwind block is now dead, nuke it.
198  if (pred_empty(UnwindBlock))
199  DeleteBasicBlock(UnwindBlock, CG); // Delete the new BB.
200 
201  ++NumRemoved;
202  MadeChange = true;
203  }
204 
205  for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; )
206  if (CallInst *CI = dyn_cast<CallInst>(I++))
207  if (CI->doesNotReturn() && !CI->isMustTailCall() &&
208  !isa<UnreachableInst>(I)) {
209  // This call calls a function that cannot return. Insert an
210  // unreachable instruction after it and simplify the code. Do this
211  // by splitting the BB, adding the unreachable, then deleting the
212  // new BB.
213  BasicBlock *New = BB->splitBasicBlock(I);
214 
215  // Remove the uncond branch and add an unreachable.
216  BB->getInstList().pop_back();
217  new UnreachableInst(BB->getContext(), &*BB);
218 
219  DeleteBasicBlock(New, CG); // Delete the new BB.
220  MadeChange = true;
221  ++NumUnreach;
222  break;
223  }
224  }
225 
226  return MadeChange;
227 }
228 
229 /// DeleteBasicBlock - remove the specified basic block from the program,
230 /// updating the callgraph to reflect any now-obsolete edges due to calls that
231 /// exist in the BB.
232 static void DeleteBasicBlock(BasicBlock *BB, CallGraph &CG) {
233  assert(pred_empty(BB) && "BB is not dead!");
234 
235  Instruction *TokenInst = nullptr;
236 
237  CallGraphNode *CGN = CG[BB->getParent()];
238  for (BasicBlock::iterator I = BB->end(), E = BB->begin(); I != E; ) {
239  --I;
240 
241  if (I->getType()->isTokenTy()) {
242  TokenInst = &*I;
243  break;
244  }
245 
246  if (auto *Call = dyn_cast<CallBase>(&*I)) {
247  const Function *Callee = Call->getCalledFunction();
248  if (!Callee || !Intrinsic::isLeaf(Callee->getIntrinsicID()))
249  CGN->removeCallEdgeFor(*Call);
250  else if (!Callee->isIntrinsic())
251  CGN->removeCallEdgeFor(*Call);
252  }
253 
254  if (!I->use_empty())
255  I->replaceAllUsesWith(UndefValue::get(I->getType()));
256  }
257 
258  if (TokenInst) {
259  if (!TokenInst->isTerminator())
260  changeToUnreachable(TokenInst->getNextNode(), /*UseLLVMTrap=*/false);
261  } else {
262  // Get the list of successors of this block.
263  std::vector<BasicBlock *> Succs(succ_begin(BB), succ_end(BB));
264 
265  for (unsigned i = 0, e = Succs.size(); i != e; ++i)
266  Succs[i]->removePredecessor(BB);
267 
268  BB->eraseFromParent();
269  }
270 }
Pass interface - Implemented by all &#39;passes&#39;.
Definition: Pass.h:77
bool isIntrinsic() const
isIntrinsic - Returns true if the function&#39;s name starts with "llvm.".
Definition: Function.h:200
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
NodeTy * getNextNode()
Get the next node, or nullptr for the list tail.
Definition: ilist_node.h:288
This class represents lattice values for constants.
Definition: AllocatorList.h:23
iterator end()
Definition: Function.h:707
static bool runImpl(CallGraphSCC &SCC, CallGraph &CG)
Definition: PruneEH.cpp:63
This class represents a function call, abstracting a target machine&#39;s calling convention.
bool isTerminator() const
Definition: Instruction.h:163
bool hasFnAttribute(Attribute::AttrKind Kind) const
Return true if the function has the attribute.
Definition: Function.h:330
STATISTIC(NumFunctions, "Total number of functions")
F(f)
A node in the call graph for a module.
Definition: CallGraph.h:174
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:289
void initializePruneEHPass(PassRegistry &)
static bool SimplifyFunction(Function *F, CallGraph &CG)
Definition: PruneEH.cpp:189
prune eh
Definition: PruneEH.cpp:58
bool canSimplifyInvokeNoUnwind(const Function *F)
Interval::succ_iterator succ_begin(Interval *I)
succ_begin/succ_end - define methods so that Intervals may be used just like BasicBlocks can with the...
Definition: Interval.h:102
This file provides interfaces used to build and manipulate a call graph, which is a very useful tool ...
static void DeleteBasicBlock(BasicBlock *BB, CallGraph &CG)
DeleteBasicBlock - remove the specified basic block from the program, updating the callgraph to refle...
Definition: PruneEH.cpp:232
iterator begin()
Definition: Function.h:705
Interval::succ_iterator succ_end(Interval *I)
Definition: Interval.h:105
The ModulePass which wraps up a CallGraph and the logic to build it.
Definition: CallGraph.h:344
bool isLeaf(ID id)
Returns true if the intrinsic is a leaf, i.e.
Definition: Function.cpp:1144
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
This function has undefined behavior.
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
This file contains the declarations for the subclasses of Constant, which represent the different fla...
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:364
bool mayThrow() const
Return true if this instruction may throw an exception.
bool doesNotReturn() const
Determine if the function cannot return.
Definition: Function.h:547
void removeCallEdgeFor(CallBase &Call)
Removes the edge in the node for the specified call site.
Definition: CallGraph.cpp:226
constexpr double e
Definition: MathExtras.h:58
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:375
bool pred_empty(const BasicBlock *BB)
Definition: CFG.h:117
lazy value info
static UndefValue * get(Type *T)
Static factory methods - Return an &#39;undef&#39; object of the specified type.
Definition: Constants.cpp:1665
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
bool doesNotThrow() const
Determine if the function cannot unwind.
Definition: Function.h:558
Iterator for intrusive lists based on ilist_node.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:439
iterator end()
Definition: BasicBlock.h:291
Intrinsic::ID getIntrinsicID() const LLVM_READONLY
getIntrinsicID - This method returns the ID number of the specified function, or Intrinsic::not_intri...
Definition: Function.h:195
void removeUnwindEdge(BasicBlock *BB, DomTreeUpdater *DTU=nullptr)
Replace &#39;BB&#39;s terminator with one that does not have an unwind successor block.
Definition: Local.cpp:2232
amdgpu Simplify well known AMD library false FunctionCallee Callee
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
The basic data container for the call graph of a Module of IR.
Definition: CallGraph.h:73
bool hasExactDefinition() const
Return true if this global has an exact defintion.
Definition: GlobalValue.h:415
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:107
std::vector< CallGraphNode * >::const_iterator iterator
SymbolTableList< BasicBlock >::iterator eraseFromParent()
Unlink &#39;this&#39; from the containing function and delete it.
Definition: BasicBlock.cpp:127
#define I(x, y, z)
Definition: MD5.cpp:59
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
Pass * createPruneEHPass()
createPruneEHPass - Return a new pass object which transforms invoke instructions into calls...
Definition: PruneEH.cpp:61
CallGraphSCC - This is a single SCC that a CallGraphSCCPass is run on.
Invoke instruction.
void addFnAttr(Attribute::AttrKind Kind)
Add function attributes to this function.
Definition: Function.h:236
INITIALIZE_PASS_BEGIN(PruneEH, "prune-eh", "Remove unused exception handling info", false, false) INITIALIZE_PASS_END(PruneEH
unsigned changeToUnreachable(Instruction *I, bool UseLLVMTrap, bool PreserveLCSSA=false, DomTreeUpdater *DTU=nullptr, MemorySSAUpdater *MSSAU=nullptr)
Insert an unreachable instruction before the specified instruction, making it and the rest of the cod...
Definition: Local.cpp:1943
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)