llvm/lib/Transforms/Utils/CallGraphUpdater.cpp

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