[block-freq] Add BlockFrequency::scale that returns a remainder from the division and make the private scale in BlockFrequency more performant.

This change is the first in a series of changes improving LLVM's Block
Frequency propogation implementation to not lose probability mass in
branchy code when propogating block frequency information from a basic
block to its successors. This patch is a simple infrastructure
improvement that does not actually modify the block frequency
algorithm. The specific changes are:

1. Changes the division algorithm used when scaling block frequencies by
branch probabilities to a short division algorithm. This gives us the
remainder for free as well as provides a nice speed boost. When I
benched the old routine and the new routine on a Sandy Bridge iMac with
disabled turbo mode performing 8192 iterations on an array of length
32768, I saw ~600% increase in speed in mean/median performance.

2. Exposes a scale method that returns a remainder. This is important so
we can ensure that when we scale a block frequency by some branch
probability BP = N/D, the remainder from the division by D can be
retrieved and propagated to other children to ensure no probability mass
is lost (more to come on this).

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

1 files changed, 8 insertions, 2 deletions

diff --git a/include/llvm/Support/BlockFrequency.h b/include/llvm/Support/BlockFrequency.h
index 666b3c822d..21879e7cbe 100644
--- a/include/llvm/Support/BlockFrequency.h
+++ b/include/llvm/Support/BlockFrequency.h
@@ -27,8 +27,10 @@ class BlockFrequency {
   uint64_t Frequency;
   static const int64_t ENTRY_FREQ = 1 << 14;
 
-  // Scale frequency by N/D, saturating on overflow.
-  void scale(uint32_t N, uint32_t D);
+  /// \brief Scale the given BlockFrequency by N/D. Return the remainder from
+  /// the division by D. Upon overflow, the routine will saturate and
+  /// additionally will return the remainder set to D.
+  uint32_t scale(uint32_t N, uint32_t D);
 
 public:
   BlockFrequency(uint64_t Freq = 0) : Frequency(Freq) { }
@@ -57,6 +59,10 @@ public:
   BlockFrequency &operator+=(const BlockFrequency &Freq);
   const BlockFrequency operator+(const BlockFrequency &Freq) const;
 
+  /// \brief Scale the given BlockFrequency by N/D. Return the remainder from
+  /// the division by D. Upon overflow, the routine will saturate.
+  uint32_t scale(const BranchProbability &Prob);
+
   bool operator<(const BlockFrequency &RHS) const {
     return Frequency < RHS.Frequency;
   }