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