From e7a1e3ee8279f12d0f2b49fb198d577949795c88 Mon Sep 17 00:00:00 2001 From: Michael Gottesman Date: Sun, 17 Nov 2013 03:25:24 +0000 Subject: [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 --- include/llvm/Support/BlockFrequency.h | 10 ++++++++-- 1 file changed, 8 insertions(+), 2 deletions(-) (limited to 'include') diff --git a/include/llvm/Support/BlockFrequency.h b/include/llvm/Support/BlockFrequency.h index 666b3c8..21879e7 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; } -- cgit v1.1