LLVM  15.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/Statistic.h"
21 #include "llvm/IR/CFG.h"
22 #include "llvm/IR/Constants.h"
23 #include "llvm/IR/Function.h"
24 #include "llvm/IR/InlineAsm.h"
25 #include "llvm/IR/Instructions.h"
26 #include "llvm/InitializePasses.h"
27 #include "llvm/Transforms/IPO.h"
30 #include <algorithm>
31 
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 static bool SimplifyFunction(Function *F, CallGraphUpdater &CGU);
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(CallGraphUpdater &CGU, SetVector<Function *> &Functions) {
63 #ifndef NDEBUG
64  for (auto *F : Functions)
65  assert(F && "null Function");
66 #endif
67  bool MadeChange = false;
68 
69  // First pass, scan all of the functions in the SCC, simplifying them
70  // according to what we know.
71  for (Function *F : Functions)
72  MadeChange |= SimplifyFunction(F, CGU);
73 
74  // Next, check to see if any callees might throw or if there are any external
75  // functions in this SCC: if so, we cannot prune any functions in this SCC.
76  // Definitions that are weak and not declared non-throwing might be
77  // overridden at linktime with something that throws, so assume that.
78  // If this SCC includes the unwind instruction, we KNOW it throws, so
79  // obviously the SCC might throw.
80  //
81  bool SCCMightUnwind = false, SCCMightReturn = false;
82  for (Function *F : Functions) {
83  if (!F->hasExactDefinition()) {
84  SCCMightUnwind |= !F->doesNotThrow();
85  SCCMightReturn |= !F->doesNotReturn();
86  } else {
87  bool CheckUnwind = !SCCMightUnwind && !F->doesNotThrow();
88  bool CheckReturn = !SCCMightReturn && !F->doesNotReturn();
89  // Determine if we should scan for InlineAsm in a naked function as it
90  // is the only way to return without a ReturnInst. Only do this for
91  // no-inline functions as functions which may be inlined cannot
92  // meaningfully return via assembly.
93  bool CheckReturnViaAsm = CheckReturn &&
94  F->hasFnAttribute(Attribute::Naked) &&
95  F->hasFnAttribute(Attribute::NoInline);
96 
97  if (!CheckUnwind && !CheckReturn)
98  continue;
99 
100  for (const BasicBlock &BB : *F) {
101  const Instruction *TI = BB.getTerminator();
102  if (CheckUnwind && TI->mayThrow()) {
103  SCCMightUnwind = true;
104  } else if (CheckReturn && isa<ReturnInst>(TI)) {
105  SCCMightReturn = true;
106  }
107 
108  for (const Instruction &I : BB) {
109  if ((!CheckUnwind || SCCMightUnwind) &&
110  (!CheckReturnViaAsm || SCCMightReturn))
111  break;
112 
113  // Check to see if this function performs an unwind or calls an
114  // unwinding function.
115  if (CheckUnwind && !SCCMightUnwind && I.mayThrow()) {
116  bool InstMightUnwind = true;
117  if (const auto *CI = dyn_cast<CallInst>(&I)) {
118  if (Function *Callee = CI->getCalledFunction()) {
119  // If the callee is outside our current SCC then we may throw
120  // because it might. If it is inside, do nothing.
121  if (Functions.contains(Callee))
122  InstMightUnwind = false;
123  }
124  }
125  SCCMightUnwind |= InstMightUnwind;
126  }
127  if (CheckReturnViaAsm && !SCCMightReturn)
128  if (const auto *CB = dyn_cast<CallBase>(&I))
129  if (const auto *IA = dyn_cast<InlineAsm>(CB->getCalledOperand()))
130  if (IA->hasSideEffects())
131  SCCMightReturn = true;
132  }
133  }
134  if (SCCMightUnwind && SCCMightReturn)
135  break;
136  }
137  }
138 
139  // If the SCC doesn't unwind or doesn't throw, note this fact.
140  if (!SCCMightUnwind || !SCCMightReturn)
141  for (Function *F : Functions) {
142  if (!SCCMightUnwind && !F->hasFnAttribute(Attribute::NoUnwind)) {
143  F->addFnAttr(Attribute::NoUnwind);
144  MadeChange = true;
145  }
146 
147  if (!SCCMightReturn && !F->hasFnAttribute(Attribute::NoReturn)) {
148  F->addFnAttr(Attribute::NoReturn);
149  MadeChange = true;
150  }
151  }
152 
153  for (Function *F : Functions) {
154  // Convert any invoke instructions to non-throwing functions in this node
155  // into call instructions with a branch. This makes the exception blocks
156  // dead.
157  MadeChange |= SimplifyFunction(F, CGU);
158  }
159 
160  return MadeChange;
161 }
162 
163 bool PruneEH::runOnSCC(CallGraphSCC &SCC) {
164  if (skipSCC(SCC))
165  return false;
166  SetVector<Function *> Functions;
167  for (auto &N : SCC) {
168  if (auto *F = N->getFunction())
169  Functions.insert(F);
170  }
171  CallGraph &CG = getAnalysis<CallGraphWrapperPass>().getCallGraph();
172  CallGraphUpdater CGU;
173  CGU.initialize(CG, SCC);
174  return runImpl(CGU, Functions);
175 }
176 
177 
178 // SimplifyFunction - Given information about callees, simplify the specified
179 // function if we have invokes to non-unwinding functions or code after calls to
180 // no-return functions.
182  bool MadeChange = false;
183  for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) {
184  if (InvokeInst *II = dyn_cast<InvokeInst>(BB->getTerminator()))
185  if (II->doesNotThrow() && canSimplifyInvokeNoUnwind(F)) {
186  BasicBlock *UnwindBlock = II->getUnwindDest();
187  removeUnwindEdge(&*BB);
188 
189  // If the unwind block is now dead, nuke it.
190  if (pred_empty(UnwindBlock))
191  DeleteBasicBlock(UnwindBlock, CGU); // Delete the new BB.
192 
193  ++NumRemoved;
194  MadeChange = true;
195  }
196 
197  for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; )
198  if (CallInst *CI = dyn_cast<CallInst>(I++))
199  if (CI->doesNotReturn() && !CI->isMustTailCall() &&
200  !isa<UnreachableInst>(I)) {
201  // This call calls a function that cannot return. Insert an
202  // unreachable instruction after it and simplify the code. Do this
203  // by splitting the BB, adding the unreachable, then deleting the
204  // new BB.
205  BasicBlock *New = BB->splitBasicBlock(I);
206 
207  // Remove the uncond branch and add an unreachable.
208  BB->getInstList().pop_back();
209  new UnreachableInst(BB->getContext(), &*BB);
210 
211  DeleteBasicBlock(New, CGU); // Delete the new BB.
212  MadeChange = true;
213  ++NumUnreach;
214  break;
215  }
216  }
217 
218  return MadeChange;
219 }
220 
221 /// DeleteBasicBlock - remove the specified basic block from the program,
222 /// updating the callgraph to reflect any now-obsolete edges due to calls that
223 /// exist in the BB.
225  assert(pred_empty(BB) && "BB is not dead!");
226 
227  Instruction *TokenInst = nullptr;
228 
229  for (BasicBlock::iterator I = BB->end(), E = BB->begin(); I != E; ) {
230  --I;
231 
232  if (I->getType()->isTokenTy()) {
233  TokenInst = &*I;
234  break;
235  }
236 
237  if (auto *Call = dyn_cast<CallBase>(&*I)) {
238  const Function *Callee = Call->getCalledFunction();
239  if (!Callee || !Intrinsic::isLeaf(Callee->getIntrinsicID()))
240  CGU.removeCallSite(*Call);
241  else if (!Callee->isIntrinsic())
242  CGU.removeCallSite(*Call);
243  }
244 
245  if (!I->use_empty())
246  I->replaceAllUsesWith(UndefValue::get(I->getType()));
247  }
248 
249  if (TokenInst) {
250  if (!TokenInst->isTerminator())
251  changeToUnreachable(TokenInst->getNextNode());
252  } else {
253  // Get the list of successors of this block.
254  std::vector<BasicBlock *> Succs(succ_begin(BB), succ_end(BB));
255 
256  for (unsigned i = 0, e = Succs.size(); i != e; ++i)
257  Succs[i]->removePredecessor(BB);
258 
259  BB->eraseFromParent();
260  }
261 }
i
i
Definition: README.txt:29
llvm::CallGraphUpdater
Wrapper to unify "old style" CallGraph and "new style" LazyCallGraph.
Definition: CallGraphUpdater.h:29
llvm::Instruction::isTerminator
bool isTerminator() const
Definition: Instruction.h:160
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
llvm::BasicBlock::iterator
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:87
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:224
llvm::succ_end
Interval::succ_iterator succ_end(Interval *I)
Definition: Interval.h:102
llvm::Function
Definition: Function.h:60
llvm::ilist_node_with_parent::getNextNode
NodeTy * getNextNode()
Get the next node, or nullptr for the list tail.
Definition: ilist_node.h:289
Statistic.h
InlineAsm.h
llvm::createPruneEHPass
Pass * createPruneEHPass()
createPruneEHPass - Return a new pass object which transforms invoke instructions into calls,...
Definition: PruneEH.cpp:60
Local.h
llvm::CallGraph
The basic data container for the call graph of a Module of IR.
Definition: CallGraph.h:72
SimplifyFunction
static bool SimplifyFunction(Function *F, CallGraphUpdater &CGU)
Definition: PruneEH.cpp:181
EHPersonalities.h
llvm::Instruction::mayThrow
bool mayThrow() const
Return true if this instruction may throw an exception.
Definition: Instruction.cpp:685
F
#define F(x, y, z)
Definition: MD5.cpp:55
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:55
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:162
false
Definition: StackSlotColoring.cpp:141
llvm::Instruction
Definition: Instruction.h:42
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:1777
llvm::CallingConv::ID
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
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:3763
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:2446
INITIALIZE_PASS_DEPENDENCY
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
llvm::canSimplifyInvokeNoUnwind
bool canSimplifyInvokeNoUnwind(const Function *F)
Definition: EHPersonalities.cpp:77
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:336
I
#define I(x, y, z)
Definition: MD5.cpp:58
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:1401
runImpl
static bool runImpl(CallGraphUpdater &CGU, SetVector< Function * > &Functions)
Definition: PruneEH.cpp:62
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
eh
prune eh
Definition: PruneEH.cpp:57
info
lazy value info
Definition: LazyValueInfo.cpp:58
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:304
llvm::pred_empty
bool pred_empty(const BasicBlock *BB)
Definition: CFG.h:118
CallGraphSCCPass.h
Callee
amdgpu Simplify well known AMD library false FunctionCallee Callee
Definition: AMDGPULibCalls.cpp:186
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:2122
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:1461
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:4727
CallGraphUpdater.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:63
llvm::SetVector< Function * >
InitializePasses.h
SetVector.h
llvm::Function::iterator
BasicBlockListType::iterator iterator
Definition: Function.h:66
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:38