1 //===-- BlockFrequencyImpl.h - Block Frequency Implementation --*- C++ -*--===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // Shared implementation of BlockFrequency for IR and Machine Instructions.
12 //===----------------------------------------------------------------------===//
14 #ifndef LLVM_ANALYSIS_BLOCKFREQUENCYIMPL_H
15 #define LLVM_ANALYSIS_BLOCKFREQUENCYIMPL_H
17 #include "llvm/ADT/DenseMap.h"
18 #include "llvm/ADT/PostOrderIterator.h"
19 #include "llvm/CodeGen/MachineBasicBlock.h"
20 #include "llvm/CodeGen/MachineFunction.h"
21 #include "llvm/IR/BasicBlock.h"
22 #include "llvm/Support/BlockFrequency.h"
23 #include "llvm/Support/BranchProbability.h"
24 #include "llvm/Support/Debug.h"
25 #include "llvm/Support/raw_ostream.h"
32 class BlockFrequencyInfo;
33 class MachineBlockFrequencyInfo;
35 /// BlockFrequencyImpl implements block frequency algorithm for IR and
36 /// Machine Instructions. Algorithm starts with value ENTRY_FREQ
37 /// for the entry block and then propagates frequencies using branch weights
38 /// from (Machine)BranchProbabilityInfo. LoopInfo is not required because
39 /// algorithm can find "backedges" by itself.
40 template<class BlockT, class FunctionT, class BlockProbInfoT>
41 class BlockFrequencyImpl {
43 DenseMap<const BlockT *, BlockFrequency> Freqs;
49 typedef GraphTraits< Inverse<BlockT *> > GT;
51 const uint32_t EntryFreq;
53 std::string getBlockName(BasicBlock *BB) const {
54 return BB->getName().str();
57 std::string getBlockName(MachineBasicBlock *MBB) const {
59 raw_string_ostream ss(str);
60 ss << "BB#" << MBB->getNumber();
62 if (const BasicBlock *BB = MBB->getBasicBlock())
63 ss << " derived from LLVM BB " << BB->getName();
68 void setBlockFreq(BlockT *BB, BlockFrequency Freq) {
70 DEBUG(dbgs() << "Frequency(" << getBlockName(BB) << ") = " << Freq << "\n");
73 /// getEdgeFreq - Return edge frequency based on SRC frequency and Src -> Dst
75 BlockFrequency getEdgeFreq(BlockT *Src, BlockT *Dst) const {
76 BranchProbability Prob = BPI->getEdgeProbability(Src, Dst);
77 return getBlockFreq(Src) * Prob;
80 /// incBlockFreq - Increase BB block frequency by FREQ.
82 void incBlockFreq(BlockT *BB, BlockFrequency Freq) {
84 DEBUG(dbgs() << "Frequency(" << getBlockName(BB) << ") += " << Freq
85 << " --> " << Freqs[BB] << "\n");
88 // All blocks in postorder.
89 std::vector<BlockT *> POT;
91 // Map Block -> Position in reverse-postorder list.
92 DenseMap<BlockT *, unsigned> RPO;
94 // For each loop header, record the per-iteration probability of exiting the
95 // loop. This is the reciprocal of the expected number of loop iterations.
96 typedef DenseMap<BlockT*, BranchProbability> LoopExitProbMap;
97 LoopExitProbMap LoopExitProb;
99 // (reverse-)postorder traversal iterators.
100 typedef typename std::vector<BlockT *>::iterator pot_iterator;
101 typedef typename std::vector<BlockT *>::reverse_iterator rpot_iterator;
103 pot_iterator pot_begin() { return POT.begin(); }
104 pot_iterator pot_end() { return POT.end(); }
106 rpot_iterator rpot_begin() { return POT.rbegin(); }
107 rpot_iterator rpot_end() { return POT.rend(); }
109 rpot_iterator rpot_at(BlockT *BB) {
110 rpot_iterator I = rpot_begin();
111 unsigned idx = RPO.lookup(BB);
113 std::advance(I, idx - 1);
119 /// isBackedge - Return if edge Src -> Dst is a reachable backedge.
121 bool isBackedge(BlockT *Src, BlockT *Dst) {
122 unsigned a = RPO.lookup(Src);
125 unsigned b = RPO.lookup(Dst);
126 assert(b && "Destination block should be reachable");
130 /// getSingleBlockPred - return single BB block predecessor or NULL if
131 /// BB has none or more predecessors.
132 BlockT *getSingleBlockPred(BlockT *BB) {
133 typename GT::ChildIteratorType
134 PI = GraphTraits< Inverse<BlockT *> >::child_begin(BB),
135 PE = GraphTraits< Inverse<BlockT *> >::child_end(BB);
149 void doBlock(BlockT *BB, BlockT *LoopHead,
150 SmallPtrSet<BlockT *, 8> &BlocksInLoop) {
152 DEBUG(dbgs() << "doBlock(" << getBlockName(BB) << ")\n");
155 if (BB == LoopHead) {
156 setBlockFreq(BB, EntryFreq);
160 if(BlockT *Pred = getSingleBlockPred(BB)) {
161 if (BlocksInLoop.count(Pred))
162 setBlockFreq(BB, getEdgeFreq(Pred, BB));
163 // TODO: else? irreducible, ignore it for now.
167 bool isInLoop = false;
168 bool isLoopHead = false;
170 for (typename GT::ChildIteratorType
171 PI = GraphTraits< Inverse<BlockT *> >::child_begin(BB),
172 PE = GraphTraits< Inverse<BlockT *> >::child_end(BB);
176 if (isBackedge(Pred, BB)) {
178 } else if (BlocksInLoop.count(Pred)) {
179 incBlockFreq(BB, getEdgeFreq(Pred, BB));
182 // TODO: else? irreducible.
191 // This block is a loop header, so boost its frequency by the expected
192 // number of loop iterations. The loop blocks will be revisited so they all
194 typename LoopExitProbMap::const_iterator I = LoopExitProb.find(BB);
195 assert(I != LoopExitProb.end() && "Loop header missing from table");
196 Freqs[BB] /= I->second;
197 DEBUG(dbgs() << "Loop header scaled to " << Freqs[BB] << ".\n");
200 /// doLoop - Propagate block frequency down through the loop.
201 void doLoop(BlockT *Head, BlockT *Tail) {
202 DEBUG(dbgs() << "doLoop(" << getBlockName(Head) << ", "
203 << getBlockName(Tail) << ")\n");
205 SmallPtrSet<BlockT *, 8> BlocksInLoop;
207 for (rpot_iterator I = rpot_at(Head), E = rpot_at(Tail); ; ++I) {
209 doBlock(BB, Head, BlocksInLoop);
211 BlocksInLoop.insert(BB);
216 // Compute loop's cyclic probability using backedges probabilities.
217 BlockFrequency BackFreq;
218 for (typename GT::ChildIteratorType
219 PI = GraphTraits< Inverse<BlockT *> >::child_begin(Head),
220 PE = GraphTraits< Inverse<BlockT *> >::child_end(Head);
224 if (isBackedge(Pred, Head))
225 BackFreq += getEdgeFreq(Pred, Head);
228 // The cyclic probability is freq(BackEdges) / freq(Head), where freq(Head)
229 // only counts edges entering the loop, not the loop backedges.
230 // The probability of leaving the loop on each iteration is:
232 // ExitProb = 1 - CyclicProb
234 // The Expected number of loop iterations is:
236 // Iterations = 1 / ExitProb
238 uint64_t D = std::max(getBlockFreq(Head).getFrequency(), UINT64_C(1));
239 uint64_t N = std::max(BackFreq.getFrequency(), UINT64_C(1));
243 // We'd expect N < D, but rounding and saturation means that can't be
247 // Now ExitProb = N / D, make sure it fits in an i32/i32 fraction.
249 if (D > UINT32_MAX) {
250 unsigned Shift = 32 - countLeadingZeros(D);
256 BranchProbability LEP = BranchProbability(N, D);
257 LoopExitProb.insert(std::make_pair(Head, LEP));
258 DEBUG(dbgs() << "LoopExitProb[" << getBlockName(Head) << "] = " << LEP
259 << " from 1 - " << BackFreq << " / " << getBlockFreq(Head)
263 friend class BlockFrequencyInfo;
264 friend class MachineBlockFrequencyInfo;
266 BlockFrequencyImpl() : EntryFreq(BlockFrequency::getEntryFrequency()) { }
268 void doFunction(FunctionT *fn, BlockProbInfoT *bpi) {
275 LoopExitProb.clear();
278 BlockT *EntryBlock = fn->begin();
280 std::copy(po_begin(EntryBlock), po_end(EntryBlock), std::back_inserter(POT));
283 for (rpot_iterator I = rpot_begin(), E = rpot_end(); I != E; ++I) {
286 DEBUG(dbgs() << "RPO[" << getBlockName(BB) << "] = " << RPO[BB] << "\n");
289 // Travel over all blocks in postorder.
290 for (pot_iterator I = pot_begin(), E = pot_end(); I != E; ++I) {
292 BlockT *LastTail = 0;
293 DEBUG(dbgs() << "POT: " << getBlockName(BB) << "\n");
295 for (typename GT::ChildIteratorType
296 PI = GraphTraits< Inverse<BlockT *> >::child_begin(BB),
297 PE = GraphTraits< Inverse<BlockT *> >::child_end(BB);
301 if (isBackedge(Pred, BB) && (!LastTail || RPO[Pred] > RPO[LastTail]))
306 doLoop(BB, LastTail);
309 // At the end assume the whole function as a loop, and travel over it once
311 doLoop(*(rpot_begin()), *(pot_begin()));
315 /// getBlockFreq - Return block frequency. Return 0 if we don't have it.
316 BlockFrequency getBlockFreq(const BlockT *BB) const {
317 typename DenseMap<const BlockT *, BlockFrequency>::const_iterator
319 if (I != Freqs.end())
324 void print(raw_ostream &OS) const {
325 OS << "\n\n---- Block Freqs ----\n";
326 for (typename FunctionT::iterator I = Fn->begin(), E = Fn->end(); I != E;) {
328 OS << " " << getBlockName(BB) << " = " << getBlockFreq(BB) << "\n";
330 for (typename GraphTraits<BlockT *>::ChildIteratorType
331 SI = GraphTraits<BlockT *>::child_begin(BB),
332 SE = GraphTraits<BlockT *>::child_end(BB); SI != SE; ++SI) {
334 OS << " " << getBlockName(BB) << " -> " << getBlockName(Succ)
335 << " = " << getEdgeFreq(BB, Succ) << "\n";