summaryrefslogtreecommitdiffstats
path: root/include
diff options
context:
space:
mode:
authorMichael Gottesman <mgottesman@apple.com>2013-11-17 03:25:24 +0000
committerMichael Gottesman <mgottesman@apple.com>2013-11-17 03:25:24 +0000
commite7a1e3ee8279f12d0f2b49fb198d577949795c88 (patch)
tree14e5e6af966229b0636a5b96eb1a736b33c18df8 /include
parent8417e857818e972f318bd549caabc54bdf537c26 (diff)
downloadexternal_llvm-e7a1e3ee8279f12d0f2b49fb198d577949795c88.zip
external_llvm-e7a1e3ee8279f12d0f2b49fb198d577949795c88.tar.gz
external_llvm-e7a1e3ee8279f12d0f2b49fb198d577949795c88.tar.bz2
[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
Diffstat (limited to 'include')
-rw-r--r--include/llvm/Support/BlockFrequency.h10
1 files changed, 8 insertions, 2 deletions
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;
}