1dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines//===- MachineBlockFrequencyInfo.cpp - MBB Frequency Analysis -------------===// 259a9dab4d8650d3408efa431907183e13b91867bJakub Staszak// 359a9dab4d8650d3408efa431907183e13b91867bJakub Staszak// The LLVM Compiler Infrastructure 459a9dab4d8650d3408efa431907183e13b91867bJakub Staszak// 559a9dab4d8650d3408efa431907183e13b91867bJakub Staszak// This file is distributed under the University of Illinois Open Source 659a9dab4d8650d3408efa431907183e13b91867bJakub Staszak// License. See LICENSE.TXT for details. 759a9dab4d8650d3408efa431907183e13b91867bJakub Staszak// 859a9dab4d8650d3408efa431907183e13b91867bJakub Staszak//===----------------------------------------------------------------------===// 959a9dab4d8650d3408efa431907183e13b91867bJakub Staszak// 1059a9dab4d8650d3408efa431907183e13b91867bJakub Staszak// Loops should be simplified before this analysis. 1159a9dab4d8650d3408efa431907183e13b91867bJakub Staszak// 1259a9dab4d8650d3408efa431907183e13b91867bJakub Staszak//===----------------------------------------------------------------------===// 1359a9dab4d8650d3408efa431907183e13b91867bJakub Staszak 14f55c1c85881afd65647bde5346f64d9685235c7cJakub Staszak#include "llvm/CodeGen/MachineBlockFrequencyInfo.h" 15dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines#include "llvm/Analysis/BlockFrequencyInfoImpl.h" 1659a9dab4d8650d3408efa431907183e13b91867bJakub Staszak#include "llvm/CodeGen/MachineBranchProbabilityInfo.h" 17dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines#include "llvm/CodeGen/MachineFunction.h" 18dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines#include "llvm/CodeGen/MachineLoopInfo.h" 19d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/CodeGen/Passes.h" 20d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/InitializePasses.h" 2136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/Support/CommandLine.h" 2236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/Support/Debug.h" 2336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/Support/GraphWriter.h" 2459a9dab4d8650d3408efa431907183e13b91867bJakub Staszak 2559a9dab4d8650d3408efa431907183e13b91867bJakub Staszakusing namespace llvm; 2659a9dab4d8650d3408efa431907183e13b91867bJakub Staszak 27dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines#define DEBUG_TYPE "block-freq" 28dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 2936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#ifndef NDEBUG 3036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesenum GVDAGType { 3136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines GVDT_None, 3236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines GVDT_Fraction, 3336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines GVDT_Integer 3436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines}; 3536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 3636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesstatic cl::opt<GVDAGType> 3736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen HinesViewMachineBlockFreqPropagationDAG("view-machine-block-freq-propagation-dags", 3836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines cl::Hidden, 3936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines cl::desc("Pop up a window to show a dag displaying how machine block " 4036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines "frequencies propagate through the CFG."), 4136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines cl::values( 4236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines clEnumValN(GVDT_None, "none", 4336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines "do not display graphs."), 4436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines clEnumValN(GVDT_Fraction, "fraction", "display a graph using the " 4536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines "fractional block frequency representation."), 4636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines clEnumValN(GVDT_Integer, "integer", "display a graph using the raw " 4736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines "integer fractional block frequency representation."), 4836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines clEnumValEnd)); 4936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 5036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesnamespace llvm { 5136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 5236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinestemplate <> 5336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesstruct GraphTraits<MachineBlockFrequencyInfo *> { 5436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines typedef const MachineBasicBlock NodeType; 5536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines typedef MachineBasicBlock::const_succ_iterator ChildIteratorType; 5636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines typedef MachineFunction::const_iterator nodes_iterator; 5736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 5836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines static inline 5936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines const NodeType *getEntryNode(const MachineBlockFrequencyInfo *G) { 6036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return G->getFunction()->begin(); 6136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 6236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 6336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines static ChildIteratorType child_begin(const NodeType *N) { 6436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return N->succ_begin(); 6536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 6636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 6736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines static ChildIteratorType child_end(const NodeType *N) { 6836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return N->succ_end(); 6936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 7036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 7136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines static nodes_iterator nodes_begin(const MachineBlockFrequencyInfo *G) { 7236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return G->getFunction()->begin(); 7336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 7436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 7536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines static nodes_iterator nodes_end(const MachineBlockFrequencyInfo *G) { 7636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return G->getFunction()->end(); 7736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 7836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines}; 7936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 8036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinestemplate<> 8136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesstruct DOTGraphTraits<MachineBlockFrequencyInfo*> : 8236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines public DefaultDOTGraphTraits { 8336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines explicit DOTGraphTraits(bool isSimple=false) : 8436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DefaultDOTGraphTraits(isSimple) {} 8536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 8636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines static std::string getGraphName(const MachineBlockFrequencyInfo *G) { 8736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return G->getFunction()->getName(); 8836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 8936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 9036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines std::string getNodeLabel(const MachineBasicBlock *Node, 9136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines const MachineBlockFrequencyInfo *Graph) { 9236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines std::string Result; 9336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines raw_string_ostream OS(Result); 9436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 9536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines OS << Node->getName().str() << ":"; 9636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines switch (ViewMachineBlockFreqPropagationDAG) { 9736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines case GVDT_Fraction: 9836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Graph->printBlockFreq(OS, Node); 9936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines break; 10036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines case GVDT_Integer: 10136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines OS << Graph->getBlockFreq(Node).getFrequency(); 10236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines break; 10336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines case GVDT_None: 10436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines llvm_unreachable("If we are not supposed to render a graph we should " 10536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines "never reach this point."); 10636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 10736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 10836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return Result; 10936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 11036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines}; 11136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 11236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 11336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines} // end namespace llvm 11436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#endif 11536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 116f55c1c85881afd65647bde5346f64d9685235c7cJakub StaszakINITIALIZE_PASS_BEGIN(MachineBlockFrequencyInfo, "machine-block-freq", 11759a9dab4d8650d3408efa431907183e13b91867bJakub Staszak "Machine Block Frequency Analysis", true, true) 11859a9dab4d8650d3408efa431907183e13b91867bJakub StaszakINITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfo) 119dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen HinesINITIALIZE_PASS_DEPENDENCY(MachineLoopInfo) 120f55c1c85881afd65647bde5346f64d9685235c7cJakub StaszakINITIALIZE_PASS_END(MachineBlockFrequencyInfo, "machine-block-freq", 12159a9dab4d8650d3408efa431907183e13b91867bJakub Staszak "Machine Block Frequency Analysis", true, true) 12259a9dab4d8650d3408efa431907183e13b91867bJakub Staszak 123f55c1c85881afd65647bde5346f64d9685235c7cJakub Staszakchar MachineBlockFrequencyInfo::ID = 0; 12459a9dab4d8650d3408efa431907183e13b91867bJakub Staszak 12559a9dab4d8650d3408efa431907183e13b91867bJakub Staszak 12636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen HinesMachineBlockFrequencyInfo:: 12736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen HinesMachineBlockFrequencyInfo() :MachineFunctionPass(ID) { 128f55c1c85881afd65647bde5346f64d9685235c7cJakub Staszak initializeMachineBlockFrequencyInfoPass(*PassRegistry::getPassRegistry()); 12959a9dab4d8650d3408efa431907183e13b91867bJakub Staszak} 13059a9dab4d8650d3408efa431907183e13b91867bJakub Staszak 13136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen HinesMachineBlockFrequencyInfo::~MachineBlockFrequencyInfo() {} 13259a9dab4d8650d3408efa431907183e13b91867bJakub Staszak 133f55c1c85881afd65647bde5346f64d9685235c7cJakub Staszakvoid MachineBlockFrequencyInfo::getAnalysisUsage(AnalysisUsage &AU) const { 13459a9dab4d8650d3408efa431907183e13b91867bJakub Staszak AU.addRequired<MachineBranchProbabilityInfo>(); 135dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines AU.addRequired<MachineLoopInfo>(); 13659a9dab4d8650d3408efa431907183e13b91867bJakub Staszak AU.setPreservesAll(); 1379d81c97c8a3bbce302d0675feffec2c801cdf718Jakub Staszak MachineFunctionPass::getAnalysisUsage(AU); 13859a9dab4d8650d3408efa431907183e13b91867bJakub Staszak} 13959a9dab4d8650d3408efa431907183e13b91867bJakub Staszak 140f55c1c85881afd65647bde5346f64d9685235c7cJakub Staszakbool MachineBlockFrequencyInfo::runOnMachineFunction(MachineFunction &F) { 14136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines MachineBranchProbabilityInfo &MBPI = 142dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines getAnalysis<MachineBranchProbabilityInfo>(); 143dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines MachineLoopInfo &MLI = getAnalysis<MachineLoopInfo>(); 14436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (!MBFI) 14536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines MBFI.reset(new ImplType); 146dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines MBFI->doFunction(&F, &MBPI, &MLI); 14736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#ifndef NDEBUG 14836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (ViewMachineBlockFreqPropagationDAG != GVDT_None) { 14936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines view(); 15036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 15136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#endif 15259a9dab4d8650d3408efa431907183e13b91867bJakub Staszak return false; 15359a9dab4d8650d3408efa431907183e13b91867bJakub Staszak} 15459a9dab4d8650d3408efa431907183e13b91867bJakub Staszak 15536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesvoid MachineBlockFrequencyInfo::releaseMemory() { MBFI.reset(); } 15636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 15736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// Pop up a ghostview window with the current block frequency propagation 15836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// rendered using dot. 15936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesvoid MachineBlockFrequencyInfo::view() const { 16036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// This code is only for debugging. 16136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#ifndef NDEBUG 16236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines ViewGraph(const_cast<MachineBlockFrequencyInfo *>(this), 16336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines "MachineBlockFrequencyDAGs"); 16436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#else 16536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines errs() << "MachineBlockFrequencyInfo::view is only available in debug builds " 16636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines "on systems with Graphviz or gv!\n"; 16736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#endif // NDEBUG 16836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines} 16936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 1708ea45231dc6c30d0c4a55ce038a08edccc308a73Jakub StaszakBlockFrequency MachineBlockFrequencyInfo:: 17125101bb2a799a36be9f077ee2fc2dcf0df2b6efbJakub StaszakgetBlockFreq(const MachineBasicBlock *MBB) const { 17236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return MBFI ? MBFI->getBlockFreq(MBB) : 0; 17336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines} 17436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 17536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesconst MachineFunction *MachineBlockFrequencyInfo::getFunction() const { 176dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return MBFI ? MBFI->getFunction() : nullptr; 17736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines} 17836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 17936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesraw_ostream & 18036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen HinesMachineBlockFrequencyInfo::printBlockFreq(raw_ostream &OS, 18136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines const BlockFrequency Freq) const { 18236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return MBFI ? MBFI->printBlockFreq(OS, Freq) : OS; 18336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines} 18436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 18536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesraw_ostream & 18636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen HinesMachineBlockFrequencyInfo::printBlockFreq(raw_ostream &OS, 18736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines const MachineBasicBlock *MBB) const { 18836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return MBFI ? MBFI->printBlockFreq(OS, MBB) : OS; 18936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines} 19036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 19136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesuint64_t MachineBlockFrequencyInfo::getEntryFreq() const { 19236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return MBFI ? MBFI->getEntryFreq() : 0; 19359a9dab4d8650d3408efa431907183e13b91867bJakub Staszak} 194