1*9880d681SAndroid Build Coastguard Worker //=- MachineBranchProbabilityInfo.h - Branch Probability Analysis -*- C++ -*-=// 2*9880d681SAndroid Build Coastguard Worker // 3*9880d681SAndroid Build Coastguard Worker // The LLVM Compiler Infrastructure 4*9880d681SAndroid Build Coastguard Worker // 5*9880d681SAndroid Build Coastguard Worker // This file is distributed under the University of Illinois Open Source 6*9880d681SAndroid Build Coastguard Worker // License. See LICENSE.TXT for details. 7*9880d681SAndroid Build Coastguard Worker // 8*9880d681SAndroid Build Coastguard Worker //===----------------------------------------------------------------------===// 9*9880d681SAndroid Build Coastguard Worker // 10*9880d681SAndroid Build Coastguard Worker // This pass is used to evaluate branch probabilties on machine basic blocks. 11*9880d681SAndroid Build Coastguard Worker // 12*9880d681SAndroid Build Coastguard Worker //===----------------------------------------------------------------------===// 13*9880d681SAndroid Build Coastguard Worker 14*9880d681SAndroid Build Coastguard Worker #ifndef LLVM_CODEGEN_MACHINEBRANCHPROBABILITYINFO_H 15*9880d681SAndroid Build Coastguard Worker #define LLVM_CODEGEN_MACHINEBRANCHPROBABILITYINFO_H 16*9880d681SAndroid Build Coastguard Worker 17*9880d681SAndroid Build Coastguard Worker #include "llvm/CodeGen/MachineBasicBlock.h" 18*9880d681SAndroid Build Coastguard Worker #include "llvm/Pass.h" 19*9880d681SAndroid Build Coastguard Worker #include "llvm/Support/BranchProbability.h" 20*9880d681SAndroid Build Coastguard Worker #include <climits> 21*9880d681SAndroid Build Coastguard Worker #include <numeric> 22*9880d681SAndroid Build Coastguard Worker 23*9880d681SAndroid Build Coastguard Worker namespace llvm { 24*9880d681SAndroid Build Coastguard Worker 25*9880d681SAndroid Build Coastguard Worker class MachineBranchProbabilityInfo : public ImmutablePass { 26*9880d681SAndroid Build Coastguard Worker virtual void anchor(); 27*9880d681SAndroid Build Coastguard Worker 28*9880d681SAndroid Build Coastguard Worker // Default weight value. Used when we don't have information about the edge. 29*9880d681SAndroid Build Coastguard Worker // TODO: DEFAULT_WEIGHT makes sense during static predication, when none of 30*9880d681SAndroid Build Coastguard Worker // the successors have a weight yet. But it doesn't make sense when providing 31*9880d681SAndroid Build Coastguard Worker // weight to an edge that may have siblings with non-zero weights. This can 32*9880d681SAndroid Build Coastguard Worker // be handled various ways, but it's probably fine for an edge with unknown 33*9880d681SAndroid Build Coastguard Worker // weight to just "inherit" the non-zero weight of an adjacent successor. 34*9880d681SAndroid Build Coastguard Worker static const uint32_t DEFAULT_WEIGHT = 16; 35*9880d681SAndroid Build Coastguard Worker 36*9880d681SAndroid Build Coastguard Worker public: 37*9880d681SAndroid Build Coastguard Worker static char ID; 38*9880d681SAndroid Build Coastguard Worker MachineBranchProbabilityInfo()39*9880d681SAndroid Build Coastguard Worker MachineBranchProbabilityInfo() : ImmutablePass(ID) { 40*9880d681SAndroid Build Coastguard Worker PassRegistry &Registry = *PassRegistry::getPassRegistry(); 41*9880d681SAndroid Build Coastguard Worker initializeMachineBranchProbabilityInfoPass(Registry); 42*9880d681SAndroid Build Coastguard Worker } 43*9880d681SAndroid Build Coastguard Worker getAnalysisUsage(AnalysisUsage & AU)44*9880d681SAndroid Build Coastguard Worker void getAnalysisUsage(AnalysisUsage &AU) const override { 45*9880d681SAndroid Build Coastguard Worker AU.setPreservesAll(); 46*9880d681SAndroid Build Coastguard Worker } 47*9880d681SAndroid Build Coastguard Worker 48*9880d681SAndroid Build Coastguard Worker // Return edge probability. 49*9880d681SAndroid Build Coastguard Worker BranchProbability getEdgeProbability(const MachineBasicBlock *Src, 50*9880d681SAndroid Build Coastguard Worker const MachineBasicBlock *Dst) const; 51*9880d681SAndroid Build Coastguard Worker 52*9880d681SAndroid Build Coastguard Worker // Same as above, but using a const_succ_iterator from Src. This is faster 53*9880d681SAndroid Build Coastguard Worker // when the iterator is already available. 54*9880d681SAndroid Build Coastguard Worker BranchProbability 55*9880d681SAndroid Build Coastguard Worker getEdgeProbability(const MachineBasicBlock *Src, 56*9880d681SAndroid Build Coastguard Worker MachineBasicBlock::const_succ_iterator Dst) const; 57*9880d681SAndroid Build Coastguard Worker 58*9880d681SAndroid Build Coastguard Worker // A 'Hot' edge is an edge which probability is >= 80%. 59*9880d681SAndroid Build Coastguard Worker bool isEdgeHot(const MachineBasicBlock *Src, 60*9880d681SAndroid Build Coastguard Worker const MachineBasicBlock *Dst) const; 61*9880d681SAndroid Build Coastguard Worker 62*9880d681SAndroid Build Coastguard Worker // Return a hot successor for the block BB or null if there isn't one. 63*9880d681SAndroid Build Coastguard Worker // NB: This routine's complexity is linear on the number of successors. 64*9880d681SAndroid Build Coastguard Worker MachineBasicBlock *getHotSucc(MachineBasicBlock *MBB) const; 65*9880d681SAndroid Build Coastguard Worker 66*9880d681SAndroid Build Coastguard Worker // Print value between 0 (0% probability) and 1 (100% probability), 67*9880d681SAndroid Build Coastguard Worker // however the value is never equal to 0, and can be 1 only iff SRC block 68*9880d681SAndroid Build Coastguard Worker // has only one successor. 69*9880d681SAndroid Build Coastguard Worker raw_ostream &printEdgeProbability(raw_ostream &OS, 70*9880d681SAndroid Build Coastguard Worker const MachineBasicBlock *Src, 71*9880d681SAndroid Build Coastguard Worker const MachineBasicBlock *Dst) const; 72*9880d681SAndroid Build Coastguard Worker }; 73*9880d681SAndroid Build Coastguard Worker 74*9880d681SAndroid Build Coastguard Worker } 75*9880d681SAndroid Build Coastguard Worker 76*9880d681SAndroid Build Coastguard Worker 77*9880d681SAndroid Build Coastguard Worker #endif 78