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