18d5a16ca0b3d19fdde3d0d453dd16a9c46395345Chris Lattner//===- CallGraph.cpp - Build a Module's call graph ------------------------===// 22b37d7cf28b1382420b5e4007042feeb66d21ac8Misha Brukman// 3b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// The LLVM Compiler Infrastructure 4b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// 54ee451de366474b9c228b4e5fa573795a715216dChris Lattner// This file is distributed under the University of Illinois Open Source 64ee451de366474b9c228b4e5fa573795a715216dChris Lattner// License. See LICENSE.TXT for details. 72b37d7cf28b1382420b5e4007042feeb66d21ac8Misha Brukman// 8b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell//===----------------------------------------------------------------------===// 941fbf305ee3e2c3b8610459e8c09b60e61f4d34dChris Lattner 1041fbf305ee3e2c3b8610459e8c09b60e61f4d34dChris Lattner#include "llvm/Analysis/CallGraph.h" 1136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/IR/CallSite.h" 120b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Instructions.h" 130b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/IntrinsicInst.h" 140b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Module.h" 15265c026fee512f8206050c0b3f956fe072b05b34David Greene#include "llvm/Support/Debug.h" 1645cfe545ec8177262dabc70580ce05feaa1c3880Chris Lattner#include "llvm/Support/raw_ostream.h" 17b81c021f14107b12d1275c84fbce170db06437a5Chris Lattnerusing namespace llvm; 18d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 1936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines//===----------------------------------------------------------------------===// 2036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// Implementations of the CallGraph class methods. 2136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// 2236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 2336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen HinesCallGraph::CallGraph(Module &M) 24dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines : M(M), Root(nullptr), ExternalCallingNode(getOrInsertFunction(nullptr)), 25dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines CallsExternalNode(new CallGraphNode(nullptr)) { 2636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Add every function to the call graph. 2736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) 2836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines addToCallGraph(I); 2936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 3036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // If we didn't find a main function, use the external call graph node 31dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (!Root) 3236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Root = ExternalCallingNode; 3336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines} 3436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 3536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen HinesCallGraph::~CallGraph() { 3636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // CallsExternalNode is not in the function map, delete it explicitly. 3736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines CallsExternalNode->allReferencesDropped(); 3836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines delete CallsExternalNode; 3936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 4036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// Reset all node's use counts to zero before deleting them to prevent an 4136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// assertion from firing. 4236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#ifndef NDEBUG 4336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines for (FunctionMapTy::iterator I = FunctionMap.begin(), E = FunctionMap.end(); 4436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines I != E; ++I) 4536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines I->second->allReferencesDropped(); 4636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#endif 4736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines for (FunctionMapTy::iterator I = FunctionMap.begin(), E = FunctionMap.end(); 4836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines I != E; ++I) 4936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines delete I->second; 50c143c7573bfd0d55cf283cc2676dbd852f939c87Rafael Espindola} 5103839956e2b99348812f4c45fb57649804c77c2dChris Lattner 52c143c7573bfd0d55cf283cc2676dbd852f939c87Rafael Espindolavoid CallGraph::addToCallGraph(Function *F) { 53c143c7573bfd0d55cf283cc2676dbd852f939c87Rafael Espindola CallGraphNode *Node = getOrInsertFunction(F); 5403839956e2b99348812f4c45fb57649804c77c2dChris Lattner 55c143c7573bfd0d55cf283cc2676dbd852f939c87Rafael Espindola // If this function has external linkage, anything could call it. 56c143c7573bfd0d55cf283cc2676dbd852f939c87Rafael Espindola if (!F->hasLocalLinkage()) { 57c143c7573bfd0d55cf283cc2676dbd852f939c87Rafael Espindola ExternalCallingNode->addCalledFunction(CallSite(), Node); 582b37d7cf28b1382420b5e4007042feeb66d21ac8Misha Brukman 59c143c7573bfd0d55cf283cc2676dbd852f939c87Rafael Espindola // Found the entry point? 60c143c7573bfd0d55cf283cc2676dbd852f939c87Rafael Espindola if (F->getName() == "main") { 61c143c7573bfd0d55cf283cc2676dbd852f939c87Rafael Espindola if (Root) // Found multiple external mains? Don't pick one. 62c143c7573bfd0d55cf283cc2676dbd852f939c87Rafael Espindola Root = ExternalCallingNode; 63c143c7573bfd0d55cf283cc2676dbd852f939c87Rafael Espindola else 64c143c7573bfd0d55cf283cc2676dbd852f939c87Rafael Espindola Root = Node; // Found a main, keep track of it! 6545cfe545ec8177262dabc70580ce05feaa1c3880Chris Lattner } 6603839956e2b99348812f4c45fb57649804c77c2dChris Lattner } 6703839956e2b99348812f4c45fb57649804c77c2dChris Lattner 68c143c7573bfd0d55cf283cc2676dbd852f939c87Rafael Espindola // If this function has its address taken, anything could call it. 69c143c7573bfd0d55cf283cc2676dbd852f939c87Rafael Espindola if (F->hasAddressTaken()) 70c143c7573bfd0d55cf283cc2676dbd852f939c87Rafael Espindola ExternalCallingNode->addCalledFunction(CallSite(), Node); 71c143c7573bfd0d55cf283cc2676dbd852f939c87Rafael Espindola 72c143c7573bfd0d55cf283cc2676dbd852f939c87Rafael Espindola // If this function is not defined in this translation unit, it could call 73c143c7573bfd0d55cf283cc2676dbd852f939c87Rafael Espindola // anything. 74c143c7573bfd0d55cf283cc2676dbd852f939c87Rafael Espindola if (F->isDeclaration() && !F->isIntrinsic()) 75c143c7573bfd0d55cf283cc2676dbd852f939c87Rafael Espindola Node->addCalledFunction(CallSite(), CallsExternalNode); 76c143c7573bfd0d55cf283cc2676dbd852f939c87Rafael Espindola 77c143c7573bfd0d55cf283cc2676dbd852f939c87Rafael Espindola // Look for calls by this function. 78c143c7573bfd0d55cf283cc2676dbd852f939c87Rafael Espindola for (Function::iterator BB = F->begin(), BBE = F->end(); BB != BBE; ++BB) 79c143c7573bfd0d55cf283cc2676dbd852f939c87Rafael Espindola for (BasicBlock::iterator II = BB->begin(), IE = BB->end(); II != IE; 80c143c7573bfd0d55cf283cc2676dbd852f939c87Rafael Espindola ++II) { 81c143c7573bfd0d55cf283cc2676dbd852f939c87Rafael Espindola CallSite CS(cast<Value>(II)); 82c143c7573bfd0d55cf283cc2676dbd852f939c87Rafael Espindola if (CS) { 83c143c7573bfd0d55cf283cc2676dbd852f939c87Rafael Espindola const Function *Callee = CS.getCalledFunction(); 84c143c7573bfd0d55cf283cc2676dbd852f939c87Rafael Espindola if (!Callee) 85c143c7573bfd0d55cf283cc2676dbd852f939c87Rafael Espindola // Indirect calls of intrinsics are not allowed so no need to check. 86c143c7573bfd0d55cf283cc2676dbd852f939c87Rafael Espindola Node->addCalledFunction(CS, CallsExternalNode); 87c143c7573bfd0d55cf283cc2676dbd852f939c87Rafael Espindola else if (!Callee->isIntrinsic()) 88c143c7573bfd0d55cf283cc2676dbd852f939c87Rafael Espindola Node->addCalledFunction(CS, getOrInsertFunction(Callee)); 8903839956e2b99348812f4c45fb57649804c77c2dChris Lattner } 9003839956e2b99348812f4c45fb57649804c77c2dChris Lattner } 91c143c7573bfd0d55cf283cc2676dbd852f939c87Rafael Espindola} 9203839956e2b99348812f4c45fb57649804c77c2dChris Lattner 9336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesvoid CallGraph::print(raw_ostream &OS) const { 94c143c7573bfd0d55cf283cc2676dbd852f939c87Rafael Espindola OS << "CallGraph Root is: "; 95c143c7573bfd0d55cf283cc2676dbd852f939c87Rafael Espindola if (Function *F = Root->getFunction()) 96c143c7573bfd0d55cf283cc2676dbd852f939c87Rafael Espindola OS << F->getName() << "\n"; 97c143c7573bfd0d55cf283cc2676dbd852f939c87Rafael Espindola else { 98c143c7573bfd0d55cf283cc2676dbd852f939c87Rafael Espindola OS << "<<null function: 0x" << Root << ">>\n"; 99c143c7573bfd0d55cf283cc2676dbd852f939c87Rafael Espindola } 100c143c7573bfd0d55cf283cc2676dbd852f939c87Rafael Espindola 10116500158223d4147ae97513bf698d5f321b15889Chris Lattner for (CallGraph::const_iterator I = begin(), E = end(); I != E; ++I) 102af8a42445c99d2d733caf1f9ef3e3b53827613d5Chris Lattner I->second->print(OS); 103af8a42445c99d2d733caf1f9ef3e3b53827613d5Chris Lattner} 10436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 105286c4dc355b8be6806081b23c3097485821c7642Manman Ren#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 10636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesvoid CallGraph::dump() const { print(dbgs()); } 107cc77eece74c8db09acc2af425e7e6c88a5bb30d1Manman Ren#endif 108af8a42445c99d2d733caf1f9ef3e3b53827613d5Chris Lattner 109d99d4d7b70b45d25e7dc91c6e7edb9206509ed39Chris Lattner// removeFunctionFromModule - Unlink the function from this module, returning 110d99d4d7b70b45d25e7dc91c6e7edb9206509ed39Chris Lattner// it. Because this removes the function from the module, the call graph node 111d99d4d7b70b45d25e7dc91c6e7edb9206509ed39Chris Lattner// is destroyed. This is only valid if the function does not call any other 112d99d4d7b70b45d25e7dc91c6e7edb9206509ed39Chris Lattner// functions (ie, there are no edges in it's CGN). The easiest way to do this 11325e9cad236c5ebb0f96f2c213c294616a1d04155Chris Lattner// is to dropAllReferences before calling this. 11425e9cad236c5ebb0f96f2c213c294616a1d04155Chris Lattner// 115d99d4d7b70b45d25e7dc91c6e7edb9206509ed39Chris LattnerFunction *CallGraph::removeFunctionFromModule(CallGraphNode *CGN) { 1162adb8306e2256a4d1bef8f21ebb6dba55a108a88Chris Lattner assert(CGN->empty() && "Cannot remove function from call " 117d99d4d7b70b45d25e7dc91c6e7edb9206509ed39Chris Lattner "graph if it references other functions!"); 1185714c974006d4fe28ddd66d15e9b158493df00b6Chris Lattner Function *F = CGN->getFunction(); // Get the function for the call graph node 119d99d4d7b70b45d25e7dc91c6e7edb9206509ed39Chris Lattner delete CGN; // Delete the call graph node for this func 1205714c974006d4fe28ddd66d15e9b158493df00b6Chris Lattner FunctionMap.erase(F); // Remove the call graph node from the map 12125e9cad236c5ebb0f96f2c213c294616a1d04155Chris Lattner 12236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines M.getFunctionList().remove(F); 1235714c974006d4fe28ddd66d15e9b158493df00b6Chris Lattner return F; 12425e9cad236c5ebb0f96f2c213c294616a1d04155Chris Lattner} 12525e9cad236c5ebb0f96f2c213c294616a1d04155Chris Lattner 1269ad1cb59deda265441c1614fee5ec7f7dea7625dNick Lewycky/// spliceFunction - Replace the function represented by this node by another. 1279ad1cb59deda265441c1614fee5ec7f7dea7625dNick Lewycky/// This does not rescan the body of the function, so it is suitable when 1289ad1cb59deda265441c1614fee5ec7f7dea7625dNick Lewycky/// splicing the body of the old function to the new while also updating all 1299ad1cb59deda265441c1614fee5ec7f7dea7625dNick Lewycky/// callers from old to new. 1309ad1cb59deda265441c1614fee5ec7f7dea7625dNick Lewycky/// 1319ad1cb59deda265441c1614fee5ec7f7dea7625dNick Lewyckyvoid CallGraph::spliceFunction(const Function *From, const Function *To) { 1329ad1cb59deda265441c1614fee5ec7f7dea7625dNick Lewycky assert(FunctionMap.count(From) && "No CallGraphNode for function!"); 1339ad1cb59deda265441c1614fee5ec7f7dea7625dNick Lewycky assert(!FunctionMap.count(To) && 1349ad1cb59deda265441c1614fee5ec7f7dea7625dNick Lewycky "Pointing CallGraphNode at a function that already exists"); 1359ad1cb59deda265441c1614fee5ec7f7dea7625dNick Lewycky FunctionMapTy::iterator I = FunctionMap.find(From); 1369ad1cb59deda265441c1614fee5ec7f7dea7625dNick Lewycky I->second->F = const_cast<Function*>(To); 1379ad1cb59deda265441c1614fee5ec7f7dea7625dNick Lewycky FunctionMap[To] = I->second; 1389ad1cb59deda265441c1614fee5ec7f7dea7625dNick Lewycky FunctionMap.erase(I); 1399ad1cb59deda265441c1614fee5ec7f7dea7625dNick Lewycky} 1409ad1cb59deda265441c1614fee5ec7f7dea7625dNick Lewycky 141c54b1c1f8b7cf7419b2843d54e9da6c8c15e0dd0Chris Lattner// getOrInsertFunction - This method is identical to calling operator[], but 142c54b1c1f8b7cf7419b2843d54e9da6c8c15e0dd0Chris Lattner// it will insert a new CallGraphNode for the specified function if one does 143c54b1c1f8b7cf7419b2843d54e9da6c8c15e0dd0Chris Lattner// not already exist. 144c54b1c1f8b7cf7419b2843d54e9da6c8c15e0dd0Chris LattnerCallGraphNode *CallGraph::getOrInsertFunction(const Function *F) { 145c54b1c1f8b7cf7419b2843d54e9da6c8c15e0dd0Chris Lattner CallGraphNode *&CGN = FunctionMap[F]; 14636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (CGN) 14736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return CGN; 14836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 14936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines assert((!F || F->getParent() == &M) && "Function not in current module!"); 150c54b1c1f8b7cf7419b2843d54e9da6c8c15e0dd0Chris Lattner return CGN = new CallGraphNode(const_cast<Function*>(F)); 151c54b1c1f8b7cf7419b2843d54e9da6c8c15e0dd0Chris Lattner} 152c54b1c1f8b7cf7419b2843d54e9da6c8c15e0dd0Chris Lattner 15336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines//===----------------------------------------------------------------------===// 15436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// Implementations of the CallGraphNode class methods. 15536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// 15636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 15745cfe545ec8177262dabc70580ce05feaa1c3880Chris Lattnervoid CallGraphNode::print(raw_ostream &OS) const { 15803839956e2b99348812f4c45fb57649804c77c2dChris Lattner if (Function *F = getFunction()) 159b374b90e81d0ce6b5d02041ba4f7b15a945b38d8Chris Lattner OS << "Call graph node for function: '" << F->getName() << "'"; 16003839956e2b99348812f4c45fb57649804c77c2dChris Lattner else 161b374b90e81d0ce6b5d02041ba4f7b15a945b38d8Chris Lattner OS << "Call graph node <<null function>>"; 162b374b90e81d0ce6b5d02041ba4f7b15a945b38d8Chris Lattner 1636275413ff5977a7950b775ecc8e8d55af191934dChris Lattner OS << "<<" << this << ">> #uses=" << getNumReferences() << '\n'; 16403839956e2b99348812f4c45fb57649804c77c2dChris Lattner 1656275413ff5977a7950b775ecc8e8d55af191934dChris Lattner for (const_iterator I = begin(), E = end(); I != E; ++I) { 1666275413ff5977a7950b775ecc8e8d55af191934dChris Lattner OS << " CS<" << I->first << "> calls "; 1676104626b467d22518f16c74cd67cba89168f65d4Gabor Greif if (Function *FI = I->second->getFunction()) 1686275413ff5977a7950b775ecc8e8d55af191934dChris Lattner OS << "function '" << FI->getName() <<"'\n"; 1696275413ff5977a7950b775ecc8e8d55af191934dChris Lattner else 1706275413ff5977a7950b775ecc8e8d55af191934dChris Lattner OS << "external node\n"; 1716275413ff5977a7950b775ecc8e8d55af191934dChris Lattner } 1726275413ff5977a7950b775ecc8e8d55af191934dChris Lattner OS << '\n'; 17303839956e2b99348812f4c45fb57649804c77c2dChris Lattner} 17403839956e2b99348812f4c45fb57649804c77c2dChris Lattner 175286c4dc355b8be6806081b23c3097485821c7642Manman Ren#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 176265c026fee512f8206050c0b3f956fe072b05b34David Greenevoid CallGraphNode::dump() const { print(dbgs()); } 177cc77eece74c8db09acc2af425e7e6c88a5bb30d1Manman Ren#endif 17803839956e2b99348812f4c45fb57649804c77c2dChris Lattner 17975caee241955fdcd9942c42be8b77ba9996e94d6Chris Lattner/// removeCallEdgeFor - This method removes the edge in the node for the 18075caee241955fdcd9942c42be8b77ba9996e94d6Chris Lattner/// specified call site. Note that this method takes linear time, so it 18175caee241955fdcd9942c42be8b77ba9996e94d6Chris Lattner/// should be used sparingly. 18275caee241955fdcd9942c42be8b77ba9996e94d6Chris Lattnervoid CallGraphNode::removeCallEdgeFor(CallSite CS) { 183be577659d3c1222cc58c33628c0baddb94d241abChris Lattner for (CalledFunctionsVector::iterator I = CalledFunctions.begin(); ; ++I) { 184be577659d3c1222cc58c33628c0baddb94d241abChris Lattner assert(I != CalledFunctions.end() && "Cannot find callsite to remove!"); 185a541b0fde2ab6b8b037edf113d42da41a2c5aae9Chris Lattner if (I->first == CS.getInstruction()) { 186be577659d3c1222cc58c33628c0baddb94d241abChris Lattner I->second->DropRef(); 187be577659d3c1222cc58c33628c0baddb94d241abChris Lattner *I = CalledFunctions.back(); 188be577659d3c1222cc58c33628c0baddb94d241abChris Lattner CalledFunctions.pop_back(); 189be577659d3c1222cc58c33628c0baddb94d241abChris Lattner return; 190be577659d3c1222cc58c33628c0baddb94d241abChris Lattner } 191be577659d3c1222cc58c33628c0baddb94d241abChris Lattner } 192be577659d3c1222cc58c33628c0baddb94d241abChris Lattner} 193be577659d3c1222cc58c33628c0baddb94d241abChris Lattner 194cd382a3725e46a41c6dfb923cd1ee295fa0461aaChris Lattner// removeAnyCallEdgeTo - This method removes any call edges from this node to 195cd382a3725e46a41c6dfb923cd1ee295fa0461aaChris Lattner// the specified callee function. This takes more time to execute than 196cd382a3725e46a41c6dfb923cd1ee295fa0461aaChris Lattner// removeCallEdgeTo, so it should not be used unless necessary. 197cd382a3725e46a41c6dfb923cd1ee295fa0461aaChris Lattnervoid CallGraphNode::removeAnyCallEdgeTo(CallGraphNode *Callee) { 198fff03c9074ba5ee883b67d422c581f2397779264Chris Lattner for (unsigned i = 0, e = CalledFunctions.size(); i != e; ++i) 199d85340f4ec587e22b0239617f3b747a6df113894Chris Lattner if (CalledFunctions[i].second == Callee) { 200b374b90e81d0ce6b5d02041ba4f7b15a945b38d8Chris Lattner Callee->DropRef(); 201fff03c9074ba5ee883b67d422c581f2397779264Chris Lattner CalledFunctions[i] = CalledFunctions.back(); 202fff03c9074ba5ee883b67d422c581f2397779264Chris Lattner CalledFunctions.pop_back(); 203fff03c9074ba5ee883b67d422c581f2397779264Chris Lattner --i; --e; 204cd382a3725e46a41c6dfb923cd1ee295fa0461aaChris Lattner } 205cd382a3725e46a41c6dfb923cd1ee295fa0461aaChris Lattner} 2064f1bd9e9963239c119db70070db1d68286b3de7eReid Spencer 207a2582da44dbe7204aac49cdaeccfd4e77ff7c408Duncan Sands/// removeOneAbstractEdgeTo - Remove one edge associated with a null callsite 208a2582da44dbe7204aac49cdaeccfd4e77ff7c408Duncan Sands/// from this node to the specified callee function. 209a2582da44dbe7204aac49cdaeccfd4e77ff7c408Duncan Sandsvoid CallGraphNode::removeOneAbstractEdgeTo(CallGraphNode *Callee) { 2107f2e381b565701d9856ac75d9a90454eed57547cGabor Greif for (CalledFunctionsVector::iterator I = CalledFunctions.begin(); ; ++I) { 2117f2e381b565701d9856ac75d9a90454eed57547cGabor Greif assert(I != CalledFunctions.end() && "Cannot find callee to remove!"); 2127f2e381b565701d9856ac75d9a90454eed57547cGabor Greif CallRecord &CR = *I; 213dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (CR.second == Callee && CR.first == nullptr) { 214b374b90e81d0ce6b5d02041ba4f7b15a945b38d8Chris Lattner Callee->DropRef(); 215b374b90e81d0ce6b5d02041ba4f7b15a945b38d8Chris Lattner *I = CalledFunctions.back(); 216b374b90e81d0ce6b5d02041ba4f7b15a945b38d8Chris Lattner CalledFunctions.pop_back(); 217a2582da44dbe7204aac49cdaeccfd4e77ff7c408Duncan Sands return; 218a2582da44dbe7204aac49cdaeccfd4e77ff7c408Duncan Sands } 219a2582da44dbe7204aac49cdaeccfd4e77ff7c408Duncan Sands } 220a2582da44dbe7204aac49cdaeccfd4e77ff7c408Duncan Sands} 221a2582da44dbe7204aac49cdaeccfd4e77ff7c408Duncan Sands 222a51c39cc3265f5d0d5de87b4a3ef9332c83556e1Chris Lattner/// replaceCallEdge - This method replaces the edge in the node for the 223a51c39cc3265f5d0d5de87b4a3ef9332c83556e1Chris Lattner/// specified call site with a new one. Note that this method takes linear 224a51c39cc3265f5d0d5de87b4a3ef9332c83556e1Chris Lattner/// time, so it should be used sparingly. 225a51c39cc3265f5d0d5de87b4a3ef9332c83556e1Chris Lattnervoid CallGraphNode::replaceCallEdge(CallSite CS, 226a51c39cc3265f5d0d5de87b4a3ef9332c83556e1Chris Lattner CallSite NewCS, CallGraphNode *NewNode){ 227a51c39cc3265f5d0d5de87b4a3ef9332c83556e1Chris Lattner for (CalledFunctionsVector::iterator I = CalledFunctions.begin(); ; ++I) { 228a51c39cc3265f5d0d5de87b4a3ef9332c83556e1Chris Lattner assert(I != CalledFunctions.end() && "Cannot find callsite to remove!"); 229a51c39cc3265f5d0d5de87b4a3ef9332c83556e1Chris Lattner if (I->first == CS.getInstruction()) { 230a51c39cc3265f5d0d5de87b4a3ef9332c83556e1Chris Lattner I->second->DropRef(); 231a51c39cc3265f5d0d5de87b4a3ef9332c83556e1Chris Lattner I->first = NewCS.getInstruction(); 232a51c39cc3265f5d0d5de87b4a3ef9332c83556e1Chris Lattner I->second = NewNode; 233a51c39cc3265f5d0d5de87b4a3ef9332c83556e1Chris Lattner NewNode->AddRef(); 234a51c39cc3265f5d0d5de87b4a3ef9332c83556e1Chris Lattner return; 235a51c39cc3265f5d0d5de87b4a3ef9332c83556e1Chris Lattner } 236a51c39cc3265f5d0d5de87b4a3ef9332c83556e1Chris Lattner } 237a51c39cc3265f5d0d5de87b4a3ef9332c83556e1Chris Lattner} 238a51c39cc3265f5d0d5de87b4a3ef9332c83556e1Chris Lattner 23936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines//===----------------------------------------------------------------------===// 24036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// Out-of-line definitions of CallGraphAnalysis class members. 24136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// 24236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 24336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hineschar CallGraphAnalysis::PassID; 24436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 24536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines//===----------------------------------------------------------------------===// 24636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// Implementations of the CallGraphWrapperPass class methods. 24736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// 24836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 24936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen HinesCallGraphWrapperPass::CallGraphWrapperPass() : ModulePass(ID) { 25036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines initializeCallGraphWrapperPassPass(*PassRegistry::getPassRegistry()); 25136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines} 25236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 25336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen HinesCallGraphWrapperPass::~CallGraphWrapperPass() {} 25436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 25536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesvoid CallGraphWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const { 25636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines AU.setPreservesAll(); 25736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines} 25836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 25936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesbool CallGraphWrapperPass::runOnModule(Module &M) { 26036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // All the real work is done in the constructor for the CallGraph. 26136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines G.reset(new CallGraph(M)); 26236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return false; 26336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines} 26436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 26536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen HinesINITIALIZE_PASS(CallGraphWrapperPass, "basiccg", "CallGraph Construction", 26636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines false, true) 26736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 26836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hineschar CallGraphWrapperPass::ID = 0; 26936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 270dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinesvoid CallGraphWrapperPass::releaseMemory() { G.reset(nullptr); } 27136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 27236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesvoid CallGraphWrapperPass::print(raw_ostream &OS, const Module *) const { 27336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (!G) { 27436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines OS << "No call graph has been built!\n"; 27536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return; 27636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 27736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 27836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Just delegate. 27936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines G->print(OS); 28036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines} 28136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 28236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 283dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinesvoid CallGraphWrapperPass::dump() const { print(dbgs(), nullptr); } 28436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#endif 28536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 2864f1bd9e9963239c119db70070db1d68286b3de7eReid Spencer// Enuse that users of CallGraph.h also link with this file 2874f1bd9e9963239c119db70070db1d68286b3de7eReid SpencerDEFINING_FILE_FOR(CallGraph) 288