LLVM  6.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/IntrinsicInst.h"
28 #include "llvm/IR/LLVMContext.h"
30 #include "llvm/Transforms/IPO.h"
32 #include <algorithm>
33 using namespace llvm;
34 
35 #define DEBUG_TYPE "prune-eh"
36 
37 STATISTIC(NumRemoved, "Number of invokes removed");
38 STATISTIC(NumUnreach, "Number of noreturn calls optimized");
39 
40 namespace {
41  struct PruneEH : public CallGraphSCCPass {
42  static char ID; // Pass identification, replacement for typeid
43  PruneEH() : CallGraphSCCPass(ID) {
45  }
46 
47  // runOnSCC - Analyze the SCC, performing the transformation if possible.
48  bool runOnSCC(CallGraphSCC &SCC) override;
49 
50  };
51 }
52 static bool SimplifyFunction(Function *F, CallGraph &CG);
53 static void DeleteBasicBlock(BasicBlock *BB, CallGraph &CG);
54 
55 char PruneEH::ID = 0;
56 INITIALIZE_PASS_BEGIN(PruneEH, "prune-eh",
57  "Remove unused exception handling info", false, false)
59 INITIALIZE_PASS_END(PruneEH, "prune-eh",
60  "Remove unused exception handling info", false, false)
61 
62 Pass *llvm::createPruneEHPass() { return new PruneEH(); }
63 
64 static bool runImpl(CallGraphSCC &SCC, CallGraph &CG) {
66  bool MadeChange = false;
67 
68  // Fill SCCNodes with the elements of the SCC. Used for quickly
69  // looking up whether a given CallGraphNode is in this SCC.
70  for (CallGraphNode *I : SCC)
71  SCCNodes.insert(I);
72 
73  // First pass, scan all of the functions in the SCC, simplifying them
74  // according to what we know.
75  for (CallGraphNode *I : SCC)
76  if (Function *F = I->getFunction())
77  MadeChange |= SimplifyFunction(F, CG);
78 
79  // Next, check to see if any callees might throw or if there are any external
80  // functions in this SCC: if so, we cannot prune any functions in this SCC.
81  // Definitions that are weak and not declared non-throwing might be
82  // overridden at linktime with something that throws, so assume that.
83  // If this SCC includes the unwind instruction, we KNOW it throws, so
84  // obviously the SCC might throw.
85  //
86  bool SCCMightUnwind = false, SCCMightReturn = false;
87  for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end();
88  (!SCCMightUnwind || !SCCMightReturn) && I != E; ++I) {
89  Function *F = (*I)->getFunction();
90  if (!F) {
91  SCCMightUnwind = true;
92  SCCMightReturn = true;
93  } else if (!F->hasExactDefinition()) {
94  SCCMightUnwind |= !F->doesNotThrow();
95  SCCMightReturn |= !F->doesNotReturn();
96  } else {
97  bool CheckUnwind = !SCCMightUnwind && !F->doesNotThrow();
98  bool CheckReturn = !SCCMightReturn && !F->doesNotReturn();
99  // Determine if we should scan for InlineAsm in a naked function as it
100  // is the only way to return without a ReturnInst. Only do this for
101  // no-inline functions as functions which may be inlined cannot
102  // meaningfully return via assembly.
103  bool CheckReturnViaAsm = CheckReturn &&
104  F->hasFnAttribute(Attribute::Naked) &&
105  F->hasFnAttribute(Attribute::NoInline);
106 
107  if (!CheckUnwind && !CheckReturn)
108  continue;
109 
110  for (const BasicBlock &BB : *F) {
111  const TerminatorInst *TI = BB.getTerminator();
112  if (CheckUnwind && TI->mayThrow()) {
113  SCCMightUnwind = true;
114  } else if (CheckReturn && isa<ReturnInst>(TI)) {
115  SCCMightReturn = true;
116  }
117 
118  for (const Instruction &I : BB) {
119  if ((!CheckUnwind || SCCMightUnwind) &&
120  (!CheckReturnViaAsm || SCCMightReturn))
121  break;
122 
123  // Check to see if this function performs an unwind or calls an
124  // unwinding function.
125  if (CheckUnwind && !SCCMightUnwind && I.mayThrow()) {
126  bool InstMightUnwind = true;
127  if (const auto *CI = dyn_cast<CallInst>(&I)) {
128  if (Function *Callee = CI->getCalledFunction()) {
129  CallGraphNode *CalleeNode = CG[Callee];
130  // If the callee is outside our current SCC then we may throw
131  // because it might. If it is inside, do nothing.
132  if (SCCNodes.count(CalleeNode) > 0)
133  InstMightUnwind = false;
134  }
135  }
136  SCCMightUnwind |= InstMightUnwind;
137  }
138  if (CheckReturnViaAsm && !SCCMightReturn)
139  if (auto ICS = ImmutableCallSite(&I))
140  if (const auto *IA = dyn_cast<InlineAsm>(ICS.getCalledValue()))
141  if (IA->hasSideEffects())
142  SCCMightReturn = true;
143  }
144 
145  if (SCCMightUnwind && SCCMightReturn)
146  break;
147  }
148  }
149  }
150 
151  // If the SCC doesn't unwind or doesn't throw, note this fact.
152  if (!SCCMightUnwind || !SCCMightReturn)
153  for (CallGraphNode *I : SCC) {
154  Function *F = I->getFunction();
155 
156  if (!SCCMightUnwind && !F->hasFnAttribute(Attribute::NoUnwind)) {
157  F->addFnAttr(Attribute::NoUnwind);
158  MadeChange = true;
159  }
160 
161  if (!SCCMightReturn && !F->hasFnAttribute(Attribute::NoReturn)) {
162  F->addFnAttr(Attribute::NoReturn);
163  MadeChange = true;
164  }
165  }
166 
167  for (CallGraphNode *I : SCC) {
168  // Convert any invoke instructions to non-throwing functions in this node
169  // into call instructions with a branch. This makes the exception blocks
170  // dead.
171  if (Function *F = I->getFunction())
172  MadeChange |= SimplifyFunction(F, CG);
173  }
174 
175  return MadeChange;
176 }
177 
178 
179 bool PruneEH::runOnSCC(CallGraphSCC &SCC) {
180  if (skipSCC(SCC))
181  return false;
182  CallGraph &CG = getAnalysis<CallGraphWrapperPass>().getCallGraph();
183  return runImpl(SCC, CG);
184 }
185 
186 
187 // SimplifyFunction - Given information about callees, simplify the specified
188 // function if we have invokes to non-unwinding functions or code after calls to
189 // no-return functions.
190 static bool SimplifyFunction(Function *F, CallGraph &CG) {
191  bool MadeChange = false;
192  for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) {
193  if (InvokeInst *II = dyn_cast<InvokeInst>(BB->getTerminator()))
194  if (II->doesNotThrow() && canSimplifyInvokeNoUnwind(F)) {
195  BasicBlock *UnwindBlock = II->getUnwindDest();
196  removeUnwindEdge(&*BB);
197 
198  // If the unwind block is now dead, nuke it.
199  if (pred_empty(UnwindBlock))
200  DeleteBasicBlock(UnwindBlock, CG); // Delete the new BB.
201 
202  ++NumRemoved;
203  MadeChange = true;
204  }
205 
206  for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; )
207  if (CallInst *CI = dyn_cast<CallInst>(I++))
208  if (CI->doesNotReturn() && !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 CS = CallSite (&*I)) {
247  const Function *Callee = CS.getCalledFunction();
248  if (!Callee || !Intrinsic::isLeaf(Callee->getIntrinsicID()))
249  CGN->removeCallEdgeFor(CS);
250  else if (!Callee->isIntrinsic())
251  CGN->removeCallEdgeFor(CS);
252  }
253 
254  if (!I->use_empty())
255  I->replaceAllUsesWith(UndefValue::get(I->getType()));
256  }
257 
258  if (TokenInst) {
259  if (!isa<TerminatorInst>(TokenInst))
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: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:590
static bool runImpl(CallGraphSCC &SCC, CallGraph &CG)
Definition: PruneEH.cpp:64
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:262
STATISTIC(NumFunctions, "Total number of functions")
F(f)
unsigned changeToUnreachable(Instruction *I, bool UseLLVMTrap, bool PreserveLCSSA=false)
Insert an unreachable instruction before the specified instruction, making it and the rest of the cod...
Definition: Local.cpp:1452
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:190
prune eh
Definition: PruneEH.cpp:59
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:232
iterator begin()
Definition: Function.h:588
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:444
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:1320
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:452
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
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
void removeUnwindEdge(BasicBlock *BB)
Replace &#39;BB&#39;s terminator with one that does not have an unwind successor block.
Definition: Local.cpp:1692
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:398
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:382
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
Pass * createPruneEHPass()
createPruneEHPass - Return a new pass object which transforms invoke instructions into calls...
Definition: PruneEH.cpp:62
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