14a81067a84e18c44898149f5afdbaa3e18b3e821Chris Lattner//===- CallGraphSCCPass.h - Pass that operates BU on call graph -*- C++ -*-===// 29769ab22265b313171d201b5928688524a01bd87Misha Brukman// 36fbcc26f1460eaee4e0eb8b426fc1ff0c7af11beJohn Criswell// The LLVM Compiler Infrastructure 46fbcc26f1460eaee4e0eb8b426fc1ff0c7af11beJohn Criswell// 57ed47a13356daed2a34cd2209a31f92552e3bdd8Chris Lattner// This file is distributed under the University of Illinois Open Source 67ed47a13356daed2a34cd2209a31f92552e3bdd8Chris Lattner// License. See LICENSE.TXT for details. 79769ab22265b313171d201b5928688524a01bd87Misha Brukman// 86fbcc26f1460eaee4e0eb8b426fc1ff0c7af11beJohn Criswell//===----------------------------------------------------------------------===// 94a81067a84e18c44898149f5afdbaa3e18b3e821Chris Lattner// 104a81067a84e18c44898149f5afdbaa3e18b3e821Chris Lattner// This file defines the CallGraphSCCPass class, which is used for passes which 114a81067a84e18c44898149f5afdbaa3e18b3e821Chris Lattner// are implemented as bottom-up traversals on the call graph. Because there may 124a81067a84e18c44898149f5afdbaa3e18b3e821Chris Lattner// be cycles in the call graph, passes of this type operate on the call-graph in 134a81067a84e18c44898149f5afdbaa3e18b3e821Chris Lattner// SCC order: that is, they process function bottom-up, except for recursive 144a81067a84e18c44898149f5afdbaa3e18b3e821Chris Lattner// functions, which they process all at once. 154a81067a84e18c44898149f5afdbaa3e18b3e821Chris Lattner// 164a81067a84e18c44898149f5afdbaa3e18b3e821Chris Lattner// These passes are inherently interprocedural, and are required to keep the 174a81067a84e18c44898149f5afdbaa3e18b3e821Chris Lattner// call graph up-to-date if they do anything which could modify it. 184a81067a84e18c44898149f5afdbaa3e18b3e821Chris Lattner// 194a81067a84e18c44898149f5afdbaa3e18b3e821Chris Lattner//===----------------------------------------------------------------------===// 204a81067a84e18c44898149f5afdbaa3e18b3e821Chris Lattner 21674be02d525d4e24bc6943ed9274958c580bcfbcJakub Staszak#ifndef LLVM_ANALYSIS_CALLGRAPHSCCPASS_H 22674be02d525d4e24bc6943ed9274958c580bcfbcJakub Staszak#define LLVM_ANALYSIS_CALLGRAPHSCCPASS_H 234a81067a84e18c44898149f5afdbaa3e18b3e821Chris Lattner 24001dbfebcbbded8c8e74b19e838b50da2b6c6fb5Owen Anderson#include "llvm/Analysis/CallGraph.h" 25255f89faee13dc491cb64fbeae3c763e7e2ea4e6Chandler Carruth#include "llvm/Pass.h" 264a81067a84e18c44898149f5afdbaa3e18b3e821Chris Lattner 27d0fde30ce850b78371fd1386338350591f9ff494Brian Gaekenamespace llvm { 28d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 294a81067a84e18c44898149f5afdbaa3e18b3e821Chris Lattnerclass CallGraphNode; 3025942e9f5c1ad7f93b00059365230f7fd0089dfeChris Lattnerclass CallGraph; 3197fd2439f2b30b575cdd67eef52e03937d483680Devang Patelclass PMStack; 322decb22222cac46bb1d9163e7b89d7e5be8ef65fChris Lattnerclass CallGraphSCC; 332decb22222cac46bb1d9163e7b89d7e5be8ef65fChris Lattner 342decb22222cac46bb1d9163e7b89d7e5be8ef65fChris Lattnerclass CallGraphSCCPass : public Pass { 352decb22222cac46bb1d9163e7b89d7e5be8ef65fChris Lattnerpublic: 3690c579de5a383cee278acc3f7e7b9d0a656e6a35Owen Anderson explicit CallGraphSCCPass(char &pid) : Pass(PT_CallGraphSCC, pid) {} 37794fd75c67a2cdc128d67342c6d88a504d186896Devang Patel 385c8aa950fe3484b6e115647328c196f8be64f9edDavid Greene /// createPrinterPass - Get a pass that prints the Module 395c8aa950fe3484b6e115647328c196f8be64f9edDavid Greene /// corresponding to a CallGraph. 4036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Pass *createPrinterPass(raw_ostream &O, 4136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines const std::string &Banner) const override; 425c8aa950fe3484b6e115647328c196f8be64f9edDavid Greene 4349eb628c21b358380b76df82aa3dfe0baab4c6ecPedro Artigas using llvm::Pass::doInitialization; 4449eb628c21b358380b76df82aa3dfe0baab4c6ecPedro Artigas using llvm::Pass::doFinalization; 4549eb628c21b358380b76df82aa3dfe0baab4c6ecPedro Artigas 46a10df5028211fc897751d23e91d035db47d23facChris Lattner /// doInitialization - This method is called before the SCC's of the program 47a10df5028211fc897751d23e91d035db47d23facChris Lattner /// has been processed, allowing the pass to do initialization as necessary. 4825942e9f5c1ad7f93b00059365230f7fd0089dfeChris Lattner virtual bool doInitialization(CallGraph &CG) { 49a10df5028211fc897751d23e91d035db47d23facChris Lattner return false; 50a10df5028211fc897751d23e91d035db47d23facChris Lattner } 51a10df5028211fc897751d23e91d035db47d23facChris Lattner 524a81067a84e18c44898149f5afdbaa3e18b3e821Chris Lattner /// runOnSCC - This method should be implemented by the subclass to perform 534a81067a84e18c44898149f5afdbaa3e18b3e821Chris Lattner /// whatever action is necessary for the specified SCC. Note that 544a81067a84e18c44898149f5afdbaa3e18b3e821Chris Lattner /// non-recursive (or only self-recursive) functions will have an SCC size of 554a81067a84e18c44898149f5afdbaa3e18b3e821Chris Lattner /// 1, where recursive portions of the call graph will have SCC size > 1. 564a81067a84e18c44898149f5afdbaa3e18b3e821Chris Lattner /// 575095e3d1d1caef8d573534d369e37277c623064cChris Lattner /// SCC passes that add or delete functions to the SCC are required to update 585095e3d1d1caef8d573534d369e37277c623064cChris Lattner /// the SCC list, otherwise stale pointers may be dereferenced. 595095e3d1d1caef8d573534d369e37277c623064cChris Lattner /// 602decb22222cac46bb1d9163e7b89d7e5be8ef65fChris Lattner virtual bool runOnSCC(CallGraphSCC &SCC) = 0; 614a81067a84e18c44898149f5afdbaa3e18b3e821Chris Lattner 62a10df5028211fc897751d23e91d035db47d23facChris Lattner /// doFinalization - This method is called after the SCC's of the program has 63a10df5028211fc897751d23e91d035db47d23facChris Lattner /// been processed, allowing the pass to do final cleanup as necessary. 6425942e9f5c1ad7f93b00059365230f7fd0089dfeChris Lattner virtual bool doFinalization(CallGraph &CG) { 65a10df5028211fc897751d23e91d035db47d23facChris Lattner return false; 66a10df5028211fc897751d23e91d035db47d23facChris Lattner } 67a10df5028211fc897751d23e91d035db47d23facChris Lattner 6897fd2439f2b30b575cdd67eef52e03937d483680Devang Patel /// Assign pass manager to manager this pass 6936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void assignPassManager(PMStack &PMS, PassManagerType PMT) override; 704a81067a84e18c44898149f5afdbaa3e18b3e821Chris Lattner 718f93b7fc36dbeba428c6dd122c07fe0777baa664Devang Patel /// Return what kind of Pass Manager can manage this pass. 7236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines PassManagerType getPotentialPassManagerType() const override { 738f93b7fc36dbeba428c6dd122c07fe0777baa664Devang Patel return PMT_CallGraphPassManager; 748f93b7fc36dbeba428c6dd122c07fe0777baa664Devang Patel } 758f93b7fc36dbeba428c6dd122c07fe0777baa664Devang Patel 764a81067a84e18c44898149f5afdbaa3e18b3e821Chris Lattner /// getAnalysisUsage - For this class, we declare that we require and preserve 774a81067a84e18c44898149f5afdbaa3e18b3e821Chris Lattner /// the call graph. If the derived class implements this method, it should 784a81067a84e18c44898149f5afdbaa3e18b3e821Chris Lattner /// always explicitly call the implementation here. 7936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void getAnalysisUsage(AnalysisUsage &Info) const override; 804a81067a84e18c44898149f5afdbaa3e18b3e821Chris Lattner}; 814a81067a84e18c44898149f5afdbaa3e18b3e821Chris Lattner 822decb22222cac46bb1d9163e7b89d7e5be8ef65fChris Lattner/// CallGraphSCC - This is a single SCC that a CallGraphSCCPass is run on. 832decb22222cac46bb1d9163e7b89d7e5be8ef65fChris Lattnerclass CallGraphSCC { 842decb22222cac46bb1d9163e7b89d7e5be8ef65fChris Lattner void *Context; // The CGPassManager object that is vending this. 852decb22222cac46bb1d9163e7b89d7e5be8ef65fChris Lattner std::vector<CallGraphNode*> Nodes; 862decb22222cac46bb1d9163e7b89d7e5be8ef65fChris Lattnerpublic: 872decb22222cac46bb1d9163e7b89d7e5be8ef65fChris Lattner CallGraphSCC(void *context) : Context(context) {} 882decb22222cac46bb1d9163e7b89d7e5be8ef65fChris Lattner 892decb22222cac46bb1d9163e7b89d7e5be8ef65fChris Lattner void initialize(CallGraphNode*const*I, CallGraphNode*const*E) { 902decb22222cac46bb1d9163e7b89d7e5be8ef65fChris Lattner Nodes.assign(I, E); 912decb22222cac46bb1d9163e7b89d7e5be8ef65fChris Lattner } 922decb22222cac46bb1d9163e7b89d7e5be8ef65fChris Lattner 932decb22222cac46bb1d9163e7b89d7e5be8ef65fChris Lattner bool isSingular() const { return Nodes.size() == 1; } 942decb22222cac46bb1d9163e7b89d7e5be8ef65fChris Lattner unsigned size() const { return Nodes.size(); } 952decb22222cac46bb1d9163e7b89d7e5be8ef65fChris Lattner 962decb22222cac46bb1d9163e7b89d7e5be8ef65fChris Lattner /// ReplaceNode - This informs the SCC and the pass manager that the specified 972decb22222cac46bb1d9163e7b89d7e5be8ef65fChris Lattner /// Old node has been deleted, and New is to be used in its place. 98a3dfc646b4d772979f8994c07eeee6af57480d34Chris Lattner void ReplaceNode(CallGraphNode *Old, CallGraphNode *New); 992decb22222cac46bb1d9163e7b89d7e5be8ef65fChris Lattner 1002decb22222cac46bb1d9163e7b89d7e5be8ef65fChris Lattner typedef std::vector<CallGraphNode*>::const_iterator iterator; 1012decb22222cac46bb1d9163e7b89d7e5be8ef65fChris Lattner iterator begin() const { return Nodes.begin(); } 1022decb22222cac46bb1d9163e7b89d7e5be8ef65fChris Lattner iterator end() const { return Nodes.end(); } 1032decb22222cac46bb1d9163e7b89d7e5be8ef65fChris Lattner}; 1042decb22222cac46bb1d9163e7b89d7e5be8ef65fChris Lattner 105d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke} // End llvm namespace 106d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 1074a81067a84e18c44898149f5afdbaa3e18b3e821Chris Lattner#endif 108