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/Analysis/CallGraph.h"
18 #include "llvm/Analysis/CallGraphSCCPass.h"
19 #include "llvm/IR/Constants.h"
20 #include "llvm/Transforms/Utils/ModuleUtils.h"
21
22 using namespace llvm;
23
finalize()24 bool CallGraphUpdater::finalize() {
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();
38 CG->getExternalCallingNode()->removeAnyCallEdgeTo(DeadCGN);
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) {
53 DeadFn->removeDeadConstantUsers();
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
64 FunctionAnalysisManager &FAM =
65 AM->getResult<FunctionAnalysisManagerCGSCCProxy>(*DeadSCC, *LCG)
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
reanalyzeFunction(Function & Fn)89 void CallGraphUpdater::reanalyzeFunction(Function &Fn) {
90 if (CG) {
91 CallGraphNode *OldCGN = CG->getOrInsertFunction(&Fn);
92 OldCGN->removeAllCalledFunctions();
93 CG->populateCallGraphNode(OldCGN);
94 } else if (LCG) {
95 LazyCallGraph::Node &N = LCG->get(Fn);
96 LazyCallGraph::SCC *C = LCG->lookupSCC(N);
97 updateCGAndAnalysisManagerForCGSCCPass(*LCG, *C, N, *AM, *UR, *FAM);
98 }
99 }
100
registerOutlinedFunction(Function & OriginalFn,Function & NewFn)101 void CallGraphUpdater::registerOutlinedFunction(Function &OriginalFn,
102 Function &NewFn) {
103 if (CG)
104 CG->addToCallGraph(&NewFn);
105 else if (LCG)
106 LCG->addSplitFunction(OriginalFn, NewFn);
107 }
108
removeFunction(Function & DeadFn)109 void CallGraphUpdater::removeFunction(Function &DeadFn) {
110 DeadFn.deleteBody();
111 DeadFn.setLinkage(GlobalValue::ExternalLinkage);
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 }
124
replaceFunctionWith(Function & OldFn,Function & NewFn)125 void CallGraphUpdater::replaceFunctionWith(Function &OldFn, Function &NewFn) {
126 OldFn.removeDeadConstantUsers();
127 ReplacedFunctions.insert(&OldFn);
128 if (CG) {
129 // Update the call graph for the newly promoted function.
130 CallGraphNode *OldCGN = (*CG)[&OldFn];
131 CallGraphNode *NewCGN = CG->getOrInsertFunction(&NewFn);
132 NewCGN->stealCalledFunctionsFrom(OldCGN);
133 CG->ReplaceExternalCallEdge(OldCGN, NewCGN);
134
135 // And update the SCC we're iterating as well.
136 CGSCC->ReplaceNode(OldCGN, NewCGN);
137 } else if (LCG) {
138 // Directly substitute the functions in the call graph.
139 LazyCallGraph::Node &OldLCGN = LCG->get(OldFn);
140 SCC->getOuterRefSCC().replaceNodeFunction(OldLCGN, NewFn);
141 }
142 removeFunction(OldFn);
143 }
144
replaceCallSite(CallBase & OldCS,CallBase & NewCS)145 bool CallGraphUpdater::replaceCallSite(CallBase &OldCS, CallBase &NewCS) {
146 // This is only necessary in the (old) CG.
147 if (!CG)
148 return true;
149
150 Function *Caller = OldCS.getCaller();
151 CallGraphNode *NewCalleeNode =
152 CG->getOrInsertFunction(NewCS.getCalledFunction());
153 CallGraphNode *CallerNode = (*CG)[Caller];
154 if (llvm::none_of(*CallerNode, [&OldCS](const CallGraphNode::CallRecord &CR) {
155 return CR.first && *CR.first == &OldCS;
156 }))
157 return false;
158 CallerNode->replaceCallEdge(OldCS, NewCS, NewCalleeNode);
159 return true;
160 }
161
removeCallSite(CallBase & CS)162 void CallGraphUpdater::removeCallSite(CallBase &CS) {
163 // This is only necessary in the (old) CG.
164 if (!CG)
165 return;
166
167 Function *Caller = CS.getCaller();
168 CallGraphNode *CallerNode = (*CG)[Caller];
169 CallerNode->removeCallEdgeFor(CS);
170 }
171