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 | |
24 | bool CallGraphUpdater::finalize() { |
25 | if (!DeadFunctionsInComdats.empty()) { |
26 | filterDeadComdatFunctions(DeadComdatFunctions&: DeadFunctionsInComdats); |
27 | DeadFunctions.append(in_start: DeadFunctionsInComdats.begin(), |
28 | in_end: 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(Callee: DeadCGN); |
39 | DeadFn->replaceAllUsesWith(V: PoisonValue::get(T: DeadFn->getType())); |
40 | } |
41 | |
42 | // Then remove the node and function from the module. |
43 | for (Function *DeadFn : DeadFunctions) { |
44 | CallGraphNode *DeadCGN = CG->getOrInsertFunction(F: DeadFn); |
45 | assert(DeadCGN->getNumReferences() == 0 && |
46 | "References should have been handled by now" ); |
47 | delete CG->removeFunctionFromModule(CGN: 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(V: PoisonValue::get(T: DeadFn->getType())); |
55 | |
56 | if (LCG && !ReplacedFunctions.count(Ptr: DeadFn)) { |
57 | // Taken mostly from the inliner: |
58 | LazyCallGraph::Node &N = LCG->get(F&: *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>(IR&: *DeadSCC, ExtraArgs&: *LCG) |
66 | .getManager(); |
67 | |
68 | FAM.clear(IR&: *DeadFn, Name: DeadFn->getName()); |
69 | AM->clear(IR&: *DeadSCC, Name: DeadSCC->getName()); |
70 | LCG->removeDeadFunction(F&: *DeadFn); |
71 | |
72 | // Mark the relevant parts of the call graph as invalid so we don't |
73 | // visit them. |
74 | UR->InvalidatedSCCs.insert(Ptr: DeadSCC); |
75 | UR->InvalidatedRefSCCs.insert(Ptr: &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 | |
89 | void CallGraphUpdater::reanalyzeFunction(Function &Fn) { |
90 | if (CG) { |
91 | CallGraphNode *OldCGN = CG->getOrInsertFunction(F: &Fn); |
92 | OldCGN->removeAllCalledFunctions(); |
93 | CG->populateCallGraphNode(CGN: OldCGN); |
94 | } else if (LCG) { |
95 | LazyCallGraph::Node &N = LCG->get(F&: Fn); |
96 | LazyCallGraph::SCC *C = LCG->lookupSCC(N); |
97 | updateCGAndAnalysisManagerForCGSCCPass(G&: *LCG, C&: *C, N, AM&: *AM, UR&: *UR, FAM&: *FAM); |
98 | } |
99 | } |
100 | |
101 | void CallGraphUpdater::registerOutlinedFunction(Function &OriginalFn, |
102 | Function &NewFn) { |
103 | if (CG) |
104 | CG->addToCallGraph(F: &NewFn); |
105 | else if (LCG) |
106 | LCG->addSplitFunction(OriginalFunction&: OriginalFn, NewFunction&: NewFn); |
107 | } |
108 | |
109 | void CallGraphUpdater::removeFunction(Function &DeadFn) { |
110 | DeadFn.deleteBody(); |
111 | DeadFn.setLinkage(GlobalValue::ExternalLinkage); |
112 | if (DeadFn.hasComdat()) |
113 | DeadFunctionsInComdats.push_back(Elt: &DeadFn); |
114 | else |
115 | DeadFunctions.push_back(Elt: &DeadFn); |
116 | |
117 | // For the old call graph we remove the function from the SCC right away. |
118 | if (CG && !ReplacedFunctions.count(Ptr: &DeadFn)) { |
119 | CallGraphNode *DeadCGN = (*CG)[&DeadFn]; |
120 | DeadCGN->removeAllCalledFunctions(); |
121 | CGSCC->DeleteNode(Old: DeadCGN); |
122 | } |
123 | if (FAM) |
124 | FAM->clear(IR&: DeadFn, Name: DeadFn.getName()); |
125 | } |
126 | |
127 | void CallGraphUpdater::replaceFunctionWith(Function &OldFn, Function &NewFn) { |
128 | OldFn.removeDeadConstantUsers(); |
129 | ReplacedFunctions.insert(Ptr: &OldFn); |
130 | if (CG) { |
131 | // Update the call graph for the newly promoted function. |
132 | CallGraphNode *OldCGN = (*CG)[&OldFn]; |
133 | CallGraphNode *NewCGN = CG->getOrInsertFunction(F: &NewFn); |
134 | NewCGN->stealCalledFunctionsFrom(N: OldCGN); |
135 | CG->ReplaceExternalCallEdge(Old: OldCGN, New: NewCGN); |
136 | |
137 | // And update the SCC we're iterating as well. |
138 | CGSCC->ReplaceNode(Old: OldCGN, New: NewCGN); |
139 | } else if (LCG) { |
140 | // Directly substitute the functions in the call graph. |
141 | LazyCallGraph::Node &OldLCGN = LCG->get(F&: OldFn); |
142 | SCC->getOuterRefSCC().replaceNodeFunction(N&: OldLCGN, NewF&: NewFn); |
143 | } |
144 | removeFunction(DeadFn&: OldFn); |
145 | } |
146 | |
147 | bool CallGraphUpdater::replaceCallSite(CallBase &OldCS, CallBase &NewCS) { |
148 | // This is only necessary in the (old) CG. |
149 | if (!CG) |
150 | return true; |
151 | |
152 | Function *Caller = OldCS.getCaller(); |
153 | CallGraphNode *NewCalleeNode = |
154 | CG->getOrInsertFunction(F: NewCS.getCalledFunction()); |
155 | CallGraphNode *CallerNode = (*CG)[Caller]; |
156 | if (llvm::none_of(Range&: *CallerNode, P: [&OldCS](const CallGraphNode::CallRecord &CR) { |
157 | return CR.first && *CR.first == &OldCS; |
158 | })) |
159 | return false; |
160 | CallerNode->replaceCallEdge(Call&: OldCS, NewCall&: NewCS, NewNode: NewCalleeNode); |
161 | return true; |
162 | } |
163 | |
164 | void CallGraphUpdater::removeCallSite(CallBase &CS) { |
165 | // This is only necessary in the (old) CG. |
166 | if (!CG) |
167 | return; |
168 | |
169 | Function *Caller = CS.getCaller(); |
170 | CallGraphNode *CallerNode = (*CG)[Caller]; |
171 | CallerNode->removeCallEdgeFor(Call&: CS); |
172 | } |
173 | |