LLVM  7.0.0svn
PruneEH.cpp
Go to the documentation of this file.
1 //===- PruneEH.cpp - Pass which deletes unused exception handlers ---------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file implements a simple interprocedural pass which walks the
11 // call-graph, turning invoke instructions into calls, iff the callee cannot
12 // throw an exception, and marking functions 'nounwind' if they cannot throw.
13 // It implements this as a bottom-up traversal of the call-graph.
14 //
15 //===----------------------------------------------------------------------===//
16 
17 #include "llvm/ADT/SmallPtrSet.h"
18 #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"
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)
58 INITIALIZE_PASS_END(PruneEH, "prune-eh",
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 TerminatorInst *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 (auto ICS = ImmutableCallSite(&I))
139  if (const auto *IA = dyn_cast<InlineAsm>(ICS.getCalledValue()))
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() && !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 CS = CallSite (&*I)) {
246  const Function *Callee = CS.getCalledFunction();
247  if (!Callee || !Intrinsic::isLeaf(Callee->getIntrinsicID()))
248  CGN->removeCallEdgeFor(CS);
249  else if (!Callee->isIntrinsic())
250  CGN->removeCallEdgeFor(CS);
251  }
252 
253  if (!I->use_empty())
254  I->replaceAllUsesWith(UndefValue::get(I->getType()));
255  }
256 
257  if (TokenInst) {
258  if (!isa<TerminatorInst>(TokenInst))
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:81
bool isIntrinsic() const
isIntrinsic - Returns true if the function&#39;s name starts with "llvm.".
Definition: Function.h:180
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:289
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
iterator end()
Definition: Function.h:636
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 hasFnAttribute(Attribute::AttrKind Kind) const
Return true if the function has the attribute.
Definition: Function.h:302
STATISTIC(NumFunctions, "Total number of functions")
F(f)
A node in the call graph for a module.
Definition: CallGraph.h:165
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:252
void initializePruneEHPass(PassRegistry &)
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:51
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:103
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:634
amdgpu Simplify well known AMD library false Value * Callee
Interval::succ_iterator succ_end(Interval *I)
Definition: Interval.h:106
Subclasses of this class are all able to terminate a basic block.
Definition: InstrTypes.h:54
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:963
LLVM Basic Block Representation.
Definition: BasicBlock.h:59
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:371
bool mayThrow() const
Return true if this instruction may throw an exception.
bool doesNotReturn() const
Determine if the function cannot return.
Definition: Function.h:490
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:382
bool pred_empty(const BasicBlock *BB)
Definition: CFG.h:107
lazy value info
static UndefValue * get(Type *T)
Static factory methods - Return an &#39;undef&#39; object of the specified type.
Definition: Constants.cpp:1356
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:498
const InstListType & getInstList() const
Return the underlying instruction list container.
Definition: BasicBlock.h:317
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:418
iterator end()
Definition: BasicBlock.h:254
void removeUnwindEdge(BasicBlock *BB, DeferredDominance *DDT=nullptr)
Replace &#39;BB&#39;s terminator with one that does not have an unwind successor block.
Definition: Local.cpp:1882
Intrinsic::ID getIntrinsicID() const LLVM_READONLY
getIntrinsicID - This method returns the ID number of the specified function, or Intrinsic::not_intri...
Definition: Function.h:175
The basic data container for the call graph of a Module of IR.
Definition: CallGraph.h:74
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:713
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:108
std::vector< CallGraphNode * >::const_iterator iterator
SymbolTableList< BasicBlock >::iterator eraseFromParent()
Unlink &#39;this&#39; from the containing function and delete it.
Definition: BasicBlock.cpp:97
#define I(x, y, z)
Definition: MD5.cpp:58
BasicBlock * splitBasicBlock(iterator I, const Twine &BBName="")
Split the basic block into two basic blocks at the specified instruction.
Definition: BasicBlock.cpp:383
unsigned changeToUnreachable(Instruction *I, bool UseLLVMTrap, bool PreserveLCSSA=false, DeferredDominance *DDT=nullptr)
Insert an unreachable instruction before the specified instruction, making it and the rest of the cod...
Definition: Local.cpp:1623
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.
void removeCallEdgeFor(CallSite CS)
Removes the edge in the node for the specified call site.
Definition: CallGraph.cpp:188
Invoke instruction.
void addFnAttr(Attribute::AttrKind Kind)
Add function attributes to this function.
Definition: Function.h:211
INITIALIZE_PASS_BEGIN(PruneEH, "prune-eh", "Remove unused exception handling info", false, false) INITIALIZE_PASS_END(PruneEH
void pop_back()
Definition: ilist.h:331