1 //===- CallGraphUpdater.cpp - A (lazy) call graph update helper -----------===//
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
7 //===----------------------------------------------------------------------===//
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.
13 //===----------------------------------------------------------------------===//
15 #include "llvm/Transforms/Utils/CallGraphUpdater.h"
16 #include "llvm/ADT/STLExtras.h"
17 #include "llvm/Transforms/Utils/ModuleUtils.h"
21 bool CallGraphUpdater::finalize() {
22 if (!DeadFunctionsInComdats.empty()) {
23 filterDeadComdatFunctions(*DeadFunctionsInComdats.front()->getParent(),
24 DeadFunctionsInComdats);
25 DeadFunctions.append(DeadFunctionsInComdats.begin(),
26 DeadFunctionsInComdats.end());
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()));
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);
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()));
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();
62 FunctionAnalysisManager &FAM =
63 AM->getResult<FunctionAnalysisManagerCGSCCProxy>(*DeadSCC, *LCG)
66 FAM.clear(*DeadFn, DeadFn->getName());
67 AM->clear(*DeadSCC, DeadSCC->getName());
68 LCG->removeDeadFunction(*DeadFn);
70 // Mark the relevant parts of the call graph as invalid so we don't
72 UR->InvalidatedSCCs.insert(DeadSCC);
73 UR->InvalidatedRefSCCs.insert(&DeadRC);
76 // The function is now really dead and de-attached from everything.
77 DeadFn->eraseFromParent();
81 bool Changed = !DeadFunctions.empty();
82 DeadFunctionsInComdats.clear();
83 DeadFunctions.clear();
87 void CallGraphUpdater::reanalyzeFunction(Function &Fn) {
89 CallGraphNode *OldCGN = CG->getOrInsertFunction(&Fn);
90 OldCGN->removeAllCalledFunctions();
91 CG->populateCallGraphNode(OldCGN);
93 LazyCallGraph::Node &N = LCG->get(Fn);
94 LazyCallGraph::SCC *C = LCG->lookupSCC(N);
95 updateCGAndAnalysisManagerForCGSCCPass(*LCG, *C, N, *AM, *UR, *FAM);
99 void CallGraphUpdater::registerOutlinedFunction(Function &NewFn) {
101 CG->addToCallGraph(&NewFn);
103 LCG->addNewFunctionIntoSCC(NewFn, *SCC);
106 void CallGraphUpdater::removeFunction(Function &DeadFn) {
108 DeadFn.setLinkage(GlobalValue::ExternalLinkage);
109 if (DeadFn.hasComdat())
110 DeadFunctionsInComdats.push_back(&DeadFn);
112 DeadFunctions.push_back(&DeadFn);
114 // For the old call graph we remove the function from the SCC right away.
115 if (CG && !ReplacedFunctions.count(&DeadFn)) {
116 CallGraphNode *DeadCGN = (*CG)[&DeadFn];
117 DeadCGN->removeAllCalledFunctions();
118 CGSCC->DeleteNode(DeadCGN);
122 void CallGraphUpdater::replaceFunctionWith(Function &OldFn, Function &NewFn) {
123 OldFn.removeDeadConstantUsers();
124 ReplacedFunctions.insert(&OldFn);
126 // Update the call graph for the newly promoted function.
127 CallGraphNode *OldCGN = (*CG)[&OldFn];
128 CallGraphNode *NewCGN = CG->getOrInsertFunction(&NewFn);
129 NewCGN->stealCalledFunctionsFrom(OldCGN);
130 CG->ReplaceExternalCallEdge(OldCGN, NewCGN);
132 // And update the SCC we're iterating as well.
133 CGSCC->ReplaceNode(OldCGN, NewCGN);
135 // Directly substitute the functions in the call graph.
136 LazyCallGraph::Node &OldLCGN = LCG->get(OldFn);
137 SCC->getOuterRefSCC().replaceNodeFunction(OldLCGN, NewFn);
139 removeFunction(OldFn);
142 bool CallGraphUpdater::replaceCallSite(CallBase &OldCS, CallBase &NewCS) {
143 // This is only necessary in the (old) CG.
147 Function *Caller = OldCS.getCaller();
148 CallGraphNode *NewCalleeNode =
149 CG->getOrInsertFunction(NewCS.getCalledFunction());
150 CallGraphNode *CallerNode = (*CG)[Caller];
151 if (llvm::none_of(*CallerNode, [&OldCS](const CallGraphNode::CallRecord &CR) {
152 return CR.first && *CR.first == &OldCS;
155 CallerNode->replaceCallEdge(OldCS, NewCS, NewCalleeNode);
159 void CallGraphUpdater::removeCallSite(CallBase &CS) {
160 // This is only necessary in the (old) CG.
164 Function *Caller = CS.getCaller();
165 CallGraphNode *CallerNode = (*CG)[Caller];
166 CallerNode->removeCallEdgeFor(CS);