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 
115 void CallGraphUpdater::replaceFunctionWith(Function &OldFn, Function &NewFn) {
116   OldFn.removeDeadConstantUsers();
117   ReplacedFunctions.insert(&OldFn);
118   if (CG) {
119     // Update the call graph for the newly promoted function.
120     // CG->spliceFunction(&OldFn, &NewFn);
121     CallGraphNode *OldCGN = (*CG)[&OldFn];
122     CallGraphNode *NewCGN = CG->getOrInsertFunction(&NewFn);
123     NewCGN->stealCalledFunctionsFrom(OldCGN);
124 
125     // And update the SCC we're iterating as well.
126     CGSCC->ReplaceNode(OldCGN, NewCGN);
127   } else if (LCG) {
128     // Directly substitute the functions in the call graph.
129     LazyCallGraph::Node &OldLCGN = LCG->get(OldFn);
130     SCC->getOuterRefSCC().replaceNodeFunction(OldLCGN, NewFn);
131   }
132   removeFunction(OldFn);
133 }
134 
135 bool CallGraphUpdater::replaceCallSite(CallBase &OldCS, CallBase &NewCS) {
136   // This is only necessary in the (old) CG.
137   if (!CG)
138     return true;
139 
140   Function *Caller = OldCS.getCaller();
141   CallGraphNode *NewCalleeNode =
142       CG->getOrInsertFunction(NewCS.getCalledFunction());
143   CallGraphNode *CallerNode = (*CG)[Caller];
144   if (llvm::none_of(*CallerNode, [&OldCS](const CallGraphNode::CallRecord &CR) {
145         return CR.first == &OldCS;
146       }))
147     return false;
148   CallerNode->replaceCallEdge(OldCS, NewCS, NewCalleeNode);
149   return true;
150 }
151 
152 void CallGraphUpdater::removeCallSite(CallBase &CS) {
153   // This is only necessary in the (old) CG.
154   if (!CG)
155     return;
156 
157   Function *Caller = CS.getCaller();
158   CallGraphNode *CallerNode = (*CG)[Caller];
159   CallerNode->removeCallEdgeFor(CS);
160 }
161