LLVM  13.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);
95  updateCGAndAnalysisManagerForCGSCCPass(*LCG, *C, N, *AM, *UR, *FAM);
96  }
97 }
98 
100  Function &NewFn) {
101  if (CG)
102  CG->addToCallGraph(&NewFn);
103  else if (LCG)
104  LCG->addSplitFunction(OriginalFn, NewFn);
105 }
106 
108  DeadFn.deleteBody();
110  if (DeadFn.hasComdat())
111  DeadFunctionsInComdats.push_back(&DeadFn);
112  else
113  DeadFunctions.push_back(&DeadFn);
114 
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 }
122 
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);
132 
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 }
142 
144  // This is only necessary in the (old) CG.
145  if (!CG)
146  return true;
147 
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 }
159 
161  // This is only necessary in the (old) CG.
162  if (!CG)
163  return;
164 
165  Function *Caller = CS.getCaller();
166  CallGraphNode *CallerNode = (*CG)[Caller];
167  CallerNode->removeCallEdgeFor(CS);
168 }
llvm::CallGraphNode::removeAnyCallEdgeTo
void removeAnyCallEdgeTo(CallGraphNode *Callee)
Removes all call edges from this node to the specified callee function.
Definition: CallGraph.cpp:234
llvm
This class represents lattice values for constants.
Definition: AllocatorList.h:23
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:1512
llvm::CallGraph::getExternalCallingNode
CallGraphNode * getExternalCallingNode() const
Returns the CallGraphNode which is used to represent undetermined calls into the callgraph.
Definition: CallGraph.h:128
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::filterDeadComdatFunctions
void filterDeadComdatFunctions(Module &M, SmallVectorImpl< Function * > &DeadComdatFunctions)
Filter out potentially dead comdat functions where other entries keep the entire comdat group alive.
Definition: ModuleUtils.cpp:199
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:785
llvm::Function
Definition: Function.h:61
llvm::CallGraphUpdater::replaceCallSite
bool replaceCallSite(CallBase &OldCS, CallBase &NewCS)
Replace OldCS with the new call site NewCS.
Definition: CallGraphUpdater.cpp:143
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:179
llvm::CallGraphNode::removeCallEdgeFor
void removeCallEdgeFor(CallBase &Call)
Removes the edge in the node for the specified call site.
Definition: CallGraph.cpp:214
llvm::LazyCallGraph::removeDeadFunction
void removeDeadFunction(Function &F)
Remove a dead function from the call graph (typically to delete it).
Definition: LazyCallGraph.cpp:1504
STLExtras.h
llvm::CallGraphUpdater::finalize
bool finalize()
}
Definition: CallGraphUpdater.cpp:21
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:175
llvm::LazyCallGraph::SCC
An SCC of the call graph.
Definition: LazyCallGraph.h:421
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:209
llvm::CallGraphUpdater::removeCallSite
void removeCallSite(CallBase &CS)
Remove the call site CS from the call graph.
Definition: CallGraphUpdater.cpp:160
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.
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:38
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:591
llvm::UndefValue::get
static UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
Definition: Constants.cpp:1751
llvm::CallGraphNode
A node in the call graph for a module.
Definition: CallGraph.h:167
llvm::LazyCallGraph::lookupSCC
SCC * lookupSCC(Node &N) const
Lookup a function's SCC in the graph.
Definition: LazyCallGraph.h:959
llvm::CallBase::getCaller
Function * getCaller()
Helper to get the caller (the parent function).
Definition: Instructions.cpp:278
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:146
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:974
llvm::CallGraph::populateCallGraphNode
void populateCallGraphNode(CallGraphNode *CGN)
Populate CGN based on the calls inside the associated function.
Definition: CallGraph.cpp:91
llvm::CallGraphNode::removeAllCalledFunctions
void removeAllCalledFunctions()
Removes all edges from this CallGraphNode to any functions it calls.
Definition: CallGraph.h:228
llvm::LazyCallGraph::addSplitFunction
void addSplitFunction(Function &OriginalFunction, Function &NewFunction)
Add a new function split/outlined from an existing function.
Definition: LazyCallGraph.cpp:1612
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:609
llvm::GlobalValue::setLinkage
void setLinkage(LinkageTypes LT)
Definition: GlobalValue.h:454
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:162
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:99
llvm::LazyCallGraph::Node
A node in the call graph.
Definition: LazyCallGraph.h:317
llvm::GlobalObject::hasComdat
bool hasComdat() const
Definition: GlobalObject.h:124
llvm::Constant::removeDeadConstantUsers
void removeDeadConstantUsers() const
If there are any dead constant users dangling off of this constant, remove them.
Definition: Constants.cpp:729
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:77
llvm::LazyCallGraph::RefSCC::replaceNodeFunction
void replaceNodeFunction(Node &N, Function &NewF)
Directly replace a node's function with a new function.
Definition: LazyCallGraph.cpp:1458
llvm::CallGraphUpdater::replaceFunctionWith
void replaceFunctionWith(Function &OldFn, Function &NewFn)
Replace OldFn in the call graph (and SCC) with NewFn.
Definition: CallGraphUpdater.cpp:123
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:1234
llvm::Function::deleteBody
void deleteBody()
deleteBody - This method deletes the body of the function, and converts the linkage to external.
Definition: Function.h:700
llvm::GlobalValue::ExternalLinkage
@ ExternalLinkage
Externally visible function.
Definition: GlobalValue.h:48
llvm::CallGraphUpdater::removeFunction
void removeFunction(Function &Fn)
Remove Fn from the call graph.
Definition: CallGraphUpdater.cpp:107
ModuleUtils.h
N
#define N
llvm::LazyCallGraph::SCC::getOuterRefSCC
RefSCC & getOuterRefSCC() const
Definition: LazyCallGraph.h:483
llvm::CallBase
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1164
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:43
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:87
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:236
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:262