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/Analysis/CallGraph.h"
18 #include "llvm/Analysis/CallGraphSCCPass.h"
19 #include "llvm/IR/Constants.h"
20 #include "llvm/Transforms/Utils/ModuleUtils.h"
21 
22 using namespace llvm;
23 
24 bool CallGraphUpdater::finalize() {
25   if (!DeadFunctionsInComdats.empty()) {
26     filterDeadComdatFunctions(DeadFunctionsInComdats);
27     DeadFunctions.append(DeadFunctionsInComdats.begin(),
28                          DeadFunctionsInComdats.end());
29   }
30 
31   if (CG) {
32     // First remove all references, e.g., outgoing via called functions. This is
33     // necessary as we can delete functions that have circular references.
34     for (Function *DeadFn : DeadFunctions) {
35       DeadFn->removeDeadConstantUsers();
36       CallGraphNode *DeadCGN = (*CG)[DeadFn];
37       DeadCGN->removeAllCalledFunctions();
38       CG->getExternalCallingNode()->removeAnyCallEdgeTo(DeadCGN);
39       DeadFn->replaceAllUsesWith(UndefValue::get(DeadFn->getType()));
40     }
41 
42     // Then remove the node and function from the module.
43     for (Function *DeadFn : DeadFunctions) {
44       CallGraphNode *DeadCGN = CG->getOrInsertFunction(DeadFn);
45       assert(DeadCGN->getNumReferences() == 0 &&
46              "References should have been handled by now");
47       delete CG->removeFunctionFromModule(DeadCGN);
48     }
49   } else {
50     // This is the code path for the new lazy call graph and for the case were
51     // no call graph was provided.
52     for (Function *DeadFn : DeadFunctions) {
53       DeadFn->removeDeadConstantUsers();
54       DeadFn->replaceAllUsesWith(UndefValue::get(DeadFn->getType()));
55 
56       if (LCG && !ReplacedFunctions.count(DeadFn)) {
57         // Taken mostly from the inliner:
58         LazyCallGraph::Node &N = LCG->get(*DeadFn);
59         auto *DeadSCC = LCG->lookupSCC(N);
60         assert(DeadSCC && DeadSCC->size() == 1 &&
61                &DeadSCC->begin()->getFunction() == DeadFn);
62         auto &DeadRC = DeadSCC->getOuterRefSCC();
63 
64         FunctionAnalysisManager &FAM =
65             AM->getResult<FunctionAnalysisManagerCGSCCProxy>(*DeadSCC, *LCG)
66                 .getManager();
67 
68         FAM.clear(*DeadFn, DeadFn->getName());
69         AM->clear(*DeadSCC, DeadSCC->getName());
70         LCG->removeDeadFunction(*DeadFn);
71 
72         // Mark the relevant parts of the call graph as invalid so we don't
73         // visit them.
74         UR->InvalidatedSCCs.insert(DeadSCC);
75         UR->InvalidatedRefSCCs.insert(&DeadRC);
76       }
77 
78       // The function is now really dead and de-attached from everything.
79       DeadFn->eraseFromParent();
80     }
81   }
82 
83   bool Changed = !DeadFunctions.empty();
84   DeadFunctionsInComdats.clear();
85   DeadFunctions.clear();
86   return Changed;
87 }
88 
89 void CallGraphUpdater::reanalyzeFunction(Function &Fn) {
90   if (CG) {
91     CallGraphNode *OldCGN = CG->getOrInsertFunction(&Fn);
92     OldCGN->removeAllCalledFunctions();
93     CG->populateCallGraphNode(OldCGN);
94   } else if (LCG) {
95     LazyCallGraph::Node &N = LCG->get(Fn);
96     LazyCallGraph::SCC *C = LCG->lookupSCC(N);
97     updateCGAndAnalysisManagerForCGSCCPass(*LCG, *C, N, *AM, *UR, *FAM);
98   }
99 }
100 
101 void CallGraphUpdater::registerOutlinedFunction(Function &OriginalFn,
102                                                 Function &NewFn) {
103   if (CG)
104     CG->addToCallGraph(&NewFn);
105   else if (LCG)
106     LCG->addSplitFunction(OriginalFn, NewFn);
107 }
108 
109 void CallGraphUpdater::removeFunction(Function &DeadFn) {
110   DeadFn.deleteBody();
111   DeadFn.setLinkage(GlobalValue::ExternalLinkage);
112   if (DeadFn.hasComdat())
113     DeadFunctionsInComdats.push_back(&DeadFn);
114   else
115     DeadFunctions.push_back(&DeadFn);
116 
117   // For the old call graph we remove the function from the SCC right away.
118   if (CG && !ReplacedFunctions.count(&DeadFn)) {
119     CallGraphNode *DeadCGN = (*CG)[&DeadFn];
120     DeadCGN->removeAllCalledFunctions();
121     CGSCC->DeleteNode(DeadCGN);
122   }
123 }
124 
125 void CallGraphUpdater::replaceFunctionWith(Function &OldFn, Function &NewFn) {
126   OldFn.removeDeadConstantUsers();
127   ReplacedFunctions.insert(&OldFn);
128   if (CG) {
129     // Update the call graph for the newly promoted function.
130     CallGraphNode *OldCGN = (*CG)[&OldFn];
131     CallGraphNode *NewCGN = CG->getOrInsertFunction(&NewFn);
132     NewCGN->stealCalledFunctionsFrom(OldCGN);
133     CG->ReplaceExternalCallEdge(OldCGN, NewCGN);
134 
135     // And update the SCC we're iterating as well.
136     CGSCC->ReplaceNode(OldCGN, NewCGN);
137   } else if (LCG) {
138     // Directly substitute the functions in the call graph.
139     LazyCallGraph::Node &OldLCGN = LCG->get(OldFn);
140     SCC->getOuterRefSCC().replaceNodeFunction(OldLCGN, NewFn);
141   }
142   removeFunction(OldFn);
143 }
144 
145 bool CallGraphUpdater::replaceCallSite(CallBase &OldCS, CallBase &NewCS) {
146   // This is only necessary in the (old) CG.
147   if (!CG)
148     return true;
149 
150   Function *Caller = OldCS.getCaller();
151   CallGraphNode *NewCalleeNode =
152       CG->getOrInsertFunction(NewCS.getCalledFunction());
153   CallGraphNode *CallerNode = (*CG)[Caller];
154   if (llvm::none_of(*CallerNode, [&OldCS](const CallGraphNode::CallRecord &CR) {
155         return CR.first && *CR.first == &OldCS;
156       }))
157     return false;
158   CallerNode->replaceCallEdge(OldCS, NewCS, NewCalleeNode);
159   return true;
160 }
161 
162 void CallGraphUpdater::removeCallSite(CallBase &CS) {
163   // This is only necessary in the (old) CG.
164   if (!CG)
165     return;
166 
167   Function *Caller = CS.getCaller();
168   CallGraphNode *CallerNode = (*CG)[Caller];
169   CallerNode->removeCallEdgeFor(CS);
170 }
171