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, *FAM);
96   }
97 }
98 
99 void CallGraphUpdater::registerOutlinedFunction(Function &NewFn) {
100   if (CG)
101     CG->addToCallGraph(&NewFn);
102 }
103 
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 
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 
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 
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