MachineTraceMetrics.cpp revision 8e54ab5c7618bf3813c337ad181a741f30eb36cc
1//===- lib/CodeGen/MachineTraceMetrics.cpp ----------------------*- 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#define DEBUG_TYPE "early-ifcvt" 11#include "MachineTraceMetrics.h" 12#include "llvm/CodeGen/MachineBasicBlock.h" 13#include "llvm/CodeGen/MachineBranchProbabilityInfo.h" 14#include "llvm/CodeGen/MachineLoopInfo.h" 15#include "llvm/CodeGen/MachineRegisterInfo.h" 16#include "llvm/CodeGen/Passes.h" 17#include "llvm/Target/TargetInstrInfo.h" 18#include "llvm/Target/TargetRegisterInfo.h" 19#include "llvm/Support/Debug.h" 20#include "llvm/Support/raw_ostream.h" 21#include "llvm/ADT/PostOrderIterator.h" 22 23using namespace llvm; 24 25char MachineTraceMetrics::ID = 0; 26char &llvm::MachineTraceMetricsID = MachineTraceMetrics::ID; 27 28INITIALIZE_PASS_BEGIN(MachineTraceMetrics, 29 "machine-trace-metrics", "Machine Trace Metrics", false, true) 30INITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfo) 31INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo) 32INITIALIZE_PASS_END(MachineTraceMetrics, 33 "machine-trace-metrics", "Machine Trace Metrics", false, true) 34 35MachineTraceMetrics::MachineTraceMetrics() 36 : MachineFunctionPass(ID), TII(0), TRI(0), MRI(0), Loops(0) { 37 std::fill(Ensembles, array_endof(Ensembles), (Ensemble*)0); 38} 39 40void MachineTraceMetrics::getAnalysisUsage(AnalysisUsage &AU) const { 41 AU.setPreservesAll(); 42 AU.addRequired<MachineBranchProbabilityInfo>(); 43 AU.addRequired<MachineLoopInfo>(); 44 MachineFunctionPass::getAnalysisUsage(AU); 45} 46 47bool MachineTraceMetrics::runOnMachineFunction(MachineFunction &Func) { 48 MF = &Func; 49 TII = MF->getTarget().getInstrInfo(); 50 TRI = MF->getTarget().getRegisterInfo(); 51 MRI = &MF->getRegInfo(); 52 Loops = &getAnalysis<MachineLoopInfo>(); 53 BlockInfo.resize(MF->getNumBlockIDs()); 54 return false; 55} 56 57void MachineTraceMetrics::releaseMemory() { 58 BlockInfo.clear(); 59 for (unsigned i = 0; i != TS_NumStrategies; ++i) { 60 delete Ensembles[i]; 61 Ensembles[i] = 0; 62 } 63} 64 65//===----------------------------------------------------------------------===// 66// Fixed block information 67//===----------------------------------------------------------------------===// 68// 69// The number of instructions in a basic block and the CPU resources used by 70// those instructions don't depend on any given trace strategy. 71 72/// Compute the resource usage in basic block MBB. 73const MachineTraceMetrics::FixedBlockInfo* 74MachineTraceMetrics::getResources(const MachineBasicBlock *MBB) { 75 assert(MBB && "No basic block"); 76 FixedBlockInfo *FBI = &BlockInfo[MBB->getNumber()]; 77 if (FBI->hasResources()) 78 return FBI; 79 80 // Compute resource usage in the block. 81 // FIXME: Compute per-functional unit counts. 82 FBI->HasCalls = false; 83 unsigned InstrCount = 0; 84 for (MachineBasicBlock::const_iterator I = MBB->begin(), E = MBB->end(); 85 I != E; ++I) { 86 const MachineInstr *MI = I; 87 if (MI->isTransient()) 88 continue; 89 ++InstrCount; 90 if (MI->isCall()) 91 FBI->HasCalls = true; 92 } 93 FBI->InstrCount = InstrCount; 94 return FBI; 95} 96 97//===----------------------------------------------------------------------===// 98// Ensemble utility functions 99//===----------------------------------------------------------------------===// 100 101MachineTraceMetrics::Ensemble::Ensemble(MachineTraceMetrics *ct) 102 : CT(*ct) { 103 BlockInfo.resize(CT.BlockInfo.size()); 104} 105 106// Virtual destructor serves as an anchor. 107MachineTraceMetrics::Ensemble::~Ensemble() {} 108 109const MachineLoop* 110MachineTraceMetrics::Ensemble::getLoopFor(const MachineBasicBlock *MBB) const { 111 return CT.Loops->getLoopFor(MBB); 112} 113 114// Update resource-related information in the TraceBlockInfo for MBB. 115// Only update resources related to the trace above MBB. 116void MachineTraceMetrics::Ensemble:: 117computeDepthResources(const MachineBasicBlock *MBB) { 118 TraceBlockInfo *TBI = &BlockInfo[MBB->getNumber()]; 119 120 // Compute resources from trace above. The top block is simple. 121 if (!TBI->Pred) { 122 TBI->InstrDepth = 0; 123 TBI->Head = MBB->getNumber(); 124 return; 125 } 126 127 // Compute from the block above. A post-order traversal ensures the 128 // predecessor is always computed first. 129 TraceBlockInfo *PredTBI = &BlockInfo[TBI->Pred->getNumber()]; 130 assert(PredTBI->hasValidDepth() && "Trace above has not been computed yet"); 131 const FixedBlockInfo *PredFBI = CT.getResources(TBI->Pred); 132 TBI->InstrDepth = PredTBI->InstrDepth + PredFBI->InstrCount; 133 TBI->Head = PredTBI->Head; 134} 135 136// Update resource-related information in the TraceBlockInfo for MBB. 137// Only update resources related to the trace below MBB. 138void MachineTraceMetrics::Ensemble:: 139computeHeightResources(const MachineBasicBlock *MBB) { 140 TraceBlockInfo *TBI = &BlockInfo[MBB->getNumber()]; 141 142 // Compute resources for the current block. 143 TBI->InstrHeight = CT.getResources(MBB)->InstrCount; 144 145 // The trace tail is done. 146 if (!TBI->Succ) { 147 TBI->Tail = MBB->getNumber(); 148 return; 149 } 150 151 // Compute from the block below. A post-order traversal ensures the 152 // predecessor is always computed first. 153 TraceBlockInfo *SuccTBI = &BlockInfo[TBI->Succ->getNumber()]; 154 assert(SuccTBI->hasValidHeight() && "Trace below has not been computed yet"); 155 TBI->InstrHeight += SuccTBI->InstrHeight; 156 TBI->Tail = SuccTBI->Tail; 157} 158 159// Check if depth resources for MBB are valid and return the TBI. 160// Return NULL if the resources have been invalidated. 161const MachineTraceMetrics::TraceBlockInfo* 162MachineTraceMetrics::Ensemble:: 163getDepthResources(const MachineBasicBlock *MBB) const { 164 const TraceBlockInfo *TBI = &BlockInfo[MBB->getNumber()]; 165 return TBI->hasValidDepth() ? TBI : 0; 166} 167 168// Check if height resources for MBB are valid and return the TBI. 169// Return NULL if the resources have been invalidated. 170const MachineTraceMetrics::TraceBlockInfo* 171MachineTraceMetrics::Ensemble:: 172getHeightResources(const MachineBasicBlock *MBB) const { 173 const TraceBlockInfo *TBI = &BlockInfo[MBB->getNumber()]; 174 return TBI->hasValidHeight() ? TBI : 0; 175} 176 177//===----------------------------------------------------------------------===// 178// Trace Selection Strategies 179//===----------------------------------------------------------------------===// 180// 181// A trace selection strategy is implemented as a sub-class of Ensemble. The 182// trace through a block B is computed by two DFS traversals of the CFG 183// starting from B. One upwards, and one downwards. During the upwards DFS, 184// pickTracePred() is called on the post-ordered blocks. During the downwards 185// DFS, pickTraceSucc() is called in a post-order. 186// 187 188// MinInstrCountEnsemble - Pick the trace that executes the least number of 189// instructions. 190namespace { 191class MinInstrCountEnsemble : public MachineTraceMetrics::Ensemble { 192 const char *getName() const { return "MinInstr"; } 193 const MachineBasicBlock *pickTracePred(const MachineBasicBlock*); 194 const MachineBasicBlock *pickTraceSucc(const MachineBasicBlock*); 195 196public: 197 MinInstrCountEnsemble(MachineTraceMetrics *ct) 198 : MachineTraceMetrics::Ensemble(ct) {} 199}; 200} 201 202// Select the preferred predecessor for MBB. 203const MachineBasicBlock* 204MinInstrCountEnsemble::pickTracePred(const MachineBasicBlock *MBB) { 205 if (MBB->pred_empty()) 206 return 0; 207 const MachineLoop *CurLoop = getLoopFor(MBB); 208 // Don't leave loops, and never follow back-edges. 209 if (CurLoop && MBB == CurLoop->getHeader()) 210 return 0; 211 unsigned CurCount = CT.getResources(MBB)->InstrCount; 212 const MachineBasicBlock *Best = 0; 213 unsigned BestDepth = 0; 214 for (MachineBasicBlock::const_pred_iterator 215 I = MBB->pred_begin(), E = MBB->pred_end(); I != E; ++I) { 216 const MachineBasicBlock *Pred = *I; 217 // Don't consider predecessors in other loops. 218 if (getLoopFor(Pred) != CurLoop) 219 continue; 220 const MachineTraceMetrics::TraceBlockInfo *PredTBI = 221 getDepthResources(Pred); 222 assert(PredTBI && "Predecessor must be visited first"); 223 // Pick the predecessor that would give this block the smallest InstrDepth. 224 unsigned Depth = PredTBI->InstrDepth + CurCount; 225 if (!Best || Depth < BestDepth) 226 Best = Pred, BestDepth = Depth; 227 } 228 return Best; 229} 230 231// Select the preferred successor for MBB. 232const MachineBasicBlock* 233MinInstrCountEnsemble::pickTraceSucc(const MachineBasicBlock *MBB) { 234 if (MBB->pred_empty()) 235 return 0; 236 const MachineLoop *CurLoop = getLoopFor(MBB); 237 const MachineBasicBlock *Best = 0; 238 unsigned BestHeight = 0; 239 for (MachineBasicBlock::const_succ_iterator 240 I = MBB->succ_begin(), E = MBB->succ_end(); I != E; ++I) { 241 const MachineBasicBlock *Succ = *I; 242 // Don't consider back-edges. 243 if (CurLoop && Succ == CurLoop->getHeader()) 244 continue; 245 // Don't consider successors in other loops. 246 if (getLoopFor(Succ) != CurLoop) 247 continue; 248 const MachineTraceMetrics::TraceBlockInfo *SuccTBI = 249 getHeightResources(Succ); 250 assert(SuccTBI && "Successor must be visited first"); 251 // Pick the successor that would give this block the smallest InstrHeight. 252 unsigned Height = SuccTBI->InstrHeight; 253 if (!Best || Height < BestHeight) 254 Best = Succ, BestHeight = Height; 255 } 256 return Best; 257} 258 259// Get an Ensemble sub-class for the requested trace strategy. 260MachineTraceMetrics::Ensemble * 261MachineTraceMetrics::getEnsemble(MachineTraceMetrics::Strategy strategy) { 262 assert(strategy < TS_NumStrategies && "Invalid trace strategy enum"); 263 Ensemble *&E = Ensembles[strategy]; 264 if (E) 265 return E; 266 267 // Allocate new Ensemble on demand. 268 switch (strategy) { 269 case TS_MinInstrCount: return (E = new MinInstrCountEnsemble(this)); 270 default: llvm_unreachable("Invalid trace strategy enum"); 271 } 272} 273 274void MachineTraceMetrics::invalidate(const MachineBasicBlock *MBB) { 275 DEBUG(dbgs() << "Invalidate traces through BB#" << MBB->getNumber() << '\n'); 276 BlockInfo[MBB->getNumber()].invalidate(); 277 for (unsigned i = 0; i != TS_NumStrategies; ++i) 278 if (Ensembles[i]) 279 Ensembles[i]->invalidate(MBB); 280} 281 282void MachineTraceMetrics::verifyAnalysis() const { 283#ifndef NDEBUG 284 assert(BlockInfo.size() == MF->getNumBlockIDs() && "Outdated BlockInfo size"); 285 for (unsigned i = 0; i != TS_NumStrategies; ++i) 286 if (Ensembles[i]) 287 Ensembles[i]->verify(); 288#endif 289} 290 291//===----------------------------------------------------------------------===// 292// Trace building 293//===----------------------------------------------------------------------===// 294// 295// Traces are built by two CFG traversals. To avoid recomputing too much, use a 296// set abstraction that confines the search to the current loop, and doesn't 297// revisit blocks. 298 299namespace { 300struct LoopBounds { 301 MutableArrayRef<MachineTraceMetrics::TraceBlockInfo> Blocks; 302 const MachineLoopInfo *Loops; 303 const MachineLoop *CurLoop; 304 bool Downward; 305 LoopBounds(MutableArrayRef<MachineTraceMetrics::TraceBlockInfo> blocks, 306 const MachineLoopInfo *loops, const MachineLoop *curloop) 307 : Blocks(blocks), Loops(loops), CurLoop(curloop), Downward(false) {} 308}; 309} 310 311// Specialize po_iterator_storage in order to prune the post-order traversal so 312// it is limited to the current loop and doesn't traverse the loop back edges. 313namespace llvm { 314template<> 315class po_iterator_storage<LoopBounds, true> { 316 LoopBounds &LB; 317public: 318 po_iterator_storage(LoopBounds &lb) : LB(lb) {} 319 void finishPostorder(const MachineBasicBlock*) {} 320 321 bool insertEdge(const MachineBasicBlock *From, const MachineBasicBlock *To) { 322 // Skip already visited To blocks. 323 MachineTraceMetrics::TraceBlockInfo &TBI = LB.Blocks[To->getNumber()]; 324 if (LB.Downward ? TBI.hasValidHeight() : TBI.hasValidDepth()) 325 return false; 326 // Don't follow CurLoop backedges. 327 if (LB.CurLoop && (LB.Downward ? To : From) == LB.CurLoop->getHeader()) 328 return false; 329 // Don't leave CurLoop. 330 if (LB.Loops->getLoopFor(To) != LB.CurLoop) 331 return false; 332 // This is a new block. The PO traversal will compute height/depth 333 // resources, causing us to reject new edges to To. This only works because 334 // we reject back-edges, so the CFG is cycle-free. 335 return true; 336 } 337}; 338} 339 340/// Compute the trace through MBB. 341void MachineTraceMetrics::Ensemble::computeTrace(const MachineBasicBlock *MBB) { 342 DEBUG(dbgs() << "Computing " << getName() << " trace through BB#" 343 << MBB->getNumber() << '\n'); 344 // Set up loop bounds for the backwards post-order traversal. 345 LoopBounds Bounds(BlockInfo, CT.Loops, getLoopFor(MBB)); 346 347 // Run an upwards post-order search for the trace start. 348 Bounds.Downward = false; 349 typedef ipo_ext_iterator<const MachineBasicBlock*, LoopBounds> UpwardPO; 350 for (UpwardPO I = ipo_ext_begin(MBB, Bounds), E = ipo_ext_end(MBB, Bounds); 351 I != E; ++I) { 352 DEBUG(dbgs() << " pred for BB#" << I->getNumber() << ": "); 353 TraceBlockInfo &TBI = BlockInfo[I->getNumber()]; 354 // All the predecessors have been visited, pick the preferred one. 355 TBI.Pred = pickTracePred(*I); 356 DEBUG({ 357 if (TBI.Pred) 358 dbgs() << "BB#" << TBI.Pred->getNumber() << '\n'; 359 else 360 dbgs() << "null\n"; 361 }); 362 // The trace leading to I is now known, compute the depth resources. 363 computeDepthResources(*I); 364 } 365 366 // Run a downwards post-order search for the trace end. 367 Bounds.Downward = true; 368 typedef po_ext_iterator<const MachineBasicBlock*, LoopBounds> DownwardPO; 369 for (DownwardPO I = po_ext_begin(MBB, Bounds), E = po_ext_end(MBB, Bounds); 370 I != E; ++I) { 371 DEBUG(dbgs() << " succ for BB#" << I->getNumber() << ": "); 372 TraceBlockInfo &TBI = BlockInfo[I->getNumber()]; 373 // All the successors have been visited, pick the preferred one. 374 TBI.Succ = pickTraceSucc(*I); 375 DEBUG({ 376 if (TBI.Pred) 377 dbgs() << "BB#" << TBI.Succ->getNumber() << '\n'; 378 else 379 dbgs() << "null\n"; 380 }); 381 // The trace leaving I is now known, compute the height resources. 382 computeHeightResources(*I); 383 } 384} 385 386/// Invalidate traces through BadMBB. 387void 388MachineTraceMetrics::Ensemble::invalidate(const MachineBasicBlock *BadMBB) { 389 SmallVector<const MachineBasicBlock*, 16> WorkList; 390 TraceBlockInfo &BadTBI = BlockInfo[BadMBB->getNumber()]; 391 392 // Invalidate height resources of blocks above MBB. 393 if (BadTBI.hasValidHeight()) { 394 BadTBI.invalidateHeight(); 395 WorkList.push_back(BadMBB); 396 do { 397 const MachineBasicBlock *MBB = WorkList.pop_back_val(); 398 DEBUG(dbgs() << "Invalidate BB#" << MBB->getNumber() << ' ' << getName() 399 << " height.\n"); 400 // Find any MBB predecessors that have MBB as their preferred successor. 401 // They are the only ones that need to be invalidated. 402 for (MachineBasicBlock::const_pred_iterator 403 I = MBB->pred_begin(), E = MBB->pred_end(); I != E; ++I) { 404 TraceBlockInfo &TBI = BlockInfo[(*I)->getNumber()]; 405 if (!TBI.hasValidHeight()) 406 continue; 407 if (TBI.Succ == MBB) { 408 TBI.invalidateHeight(); 409 WorkList.push_back(*I); 410 continue; 411 } 412 // Verify that TBI.Succ is actually a *I successor. 413 assert((!TBI.Succ || (*I)->isSuccessor(TBI.Succ)) && "CFG changed"); 414 } 415 } while (!WorkList.empty()); 416 } 417 418 // Invalidate depth resources of blocks below MBB. 419 if (BadTBI.hasValidDepth()) { 420 BadTBI.invalidateDepth(); 421 WorkList.push_back(BadMBB); 422 do { 423 const MachineBasicBlock *MBB = WorkList.pop_back_val(); 424 DEBUG(dbgs() << "Invalidate BB#" << MBB->getNumber() << ' ' << getName() 425 << " depth.\n"); 426 // Find any MBB successors that have MBB as their preferred predecessor. 427 // They are the only ones that need to be invalidated. 428 for (MachineBasicBlock::const_succ_iterator 429 I = MBB->succ_begin(), E = MBB->succ_end(); I != E; ++I) { 430 TraceBlockInfo &TBI = BlockInfo[(*I)->getNumber()]; 431 if (!TBI.hasValidDepth()) 432 continue; 433 if (TBI.Pred == MBB) { 434 TBI.invalidateDepth(); 435 WorkList.push_back(*I); 436 continue; 437 } 438 // Verify that TBI.Pred is actually a *I predecessor. 439 assert((!TBI.Pred || (*I)->isPredecessor(TBI.Pred)) && "CFG changed"); 440 } 441 } while (!WorkList.empty()); 442 } 443} 444 445void MachineTraceMetrics::Ensemble::verify() const { 446#ifndef NDEBUG 447 assert(BlockInfo.size() == CT.MF->getNumBlockIDs() && 448 "Outdated BlockInfo size"); 449 for (unsigned Num = 0, e = BlockInfo.size(); Num != e; ++Num) { 450 const TraceBlockInfo &TBI = BlockInfo[Num]; 451 if (TBI.hasValidDepth() && TBI.Pred) { 452 const MachineBasicBlock *MBB = CT.MF->getBlockNumbered(Num); 453 assert(MBB->isPredecessor(TBI.Pred) && "CFG doesn't match trace"); 454 assert(BlockInfo[TBI.Pred->getNumber()].hasValidDepth() && 455 "Trace is broken, depth should have been invalidated."); 456 const MachineLoop *Loop = getLoopFor(MBB); 457 assert(!(Loop && MBB == Loop->getHeader()) && "Trace contains backedge"); 458 } 459 if (TBI.hasValidHeight() && TBI.Succ) { 460 const MachineBasicBlock *MBB = CT.MF->getBlockNumbered(Num); 461 assert(MBB->isSuccessor(TBI.Succ) && "CFG doesn't match trace"); 462 assert(BlockInfo[TBI.Succ->getNumber()].hasValidHeight() && 463 "Trace is broken, height should have been invalidated."); 464 const MachineLoop *Loop = getLoopFor(MBB); 465 const MachineLoop *SuccLoop = getLoopFor(TBI.Succ); 466 assert(!(Loop && Loop == SuccLoop && TBI.Succ == Loop->getHeader()) && 467 "Trace contains backedge"); 468 } 469 } 470#endif 471} 472 473MachineTraceMetrics::Trace 474MachineTraceMetrics::Ensemble::getTrace(const MachineBasicBlock *MBB) { 475 // FIXME: Check cache tags, recompute as needed. 476 computeTrace(MBB); 477 return Trace(*this, BlockInfo[MBB->getNumber()]); 478} 479 480void MachineTraceMetrics::Ensemble::print(raw_ostream &OS) const { 481 OS << getName() << " ensemble:\n"; 482 for (unsigned i = 0, e = BlockInfo.size(); i != e; ++i) { 483 OS << " BB#" << i << '\t'; 484 BlockInfo[i].print(OS); 485 OS << '\n'; 486 } 487} 488 489void MachineTraceMetrics::TraceBlockInfo::print(raw_ostream &OS) const { 490 if (hasValidDepth()) { 491 OS << "depth=" << InstrDepth; 492 if (Pred) 493 OS << " pred=BB#" << Pred->getNumber(); 494 else 495 OS << " pred=null"; 496 OS << " head=BB#" << Head; 497 } else 498 OS << "depth invalid"; 499 OS << ", "; 500 if (hasValidHeight()) { 501 OS << "height=" << InstrHeight; 502 if (Succ) 503 OS << " succ=BB#" << Succ->getNumber(); 504 else 505 OS << " succ=null"; 506 OS << " tail=BB#" << Tail; 507 } else 508 OS << "height invalid"; 509} 510 511void MachineTraceMetrics::Trace::print(raw_ostream &OS) const { 512 unsigned MBBNum = &TBI - &TE.BlockInfo[0]; 513 514 OS << TE.getName() << " trace BB#" << TBI.Head << " --> BB#" << MBBNum 515 << " --> BB#" << TBI.Tail << ':'; 516 if (TBI.hasValidHeight() && TBI.hasValidDepth()) 517 OS << ' ' << getInstrCount() << " instrs."; 518 519 const MachineTraceMetrics::TraceBlockInfo *Block = &TBI; 520 OS << "\nBB#" << MBBNum; 521 while (Block->hasValidDepth() && Block->Pred) { 522 unsigned Num = Block->Pred->getNumber(); 523 OS << " <- BB#" << Num; 524 Block = &TE.BlockInfo[Num]; 525 } 526 527 Block = &TBI; 528 OS << "\n "; 529 while (Block->hasValidHeight() && Block->Succ) { 530 unsigned Num = Block->Succ->getNumber(); 531 OS << " -> BB#" << Num; 532 Block = &TE.BlockInfo[Num]; 533 } 534 OS << '\n'; 535} 536