contrib/llvm/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/BasicBlock.h"
  18 #include "llvm/ADT/DenseMap.h"
  19 #include "llvm/ADT/PostOrderIterator.h"
  20 #include "llvm/CodeGen/MachineBasicBlock.h"
  21 #include "llvm/CodeGen/MachineFunction.h"
  22 #include "llvm/Support/BranchProbability.h"
  23 #include "llvm/Support/Debug.h"
  24 #include "llvm/Support/raw_ostream.h"
  25 #include <vector>
  26 #include <sstream>
  27 #include <string>
  28
  29 namespace llvm {
  30
  31
  32 class BlockFrequency;
  33 class MachineBlockFrequency;
  34
  35 /// BlockFrequencyImpl implements block frequency algorithm for IR and
  36 /// Machine Instructions. Algorithm starts with value 1024 (START_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<BlockT *, uint32_t> Freqs;
  44
  45   BlockProbInfoT *BPI;
  46
  47   FunctionT *Fn;
  48
  49   typedef GraphTraits< Inverse<BlockT *> > GT;
  50
  51   static const uint32_t START_FREQ = 1024;
  52
  53   std::string getBlockName(BasicBlock *BB) const {
  54     return BB->getNameStr();
  55   }
  56
  57   std::string getBlockName(MachineBasicBlock *MBB) const {
  58     std::stringstream ss;
  59     ss << "BB#" << MBB->getNumber();
  60
  61     if (const BasicBlock *BB = MBB->getBasicBlock())
  62       ss << " derived from LLVM BB " << BB->getNameStr();
  63
  64     return ss.str();
  65   }
  66
  67   void setBlockFreq(BlockT *BB, uint32_t Freq) {
  68     Freqs[BB] = Freq;
  69     DEBUG(dbgs() << "Frequency(" << getBlockName(BB) << ") = " << Freq << "\n");
  70   }
  71
  72   /// getEdgeFreq - Return edge frequency based on SRC frequency and Src -> Dst
  73   /// edge probability.
  74   uint32_t getEdgeFreq(BlockT *Src, BlockT *Dst) const {
  75     BranchProbability Prob = BPI->getEdgeProbability(Src, Dst);
  76     uint64_t N = Prob.getNumerator();
  77     uint64_t D = Prob.getDenominator();
  78     uint64_t Res = (N * getBlockFreq(Src)) / D;
  79
  80     assert(Res <= UINT32_MAX);
  81     return (uint32_t) Res;
  82   }
  83
  84   /// incBlockFreq - Increase BB block frequency by FREQ.
  85   ///
  86   void incBlockFreq(BlockT *BB, uint32_t Freq) {
  87     Freqs[BB] += Freq;
  88     DEBUG(dbgs() << "Frequency(" << getBlockName(BB) << ") += " << Freq
  89                  << " --> " << Freqs[BB] << "\n");
  90   }
  91
  92   /// divBlockFreq - Divide BB block frequency by PROB. If Prob = 0 do nothing.
  93   ///
  94   void divBlockFreq(BlockT *BB, BranchProbability Prob) {
  95     uint64_t N = Prob.getNumerator();
  96     assert(N && "Illegal division by zero!");
  97     uint64_t D = Prob.getDenominator();
  98     uint64_t Freq = (Freqs[BB] * D) / N;
  99
 100     // Should we assert it?
 101     if (Freq > UINT32_MAX)
 102       Freq = UINT32_MAX;
 103
 104     Freqs[BB] = (uint32_t) Freq;
 105     DEBUG(dbgs() << "Frequency(" << getBlockName(BB) << ") /= (" << Prob
 106                  << ") --> " << 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   // Cycle Probability for each bloch.
 116   DenseMap<BlockT *, uint32_t> CycleProb;
 117
 118   // (reverse-)postorder traversal iterators.
 119   typedef typename std::vector<BlockT *>::iterator pot_iterator;
 120   typedef typename std::vector<BlockT *>::reverse_iterator rpot_iterator;
 121
 122   pot_iterator pot_begin() { return POT.begin(); }
 123   pot_iterator pot_end() { return POT.end(); }
 124
 125   rpot_iterator rpot_begin() { return POT.rbegin(); }
 126   rpot_iterator rpot_end() { return POT.rend(); }
 127
 128   rpot_iterator rpot_at(BlockT *BB) {
 129     rpot_iterator I = rpot_begin();
 130     unsigned idx = RPO[BB];
 131     assert(idx);
 132     std::advance(I, idx - 1);
 133
 134     assert(*I == BB);
 135     return I;
 136   }
 137
 138
 139   /// Return a probability of getting to the DST block through SRC->DST edge.
 140   ///
 141   BranchProbability getBackEdgeProbability(BlockT *Src, BlockT *Dst) const {
 142     uint32_t N = getEdgeFreq(Src, Dst);
 143     uint32_t D = getBlockFreq(Dst);
 144
 145     return BranchProbability(N, D);
 146   }
 147
 148   /// isReachable - Returns if BB block is reachable from the entry.
 149   ///
 150   bool isReachable(BlockT *BB) {
 151     return RPO.count(BB);
 152   }
 153
 154   /// isBackedge - Return if edge Src -> Dst is a backedge.
 155   ///
 156   bool isBackedge(BlockT *Src, BlockT *Dst) {
 157     assert(isReachable(Src));
 158     assert(isReachable(Dst));
 159
 160     unsigned a = RPO[Src];
 161     unsigned b = RPO[Dst];
 162
 163     return a > b;
 164   }
 165
 166   /// getSingleBlockPred - return single BB block predecessor or NULL if
 167   /// BB has none or more predecessors.
 168   BlockT *getSingleBlockPred(BlockT *BB) {
 169     typename GT::ChildIteratorType
 170       PI = GraphTraits< Inverse<BlockT *> >::child_begin(BB),
 171       PE = GraphTraits< Inverse<BlockT *> >::child_end(BB);
 172
 173     if (PI == PE)
 174       return 0;
 175
 176     BlockT *Pred = *PI;
 177
 178     ++PI;
 179     if (PI != PE)
 180       return 0;
 181
 182     return Pred;
 183   }
 184
 185   void doBlock(BlockT *BB, BlockT *LoopHead,
 186                SmallPtrSet<BlockT *, 8> &BlocksInLoop) {
 187
 188     DEBUG(dbgs() << "doBlock(" << getBlockName(BB) << ")\n");
 189     setBlockFreq(BB, 0);
 190
 191     if (BB == LoopHead) {
 192       setBlockFreq(BB, START_FREQ);
 193       return;
 194     }
 195
 196     if(BlockT *Pred = getSingleBlockPred(BB)) {
 197       if (BlocksInLoop.count(Pred))
 198         setBlockFreq(BB, getEdgeFreq(Pred, BB));
 199       // TODO: else? irreducible, ignore it for now.
 200       return;
 201     }
 202
 203     bool isInLoop = false;
 204     bool isLoopHead = false;
 205
 206     for (typename GT::ChildIteratorType
 207          PI = GraphTraits< Inverse<BlockT *> >::child_begin(BB),
 208          PE = GraphTraits< Inverse<BlockT *> >::child_end(BB);
 209          PI != PE; ++PI) {
 210       BlockT *Pred = *PI;
 211
 212       if (isReachable(Pred) && isBackedge(Pred, BB)) {
 213         isLoopHead = true;
 214       } else if (BlocksInLoop.count(Pred)) {
 215         incBlockFreq(BB, getEdgeFreq(Pred, BB));
 216         isInLoop = true;
 217       }
 218       // TODO: else? irreducible.
 219     }
 220
 221     if (!isInLoop)
 222       return;
 223
 224     if (!isLoopHead)
 225       return;
 226
 227     assert(START_FREQ >= CycleProb[BB]);
 228     uint32_t CProb = CycleProb[BB];
 229     uint32_t Numerator = START_FREQ - CProb ? START_FREQ - CProb : 1;
 230     divBlockFreq(BB, BranchProbability(Numerator, START_FREQ));
 231   }
 232
 233   /// doLoop - Propagate block frequency down throught the loop.
 234   void doLoop(BlockT *Head, BlockT *Tail) {
 235     DEBUG(dbgs() << "doLoop(" << getBlockName(Head) << ", "
 236                  << getBlockName(Tail) << ")\n");
 237
 238     SmallPtrSet<BlockT *, 8> BlocksInLoop;
 239
 240     for (rpot_iterator I = rpot_at(Head), E = rpot_end(); I != E; ++I) {
 241       BlockT *BB = *I;
 242       doBlock(BB, Head, BlocksInLoop);
 243
 244       BlocksInLoop.insert(BB);
 245     }
 246
 247     // Compute loop's cyclic probability using backedges probabilities.
 248     for (typename GT::ChildIteratorType
 249          PI = GraphTraits< Inverse<BlockT *> >::child_begin(Head),
 250          PE = GraphTraits< Inverse<BlockT *> >::child_end(Head);
 251          PI != PE; ++PI) {
 252       BlockT *Pred = *PI;
 253       assert(Pred);
 254       if (isReachable(Pred) && isBackedge(Pred, Head)) {
 255         BranchProbability Prob = getBackEdgeProbability(Pred, Head);
 256         uint64_t N = Prob.getNumerator();
 257         uint64_t D = Prob.getDenominator();
 258         uint64_t Res = (N * START_FREQ) / D;
 259
 260         assert(Res <= UINT32_MAX);
 261         CycleProb[Head] += (uint32_t) Res;
 262       }
 263     }
 264   }
 265
 266   friend class BlockFrequency;
 267   friend class MachineBlockFrequency;
 268
 269   void doFunction(FunctionT *fn, BlockProbInfoT *bpi) {
 270     Fn = fn;
 271     BPI = bpi;
 272
 273     // Clear everything.
 274     RPO.clear();
 275     POT.clear();
 276     CycleProb.clear();
 277     Freqs.clear();
 278
 279     BlockT *EntryBlock = fn->begin();
 280
 281     copy(po_begin(EntryBlock), po_end(EntryBlock), back_inserter(POT));
 282
 283     unsigned RPOidx = 0;
 284     for (rpot_iterator I = rpot_begin(), E = rpot_end(); I != E; ++I) {
 285       BlockT *BB = *I;
 286       RPO[BB] = ++RPOidx;
 287       DEBUG(dbgs() << "RPO[" << getBlockName(BB) << "] = " << RPO[BB] << "\n");
 288     }
 289
 290     // Travel over all blocks in postorder.
 291     for (pot_iterator I = pot_begin(), E = pot_end(); I != E; ++I) {
 292       BlockT *BB = *I;
 293       BlockT *LastTail = 0;
 294       DEBUG(dbgs() << "POT: " << getBlockName(BB) << "\n");
 295
 296       for (typename GT::ChildIteratorType
 297            PI = GraphTraits< Inverse<BlockT *> >::child_begin(BB),
 298            PE = GraphTraits< Inverse<BlockT *> >::child_end(BB);
 299            PI != PE; ++PI) {
 300
 301         BlockT *Pred = *PI;
 302         if (isReachable(Pred) && isBackedge(Pred, BB)
 303             && (!LastTail || RPO[Pred] > RPO[LastTail]))
 304           LastTail = Pred;
 305       }
 306
 307       if (LastTail)
 308         doLoop(BB, LastTail);
 309     }
 310
 311     // At the end assume the whole function as a loop, and travel over it once
 312     // again.
 313     doLoop(*(rpot_begin()), *(pot_begin()));
 314   }
 315
 316 public:
 317   /// getBlockFreq - Return block frequency. Never return 0, value must be
 318   /// positive.
 319   uint32_t getBlockFreq(BlockT *BB) const {
 320     typename DenseMap<BlockT *, uint32_t>::const_iterator I = Freqs.find(BB);
 321     if (I != Freqs.end())
 322       return I->second ? I->second : 1;
 323     return 1;
 324   }
 325
 326   void print(raw_ostream &OS) const {
 327     OS << "\n\n---- Block Freqs ----\n";
 328     for (typename FunctionT::iterator I = Fn->begin(), E = Fn->end(); I != E;) {
 329       BlockT *BB = I++;
 330       OS << " " << getBlockName(BB) << " = " << getBlockFreq(BB) << "\n";
 331
 332       for (typename GraphTraits<BlockT *>::ChildIteratorType
 333            SI = GraphTraits<BlockT *>::child_begin(BB),
 334            SE = GraphTraits<BlockT *>::child_end(BB); SI != SE; ++SI) {
 335         BlockT *Succ = *SI;
 336         OS << "  " << getBlockName(BB) << " -> " << getBlockName(Succ)
 337            << " = " << getEdgeFreq(BB, Succ) << "\n";
 338       }
 339     }
 340   }
 341
 342   void dump() const {
 343     print(dbgs());
 344   }
 345 };
 346
 347 }
 348
 349 #endif