BranchProbabilityInfo.h revision b068bbbaecf338f481124551a5e6f37484fad800
19e76422b963a65f243fdbee0abed61068b82dd98Andrew Trick//===--- BranchProbabilityInfo.h - Branch Probability Analysis --*- C++ -*-===// 29e76422b963a65f243fdbee0abed61068b82dd98Andrew Trick// 39e76422b963a65f243fdbee0abed61068b82dd98Andrew Trick// The LLVM Compiler Infrastructure 49e76422b963a65f243fdbee0abed61068b82dd98Andrew Trick// 59e76422b963a65f243fdbee0abed61068b82dd98Andrew Trick// This file is distributed under the University of Illinois Open Source 69e76422b963a65f243fdbee0abed61068b82dd98Andrew Trick// License. See LICENSE.TXT for details. 79e76422b963a65f243fdbee0abed61068b82dd98Andrew Trick// 89e76422b963a65f243fdbee0abed61068b82dd98Andrew Trick//===----------------------------------------------------------------------===// 99e76422b963a65f243fdbee0abed61068b82dd98Andrew Trick// 109e76422b963a65f243fdbee0abed61068b82dd98Andrew Trick// This pass is used to evaluate branch probabilties. 119e76422b963a65f243fdbee0abed61068b82dd98Andrew Trick// 129e76422b963a65f243fdbee0abed61068b82dd98Andrew Trick//===----------------------------------------------------------------------===// 139e76422b963a65f243fdbee0abed61068b82dd98Andrew Trick 149e76422b963a65f243fdbee0abed61068b82dd98Andrew Trick#ifndef LLVM_ANALYSIS_BRANCHPROBABILITYINFO_H 159e76422b963a65f243fdbee0abed61068b82dd98Andrew Trick#define LLVM_ANALYSIS_BRANCHPROBABILITYINFO_H 169e76422b963a65f243fdbee0abed61068b82dd98Andrew Trick 179e76422b963a65f243fdbee0abed61068b82dd98Andrew Trick#include "llvm/InitializePasses.h" 1812af93ae86cb4a517d1b67f9363fbf21f24f583bJakub Staszak#include "llvm/Pass.h" 1912af93ae86cb4a517d1b67f9363fbf21f24f583bJakub Staszak#include "llvm/ADT/DenseMap.h" 20f289df2d9544bd3a0934651daa20e589544413baAndrew Trick#include "llvm/Support/BranchProbability.h" 219e76422b963a65f243fdbee0abed61068b82dd98Andrew Trick 229e76422b963a65f243fdbee0abed61068b82dd98Andrew Tricknamespace llvm { 23b068bbbaecf338f481124551a5e6f37484fad800Chandler Carruthclass LoopInfo; 24f289df2d9544bd3a0934651daa20e589544413baAndrew Trickclass raw_ostream; 25f289df2d9544bd3a0934651daa20e589544413baAndrew Trick 269e76422b963a65f243fdbee0abed61068b82dd98Andrew Trickclass BranchProbabilityInfo : public FunctionPass { 279e76422b963a65f243fdbee0abed61068b82dd98Andrew Trickpublic: 289e76422b963a65f243fdbee0abed61068b82dd98Andrew Trick static char ID; 299e76422b963a65f243fdbee0abed61068b82dd98Andrew Trick 309e76422b963a65f243fdbee0abed61068b82dd98Andrew Trick BranchProbabilityInfo() : FunctionPass(ID) { 319e76422b963a65f243fdbee0abed61068b82dd98Andrew Trick initializeBranchProbabilityInfoPass(*PassRegistry::getPassRegistry()); 329e76422b963a65f243fdbee0abed61068b82dd98Andrew Trick } 339e76422b963a65f243fdbee0abed61068b82dd98Andrew Trick 3412af93ae86cb4a517d1b67f9363fbf21f24f583bJakub Staszak void getAnalysisUsage(AnalysisUsage &AU) const; 359e76422b963a65f243fdbee0abed61068b82dd98Andrew Trick bool runOnFunction(Function &F); 3614edd314af99ccaad194d071f23e437a1371f176Chandler Carruth void print(raw_ostream &OS, const Module *M = 0) const; 379e76422b963a65f243fdbee0abed61068b82dd98Andrew Trick 38f289df2d9544bd3a0934651daa20e589544413baAndrew Trick // Returned value is between 1 and UINT32_MAX. Look at 39f289df2d9544bd3a0934651daa20e589544413baAndrew Trick // BranchProbabilityInfo.cpp for details. 406f6baf1bdd7531da5ddb925ffcfcf38724e9e4aaJakub Staszak uint32_t getEdgeWeight(const BasicBlock *Src, const BasicBlock *Dst) const; 419e76422b963a65f243fdbee0abed61068b82dd98Andrew Trick 429e76422b963a65f243fdbee0abed61068b82dd98Andrew Trick // Look at BranchProbabilityInfo.cpp for details. Use it with caution! 436f6baf1bdd7531da5ddb925ffcfcf38724e9e4aaJakub Staszak void setEdgeWeight(const BasicBlock *Src, const BasicBlock *Dst, 446f6baf1bdd7531da5ddb925ffcfcf38724e9e4aaJakub Staszak uint32_t Weight); 459e76422b963a65f243fdbee0abed61068b82dd98Andrew Trick 469e76422b963a65f243fdbee0abed61068b82dd98Andrew Trick // A 'Hot' edge is an edge which probability is >= 80%. 476f6baf1bdd7531da5ddb925ffcfcf38724e9e4aaJakub Staszak bool isEdgeHot(const BasicBlock *Src, const BasicBlock *Dst) const; 489e76422b963a65f243fdbee0abed61068b82dd98Andrew Trick 499e76422b963a65f243fdbee0abed61068b82dd98Andrew Trick // Return a hot successor for the block BB or null if there isn't one. 509e76422b963a65f243fdbee0abed61068b82dd98Andrew Trick BasicBlock *getHotSucc(BasicBlock *BB) const; 519e76422b963a65f243fdbee0abed61068b82dd98Andrew Trick 52f289df2d9544bd3a0934651daa20e589544413baAndrew Trick // Return a probability as a fraction between 0 (0% probability) and 53f289df2d9544bd3a0934651daa20e589544413baAndrew Trick // 1 (100% probability), however the value is never equal to 0, and can be 1 54f289df2d9544bd3a0934651daa20e589544413baAndrew Trick // only iff SRC block has only one successor. 556f6baf1bdd7531da5ddb925ffcfcf38724e9e4aaJakub Staszak BranchProbability getEdgeProbability(const BasicBlock *Src, 566f6baf1bdd7531da5ddb925ffcfcf38724e9e4aaJakub Staszak const BasicBlock *Dst) const; 57f289df2d9544bd3a0934651daa20e589544413baAndrew Trick 589e76422b963a65f243fdbee0abed61068b82dd98Andrew Trick // Print value between 0 (0% probability) and 1 (100% probability), 599e76422b963a65f243fdbee0abed61068b82dd98Andrew Trick // however the value is never equal to 0, and can be 1 only iff SRC block 609e76422b963a65f243fdbee0abed61068b82dd98Andrew Trick // has only one successor. 6114edd314af99ccaad194d071f23e437a1371f176Chandler Carruth raw_ostream &printEdgeProbability(raw_ostream &OS, const BasicBlock *Src, 6214edd314af99ccaad194d071f23e437a1371f176Chandler Carruth const BasicBlock *Dst) const; 63b068bbbaecf338f481124551a5e6f37484fad800Chandler Carruth 64b068bbbaecf338f481124551a5e6f37484fad800Chandler Carruthprivate: 65b068bbbaecf338f481124551a5e6f37484fad800Chandler Carruth typedef std::pair<const BasicBlock *, const BasicBlock *> Edge; 66b068bbbaecf338f481124551a5e6f37484fad800Chandler Carruth 67b068bbbaecf338f481124551a5e6f37484fad800Chandler Carruth // Default weight value. Used when we don't have information about the edge. 68b068bbbaecf338f481124551a5e6f37484fad800Chandler Carruth // TODO: DEFAULT_WEIGHT makes sense during static predication, when none of 69b068bbbaecf338f481124551a5e6f37484fad800Chandler Carruth // the successors have a weight yet. But it doesn't make sense when providing 70b068bbbaecf338f481124551a5e6f37484fad800Chandler Carruth // weight to an edge that may have siblings with non-zero weights. This can 71b068bbbaecf338f481124551a5e6f37484fad800Chandler Carruth // be handled various ways, but it's probably fine for an edge with unknown 72b068bbbaecf338f481124551a5e6f37484fad800Chandler Carruth // weight to just "inherit" the non-zero weight of an adjacent successor. 73b068bbbaecf338f481124551a5e6f37484fad800Chandler Carruth static const uint32_t DEFAULT_WEIGHT = 16; 74b068bbbaecf338f481124551a5e6f37484fad800Chandler Carruth 75b068bbbaecf338f481124551a5e6f37484fad800Chandler Carruth DenseMap<Edge, uint32_t> Weights; 76b068bbbaecf338f481124551a5e6f37484fad800Chandler Carruth 77b068bbbaecf338f481124551a5e6f37484fad800Chandler Carruth /// \brief Handle to the LoopInfo analysis. 78b068bbbaecf338f481124551a5e6f37484fad800Chandler Carruth LoopInfo *LI; 79b068bbbaecf338f481124551a5e6f37484fad800Chandler Carruth 80b068bbbaecf338f481124551a5e6f37484fad800Chandler Carruth /// \brief Track the last function we run over for printing. 81b068bbbaecf338f481124551a5e6f37484fad800Chandler Carruth Function *LastF; 82b068bbbaecf338f481124551a5e6f37484fad800Chandler Carruth 83b068bbbaecf338f481124551a5e6f37484fad800Chandler Carruth /// \brief Get sum of the block successors' weights. 84b068bbbaecf338f481124551a5e6f37484fad800Chandler Carruth uint32_t getSumForBlock(const BasicBlock *BB) const; 85b068bbbaecf338f481124551a5e6f37484fad800Chandler Carruth 86b068bbbaecf338f481124551a5e6f37484fad800Chandler Carruth bool calcMetadataWeights(BasicBlock *BB); 87b068bbbaecf338f481124551a5e6f37484fad800Chandler Carruth bool calcReturnHeuristics(BasicBlock *BB); 88b068bbbaecf338f481124551a5e6f37484fad800Chandler Carruth bool calcPointerHeuristics(BasicBlock *BB); 89b068bbbaecf338f481124551a5e6f37484fad800Chandler Carruth bool calcLoopBranchHeuristics(BasicBlock *BB); 90b068bbbaecf338f481124551a5e6f37484fad800Chandler Carruth bool calcZeroHeuristics(BasicBlock *BB); 91b068bbbaecf338f481124551a5e6f37484fad800Chandler Carruth bool calcFloatingPointHeuristics(BasicBlock *BB); 929e76422b963a65f243fdbee0abed61068b82dd98Andrew Trick}; 939e76422b963a65f243fdbee0abed61068b82dd98Andrew Trick 949e76422b963a65f243fdbee0abed61068b82dd98Andrew Trick} 959e76422b963a65f243fdbee0abed61068b82dd98Andrew Trick 969e76422b963a65f243fdbee0abed61068b82dd98Andrew Trick#endif 97