Home | History | Annotate | Line # | Download | only in Utils 
      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 }
    169