1//===---- BlockFrequencyImpl.h - Machine Block Frequency Implementation ---===//
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/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"
26#include <vector>
27#include <string>
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 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.
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  /// divBlockFreq - Divide BB block frequency by PROB. If Prob = 0 do nothing.
89  ///
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;
95
96    // Should we assert it?
97    if (Freq > UINT32_MAX)
98      Freq = UINT32_MAX;
99
100    Freqs[BB] = BlockFrequency(Freq);
101    DEBUG(dbgs() << "Frequency(" << getBlockName(BB) << ") /= (" << Prob
102                 << ") --> " << Freqs[BB] << "\n");
103  }
104
105  // All blocks in postorder.
106  std::vector<BlockT *> POT;
107
108  // Map Block -> Position in reverse-postorder list.
109  DenseMap<BlockT *, unsigned> RPO;
110
111  // Cycle Probability for each bloch.
112  DenseMap<BlockT *, uint32_t> CycleProb;
113
114  // (reverse-)postorder traversal iterators.
115  typedef typename std::vector<BlockT *>::iterator pot_iterator;
116  typedef typename std::vector<BlockT *>::reverse_iterator rpot_iterator;
117
118  pot_iterator pot_begin() { return POT.begin(); }
119  pot_iterator pot_end() { return POT.end(); }
120
121  rpot_iterator rpot_begin() { return POT.rbegin(); }
122  rpot_iterator rpot_end() { return POT.rend(); }
123
124  rpot_iterator rpot_at(BlockT *BB) {
125    rpot_iterator I = rpot_begin();
126    unsigned idx = RPO[BB];
127    assert(idx);
128    std::advance(I, idx - 1);
129
130    assert(*I == BB);
131    return I;
132  }
133
134
135  /// isReachable - Returns if BB block is reachable from the entry.
136  ///
137  bool isReachable(BlockT *BB) {
138    return RPO.count(BB);
139  }
140
141  /// isBackedge - Return if edge Src -> Dst is a backedge.
142  ///
143  bool isBackedge(BlockT *Src, BlockT *Dst) {
144    assert(isReachable(Src));
145    assert(isReachable(Dst));
146
147    unsigned a = RPO[Src];
148    unsigned b = RPO[Dst];
149
150    return a >= b;
151  }
152
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);
159
160    if (PI == PE)
161      return 0;
162
163    BlockT *Pred = *PI;
164
165    ++PI;
166    if (PI != PE)
167      return 0;
168
169    return Pred;
170  }
171
172  void doBlock(BlockT *BB, BlockT *LoopHead,
173               SmallPtrSet<BlockT *, 8> &BlocksInLoop) {
174
175    DEBUG(dbgs() << "doBlock(" << getBlockName(BB) << ")\n");
176    setBlockFreq(BB, 0);
177
178    if (BB == LoopHead) {
179      setBlockFreq(BB, EntryFreq);
180      return;
181    }
182
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.
187      return;
188    }
189
190    bool isInLoop = false;
191    bool isLoopHead = false;
192
193    for (typename GT::ChildIteratorType
194         PI = GraphTraits< Inverse<BlockT *> >::child_begin(BB),
195         PE = GraphTraits< Inverse<BlockT *> >::child_end(BB);
196         PI != PE; ++PI) {
197      BlockT *Pred = *PI;
198
199      if (isReachable(Pred) && isBackedge(Pred, BB)) {
200        isLoopHead = true;
201      } else if (BlocksInLoop.count(Pred)) {
202        incBlockFreq(BB, getEdgeFreq(Pred, BB));
203        isInLoop = true;
204      }
205      // TODO: else? irreducible.
206    }
207
208    if (!isInLoop)
209      return;
210
211    if (!isLoopHead)
212      return;
213
214    assert(EntryFreq >= CycleProb[BB]);
215    uint32_t CProb = CycleProb[BB];
216    uint32_t Numerator = EntryFreq - CProb ? EntryFreq - CProb : 1;
217    divBlockFreq(BB, BranchProbability(Numerator, EntryFreq));
218  }
219
220  /// doLoop - Propagate block frequency down through the loop.
221  void doLoop(BlockT *Head, BlockT *Tail) {
222    DEBUG(dbgs() << "doLoop(" << getBlockName(Head) << ", "
223                 << getBlockName(Tail) << ")\n");
224
225    SmallPtrSet<BlockT *, 8> BlocksInLoop;
226
227    for (rpot_iterator I = rpot_at(Head), E = rpot_at(Tail); ; ++I) {
228      BlockT *BB = *I;
229      doBlock(BB, Head, BlocksInLoop);
230
231      BlocksInLoop.insert(BB);
232      if (I == E)
233        break;
234    }
235
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);
240         PI != PE; ++PI) {
241      BlockT *Pred = *PI;
242      assert(Pred);
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 <= EntryFreq && "Backedge frequency must be <= EntryFreq!");
247        uint64_t Res = (N * EntryFreq) / D;
248
249        assert(Res <= UINT32_MAX);
250        CycleProb[Head] += (uint32_t) Res;
251        DEBUG(dbgs() << "  CycleProb[" << getBlockName(Head) << "] += " << Res
252                     << " --> " << CycleProb[Head] << "\n");
253      }
254    }
255  }
256
257  friend class BlockFrequencyInfo;
258  friend class MachineBlockFrequencyInfo;
259
260  BlockFrequencyImpl() : EntryFreq(BlockFrequency::getEntryFrequency()) { }
261
262  void doFunction(FunctionT *fn, BlockProbInfoT *bpi) {
263    Fn = fn;
264    BPI = bpi;
265
266    // Clear everything.
267    RPO.clear();
268    POT.clear();
269    CycleProb.clear();
270    Freqs.clear();
271
272    BlockT *EntryBlock = fn->begin();
273
274    copy(po_begin(EntryBlock), po_end(EntryBlock), back_inserter(POT));
275
276    unsigned RPOidx = 0;
277    for (rpot_iterator I = rpot_begin(), E = rpot_end(); I != E; ++I) {
278      BlockT *BB = *I;
279      RPO[BB] = ++RPOidx;
280      DEBUG(dbgs() << "RPO[" << getBlockName(BB) << "] = " << RPO[BB] << "\n");
281    }
282
283    // Travel over all blocks in postorder.
284    for (pot_iterator I = pot_begin(), E = pot_end(); I != E; ++I) {
285      BlockT *BB = *I;
286      BlockT *LastTail = 0;
287      DEBUG(dbgs() << "POT: " << getBlockName(BB) << "\n");
288
289      for (typename GT::ChildIteratorType
290           PI = GraphTraits< Inverse<BlockT *> >::child_begin(BB),
291           PE = GraphTraits< Inverse<BlockT *> >::child_end(BB);
292           PI != PE; ++PI) {
293
294        BlockT *Pred = *PI;
295        if (isReachable(Pred) && isBackedge(Pred, BB)
296            && (!LastTail || RPO[Pred] > RPO[LastTail]))
297          LastTail = Pred;
298      }
299
300      if (LastTail)
301        doLoop(BB, LastTail);
302    }
303
304    // At the end assume the whole function as a loop, and travel over it once
305    // again.
306    doLoop(*(rpot_begin()), *(pot_begin()));
307  }
308
309public:
310  /// getBlockFreq - Return block frequency. Return 0 if we don't have it.
311  BlockFrequency getBlockFreq(const BlockT *BB) const {
312    typename DenseMap<const BlockT *, BlockFrequency>::const_iterator
313      I = Freqs.find(BB);
314    if (I != Freqs.end())
315      return I->second;
316    return 0;
317  }
318
319  void print(raw_ostream &OS) const {
320    OS << "\n\n---- Block Freqs ----\n";
321    for (typename FunctionT::iterator I = Fn->begin(), E = Fn->end(); I != E;) {
322      BlockT *BB = I++;
323      OS << " " << getBlockName(BB) << " = " << getBlockFreq(BB) << "\n";
324
325      for (typename GraphTraits<BlockT *>::ChildIteratorType
326           SI = GraphTraits<BlockT *>::child_begin(BB),
327           SE = GraphTraits<BlockT *>::child_end(BB); SI != SE; ++SI) {
328        BlockT *Succ = *SI;
329        OS << "  " << getBlockName(BB) << " -> " << getBlockName(Succ)
330           << " = " << getEdgeFreq(BB, Succ) << "\n";
331      }
332    }
333  }
334
335  void dump() const {
336    print(dbgs());
337  }
338};
339
340}
341
342#endif
343