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"
33 class BlockFrequencyInfo;
34 class MachineBlockFrequencyInfo;
36 /// BlockFrequencyImpl implements block frequency algorithm for IR and
37 /// Machine Instructions. Algorithm starts with value 1024 (START_FREQ)
38 /// for the entry block and then propagates frequencies using branch weights
39 /// from (Machine)BranchProbabilityInfo. LoopInfo is not required because
40 /// algorithm can find "backedges" by itself.
41 template<class BlockT, class FunctionT, class BlockProbInfoT>
42 class BlockFrequencyImpl {
44 DenseMap<BlockT *, BlockFrequency> Freqs;
50 typedef GraphTraits< Inverse<BlockT *> > GT;
52 static const uint32_t START_FREQ = 1024;
54 std::string getBlockName(BasicBlock *BB) const {
55 return BB->getNameStr();
58 std::string getBlockName(MachineBasicBlock *MBB) const {
60 ss << "BB#" << MBB->getNumber();
62 if (const BasicBlock *BB = MBB->getBasicBlock())
63 ss << " derived from LLVM BB " << BB->getNameStr();
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, START_FREQ);
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(START_FREQ >= CycleProb[BB]);
215 uint32_t CProb = CycleProb[BB];
216 uint32_t Numerator = START_FREQ - CProb ? START_FREQ - CProb : 1;
217 divBlockFreq(BB, BranchProbability(Numerator, START_FREQ));
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 <= 1024 && "Backedge frequency must be <= 1024!");
247 uint64_t Res = (N * START_FREQ) / D;
249 assert(Res <= UINT32_MAX);
250 CycleProb[Head] += (uint32_t) Res;
255 friend class BlockFrequencyInfo;
256 friend class MachineBlockFrequencyInfo;
258 void doFunction(FunctionT *fn, BlockProbInfoT *bpi) {
268 BlockT *EntryBlock = fn->begin();
270 copy(po_begin(EntryBlock), po_end(EntryBlock), back_inserter(POT));
273 for (rpot_iterator I = rpot_begin(), E = rpot_end(); I != E; ++I) {
276 DEBUG(dbgs() << "RPO[" << getBlockName(BB) << "] = " << RPO[BB] << "\n");
279 // Travel over all blocks in postorder.
280 for (pot_iterator I = pot_begin(), E = pot_end(); I != E; ++I) {
282 BlockT *LastTail = 0;
283 DEBUG(dbgs() << "POT: " << getBlockName(BB) << "\n");
285 for (typename GT::ChildIteratorType
286 PI = GraphTraits< Inverse<BlockT *> >::child_begin(BB),
287 PE = GraphTraits< Inverse<BlockT *> >::child_end(BB);
291 if (isReachable(Pred) && isBackedge(Pred, BB)
292 && (!LastTail || RPO[Pred] > RPO[LastTail]))
297 doLoop(BB, LastTail);
300 // At the end assume the whole function as a loop, and travel over it once
302 doLoop(*(rpot_begin()), *(pot_begin()));
306 /// getBlockFreq - Return block frequency. Return 0 if we don't have it.
307 BlockFrequency getBlockFreq(BlockT *BB) const {
308 typename DenseMap<BlockT *, BlockFrequency>::const_iterator I = Freqs.find(BB);
309 if (I != Freqs.end())
314 void print(raw_ostream &OS) const {
315 OS << "\n\n---- Block Freqs ----\n";
316 for (typename FunctionT::iterator I = Fn->begin(), E = Fn->end(); I != E;) {
318 OS << " " << getBlockName(BB) << " = " << getBlockFreq(BB) << "\n";
320 for (typename GraphTraits<BlockT *>::ChildIteratorType
321 SI = GraphTraits<BlockT *>::child_begin(BB),
322 SE = GraphTraits<BlockT *>::child_end(BB); SI != SE; ++SI) {
324 OS << " " << getBlockName(BB) << " -> " << getBlockName(Succ)
325 << " = " << getEdgeFreq(BB, Succ) << "\n";