LCOV - code coverage report
Current view: top level - lib/Analysis - CallGraph.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 121 137 88.3 %
Date: 2017-09-14 15:23:50 Functions: 25 28 89.3 %
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/IR/CallSite.h"
      14             : #include "llvm/IR/Module.h"
      15             : #include "llvm/IR/Function.h"
      16             : #include "llvm/IR/Intrinsics.h"
      17             : #include "llvm/IR/PassManager.h"
      18             : #include "llvm/Pass.h"
      19             : #include "llvm/Support/Compiler.h"
      20             : #include "llvm/Support/Debug.h"
      21             : #include "llvm/Support/raw_ostream.h"
      22             : #include <algorithm>
      23             : #include <cassert>
      24             : 
      25             : using namespace llvm;
      26             : 
      27             : //===----------------------------------------------------------------------===//
      28             : // Implementations of the CallGraph class methods.
      29             : //
      30             : 
      31       11174 : CallGraph::CallGraph(Module &M)
      32       11174 :     : M(M), ExternalCallingNode(getOrInsertFunction(nullptr)),
      33       33522 :       CallsExternalNode(llvm::make_unique<CallGraphNode>(nullptr)) {
      34             :   // Add every function to the call graph.
      35      223381 :   for (Function &F : M)
      36      189859 :     addToCallGraph(&F);
      37       11174 : }
      38             : 
      39         182 : CallGraph::CallGraph(CallGraph &&Arg)
      40         364 :     : M(Arg.M), FunctionMap(std::move(Arg.FunctionMap)),
      41         182 :       ExternalCallingNode(Arg.ExternalCallingNode),
      42         728 :       CallsExternalNode(std::move(Arg.CallsExternalNode)) {
      43         364 :   Arg.FunctionMap.clear();
      44         182 :   Arg.ExternalCallingNode = nullptr;
      45         182 : }
      46             : 
      47       34044 : CallGraph::~CallGraph() {
      48             :   // CallsExternalNode is not in the function map, delete it explicitly.
      49       22696 :   if (CallsExternalNode)
      50       22332 :     CallsExternalNode->allReferencesDropped();
      51             : 
      52             : // Reset all node's use counts to zero before deleting them to prevent an
      53             : // assertion from firing.
      54             : #ifndef NDEBUG
      55             :   for (auto &I : FunctionMap)
      56             :     I.second->allReferencesDropped();
      57             : #endif
      58       11348 : }
      59             : 
      60      189859 : void CallGraph::addToCallGraph(Function *F) {
      61      189859 :   CallGraphNode *Node = getOrInsertFunction(F);
      62             : 
      63             :   // If this function has external linkage or has its address taken, anything
      64             :   // could call it.
      65      220771 :   if (!F->hasLocalLinkage() || F->hasAddressTaken())
      66      496437 :     ExternalCallingNode->addCalledFunction(CallSite(), Node);
      67             : 
      68             :   // If this function is not defined in this translation unit, it could call
      69             :   // anything.
      70      232372 :   if (F->isDeclaration() && !F->isIntrinsic())
      71       94024 :     Node->addCalledFunction(CallSite(), CallsExternalNode.get());
      72             : 
      73             :   // Look for calls by this function.
      74      957287 :   for (BasicBlock &BB : *F)
      75     4892379 :     for (Instruction &I : BB) {
      76     7458498 :       if (auto CS = CallSite(&I)) {
      77      634863 :         const Function *Callee = CS.getCalledFunction();
      78      634863 :         if (!Callee || !Intrinsic::isLeaf(Callee->getIntrinsicID()))
      79             :           // Indirect calls of intrinsics are not allowed so no need to check.
      80             :           // We can be more precise here by using TargetArg returned by
      81             :           // Intrinsic::isLeaf.
      82       15840 :           Node->addCalledFunction(CS, CallsExternalNode.get());
      83      634853 :         else if (!Callee->isIntrinsic())
      84      429852 :           Node->addCalledFunction(CS, getOrInsertFunction(Callee));
      85             :       }
      86             :     }
      87      189859 : }
      88             : 
      89           6 : void CallGraph::print(raw_ostream &OS) const {
      90             :   // Print in a deterministic order by sorting CallGraphNodes by name.  We do
      91             :   // this here to avoid slowing down the non-printing fast path.
      92             : 
      93          12 :   SmallVector<CallGraphNode *, 16> Nodes;
      94          12 :   Nodes.reserve(FunctionMap.size());
      95             : 
      96          37 :   for (const auto &I : *this)
      97          38 :     Nodes.push_back(I.second.get());
      98             : 
      99          18 :   std::sort(Nodes.begin(), Nodes.end(),
     100          38 :             [](CallGraphNode *LHS, CallGraphNode *RHS) {
     101          38 :     if (Function *LF = LHS->getFunction())
     102          38 :       if (Function *RF = RHS->getFunction())
     103          13 :         return LF->getName() < RF->getName();
     104             : 
     105          25 :     return RHS->getFunction() != nullptr;
     106             :   });
     107             : 
     108          37 :   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       38312 : Function *CallGraph::removeFunctionFromModule(CallGraphNode *CGN) {
     123             :   assert(CGN->empty() && "Cannot remove function from call "
     124             :          "graph if it references other functions!");
     125       38312 :   Function *F = CGN->getFunction(); // Get the function for the call graph node
     126       76624 :   FunctionMap.erase(F);             // Remove the call graph node from the map
     127             : 
     128       76624 :   M.getFunctionList().remove(F);
     129       38312 :   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           0 :   FunctionMapTy::iterator I = FunctionMap.find(From);
     141           0 :   I->second->F = const_cast<Function*>(To);
     142           0 :   FunctionMap[To] = std::move(I->second);
     143           0 :   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      631614 : CallGraphNode *CallGraph::getOrInsertFunction(const Function *F) {
     150      631614 :   auto &CGN = FunctionMap[F];
     151      631614 :   if (CGN)
     152             :     return CGN.get();
     153             : 
     154             :   assert((!F || F->getParent() == &M) && "Function not in current module!");
     155      402350 :   CGN = llvm::make_unique<CallGraphNode>(const_cast<Function *>(F));
     156      201175 :   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          57 :   OS << "<<" << this << ">>  #uses=" << getNumReferences() << '\n';
     170             : 
     171          93 :   for (const auto &I : *this) {
     172          34 :     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          19 :   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       88287 : void CallGraphNode::removeCallEdgeFor(CallSite CS) {
     189      176574 :   for (CalledFunctionsVector::iterator I = CalledFunctions.begin(); ; ++I) {
     190             :     assert(I != CalledFunctions.end() && "Cannot find callsite to remove!");
     191    11660457 :     if (I->first == CS.getInstruction()) {
     192       88287 :       I->second->DropRef();
     193      264861 :       *I = CalledFunctions.back();
     194       88287 :       CalledFunctions.pop_back();
     195       88287 :       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       18220 : void CallGraphNode::removeAnyCallEdgeTo(CallGraphNode *Callee) {
     204    11328619 :   for (unsigned i = 0, e = CalledFunctions.size(); i != e; ++i)
     205    22584358 :     if (CalledFunctions[i].second == Callee) {
     206       18202 :       Callee->DropRef();
     207       54606 :       CalledFunctions[i] = CalledFunctions.back();
     208       18202 :       CalledFunctions.pop_back();
     209       18202 :       --i; --e;
     210             :     }
     211       18220 : }
     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           0 :   for (CalledFunctionsVector::iterator I = CalledFunctions.begin(); ; ++I) {
     217             :     assert(I != CalledFunctions.end() && "Cannot find callee to remove!");
     218           0 :     CallRecord &CR = *I;
     219           0 :     if (CR.second == Callee && CR.first == nullptr) {
     220           0 :       Callee->DropRef();
     221           0 :       *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          94 : void CallGraphNode::replaceCallEdge(CallSite CS,
     232             :                                     CallSite NewCS, CallGraphNode *NewNode){
     233         188 :   for (CalledFunctionsVector::iterator I = CalledFunctions.begin(); ; ++I) {
     234             :     assert(I != CalledFunctions.end() && "Cannot find callsite to remove!");
     235         786 :     if (I->first == CS.getInstruction()) {
     236         188 :       I->second->DropRef();
     237         188 :       I->first = NewCS.getInstruction();
     238          94 :       I->second = NewNode;
     239          94 :       NewNode->AddRef();
     240          94 :       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       33240 : CallGraphWrapperPass::CallGraphWrapperPass() : ModulePass(ID) {
     263       11080 :   initializeCallGraphWrapperPassPass(*PassRegistry::getPassRegistry());
     264       11080 : }
     265             : 
     266             : CallGraphWrapperPass::~CallGraphWrapperPass() = default;
     267             : 
     268       11080 : void CallGraphWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
     269       11080 :   AU.setPreservesAll();
     270       11080 : }
     271             : 
     272       11080 : bool CallGraphWrapperPass::runOnModule(Module &M) {
     273             :   // All the real work is done in the constructor for the CallGraph.
     274       22160 :   G.reset(new CallGraph(M));
     275       11080 :   return false;
     276             : }
     277             : 
     278      550058 : INITIALIZE_PASS(CallGraphWrapperPass, "basiccg", "CallGraph Construction",
     279             :                 false, true)
     280             : 
     281             : char CallGraphWrapperPass::ID = 0;
     282             : 
     283       22144 : void CallGraphWrapperPass::releaseMemory() { G.reset(); }
     284             : 
     285           5 : void CallGraphWrapperPass::print(raw_ostream &OS, const Module *) const {
     286          10 :   if (!G) {
     287           0 :     OS << "No call graph has been built!\n";
     288           0 :     return;
     289             :   }
     290             : 
     291             :   // Just delegate.
     292          10 :   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           5 : struct CallGraphPrinterLegacyPass : public ModulePass {
     303             :   static char ID; // Pass ID, replacement for typeid
     304             : 
     305          10 :   CallGraphPrinterLegacyPass() : ModulePass(ID) {
     306           5 :     initializeCallGraphPrinterLegacyPassPass(*PassRegistry::getPassRegistry());
     307             :   }
     308             : 
     309           5 :   void getAnalysisUsage(AnalysisUsage &AU) const override {
     310          10 :     AU.setPreservesAll();
     311           5 :     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        9158 : INITIALIZE_PASS_BEGIN(CallGraphPrinterLegacyPass, "print-callgraph",
     325             :                       "Print a call graph", true, true)
     326        9158 : INITIALIZE_PASS_DEPENDENCY(CallGraphWrapperPass)
     327       45805 : INITIALIZE_PASS_END(CallGraphPrinterLegacyPass, "print-callgraph",
     328             :                     "Print a call graph", true, true)

Generated by: LCOV version 1.13