From 44eb49c2a191108df801977c8e3dc03466c6c02a Mon Sep 17 00:00:00 2001 From: Jakub Staszak Date: Thu, 23 Jun 2011 21:45:20 +0000 Subject: [PATCH] Introduce BlockFrequency analysis for BasicBlocks. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@133766 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Analysis/BranchProbabilityInfo.h | 10 ++++++++ include/llvm/InitializePasses.h | 1 + include/llvm/Support/BranchProbability.h | 10 +++++++- lib/Analysis/Analysis.cpp | 1 + lib/Analysis/BranchProbabilityInfo.cpp | 24 +++++++++++++++++++ lib/Analysis/CMakeLists.txt | 1 + 6 files changed, 46 insertions(+), 1 deletion(-) diff --git a/include/llvm/Analysis/BranchProbabilityInfo.h b/include/llvm/Analysis/BranchProbabilityInfo.h index 5a17a76f5b4..e40d2044dc5 100644 --- a/include/llvm/Analysis/BranchProbabilityInfo.h +++ b/include/llvm/Analysis/BranchProbabilityInfo.h @@ -39,6 +39,9 @@ class BranchProbabilityInfo : public FunctionPass { // Get sum of the block successors' weights. uint32_t getSumForBlock(BasicBlock *BB) const; + // Get sum of the edge weights going to the BB block. + uint32_t getBackSumForBlock(BasicBlock *BB) const; + public: static char ID; @@ -71,6 +74,13 @@ public: // only iff SRC block has only one successor. BranchProbability getEdgeProbability(BasicBlock *Src, BasicBlock *Dst) const; + // Return a probability of getting to the DST block through SRC->DST edge. + // Returned value is a fraction between 0 (0% probability) and + // 1 (100% probability), however the value is never equal to 0, and can be 1 + // only iff DST block has only one predecesor. + BranchProbability getBackEdgeProbability(BasicBlock *Src, + BasicBlock *Dst) const; + // Print value between 0 (0% probability) and 1 (100% probability), // however the value is never equal to 0, and can be 1 only iff SRC block // has only one successor. diff --git a/include/llvm/InitializePasses.h b/include/llvm/InitializePasses.h index 5efdcc9976c..5dfc4b3ceb6 100644 --- a/include/llvm/InitializePasses.h +++ b/include/llvm/InitializePasses.h @@ -65,6 +65,7 @@ void initializeArgPromotionPass(PassRegistry&); void initializeBasicAliasAnalysisPass(PassRegistry&); void initializeBasicCallGraphPass(PassRegistry&); void initializeBlockExtractorPassPass(PassRegistry&); +void initializeBlockFrequencyPass(PassRegistry&); void initializeBlockPlacementPass(PassRegistry&); void initializeBranchProbabilityInfoPass(PassRegistry&); void initializeBreakCriticalEdgesPass(PassRegistry&); diff --git a/include/llvm/Support/BranchProbability.h b/include/llvm/Support/BranchProbability.h index 7ba649133b2..c66d2248866 100644 --- a/include/llvm/Support/BranchProbability.h +++ b/include/llvm/Support/BranchProbability.h @@ -18,13 +18,17 @@ namespace llvm { -class raw_ostream; +template +class BlockFrequencyImpl; class BranchProbabilityInfo; class MachineBranchProbabilityInfo; class MachineBasicBlock; +class raw_ostream; // This class represents Branch Probability as a non-negative fraction. class BranchProbability { + template + friend class BlockFrequencyImpl; friend class BranchProbabilityInfo; friend class MachineBranchProbabilityInfo; friend class MachineBasicBlock; @@ -38,6 +42,10 @@ class BranchProbability { BranchProbability(uint32_t n, uint32_t d); public: + + uint32_t getNumerator() const { return N; } + uint32_t getDenominator() const { return D; } + raw_ostream &print(raw_ostream &OS) const; void dump() const; diff --git a/lib/Analysis/Analysis.cpp b/lib/Analysis/Analysis.cpp index e57ba783329..71e0a832696 100644 --- a/lib/Analysis/Analysis.cpp +++ b/lib/Analysis/Analysis.cpp @@ -23,6 +23,7 @@ void llvm::initializeAnalysis(PassRegistry &Registry) { initializeAliasSetPrinterPass(Registry); initializeNoAAPass(Registry); initializeBasicAliasAnalysisPass(Registry); + initializeBlockFrequencyPass(Registry); initializeBranchProbabilityInfoPass(Registry); initializeCFGViewerPass(Registry); initializeCFGPrinterPass(Registry); diff --git a/lib/Analysis/BranchProbabilityInfo.cpp b/lib/Analysis/BranchProbabilityInfo.cpp index 15059c733ab..263ea2c26b0 100644 --- a/lib/Analysis/BranchProbabilityInfo.cpp +++ b/lib/Analysis/BranchProbabilityInfo.cpp @@ -279,6 +279,21 @@ uint32_t BranchProbabilityInfo::getSumForBlock(BasicBlock *BB) const { return Sum; } +uint32_t BranchProbabilityInfo::getBackSumForBlock(BasicBlock *BB) const { + uint32_t Sum = 0; + + for (pred_iterator I = pred_begin(BB), E = pred_end(BB); I != E; ++I) { + BasicBlock *Pred = *I; + uint32_t Weight = getEdgeWeight(Pred, BB); + uint32_t PrevSum = Sum; + + Sum += Weight; + assert(Sum > PrevSum); (void) PrevSum; + } + + return Sum; +} + bool BranchProbabilityInfo::isEdgeHot(BasicBlock *Src, BasicBlock *Dst) const { // Hot probability is at least 4/5 = 80% uint32_t Weight = getEdgeWeight(Src, Dst); @@ -345,6 +360,15 @@ getEdgeProbability(BasicBlock *Src, BasicBlock *Dst) const { return BranchProbability(N, D); } +BranchProbability BranchProbabilityInfo:: +getBackEdgeProbability(BasicBlock *Src, BasicBlock *Dst) const { + + uint32_t N = getEdgeWeight(Src, Dst); + uint32_t D = getBackSumForBlock(Dst); + + return BranchProbability(N, D); +} + raw_ostream & BranchProbabilityInfo::printEdgeProbability(raw_ostream &OS, BasicBlock *Src, BasicBlock *Dst) const { diff --git a/lib/Analysis/CMakeLists.txt b/lib/Analysis/CMakeLists.txt index 1a975bf4a58..ab846a26b4d 100644 --- a/lib/Analysis/CMakeLists.txt +++ b/lib/Analysis/CMakeLists.txt @@ -6,6 +6,7 @@ add_llvm_library(LLVMAnalysis AliasSetTracker.cpp Analysis.cpp BasicAliasAnalysis.cpp + BlockFrequency.cpp BranchProbabilityInfo.cpp CFGPrinter.cpp CaptureTracking.cpp -- 2.34.1