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/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 /// 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.lookup(BB);
128 std::advance(I, idx - 1);
134 /// isBackedge - Return if edge Src -> Dst is a reachable backedge.
136 bool isBackedge(BlockT *Src, BlockT *Dst) {
137 unsigned a = RPO.lookup(Src);
140 unsigned b = RPO.lookup(Dst);
141 assert(b && "Destination block should be reachable");
145 /// getSingleBlockPred - return single BB block predecessor or NULL if
146 /// BB has none or more predecessors.
147 BlockT *getSingleBlockPred(BlockT *BB) {
148 typename GT::ChildIteratorType
149 PI = GraphTraits< Inverse<BlockT *> >::child_begin(BB),
150 PE = GraphTraits< Inverse<BlockT *> >::child_end(BB);
164 void doBlock(BlockT *BB, BlockT *LoopHead,
165 SmallPtrSet<BlockT *, 8> &BlocksInLoop) {
167 DEBUG(dbgs() << "doBlock(" << getBlockName(BB) << ")\n");
170 if (BB == LoopHead) {
171 setBlockFreq(BB, EntryFreq);
175 if(BlockT *Pred = getSingleBlockPred(BB)) {
176 if (BlocksInLoop.count(Pred))
177 setBlockFreq(BB, getEdgeFreq(Pred, BB));
178 // TODO: else? irreducible, ignore it for now.
182 bool isInLoop = false;
183 bool isLoopHead = false;
185 for (typename GT::ChildIteratorType
186 PI = GraphTraits< Inverse<BlockT *> >::child_begin(BB),
187 PE = GraphTraits< Inverse<BlockT *> >::child_end(BB);
191 if (isBackedge(Pred, BB)) {
193 } else if (BlocksInLoop.count(Pred)) {
194 incBlockFreq(BB, getEdgeFreq(Pred, BB));
197 // TODO: else? irreducible.
206 assert(EntryFreq >= CycleProb[BB]);
207 uint32_t CProb = CycleProb[BB];
208 uint32_t Numerator = EntryFreq - CProb ? EntryFreq - CProb : 1;
209 divBlockFreq(BB, BranchProbability(Numerator, EntryFreq));
212 /// doLoop - Propagate block frequency down through the loop.
213 void doLoop(BlockT *Head, BlockT *Tail) {
214 DEBUG(dbgs() << "doLoop(" << getBlockName(Head) << ", "
215 << getBlockName(Tail) << ")\n");
217 SmallPtrSet<BlockT *, 8> BlocksInLoop;
219 for (rpot_iterator I = rpot_at(Head), E = rpot_at(Tail); ; ++I) {
221 doBlock(BB, Head, BlocksInLoop);
223 BlocksInLoop.insert(BB);
228 // Compute loop's cyclic probability using backedges probabilities.
229 for (typename GT::ChildIteratorType
230 PI = GraphTraits< Inverse<BlockT *> >::child_begin(Head),
231 PE = GraphTraits< Inverse<BlockT *> >::child_end(Head);
235 if (isBackedge(Pred, Head)) {
236 uint64_t N = getEdgeFreq(Pred, Head).getFrequency();
237 uint64_t D = getBlockFreq(Head).getFrequency();
238 assert(N <= EntryFreq && "Backedge frequency must be <= EntryFreq!");
239 uint64_t Res = (N * EntryFreq) / D;
241 assert(Res <= UINT32_MAX);
242 CycleProb[Head] += (uint32_t) Res;
243 DEBUG(dbgs() << " CycleProb[" << getBlockName(Head) << "] += " << Res
244 << " --> " << CycleProb[Head] << "\n");
249 friend class BlockFrequencyInfo;
250 friend class MachineBlockFrequencyInfo;
252 BlockFrequencyImpl() : EntryFreq(BlockFrequency::getEntryFrequency()) { }
254 void doFunction(FunctionT *fn, BlockProbInfoT *bpi) {
264 BlockT *EntryBlock = fn->begin();
266 std::copy(po_begin(EntryBlock), po_end(EntryBlock), std::back_inserter(POT));
269 for (rpot_iterator I = rpot_begin(), E = rpot_end(); I != E; ++I) {
272 DEBUG(dbgs() << "RPO[" << getBlockName(BB) << "] = " << RPO[BB] << "\n");
275 // Travel over all blocks in postorder.
276 for (pot_iterator I = pot_begin(), E = pot_end(); I != E; ++I) {
278 BlockT *LastTail = 0;
279 DEBUG(dbgs() << "POT: " << getBlockName(BB) << "\n");
281 for (typename GT::ChildIteratorType
282 PI = GraphTraits< Inverse<BlockT *> >::child_begin(BB),
283 PE = GraphTraits< Inverse<BlockT *> >::child_end(BB);
287 if (isBackedge(Pred, BB) && (!LastTail || RPO[Pred] > RPO[LastTail]))
292 doLoop(BB, LastTail);
295 // At the end assume the whole function as a loop, and travel over it once
297 doLoop(*(rpot_begin()), *(pot_begin()));
301 /// getBlockFreq - Return block frequency. Return 0 if we don't have it.
302 BlockFrequency getBlockFreq(const BlockT *BB) const {
303 typename DenseMap<const BlockT *, BlockFrequency>::const_iterator
305 if (I != Freqs.end())
310 void print(raw_ostream &OS) const {
311 OS << "\n\n---- Block Freqs ----\n";
312 for (typename FunctionT::iterator I = Fn->begin(), E = Fn->end(); I != E;) {
314 OS << " " << getBlockName(BB) << " = " << getBlockFreq(BB) << "\n";
316 for (typename GraphTraits<BlockT *>::ChildIteratorType
317 SI = GraphTraits<BlockT *>::child_begin(BB),
318 SE = GraphTraits<BlockT *>::child_end(BB); SI != SE; ++SI) {
320 OS << " " << getBlockName(BB) << " -> " << getBlockName(Succ)
321 << " = " << getEdgeFreq(BB, Succ) << "\n";