LCOV - code coverage report
Current view: top level - lib/Analysis - CallGraph.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 98 108 90.7 %
Date: 2018-10-20 13:21:21 Functions: 23 25 92.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : //===- CallGraph.cpp - Build a Module's call graph ------------------------===//
       2             : //
       3             : //                     The LLVM Compiler Infrastructure
       4             : //
       5             : // This file is distributed under the University of Illinois Open Source
       6             : // License. See LICENSE.TXT for details.
       7             : //
       8             : //===----------------------------------------------------------------------===//
       9             : 
      10             : #include "llvm/Analysis/CallGraph.h"
      11             : #include "llvm/ADT/STLExtras.h"
      12             : #include "llvm/ADT/SmallVector.h"
      13             : #include "llvm/Config/llvm-config.h"
      14             : #include "llvm/IR/CallSite.h"
      15             : #include "llvm/IR/Module.h"
      16             : #include "llvm/IR/Function.h"
      17             : #include "llvm/IR/Intrinsics.h"
      18             : #include "llvm/IR/PassManager.h"
      19             : #include "llvm/Pass.h"
      20             : #include "llvm/Support/Compiler.h"
      21             : #include "llvm/Support/Debug.h"
      22             : #include "llvm/Support/raw_ostream.h"
      23             : #include <algorithm>
      24             : #include <cassert>
      25             : 
      26             : using namespace llvm;
      27             : 
      28             : //===----------------------------------------------------------------------===//
      29             : // Implementations of the CallGraph class methods.
      30             : //
      31             : 
      32       23930 : CallGraph::CallGraph(Module &M)
      33       23930 :     : M(M), ExternalCallingNode(getOrInsertFunction(nullptr)),
      34       23930 :       CallsExternalNode(llvm::make_unique<CallGraphNode>(nullptr)) {
      35             :   // Add every function to the call graph.
      36     1067215 :   for (Function &F : M)
      37     1043285 :     addToCallGraph(&F);
      38       23930 : }
      39             : 
      40         258 : CallGraph::CallGraph(CallGraph &&Arg)
      41         258 :     : M(Arg.M), FunctionMap(std::move(Arg.FunctionMap)),
      42         258 :       ExternalCallingNode(Arg.ExternalCallingNode),
      43         516 :       CallsExternalNode(std::move(Arg.CallsExternalNode)) {
      44             :   Arg.FunctionMap.clear();
      45         258 :   Arg.ExternalCallingNode = nullptr;
      46         258 : }
      47             : 
      48       48100 : CallGraph::~CallGraph() {
      49             :   // CallsExternalNode is not in the function map, delete it explicitly.
      50       24179 :   if (CallsExternalNode)
      51             :     CallsExternalNode->allReferencesDropped();
      52             : 
      53             : // Reset all node's use counts to zero before deleting them to prevent an
      54             : // assertion from firing.
      55             : #ifndef NDEBUG
      56             :   for (auto &I : FunctionMap)
      57             :     I.second->allReferencesDropped();
      58             : #endif
      59       24179 : }
      60             : 
      61     1043285 : void CallGraph::addToCallGraph(Function *F) {
      62     1043285 :   CallGraphNode *Node = getOrInsertFunction(F);
      63             : 
      64             :   // If this function has external linkage or has its address taken, anything
      65             :   // could call it.
      66       54450 :   if (!F->hasLocalLinkage() || F->hasAddressTaken())
      67     1006910 :     ExternalCallingNode->addCalledFunction(CallSite(), Node);
      68             : 
      69             :   // If this function is not defined in this translation unit, it could call
      70             :   // anything.
      71     1043285 :   if (F->isDeclaration() && !F->isIntrinsic())
      72      105968 :     Node->addCalledFunction(CallSite(), CallsExternalNode.get());
      73             : 
      74             :   // Look for calls by this function.
      75     4580308 :   for (BasicBlock &BB : *F)
      76    27509372 :     for (Instruction &I : BB) {
      77    23972349 :       if (auto CS = CallSite(&I)) {
      78             :         const Function *Callee = CS.getCalledFunction();
      79     3800809 :         if (!Callee || !Intrinsic::isLeaf(Callee->getIntrinsicID()))
      80             :           // Indirect calls of intrinsics are not allowed so no need to check.
      81             :           // We can be more precise here by using TargetArg returned by
      82             :           // Intrinsic::isLeaf.
      83       41759 :           Node->addCalledFunction(CS, CallsExternalNode.get());
      84     3800795 :         else if (!Callee->isIntrinsic())
      85     6067580 :           Node->addCalledFunction(CS, getOrInsertFunction(Callee));
      86             :       }
      87             :     }
      88     1043285 : }
      89             : 
      90           6 : void CallGraph::print(raw_ostream &OS) const {
      91             :   // Print in a deterministic order by sorting CallGraphNodes by name.  We do
      92             :   // this here to avoid slowing down the non-printing fast path.
      93             : 
      94             :   SmallVector<CallGraphNode *, 16> Nodes;
      95             :   Nodes.reserve(FunctionMap.size());
      96             : 
      97          25 :   for (const auto &I : *this)
      98          19 :     Nodes.push_back(I.second.get());
      99             : 
     100             :   llvm::sort(Nodes, [](CallGraphNode *LHS, CallGraphNode *RHS) {
     101             :     if (Function *LF = LHS->getFunction())
     102             :       if (Function *RF = RHS->getFunction())
     103             :         return LF->getName() < RF->getName();
     104             : 
     105             :     return RHS->getFunction() != nullptr;
     106             :   });
     107             : 
     108          25 :   for (CallGraphNode *CN : Nodes)
     109          19 :     CN->print(OS);
     110           6 : }
     111             : 
     112             : #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
     113             : LLVM_DUMP_METHOD void CallGraph::dump() const { print(dbgs()); }
     114             : #endif
     115             : 
     116             : // removeFunctionFromModule - Unlink the function from this module, returning
     117             : // it.  Because this removes the function from the module, the call graph node
     118             : // is destroyed.  This is only valid if the function does not call any other
     119             : // functions (ie, there are no edges in it's CGN).  The easiest way to do this
     120             : // is to dropAllReferences before calling this.
     121             : //
     122      527028 : Function *CallGraph::removeFunctionFromModule(CallGraphNode *CGN) {
     123             :   assert(CGN->empty() && "Cannot remove function from call "
     124             :          "graph if it references other functions!");
     125      527028 :   Function *F = CGN->getFunction(); // Get the function for the call graph node
     126      527028 :   FunctionMap.erase(F);             // Remove the call graph node from the map
     127             : 
     128      527028 :   M.getFunctionList().remove(F);
     129      527028 :   return F;
     130             : }
     131             : 
     132             : /// spliceFunction - Replace the function represented by this node by another.
     133             : /// This does not rescan the body of the function, so it is suitable when
     134             : /// splicing the body of the old function to the new while also updating all
     135             : /// callers from old to new.
     136           0 : void CallGraph::spliceFunction(const Function *From, const Function *To) {
     137             :   assert(FunctionMap.count(From) && "No CallGraphNode for function!");
     138             :   assert(!FunctionMap.count(To) &&
     139             :          "Pointing CallGraphNode at a function that already exists");
     140             :   FunctionMapTy::iterator I = FunctionMap.find(From);
     141           0 :   I->second->F = const_cast<Function*>(To);
     142           0 :   FunctionMap[To] = std::move(I->second);
     143             :   FunctionMap.erase(I);
     144           0 : }
     145             : 
     146             : // getOrInsertFunction - This method is identical to calling operator[], but
     147             : // it will insert a new CallGraphNode for the specified function if one does
     148             : // not already exist.
     149     4102909 : CallGraphNode *CallGraph::getOrInsertFunction(const Function *F) {
     150     4102909 :   auto &CGN = FunctionMap[F];
     151     4102909 :   if (CGN)
     152             :     return CGN.get();
     153             : 
     154             :   assert((!F || F->getParent() == &M) && "Function not in current module!");
     155     1067438 :   CGN = llvm::make_unique<CallGraphNode>(const_cast<Function *>(F));
     156     1067438 :   return CGN.get();
     157             : }
     158             : 
     159             : //===----------------------------------------------------------------------===//
     160             : // Implementations of the CallGraphNode class methods.
     161             : //
     162             : 
     163          19 : void CallGraphNode::print(raw_ostream &OS) const {
     164          19 :   if (Function *F = getFunction())
     165          13 :     OS << "Call graph node for function: '" << F->getName() << "'";
     166             :   else
     167           6 :     OS << "Call graph node <<null function>>";
     168             : 
     169          19 :   OS << "<<" << this << ">>  #uses=" << getNumReferences() << '\n';
     170             : 
     171          36 :   for (const auto &I : *this) {
     172          17 :     OS << "  CS<" << I.first << "> calls ";
     173          17 :     if (Function *FI = I.second->getFunction())
     174          14 :       OS << "function '" << FI->getName() <<"'\n";
     175             :     else
     176           3 :       OS << "external node\n";
     177             :   }
     178             :   OS << '\n';
     179          19 : }
     180             : 
     181             : #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
     182             : LLVM_DUMP_METHOD void CallGraphNode::dump() const { print(dbgs()); }
     183             : #endif
     184             : 
     185             : /// removeCallEdgeFor - This method removes the edge in the node for the
     186             : /// specified call site.  Note that this method takes linear time, so it
     187             : /// should be used sparingly.
     188     1399050 : void CallGraphNode::removeCallEdgeFor(CallSite CS) {
     189             :   for (CalledFunctionsVector::iterator I = CalledFunctions.begin(); ; ++I) {
     190             :     assert(I != CalledFunctions.end() && "Cannot find callsite to remove!");
     191   112850180 :     if (I->first == CS.getInstruction()) {
     192     1399050 :       I->second->DropRef();
     193             :       *I = CalledFunctions.back();
     194     1399050 :       CalledFunctions.pop_back();
     195     1399050 :       return;
     196             :     }
     197             :   }
     198             : }
     199             : 
     200             : // removeAnyCallEdgeTo - This method removes any call edges from this node to
     201             : // the specified callee function.  This takes more time to execute than
     202             : // removeCallEdgeTo, so it should not be used unless necessary.
     203      505665 : void CallGraphNode::removeAnyCallEdgeTo(CallGraphNode *Callee) {
     204   211337373 :   for (unsigned i = 0, e = CalledFunctions.size(); i != e; ++i)
     205   420652086 :     if (CalledFunctions[i].second == Callee) {
     206             :       Callee->DropRef();
     207             :       CalledFunctions[i] = CalledFunctions.back();
     208      505491 :       CalledFunctions.pop_back();
     209      505491 :       --i; --e;
     210             :     }
     211      505665 : }
     212             : 
     213             : /// removeOneAbstractEdgeTo - Remove one edge associated with a null callsite
     214             : /// from this node to the specified callee function.
     215           0 : void CallGraphNode::removeOneAbstractEdgeTo(CallGraphNode *Callee) {
     216             :   for (CalledFunctionsVector::iterator I = CalledFunctions.begin(); ; ++I) {
     217             :     assert(I != CalledFunctions.end() && "Cannot find callee to remove!");
     218             :     CallRecord &CR = *I;
     219           0 :     if (CR.second == Callee && CR.first == nullptr) {
     220             :       Callee->DropRef();
     221             :       *I = CalledFunctions.back();
     222           0 :       CalledFunctions.pop_back();
     223           0 :       return;
     224             :     }
     225             :   }
     226             : }
     227             : 
     228             : /// replaceCallEdge - This method replaces the edge in the node for the
     229             : /// specified call site with a new one.  Note that this method takes linear
     230             : /// time, so it should be used sparingly.
     231         169 : void CallGraphNode::replaceCallEdge(CallSite CS,
     232             :                                     CallSite NewCS, CallGraphNode *NewNode){
     233             :   for (CalledFunctionsVector::iterator I = CalledFunctions.begin(); ; ++I) {
     234             :     assert(I != CalledFunctions.end() && "Cannot find callsite to remove!");
     235        1163 :     if (I->first == CS.getInstruction()) {
     236         169 :       I->second->DropRef();
     237             :       I->first = NewCS.getInstruction();
     238         169 :       I->second = NewNode;
     239             :       NewNode->AddRef();
     240         169 :       return;
     241             :     }
     242             :   }
     243             : }
     244             : 
     245             : // Provide an explicit template instantiation for the static ID.
     246             : AnalysisKey CallGraphAnalysis::Key;
     247             : 
     248           1 : PreservedAnalyses CallGraphPrinterPass::run(Module &M,
     249             :                                             ModuleAnalysisManager &AM) {
     250           1 :   AM.getResult<CallGraphAnalysis>(M).print(OS);
     251           1 :   return PreservedAnalyses::all();
     252             : }
     253             : 
     254             : //===----------------------------------------------------------------------===//
     255             : // Out-of-line definitions of CallGraphAnalysis class members.
     256             : //
     257             : 
     258             : //===----------------------------------------------------------------------===//
     259             : // Implementations of the CallGraphWrapperPass class methods.
     260             : //
     261             : 
     262       47642 : CallGraphWrapperPass::CallGraphWrapperPass() : ModulePass(ID) {
     263       23821 :   initializeCallGraphWrapperPassPass(*PassRegistry::getPassRegistry());
     264       23821 : }
     265             : 
     266             : CallGraphWrapperPass::~CallGraphWrapperPass() = default;
     267             : 
     268       23821 : void CallGraphWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
     269             :   AU.setPreservesAll();
     270       23821 : }
     271             : 
     272       23795 : bool CallGraphWrapperPass::runOnModule(Module &M) {
     273             :   // All the real work is done in the constructor for the CallGraph.
     274       23795 :   G.reset(new CallGraph(M));
     275       23795 :   return false;
     276             : }
     277             : 
     278      387429 : INITIALIZE_PASS(CallGraphWrapperPass, "basiccg", "CallGraph Construction",
     279             :                 false, true)
     280             : 
     281             : char CallGraphWrapperPass::ID = 0;
     282             : 
     283       23786 : void CallGraphWrapperPass::releaseMemory() { G.reset(); }
     284             : 
     285           5 : void CallGraphWrapperPass::print(raw_ostream &OS, const Module *) const {
     286           5 :   if (!G) {
     287           0 :     OS << "No call graph has been built!\n";
     288           0 :     return;
     289             :   }
     290             : 
     291             :   // Just delegate.
     292           5 :   G->print(OS);
     293             : }
     294             : 
     295             : #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
     296             : LLVM_DUMP_METHOD
     297             : void CallGraphWrapperPass::dump() const { print(dbgs(), nullptr); }
     298             : #endif
     299             : 
     300             : namespace {
     301             : 
     302             : struct CallGraphPrinterLegacyPass : public ModulePass {
     303             :   static char ID; // Pass ID, replacement for typeid
     304             : 
     305           5 :   CallGraphPrinterLegacyPass() : ModulePass(ID) {
     306           5 :     initializeCallGraphPrinterLegacyPassPass(*PassRegistry::getPassRegistry());
     307             :   }
     308             : 
     309           5 :   void getAnalysisUsage(AnalysisUsage &AU) const override {
     310             :     AU.setPreservesAll();
     311             :     AU.addRequiredTransitive<CallGraphWrapperPass>();
     312           5 :   }
     313             : 
     314           5 :   bool runOnModule(Module &M) override {
     315           5 :     getAnalysis<CallGraphWrapperPass>().print(errs(), &M);
     316           5 :     return false;
     317             :   }
     318             : };
     319             : 
     320             : } // end anonymous namespace
     321             : 
     322             : char CallGraphPrinterLegacyPass::ID = 0;
     323             : 
     324       10756 : INITIALIZE_PASS_BEGIN(CallGraphPrinterLegacyPass, "print-callgraph",
     325             :                       "Print a call graph", true, true)
     326       10756 : INITIALIZE_PASS_DEPENDENCY(CallGraphWrapperPass)
     327       21517 : INITIALIZE_PASS_END(CallGraphPrinterLegacyPass, "print-callgraph",
     328             :                     "Print a call graph", true, true)

Generated by: LCOV version 1.13