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