diff options
author | Jakob Stoklund Olesen <stoklund@2pi.dk> | 2013-06-28 22:40:43 +0000 |
---|---|---|
committer | Jakob Stoklund Olesen <stoklund@2pi.dk> | 2013-06-28 22:40:43 +0000 |
commit | 97be1d608e0fd8f0578342932b3b8116e5028a02 (patch) | |
tree | 5ece32ea44d40cf58ec988e29428dac2e81215e9 /include/llvm/Analysis | |
parent | 6a636a813f33b46b3271ec8517ee1936a0c92c9f (diff) | |
download | llvm-97be1d608e0fd8f0578342932b3b8116e5028a02.tar.gz llvm-97be1d608e0fd8f0578342932b3b8116e5028a02.tar.bz2 llvm-97be1d608e0fd8f0578342932b3b8116e5028a02.tar.xz |
Minimize precision loss when computing cyclic probabilities.
Allow block frequencies to exceed 32 bits by using the new
BlockFrequency division function.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@185236 91177308-0d34-0410-b5e6-96231b3b80d8
Diffstat (limited to 'include/llvm/Analysis')
-rw-r--r-- | include/llvm/Analysis/BlockFrequencyImpl.h | 84 |
1 files changed, 49 insertions, 35 deletions
diff --git a/include/llvm/Analysis/BlockFrequencyImpl.h b/include/llvm/Analysis/BlockFrequencyImpl.h index c4c16016f7..c9067a0721 100644 --- 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(); |