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/BranchProbability.h"
23 #include "llvm/Support/Debug.h"
24 #include "llvm/Support/raw_ostream.h"
33 class MachineBlockFrequency;
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<BlockT *, uint32_t> Freqs;
49 typedef GraphTraits< Inverse<BlockT *> > GT;
51 static const uint32_t START_FREQ = 1024;
53 std::string getBlockName(BasicBlock *BB) const {
54 return BB->getNameStr();
57 std::string getBlockName(MachineBasicBlock *MBB) const {
59 ss << "BB#" << MBB->getNumber();
61 if (const BasicBlock *BB = MBB->getBasicBlock())
62 ss << " derived from LLVM BB " << BB->getNameStr();
67 void setBlockFreq(BlockT *BB, uint32_t Freq) {
69 DEBUG(dbgs() << "Frequency(" << getBlockName(BB) << ") = " << Freq << "\n");
72 /// getEdgeFreq - Return edge frequency based on SRC frequency and Src -> Dst
74 uint32_t getEdgeFreq(BlockT *Src, BlockT *Dst) const {
75 BranchProbability Prob = BPI->getEdgeProbability(Src, Dst);
76 uint64_t N = Prob.getNumerator();
77 uint64_t D = Prob.getDenominator();
78 uint64_t Res = (N * getBlockFreq(Src)) / D;
80 assert(Res <= UINT32_MAX);
81 return (uint32_t) Res;
84 /// incBlockFreq - Increase BB block frequency by FREQ.
86 void incBlockFreq(BlockT *BB, uint32_t Freq) {
88 DEBUG(dbgs() << "Frequency(" << getBlockName(BB) << ") += " << Freq
89 << " --> " << Freqs[BB] << "\n");
92 /// divBlockFreq - Divide BB block frequency by PROB. If Prob = 0 do nothing.
94 void divBlockFreq(BlockT *BB, BranchProbability Prob) {
95 uint64_t N = Prob.getNumerator();
96 assert(N && "Illegal division by zero!");
97 uint64_t D = Prob.getDenominator();
98 uint64_t Freq = (Freqs[BB] * D) / N;
100 // Should we assert it?
101 if (Freq > UINT32_MAX)
104 Freqs[BB] = (uint32_t) Freq;
105 DEBUG(dbgs() << "Frequency(" << getBlockName(BB) << ") /= (" << Prob
106 << ") --> " << Freqs[BB] << "\n");
109 // All blocks in postorder.
110 std::vector<BlockT *> POT;
112 // Map Block -> Position in reverse-postorder list.
113 DenseMap<BlockT *, unsigned> RPO;
115 // Cycle Probability for each bloch.
116 DenseMap<BlockT *, uint32_t> CycleProb;
118 // (reverse-)postorder traversal iterators.
119 typedef typename std::vector<BlockT *>::iterator pot_iterator;
120 typedef typename std::vector<BlockT *>::reverse_iterator rpot_iterator;
122 pot_iterator pot_begin() { return POT.begin(); }
123 pot_iterator pot_end() { return POT.end(); }
125 rpot_iterator rpot_begin() { return POT.rbegin(); }
126 rpot_iterator rpot_end() { return POT.rend(); }
128 rpot_iterator rpot_at(BlockT *BB) {
129 rpot_iterator I = rpot_begin();
130 unsigned idx = RPO[BB];
132 std::advance(I, idx - 1);
139 /// Return a probability of getting to the DST block through SRC->DST edge.
141 BranchProbability getBackEdgeProbability(BlockT *Src, BlockT *Dst) const {
142 uint32_t N = getEdgeFreq(Src, Dst);
143 uint32_t D = getBlockFreq(Dst);
145 return BranchProbability(N, D);
148 /// isReachable - Returns if BB block is reachable from the entry.
150 bool isReachable(BlockT *BB) {
151 return RPO.count(BB);
154 /// isBackedge - Return if edge Src -> Dst is a backedge.
156 bool isBackedge(BlockT *Src, BlockT *Dst) {
157 assert(isReachable(Src));
158 assert(isReachable(Dst));
160 unsigned a = RPO[Src];
161 unsigned b = RPO[Dst];
166 /// getSingleBlockPred - return single BB block predecessor or NULL if
167 /// BB has none or more predecessors.
168 BlockT *getSingleBlockPred(BlockT *BB) {
169 typename GT::ChildIteratorType
170 PI = GraphTraits< Inverse<BlockT *> >::child_begin(BB),
171 PE = GraphTraits< Inverse<BlockT *> >::child_end(BB);
185 void doBlock(BlockT *BB, BlockT *LoopHead,
186 SmallPtrSet<BlockT *, 8> &BlocksInLoop) {
188 DEBUG(dbgs() << "doBlock(" << getBlockName(BB) << ")\n");
191 if (BB == LoopHead) {
192 setBlockFreq(BB, START_FREQ);
196 if(BlockT *Pred = getSingleBlockPred(BB)) {
197 if (BlocksInLoop.count(Pred))
198 setBlockFreq(BB, getEdgeFreq(Pred, BB));
199 // TODO: else? irreducible, ignore it for now.
203 bool isInLoop = false;
204 bool isLoopHead = false;
206 for (typename GT::ChildIteratorType
207 PI = GraphTraits< Inverse<BlockT *> >::child_begin(BB),
208 PE = GraphTraits< Inverse<BlockT *> >::child_end(BB);
212 if (isReachable(Pred) && isBackedge(Pred, BB)) {
214 } else if (BlocksInLoop.count(Pred)) {
215 incBlockFreq(BB, getEdgeFreq(Pred, BB));
218 // TODO: else? irreducible.
227 assert(START_FREQ >= CycleProb[BB]);
228 uint32_t CProb = CycleProb[BB];
229 uint32_t Numerator = START_FREQ - CProb ? START_FREQ - CProb : 1;
230 divBlockFreq(BB, BranchProbability(Numerator, START_FREQ));
233 /// doLoop - Propagate block frequency down throught the loop.
234 void doLoop(BlockT *Head, BlockT *Tail) {
235 DEBUG(dbgs() << "doLoop(" << getBlockName(Head) << ", "
236 << getBlockName(Tail) << ")\n");
238 SmallPtrSet<BlockT *, 8> BlocksInLoop;
240 for (rpot_iterator I = rpot_at(Head), E = rpot_end(); I != E; ++I) {
242 doBlock(BB, Head, BlocksInLoop);
244 BlocksInLoop.insert(BB);
247 // Compute loop's cyclic probability using backedges probabilities.
248 for (typename GT::ChildIteratorType
249 PI = GraphTraits< Inverse<BlockT *> >::child_begin(Head),
250 PE = GraphTraits< Inverse<BlockT *> >::child_end(Head);
254 if (isReachable(Pred) && isBackedge(Pred, Head)) {
255 BranchProbability Prob = getBackEdgeProbability(Pred, Head);
256 uint64_t N = Prob.getNumerator();
257 uint64_t D = Prob.getDenominator();
258 uint64_t Res = (N * START_FREQ) / D;
260 assert(Res <= UINT32_MAX);
261 CycleProb[Head] += (uint32_t) Res;
266 friend class BlockFrequency;
267 friend class MachineBlockFrequency;
269 void doFunction(FunctionT *fn, BlockProbInfoT *bpi) {
279 BlockT *EntryBlock = fn->begin();
281 copy(po_begin(EntryBlock), po_end(EntryBlock), back_inserter(POT));
284 for (rpot_iterator I = rpot_begin(), E = rpot_end(); I != E; ++I) {
287 DEBUG(dbgs() << "RPO[" << getBlockName(BB) << "] = " << RPO[BB] << "\n");
290 // Travel over all blocks in postorder.
291 for (pot_iterator I = pot_begin(), E = pot_end(); I != E; ++I) {
293 BlockT *LastTail = 0;
294 DEBUG(dbgs() << "POT: " << getBlockName(BB) << "\n");
296 for (typename GT::ChildIteratorType
297 PI = GraphTraits< Inverse<BlockT *> >::child_begin(BB),
298 PE = GraphTraits< Inverse<BlockT *> >::child_end(BB);
302 if (isReachable(Pred) && isBackedge(Pred, BB)
303 && (!LastTail || RPO[Pred] > RPO[LastTail]))
308 doLoop(BB, LastTail);
311 // At the end assume the whole function as a loop, and travel over it once
313 doLoop(*(rpot_begin()), *(pot_begin()));
317 /// getBlockFreq - Return block frequency. Never return 0, value must be
319 uint32_t getBlockFreq(BlockT *BB) const {
320 typename DenseMap<BlockT *, uint32_t>::const_iterator I = Freqs.find(BB);
321 if (I != Freqs.end())
322 return I->second ? I->second : 1;
326 void print(raw_ostream &OS) const {
327 OS << "\n\n---- Block Freqs ----\n";
328 for (typename FunctionT::iterator I = Fn->begin(), E = Fn->end(); I != E;) {
330 OS << " " << getBlockName(BB) << " = " << getBlockFreq(BB) << "\n";
332 for (typename GraphTraits<BlockT *>::ChildIteratorType
333 SI = GraphTraits<BlockT *>::child_begin(BB),
334 SE = GraphTraits<BlockT *>::child_end(BB); SI != SE; ++SI) {
336 OS << " " << getBlockName(BB) << " -> " << getBlockName(Succ)
337 << " = " << getEdgeFreq(BB, Succ) << "\n";