LLVM  12.0.0git
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 //===----------------------------------------------------------------------===//
16 #include "llvm/ADT/STLExtras.h"
19 using namespace llvm;
22  if (!DeadFunctionsInComdats.empty()) {
23  filterDeadComdatFunctions(*DeadFunctionsInComdats.front()->getParent(),
24  DeadFunctionsInComdats);
25  DeadFunctions.append(DeadFunctionsInComdats.begin(),
26  DeadFunctionsInComdats.end());
27  }
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  }
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()));
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();
63  AM->getResult<FunctionAnalysisManagerCGSCCProxy>(*DeadSCC, *LCG)
64  .getManager();
66  FAM.clear(*DeadFn, DeadFn->getName());
67  AM->clear(*DeadSCC, DeadSCC->getName());
68  LCG->removeDeadFunction(*DeadFn);
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  }
76  // The function is now really dead and de-attached from everything.
77  DeadFn->eraseFromParent();
78  }
79  }
81  bool Changed = !DeadFunctions.empty();
82  DeadFunctionsInComdats.clear();
83  DeadFunctions.clear();
84  return Changed;
85 }
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);
95  updateCGAndAnalysisManagerForCGSCCPass(*LCG, *C, N, *AM, *UR, *FAM);
96  }
97 }
100  Function &NewFn) {
101  if (CG)
102  CG->addToCallGraph(&NewFn);
103  else if (LCG)
104  LCG->addSplitFunction(OriginalFn, NewFn);
105 }
108  DeadFn.deleteBody();
110  if (DeadFn.hasComdat())
111  DeadFunctionsInComdats.push_back(&DeadFn);
112  else
113  DeadFunctions.push_back(&DeadFn);
115  // For the old call graph we remove the function from the SCC right away.
116  if (CG && !ReplacedFunctions.count(&DeadFn)) {
117  CallGraphNode *DeadCGN = (*CG)[&DeadFn];
118  DeadCGN->removeAllCalledFunctions();
119  CGSCC->DeleteNode(DeadCGN);
120  }
121 }
124  OldFn.removeDeadConstantUsers();
125  ReplacedFunctions.insert(&OldFn);
126  if (CG) {
127  // Update the call graph for the newly promoted function.
128  CallGraphNode *OldCGN = (*CG)[&OldFn];
129  CallGraphNode *NewCGN = CG->getOrInsertFunction(&NewFn);
130  NewCGN->stealCalledFunctionsFrom(OldCGN);
131  CG->ReplaceExternalCallEdge(OldCGN, NewCGN);
133  // And update the SCC we're iterating as well.
134  CGSCC->ReplaceNode(OldCGN, NewCGN);
135  } else if (LCG) {
136  // Directly substitute the functions in the call graph.
137  LazyCallGraph::Node &OldLCGN = LCG->get(OldFn);
138  SCC->getOuterRefSCC().replaceNodeFunction(OldLCGN, NewFn);
139  }
140  removeFunction(OldFn);
141 }
144  // This is only necessary in the (old) CG.
145  if (!CG)
146  return true;
148  Function *Caller = OldCS.getCaller();
149  CallGraphNode *NewCalleeNode =
151  CallGraphNode *CallerNode = (*CG)[Caller];
152  if (llvm::none_of(*CallerNode, [&OldCS](const CallGraphNode::CallRecord &CR) {
153  return CR.first && *CR.first == &OldCS;
154  }))
155  return false;
156  CallerNode->replaceCallEdge(OldCS, NewCS, NewCalleeNode);
157  return true;
158 }
161  // This is only necessary in the (old) CG.
162  if (!CG)
163  return;
165  Function *Caller = CS.getCaller();
166  CallGraphNode *CallerNode = (*CG)[Caller];
167  CallerNode->removeCallEdgeFor(CS);
168 }
uint64_t CallInst * C
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:785
This class represents lattice values for constants.
Definition: AllocatorList.h:23
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...
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'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:1164
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:167
unsigned getNumReferences() const
Returns the number of other CallGraphNodes in this CallGraph that reference this node in their callee...
Definition: CallGraph.h:209
RefSCC & getOuterRefSCC() const
void removeCallSite(CallBase &CS)
Remove the call site CS from the call graph.
void addSplitFunction(Function &OriginalFunction, Function &NewFunction)
Add a new function split/outlined from an existing function.
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:1512
Function * removeFunctionFromModule(CallGraphNode *CGN)
Unlink the function from this module, returning it.
Definition: CallGraph.cpp:160
void filterDeadComdatFunctions(Module &M, SmallVectorImpl< Function * > &DeadComdatFunctions)
Filter out potentially dead comdat functions where other entries keep the entire comdat group alive.
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'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:720
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:232
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:700
void stealCalledFunctionsFrom(CallGraphNode *N)
Moves all the callee information from N to this node.
Definition: CallGraph.h:236
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:212
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:179
static UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
Definition: Constants.cpp:1742
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:124
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:228
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:260
Function * getCalledFunction() const
Returns the function called, or null if this is an indirect function invocation.
Definition: InstrTypes.h:1378
#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:128
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:173
A container for analyses that lazily runs them and caches their results.