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 & NewFn)99 void CallGraphUpdater::registerOutlinedFunction(Function &NewFn) {
100 if (CG)
101 CG->addToCallGraph(&NewFn);
102 }
103
removeFunction(Function & DeadFn)104 void CallGraphUpdater::removeFunction(Function &DeadFn) {
105 DeadFn.deleteBody();
106 DeadFn.setLinkage(GlobalValue::ExternalLinkage);
107 if (DeadFn.hasComdat())
108 DeadFunctionsInComdats.push_back(&DeadFn);
109 else
110 DeadFunctions.push_back(&DeadFn);
111
112 // For the old call graph we remove the function from the SCC right away.
113 if (CG && !ReplacedFunctions.count(&DeadFn)) {
114 CallGraphNode *DeadCGN = (*CG)[&DeadFn];
115 DeadCGN->removeAllCalledFunctions();
116 CGSCC->DeleteNode(DeadCGN);
117 }
118 }
119
replaceFunctionWith(Function & OldFn,Function & NewFn)120 void CallGraphUpdater::replaceFunctionWith(Function &OldFn, Function &NewFn) {
121 OldFn.removeDeadConstantUsers();
122 ReplacedFunctions.insert(&OldFn);
123 if (CG) {
124 // Update the call graph for the newly promoted function.
125 CallGraphNode *OldCGN = (*CG)[&OldFn];
126 CallGraphNode *NewCGN = CG->getOrInsertFunction(&NewFn);
127 NewCGN->stealCalledFunctionsFrom(OldCGN);
128 CG->ReplaceExternalCallEdge(OldCGN, NewCGN);
129
130 // And update the SCC we're iterating as well.
131 CGSCC->ReplaceNode(OldCGN, NewCGN);
132 } else if (LCG) {
133 // Directly substitute the functions in the call graph.
134 LazyCallGraph::Node &OldLCGN = LCG->get(OldFn);
135 SCC->getOuterRefSCC().replaceNodeFunction(OldLCGN, NewFn);
136 }
137 removeFunction(OldFn);
138 }
139
replaceCallSite(CallBase & OldCS,CallBase & NewCS)140 bool CallGraphUpdater::replaceCallSite(CallBase &OldCS, CallBase &NewCS) {
141 // This is only necessary in the (old) CG.
142 if (!CG)
143 return true;
144
145 Function *Caller = OldCS.getCaller();
146 CallGraphNode *NewCalleeNode =
147 CG->getOrInsertFunction(NewCS.getCalledFunction());
148 CallGraphNode *CallerNode = (*CG)[Caller];
149 if (llvm::none_of(*CallerNode, [&OldCS](const CallGraphNode::CallRecord &CR) {
150 return CR.first && *CR.first == &OldCS;
151 }))
152 return false;
153 CallerNode->replaceCallEdge(OldCS, NewCS, NewCalleeNode);
154 return true;
155 }
156
removeCallSite(CallBase & CS)157 void CallGraphUpdater::removeCallSite(CallBase &CS) {
158 // This is only necessary in the (old) CG.
159 if (!CG)
160 return;
161
162 Function *Caller = CS.getCaller();
163 CallGraphNode *CallerNode = (*CG)[Caller];
164 CallerNode->removeCallEdgeFor(CS);
165 }
166