LLVM  9.0.0svn
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"
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"
29 #include "llvm/Transforms/IPO.h"
30 #include <algorithm>
31 using namespace llvm;
32 
33 #define DEBUG_TYPE "prune-eh"
34 
35 STATISTIC(NumRemoved, "Number of invokes removed");
36 STATISTIC(NumUnreach, "Number of noreturn calls optimized");
37 
38 namespace {
39  struct PruneEH : public CallGraphSCCPass {
40  static char ID; // Pass identification, replacement for typeid
41  PruneEH() : CallGraphSCCPass(ID) {
43  }
44 
45  // runOnSCC - Analyze the SCC, performing the transformation if possible.
46  bool runOnSCC(CallGraphSCC &SCC) override;
47 
48  };
49 }
50 static bool SimplifyFunction(Function *F, CallGraph &CG);
51 static void DeleteBasicBlock(BasicBlock *BB, CallGraph &CG);
52 
53 char PruneEH::ID = 0;
54 INITIALIZE_PASS_BEGIN(PruneEH, "prune-eh",
55  "Remove unused exception handling info", false, false)
58  "Remove unused exception handling info", false, false)
59 
60 Pass *llvm::createPruneEHPass() { return new PruneEH(); }
61 
62 static bool runImpl(CallGraphSCC &SCC, CallGraph &CG) {
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 
177 bool 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.
188 static 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.
231 static 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 }
Pass interface - Implemented by all &#39;passes&#39;.
Definition: Pass.h:80
bool isIntrinsic() const
isIntrinsic - Returns true if the function&#39;s name starts with "llvm.".
Definition: Function.h:198
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:660
static bool runImpl(CallGraphSCC &SCC, CallGraph &CG)
Definition: PruneEH.cpp:62
This class represents a function call, abstracting a target machine&#39;s calling convention.
bool isTerminator() const
Definition: Instruction.h:128
bool hasFnAttribute(Attribute::AttrKind Kind) const
Return true if the function has the attribute.
Definition: Function.h:320
STATISTIC(NumFunctions, "Total number of functions")
F(f)
A node in the call graph for a module.
Definition: CallGraph.h:164
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:268
void initializePruneEHPass(PassRegistry &)
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:50
unsigned changeToUnreachable(Instruction *I, bool UseLLVMTrap, bool PreserveLCSSA=false, DomTreeUpdater *DTU=nullptr)
Insert an unreachable instruction before the specified instruction, making it and the rest of the cod...
Definition: Local.cpp:1896
static bool SimplifyFunction(Function *F, CallGraph &CG)
Definition: PruneEH.cpp:188
prune eh
Definition: PruneEH.cpp:57
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:231
iterator begin()
Definition: Function.h:658
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:324
bool isLeaf(ID id)
Returns true if the intrinsic is a leaf, i.e.
Definition: Function.cpp:1001
LLVM Basic Block Representation.
Definition: BasicBlock.h:57
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:370
bool mayThrow() const
Return true if this instruction may throw an exception.
bool doesNotReturn() const
Determine if the function cannot return.
Definition: Function.h:508
void removeCallEdgeFor(CallBase &Call)
Removes the edge in the node for the specified call site.
Definition: CallGraph.cpp:186
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:381
bool pred_empty(const BasicBlock *BB)
Definition: CFG.h:116
lazy value info
static UndefValue * get(Type *T)
Static factory methods - Return an &#39;undef&#39; object of the specified type.
Definition: Constants.cpp:1424
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:519
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:417
iterator end()
Definition: BasicBlock.h:270
Intrinsic::ID getIntrinsicID() const LLVM_READONLY
getIntrinsicID - This method returns the ID number of the specified function, or Intrinsic::not_intri...
Definition: Function.h:193
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:2163
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:406
Establish a view to a call site for examination.
Definition: CallSite.h:892
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:106
std::vector< CallGraphNode * >::const_iterator iterator
SymbolTableList< BasicBlock >::iterator eraseFromParent()
Unlink &#39;this&#39; from the containing function and delete it.
Definition: BasicBlock.cpp:114
#define I(x, y, z)
Definition: MD5.cpp:58
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
Pass * createPruneEHPass()
createPruneEHPass - Return a new pass object which transforms invoke instructions into calls...
Definition: PruneEH.cpp:60
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:229
INITIALIZE_PASS_BEGIN(PruneEH, "prune-eh", "Remove unused exception handling info", false, false) INITIALIZE_PASS_END(PruneEH