Minimize precision loss when computing cyclic probabilities.

[oota-llvm.git] / include / llvm / Analysis / BlockFrequencyImpl.h

diff --git a/include/llvm/Analysis/BlockFrequencyImpl.h b/include/llvm/Analysis/BlockFrequencyImpl.h
index c4c16016f7106207ed810392729923f090f8cb63..c9067a0721b0c8e70bb2a67595a9d45e2651bffc 100644 (file)
--- a/include/llvm/Analysis/BlockFrequencyImpl.h
+++ b/include/llvm/Analysis/BlockFrequencyImpl.h
@@ -85,31 +85,16 @@ class BlockFrequencyImpl {
                  << " --> " << Freqs[BB] << "\n");
   }
 
-  /// divBlockFreq - Divide BB block frequency by PROB. If Prob = 0 do nothing.
-  ///
-  void divBlockFreq(BlockT *BB, BranchProbability Prob) {
-    uint64_t N = Prob.getNumerator();
-    assert(N && "Illegal division by zero!");
-    uint64_t D = Prob.getDenominator();
-    uint64_t Freq = (Freqs[BB].getFrequency() * D) / N;
-
-    // Should we assert it?
-    if (Freq > UINT32_MAX)
-      Freq = UINT32_MAX;
-
-    Freqs[BB] = BlockFrequency(Freq);
-    DEBUG(dbgs() << "Frequency(" << getBlockName(BB) << ") /= (" << Prob
-                 << ") --> " << Freqs[BB] << "\n");
-  }
-
   // All blocks in postorder.
   std::vector<BlockT *> POT;
 
   // Map Block -> Position in reverse-postorder list.
   DenseMap<BlockT *, unsigned> RPO;
 
-  // Cycle Probability for each bloch.
-  DenseMap<BlockT *, uint32_t> CycleProb;
+  // For each loop header, record the per-iteration probability of exiting the
+  // loop. This is the reciprocal of the expected number of loop iterations.
+  typedef DenseMap<BlockT*, BranchProbability> LoopExitProbMap;
+  LoopExitProbMap LoopExitProb;
 
   // (reverse-)postorder traversal iterators.
   typedef typename std::vector<BlockT *>::iterator pot_iterator;
@@ -203,10 +188,13 @@ class BlockFrequencyImpl {
     if (!isLoopHead)
       return;
 
-    assert(EntryFreq >= CycleProb[BB]);
-    uint32_t CProb = CycleProb[BB];
-    uint32_t Numerator = EntryFreq - CProb ? EntryFreq - CProb : 1;
-    divBlockFreq(BB, BranchProbability(Numerator, EntryFreq));
+    // This block is a loop header, so boost its frequency by the expected
+    // number of loop iterations. The loop blocks will be revisited so they all
+    // get this boost.
+    typename LoopExitProbMap::const_iterator I = LoopExitProb.find(BB);
+    assert(I != LoopExitProb.end() && "Loop header missing from table");
+    Freqs[BB] /= I->second;
+    DEBUG(dbgs() << "Loop header scaled to " << Freqs[BB] << ".\n");
   }
 
   /// doLoop - Propagate block frequency down through the loop.
@@ -226,24 +214,50 @@ class BlockFrequencyImpl {
     }
 
     // Compute loop's cyclic probability using backedges probabilities.
+    BlockFrequency BackFreq;
     for (typename GT::ChildIteratorType
          PI = GraphTraits< Inverse<BlockT *> >::child_begin(Head),
          PE = GraphTraits< Inverse<BlockT *> >::child_end(Head);
          PI != PE; ++PI) {
       BlockT *Pred = *PI;
       assert(Pred);
-      if (isBackedge(Pred, Head)) {
-        uint64_t N = getEdgeFreq(Pred, Head).getFrequency();
-        uint64_t D = getBlockFreq(Head).getFrequency();
-        assert(N <= EntryFreq && "Backedge frequency must be <= EntryFreq!");
-        uint64_t Res = (N * EntryFreq) / D;
-
-        assert(Res <= UINT32_MAX);
-        CycleProb[Head] += (uint32_t) Res;
-        DEBUG(dbgs() << "  CycleProb[" << getBlockName(Head) << "] += " << Res
-                     << " --> " << CycleProb[Head] << "\n");
-      }
+      if (isBackedge(Pred, Head))
+        BackFreq += getEdgeFreq(Pred, Head);
+    }
+
+    // The cyclic probability is freq(BackEdges) / freq(Head), where freq(Head)
+    // only counts edges entering the loop, not the loop backedges.
+    // The probability of leaving the loop on each iteration is:
+    //
+    //   ExitProb = 1 - CyclicProb
+    //
+    // The Expected number of loop iterations is:
+    //
+    //   Iterations = 1 / ExitProb
+    //
+    uint64_t D = std::max(getBlockFreq(Head).getFrequency(), 1ull);
+    uint64_t N = std::max(BackFreq.getFrequency(), 1ull);
+    if (N < D)
+      N = D - N;
+    else
+      // We'd expect N < D, but rounding and saturation means that can't be
+      // guaranteed.
+      N = 1;
+
+    // Now ExitProb = N / D, make sure it fits in an i32/i32 fraction.
+    assert(N <= D);
+    if (D > UINT32_MAX) {
+      unsigned Shift = 32 - countLeadingZeros(D);
+      D >>= Shift;
+      N >>= Shift;
+      if (N == 0)
+        N = 1;
     }
+    BranchProbability LEP = BranchProbability(N, D);
+    LoopExitProb.insert(std::make_pair(Head, LEP));
+    DEBUG(dbgs() << "LoopExitProb[" << getBlockName(Head) << "] = " << LEP
+                 << " from 1 - " << BackFreq << " / " << getBlockFreq(Head)
+                 << ".\n");
   }
 
   friend class BlockFrequencyInfo;
@@ -258,7 +272,7 @@ class BlockFrequencyImpl {
     // Clear everything.
     RPO.clear();
     POT.clear();
-    CycleProb.clear();
+    LoopExitProb.clear();
     Freqs.clear();
 
     BlockT *EntryBlock = fn->begin();