include/llvm/Analysis/BlockFrequencyImpl.h

   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
  29 namespace llvm {
  30
  31
  32 class BlockFrequencyInfo;
  33 class 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.
  40 template<class BlockT, class FunctionT, class BlockProbInfoT>
  41 class 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 throught 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
 309 public:
 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