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