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/SetVector.h"
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"
28 #include "llvm/InitializePasses.h"
30 #include "llvm/Transforms/IPO.h"
33 #include <algorithm>
34 
35 using namespace llvm;
36 
37 #define DEBUG_TYPE "prune-eh"
38 
39 STATISTIC(NumRemoved, "Number of invokes removed");
40 STATISTIC(NumUnreach, "Number of noreturn calls optimized");
41 
42 namespace {
43  struct PruneEH : public CallGraphSCCPass {
44  static char ID; // Pass identification, replacement for typeid
45  PruneEH() : CallGraphSCCPass(ID) {
47  }
48 
49  // runOnSCC - Analyze the SCC, performing the transformation if possible.
50  bool runOnSCC(CallGraphSCC &SCC) override;
51  };
52 }
53 static bool SimplifyFunction(Function *F, CallGraphUpdater &CGU);
54 static void DeleteBasicBlock(BasicBlock *BB, CallGraphUpdater &CGU);
55 
56 char PruneEH::ID = 0;
57 INITIALIZE_PASS_BEGIN(PruneEH, "prune-eh",
58  "Remove unused exception handling info", false, false)
61  "Remove unused exception handling info", false, false)
62 
63 Pass *llvm::createPruneEHPass() { return new PruneEH(); }
64 
65 static bool runImpl(CallGraphUpdater &CGU, SetVector<Function *> &Functions) {
66 #ifndef NDEBUG
67  for (auto *F : Functions)
68  assert(F && "null Function");
69 #endif
70  bool MadeChange = false;
71 
72  // First pass, scan all of the functions in the SCC, simplifying them
73  // according to what we know.
74  for (Function *F : Functions)
75  MadeChange |= SimplifyFunction(F, CGU);
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 (Function *F : Functions) {
86  if (!F->hasExactDefinition()) {
87  SCCMightUnwind |= !F->doesNotThrow();
88  SCCMightReturn |= !F->doesNotReturn();
89  } else {
90  bool CheckUnwind = !SCCMightUnwind && !F->doesNotThrow();
91  bool CheckReturn = !SCCMightReturn && !F->doesNotReturn();
92  // Determine if we should scan for InlineAsm in a naked function as it
93  // is the only way to return without a ReturnInst. Only do this for
94  // no-inline functions as functions which may be inlined cannot
95  // meaningfully return via assembly.
96  bool CheckReturnViaAsm = CheckReturn &&
97  F->hasFnAttribute(Attribute::Naked) &&
98  F->hasFnAttribute(Attribute::NoInline);
99 
100  if (!CheckUnwind && !CheckReturn)
101  continue;
102 
103  for (const BasicBlock &BB : *F) {
104  const Instruction *TI = BB.getTerminator();
105  if (CheckUnwind && TI->mayThrow()) {
106  SCCMightUnwind = true;
107  } else if (CheckReturn && isa<ReturnInst>(TI)) {
108  SCCMightReturn = true;
109  }
110 
111  for (const Instruction &I : BB) {
112  if ((!CheckUnwind || SCCMightUnwind) &&
113  (!CheckReturnViaAsm || SCCMightReturn))
114  break;
115 
116  // Check to see if this function performs an unwind or calls an
117  // unwinding function.
118  if (CheckUnwind && !SCCMightUnwind && I.mayThrow()) {
119  bool InstMightUnwind = true;
120  if (const auto *CI = dyn_cast<CallInst>(&I)) {
121  if (Function *Callee = CI->getCalledFunction()) {
122  // If the callee is outside our current SCC then we may throw
123  // because it might. If it is inside, do nothing.
124  if (Functions.contains(Callee))
125  InstMightUnwind = false;
126  }
127  }
128  SCCMightUnwind |= InstMightUnwind;
129  }
130  if (CheckReturnViaAsm && !SCCMightReturn)
131  if (const auto *CB = dyn_cast<CallBase>(&I))
132  if (const auto *IA = dyn_cast<InlineAsm>(CB->getCalledOperand()))
133  if (IA->hasSideEffects())
134  SCCMightReturn = true;
135  }
136  }
137  if (SCCMightUnwind && SCCMightReturn)
138  break;
139  }
140  }
141 
142  // If the SCC doesn't unwind or doesn't throw, note this fact.
143  if (!SCCMightUnwind || !SCCMightReturn)
144  for (Function *F : Functions) {
145  if (!SCCMightUnwind && !F->hasFnAttribute(Attribute::NoUnwind)) {
146  F->addFnAttr(Attribute::NoUnwind);
147  MadeChange = true;
148  }
149 
150  if (!SCCMightReturn && !F->hasFnAttribute(Attribute::NoReturn)) {
151  F->addFnAttr(Attribute::NoReturn);
152  MadeChange = true;
153  }
154  }
155 
156  for (Function *F : Functions) {
157  // Convert any invoke instructions to non-throwing functions in this node
158  // into call instructions with a branch. This makes the exception blocks
159  // dead.
160  MadeChange |= SimplifyFunction(F, CGU);
161  }
162 
163  return MadeChange;
164 }
165 
166 bool PruneEH::runOnSCC(CallGraphSCC &SCC) {
167  if (skipSCC(SCC))
168  return false;
169  SetVector<Function *> Functions;
170  for (auto &N : SCC) {
171  if (auto *F = N->getFunction())
172  Functions.insert(F);
173  }
174  CallGraph &CG = getAnalysis<CallGraphWrapperPass>().getCallGraph();
175  CallGraphUpdater CGU;
176  CGU.initialize(CG, SCC);
177  return runImpl(CGU, Functions);
178 }
179 
180 
181 // SimplifyFunction - Given information about callees, simplify the specified
182 // function if we have invokes to non-unwinding functions or code after calls to
183 // no-return functions.
185  bool MadeChange = false;
186  for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) {
187  if (InvokeInst *II = dyn_cast<InvokeInst>(BB->getTerminator()))
188  if (II->doesNotThrow() && canSimplifyInvokeNoUnwind(F)) {
189  BasicBlock *UnwindBlock = II->getUnwindDest();
190  removeUnwindEdge(&*BB);
191 
192  // If the unwind block is now dead, nuke it.
193  if (pred_empty(UnwindBlock))
194  DeleteBasicBlock(UnwindBlock, CGU); // Delete the new BB.
195 
196  ++NumRemoved;
197  MadeChange = true;
198  }
199 
200  for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; )
201  if (CallInst *CI = dyn_cast<CallInst>(I++))
202  if (CI->doesNotReturn() && !CI->isMustTailCall() &&
203  !isa<UnreachableInst>(I)) {
204  // This call calls a function that cannot return. Insert an
205  // unreachable instruction after it and simplify the code. Do this
206  // by splitting the BB, adding the unreachable, then deleting the
207  // new BB.
208  BasicBlock *New = BB->splitBasicBlock(I);
209 
210  // Remove the uncond branch and add an unreachable.
211  BB->getInstList().pop_back();
212  new UnreachableInst(BB->getContext(), &*BB);
213 
214  DeleteBasicBlock(New, CGU); // Delete the new BB.
215  MadeChange = true;
216  ++NumUnreach;
217  break;
218  }
219  }
220 
221  return MadeChange;
222 }
223 
224 /// DeleteBasicBlock - remove the specified basic block from the program,
225 /// updating the callgraph to reflect any now-obsolete edges due to calls that
226 /// exist in the BB.
228  assert(pred_empty(BB) && "BB is not dead!");
229 
230  Instruction *TokenInst = nullptr;
231 
232  for (BasicBlock::iterator I = BB->end(), E = BB->begin(); I != E; ) {
233  --I;
234 
235  if (I->getType()->isTokenTy()) {
236  TokenInst = &*I;
237  break;
238  }
239 
240  if (auto *Call = dyn_cast<CallBase>(&*I)) {
241  const Function *Callee = Call->getCalledFunction();
242  if (!Callee || !Intrinsic::isLeaf(Callee->getIntrinsicID()))
243  CGU.removeCallSite(*Call);
244  else if (!Callee->isIntrinsic())
245  CGU.removeCallSite(*Call);
246  }
247 
248  if (!I->use_empty())
249  I->replaceAllUsesWith(UndefValue::get(I->getType()));
250  }
251 
252  if (TokenInst) {
253  if (!TokenInst->isTerminator())
254  changeToUnreachable(TokenInst->getNextNode(), /*UseLLVMTrap=*/false);
255  } else {
256  // Get the list of successors of this block.
257  std::vector<BasicBlock *> Succs(succ_begin(BB), succ_end(BB));
258 
259  for (unsigned i = 0, e = Succs.size(); i != e; ++i)
260  Succs[i]->removePredecessor(BB);
261 
262  BB->eraseFromParent();
263  }
264 }
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
static bool SimplifyFunction(Function *F, CallGraphUpdater &CGU)
Definition: PruneEH.cpp:184
iterator end()
Definition: Function.h:736
This class represents a function call, abstracting a target machine&#39;s calling convention.
bool isTerminator() const
Definition: Instruction.h:163
STATISTIC(NumFunctions, "Total number of functions")
F(f)
Wrapper to unify "old style" CallGraph and "new style" LazyCallGraph.
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:296
void initializePruneEHPass(PassRegistry &)
void removeCallSite(CallBase &CS)
Remove the call site CS from the call graph.
prune eh
Definition: PruneEH.cpp:60
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 ...
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:141
This file provides interfaces used to manipulate a call graph, regardless if it is a "old style" Call...
iterator begin()
Definition: Function.h:734
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:1219
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...
bool mayThrow() const
Return true if this instruction may throw an exception.
constexpr double e
Definition: MathExtras.h:58
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:1684
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
Iterator for intrusive lists based on ilist_node.
iterator end()
Definition: BasicBlock.h:298
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:2326
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
static bool runImpl(CallGraphUpdater &CGU, SetVector< Function *> &Functions)
Definition: PruneEH.cpp:65
SymbolTableList< BasicBlock >::iterator eraseFromParent()
Unlink &#39;this&#39; from the containing function and delete it.
Definition: BasicBlock.cpp:129
#define I(x, y, z)
Definition: MD5.cpp:59
#define N
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
Pass * createPruneEHPass()
createPruneEHPass - Return a new pass object which transforms invoke instructions into calls...
Definition: PruneEH.cpp:63
CallGraphSCC - This is a single SCC that a CallGraphSCCPass is run on.
A vector that has set insertion semantics.
Definition: SetVector.h:40
Invoke instruction.
INITIALIZE_PASS_BEGIN(PruneEH, "prune-eh", "Remove unused exception handling info", false, false) INITIALIZE_PASS_END(PruneEH
void initialize(CallGraph &CG, CallGraphSCC &SCC)
Initializers for usage outside of a CGSCC pass, inside a CGSCC pass in the old and new pass manager (...
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:2037
static void DeleteBasicBlock(BasicBlock *BB, CallGraphUpdater &CGU)
DeleteBasicBlock - remove the specified basic block from the program, updating the callgraph to refle...
Definition: PruneEH.cpp:227
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)