• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 <sstream>
28 #include <string>
29 
30 namespace llvm {
31 
32 
33 class BlockFrequencyInfo;
34 class MachineBlockFrequencyInfo;
35 
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 {
43 
44   DenseMap<BlockT *, BlockFrequency> Freqs;
45 
46   BlockProbInfoT *BPI;
47 
48   FunctionT *Fn;
49 
50   typedef GraphTraits< Inverse<BlockT *> > GT;
51 
52   const uint32_t EntryFreq;
53 
getBlockName(BasicBlock * BB)54   std::string getBlockName(BasicBlock *BB) const {
55     return BB->getNameStr();
56   }
57 
getBlockName(MachineBasicBlock * MBB)58   std::string getBlockName(MachineBasicBlock *MBB) const {
59     std::stringstream ss;
60     ss << "BB#" << MBB->getNumber();
61 
62     if (const BasicBlock *BB = MBB->getBasicBlock())
63       ss << " derived from LLVM BB " << BB->getNameStr();
64 
65     return ss.str();
66   }
67 
setBlockFreq(BlockT * BB,BlockFrequency Freq)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.
getEdgeFreq(BlockT * Src,BlockT * Dst)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   ///
incBlockFreq(BlockT * BB,BlockFrequency Freq)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   ///
divBlockFreq(BlockT * BB,BranchProbability Prob)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 
pot_begin()118   pot_iterator pot_begin() { return POT.begin(); }
pot_end()119   pot_iterator pot_end() { return POT.end(); }
120 
rpot_begin()121   rpot_iterator rpot_begin() { return POT.rbegin(); }
rpot_end()122   rpot_iterator rpot_end() { return POT.rend(); }
123 
rpot_at(BlockT * BB)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   ///
isReachable(BlockT * BB)137   bool isReachable(BlockT *BB) {
138     return RPO.count(BB);
139   }
140 
141   /// isBackedge - Return if edge Src -> Dst is a backedge.
142   ///
isBackedge(BlockT * Src,BlockT * Dst)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.
getSingleBlockPred(BlockT * BB)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 
doBlock(BlockT * BB,BlockT * LoopHead,SmallPtrSet<BlockT *,8> & BlocksInLoop)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 throught the loop.
doLoop(BlockT * Head,BlockT * Tail)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 
BlockFrequencyImpl()260   BlockFrequencyImpl() : EntryFreq(BlockFrequency::getEntryFrequency()) { }
261 
doFunction(FunctionT * fn,BlockProbInfoT * bpi)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 
309 public:
310   /// getBlockFreq - Return block frequency. Return 0 if we don't have it.
getBlockFreq(BlockT * BB)311   BlockFrequency getBlockFreq(BlockT *BB) const {
312     typename DenseMap<BlockT *, BlockFrequency>::const_iterator I = Freqs.find(BB);
313     if (I != Freqs.end())
314       return I->second;
315     return 0;
316   }
317 
print(raw_ostream & OS)318   void print(raw_ostream &OS) const {
319     OS << "\n\n---- Block Freqs ----\n";
320     for (typename FunctionT::iterator I = Fn->begin(), E = Fn->end(); I != E;) {
321       BlockT *BB = I++;
322       OS << " " << getBlockName(BB) << " = " << getBlockFreq(BB) << "\n";
323 
324       for (typename GraphTraits<BlockT *>::ChildIteratorType
325            SI = GraphTraits<BlockT *>::child_begin(BB),
326            SE = GraphTraits<BlockT *>::child_end(BB); SI != SE; ++SI) {
327         BlockT *Succ = *SI;
328         OS << "  " << getBlockName(BB) << " -> " << getBlockName(Succ)
329            << " = " << getEdgeFreq(BB, Succ) << "\n";
330       }
331     }
332   }
333 
dump()334   void dump() const {
335     print(dbgs());
336   }
337 };
338 
339 }
340 
341 #endif
342