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/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 }