lib/Analysis/DataStructure/CallTargets.cpp

   1 //=- lib/Analysis/IPA/CallTargets.cpp - Resolve Call Targets --*- C++ -*-=====//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by the LLVM research group and is distributed under
   6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This pass uses DSA to map targets of all calls, and reports on if it
  11 // thinks it knows all targets of a given call.
  12 //
  13 // Loop over all callsites, and lookup the DSNode for that site.  Pull the
  14 // Functions from the node as callees.
  15 // This is essentially a utility pass to simplify later passes that only depend
  16 // on call sites and callees to operate (such as a devirtualizer).
  17 //
  18 //===----------------------------------------------------------------------===//
  19
  20 #include "llvm/Module.h"
  21 #include "llvm/Instructions.h"
  22 #include "llvm/Analysis/DataStructure/DataStructure.h"
  23 #include "llvm/Analysis/DataStructure/DSGraph.h"
  24 #include "llvm/Analysis/DataStructure/CallTargets.h"
  25 #include "llvm/ADT/Statistic.h"
  26 #include <iostream>
  27 #include "llvm/Constants.h"
  28
  29 using namespace llvm;
  30
  31 namespace {
  32   Statistic<> DirCall("calltarget", "Number of direct calls");
  33   Statistic<> IndCall("calltarget", "Number of indirect calls");
  34   Statistic<> CompleteInd("calltarget", "Number of complete indirect calls");
  35   Statistic<> CompleteEmpty("calltarget", "Number of complete empty calls");
  36
  37   RegisterPass<CallTargetFinder> X("calltarget","Find Call Targets (uses DSA)");
  38 }
  39
  40 void CallTargetFinder::findIndTargets(Module &M)
  41 {
  42   TDDataStructures* T = &getAnalysis<TDDataStructures>();
  43   for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
  44     if (!I->isExternal())
  45       for (Function::iterator F = I->begin(), FE = I->end(); F != FE; ++F)
  46         for (BasicBlock::iterator B = F->begin(), BE = F->end(); B != BE; ++B)
  47           if (isa<CallInst>(B) || isa<InvokeInst>(B)) {
  48             CallSite cs = CallSite::get(B);
  49             AllSites.push_back(cs);
  50             if (!cs.getCalledFunction()) {
  51               IndCall++;
  52               DSNode* N = T->getDSGraph(*cs.getCaller())
  53                 .getNodeForValue(cs.getCalledValue()).getNode();
  54               N->addFullFunctionList(IndMap[cs]);
  55               if (N->isComplete() && IndMap[cs].size()) {
  56                 CompleteSites.insert(cs);
  57                 ++CompleteInd;
  58               }
  59               if (N->isComplete() && !IndMap[cs].size()) {
  60                 ++CompleteEmpty;
  61                 std::cerr << "Call site empty: '"
  62                 << cs.getInstruction()->getName()
  63                           << "' In '"
  64                 << cs.getInstruction()->getParent()->getParent()->getName()
  65                           << "'\n";
  66               }
  67             } else {
  68               ++DirCall;
  69               IndMap[cs].push_back(cs.getCalledFunction());
  70               CompleteSites.insert(cs);
  71             }
  72           }
  73 }
  74
  75 void CallTargetFinder::print(std::ostream &O, const Module *M) const
  76 {
  77   return;
  78   O << "[* = incomplete] CS: func list\n";
  79   for (std::map<CallSite, std::vector<Function*> >::const_iterator ii =
  80        IndMap.begin(),
  81          ee = IndMap.end(); ii != ee; ++ii) {
  82     if (!ii->first.getCalledFunction()) { //only print indirect
  83       if (!isComplete(ii->first)) {
  84         O << "* ";
  85         CallSite cs = ii->first;
  86         cs.getInstruction()->dump();
  87         O << cs.getInstruction()->getParent()->getParent()->getName() << " "
  88           << cs.getInstruction()->getName() << " ";
  89       }
  90       O << ii->first.getInstruction() << ":";
  91       for (std::vector<Function*>::const_iterator i = ii->second.begin(),
  92              e = ii->second.end(); i != e; ++i) {
  93         O << " " << (*i)->getName();
  94       }
  95       O << "\n";
  96     }
  97   }
  98 }
  99
 100 bool CallTargetFinder::runOnModule(Module &M) {
 101   findIndTargets(M);
 102   return false;
 103 }
 104
 105 void CallTargetFinder::getAnalysisUsage(AnalysisUsage &AU) const {
 106   AU.setPreservesAll();
 107   AU.addRequired<TDDataStructures>();
 108 }
 109
 110 std::vector<Function*>::iterator CallTargetFinder::begin(CallSite cs) {
 111   return IndMap[cs].begin();
 112 }
 113
 114 std::vector<Function*>::iterator CallTargetFinder::end(CallSite cs) {
 115   return IndMap[cs].end();
 116 }
 117
 118 bool CallTargetFinder::isComplete(CallSite cs) const {
 119   return CompleteSites.find(cs) != CompleteSites.end();
 120 }
 121
 122 std::list<CallSite>::iterator CallTargetFinder::cs_begin() {
 123   return AllSites.begin();
 124 }
 125
 126 std::list<CallSite>::iterator CallTargetFinder::cs_end() {
 127   return AllSites.end();
 128 }