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
22using namespace llvm;
23
24bool 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
89void 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
101void 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
109void 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
127void 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
147bool 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
164void 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

source code of llvm/lib/Transforms/Utils/CallGraphUpdater.cpp