LLVM 19.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
22using 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(PoisonValue::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) {
54 DeadFn->replaceAllUsesWith(PoisonValue::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
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);
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 if (FAM)
124 FAM->clear(DeadFn, DeadFn.getName());
125}
126
129 ReplacedFunctions.insert(&OldFn);
130 if (CG) {
131 // Update the call graph for the newly promoted function.
132 CallGraphNode *OldCGN = (*CG)[&OldFn];
133 CallGraphNode *NewCGN = CG->getOrInsertFunction(&NewFn);
134 NewCGN->stealCalledFunctionsFrom(OldCGN);
135 CG->ReplaceExternalCallEdge(OldCGN, NewCGN);
136
137 // And update the SCC we're iterating as well.
138 CGSCC->ReplaceNode(OldCGN, NewCGN);
139 } else if (LCG) {
140 // Directly substitute the functions in the call graph.
141 LazyCallGraph::Node &OldLCGN = LCG->get(OldFn);
142 SCC->getOuterRefSCC().replaceNodeFunction(OldLCGN, NewFn);
143 }
144 removeFunction(OldFn);
145}
146
148 // This is only necessary in the (old) CG.
149 if (!CG)
150 return true;
151
152 Function *Caller = OldCS.getCaller();
153 CallGraphNode *NewCalleeNode =
155 CallGraphNode *CallerNode = (*CG)[Caller];
156 if (llvm::none_of(*CallerNode, [&OldCS](const CallGraphNode::CallRecord &CR) {
157 return CR.first && *CR.first == &OldCS;
158 }))
159 return false;
160 CallerNode->replaceCallEdge(OldCS, NewCS, NewCalleeNode);
161 return true;
162}
163
165 // This is only necessary in the (old) CG.
166 if (!CG)
167 return;
168
169 Function *Caller = CS.getCaller();
170 CallGraphNode *CallerNode = (*CG)[Caller];
171 CallerNode->removeCallEdgeFor(CS);
172}
This file provides interfaces used to manipulate a call graph, regardless if it is a "old style" Call...
This file provides interfaces used to build and manipulate a call graph, which is a very useful tool ...
This file contains the declarations for the subclasses of Constant, which represent the different fla...
FunctionAnalysisManager FAM
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file contains some templates that are useful if you are working with the STL at all.
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:348
void clear(IRUnitT &IR, llvm::StringRef Name)
Clear any cached analysis results for a single unit of IR.
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:500
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1461
Function * getCalledFunction() const
Returns the function called, or null if this is an indirect function invocation or the function signa...
Definition: InstrTypes.h:1709
Function * getCaller()
Helper to get the caller (the parent function).
A node in the call graph for a module.
Definition: CallGraph.h:166
void removeCallEdgeFor(CallBase &Call)
Removes the edge in the node for the specified call site.
Definition: CallGraph.cpp:209
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:257
void stealCalledFunctionsFrom(CallGraphNode *N)
Moves all the callee information from N to this node.
Definition: CallGraph.h:235
void removeAllCalledFunctions()
Removes all edges from this CallGraphNode to any functions it calls.
Definition: CallGraph.h:227
unsigned getNumReferences() const
Returns the number of other CallGraphNodes in this CallGraph that reference this node in their callee...
Definition: CallGraph.h:208
void removeAnyCallEdgeTo(CallGraphNode *Callee)
Removes all call edges from this node to the specified callee function.
Definition: CallGraph.cpp:229
std::pair< std::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
void ReplaceNode(CallGraphNode *Old, CallGraphNode *New)
ReplaceNode - This informs the SCC and the pass manager that the specified Old node has been deleted,...
void DeleteNode(CallGraphNode *Old)
DeleteNode - This informs the SCC and the pass manager that the specified Old node has been deleted.
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...
void removeFunction(Function &Fn)
Remove Fn from the call graph.
void removeCallSite(CallBase &CS)
Remove the call site CS from the call graph.
void replaceFunctionWith(Function &OldFn, Function &NewFn)
Replace OldFn in the call graph (and SCC) with NewFn.
void reanalyzeFunction(Function &Fn)
After an CGSCC pass changes a function in ways that affect the call graph, this method can be called ...
bool replaceCallSite(CallBase &OldCS, CallBase &NewCS)
Replace OldCS with the new call site NewCS.
Function * removeFunctionFromModule(CallGraphNode *CGN)
Unlink the function from this module, returning it.
Definition: CallGraph.cpp:157
void populateCallGraphNode(CallGraphNode *CGN)
Populate CGN based on the calls inside the associated function.
Definition: CallGraph.cpp:89
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
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:170
CallGraphNode * getExternalCallingNode() const
Returns the CallGraphNode which is used to represent undetermined calls into the callgraph.
Definition: CallGraph.h:127
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:141
void removeDeadConstantUsers() const
If there are any dead constant users dangling off of this constant, remove them.
Definition: Constants.cpp:722
A proxy from a FunctionAnalysisManager to an SCC.
void deleteBody()
deleteBody - This method deletes the body of the function, and converts the linkage to external.
Definition: Function.h:704
bool hasComdat() const
Definition: GlobalObject.h:128
void setLinkage(LinkageTypes LT)
Definition: GlobalValue.h:536
@ ExternalLinkage
Externally visible function.
Definition: GlobalValue.h:52
A node in the call graph.
void replaceNodeFunction(Node &N, Function &NewF)
Directly replace a node's function with a new function.
An SCC of the call graph.
RefSCC & getOuterRefSCC() const
void removeDeadFunction(Function &F)
Remove a dead function from the call graph (typically to delete it).
void addSplitFunction(Function &OriginalFunction, Function &NewFunction)
Add a new function split/outlined from an existing function.
Node & get(Function &F)
Get a graph node for a given function, scanning it to populate the graph data as necessary.
SCC * lookupSCC(Node &N) const
Lookup a function's SCC in the graph.
static PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
Definition: Constants.cpp:1827
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:309
@ C
The default llvm calling convention, compatible with C.
Definition: CallingConv.h:34
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
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.
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:1745
void filterDeadComdatFunctions(SmallVectorImpl< Function * > &DeadComdatFunctions)
Filter out potentially dead comdat functions where other entries keep the entire comdat group alive.
#define N
SmallPtrSetImpl< LazyCallGraph::SCC * > & InvalidatedSCCs
The set of invalidated SCCs which should be skipped if they are found in CWorklist.
SmallPtrSetImpl< LazyCallGraph::RefSCC * > & InvalidatedRefSCCs
The set of invalidated RefSCCs which should be skipped if they are found in RCWorklist.