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) { 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 348
