LLVM  12.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"
18 
19 using namespace llvm;
20 
22  if (!DeadFunctionsInComdats.empty()) {
23  filterDeadComdatFunctions(*DeadFunctionsInComdats.front()->getParent(),
24  DeadFunctionsInComdats);
25  DeadFunctions.append(DeadFunctionsInComdats.begin(),
26  DeadFunctionsInComdats.end());
27  }
28 
29  if (CG) {
30  // First remove all references, e.g., outgoing via called functions. This is
31  // necessary as we can delete functions that have circular references.
32  for (Function *DeadFn : DeadFunctions) {
33  DeadFn->removeDeadConstantUsers();
34  CallGraphNode *DeadCGN = (*CG)[DeadFn];
35  DeadCGN->removeAllCalledFunctions();
37  DeadFn->replaceAllUsesWith(UndefValue::get(DeadFn->getType()));
38  }
39 
40  // Then remove the node and function from the module.
41  for (Function *DeadFn : DeadFunctions) {
42  CallGraphNode *DeadCGN = CG->getOrInsertFunction(DeadFn);
43  assert(DeadCGN->getNumReferences() == 0 &&
44  "References should have been handled by now");
45  delete CG->removeFunctionFromModule(DeadCGN);
46  }
47  } else {
48  // This is the code path for the new lazy call graph and for the case were
49  // no call graph was provided.
50  for (Function *DeadFn : DeadFunctions) {
51  DeadFn->removeDeadConstantUsers();
52  DeadFn->replaceAllUsesWith(UndefValue::get(DeadFn->getType()));
53 
54  if (LCG && !ReplacedFunctions.count(DeadFn)) {
55  // Taken mostly from the inliner:
56  LazyCallGraph::Node &N = LCG->get(*DeadFn);
57  auto *DeadSCC = LCG->lookupSCC(N);
58  assert(DeadSCC && DeadSCC->size() == 1 &&
59  &DeadSCC->begin()->getFunction() == DeadFn);
60  auto &DeadRC = DeadSCC->getOuterRefSCC();
61 
63  AM->getResult<FunctionAnalysisManagerCGSCCProxy>(*DeadSCC, *LCG)
64  .getManager();
65 
66  FAM.clear(*DeadFn, DeadFn->getName());
67  AM->clear(*DeadSCC, DeadSCC->getName());
68  LCG->removeDeadFunction(*DeadFn);
69 
70  // Mark the relevant parts of the call graph as invalid so we don't
71  // visit them.
72  UR->InvalidatedSCCs.insert(DeadSCC);
73  UR->InvalidatedRefSCCs.insert(&DeadRC);
74  }
75 
76  // The function is now really dead and de-attached from everything.
77  DeadFn->eraseFromParent();
78  }
79  }
80 
81  bool Changed = !DeadFunctions.empty();
82  DeadFunctionsInComdats.clear();
83  DeadFunctions.clear();
84  return Changed;
85 }
86 
88  if (CG) {
89  CallGraphNode *OldCGN = CG->getOrInsertFunction(&Fn);
90  OldCGN->removeAllCalledFunctions();
91  CG->populateCallGraphNode(OldCGN);
92  } else if (LCG) {
93  LazyCallGraph::Node &N = LCG->get(Fn);
94  LazyCallGraph::SCC *C = LCG->lookupSCC(N);
95  updateCGAndAnalysisManagerForCGSCCPass(*LCG, *C, N, *AM, *UR, *FAM);
96  }
97 }
98 
100  if (CG)
101  CG->addToCallGraph(&NewFn);
102  else if (LCG)
103  LCG->addNewFunctionIntoSCC(NewFn, *SCC);
104 }
105 
107  DeadFn.deleteBody();
109  if (DeadFn.hasComdat())
110  DeadFunctionsInComdats.push_back(&DeadFn);
111  else
112  DeadFunctions.push_back(&DeadFn);
113 
114  // For the old call graph we remove the function from the SCC right away.
115  if (CG && !ReplacedFunctions.count(&DeadFn)) {
116  CallGraphNode *DeadCGN = (*CG)[&DeadFn];
117  DeadCGN->removeAllCalledFunctions();
118  CGSCC->DeleteNode(DeadCGN);
119  }
120 }
121 
123  OldFn.removeDeadConstantUsers();
124  ReplacedFunctions.insert(&OldFn);
125  if (CG) {
126  // Update the call graph for the newly promoted function.
127  CallGraphNode *OldCGN = (*CG)[&OldFn];
128  CallGraphNode *NewCGN = CG->getOrInsertFunction(&NewFn);
129  NewCGN->stealCalledFunctionsFrom(OldCGN);
130  CG->ReplaceExternalCallEdge(OldCGN, NewCGN);
131 
132  // And update the SCC we're iterating as well.
133  CGSCC->ReplaceNode(OldCGN, NewCGN);
134  } else if (LCG) {
135  // Directly substitute the functions in the call graph.
136  LazyCallGraph::Node &OldLCGN = LCG->get(OldFn);
137  SCC->getOuterRefSCC().replaceNodeFunction(OldLCGN, NewFn);
138  }
139  removeFunction(OldFn);
140 }
141 
143  // This is only necessary in the (old) CG.
144  if (!CG)
145  return true;
146 
147  Function *Caller = OldCS.getCaller();
148  CallGraphNode *NewCalleeNode =
150  CallGraphNode *CallerNode = (*CG)[Caller];
151  if (llvm::none_of(*CallerNode, [&OldCS](const CallGraphNode::CallRecord &CR) {
152  return CR.first && *CR.first == &OldCS;
153  }))
154  return false;
155  CallerNode->replaceCallEdge(OldCS, NewCS, NewCalleeNode);
156  return true;
157 }
158 
160  // This is only necessary in the (old) CG.
161  if (!CG)
162  return;
163 
164  Function *Caller = CS.getCaller();
165  CallGraphNode *CallerNode = (*CG)[Caller];
166  CallerNode->removeCallEdgeFor(CS);
167 }
uint64_t CallInst * C
void registerOutlinedFunction(Function &NewFn)
If a new function was created by outlining, this method can be called to update the call graph for th...
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:769
This class represents lattice values for constants.
Definition: AllocatorList.h:23
Function * getCaller()
Helper to get the caller (the parent function).
void clear(IRUnitT &IR, llvm::StringRef Name)
Clear any cached analysis results for a single unit of IR.
SCC * lookupSCC(Node &N) const
Lookup a function&#39;s SCC in the graph.
Externally visible function.
Definition: GlobalValue.h:48
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1100
A proxy from a FunctionAnalysisManager to an SCC.
Node & get(Function &F)
Get a graph node for a given function, scanning it to populate the graph data as necessary.
A node in the call graph for a module.
Definition: CallGraph.h:174
unsigned getNumReferences() const
Returns the number of other CallGraphNodes in this CallGraph that reference this node in their callee...
Definition: CallGraph.h:216
RefSCC & getOuterRefSCC() const
void removeCallSite(CallBase &CS)
Remove the call site CS from the call graph.
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:1505
Function * removeFunctionFromModule(CallGraphNode *CGN)
Unlink the function from this module, returning it.
Definition: CallGraph.cpp:160
void replaceFunctionWith(Function &OldFn, Function &NewFn)
Replace OldFn in the call graph (and SCC) with NewFn.
This file provides interfaces used to manipulate a call graph, regardless if it is a "old style" Call...
void replaceNodeFunction(Node &N, Function &NewF)
Directly replace a node&#39;s function with a new function.
void removeDeadConstantUsers() const
If there are any dead constant users dangling off of this constant, remove them.
Definition: Constants.cpp:681
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
void removeAnyCallEdgeTo(CallGraphNode *Callee)
Removes all call edges from this node to the specified callee function.
Definition: CallGraph.cpp:246
void reanalyzeFunction(Function &Fn)
After an CGSCC pass changes a function in ways that affect the call graph, this method can be called ...
void deleteBody()
deleteBody - This method deletes the body of the function, and converts the linkage to external...
Definition: Function.h:658
void stealCalledFunctionsFrom(CallGraphNode *N)
Moves all the callee information from N to this node.
Definition: CallGraph.h:243
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.
SmallPtrSetImpl< LazyCallGraph::RefSCC * > & InvalidatedRefSCCs
The set of invalidated RefSCCs which should be skipped if they are found in RCWorklist.
SmallPtrSetImpl< LazyCallGraph::SCC * > & InvalidatedSCCs
The set of invalidated SCCs which should be skipped if they are found in CWorklist.
void DeleteNode(CallGraphNode *Old)
DeleteNode - This informs the SCC and the pass manager that the specified Old node has been deleted...
void removeCallEdgeFor(CallBase &Call)
Removes the edge in the node for the specified call site.
Definition: CallGraph.cpp:226
void populateCallGraphNode(CallGraphNode *CGN)
Populate CGN based on the calls inside the associated function.
Definition: CallGraph.cpp:89
A node in the call graph.
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:186
static UndefValue * get(Type *T)
Static factory methods - Return an &#39;undef&#39; object of the specified type.
Definition: Constants.cpp:1665
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:77
void removeDeadFunction(Function &F)
Remove a dead function from the call graph (typically to delete it).
void setLinkage(LinkageTypes LT)
Definition: GlobalValue.h:454
bool hasComdat() const
Definition: GlobalObject.h:125
void filterDeadComdatFunctions(Module &M, SmallVectorImpl< Function *> &DeadComdatFunctions)
Filter out potentially dead comdat functions where other entries keep the entire comdat group alive...
bool replaceCallSite(CallBase &OldCS, CallBase &NewCS)
Replace OldCS with the new call site NewCS.
void removeAllCalledFunctions()
Removes all edges from this CallGraphNode to any functions it calls.
Definition: CallGraph.h:235
void ReplaceNode(CallGraphNode *Old, CallGraphNode *New)
ReplaceNode - This informs the SCC and the pass manager that the specified Old node has been deleted...
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:274
Function * getCalledFunction() const
Returns the function called, or null if this is an indirect function invocation.
Definition: InstrTypes.h:1314
#define N
void removeFunction(Function &Fn)
Remove Fn from the call graph.
CallGraphNode * getExternalCallingNode() const
Returns the CallGraphNode which is used to represent undetermined calls into the callgraph.
Definition: CallGraph.h:135
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
An SCC of the call graph.
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:187
A container for analyses that lazily runs them and caches their results.
void addNewFunctionIntoSCC(Function &NewF, SCC &C)
Introduce a node for the function NewF in the SCC C.