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