lib/Analysis/CallGraph.cpp

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