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/IR/Constants.h"
17#include "llvm/Transforms/Utils/ModuleUtils.h"
18
19using namespace llvm;
20
21bool CallGraphUpdater::finalize() {
22 if (!DeadFunctionsInComdats.empty()) {
23 filterDeadComdatFunctions(DeadComdatFunctions&: DeadFunctionsInComdats);
24 for (Function *DeadFn : DeadFunctionsInComdats)
25 makeFunctionBodyUnreachable(F&: *DeadFn);
26 DeadFunctions.append(in_start: DeadFunctionsInComdats.begin(),
27 in_end: DeadFunctionsInComdats.end());
28 }
29
30 // This is the code path for the new lazy call graph and for the case were
31 // no call graph was provided.
32 for (Function *DeadFn : DeadFunctions) {
33 DeadFn->removeDeadConstantUsers();
34 // If the function is used by metadata, we don't want it to be replaced with
35 // poison in the metadata, so we replace it with nullptr in the metadata
36 // before RAUW'ing the non-metadata uses below.
37 if (DeadFn->isUsedByMetadata())
38 ValueAsMetadata::handleDeletion(V: DeadFn);
39 DeadFn->replaceNonMetadataUsesWith(V: PoisonValue::get(T: DeadFn->getType()));
40
41 if (LCG && !ReplacedFunctions.count(Ptr: DeadFn)) {
42 // Taken mostly from the inliner:
43 LazyCallGraph::Node &N = LCG->get(F&: *DeadFn);
44 auto *DeadSCC = LCG->lookupSCC(N);
45 assert(DeadSCC && DeadSCC->size() == 1 &&
46 &DeadSCC->begin()->getFunction() == DeadFn);
47
48 FAM->clear(IR&: *DeadFn, Name: DeadFn->getName());
49 AM->clear(IR&: *DeadSCC, Name: DeadSCC->getName());
50 LCG->markDeadFunction(F&: *DeadFn);
51
52 // Mark the relevant parts of the call graph as invalid so we don't
53 // visit them.
54 UR->InvalidatedSCCs.insert(Ptr: LCG->lookupSCC(N));
55 UR->DeadFunctions.push_back(Elt: DeadFn);
56 } else {
57 // The CGSCC infrastructure batch deletes functions at the end of the
58 // call graph walk, so only erase the function if we're not using that
59 // infrastructure.
60 // The function is now really dead and de-attached from everything.
61 DeadFn->eraseFromParent();
62 }
63 }
64
65 bool Changed = !DeadFunctions.empty();
66 DeadFunctionsInComdats.clear();
67 DeadFunctions.clear();
68 return Changed;
69}
70
71void CallGraphUpdater::reanalyzeFunction(Function &Fn) {
72 if (LCG) {
73 LazyCallGraph::Node &N = LCG->get(F&: Fn);
74 LazyCallGraph::SCC *C = LCG->lookupSCC(N);
75 updateCGAndAnalysisManagerForCGSCCPass(G&: *LCG, C&: *C, N, AM&: *AM, UR&: *UR, FAM&: *FAM);
76 }
77}
78
79void CallGraphUpdater::addReferences(Function &Fn, Constant &C) {
80 if (!LCG)
81 return;
82
83 LazyCallGraph::Node &N = LCG->get(F&: Fn);
84 SmallVector<Constant *, 4> Worklist = {&C};
85 SmallPtrSet<Constant *, 4> Visited = {&C};
86 LazyCallGraph::visitReferences(Worklist, Visited, Callback: [&](Function &Referee) {
87 LazyCallGraph::Node &RefereeN = LCG->get(F&: Referee);
88 if (!N->lookup(N&: RefereeN))
89 LCG->lookupRefSCC(N)->insertTrivialRefEdge(SourceN&: N, TargetN&: RefereeN);
90 });
91}
92
93void CallGraphUpdater::registerOutlinedFunction(Function &OriginalFn,
94 Function &NewFn) {
95 if (LCG)
96 LCG->addSplitFunction(OriginalFunction&: OriginalFn, NewFunction&: NewFn);
97}
98
99void CallGraphUpdater::removeFunction(Function &DeadFn) {
100 // With a LazyCallGraph, the function is erased only at the end of the CGSCC
101 // walk, and its node must stay a definition until then. Functions in a comdat
102 // are only cleared in finalize(), once we know the whole comdat is dead.
103 if (DeadFn.hasComdat()) {
104 DeadFunctionsInComdats.push_back(Elt: &DeadFn);
105 } else {
106 makeFunctionBodyUnreachable(F&: DeadFn);
107 DeadFunctions.push_back(Elt: &DeadFn);
108 }
109
110 if (FAM)
111 FAM->clear(IR&: DeadFn, Name: DeadFn.getName());
112}
113
114void CallGraphUpdater::replaceFunctionWith(Function &OldFn, Function &NewFn) {
115 OldFn.removeDeadConstantUsers();
116 ReplacedFunctions.insert(Ptr: &OldFn);
117 if (LCG) {
118 // Directly substitute the functions in the call graph.
119 LazyCallGraph::Node &OldLCGN = LCG->get(F&: OldFn);
120 SCC->getOuterRefSCC().replaceNodeFunction(N&: OldLCGN, NewF&: NewFn);
121 }
122 removeFunction(DeadFn&: OldFn);
123}
124