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   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     CallGraphNode *DeadCGN = (*CG)[&DeadFn];
117     DeadCGN->removeAllCalledFunctions();
118     CGSCC->DeleteNode(DeadCGN);
119   }
120 }
121 
122 void CallGraphUpdater::replaceFunctionWith(Function &OldFn, Function &NewFn) {
123   OldFn.removeDeadConstantUsers();
124   ReplacedFunctions.insert(&OldFn);
125   if (CG) {
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);
131 
132     // And update the SCC we're iterating as well.
133     CGSCC->ReplaceNode(OldCGN, NewCGN);
134   } else if (LCG) {
135     // Directly substitute the functions in the call graph.
136     LazyCallGraph::Node &OldLCGN = LCG->get(OldFn);
137     SCC->getOuterRefSCC().replaceNodeFunction(OldLCGN, NewFn);
138   }
139   removeFunction(OldFn);
140 }
141 
142 bool CallGraphUpdater::replaceCallSite(CallBase &OldCS, CallBase &NewCS) {
143   // This is only necessary in the (old) CG.
144   if (!CG)
145     return true;
146 
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;
153       }))
154     return false;
155   CallerNode->replaceCallEdge(OldCS, NewCS, NewCalleeNode);
156   return true;
157 }
158 
159 void CallGraphUpdater::removeCallSite(CallBase &CS) {
160   // This is only necessary in the (old) CG.
161   if (!CG)
162     return;
163 
164   Function *Caller = CS.getCaller();
165   CallGraphNode *CallerNode = (*CG)[Caller];
166   CallerNode->removeCallEdgeFor(CS);
167 }
168