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