1 //===---- BlockFrequencyImpl.h - Machine Block Frequency Implementation ---===//
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/BasicBlock.h"
18 #include "llvm/ADT/DenseMap.h"
19 #include "llvm/ADT/PostOrderIterator.h"
20 #include "llvm/CodeGen/MachineBasicBlock.h"
21 #include "llvm/CodeGen/MachineFunction.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 1024 (START_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 /// divBlockFreq - Divide BB block frequency by PROB. If Prob = 0 do nothing.
90 void divBlockFreq(BlockT *BB, BranchProbability Prob) {
91 uint64_t N = Prob.getNumerator();
92 assert(N && "Illegal division by zero!");
93 uint64_t D = Prob.getDenominator();
94 uint64_t Freq = (Freqs[BB].getFrequency() * D) / N;
96 // Should we assert it?
97 if (Freq > UINT32_MAX)
100 Freqs[BB] = BlockFrequency(Freq);
101 DEBUG(dbgs() << "Frequency(" << getBlockName(BB) << ") /= (" << Prob
102 << ") --> " << Freqs[BB] << "\n");
105 // All blocks in postorder.
106 std::vector<BlockT *> POT;
108 // Map Block -> Position in reverse-postorder list.
109 DenseMap<BlockT *, unsigned> RPO;
111 // Cycle Probability for each bloch.
112 DenseMap<BlockT *, uint32_t> CycleProb;
114 // (reverse-)postorder traversal iterators.
115 typedef typename std::vector<BlockT *>::iterator pot_iterator;
116 typedef typename std::vector<BlockT *>::reverse_iterator rpot_iterator;
118 pot_iterator pot_begin() { return POT.begin(); }
119 pot_iterator pot_end() { return POT.end(); }
121 rpot_iterator rpot_begin() { return POT.rbegin(); }
122 rpot_iterator rpot_end() { return POT.rend(); }
124 rpot_iterator rpot_at(BlockT *BB) {
125 rpot_iterator I = rpot_begin();
126 unsigned idx = RPO[BB];
128 std::advance(I, idx - 1);
135 /// isReachable - Returns if BB block is reachable from the entry.
137 bool isReachable(BlockT *BB) {
138 return RPO.count(BB);
141 /// isBackedge - Return if edge Src -> Dst is a backedge.
143 bool isBackedge(BlockT *Src, BlockT *Dst) {
144 assert(isReachable(Src));
145 assert(isReachable(Dst));
147 unsigned a = RPO[Src];
148 unsigned b = RPO[Dst];
153 /// getSingleBlockPred - return single BB block predecessor or NULL if
154 /// BB has none or more predecessors.
155 BlockT *getSingleBlockPred(BlockT *BB) {
156 typename GT::ChildIteratorType
157 PI = GraphTraits< Inverse<BlockT *> >::child_begin(BB),
158 PE = GraphTraits< Inverse<BlockT *> >::child_end(BB);
172 void doBlock(BlockT *BB, BlockT *LoopHead,
173 SmallPtrSet<BlockT *, 8> &BlocksInLoop) {
175 DEBUG(dbgs() << "doBlock(" << getBlockName(BB) << ")\n");
178 if (BB == LoopHead) {
179 setBlockFreq(BB, EntryFreq);
183 if(BlockT *Pred = getSingleBlockPred(BB)) {
184 if (BlocksInLoop.count(Pred))
185 setBlockFreq(BB, getEdgeFreq(Pred, BB));
186 // TODO: else? irreducible, ignore it for now.
190 bool isInLoop = false;
191 bool isLoopHead = false;
193 for (typename GT::ChildIteratorType
194 PI = GraphTraits< Inverse<BlockT *> >::child_begin(BB),
195 PE = GraphTraits< Inverse<BlockT *> >::child_end(BB);
199 if (isReachable(Pred) && isBackedge(Pred, BB)) {
201 } else if (BlocksInLoop.count(Pred)) {
202 incBlockFreq(BB, getEdgeFreq(Pred, BB));
205 // TODO: else? irreducible.
214 assert(EntryFreq >= CycleProb[BB]);
215 uint32_t CProb = CycleProb[BB];
216 uint32_t Numerator = EntryFreq - CProb ? EntryFreq - CProb : 1;
217 divBlockFreq(BB, BranchProbability(Numerator, EntryFreq));
220 /// doLoop - Propagate block frequency down throught the loop.
221 void doLoop(BlockT *Head, BlockT *Tail) {
222 DEBUG(dbgs() << "doLoop(" << getBlockName(Head) << ", "
223 << getBlockName(Tail) << ")\n");
225 SmallPtrSet<BlockT *, 8> BlocksInLoop;
227 for (rpot_iterator I = rpot_at(Head), E = rpot_at(Tail); ; ++I) {
229 doBlock(BB, Head, BlocksInLoop);
231 BlocksInLoop.insert(BB);
236 // Compute loop's cyclic probability using backedges probabilities.
237 for (typename GT::ChildIteratorType
238 PI = GraphTraits< Inverse<BlockT *> >::child_begin(Head),
239 PE = GraphTraits< Inverse<BlockT *> >::child_end(Head);
243 if (isReachable(Pred) && isBackedge(Pred, Head)) {
244 uint64_t N = getEdgeFreq(Pred, Head).getFrequency();
245 uint64_t D = getBlockFreq(Head).getFrequency();
246 assert(N <= EntryFreq && "Backedge frequency must be <= EntryFreq!");
247 uint64_t Res = (N * EntryFreq) / D;
249 assert(Res <= UINT32_MAX);
250 CycleProb[Head] += (uint32_t) Res;
251 DEBUG(dbgs() << " CycleProb[" << getBlockName(Head) << "] += " << Res
252 << " --> " << CycleProb[Head] << "\n");
257 friend class BlockFrequencyInfo;
258 friend class MachineBlockFrequencyInfo;
260 BlockFrequencyImpl() : EntryFreq(BlockFrequency::getEntryFrequency()) { }
262 void doFunction(FunctionT *fn, BlockProbInfoT *bpi) {
272 BlockT *EntryBlock = fn->begin();
274 copy(po_begin(EntryBlock), po_end(EntryBlock), back_inserter(POT));
277 for (rpot_iterator I = rpot_begin(), E = rpot_end(); I != E; ++I) {
280 DEBUG(dbgs() << "RPO[" << getBlockName(BB) << "] = " << RPO[BB] << "\n");
283 // Travel over all blocks in postorder.
284 for (pot_iterator I = pot_begin(), E = pot_end(); I != E; ++I) {
286 BlockT *LastTail = 0;
287 DEBUG(dbgs() << "POT: " << getBlockName(BB) << "\n");
289 for (typename GT::ChildIteratorType
290 PI = GraphTraits< Inverse<BlockT *> >::child_begin(BB),
291 PE = GraphTraits< Inverse<BlockT *> >::child_end(BB);
295 if (isReachable(Pred) && isBackedge(Pred, BB)
296 && (!LastTail || RPO[Pred] > RPO[LastTail]))
301 doLoop(BB, LastTail);
304 // At the end assume the whole function as a loop, and travel over it once
306 doLoop(*(rpot_begin()), *(pot_begin()));
310 /// getBlockFreq - Return block frequency. Return 0 if we don't have it.
311 BlockFrequency getBlockFreq(const BlockT *BB) const {
312 typename DenseMap<const BlockT *, BlockFrequency>::const_iterator
314 if (I != Freqs.end())
319 void print(raw_ostream &OS) const {
320 OS << "\n\n---- Block Freqs ----\n";
321 for (typename FunctionT::iterator I = Fn->begin(), E = Fn->end(); I != E;) {
323 OS << " " << getBlockName(BB) << " = " << getBlockFreq(BB) << "\n";
325 for (typename GraphTraits<BlockT *>::ChildIteratorType
326 SI = GraphTraits<BlockT *>::child_begin(BB),
327 SE = GraphTraits<BlockT *>::child_end(BB); SI != SE; ++SI) {
329 OS << " " << getBlockName(BB) << " -> " << getBlockName(Succ)
330 << " = " << getEdgeFreq(BB, Succ) << "\n";