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