Introduce BlockFrequency analysis for BasicBlocks.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@133766 91177308-0d34-0410-b5e6-96231b3b80d8

diff --git a/include/llvm/Analysis/BranchProbabilityInfo.h b/include/llvm/Analysis/BranchProbabilityInfo.h
index 5a17a76f5b4aa7285d43924bdf1fb48138c0d7a4..e40d2044dc56ed3434b2c471e78cdc79f1eca3a5 100644 (file)
--- 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 5efdcc9976cc2b0387e97c139c600045561ba4d0..5dfc4b3ceb6de08b32976bf68b7c78a8144828c3 100644 (file)
--- 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 7ba649133b29150a8d33eb65a1435522a830454a..c66d2248866cba31725866709ea9076d147808b9 100644 (file)
--- a/include/llvm/Support/BranchProbability.h
+++ b/include/llvm/Support/BranchProbability.h
@@ -18,13 +18,17 @@
 
 namespace llvm {
 
-class raw_ostream;
+template<class BlockT, class FunctionT, class BranchProbInfoT>
+class BlockFrequencyImpl;
 class BranchProbabilityInfo;
 class MachineBranchProbabilityInfo;
 class MachineBasicBlock;
+class raw_ostream;
 
 // This class represents Branch Probability as a non-negative fraction.
 class BranchProbability {
+  template<class BlockT, class FunctionT, class BranchProbInfoT>
+  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 e57ba783329500aa86abe4e2649a915f1f101443..71e0a832696ce73f313bc3b5f0c671e6579ef9e0 100644 (file)
--- 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 15059c733ab6aaca24c00793cae19e16463dd8eb..263ea2c26b06611d6b3d42c9f2683a7a6dab74ef 100644 (file)
--- 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 1a975bf4a582ad2f232f231f3fad41b2ab8cb9e4..ab846a26b4db8cf5c0fa6f51a67e1de2886a74bc 100644 (file)
--- 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