contrib/llvm/lib/Analysis/CallGraph.cpp

   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 CallGraph::CallGraph(Module &M)
  33     : M(M), ExternalCallingNode(getOrInsertFunction(nullptr)),
  34       CallsExternalNode(llvm::make_unique<CallGraphNode>(nullptr)) {
  35   // Add every function to the call graph.
  36   for (Function &F : M)
  37     addToCallGraph(&F);
  38 }
  39
  40 CallGraph::CallGraph(CallGraph &&Arg)
  41     : M(Arg.M), FunctionMap(std::move(Arg.FunctionMap)),
  42       ExternalCallingNode(Arg.ExternalCallingNode),
  43       CallsExternalNode(std::move(Arg.CallsExternalNode)) {
  44   Arg.FunctionMap.clear();
  45   Arg.ExternalCallingNode = nullptr;
  46 }
  47
  48 CallGraph::~CallGraph() {
  49   // CallsExternalNode is not in the function map, delete it explicitly.
  50   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 }
  60
  61 void CallGraph::addToCallGraph(Function *F) {
  62   CallGraphNode *Node = getOrInsertFunction(F);
  63
  64   // If this function has external linkage or has its address taken, anything
  65   // could call it.
  66   if (!F->hasLocalLinkage() || F->hasAddressTaken())
  67     ExternalCallingNode->addCalledFunction(CallSite(), Node);
  68
  69   // If this function is not defined in this translation unit, it could call
  70   // anything.
  71   if (F->isDeclaration() && !F->isIntrinsic())
  72     Node->addCalledFunction(CallSite(), CallsExternalNode.get());
  73
  74   // Look for calls by this function.
  75   for (BasicBlock &BB : *F)
  76     for (Instruction &I : BB) {
  77       if (auto CS = CallSite(&I)) {
  78         const Function *Callee = CS.getCalledFunction();
  79         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         else if (!Callee->isIntrinsic())
  85           Node->addCalledFunction(CS, getOrInsertFunction(Callee));
  86       }
  87     }
  88 }
  89
  90 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   for (const auto &I : *this)
  98     Nodes.push_back(I.second.get());
  99
 100   llvm::sort(Nodes.begin(), Nodes.end(),
 101              [](CallGraphNode *LHS, CallGraphNode *RHS) {
 102     if (Function *LF = LHS->getFunction())
 103       if (Function *RF = RHS->getFunction())
 104         return LF->getName() < RF->getName();
 105
 106     return RHS->getFunction() != nullptr;
 107   });
 108
 109   for (CallGraphNode *CN : Nodes)
 110     CN->print(OS);
 111 }
 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 Function *CallGraph::removeFunctionFromModule(CallGraphNode *CGN) {
 124   assert(CGN->empty() && "Cannot remove function from call "
 125          "graph if it references other functions!");
 126   Function *F = CGN->getFunction(); // Get the function for the call graph node
 127   FunctionMap.erase(F);             // Remove the call graph node from the map
 128
 129   M.getFunctionList().remove(F);
 130   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 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   I->second->F = const_cast<Function*>(To);
 143   FunctionMap[To] = std::move(I->second);
 144   FunctionMap.erase(I);
 145 }
 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 CallGraphNode *CallGraph::getOrInsertFunction(const Function *F) {
 151   auto &CGN = FunctionMap[F];
 152   if (CGN)
 153     return CGN.get();
 154
 155   assert((!F || F->getParent() == &M) && "Function not in current module!");
 156   CGN = llvm::make_unique<CallGraphNode>(const_cast<Function *>(F));
 157   return CGN.get();
 158 }
 159
 160 //===----------------------------------------------------------------------===//
 161 // Implementations of the CallGraphNode class methods.
 162 //
 163
 164 void CallGraphNode::print(raw_ostream &OS) const {
 165   if (Function *F = getFunction())
 166     OS << "Call graph node for function: '" << F->getName() << "'";
 167   else
 168     OS << "Call graph node <<null function>>";
 169
 170   OS << "<<" << this << ">>  #uses=" << getNumReferences() << '\n';
 171
 172   for (const auto &I : *this) {
 173     OS << "  CS<" << I.first << "> calls ";
 174     if (Function *FI = I.second->getFunction())
 175       OS << "function '" << FI->getName() <<"'\n";
 176     else
 177       OS << "external node\n";
 178   }
 179   OS << '\n';
 180 }
 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 void CallGraphNode::removeCallEdgeFor(CallSite CS) {
 190   for (CalledFunctionsVector::iterator I = CalledFunctions.begin(); ; ++I) {
 191     assert(I != CalledFunctions.end() && "Cannot find callsite to remove!");
 192     if (I->first == CS.getInstruction()) {
 193       I->second->DropRef();
 194       *I = CalledFunctions.back();
 195       CalledFunctions.pop_back();
 196       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 void CallGraphNode::removeAnyCallEdgeTo(CallGraphNode *Callee) {
 205   for (unsigned i = 0, e = CalledFunctions.size(); i != e; ++i)
 206     if (CalledFunctions[i].second == Callee) {
 207       Callee->DropRef();
 208       CalledFunctions[i] = CalledFunctions.back();
 209       CalledFunctions.pop_back();
 210       --i; --e;
 211     }
 212 }
 213
 214 /// removeOneAbstractEdgeTo - Remove one edge associated with a null callsite
 215 /// from this node to the specified callee function.
 216 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     if (CR.second == Callee && CR.first == nullptr) {
 221       Callee->DropRef();
 222       *I = CalledFunctions.back();
 223       CalledFunctions.pop_back();
 224       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 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     if (I->first == CS.getInstruction()) {
 237       I->second->DropRef();
 238       I->first = NewCS.getInstruction();
 239       I->second = NewNode;
 240       NewNode->AddRef();
 241       return;
 242     }
 243   }
 244 }
 245
 246 // Provide an explicit template instantiation for the static ID.
 247 AnalysisKey CallGraphAnalysis::Key;
 248
 249 PreservedAnalyses CallGraphPrinterPass::run(Module &M,
 250                                             ModuleAnalysisManager &AM) {
 251   AM.getResult<CallGraphAnalysis>(M).print(OS);
 252   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 CallGraphWrapperPass::CallGraphWrapperPass() : ModulePass(ID) {
 264   initializeCallGraphWrapperPassPass(*PassRegistry::getPassRegistry());
 265 }
 266
 267 CallGraphWrapperPass::~CallGraphWrapperPass() = default;
 268
 269 void CallGraphWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
 270   AU.setPreservesAll();
 271 }
 272
 273 bool CallGraphWrapperPass::runOnModule(Module &M) {
 274   // All the real work is done in the constructor for the CallGraph.
 275   G.reset(new CallGraph(M));
 276   return false;
 277 }
 278
 279 INITIALIZE_PASS(CallGraphWrapperPass, "basiccg", "CallGraph Construction",
 280                 false, true)
 281
 282 char CallGraphWrapperPass::ID = 0;
 283
 284 void CallGraphWrapperPass::releaseMemory() { G.reset(); }
 285
 286 void CallGraphWrapperPass::print(raw_ostream &OS, const Module *) const {
 287   if (!G) {
 288     OS << "No call graph has been built!\n";
 289     return;
 290   }
 291
 292   // Just delegate.
 293   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 struct CallGraphPrinterLegacyPass : public ModulePass {
 304   static char ID; // Pass ID, replacement for typeid
 305
 306   CallGraphPrinterLegacyPass() : ModulePass(ID) {
 307     initializeCallGraphPrinterLegacyPassPass(*PassRegistry::getPassRegistry());
 308   }
 309
 310   void getAnalysisUsage(AnalysisUsage &AU) const override {
 311     AU.setPreservesAll();
 312     AU.addRequiredTransitive<CallGraphWrapperPass>();
 313   }
 314
 315   bool runOnModule(Module &M) override {
 316     getAnalysis<CallGraphWrapperPass>().print(errs(), &M);
 317     return false;
 318   }
 319 };
 320
 321 } // end anonymous namespace
 322
 323 char CallGraphPrinterLegacyPass::ID = 0;
 324
 325 INITIALIZE_PASS_BEGIN(CallGraphPrinterLegacyPass, "print-callgraph",
 326                       "Print a call graph", true, true)
 327 INITIALIZE_PASS_DEPENDENCY(CallGraphWrapperPass)
 328 INITIALIZE_PASS_END(CallGraphPrinterLegacyPass, "print-callgraph",
 329                     "Print a call graph", true, true)