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