include/llvm/Analysis/BlockFrequencyImpl.h

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