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/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
  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 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.
  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.lookup(BB);
 127     assert(idx);
 128     std::advance(I, idx - 1);
 129
 130     assert(*I == BB);
 131     return I;
 132   }
 133
 134   /// isBackedge - Return if edge Src -> Dst is a reachable backedge.
 135   ///
 136   bool isBackedge(BlockT *Src, BlockT *Dst) {
 137     unsigned a = RPO.lookup(Src);
 138     if (!a)
 139       return false;
 140     unsigned b = RPO.lookup(Dst);
 141     assert(b && "Destination block should be reachable");
 142     return a >= b;
 143   }
 144
 145   /// getSingleBlockPred - return single BB block predecessor or NULL if
 146   /// BB has none or more predecessors.
 147   BlockT *getSingleBlockPred(BlockT *BB) {
 148     typename GT::ChildIteratorType
 149       PI = GraphTraits< Inverse<BlockT *> >::child_begin(BB),
 150       PE = GraphTraits< Inverse<BlockT *> >::child_end(BB);
 151
 152     if (PI == PE)
 153       return 0;
 154
 155     BlockT *Pred = *PI;
 156
 157     ++PI;
 158     if (PI != PE)
 159       return 0;
 160
 161     return Pred;
 162   }
 163
 164   void doBlock(BlockT *BB, BlockT *LoopHead,
 165                SmallPtrSet<BlockT *, 8> &BlocksInLoop) {
 166
 167     DEBUG(dbgs() << "doBlock(" << getBlockName(BB) << ")\n");
 168     setBlockFreq(BB, 0);
 169
 170     if (BB == LoopHead) {
 171       setBlockFreq(BB, EntryFreq);
 172       return;
 173     }
 174
 175     if(BlockT *Pred = getSingleBlockPred(BB)) {
 176       if (BlocksInLoop.count(Pred))
 177         setBlockFreq(BB, getEdgeFreq(Pred, BB));
 178       // TODO: else? irreducible, ignore it for now.
 179       return;
 180     }
 181
 182     bool isInLoop = false;
 183     bool isLoopHead = false;
 184
 185     for (typename GT::ChildIteratorType
 186          PI = GraphTraits< Inverse<BlockT *> >::child_begin(BB),
 187          PE = GraphTraits< Inverse<BlockT *> >::child_end(BB);
 188          PI != PE; ++PI) {
 189       BlockT *Pred = *PI;
 190
 191       if (isBackedge(Pred, BB)) {
 192         isLoopHead = true;
 193       } else if (BlocksInLoop.count(Pred)) {
 194         incBlockFreq(BB, getEdgeFreq(Pred, BB));
 195         isInLoop = true;
 196       }
 197       // TODO: else? irreducible.
 198     }
 199
 200     if (!isInLoop)
 201       return;
 202
 203     if (!isLoopHead)
 204       return;
 205
 206     assert(EntryFreq >= CycleProb[BB]);
 207     uint32_t CProb = CycleProb[BB];
 208     uint32_t Numerator = EntryFreq - CProb ? EntryFreq - CProb : 1;
 209     divBlockFreq(BB, BranchProbability(Numerator, EntryFreq));
 210   }
 211
 212   /// doLoop - Propagate block frequency down through the loop.
 213   void doLoop(BlockT *Head, BlockT *Tail) {
 214     DEBUG(dbgs() << "doLoop(" << getBlockName(Head) << ", "
 215                  << getBlockName(Tail) << ")\n");
 216
 217     SmallPtrSet<BlockT *, 8> BlocksInLoop;
 218
 219     for (rpot_iterator I = rpot_at(Head), E = rpot_at(Tail); ; ++I) {
 220       BlockT *BB = *I;
 221       doBlock(BB, Head, BlocksInLoop);
 222
 223       BlocksInLoop.insert(BB);
 224       if (I == E)
 225         break;
 226     }
 227
 228     // Compute loop's cyclic probability using backedges probabilities.
 229     for (typename GT::ChildIteratorType
 230          PI = GraphTraits< Inverse<BlockT *> >::child_begin(Head),
 231          PE = GraphTraits< Inverse<BlockT *> >::child_end(Head);
 232          PI != PE; ++PI) {
 233       BlockT *Pred = *PI;
 234       assert(Pred);
 235       if (isBackedge(Pred, Head)) {
 236         uint64_t N = getEdgeFreq(Pred, Head).getFrequency();
 237         uint64_t D = getBlockFreq(Head).getFrequency();
 238         assert(N <= EntryFreq && "Backedge frequency must be <= EntryFreq!");
 239         uint64_t Res = (N * EntryFreq) / D;
 240
 241         assert(Res <= UINT32_MAX);
 242         CycleProb[Head] += (uint32_t) Res;
 243         DEBUG(dbgs() << "  CycleProb[" << getBlockName(Head) << "] += " << Res
 244                      << " --> " << CycleProb[Head] << "\n");
 245       }
 246     }
 247   }
 248
 249   friend class BlockFrequencyInfo;
 250   friend class MachineBlockFrequencyInfo;
 251
 252   BlockFrequencyImpl() : EntryFreq(BlockFrequency::getEntryFrequency()) { }
 253
 254   void doFunction(FunctionT *fn, BlockProbInfoT *bpi) {
 255     Fn = fn;
 256     BPI = bpi;
 257
 258     // Clear everything.
 259     RPO.clear();
 260     POT.clear();
 261     CycleProb.clear();
 262     Freqs.clear();
 263
 264     BlockT *EntryBlock = fn->begin();
 265
 266     std::copy(po_begin(EntryBlock), po_end(EntryBlock), std::back_inserter(POT));
 267
 268     unsigned RPOidx = 0;
 269     for (rpot_iterator I = rpot_begin(), E = rpot_end(); I != E; ++I) {
 270       BlockT *BB = *I;
 271       RPO[BB] = ++RPOidx;
 272       DEBUG(dbgs() << "RPO[" << getBlockName(BB) << "] = " << RPO[BB] << "\n");
 273     }
 274
 275     // Travel over all blocks in postorder.
 276     for (pot_iterator I = pot_begin(), E = pot_end(); I != E; ++I) {
 277       BlockT *BB = *I;
 278       BlockT *LastTail = 0;
 279       DEBUG(dbgs() << "POT: " << getBlockName(BB) << "\n");
 280
 281       for (typename GT::ChildIteratorType
 282            PI = GraphTraits< Inverse<BlockT *> >::child_begin(BB),
 283            PE = GraphTraits< Inverse<BlockT *> >::child_end(BB);
 284            PI != PE; ++PI) {
 285
 286         BlockT *Pred = *PI;
 287         if (isBackedge(Pred, BB) && (!LastTail || RPO[Pred] > RPO[LastTail]))
 288           LastTail = Pred;
 289       }
 290
 291       if (LastTail)
 292         doLoop(BB, LastTail);
 293     }
 294
 295     // At the end assume the whole function as a loop, and travel over it once
 296     // again.
 297     doLoop(*(rpot_begin()), *(pot_begin()));
 298   }
 299
 300 public:
 301   /// getBlockFreq - Return block frequency. Return 0 if we don't have it.
 302   BlockFrequency getBlockFreq(const BlockT *BB) const {
 303     typename DenseMap<const BlockT *, BlockFrequency>::const_iterator
 304       I = Freqs.find(BB);
 305     if (I != Freqs.end())
 306       return I->second;
 307     return 0;
 308   }
 309
 310   void print(raw_ostream &OS) const {
 311     OS << "\n\n---- Block Freqs ----\n";
 312     for (typename FunctionT::iterator I = Fn->begin(), E = Fn->end(); I != E;) {
 313       BlockT *BB = I++;
 314       OS << " " << getBlockName(BB) << " = " << getBlockFreq(BB) << "\n";
 315
 316       for (typename GraphTraits<BlockT *>::ChildIteratorType
 317            SI = GraphTraits<BlockT *>::child_begin(BB),
 318            SE = GraphTraits<BlockT *>::child_end(BB); SI != SE; ++SI) {
 319         BlockT *Succ = *SI;
 320         OS << "  " << getBlockName(BB) << " -> " << getBlockName(Succ)
 321            << " = " << getEdgeFreq(BB, Succ) << "\n";
 322       }
 323     }
 324   }
 325
 326   void dump() const {
 327     print(dbgs());
 328   }
 329 };
 330
 331 }
 332
 333 #endif