1 //==- BlockFrequencyInfoImpl.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 BlockFrequencyInfo for IR and Machine Instructions.
12 //===----------------------------------------------------------------------===//
14 #ifndef LLVM_ANALYSIS_BLOCKFREQUENCYINFOIMPL_H
15 #define LLVM_ANALYSIS_BLOCKFREQUENCYINFOIMPL_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 BranchProbabilityInfo;
33 class BlockFrequencyInfo;
34 class MachineBranchProbabilityInfo;
35 class MachineBlockFrequencyInfo;
37 namespace bfi_detail {
38 template <class BlockT> struct TypeMap {};
39 template <> struct TypeMap<BasicBlock> {
40 typedef BasicBlock BlockT;
41 typedef Function FunctionT;
42 typedef BranchProbabilityInfo BranchProbabilityInfoT;
44 template <> struct TypeMap<MachineBasicBlock> {
45 typedef MachineBasicBlock BlockT;
46 typedef MachineFunction FunctionT;
47 typedef MachineBranchProbabilityInfo BranchProbabilityInfoT;
51 /// BlockFrequencyInfoImpl implements block frequency algorithm for IR and
52 /// Machine Instructions. Algorithm starts with value ENTRY_FREQ
53 /// for the entry block and then propagates frequencies using branch weights
54 /// from (Machine)BranchProbabilityInfo. LoopInfo is not required because
55 /// algorithm can find "backedges" by itself.
57 class BlockFrequencyInfoImpl {
58 typedef typename bfi_detail::TypeMap<BT>::BlockT BlockT;
59 typedef typename bfi_detail::TypeMap<BT>::FunctionT FunctionT;
60 typedef typename bfi_detail::TypeMap<BT>::BranchProbabilityInfoT
61 BranchProbabilityInfoT;
63 DenseMap<const BlockT *, BlockFrequency> Freqs;
65 BranchProbabilityInfoT *BPI;
69 typedef GraphTraits< Inverse<BlockT *> > GT;
71 static const uint64_t EntryFreq = 1 << 14;
73 std::string getBlockName(BasicBlock *BB) const {
74 return BB->getName().str();
77 std::string getBlockName(MachineBasicBlock *MBB) const {
79 raw_string_ostream ss(str);
80 ss << "BB#" << MBB->getNumber();
82 if (const BasicBlock *BB = MBB->getBasicBlock())
83 ss << " derived from LLVM BB " << BB->getName();
88 void setBlockFreq(BlockT *BB, BlockFrequency Freq) {
90 DEBUG(dbgs() << "Frequency(" << getBlockName(BB) << ") = ";
91 printBlockFreq(dbgs(), Freq) << "\n");
94 /// getEdgeFreq - Return edge frequency based on SRC frequency and Src -> Dst
96 BlockFrequency getEdgeFreq(BlockT *Src, BlockT *Dst) const {
97 BranchProbability Prob = BPI->getEdgeProbability(Src, Dst);
98 return getBlockFreq(Src) * Prob;
101 /// incBlockFreq - Increase BB block frequency by FREQ.
103 void incBlockFreq(BlockT *BB, BlockFrequency Freq) {
105 DEBUG(dbgs() << "Frequency(" << getBlockName(BB) << ") += ";
106 printBlockFreq(dbgs(), Freq) << " --> ";
107 printBlockFreq(dbgs(), Freqs[BB]) << "\n");
110 // All blocks in postorder.
111 std::vector<BlockT *> POT;
113 // Map Block -> Position in reverse-postorder list.
114 DenseMap<BlockT *, unsigned> RPO;
116 // For each loop header, record the per-iteration probability of exiting the
117 // loop. This is the reciprocal of the expected number of loop iterations.
118 typedef DenseMap<BlockT*, BranchProbability> LoopExitProbMap;
119 LoopExitProbMap LoopExitProb;
121 // (reverse-)postorder traversal iterators.
122 typedef typename std::vector<BlockT *>::iterator pot_iterator;
123 typedef typename std::vector<BlockT *>::reverse_iterator rpot_iterator;
125 pot_iterator pot_begin() { return POT.begin(); }
126 pot_iterator pot_end() { return POT.end(); }
128 rpot_iterator rpot_begin() { return POT.rbegin(); }
129 rpot_iterator rpot_end() { return POT.rend(); }
131 rpot_iterator rpot_at(BlockT *BB) {
132 rpot_iterator I = rpot_begin();
133 unsigned idx = RPO.lookup(BB);
135 std::advance(I, idx - 1);
141 /// isBackedge - Return if edge Src -> Dst is a reachable backedge.
143 bool isBackedge(BlockT *Src, BlockT *Dst) const {
144 unsigned a = RPO.lookup(Src);
147 unsigned b = RPO.lookup(Dst);
148 assert(b && "Destination block should be reachable");
152 /// getSingleBlockPred - return single BB block predecessor or NULL if
153 /// BB has none or more predecessors.
154 BlockT *getSingleBlockPred(BlockT *BB) {
155 typename GT::ChildIteratorType
156 PI = GraphTraits< Inverse<BlockT *> >::child_begin(BB),
157 PE = GraphTraits< Inverse<BlockT *> >::child_end(BB);
171 void doBlock(BlockT *BB, BlockT *LoopHead,
172 SmallPtrSet<BlockT *, 8> &BlocksInLoop) {
174 DEBUG(dbgs() << "doBlock(" << getBlockName(BB) << ")\n");
177 if (BB == LoopHead) {
178 setBlockFreq(BB, EntryFreq);
182 if (BlockT *Pred = getSingleBlockPred(BB)) {
183 if (BlocksInLoop.count(Pred))
184 setBlockFreq(BB, getEdgeFreq(Pred, BB));
185 // TODO: else? irreducible, ignore it for now.
189 bool isInLoop = false;
190 bool isLoopHead = false;
192 for (typename GT::ChildIteratorType
193 PI = GraphTraits< Inverse<BlockT *> >::child_begin(BB),
194 PE = GraphTraits< Inverse<BlockT *> >::child_end(BB);
198 if (isBackedge(Pred, BB)) {
200 } else if (BlocksInLoop.count(Pred)) {
201 incBlockFreq(BB, getEdgeFreq(Pred, BB));
204 // TODO: else? irreducible.
213 // This block is a loop header, so boost its frequency by the expected
214 // number of loop iterations. The loop blocks will be revisited so they all
216 typename LoopExitProbMap::const_iterator I = LoopExitProb.find(BB);
217 assert(I != LoopExitProb.end() && "Loop header missing from table");
218 Freqs[BB] /= I->second;
219 DEBUG(dbgs() << "Loop header scaled to ";
220 printBlockFreq(dbgs(), Freqs[BB]) << ".\n");
223 /// doLoop - Propagate block frequency down through the loop.
224 void doLoop(BlockT *Head, BlockT *Tail) {
225 DEBUG(dbgs() << "doLoop(" << getBlockName(Head) << ", "
226 << getBlockName(Tail) << ")\n");
228 SmallPtrSet<BlockT *, 8> BlocksInLoop;
230 for (rpot_iterator I = rpot_at(Head), E = rpot_at(Tail); ; ++I) {
232 doBlock(BB, Head, BlocksInLoop);
234 BlocksInLoop.insert(BB);
239 // Compute loop's cyclic probability using backedges probabilities.
240 BlockFrequency BackFreq;
241 for (typename GT::ChildIteratorType
242 PI = GraphTraits< Inverse<BlockT *> >::child_begin(Head),
243 PE = GraphTraits< Inverse<BlockT *> >::child_end(Head);
247 if (isBackedge(Pred, Head))
248 BackFreq += getEdgeFreq(Pred, Head);
251 // The cyclic probability is freq(BackEdges) / freq(Head), where freq(Head)
252 // only counts edges entering the loop, not the loop backedges.
253 // The probability of leaving the loop on each iteration is:
255 // ExitProb = 1 - CyclicProb
257 // The Expected number of loop iterations is:
259 // Iterations = 1 / ExitProb
261 uint64_t D = std::max(getBlockFreq(Head).getFrequency(), UINT64_C(1));
262 uint64_t N = std::max(BackFreq.getFrequency(), UINT64_C(1));
266 // We'd expect N < D, but rounding and saturation means that can't be
270 // Now ExitProb = N / D, make sure it fits in an i32/i32 fraction.
272 if (D > UINT32_MAX) {
273 unsigned Shift = 32 - countLeadingZeros(D);
279 BranchProbability LEP = BranchProbability(N, D);
280 LoopExitProb.insert(std::make_pair(Head, LEP));
281 DEBUG(dbgs() << "LoopExitProb[" << getBlockName(Head) << "] = " << LEP
283 printBlockFreq(dbgs(), BackFreq) << " / ";
284 printBlockFreq(dbgs(), getBlockFreq(Head)) << ".\n");
287 friend class BlockFrequencyInfo;
288 friend class MachineBlockFrequencyInfo;
290 BlockFrequencyInfoImpl() { }
292 void doFunction(FunctionT *fn, BranchProbabilityInfoT *bpi) {
299 LoopExitProb.clear();
302 BlockT *EntryBlock = fn->begin();
304 std::copy(po_begin(EntryBlock), po_end(EntryBlock), std::back_inserter(POT));
307 for (rpot_iterator I = rpot_begin(), E = rpot_end(); I != E; ++I) {
310 DEBUG(dbgs() << "RPO[" << getBlockName(BB) << "] = " << RPO[BB] << "\n");
313 // Travel over all blocks in postorder.
314 for (pot_iterator I = pot_begin(), E = pot_end(); I != E; ++I) {
316 BlockT *LastTail = 0;
317 DEBUG(dbgs() << "POT: " << getBlockName(BB) << "\n");
319 for (typename GT::ChildIteratorType
320 PI = GraphTraits< Inverse<BlockT *> >::child_begin(BB),
321 PE = GraphTraits< Inverse<BlockT *> >::child_end(BB);
325 if (isBackedge(Pred, BB) && (!LastTail || RPO[Pred] > RPO[LastTail]))
330 doLoop(BB, LastTail);
333 // At the end assume the whole function as a loop, and travel over it once
335 doLoop(*(rpot_begin()), *(pot_begin()));
340 uint64_t getEntryFreq() { return EntryFreq; }
342 /// getBlockFreq - Return block frequency. Return 0 if we don't have it.
343 BlockFrequency getBlockFreq(const BlockT *BB) const {
344 typename DenseMap<const BlockT *, BlockFrequency>::const_iterator
346 if (I != Freqs.end())
351 void print(raw_ostream &OS) const {
352 OS << "\n\n---- Block Freqs ----\n";
353 for (typename FunctionT::iterator I = Fn->begin(), E = Fn->end(); I != E;) {
355 OS << " " << getBlockName(BB) << " = ";
356 printBlockFreq(OS, getBlockFreq(BB)) << "\n";
358 for (typename GraphTraits<BlockT *>::ChildIteratorType
359 SI = GraphTraits<BlockT *>::child_begin(BB),
360 SE = GraphTraits<BlockT *>::child_end(BB); SI != SE; ++SI) {
362 OS << " " << getBlockName(BB) << " -> " << getBlockName(Succ)
363 << " = "; printBlockFreq(OS, getEdgeFreq(BB, Succ)) << "\n";
372 // Utility method that looks up the block frequency associated with BB and
374 raw_ostream &printBlockFreq(raw_ostream &OS,
376 return printBlockFreq(OS, getBlockFreq(BB));
379 raw_ostream &printBlockFreq(raw_ostream &OS,
380 const BlockFrequency &Freq) const {
381 // Convert fixed-point number to decimal.
382 uint64_t Frequency = Freq.getFrequency();
383 OS << Frequency / EntryFreq << ".";
384 uint64_t Rem = Frequency % EntryFreq;
389 OS << Rem / EntryFreq;
390 Rem = Rem % EntryFreq;
391 } while (Rem >= Eps/2);