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