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
15 #include "llvm/Transforms/Utils/CallGraphUpdater.h"
16 #include "llvm/ADT/STLExtras.h"
17 #include "llvm/Transforms/Utils/ModuleUtils.h"
18
19 using namespace llvm;
20
finalize()21 bool CallGraphUpdater::finalize() {
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();
36 CG->getExternalCallingNode()->removeAnyCallEdgeTo(DeadCGN);
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
62 FunctionAnalysisManager &FAM =
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
reanalyzeFunction(Function & Fn)87 void CallGraphUpdater::reanalyzeFunction(Function &Fn) {
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
registerOutlinedFunction(Function & OriginalFn,Function & NewFn)99 void CallGraphUpdater::registerOutlinedFunction(Function &OriginalFn,
100 Function &NewFn) {
101 if (CG)
102 CG->addToCallGraph(&NewFn);
103 else if (LCG)
104 LCG->addSplitFunction(OriginalFn, NewFn);
105 }
106
removeFunction(Function & DeadFn)107 void CallGraphUpdater::removeFunction(Function &DeadFn) {
108 DeadFn.deleteBody();
109 DeadFn.setLinkage(GlobalValue::ExternalLinkage);
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
replaceFunctionWith(Function & OldFn,Function & NewFn)123 void CallGraphUpdater::replaceFunctionWith(Function &OldFn, Function &NewFn) {
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
replaceCallSite(CallBase & OldCS,CallBase & NewCS)143 bool CallGraphUpdater::replaceCallSite(CallBase &OldCS, CallBase &NewCS) {
144 // This is only necessary in the (old) CG.
145 if (!CG)
146 return true;
147
148 Function *Caller = OldCS.getCaller();
149 CallGraphNode *NewCalleeNode =
150 CG->getOrInsertFunction(NewCS.getCalledFunction());
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
removeCallSite(CallBase & CS)160 void CallGraphUpdater::removeCallSite(CallBase &CS) {
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 }
169