LLVM  14.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);
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());
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 }
i
i
Definition: README.txt:29
llvm::CallGraphUpdater
Wrapper to unify "old style" CallGraph and "new style" LazyCallGraph.
Definition: CallGraphUpdater.h:28
llvm::Instruction::isTerminator
bool isTerminator() const
Definition: Instruction.h:163
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
llvm::BasicBlock::iterator
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:90
DeleteBasicBlock
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
llvm::succ_end
Interval::succ_iterator succ_end(Interval *I)
Definition: Interval.h:102
llvm::Function
Definition: Function.h:61
llvm::ilist_node_with_parent::getNextNode
NodeTy * getNextNode()
Get the next node, or nullptr for the list tail.
Definition: ilist_node.h:288
Statistic.h
InlineAsm.h
llvm::createPruneEHPass
Pass * createPruneEHPass()
createPruneEHPass - Return a new pass object which transforms invoke instructions into calls,...
Definition: PruneEH.cpp:63
Local.h
llvm::CallGraph
The basic data container for the call graph of a Module of IR.
Definition: CallGraph.h:73
SimplifyFunction
static bool SimplifyFunction(Function *F, CallGraphUpdater &CGU)
Definition: PruneEH.cpp:184
EHPersonalities.h
llvm::Instruction::mayThrow
bool mayThrow() const
Return true if this instruction may throw an exception.
Definition: Instruction.cpp:673
F
#define F(x, y, z)
Definition: MD5.cpp:56
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
llvm::CallGraphSCC
CallGraphSCC - This is a single SCC that a CallGraphSCCPass is run on.
Definition: CallGraphSCCPass.h:87
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:31
Constants.h
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::CallGraphUpdater::removeCallSite
void removeCallSite(CallBase &CS)
Remove the call site CS from the call graph.
Definition: CallGraphUpdater.cpp:160
false
Definition: StackSlotColoring.cpp:142
llvm::Instruction
Definition: Instruction.h:45
llvm::STATISTIC
STATISTIC(NumFunctions, "Total number of functions")
llvm::UndefValue::get
static UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
Definition: Constants.cpp:1771
SmallPtrSet.h
INITIALIZE_PASS_END
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:58
CFG.h
llvm::InvokeInst
Invoke instruction.
Definition: Instructions.h:3749
llvm::removeUnwindEdge
void removeUnwindEdge(BasicBlock *BB, DomTreeUpdater *DTU=nullptr)
Replace 'BB's terminator with one that does not have an unwind successor block.
Definition: Local.cpp:2420
INITIALIZE_PASS_DEPENDENCY
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
llvm::canSimplifyInvokeNoUnwind
bool canSimplifyInvokeNoUnwind(const Function *F)
Definition: EHPersonalities.cpp:73
IPO.h
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:57
llvm::CallGraphWrapperPass
The ModulePass which wraps up a CallGraph and the logic to build it.
Definition: CallGraph.h:337
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::succ_begin
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:99
llvm::initializePruneEHPass
void initializePruneEHPass(PassRegistry &)
llvm::Intrinsic::isLeaf
bool isLeaf(ID id)
Returns true if the intrinsic is a leaf, i.e.
Definition: Function.cpp:1362
runImpl
static bool runImpl(CallGraphUpdater &CGU, SetVector< Function * > &Functions)
Definition: PruneEH.cpp:65
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
eh
prune eh
Definition: PruneEH.cpp:60
info
lazy value info
Definition: LazyValueInfo.cpp:59
llvm::SetVector::insert
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:141
llvm::AMDGPU::CPol::SCC
@ SCC
Definition: SIDefines.h:292
llvm::pred_empty
bool pred_empty(const BasicBlock *BB)
Definition: CFG.h:119
CallGraphSCCPass.h
Callee
amdgpu Simplify well known AMD library false FunctionCallee Callee
Definition: AMDGPULibCalls.cpp:206
Function.h
llvm::CallGraphSCCPass
Definition: CallGraphSCCPass.h:34
CallGraph.h
INITIALIZE_PASS_BEGIN
INITIALIZE_PASS_BEGIN(PruneEH, "prune-eh", "Remove unused exception handling info", false, false) INITIALIZE_PASS_END(PruneEH
llvm::changeToUnreachable
unsigned changeToUnreachable(Instruction *I, 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:2101
llvm::Pass
Pass interface - Implemented by all 'passes'.
Definition: Pass.h:91
Instructions.h
N
#define N
llvm::CallInst
This class represents a function call, abstracting a target machine's calling convention.
Definition: Instructions.h:1475
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
llvm::UnreachableInst
This function has undefined behavior.
Definition: Instructions.h:4715
LLVMContext.h
CallGraphUpdater.h
raw_ostream.h
llvm::CallGraphUpdater::initialize
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 (...
Definition: CallGraphUpdater.h:62
llvm::SetVector< Function * >
InitializePasses.h
SetVector.h
llvm::Function::iterator
BasicBlockListType::iterator iterator
Definition: Function.h:67
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:37