LLVM  15.0.0git
CallGraphUpdater.cpp
Go to the documentation of this file.
1 //===- CallGraphUpdater.cpp - A (lazy) call graph update helper -----------===//
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 /// \file
9 ///
10 /// This file provides interfaces used to manipulate a call graph, regardless
11 /// if it is a "old style" CallGraph or an "new style" LazyCallGraph.
12 ///
13 //===----------------------------------------------------------------------===//
14 
16 #include "llvm/ADT/STLExtras.h"
19 #include "llvm/IR/Constants.h"
21 
22 using namespace llvm;
23 
25  if (!DeadFunctionsInComdats.empty()) {
26  filterDeadComdatFunctions(DeadFunctionsInComdats);
27  DeadFunctions.append(DeadFunctionsInComdats.begin(),
28  DeadFunctionsInComdats.end());
29  }
30 
31  if (CG) {
32  // First remove all references, e.g., outgoing via called functions. This is
33  // necessary as we can delete functions that have circular references.
34  for (Function *DeadFn : DeadFunctions) {
35  DeadFn->removeDeadConstantUsers();
36  CallGraphNode *DeadCGN = (*CG)[DeadFn];
37  DeadCGN->removeAllCalledFunctions();
39  DeadFn->replaceAllUsesWith(UndefValue::get(DeadFn->getType()));
40  }
41 
42  // Then remove the node and function from the module.
43  for (Function *DeadFn : DeadFunctions) {
44  CallGraphNode *DeadCGN = CG->getOrInsertFunction(DeadFn);
45  assert(DeadCGN->getNumReferences() == 0 &&
46  "References should have been handled by now");
47  delete CG->removeFunctionFromModule(DeadCGN);
48  }
49  } else {
50  // This is the code path for the new lazy call graph and for the case were
51  // no call graph was provided.
52  for (Function *DeadFn : DeadFunctions) {
53  DeadFn->removeDeadConstantUsers();
54  DeadFn->replaceAllUsesWith(UndefValue::get(DeadFn->getType()));
55 
56  if (LCG && !ReplacedFunctions.count(DeadFn)) {
57  // Taken mostly from the inliner:
58  LazyCallGraph::Node &N = LCG->get(*DeadFn);
59  auto *DeadSCC = LCG->lookupSCC(N);
60  assert(DeadSCC && DeadSCC->size() == 1 &&
61  &DeadSCC->begin()->getFunction() == DeadFn);
62  auto &DeadRC = DeadSCC->getOuterRefSCC();
63 
65  AM->getResult<FunctionAnalysisManagerCGSCCProxy>(*DeadSCC, *LCG)
66  .getManager();
67 
68  FAM.clear(*DeadFn, DeadFn->getName());
69  AM->clear(*DeadSCC, DeadSCC->getName());
70  LCG->removeDeadFunction(*DeadFn);
71 
72  // Mark the relevant parts of the call graph as invalid so we don't
73  // visit them.
74  UR->InvalidatedSCCs.insert(DeadSCC);
75  UR->InvalidatedRefSCCs.insert(&DeadRC);
76  }
77 
78  // The function is now really dead and de-attached from everything.
79  DeadFn->eraseFromParent();
80  }
81  }
82 
83  bool Changed = !DeadFunctions.empty();
84  DeadFunctionsInComdats.clear();
85  DeadFunctions.clear();
86  return Changed;
87 }
88 
90  if (CG) {
91  CallGraphNode *OldCGN = CG->getOrInsertFunction(&Fn);
92  OldCGN->removeAllCalledFunctions();
93  CG->populateCallGraphNode(OldCGN);
94  } else if (LCG) {
95  LazyCallGraph::Node &N = LCG->get(Fn);
97  updateCGAndAnalysisManagerForCGSCCPass(*LCG, *C, N, *AM, *UR, *FAM);
98  }
99 }
100 
102  Function &NewFn) {
103  if (CG)
104  CG->addToCallGraph(&NewFn);
105  else if (LCG)
106  LCG->addSplitFunction(OriginalFn, NewFn);
107 }
108 
110  DeadFn.deleteBody();
112  if (DeadFn.hasComdat())
113  DeadFunctionsInComdats.push_back(&DeadFn);
114  else
115  DeadFunctions.push_back(&DeadFn);
116 
117  // For the old call graph we remove the function from the SCC right away.
118  if (CG && !ReplacedFunctions.count(&DeadFn)) {
119  CallGraphNode *DeadCGN = (*CG)[&DeadFn];
120  DeadCGN->removeAllCalledFunctions();
121  CGSCC->DeleteNode(DeadCGN);
122  }
123 }
124 
126  OldFn.removeDeadConstantUsers();
127  ReplacedFunctions.insert(&OldFn);
128  if (CG) {
129  // Update the call graph for the newly promoted function.
130  CallGraphNode *OldCGN = (*CG)[&OldFn];
131  CallGraphNode *NewCGN = CG->getOrInsertFunction(&NewFn);
132  NewCGN->stealCalledFunctionsFrom(OldCGN);
133  CG->ReplaceExternalCallEdge(OldCGN, NewCGN);
134 
135  // And update the SCC we're iterating as well.
136  CGSCC->ReplaceNode(OldCGN, NewCGN);
137  } else if (LCG) {
138  // Directly substitute the functions in the call graph.
139  LazyCallGraph::Node &OldLCGN = LCG->get(OldFn);
140  SCC->getOuterRefSCC().replaceNodeFunction(OldLCGN, NewFn);
141  }
142  removeFunction(OldFn);
143 }
144 
146  // This is only necessary in the (old) CG.
147  if (!CG)
148  return true;
149 
150  Function *Caller = OldCS.getCaller();
151  CallGraphNode *NewCalleeNode =
153  CallGraphNode *CallerNode = (*CG)[Caller];
154  if (llvm::none_of(*CallerNode, [&OldCS](const CallGraphNode::CallRecord &CR) {
155  return CR.first && *CR.first == &OldCS;
156  }))
157  return false;
158  CallerNode->replaceCallEdge(OldCS, NewCS, NewCalleeNode);
159  return true;
160 }
161 
163  // This is only necessary in the (old) CG.
164  if (!CG)
165  return;
166 
167  Function *Caller = CS.getCaller();
168  CallGraphNode *CallerNode = (*CG)[Caller];
169  CallerNode->removeCallEdgeFor(CS);
170 }
llvm::CallGraphNode::removeAnyCallEdgeTo
void removeAnyCallEdgeTo(CallGraphNode *Callee)
Removes all call edges from this node to the specified callee function.
Definition: CallGraph.cpp:232
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
llvm::none_of
bool none_of(R &&Range, UnaryPredicate P)
Provide wrappers to std::none_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1631
llvm::CallGraph::getExternalCallingNode
CallGraphNode * getExternalCallingNode() const
Returns the CallGraphNode which is used to represent undetermined calls into the callgraph.
Definition: CallGraph.h:127
llvm::CGSCCUpdateResult::InvalidatedSCCs
SmallPtrSetImpl< LazyCallGraph::SCC * > & InvalidatedSCCs
The set of invalidated SCCs which should be skipped if they are found in CWorklist.
Definition: CGSCCPassManager.h:273
llvm::AnalysisManager::getResult
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:780
llvm::Function
Definition: Function.h:60
llvm::CallGraphUpdater::replaceCallSite
bool replaceCallSite(CallBase &OldCS, CallBase &NewCS)
Replace OldCS with the new call site NewCS.
Definition: CallGraphUpdater.cpp:145
llvm::CallGraphNode::CallRecord
std::pair< Optional< WeakTrackingVH >, CallGraphNode * > CallRecord
A pair of the calling instruction (a call or invoke) and the call graph node being called.
Definition: CallGraph.h:178
llvm::CallGraphNode::removeCallEdgeFor
void removeCallEdgeFor(CallBase &Call)
Removes the edge in the node for the specified call site.
Definition: CallGraph.cpp:212
llvm::LazyCallGraph::removeDeadFunction
void removeDeadFunction(Function &F)
Remove a dead function from the call graph (typically to delete it).
Definition: LazyCallGraph.cpp:1505
FAM
FunctionAnalysisManager FAM
Definition: PassBuilderBindings.cpp:59
STLExtras.h
llvm::CallGraphUpdater::finalize
bool finalize()
}
Definition: CallGraphUpdater.cpp:24
llvm::CallGraph::getOrInsertFunction
CallGraphNode * getOrInsertFunction(const Function *F)
Similar to operator[], but this will insert a new CallGraphNode for F if one does not already exist.
Definition: CallGraph.cpp:173
llvm::LazyCallGraph::SCC
An SCC of the call graph.
Definition: LazyCallGraph.h:419
llvm::CallGraphNode::getNumReferences
unsigned getNumReferences() const
Returns the number of other CallGraphNodes in this CallGraph that reference this node in their callee...
Definition: CallGraph.h:208
Constants.h
llvm::CallGraphUpdater::removeCallSite
void removeCallSite(CallBase &CS)
Remove the call site CS from the call graph.
Definition: CallGraphUpdater.cpp:162
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
llvm::CallBase::getCalledFunction
Function * getCalledFunction() const
Returns the function called, or null if this is an indirect function invocation or the function signa...
Definition: InstrTypes.h:1396
llvm::AnalysisManager::clear
void clear(IRUnitT &IR, llvm::StringRef Name)
Clear any cached analysis results for a single unit of IR.
Definition: PassManagerImpl.h:36
llvm::CallGraphSCC::ReplaceNode
void ReplaceNode(CallGraphNode *Old, CallGraphNode *New)
ReplaceNode - This informs the SCC and the pass manager that the specified Old node has been deleted,...
Definition: CallGraphSCCPass.cpp:592
llvm::UndefValue::get
static UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
Definition: Constants.cpp:1768
llvm::CallGraphNode
A node in the call graph for a module.
Definition: CallGraph.h:166
llvm::LazyCallGraph::lookupSCC
SCC * lookupSCC(Node &N) const
Lookup a function's SCC in the graph.
Definition: LazyCallGraph.h:971
llvm::CallBase::getCaller
Function * getCaller()
Helper to get the caller (the parent function).
Definition: Instructions.cpp:282
llvm::CallGraph::ReplaceExternalCallEdge
void ReplaceExternalCallEdge(CallGraphNode *Old, CallGraphNode *New)
Old node has been deleted, and New is to be used in its place, update the ExternalCallingNode.
Definition: CallGraph.cpp:144
llvm::LazyCallGraph::get
Node & get(Function &F)
Get a graph node for a given function, scanning it to populate the graph data as necessary.
Definition: LazyCallGraph.h:986
llvm::CallGraph::populateCallGraphNode
void populateCallGraphNode(CallGraphNode *CGN)
Populate CGN based on the calls inside the associated function.
Definition: CallGraph.cpp:89
llvm::CallGraphNode::removeAllCalledFunctions
void removeAllCalledFunctions()
Removes all edges from this CallGraphNode to any functions it calls.
Definition: CallGraph.h:227
llvm::LazyCallGraph::addSplitFunction
void addSplitFunction(Function &OriginalFunction, Function &NewFunction)
Add a new function split/outlined from an existing function.
Definition: LazyCallGraph.cpp:1600
llvm::CallGraphSCC::DeleteNode
void DeleteNode(CallGraphNode *Old)
DeleteNode - This informs the SCC and the pass manager that the specified Old node has been deleted.
Definition: CallGraphSCCPass.cpp:610
llvm::filterDeadComdatFunctions
void filterDeadComdatFunctions(SmallVectorImpl< Function * > &DeadComdatFunctions)
Filter out potentially dead comdat functions where other entries keep the entire comdat group alive.
Definition: ModuleUtils.cpp:179
llvm::GlobalValue::setLinkage
void setLinkage(LinkageTypes LT)
Definition: GlobalValue.h:502
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::CallGraph::removeFunctionFromModule
Function * removeFunctionFromModule(CallGraphNode *CGN)
Unlink the function from this module, returning it.
Definition: CallGraph.cpp:160
llvm::CallGraphUpdater::registerOutlinedFunction
void registerOutlinedFunction(Function &OriginalFn, Function &NewFn)
If a new function was created by outlining, this method can be called to update the call graph for th...
Definition: CallGraphUpdater.cpp:101
llvm::LazyCallGraph::Node
A node in the call graph.
Definition: LazyCallGraph.h:315
llvm::GlobalObject::hasComdat
bool hasComdat() const
Definition: GlobalObject.h:121
llvm::Constant::removeDeadConstantUsers
void removeDeadConstantUsers() const
If there are any dead constant users dangling off of this constant, remove them.
Definition: Constants.cpp:749
llvm::CallGraph::addToCallGraph
void addToCallGraph(Function *F)
Add a function to the call graph, and link the node to all of the functions that it calls.
Definition: CallGraph.cpp:75
llvm::LazyCallGraph::RefSCC::replaceNodeFunction
void replaceNodeFunction(Node &N, Function &NewF)
Directly replace a node's function with a new function.
Definition: LazyCallGraph.cpp:1459
CallGraphSCCPass.h
llvm::CallGraphUpdater::replaceFunctionWith
void replaceFunctionWith(Function &OldFn, Function &NewFn)
Replace OldFn in the call graph (and SCC) with NewFn.
Definition: CallGraphUpdater.cpp:125
llvm::updateCGAndAnalysisManagerForCGSCCPass
LazyCallGraph::SCC & updateCGAndAnalysisManagerForCGSCCPass(LazyCallGraph &G, LazyCallGraph::SCC &C, LazyCallGraph::Node &N, CGSCCAnalysisManager &AM, CGSCCUpdateResult &UR, FunctionAnalysisManager &FAM)
Helper to update the call graph after running a CGSCC pass.
Definition: CGSCCPassManager.cpp:1230
llvm::Function::deleteBody
void deleteBody()
deleteBody - This method deletes the body of the function, and converts the linkage to external.
Definition: Function.h:679
llvm::GlobalValue::ExternalLinkage
@ ExternalLinkage
Externally visible function.
Definition: GlobalValue.h:48
CallGraph.h
llvm::CallGraphUpdater::removeFunction
void removeFunction(Function &Fn)
Remove Fn from the call graph.
Definition: CallGraphUpdater.cpp:109
ModuleUtils.h
N
#define N
llvm::LazyCallGraph::SCC::getOuterRefSCC
RefSCC & getOuterRefSCC() const
Definition: LazyCallGraph.h:482
llvm::CallBase
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1174
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:42
CallGraphUpdater.h
llvm::CallGraphUpdater::reanalyzeFunction
void reanalyzeFunction(Function &Fn)
After an CGSCC pass changes a function in ways that affect the call graph, this method can be called ...
Definition: CallGraphUpdater.cpp:89
llvm::FunctionAnalysisManagerCGSCCProxy
A proxy from a FunctionAnalysisManager to an SCC.
Definition: CGSCCPassManager.h:392
llvm::CGSCCUpdateResult::InvalidatedRefSCCs
SmallPtrSetImpl< LazyCallGraph::RefSCC * > & InvalidatedRefSCCs
The set of invalidated RefSCCs which should be skipped if they are found in RCWorklist.
Definition: CGSCCPassManager.h:265
llvm::CallGraphNode::stealCalledFunctionsFrom
void stealCalledFunctionsFrom(CallGraphNode *N)
Moves all the callee information from N to this node.
Definition: CallGraph.h:235
llvm::CallGraphNode::replaceCallEdge
void replaceCallEdge(CallBase &Call, CallBase &NewCall, CallGraphNode *NewNode)
Replaces the edge in the node for the specified call site with a new one.
Definition: CallGraph.cpp:260