LCOV - code coverage report
Current view: top level - lib/Analysis - CallGraph.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 103 113 91.2 %
Date: 2018-06-17 00:07:59 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/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       18980 : CallGraph::CallGraph(Module &M)
      33       18980 :     : M(M), ExternalCallingNode(getOrInsertFunction(nullptr)),
      34       37960 :       CallsExternalNode(llvm::make_unique<CallGraphNode>(nullptr)) {
      35             :   // Add every function to the call graph.
      36      333020 :   for (Function &F : M)
      37      314040 :     addToCallGraph(&F);
      38       18980 : }
      39             : 
      40         230 : CallGraph::CallGraph(CallGraph &&Arg)
      41         230 :     : M(Arg.M), FunctionMap(std::move(Arg.FunctionMap)),
      42         230 :       ExternalCallingNode(Arg.ExternalCallingNode),
      43         460 :       CallsExternalNode(std::move(Arg.CallsExternalNode)) {
      44             :   Arg.FunctionMap.clear();
      45         230 :   Arg.ExternalCallingNode = nullptr;
      46         230 : }
      47             : 
      48       57606 : CallGraph::~CallGraph() {
      49             :   // CallsExternalNode is not in the function map, delete it explicitly.
      50       19202 :   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       19202 : }
      60             : 
      61      314040 : void CallGraph::addToCallGraph(Function *F) {
      62      314040 :   CallGraphNode *Node = getOrInsertFunction(F);
      63             : 
      64             :   // If this function has external linkage or has its address taken, anything
      65             :   // could call it.
      66       46954 :   if (!F->hasLocalLinkage() || F->hasAddressTaken())
      67      281691 :     ExternalCallingNode->addCalledFunction(CallSite(), Node);
      68             : 
      69             :   // If this function is not defined in this translation unit, it could call
      70             :   // anything.
      71      390239 :   if (F->isDeclaration() && !F->isIntrinsic())
      72             :     Node->addCalledFunction(CallSite(), CallsExternalNode.get());
      73             : 
      74             :   // Look for calls by this function.
      75     1056779 :   for (BasicBlock &BB : *F)
      76     7632634 :     for (Instruction &I : BB) {
      77     6889895 :       if (auto CS = CallSite(&I)) {
      78             :         const Function *Callee = CS.getCalledFunction();
      79     1035449 :         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             :           Node->addCalledFunction(CS, CallsExternalNode.get());
      84     1035435 :         else if (!Callee->isIntrinsic())
      85      625195 :           Node->addCalledFunction(CS, getOrInsertFunction(Callee));
      86             :       }
      87             :     }
      88      314040 : }
      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           6 :   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.begin(), Nodes.end(),
     101          38 :              [](CallGraphNode *LHS, CallGraphNode *RHS) {
     102          38 :     if (Function *LF = LHS->getFunction())
     103          38 :       if (Function *RF = RHS->getFunction())
     104          13 :         return LF->getName() < RF->getName();
     105             : 
     106          25 :     return RHS->getFunction() != nullptr;
     107             :   });
     108             : 
     109          44 :   for (CallGraphNode *CN : Nodes)
     110          19 :     CN->print(OS);
     111           6 : }
     112             : 
     113             : #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
     114             : LLVM_DUMP_METHOD void CallGraph::dump() const { print(dbgs()); }
     115             : #endif
     116             : 
     117             : // removeFunctionFromModule - Unlink the function from this module, returning
     118             : // it.  Because this removes the function from the module, the call graph node
     119             : // is destroyed.  This is only valid if the function does not call any other
     120             : // functions (ie, there are no edges in it's CGN).  The easiest way to do this
     121             : // is to dropAllReferences before calling this.
     122             : //
     123       41424 : Function *CallGraph::removeFunctionFromModule(CallGraphNode *CGN) {
     124             :   assert(CGN->empty() && "Cannot remove function from call "
     125             :          "graph if it references other functions!");
     126       41424 :   Function *F = CGN->getFunction(); // Get the function for the call graph node
     127       82848 :   FunctionMap.erase(F);             // Remove the call graph node from the map
     128             : 
     129       41424 :   M.getFunctionList().remove(F);
     130       41424 :   return F;
     131             : }
     132             : 
     133             : /// spliceFunction - Replace the function represented by this node by another.
     134             : /// This does not rescan the body of the function, so it is suitable when
     135             : /// splicing the body of the old function to the new while also updating all
     136             : /// callers from old to new.
     137           0 : void CallGraph::spliceFunction(const Function *From, const Function *To) {
     138             :   assert(FunctionMap.count(From) && "No CallGraphNode for function!");
     139             :   assert(!FunctionMap.count(To) &&
     140             :          "Pointing CallGraphNode at a function that already exists");
     141             :   FunctionMapTy::iterator I = FunctionMap.find(From);
     142           0 :   I->second->F = const_cast<Function*>(To);
     143           0 :   FunctionMap[To] = std::move(I->second);
     144             :   FunctionMap.erase(I);
     145           0 : }
     146             : 
     147             : // getOrInsertFunction - This method is identical to calling operator[], but
     148             : // it will insert a new CallGraphNode for the specified function if one does
     149             : // not already exist.
     150      959002 : CallGraphNode *CallGraph::getOrInsertFunction(const Function *F) {
     151      959002 :   auto &CGN = FunctionMap[F];
     152      959002 :   if (CGN)
     153             :     return CGN.get();
     154             : 
     155             :   assert((!F || F->getParent() == &M) && "Function not in current module!");
     156      666352 :   CGN = llvm::make_unique<CallGraphNode>(const_cast<Function *>(F));
     157      333176 :   return CGN.get();
     158             : }
     159             : 
     160             : //===----------------------------------------------------------------------===//
     161             : // Implementations of the CallGraphNode class methods.
     162             : //
     163             : 
     164          19 : void CallGraphNode::print(raw_ostream &OS) const {
     165          19 :   if (Function *F = getFunction())
     166          13 :     OS << "Call graph node for function: '" << F->getName() << "'";
     167             :   else
     168           6 :     OS << "Call graph node <<null function>>";
     169             :   
     170          19 :   OS << "<<" << this << ">>  #uses=" << getNumReferences() << '\n';
     171             : 
     172          36 :   for (const auto &I : *this) {
     173          34 :     OS << "  CS<" << I.first << "> calls ";
     174          17 :     if (Function *FI = I.second->getFunction())
     175          14 :       OS << "function '" << FI->getName() <<"'\n";
     176             :     else
     177           3 :       OS << "external node\n";
     178             :   }
     179             :   OS << '\n';
     180          19 : }
     181             : 
     182             : #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
     183             : LLVM_DUMP_METHOD void CallGraphNode::dump() const { print(dbgs()); }
     184             : #endif
     185             : 
     186             : /// removeCallEdgeFor - This method removes the edge in the node for the
     187             : /// specified call site.  Note that this method takes linear time, so it
     188             : /// should be used sparingly.
     189       95053 : void CallGraphNode::removeCallEdgeFor(CallSite CS) {
     190             :   for (CalledFunctionsVector::iterator I = CalledFunctions.begin(); ; ++I) {
     191             :     assert(I != CalledFunctions.end() && "Cannot find callsite to remove!");
     192     4002090 :     if (I->first == CS.getInstruction()) {
     193       95053 :       I->second->DropRef();
     194             :       *I = CalledFunctions.back();
     195       95053 :       CalledFunctions.pop_back();
     196       95053 :       return;
     197             :     }
     198             :   }
     199             : }
     200             : 
     201             : // removeAnyCallEdgeTo - This method removes any call edges from this node to
     202             : // the specified callee function.  This takes more time to execute than
     203             : // removeCallEdgeTo, so it should not be used unless necessary.
     204       21629 : void CallGraphNode::removeAnyCallEdgeTo(CallGraphNode *Callee) {
     205    14225631 :   for (unsigned i = 0, e = CalledFunctions.size(); i != e; ++i)
     206    28364746 :     if (CalledFunctions[i].second == Callee) {
     207             :       Callee->DropRef();
     208             :       CalledFunctions[i] = CalledFunctions.back();
     209       21585 :       CalledFunctions.pop_back();
     210       21585 :       --i; --e;
     211             :     }
     212       21629 : }
     213             : 
     214             : /// removeOneAbstractEdgeTo - Remove one edge associated with a null callsite
     215             : /// from this node to the specified callee function.
     216           0 : void CallGraphNode::removeOneAbstractEdgeTo(CallGraphNode *Callee) {
     217             :   for (CalledFunctionsVector::iterator I = CalledFunctions.begin(); ; ++I) {
     218             :     assert(I != CalledFunctions.end() && "Cannot find callee to remove!");
     219             :     CallRecord &CR = *I;
     220           0 :     if (CR.second == Callee && CR.first == nullptr) {
     221             :       Callee->DropRef();
     222             :       *I = CalledFunctions.back();
     223           0 :       CalledFunctions.pop_back();
     224           0 :       return;
     225             :     }
     226             :   }
     227             : }
     228             : 
     229             : /// replaceCallEdge - This method replaces the edge in the node for the
     230             : /// specified call site with a new one.  Note that this method takes linear
     231             : /// time, so it should be used sparingly.
     232          96 : void CallGraphNode::replaceCallEdge(CallSite CS,
     233             :                                     CallSite NewCS, CallGraphNode *NewNode){
     234             :   for (CalledFunctionsVector::iterator I = CalledFunctions.begin(); ; ++I) {
     235             :     assert(I != CalledFunctions.end() && "Cannot find callsite to remove!");
     236         263 :     if (I->first == CS.getInstruction()) {
     237          96 :       I->second->DropRef();
     238             :       I->first = NewCS.getInstruction();
     239          96 :       I->second = NewNode;
     240             :       NewNode->AddRef();
     241          96 :       return;
     242             :     }
     243             :   }
     244             : }
     245             : 
     246             : // Provide an explicit template instantiation for the static ID.
     247             : AnalysisKey CallGraphAnalysis::Key;
     248             : 
     249           1 : PreservedAnalyses CallGraphPrinterPass::run(Module &M,
     250             :                                             ModuleAnalysisManager &AM) {
     251           1 :   AM.getResult<CallGraphAnalysis>(M).print(OS);
     252           1 :   return PreservedAnalyses::all();
     253             : }
     254             : 
     255             : //===----------------------------------------------------------------------===//
     256             : // Out-of-line definitions of CallGraphAnalysis class members.
     257             : //
     258             : 
     259             : //===----------------------------------------------------------------------===//
     260             : // Implementations of the CallGraphWrapperPass class methods.
     261             : //
     262             : 
     263       37718 : CallGraphWrapperPass::CallGraphWrapperPass() : ModulePass(ID) {
     264       18859 :   initializeCallGraphWrapperPassPass(*PassRegistry::getPassRegistry());
     265       18859 : }
     266             : 
     267             : CallGraphWrapperPass::~CallGraphWrapperPass() = default;
     268             : 
     269       18859 : void CallGraphWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
     270             :   AU.setPreservesAll();
     271       18859 : }
     272             : 
     273       18859 : bool CallGraphWrapperPass::runOnModule(Module &M) {
     274             :   // All the real work is done in the constructor for the CallGraph.
     275       18859 :   G.reset(new CallGraph(M));
     276       18859 :   return false;
     277             : }
     278             : 
     279      694432 : INITIALIZE_PASS(CallGraphWrapperPass, "basiccg", "CallGraph Construction",
     280             :                 false, true)
     281             : 
     282             : char CallGraphWrapperPass::ID = 0;
     283             : 
     284       37702 : void CallGraphWrapperPass::releaseMemory() { G.reset(); }
     285             : 
     286           5 : void CallGraphWrapperPass::print(raw_ostream &OS, const Module *) const {
     287           5 :   if (!G) {
     288           0 :     OS << "No call graph has been built!\n";
     289           0 :     return;
     290             :   }
     291             : 
     292             :   // Just delegate.
     293           5 :   G->print(OS);
     294             : }
     295             : 
     296             : #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
     297             : LLVM_DUMP_METHOD
     298             : void CallGraphWrapperPass::dump() const { print(dbgs(), nullptr); }
     299             : #endif
     300             : 
     301             : namespace {
     302             : 
     303           5 : struct CallGraphPrinterLegacyPass : public ModulePass {
     304             :   static char ID; // Pass ID, replacement for typeid
     305             : 
     306           5 :   CallGraphPrinterLegacyPass() : ModulePass(ID) {
     307           5 :     initializeCallGraphPrinterLegacyPassPass(*PassRegistry::getPassRegistry());
     308             :   }
     309             : 
     310           5 :   void getAnalysisUsage(AnalysisUsage &AU) const override {
     311             :     AU.setPreservesAll();
     312             :     AU.addRequiredTransitive<CallGraphWrapperPass>();
     313           5 :   }
     314             : 
     315           5 :   bool runOnModule(Module &M) override {
     316           5 :     getAnalysis<CallGraphWrapperPass>().print(errs(), &M);
     317           5 :     return false;
     318             :   }
     319             : };
     320             : 
     321             : } // end anonymous namespace
     322             : 
     323             : char CallGraphPrinterLegacyPass::ID = 0;
     324             : 
     325       10264 : INITIALIZE_PASS_BEGIN(CallGraphPrinterLegacyPass, "print-callgraph",
     326             :                       "Print a call graph", true, true)
     327       10264 : INITIALIZE_PASS_DEPENDENCY(CallGraphWrapperPass)
     328       41066 : INITIALIZE_PASS_END(CallGraphPrinterLegacyPass, "print-callgraph",
     329             :                     "Print a call graph", true, true)

Generated by: LCOV version 1.13