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