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   for (Function *DeadFn : DeadFunctions) {
30     DeadFn->removeDeadConstantUsers();
31 
32     if (CG) {
33       CallGraphNode *OldCGN = CG->getOrInsertFunction(DeadFn);
34       CG->getExternalCallingNode()->removeAnyCallEdgeTo(OldCGN);
35       OldCGN->removeAllCalledFunctions();
36       DeadFn->replaceAllUsesWith(UndefValue::get(DeadFn->getType()));
37 
38       assert(OldCGN->getNumReferences() == 0);
39 
40       delete CG->removeFunctionFromModule(OldCGN);
41       continue;
42     }
43 
44     // The old style call graph (CG) has a value handle we do not want to
45     // replace with undef so we do this here.
46     DeadFn->replaceAllUsesWith(UndefValue::get(DeadFn->getType()));
47 
48     if (LCG && !ReplacedFunctions.count(DeadFn)) {
49       // Taken mostly from the inliner:
50       LazyCallGraph::Node &N = LCG->get(*DeadFn);
51       auto *DeadSCC = LCG->lookupSCC(N);
52       assert(DeadSCC && DeadSCC->size() == 1 &&
53              &DeadSCC->begin()->getFunction() == DeadFn);
54       auto &DeadRC = DeadSCC->getOuterRefSCC();
55 
56       FunctionAnalysisManager &FAM =
57           AM->getResult<FunctionAnalysisManagerCGSCCProxy>(*DeadSCC, *LCG)
58               .getManager();
59 
60       FAM.clear(*DeadFn, DeadFn->getName());
61       AM->clear(*DeadSCC, DeadSCC->getName());
62       LCG->removeDeadFunction(*DeadFn);
63 
64       // Mark the relevant parts of the call graph as invalid so we don't visit
65       // them.
66       UR->InvalidatedSCCs.insert(DeadSCC);
67       UR->InvalidatedRefSCCs.insert(&DeadRC);
68     }
69 
70     // The function is now really dead and de-attached from everything.
71     DeadFn->eraseFromParent();
72   }
73 
74   bool Changed = !DeadFunctions.empty();
75   DeadFunctionsInComdats.clear();
76   DeadFunctions.clear();
77   return Changed;
78 }
79 
80 void CallGraphUpdater::reanalyzeFunction(Function &Fn) {
81   if (CG) {
82     CallGraphNode *OldCGN = CG->getOrInsertFunction(&Fn);
83     OldCGN->removeAllCalledFunctions();
84     CG->populateCallGraphNode(OldCGN);
85   } else if (LCG) {
86     LazyCallGraph::Node &N = LCG->get(Fn);
87     LazyCallGraph::SCC *C = LCG->lookupSCC(N);
88     updateCGAndAnalysisManagerForCGSCCPass(*LCG, *C, N, *AM, *UR);
89   }
90 }
91 
92 void CallGraphUpdater::registerOutlinedFunction(Function &NewFn) {
93   if (CG)
94     CG->addToCallGraph(&NewFn);
95   else if (LCG)
96     LCG->addNewFunctionIntoSCC(NewFn, *SCC);
97 }
98 
99 void CallGraphUpdater::removeFunction(Function &DeadFn) {
100   DeadFn.deleteBody();
101   DeadFn.setLinkage(GlobalValue::ExternalLinkage);
102   if (DeadFn.hasComdat())
103     DeadFunctionsInComdats.push_back(&DeadFn);
104   else
105     DeadFunctions.push_back(&DeadFn);
106 }
107 
108 void CallGraphUpdater::replaceFunctionWith(Function &OldFn, Function &NewFn) {
109   ReplacedFunctions.insert(&OldFn);
110   if (CG) {
111     // Update the call graph for the newly promoted function.
112     // CG->spliceFunction(&OldFn, &NewFn);
113     CallGraphNode *OldCGN = (*CG)[&OldFn];
114     CallGraphNode *NewCGN = CG->getOrInsertFunction(&NewFn);
115     NewCGN->stealCalledFunctionsFrom(OldCGN);
116 
117     // And update the SCC we're iterating as well.
118     CGSCC->ReplaceNode(OldCGN, NewCGN);
119   } else if (LCG) {
120     // Directly substitute the functions in the call graph.
121     LazyCallGraph::Node &OldLCGN = LCG->get(OldFn);
122     SCC->getOuterRefSCC().replaceNodeFunction(OldLCGN, NewFn);
123   }
124   removeFunction(OldFn);
125 }
126 
127 bool CallGraphUpdater::replaceCallSite(CallBase &OldCS, CallBase &NewCS) {
128   // This is only necessary in the (old) CG.
129   if (!CG)
130     return true;
131 
132   Function *Caller = OldCS.getCaller();
133   CallGraphNode *NewCalleeNode =
134       CG->getOrInsertFunction(NewCS.getCalledFunction());
135   CallGraphNode *CallerNode = (*CG)[Caller];
136   if (llvm::none_of(*CallerNode, [&OldCS](const CallGraphNode::CallRecord &CR) {
137         return CR.first == &OldCS;
138       }))
139     return false;
140   CallerNode->replaceCallEdge(OldCS, NewCS, NewCalleeNode);
141   return true;
142 }
143 
144 void CallGraphUpdater::removeCallSite(CallBase &CS) {
145   // This is only necessary in the (old) CG.
146   if (!CG)
147     return;
148 
149   Function *Caller = CS.getCaller();
150   CallGraphNode *CallerNode = (*CG)[Caller];
151   CallerNode->removeCallEdgeFor(CS);
152 }
153