diff options
author | Jakob Stoklund Olesen <stoklund@2pi.dk> | 2013-06-28 18:23:42 +0000 |
---|---|---|
committer | Jakob Stoklund Olesen <stoklund@2pi.dk> | 2013-06-28 18:23:42 +0000 |
commit | d7648ff20f8bbc8217a26576ca96addc55e003de (patch) | |
tree | 533f916f95e5936947c567f3d37c2a478d8224cd /lib | |
parent | f52578c08c71dc356428c25b0ba8759fd7ee2c66 (diff) | |
download | external_llvm-d7648ff20f8bbc8217a26576ca96addc55e003de.zip external_llvm-d7648ff20f8bbc8217a26576ca96addc55e003de.tar.gz external_llvm-d7648ff20f8bbc8217a26576ca96addc55e003de.tar.bz2 |
Add a division operator to BlockFrequency.
Allow a BlockFrequency to be divided by a non-zero BranchProbability
with saturating arithmetic. This will be used to compute the frequency
of a loop header given the probability of leaving the loop.
Our long division algorithm already saturates on overflow, so that was a
freebie.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@185184 91177308-0d34-0410-b5e6-96231b3b80d8
Diffstat (limited to 'lib')
-rw-r--r-- | lib/Support/BlockFrequency.cpp | 58 |
1 files changed, 35 insertions, 23 deletions
diff --git a/lib/Support/BlockFrequency.cpp b/lib/Support/BlockFrequency.cpp index 572dbf5..08fa620 100644 --- a/lib/Support/BlockFrequency.cpp +++ b/lib/Support/BlockFrequency.cpp @@ -42,12 +42,14 @@ void mult96bit(uint64_t freq, uint32_t N, uint64_t W[2]) { } -/// div96bit - Divide 96-bit value stored in W array by D. Return 64-bit frequency. +/// div96bit - Divide 96-bit value stored in W array by D. +/// Return 64-bit quotient, saturated to UINT64_MAX on overflow. uint64_t div96bit(uint64_t W[2], uint32_t D) { uint64_t y = W[0]; uint64_t x = W[1]; int i; + // This long division algorithm automatically saturates on overflow. for (i = 1; i <= 64 && x; ++i) { uint32_t t = (int)x >> 31; x = (x << 1) | (y >> 63); @@ -63,31 +65,30 @@ uint64_t div96bit(uint64_t W[2], uint32_t D) { } +void BlockFrequency::scale(uint32_t N, uint32_t D) { + assert(D != 0 && "Division by zero"); -BlockFrequency &BlockFrequency::operator*=(const BranchProbability &Prob) { - uint32_t n = Prob.getNumerator(); - uint32_t d = Prob.getDenominator(); - - assert(n <= d && "Probability must be less or equal to 1."); - - // Calculate Frequency * n. - uint64_t mulLo = (Frequency & UINT32_MAX) * n; - uint64_t mulHi = (Frequency >> 32) * n; - uint64_t mulRes = (mulHi << 32) + mulLo; - - // If there was overflow use 96-bit operations. - if (mulHi > UINT32_MAX || mulRes < mulLo) { - // 96-bit value represented as W[1]:W[0]. - uint64_t W[2]; - - // Probability is less or equal to 1 which means that results must fit - // 64-bit. - mult96bit(Frequency, n, W); - Frequency = div96bit(W, d); - return *this; + // Calculate Frequency * N. + uint64_t MulLo = (Frequency & UINT32_MAX) * N; + uint64_t MulHi = (Frequency >> 32) * N; + uint64_t MulRes = (MulHi << 32) + MulLo; + + // If the product fits in 64 bits, just use built-in division. + if (MulHi <= UINT32_MAX && MulRes <= MulLo) { + Frequency = MulRes / D; + return; } - Frequency = mulRes / d; + // Product overflowed, use 96-bit operations. + // 96-bit value represented as W[1]:W[0]. + uint64_t W[2]; + mult96bit(Frequency, N, W); + Frequency = div96bit(W, D); + return; +} + +BlockFrequency &BlockFrequency::operator*=(const BranchProbability &Prob) { + scale(Prob.getNumerator(), Prob.getDenominator()); return *this; } @@ -98,6 +99,17 @@ BlockFrequency::operator*(const BranchProbability &Prob) const { return Freq; } +BlockFrequency &BlockFrequency::operator/=(const BranchProbability &Prob) { + scale(Prob.getDenominator(), Prob.getNumerator()); + return *this; +} + +BlockFrequency BlockFrequency::operator/(const BranchProbability &Prob) const { + BlockFrequency Freq(Frequency); + Freq /= Prob; + return Freq; +} + BlockFrequency &BlockFrequency::operator+=(const BlockFrequency &Freq) { uint64_t Before = Freq.Frequency; Frequency += Freq.Frequency; |