llvm-project

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->markDeadFunction(*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
        UR->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.
82
        DeadFn->eraseFromParent();
83
      }
84
    }
85
  }
86

87
  bool Changed = !DeadFunctions.empty();
88
  DeadFunctionsInComdats.clear();
89
  DeadFunctions.clear();
90
  return Changed;
91
}
92

93
void CallGraphUpdater::reanalyzeFunction(Function &Fn) {
94
  if (CG) {
95
    CallGraphNode *OldCGN = CG->getOrInsertFunction(&Fn);
96
    OldCGN->removeAllCalledFunctions();
97
    CG->populateCallGraphNode(OldCGN);
98
  } else if (LCG) {
99
    LazyCallGraph::Node &N = LCG->get(Fn);
100
    LazyCallGraph::SCC *C = LCG->lookupSCC(N);
101
    updateCGAndAnalysisManagerForCGSCCPass(*LCG, *C, N, *AM, *UR, *FAM);
102
  }
103
}
104

105
void CallGraphUpdater::registerOutlinedFunction(Function &OriginalFn,
106
                                                Function &NewFn) {
107
  if (CG)
108
    CG->addToCallGraph(&NewFn);
109
  else if (LCG)
110
    LCG->addSplitFunction(OriginalFn, NewFn);
111
}
112

113
void CallGraphUpdater::removeFunction(Function &DeadFn) {
114
  DeadFn.deleteBody();
115
  DeadFn.setLinkage(GlobalValue::ExternalLinkage);
116
  if (DeadFn.hasComdat())
117
    DeadFunctionsInComdats.push_back(&DeadFn);
118
  else
119
    DeadFunctions.push_back(&DeadFn);
120

121
  // For the old call graph we remove the function from the SCC right away.
122
  if (CG && !ReplacedFunctions.count(&DeadFn)) {
123
    CallGraphNode *DeadCGN = (*CG)[&DeadFn];
124
    DeadCGN->removeAllCalledFunctions();
125
    CGSCC->DeleteNode(DeadCGN);
126
  }
127
  if (FAM)
128
    FAM->clear(DeadFn, DeadFn.getName());
129
}
130

131
void CallGraphUpdater::replaceFunctionWith(Function &OldFn, Function &NewFn) {
132
  OldFn.removeDeadConstantUsers();
133
  ReplacedFunctions.insert(&OldFn);
134
  if (CG) {
135
    // Update the call graph for the newly promoted function.
136
    CallGraphNode *OldCGN = (*CG)[&OldFn];
137
    CallGraphNode *NewCGN = CG->getOrInsertFunction(&NewFn);
138
    NewCGN->stealCalledFunctionsFrom(OldCGN);
139
    CG->ReplaceExternalCallEdge(OldCGN, NewCGN);
140

141
    // And update the SCC we're iterating as well.
142
    CGSCC->ReplaceNode(OldCGN, NewCGN);
143
  } else if (LCG) {
144
    // Directly substitute the functions in the call graph.
145
    LazyCallGraph::Node &OldLCGN = LCG->get(OldFn);
146
    SCC->getOuterRefSCC().replaceNodeFunction(OldLCGN, NewFn);
147
  }
148
  removeFunction(OldFn);
149
}
150

151
bool CallGraphUpdater::replaceCallSite(CallBase &OldCS, CallBase &NewCS) {
152
  // This is only necessary in the (old) CG.
153
  if (!CG)
154
    return true;
155

156
  Function *Caller = OldCS.getCaller();
157
  CallGraphNode *NewCalleeNode =
158
      CG->getOrInsertFunction(NewCS.getCalledFunction());
159
  CallGraphNode *CallerNode = (*CG)[Caller];
160
  if (llvm::none_of(*CallerNode, [&OldCS](const CallGraphNode::CallRecord &CR) {
161
        return CR.first && *CR.first == &OldCS;
162
      }))
163
    return false;
164
  CallerNode->replaceCallEdge(OldCS, NewCS, NewCalleeNode);
165
  return true;
166
}
167

168
void CallGraphUpdater::removeCallSite(CallBase &CS) {
169
  // This is only necessary in the (old) CG.
170
  if (!CG)
171
    return;
172

173
  Function *Caller = CS.getCaller();
174
  CallGraphNode *CallerNode = (*CG)[Caller];
175
  CallerNode->removeCallEdgeFor(CS);
176
}
177