include/llvm/Analysis/BlockFrequencyInfoImpl.h

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