1//===-- BlockFrequencyImpl.h - Block Frequency Implementation --*- C++ -*--===//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// Shared implementation of BlockFrequency for IR and Machine Instructions.
11//
12//===----------------------------------------------------------------------===//
13
14#ifndef LLVM_ANALYSIS_BLOCKFREQUENCYIMPL_H
15#define LLVM_ANALYSIS_BLOCKFREQUENCYIMPL_H
16
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"
26#include <string>
27#include <vector>
28
29namespace llvm {
30
31
32class BlockFrequencyInfo;
33class MachineBlockFrequencyInfo;
34
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.
40template<class BlockT, class FunctionT, class BlockProbInfoT>
41class BlockFrequencyImpl {
42
43  DenseMap<const BlockT *, BlockFrequency> Freqs;
44
45  BlockProbInfoT *BPI;
46
47  FunctionT *Fn;
48
49  typedef GraphTraits< Inverse<BlockT *> > GT;
50
51  const uint32_t EntryFreq;
52
53  std::string getBlockName(BasicBlock *BB) const {
54    return BB->getName().str();
55  }
56
57  std::string getBlockName(MachineBasicBlock *MBB) const {
58    std::string str;
59    raw_string_ostream ss(str);
60    ss << "BB#" << MBB->getNumber();
61
62    if (const BasicBlock *BB = MBB->getBasicBlock())
63      ss << " derived from LLVM BB " << BB->getName();
64
65    return ss.str();
66  }
67
68  void setBlockFreq(BlockT *BB, BlockFrequency Freq) {
69    Freqs[BB] = Freq;
70    DEBUG(dbgs() << "Frequency(" << getBlockName(BB) << ") = " << Freq << "\n");
71  }
72
73  /// getEdgeFreq - Return edge frequency based on SRC frequency and Src -> Dst
74  /// edge probability.
75  BlockFrequency getEdgeFreq(BlockT *Src, BlockT *Dst) const {
76    BranchProbability Prob = BPI->getEdgeProbability(Src, Dst);
77    return getBlockFreq(Src) * Prob;
78  }
79
80  /// incBlockFreq - Increase BB block frequency by FREQ.
81  ///
82  void incBlockFreq(BlockT *BB, BlockFrequency Freq) {
83    Freqs[BB] += Freq;
84    DEBUG(dbgs() << "Frequency(" << getBlockName(BB) << ") += " << Freq
85                 << " --> " << Freqs[BB] << "\n");
86  }
87
88  // All blocks in postorder.
89  std::vector<BlockT *> POT;
90
91  // Map Block -> Position in reverse-postorder list.
92  DenseMap<BlockT *, unsigned> RPO;
93
94  // For each loop header, record the per-iteration probability of exiting the
95  // loop. This is the reciprocal of the expected number of loop iterations.
96  typedef DenseMap<BlockT*, BranchProbability> LoopExitProbMap;
97  LoopExitProbMap LoopExitProb;
98
99  // (reverse-)postorder traversal iterators.
100  typedef typename std::vector<BlockT *>::iterator pot_iterator;
101  typedef typename std::vector<BlockT *>::reverse_iterator rpot_iterator;
102
103  pot_iterator pot_begin() { return POT.begin(); }
104  pot_iterator pot_end() { return POT.end(); }
105
106  rpot_iterator rpot_begin() { return POT.rbegin(); }
107  rpot_iterator rpot_end() { return POT.rend(); }
108
109  rpot_iterator rpot_at(BlockT *BB) {
110    rpot_iterator I = rpot_begin();
111    unsigned idx = RPO.lookup(BB);
112    assert(idx);
113    std::advance(I, idx - 1);
114
115    assert(*I == BB);
116    return I;
117  }
118
119  /// isBackedge - Return if edge Src -> Dst is a reachable backedge.
120  ///
121  bool isBackedge(BlockT *Src, BlockT *Dst) const {
122    unsigned a = RPO.lookup(Src);
123    if (!a)
124      return false;
125    unsigned b = RPO.lookup(Dst);
126    assert(b && "Destination block should be reachable");
127    return a >= b;
128  }
129
130  /// getSingleBlockPred - return single BB block predecessor or NULL if
131  /// BB has none or more predecessors.
132  BlockT *getSingleBlockPred(BlockT *BB) {
133    typename GT::ChildIteratorType
134      PI = GraphTraits< Inverse<BlockT *> >::child_begin(BB),
135      PE = GraphTraits< Inverse<BlockT *> >::child_end(BB);
136
137    if (PI == PE)
138      return 0;
139
140    BlockT *Pred = *PI;
141
142    ++PI;
143    if (PI != PE)
144      return 0;
145
146    return Pred;
147  }
148
149  void doBlock(BlockT *BB, BlockT *LoopHead,
150               SmallPtrSet<BlockT *, 8> &BlocksInLoop) {
151
152    DEBUG(dbgs() << "doBlock(" << getBlockName(BB) << ")\n");
153    setBlockFreq(BB, 0);
154
155    if (BB == LoopHead) {
156      setBlockFreq(BB, EntryFreq);
157      return;
158    }
159
160    if(BlockT *Pred = getSingleBlockPred(BB)) {
161      if (BlocksInLoop.count(Pred))
162        setBlockFreq(BB, getEdgeFreq(Pred, BB));
163      // TODO: else? irreducible, ignore it for now.
164      return;
165    }
166
167    bool isInLoop = false;
168    bool isLoopHead = false;
169
170    for (typename GT::ChildIteratorType
171         PI = GraphTraits< Inverse<BlockT *> >::child_begin(BB),
172         PE = GraphTraits< Inverse<BlockT *> >::child_end(BB);
173         PI != PE; ++PI) {
174      BlockT *Pred = *PI;
175
176      if (isBackedge(Pred, BB)) {
177        isLoopHead = true;
178      } else if (BlocksInLoop.count(Pred)) {
179        incBlockFreq(BB, getEdgeFreq(Pred, BB));
180        isInLoop = true;
181      }
182      // TODO: else? irreducible.
183    }
184
185    if (!isInLoop)
186      return;
187
188    if (!isLoopHead)
189      return;
190
191    // This block is a loop header, so boost its frequency by the expected
192    // number of loop iterations. The loop blocks will be revisited so they all
193    // get this boost.
194    typename LoopExitProbMap::const_iterator I = LoopExitProb.find(BB);
195    assert(I != LoopExitProb.end() && "Loop header missing from table");
196    Freqs[BB] /= I->second;
197    DEBUG(dbgs() << "Loop header scaled to " << Freqs[BB] << ".\n");
198  }
199
200  /// doLoop - Propagate block frequency down through the loop.
201  void doLoop(BlockT *Head, BlockT *Tail) {
202    DEBUG(dbgs() << "doLoop(" << getBlockName(Head) << ", "
203                 << getBlockName(Tail) << ")\n");
204
205    SmallPtrSet<BlockT *, 8> BlocksInLoop;
206
207    for (rpot_iterator I = rpot_at(Head), E = rpot_at(Tail); ; ++I) {
208      BlockT *BB = *I;
209      doBlock(BB, Head, BlocksInLoop);
210
211      BlocksInLoop.insert(BB);
212      if (I == E)
213        break;
214    }
215
216    // Compute loop's cyclic probability using backedges probabilities.
217    BlockFrequency BackFreq;
218    for (typename GT::ChildIteratorType
219         PI = GraphTraits< Inverse<BlockT *> >::child_begin(Head),
220         PE = GraphTraits< Inverse<BlockT *> >::child_end(Head);
221         PI != PE; ++PI) {
222      BlockT *Pred = *PI;
223      assert(Pred);
224      if (isBackedge(Pred, Head))
225        BackFreq += getEdgeFreq(Pred, Head);
226    }
227
228    // The cyclic probability is freq(BackEdges) / freq(Head), where freq(Head)
229    // only counts edges entering the loop, not the loop backedges.
230    // The probability of leaving the loop on each iteration is:
231    //
232    //   ExitProb = 1 - CyclicProb
233    //
234    // The Expected number of loop iterations is:
235    //
236    //   Iterations = 1 / ExitProb
237    //
238    uint64_t D = std::max(getBlockFreq(Head).getFrequency(), UINT64_C(1));
239    uint64_t N = std::max(BackFreq.getFrequency(), UINT64_C(1));
240    if (N < D)
241      N = D - N;
242    else
243      // We'd expect N < D, but rounding and saturation means that can't be
244      // guaranteed.
245      N = 1;
246
247    // Now ExitProb = N / D, make sure it fits in an i32/i32 fraction.
248    assert(N <= D);
249    if (D > UINT32_MAX) {
250      unsigned Shift = 32 - countLeadingZeros(D);
251      D >>= Shift;
252      N >>= Shift;
253      if (N == 0)
254        N = 1;
255    }
256    BranchProbability LEP = BranchProbability(N, D);
257    LoopExitProb.insert(std::make_pair(Head, LEP));
258    DEBUG(dbgs() << "LoopExitProb[" << getBlockName(Head) << "] = " << LEP
259                 << " from 1 - " << BackFreq << " / " << getBlockFreq(Head)
260                 << ".\n");
261  }
262
263  friend class BlockFrequencyInfo;
264  friend class MachineBlockFrequencyInfo;
265
266  BlockFrequencyImpl() : EntryFreq(BlockFrequency::getEntryFrequency()) { }
267
268  void doFunction(FunctionT *fn, BlockProbInfoT *bpi) {
269    Fn = fn;
270    BPI = bpi;
271
272    // Clear everything.
273    RPO.clear();
274    POT.clear();
275    LoopExitProb.clear();
276    Freqs.clear();
277
278    BlockT *EntryBlock = fn->begin();
279
280    std::copy(po_begin(EntryBlock), po_end(EntryBlock), std::back_inserter(POT));
281
282    unsigned RPOidx = 0;
283    for (rpot_iterator I = rpot_begin(), E = rpot_end(); I != E; ++I) {
284      BlockT *BB = *I;
285      RPO[BB] = ++RPOidx;
286      DEBUG(dbgs() << "RPO[" << getBlockName(BB) << "] = " << RPO[BB] << "\n");
287    }
288
289    // Travel over all blocks in postorder.
290    for (pot_iterator I = pot_begin(), E = pot_end(); I != E; ++I) {
291      BlockT *BB = *I;
292      BlockT *LastTail = 0;
293      DEBUG(dbgs() << "POT: " << getBlockName(BB) << "\n");
294
295      for (typename GT::ChildIteratorType
296           PI = GraphTraits< Inverse<BlockT *> >::child_begin(BB),
297           PE = GraphTraits< Inverse<BlockT *> >::child_end(BB);
298           PI != PE; ++PI) {
299
300        BlockT *Pred = *PI;
301        if (isBackedge(Pred, BB) && (!LastTail || RPO[Pred] > RPO[LastTail]))
302          LastTail = Pred;
303      }
304
305      if (LastTail)
306        doLoop(BB, LastTail);
307    }
308
309    // At the end assume the whole function as a loop, and travel over it once
310    // again.
311    doLoop(*(rpot_begin()), *(pot_begin()));
312  }
313
314public:
315  /// getBlockFreq - Return block frequency. Return 0 if we don't have it.
316  BlockFrequency getBlockFreq(const BlockT *BB) const {
317    typename DenseMap<const BlockT *, BlockFrequency>::const_iterator
318      I = Freqs.find(BB);
319    if (I != Freqs.end())
320      return I->second;
321    return 0;
322  }
323
324  void print(raw_ostream &OS) const {
325    OS << "\n\n---- Block Freqs ----\n";
326    for (typename FunctionT::iterator I = Fn->begin(), E = Fn->end(); I != E;) {
327      BlockT *BB = I++;
328      OS << " " << getBlockName(BB) << " = " << getBlockFreq(BB) << "\n";
329
330      for (typename GraphTraits<BlockT *>::ChildIteratorType
331           SI = GraphTraits<BlockT *>::child_begin(BB),
332           SE = GraphTraits<BlockT *>::child_end(BB); SI != SE; ++SI) {
333        BlockT *Succ = *SI;
334        OS << "  " << getBlockName(BB) << " -> " << getBlockName(Succ)
335           << " = " << getEdgeFreq(BB, Succ) << "\n";
336      }
337    }
338  }
339
340  void dump() const {
341    print(dbgs());
342  }
343};
344
345}
346
347#endif
348