1 //===- lib/CodeGen/MachineTraceMetrics.cpp --------------------------------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 9 #include "llvm/CodeGen/MachineTraceMetrics.h" 10 #include "llvm/ADT/ArrayRef.h" 11 #include "llvm/ADT/DenseMap.h" 12 #include "llvm/ADT/Optional.h" 13 #include "llvm/ADT/PostOrderIterator.h" 14 #include "llvm/ADT/SmallPtrSet.h" 15 #include "llvm/ADT/SmallVector.h" 16 #include "llvm/ADT/SparseSet.h" 17 #include "llvm/CodeGen/MachineBasicBlock.h" 18 #include "llvm/CodeGen/MachineBranchProbabilityInfo.h" 19 #include "llvm/CodeGen/MachineFunction.h" 20 #include "llvm/CodeGen/MachineInstr.h" 21 #include "llvm/CodeGen/MachineLoopInfo.h" 22 #include "llvm/CodeGen/MachineOperand.h" 23 #include "llvm/CodeGen/MachineRegisterInfo.h" 24 #include "llvm/CodeGen/TargetRegisterInfo.h" 25 #include "llvm/CodeGen/TargetSchedule.h" 26 #include "llvm/CodeGen/TargetSubtargetInfo.h" 27 #include "llvm/InitializePasses.h" 28 #include "llvm/MC/MCRegisterInfo.h" 29 #include "llvm/Pass.h" 30 #include "llvm/Support/Debug.h" 31 #include "llvm/Support/ErrorHandling.h" 32 #include "llvm/Support/Format.h" 33 #include "llvm/Support/raw_ostream.h" 34 #include <algorithm> 35 #include <cassert> 36 #include <iterator> 37 #include <tuple> 38 #include <utility> 39 40 using namespace llvm; 41 42 #define DEBUG_TYPE "machine-trace-metrics" 43 44 char MachineTraceMetrics::ID = 0; 45 46 char &llvm::MachineTraceMetricsID = MachineTraceMetrics::ID; 47 48 INITIALIZE_PASS_BEGIN(MachineTraceMetrics, DEBUG_TYPE, 49 "Machine Trace Metrics", false, true) 50 INITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfo) 51 INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo) 52 INITIALIZE_PASS_END(MachineTraceMetrics, DEBUG_TYPE, 53 "Machine Trace Metrics", false, true) 54 55 MachineTraceMetrics::MachineTraceMetrics() : MachineFunctionPass(ID) { 56 std::fill(std::begin(Ensembles), std::end(Ensembles), nullptr); 57 } 58 59 void MachineTraceMetrics::getAnalysisUsage(AnalysisUsage &AU) const { 60 AU.setPreservesAll(); 61 AU.addRequired<MachineBranchProbabilityInfo>(); 62 AU.addRequired<MachineLoopInfo>(); 63 MachineFunctionPass::getAnalysisUsage(AU); 64 } 65 66 bool MachineTraceMetrics::runOnMachineFunction(MachineFunction &Func) { 67 MF = &Func; 68 const TargetSubtargetInfo &ST = MF->getSubtarget(); 69 TII = ST.getInstrInfo(); 70 TRI = ST.getRegisterInfo(); 71 MRI = &MF->getRegInfo(); 72 Loops = &getAnalysis<MachineLoopInfo>(); 73 SchedModel.init(&ST); 74 BlockInfo.resize(MF->getNumBlockIDs()); 75 ProcResourceCycles.resize(MF->getNumBlockIDs() * 76 SchedModel.getNumProcResourceKinds()); 77 return false; 78 } 79 80 void MachineTraceMetrics::releaseMemory() { 81 MF = nullptr; 82 BlockInfo.clear(); 83 for (Ensemble *&E : Ensembles) { 84 delete E; 85 E = nullptr; 86 } 87 } 88 89 //===----------------------------------------------------------------------===// 90 // Fixed block information 91 //===----------------------------------------------------------------------===// 92 // 93 // The number of instructions in a basic block and the CPU resources used by 94 // those instructions don't depend on any given trace strategy. 95 96 /// Compute the resource usage in basic block MBB. 97 const MachineTraceMetrics::FixedBlockInfo* 98 MachineTraceMetrics::getResources(const MachineBasicBlock *MBB) { 99 assert(MBB && "No basic block"); 100 FixedBlockInfo *FBI = &BlockInfo[MBB->getNumber()]; 101 if (FBI->hasResources()) 102 return FBI; 103 104 // Compute resource usage in the block. 105 FBI->HasCalls = false; 106 unsigned InstrCount = 0; 107 108 // Add up per-processor resource cycles as well. 109 unsigned PRKinds = SchedModel.getNumProcResourceKinds(); 110 SmallVector<unsigned, 32> PRCycles(PRKinds); 111 112 for (const auto &MI : *MBB) { 113 if (MI.isTransient()) 114 continue; 115 ++InstrCount; 116 if (MI.isCall()) 117 FBI->HasCalls = true; 118 119 // Count processor resources used. 120 if (!SchedModel.hasInstrSchedModel()) 121 continue; 122 const MCSchedClassDesc *SC = SchedModel.resolveSchedClass(&MI); 123 if (!SC->isValid()) 124 continue; 125 126 for (TargetSchedModel::ProcResIter 127 PI = SchedModel.getWriteProcResBegin(SC), 128 PE = SchedModel.getWriteProcResEnd(SC); PI != PE; ++PI) { 129 assert(PI->ProcResourceIdx < PRKinds && "Bad processor resource kind"); 130 PRCycles[PI->ProcResourceIdx] += PI->Cycles; 131 } 132 } 133 FBI->InstrCount = InstrCount; 134 135 // Scale the resource cycles so they are comparable. 136 unsigned PROffset = MBB->getNumber() * PRKinds; 137 for (unsigned K = 0; K != PRKinds; ++K) 138 ProcResourceCycles[PROffset + K] = 139 PRCycles[K] * SchedModel.getResourceFactor(K); 140 141 return FBI; 142 } 143 144 ArrayRef<unsigned> 145 MachineTraceMetrics::getProcResourceCycles(unsigned MBBNum) const { 146 assert(BlockInfo[MBBNum].hasResources() && 147 "getResources() must be called before getProcResourceCycles()"); 148 unsigned PRKinds = SchedModel.getNumProcResourceKinds(); 149 assert((MBBNum+1) * PRKinds <= ProcResourceCycles.size()); 150 return makeArrayRef(ProcResourceCycles.data() + MBBNum * PRKinds, PRKinds); 151 } 152 153 //===----------------------------------------------------------------------===// 154 // Ensemble utility functions 155 //===----------------------------------------------------------------------===// 156 157 MachineTraceMetrics::Ensemble::Ensemble(MachineTraceMetrics *ct) 158 : MTM(*ct) { 159 BlockInfo.resize(MTM.BlockInfo.size()); 160 unsigned PRKinds = MTM.SchedModel.getNumProcResourceKinds(); 161 ProcResourceDepths.resize(MTM.BlockInfo.size() * PRKinds); 162 ProcResourceHeights.resize(MTM.BlockInfo.size() * PRKinds); 163 } 164 165 // Virtual destructor serves as an anchor. 166 MachineTraceMetrics::Ensemble::~Ensemble() = default; 167 168 const MachineLoop* 169 MachineTraceMetrics::Ensemble::getLoopFor(const MachineBasicBlock *MBB) const { 170 return MTM.Loops->getLoopFor(MBB); 171 } 172 173 // Update resource-related information in the TraceBlockInfo for MBB. 174 // Only update resources related to the trace above MBB. 175 void MachineTraceMetrics::Ensemble:: 176 computeDepthResources(const MachineBasicBlock *MBB) { 177 TraceBlockInfo *TBI = &BlockInfo[MBB->getNumber()]; 178 unsigned PRKinds = MTM.SchedModel.getNumProcResourceKinds(); 179 unsigned PROffset = MBB->getNumber() * PRKinds; 180 181 // Compute resources from trace above. The top block is simple. 182 if (!TBI->Pred) { 183 TBI->InstrDepth = 0; 184 TBI->Head = MBB->getNumber(); 185 std::fill(ProcResourceDepths.begin() + PROffset, 186 ProcResourceDepths.begin() + PROffset + PRKinds, 0); 187 return; 188 } 189 190 // Compute from the block above. A post-order traversal ensures the 191 // predecessor is always computed first. 192 unsigned PredNum = TBI->Pred->getNumber(); 193 TraceBlockInfo *PredTBI = &BlockInfo[PredNum]; 194 assert(PredTBI->hasValidDepth() && "Trace above has not been computed yet"); 195 const FixedBlockInfo *PredFBI = MTM.getResources(TBI->Pred); 196 TBI->InstrDepth = PredTBI->InstrDepth + PredFBI->InstrCount; 197 TBI->Head = PredTBI->Head; 198 199 // Compute per-resource depths. 200 ArrayRef<unsigned> PredPRDepths = getProcResourceDepths(PredNum); 201 ArrayRef<unsigned> PredPRCycles = MTM.getProcResourceCycles(PredNum); 202 for (unsigned K = 0; K != PRKinds; ++K) 203 ProcResourceDepths[PROffset + K] = PredPRDepths[K] + PredPRCycles[K]; 204 } 205 206 // Update resource-related information in the TraceBlockInfo for MBB. 207 // Only update resources related to the trace below MBB. 208 void MachineTraceMetrics::Ensemble:: 209 computeHeightResources(const MachineBasicBlock *MBB) { 210 TraceBlockInfo *TBI = &BlockInfo[MBB->getNumber()]; 211 unsigned PRKinds = MTM.SchedModel.getNumProcResourceKinds(); 212 unsigned PROffset = MBB->getNumber() * PRKinds; 213 214 // Compute resources for the current block. 215 TBI->InstrHeight = MTM.getResources(MBB)->InstrCount; 216 ArrayRef<unsigned> PRCycles = MTM.getProcResourceCycles(MBB->getNumber()); 217 218 // The trace tail is done. 219 if (!TBI->Succ) { 220 TBI->Tail = MBB->getNumber(); 221 llvm::copy(PRCycles, ProcResourceHeights.begin() + PROffset); 222 return; 223 } 224 225 // Compute from the block below. A post-order traversal ensures the 226 // predecessor is always computed first. 227 unsigned SuccNum = TBI->Succ->getNumber(); 228 TraceBlockInfo *SuccTBI = &BlockInfo[SuccNum]; 229 assert(SuccTBI->hasValidHeight() && "Trace below has not been computed yet"); 230 TBI->InstrHeight += SuccTBI->InstrHeight; 231 TBI->Tail = SuccTBI->Tail; 232 233 // Compute per-resource heights. 234 ArrayRef<unsigned> SuccPRHeights = getProcResourceHeights(SuccNum); 235 for (unsigned K = 0; K != PRKinds; ++K) 236 ProcResourceHeights[PROffset + K] = SuccPRHeights[K] + PRCycles[K]; 237 } 238 239 // Check if depth resources for MBB are valid and return the TBI. 240 // Return NULL if the resources have been invalidated. 241 const MachineTraceMetrics::TraceBlockInfo* 242 MachineTraceMetrics::Ensemble:: 243 getDepthResources(const MachineBasicBlock *MBB) const { 244 const TraceBlockInfo *TBI = &BlockInfo[MBB->getNumber()]; 245 return TBI->hasValidDepth() ? TBI : nullptr; 246 } 247 248 // Check if height resources for MBB are valid and return the TBI. 249 // Return NULL if the resources have been invalidated. 250 const MachineTraceMetrics::TraceBlockInfo* 251 MachineTraceMetrics::Ensemble:: 252 getHeightResources(const MachineBasicBlock *MBB) const { 253 const TraceBlockInfo *TBI = &BlockInfo[MBB->getNumber()]; 254 return TBI->hasValidHeight() ? TBI : nullptr; 255 } 256 257 /// Get an array of processor resource depths for MBB. Indexed by processor 258 /// resource kind, this array contains the scaled processor resources consumed 259 /// by all blocks preceding MBB in its trace. It does not include instructions 260 /// in MBB. 261 /// 262 /// Compare TraceBlockInfo::InstrDepth. 263 ArrayRef<unsigned> 264 MachineTraceMetrics::Ensemble:: 265 getProcResourceDepths(unsigned MBBNum) const { 266 unsigned PRKinds = MTM.SchedModel.getNumProcResourceKinds(); 267 assert((MBBNum+1) * PRKinds <= ProcResourceDepths.size()); 268 return makeArrayRef(ProcResourceDepths.data() + MBBNum * PRKinds, PRKinds); 269 } 270 271 /// Get an array of processor resource heights for MBB. Indexed by processor 272 /// resource kind, this array contains the scaled processor resources consumed 273 /// by this block and all blocks following it in its trace. 274 /// 275 /// Compare TraceBlockInfo::InstrHeight. 276 ArrayRef<unsigned> 277 MachineTraceMetrics::Ensemble:: 278 getProcResourceHeights(unsigned MBBNum) const { 279 unsigned PRKinds = MTM.SchedModel.getNumProcResourceKinds(); 280 assert((MBBNum+1) * PRKinds <= ProcResourceHeights.size()); 281 return makeArrayRef(ProcResourceHeights.data() + MBBNum * PRKinds, PRKinds); 282 } 283 284 //===----------------------------------------------------------------------===// 285 // Trace Selection Strategies 286 //===----------------------------------------------------------------------===// 287 // 288 // A trace selection strategy is implemented as a sub-class of Ensemble. The 289 // trace through a block B is computed by two DFS traversals of the CFG 290 // starting from B. One upwards, and one downwards. During the upwards DFS, 291 // pickTracePred() is called on the post-ordered blocks. During the downwards 292 // DFS, pickTraceSucc() is called in a post-order. 293 // 294 295 // We never allow traces that leave loops, but we do allow traces to enter 296 // nested loops. We also never allow traces to contain back-edges. 297 // 298 // This means that a loop header can never appear above the center block of a 299 // trace, except as the trace head. Below the center block, loop exiting edges 300 // are banned. 301 // 302 // Return true if an edge from the From loop to the To loop is leaving a loop. 303 // Either of To and From can be null. 304 static bool isExitingLoop(const MachineLoop *From, const MachineLoop *To) { 305 return From && !From->contains(To); 306 } 307 308 // MinInstrCountEnsemble - Pick the trace that executes the least number of 309 // instructions. 310 namespace { 311 312 class MinInstrCountEnsemble : public MachineTraceMetrics::Ensemble { 313 const char *getName() const override { return "MinInstr"; } 314 const MachineBasicBlock *pickTracePred(const MachineBasicBlock*) override; 315 const MachineBasicBlock *pickTraceSucc(const MachineBasicBlock*) override; 316 317 public: 318 MinInstrCountEnsemble(MachineTraceMetrics *mtm) 319 : MachineTraceMetrics::Ensemble(mtm) {} 320 }; 321 322 } // end anonymous namespace 323 324 // Select the preferred predecessor for MBB. 325 const MachineBasicBlock* 326 MinInstrCountEnsemble::pickTracePred(const MachineBasicBlock *MBB) { 327 if (MBB->pred_empty()) 328 return nullptr; 329 const MachineLoop *CurLoop = getLoopFor(MBB); 330 // Don't leave loops, and never follow back-edges. 331 if (CurLoop && MBB == CurLoop->getHeader()) 332 return nullptr; 333 unsigned CurCount = MTM.getResources(MBB)->InstrCount; 334 const MachineBasicBlock *Best = nullptr; 335 unsigned BestDepth = 0; 336 for (const MachineBasicBlock *Pred : MBB->predecessors()) { 337 const MachineTraceMetrics::TraceBlockInfo *PredTBI = 338 getDepthResources(Pred); 339 // Ignore cycles that aren't natural loops. 340 if (!PredTBI) 341 continue; 342 // Pick the predecessor that would give this block the smallest InstrDepth. 343 unsigned Depth = PredTBI->InstrDepth + CurCount; 344 if (!Best || Depth < BestDepth) { 345 Best = Pred; 346 BestDepth = Depth; 347 } 348 } 349 return Best; 350 } 351 352 // Select the preferred successor for MBB. 353 const MachineBasicBlock* 354 MinInstrCountEnsemble::pickTraceSucc(const MachineBasicBlock *MBB) { 355 if (MBB->pred_empty()) 356 return nullptr; 357 const MachineLoop *CurLoop = getLoopFor(MBB); 358 const MachineBasicBlock *Best = nullptr; 359 unsigned BestHeight = 0; 360 for (const MachineBasicBlock *Succ : MBB->successors()) { 361 // Don't consider back-edges. 362 if (CurLoop && Succ == CurLoop->getHeader()) 363 continue; 364 // Don't consider successors exiting CurLoop. 365 if (isExitingLoop(CurLoop, getLoopFor(Succ))) 366 continue; 367 const MachineTraceMetrics::TraceBlockInfo *SuccTBI = 368 getHeightResources(Succ); 369 // Ignore cycles that aren't natural loops. 370 if (!SuccTBI) 371 continue; 372 // Pick the successor that would give this block the smallest InstrHeight. 373 unsigned Height = SuccTBI->InstrHeight; 374 if (!Best || Height < BestHeight) { 375 Best = Succ; 376 BestHeight = Height; 377 } 378 } 379 return Best; 380 } 381 382 // Get an Ensemble sub-class for the requested trace strategy. 383 MachineTraceMetrics::Ensemble * 384 MachineTraceMetrics::getEnsemble(MachineTraceMetrics::Strategy strategy) { 385 assert(strategy < TS_NumStrategies && "Invalid trace strategy enum"); 386 Ensemble *&E = Ensembles[strategy]; 387 if (E) 388 return E; 389 390 // Allocate new Ensemble on demand. 391 switch (strategy) { 392 case TS_MinInstrCount: return (E = new MinInstrCountEnsemble(this)); 393 default: llvm_unreachable("Invalid trace strategy enum"); 394 } 395 } 396 397 void MachineTraceMetrics::invalidate(const MachineBasicBlock *MBB) { 398 LLVM_DEBUG(dbgs() << "Invalidate traces through " << printMBBReference(*MBB) 399 << '\n'); 400 BlockInfo[MBB->getNumber()].invalidate(); 401 for (Ensemble *E : Ensembles) 402 if (E) 403 E->invalidate(MBB); 404 } 405 406 void MachineTraceMetrics::verifyAnalysis() const { 407 if (!MF) 408 return; 409 #ifndef NDEBUG 410 assert(BlockInfo.size() == MF->getNumBlockIDs() && "Outdated BlockInfo size"); 411 for (Ensemble *E : Ensembles) 412 if (E) 413 E->verify(); 414 #endif 415 } 416 417 //===----------------------------------------------------------------------===// 418 // Trace building 419 //===----------------------------------------------------------------------===// 420 // 421 // Traces are built by two CFG traversals. To avoid recomputing too much, use a 422 // set abstraction that confines the search to the current loop, and doesn't 423 // revisit blocks. 424 425 namespace { 426 427 struct LoopBounds { 428 MutableArrayRef<MachineTraceMetrics::TraceBlockInfo> Blocks; 429 SmallPtrSet<const MachineBasicBlock*, 8> Visited; 430 const MachineLoopInfo *Loops; 431 bool Downward = false; 432 433 LoopBounds(MutableArrayRef<MachineTraceMetrics::TraceBlockInfo> blocks, 434 const MachineLoopInfo *loops) : Blocks(blocks), Loops(loops) {} 435 }; 436 437 } // end anonymous namespace 438 439 // Specialize po_iterator_storage in order to prune the post-order traversal so 440 // it is limited to the current loop and doesn't traverse the loop back edges. 441 namespace llvm { 442 443 template<> 444 class po_iterator_storage<LoopBounds, true> { 445 LoopBounds &LB; 446 447 public: 448 po_iterator_storage(LoopBounds &lb) : LB(lb) {} 449 450 void finishPostorder(const MachineBasicBlock*) {} 451 452 bool insertEdge(Optional<const MachineBasicBlock *> From, 453 const MachineBasicBlock *To) { 454 // Skip already visited To blocks. 455 MachineTraceMetrics::TraceBlockInfo &TBI = LB.Blocks[To->getNumber()]; 456 if (LB.Downward ? TBI.hasValidHeight() : TBI.hasValidDepth()) 457 return false; 458 // From is null once when To is the trace center block. 459 if (From) { 460 if (const MachineLoop *FromLoop = LB.Loops->getLoopFor(*From)) { 461 // Don't follow backedges, don't leave FromLoop when going upwards. 462 if ((LB.Downward ? To : *From) == FromLoop->getHeader()) 463 return false; 464 // Don't leave FromLoop. 465 if (isExitingLoop(FromLoop, LB.Loops->getLoopFor(To))) 466 return false; 467 } 468 } 469 // To is a new block. Mark the block as visited in case the CFG has cycles 470 // that MachineLoopInfo didn't recognize as a natural loop. 471 return LB.Visited.insert(To).second; 472 } 473 }; 474 475 } // end namespace llvm 476 477 /// Compute the trace through MBB. 478 void MachineTraceMetrics::Ensemble::computeTrace(const MachineBasicBlock *MBB) { 479 LLVM_DEBUG(dbgs() << "Computing " << getName() << " trace through " 480 << printMBBReference(*MBB) << '\n'); 481 // Set up loop bounds for the backwards post-order traversal. 482 LoopBounds Bounds(BlockInfo, MTM.Loops); 483 484 // Run an upwards post-order search for the trace start. 485 Bounds.Downward = false; 486 Bounds.Visited.clear(); 487 for (const auto *I : inverse_post_order_ext(MBB, Bounds)) { 488 LLVM_DEBUG(dbgs() << " pred for " << printMBBReference(*I) << ": "); 489 TraceBlockInfo &TBI = BlockInfo[I->getNumber()]; 490 // All the predecessors have been visited, pick the preferred one. 491 TBI.Pred = pickTracePred(I); 492 LLVM_DEBUG({ 493 if (TBI.Pred) 494 dbgs() << printMBBReference(*TBI.Pred) << '\n'; 495 else 496 dbgs() << "null\n"; 497 }); 498 // The trace leading to I is now known, compute the depth resources. 499 computeDepthResources(I); 500 } 501 502 // Run a downwards post-order search for the trace end. 503 Bounds.Downward = true; 504 Bounds.Visited.clear(); 505 for (const auto *I : post_order_ext(MBB, Bounds)) { 506 LLVM_DEBUG(dbgs() << " succ for " << printMBBReference(*I) << ": "); 507 TraceBlockInfo &TBI = BlockInfo[I->getNumber()]; 508 // All the successors have been visited, pick the preferred one. 509 TBI.Succ = pickTraceSucc(I); 510 LLVM_DEBUG({ 511 if (TBI.Succ) 512 dbgs() << printMBBReference(*TBI.Succ) << '\n'; 513 else 514 dbgs() << "null\n"; 515 }); 516 // The trace leaving I is now known, compute the height resources. 517 computeHeightResources(I); 518 } 519 } 520 521 /// Invalidate traces through BadMBB. 522 void 523 MachineTraceMetrics::Ensemble::invalidate(const MachineBasicBlock *BadMBB) { 524 SmallVector<const MachineBasicBlock*, 16> WorkList; 525 TraceBlockInfo &BadTBI = BlockInfo[BadMBB->getNumber()]; 526 527 // Invalidate height resources of blocks above MBB. 528 if (BadTBI.hasValidHeight()) { 529 BadTBI.invalidateHeight(); 530 WorkList.push_back(BadMBB); 531 do { 532 const MachineBasicBlock *MBB = WorkList.pop_back_val(); 533 LLVM_DEBUG(dbgs() << "Invalidate " << printMBBReference(*MBB) << ' ' 534 << getName() << " height.\n"); 535 // Find any MBB predecessors that have MBB as their preferred successor. 536 // They are the only ones that need to be invalidated. 537 for (const MachineBasicBlock *Pred : MBB->predecessors()) { 538 TraceBlockInfo &TBI = BlockInfo[Pred->getNumber()]; 539 if (!TBI.hasValidHeight()) 540 continue; 541 if (TBI.Succ == MBB) { 542 TBI.invalidateHeight(); 543 WorkList.push_back(Pred); 544 continue; 545 } 546 // Verify that TBI.Succ is actually a *I successor. 547 assert((!TBI.Succ || Pred->isSuccessor(TBI.Succ)) && "CFG changed"); 548 } 549 } while (!WorkList.empty()); 550 } 551 552 // Invalidate depth resources of blocks below MBB. 553 if (BadTBI.hasValidDepth()) { 554 BadTBI.invalidateDepth(); 555 WorkList.push_back(BadMBB); 556 do { 557 const MachineBasicBlock *MBB = WorkList.pop_back_val(); 558 LLVM_DEBUG(dbgs() << "Invalidate " << printMBBReference(*MBB) << ' ' 559 << getName() << " depth.\n"); 560 // Find any MBB successors that have MBB as their preferred predecessor. 561 // They are the only ones that need to be invalidated. 562 for (const MachineBasicBlock *Succ : MBB->successors()) { 563 TraceBlockInfo &TBI = BlockInfo[Succ->getNumber()]; 564 if (!TBI.hasValidDepth()) 565 continue; 566 if (TBI.Pred == MBB) { 567 TBI.invalidateDepth(); 568 WorkList.push_back(Succ); 569 continue; 570 } 571 // Verify that TBI.Pred is actually a *I predecessor. 572 assert((!TBI.Pred || Succ->isPredecessor(TBI.Pred)) && "CFG changed"); 573 } 574 } while (!WorkList.empty()); 575 } 576 577 // Clear any per-instruction data. We only have to do this for BadMBB itself 578 // because the instructions in that block may change. Other blocks may be 579 // invalidated, but their instructions will stay the same, so there is no 580 // need to erase the Cycle entries. They will be overwritten when we 581 // recompute. 582 for (const auto &I : *BadMBB) 583 Cycles.erase(&I); 584 } 585 586 void MachineTraceMetrics::Ensemble::verify() const { 587 #ifndef NDEBUG 588 assert(BlockInfo.size() == MTM.MF->getNumBlockIDs() && 589 "Outdated BlockInfo size"); 590 for (unsigned Num = 0, e = BlockInfo.size(); Num != e; ++Num) { 591 const TraceBlockInfo &TBI = BlockInfo[Num]; 592 if (TBI.hasValidDepth() && TBI.Pred) { 593 const MachineBasicBlock *MBB = MTM.MF->getBlockNumbered(Num); 594 assert(MBB->isPredecessor(TBI.Pred) && "CFG doesn't match trace"); 595 assert(BlockInfo[TBI.Pred->getNumber()].hasValidDepth() && 596 "Trace is broken, depth should have been invalidated."); 597 const MachineLoop *Loop = getLoopFor(MBB); 598 assert(!(Loop && MBB == Loop->getHeader()) && "Trace contains backedge"); 599 } 600 if (TBI.hasValidHeight() && TBI.Succ) { 601 const MachineBasicBlock *MBB = MTM.MF->getBlockNumbered(Num); 602 assert(MBB->isSuccessor(TBI.Succ) && "CFG doesn't match trace"); 603 assert(BlockInfo[TBI.Succ->getNumber()].hasValidHeight() && 604 "Trace is broken, height should have been invalidated."); 605 const MachineLoop *Loop = getLoopFor(MBB); 606 const MachineLoop *SuccLoop = getLoopFor(TBI.Succ); 607 assert(!(Loop && Loop == SuccLoop && TBI.Succ == Loop->getHeader()) && 608 "Trace contains backedge"); 609 } 610 } 611 #endif 612 } 613 614 //===----------------------------------------------------------------------===// 615 // Data Dependencies 616 //===----------------------------------------------------------------------===// 617 // 618 // Compute the depth and height of each instruction based on data dependencies 619 // and instruction latencies. These cycle numbers assume that the CPU can issue 620 // an infinite number of instructions per cycle as long as their dependencies 621 // are ready. 622 623 // A data dependency is represented as a defining MI and operand numbers on the 624 // defining and using MI. 625 namespace { 626 627 struct DataDep { 628 const MachineInstr *DefMI; 629 unsigned DefOp; 630 unsigned UseOp; 631 632 DataDep(const MachineInstr *DefMI, unsigned DefOp, unsigned UseOp) 633 : DefMI(DefMI), DefOp(DefOp), UseOp(UseOp) {} 634 635 /// Create a DataDep from an SSA form virtual register. 636 DataDep(const MachineRegisterInfo *MRI, unsigned VirtReg, unsigned UseOp) 637 : UseOp(UseOp) { 638 assert(Register::isVirtualRegister(VirtReg)); 639 MachineRegisterInfo::def_iterator DefI = MRI->def_begin(VirtReg); 640 assert(!DefI.atEnd() && "Register has no defs"); 641 DefMI = DefI->getParent(); 642 DefOp = DefI.getOperandNo(); 643 assert((++DefI).atEnd() && "Register has multiple defs"); 644 } 645 }; 646 647 } // end anonymous namespace 648 649 // Get the input data dependencies that must be ready before UseMI can issue. 650 // Return true if UseMI has any physreg operands. 651 static bool getDataDeps(const MachineInstr &UseMI, 652 SmallVectorImpl<DataDep> &Deps, 653 const MachineRegisterInfo *MRI) { 654 // Debug values should not be included in any calculations. 655 if (UseMI.isDebugInstr()) 656 return false; 657 658 bool HasPhysRegs = false; 659 for (MachineInstr::const_mop_iterator I = UseMI.operands_begin(), 660 E = UseMI.operands_end(); I != E; ++I) { 661 const MachineOperand &MO = *I; 662 if (!MO.isReg()) 663 continue; 664 Register Reg = MO.getReg(); 665 if (!Reg) 666 continue; 667 if (Register::isPhysicalRegister(Reg)) { 668 HasPhysRegs = true; 669 continue; 670 } 671 // Collect virtual register reads. 672 if (MO.readsReg()) 673 Deps.push_back(DataDep(MRI, Reg, UseMI.getOperandNo(I))); 674 } 675 return HasPhysRegs; 676 } 677 678 // Get the input data dependencies of a PHI instruction, using Pred as the 679 // preferred predecessor. 680 // This will add at most one dependency to Deps. 681 static void getPHIDeps(const MachineInstr &UseMI, 682 SmallVectorImpl<DataDep> &Deps, 683 const MachineBasicBlock *Pred, 684 const MachineRegisterInfo *MRI) { 685 // No predecessor at the beginning of a trace. Ignore dependencies. 686 if (!Pred) 687 return; 688 assert(UseMI.isPHI() && UseMI.getNumOperands() % 2 && "Bad PHI"); 689 for (unsigned i = 1; i != UseMI.getNumOperands(); i += 2) { 690 if (UseMI.getOperand(i + 1).getMBB() == Pred) { 691 Register Reg = UseMI.getOperand(i).getReg(); 692 Deps.push_back(DataDep(MRI, Reg, i)); 693 return; 694 } 695 } 696 } 697 698 // Identify physreg dependencies for UseMI, and update the live regunit 699 // tracking set when scanning instructions downwards. 700 static void updatePhysDepsDownwards(const MachineInstr *UseMI, 701 SmallVectorImpl<DataDep> &Deps, 702 SparseSet<LiveRegUnit> &RegUnits, 703 const TargetRegisterInfo *TRI) { 704 SmallVector<MCRegister, 8> Kills; 705 SmallVector<unsigned, 8> LiveDefOps; 706 707 for (MachineInstr::const_mop_iterator MI = UseMI->operands_begin(), 708 ME = UseMI->operands_end(); MI != ME; ++MI) { 709 const MachineOperand &MO = *MI; 710 if (!MO.isReg() || !MO.getReg().isPhysical()) 711 continue; 712 MCRegister Reg = MO.getReg().asMCReg(); 713 // Track live defs and kills for updating RegUnits. 714 if (MO.isDef()) { 715 if (MO.isDead()) 716 Kills.push_back(Reg); 717 else 718 LiveDefOps.push_back(UseMI->getOperandNo(MI)); 719 } else if (MO.isKill()) 720 Kills.push_back(Reg); 721 // Identify dependencies. 722 if (!MO.readsReg()) 723 continue; 724 for (MCRegUnitIterator Units(Reg, TRI); Units.isValid(); ++Units) { 725 SparseSet<LiveRegUnit>::iterator I = RegUnits.find(*Units); 726 if (I == RegUnits.end()) 727 continue; 728 Deps.push_back(DataDep(I->MI, I->Op, UseMI->getOperandNo(MI))); 729 break; 730 } 731 } 732 733 // Update RegUnits to reflect live registers after UseMI. 734 // First kills. 735 for (MCRegister Kill : Kills) 736 for (MCRegUnitIterator Units(Kill, TRI); Units.isValid(); ++Units) 737 RegUnits.erase(*Units); 738 739 // Second, live defs. 740 for (unsigned DefOp : LiveDefOps) { 741 for (MCRegUnitIterator Units(UseMI->getOperand(DefOp).getReg().asMCReg(), 742 TRI); 743 Units.isValid(); ++Units) { 744 LiveRegUnit &LRU = RegUnits[*Units]; 745 LRU.MI = UseMI; 746 LRU.Op = DefOp; 747 } 748 } 749 } 750 751 /// The length of the critical path through a trace is the maximum of two path 752 /// lengths: 753 /// 754 /// 1. The maximum height+depth over all instructions in the trace center block. 755 /// 756 /// 2. The longest cross-block dependency chain. For small blocks, it is 757 /// possible that the critical path through the trace doesn't include any 758 /// instructions in the block. 759 /// 760 /// This function computes the second number from the live-in list of the 761 /// center block. 762 unsigned MachineTraceMetrics::Ensemble:: 763 computeCrossBlockCriticalPath(const TraceBlockInfo &TBI) { 764 assert(TBI.HasValidInstrDepths && "Missing depth info"); 765 assert(TBI.HasValidInstrHeights && "Missing height info"); 766 unsigned MaxLen = 0; 767 for (const LiveInReg &LIR : TBI.LiveIns) { 768 if (!LIR.Reg.isVirtual()) 769 continue; 770 const MachineInstr *DefMI = MTM.MRI->getVRegDef(LIR.Reg); 771 // Ignore dependencies outside the current trace. 772 const TraceBlockInfo &DefTBI = BlockInfo[DefMI->getParent()->getNumber()]; 773 if (!DefTBI.isUsefulDominator(TBI)) 774 continue; 775 unsigned Len = LIR.Height + Cycles[DefMI].Depth; 776 MaxLen = std::max(MaxLen, Len); 777 } 778 return MaxLen; 779 } 780 781 void MachineTraceMetrics::Ensemble:: 782 updateDepth(MachineTraceMetrics::TraceBlockInfo &TBI, const MachineInstr &UseMI, 783 SparseSet<LiveRegUnit> &RegUnits) { 784 SmallVector<DataDep, 8> Deps; 785 // Collect all data dependencies. 786 if (UseMI.isPHI()) 787 getPHIDeps(UseMI, Deps, TBI.Pred, MTM.MRI); 788 else if (getDataDeps(UseMI, Deps, MTM.MRI)) 789 updatePhysDepsDownwards(&UseMI, Deps, RegUnits, MTM.TRI); 790 791 // Filter and process dependencies, computing the earliest issue cycle. 792 unsigned Cycle = 0; 793 for (const DataDep &Dep : Deps) { 794 const TraceBlockInfo&DepTBI = 795 BlockInfo[Dep.DefMI->getParent()->getNumber()]; 796 // Ignore dependencies from outside the current trace. 797 if (!DepTBI.isUsefulDominator(TBI)) 798 continue; 799 assert(DepTBI.HasValidInstrDepths && "Inconsistent dependency"); 800 unsigned DepCycle = Cycles.lookup(Dep.DefMI).Depth; 801 // Add latency if DefMI is a real instruction. Transients get latency 0. 802 if (!Dep.DefMI->isTransient()) 803 DepCycle += MTM.SchedModel 804 .computeOperandLatency(Dep.DefMI, Dep.DefOp, &UseMI, Dep.UseOp); 805 Cycle = std::max(Cycle, DepCycle); 806 } 807 // Remember the instruction depth. 808 InstrCycles &MICycles = Cycles[&UseMI]; 809 MICycles.Depth = Cycle; 810 811 if (TBI.HasValidInstrHeights) { 812 // Update critical path length. 813 TBI.CriticalPath = std::max(TBI.CriticalPath, Cycle + MICycles.Height); 814 LLVM_DEBUG(dbgs() << TBI.CriticalPath << '\t' << Cycle << '\t' << UseMI); 815 } else { 816 LLVM_DEBUG(dbgs() << Cycle << '\t' << UseMI); 817 } 818 } 819 820 void MachineTraceMetrics::Ensemble:: 821 updateDepth(const MachineBasicBlock *MBB, const MachineInstr &UseMI, 822 SparseSet<LiveRegUnit> &RegUnits) { 823 updateDepth(BlockInfo[MBB->getNumber()], UseMI, RegUnits); 824 } 825 826 void MachineTraceMetrics::Ensemble:: 827 updateDepths(MachineBasicBlock::iterator Start, 828 MachineBasicBlock::iterator End, 829 SparseSet<LiveRegUnit> &RegUnits) { 830 for (; Start != End; Start++) 831 updateDepth(Start->getParent(), *Start, RegUnits); 832 } 833 834 /// Compute instruction depths for all instructions above or in MBB in its 835 /// trace. This assumes that the trace through MBB has already been computed. 836 void MachineTraceMetrics::Ensemble:: 837 computeInstrDepths(const MachineBasicBlock *MBB) { 838 // The top of the trace may already be computed, and HasValidInstrDepths 839 // implies Head->HasValidInstrDepths, so we only need to start from the first 840 // block in the trace that needs to be recomputed. 841 SmallVector<const MachineBasicBlock*, 8> Stack; 842 do { 843 TraceBlockInfo &TBI = BlockInfo[MBB->getNumber()]; 844 assert(TBI.hasValidDepth() && "Incomplete trace"); 845 if (TBI.HasValidInstrDepths) 846 break; 847 Stack.push_back(MBB); 848 MBB = TBI.Pred; 849 } while (MBB); 850 851 // FIXME: If MBB is non-null at this point, it is the last pre-computed block 852 // in the trace. We should track any live-out physregs that were defined in 853 // the trace. This is quite rare in SSA form, typically created by CSE 854 // hoisting a compare. 855 SparseSet<LiveRegUnit> RegUnits; 856 RegUnits.setUniverse(MTM.TRI->getNumRegUnits()); 857 858 // Go through trace blocks in top-down order, stopping after the center block. 859 while (!Stack.empty()) { 860 MBB = Stack.pop_back_val(); 861 LLVM_DEBUG(dbgs() << "\nDepths for " << printMBBReference(*MBB) << ":\n"); 862 TraceBlockInfo &TBI = BlockInfo[MBB->getNumber()]; 863 TBI.HasValidInstrDepths = true; 864 TBI.CriticalPath = 0; 865 866 // Print out resource depths here as well. 867 LLVM_DEBUG({ 868 dbgs() << format("%7u Instructions\n", TBI.InstrDepth); 869 ArrayRef<unsigned> PRDepths = getProcResourceDepths(MBB->getNumber()); 870 for (unsigned K = 0; K != PRDepths.size(); ++K) 871 if (PRDepths[K]) { 872 unsigned Factor = MTM.SchedModel.getResourceFactor(K); 873 dbgs() << format("%6uc @ ", MTM.getCycles(PRDepths[K])) 874 << MTM.SchedModel.getProcResource(K)->Name << " (" 875 << PRDepths[K]/Factor << " ops x" << Factor << ")\n"; 876 } 877 }); 878 879 // Also compute the critical path length through MBB when possible. 880 if (TBI.HasValidInstrHeights) 881 TBI.CriticalPath = computeCrossBlockCriticalPath(TBI); 882 883 for (const auto &UseMI : *MBB) { 884 updateDepth(TBI, UseMI, RegUnits); 885 } 886 } 887 } 888 889 // Identify physreg dependencies for MI when scanning instructions upwards. 890 // Return the issue height of MI after considering any live regunits. 891 // Height is the issue height computed from virtual register dependencies alone. 892 static unsigned updatePhysDepsUpwards(const MachineInstr &MI, unsigned Height, 893 SparseSet<LiveRegUnit> &RegUnits, 894 const TargetSchedModel &SchedModel, 895 const TargetInstrInfo *TII, 896 const TargetRegisterInfo *TRI) { 897 SmallVector<unsigned, 8> ReadOps; 898 899 for (MachineInstr::const_mop_iterator MOI = MI.operands_begin(), 900 MOE = MI.operands_end(); 901 MOI != MOE; ++MOI) { 902 const MachineOperand &MO = *MOI; 903 if (!MO.isReg()) 904 continue; 905 Register Reg = MO.getReg(); 906 if (!Register::isPhysicalRegister(Reg)) 907 continue; 908 if (MO.readsReg()) 909 ReadOps.push_back(MI.getOperandNo(MOI)); 910 if (!MO.isDef()) 911 continue; 912 // This is a def of Reg. Remove corresponding entries from RegUnits, and 913 // update MI Height to consider the physreg dependencies. 914 for (MCRegUnitIterator Units(Reg.asMCReg(), TRI); Units.isValid(); 915 ++Units) { 916 SparseSet<LiveRegUnit>::iterator I = RegUnits.find(*Units); 917 if (I == RegUnits.end()) 918 continue; 919 unsigned DepHeight = I->Cycle; 920 if (!MI.isTransient()) { 921 // We may not know the UseMI of this dependency, if it came from the 922 // live-in list. SchedModel can handle a NULL UseMI. 923 DepHeight += SchedModel.computeOperandLatency(&MI, MI.getOperandNo(MOI), 924 I->MI, I->Op); 925 } 926 Height = std::max(Height, DepHeight); 927 // This regunit is dead above MI. 928 RegUnits.erase(I); 929 } 930 } 931 932 // Now we know the height of MI. Update any regunits read. 933 for (size_t I = 0, E = ReadOps.size(); I != E; ++I) { 934 MCRegister Reg = MI.getOperand(ReadOps[I]).getReg().asMCReg(); 935 for (MCRegUnitIterator Units(Reg, TRI); Units.isValid(); ++Units) { 936 LiveRegUnit &LRU = RegUnits[*Units]; 937 // Set the height to the highest reader of the unit. 938 if (LRU.Cycle <= Height && LRU.MI != &MI) { 939 LRU.Cycle = Height; 940 LRU.MI = &MI; 941 LRU.Op = ReadOps[I]; 942 } 943 } 944 } 945 946 return Height; 947 } 948 949 using MIHeightMap = DenseMap<const MachineInstr *, unsigned>; 950 951 // Push the height of DefMI upwards if required to match UseMI. 952 // Return true if this is the first time DefMI was seen. 953 static bool pushDepHeight(const DataDep &Dep, const MachineInstr &UseMI, 954 unsigned UseHeight, MIHeightMap &Heights, 955 const TargetSchedModel &SchedModel, 956 const TargetInstrInfo *TII) { 957 // Adjust height by Dep.DefMI latency. 958 if (!Dep.DefMI->isTransient()) 959 UseHeight += SchedModel.computeOperandLatency(Dep.DefMI, Dep.DefOp, &UseMI, 960 Dep.UseOp); 961 962 // Update Heights[DefMI] to be the maximum height seen. 963 MIHeightMap::iterator I; 964 bool New; 965 std::tie(I, New) = Heights.insert(std::make_pair(Dep.DefMI, UseHeight)); 966 if (New) 967 return true; 968 969 // DefMI has been pushed before. Give it the max height. 970 if (I->second < UseHeight) 971 I->second = UseHeight; 972 return false; 973 } 974 975 /// Assuming that the virtual register defined by DefMI:DefOp was used by 976 /// Trace.back(), add it to the live-in lists of all the blocks in Trace. Stop 977 /// when reaching the block that contains DefMI. 978 void MachineTraceMetrics::Ensemble:: 979 addLiveIns(const MachineInstr *DefMI, unsigned DefOp, 980 ArrayRef<const MachineBasicBlock*> Trace) { 981 assert(!Trace.empty() && "Trace should contain at least one block"); 982 Register Reg = DefMI->getOperand(DefOp).getReg(); 983 assert(Register::isVirtualRegister(Reg)); 984 const MachineBasicBlock *DefMBB = DefMI->getParent(); 985 986 // Reg is live-in to all blocks in Trace that follow DefMBB. 987 for (const MachineBasicBlock *MBB : llvm::reverse(Trace)) { 988 if (MBB == DefMBB) 989 return; 990 TraceBlockInfo &TBI = BlockInfo[MBB->getNumber()]; 991 // Just add the register. The height will be updated later. 992 TBI.LiveIns.push_back(Reg); 993 } 994 } 995 996 /// Compute instruction heights in the trace through MBB. This updates MBB and 997 /// the blocks below it in the trace. It is assumed that the trace has already 998 /// been computed. 999 void MachineTraceMetrics::Ensemble:: 1000 computeInstrHeights(const MachineBasicBlock *MBB) { 1001 // The bottom of the trace may already be computed. 1002 // Find the blocks that need updating. 1003 SmallVector<const MachineBasicBlock*, 8> Stack; 1004 do { 1005 TraceBlockInfo &TBI = BlockInfo[MBB->getNumber()]; 1006 assert(TBI.hasValidHeight() && "Incomplete trace"); 1007 if (TBI.HasValidInstrHeights) 1008 break; 1009 Stack.push_back(MBB); 1010 TBI.LiveIns.clear(); 1011 MBB = TBI.Succ; 1012 } while (MBB); 1013 1014 // As we move upwards in the trace, keep track of instructions that are 1015 // required by deeper trace instructions. Map MI -> height required so far. 1016 MIHeightMap Heights; 1017 1018 // For physregs, the def isn't known when we see the use. 1019 // Instead, keep track of the highest use of each regunit. 1020 SparseSet<LiveRegUnit> RegUnits; 1021 RegUnits.setUniverse(MTM.TRI->getNumRegUnits()); 1022 1023 // If the bottom of the trace was already precomputed, initialize heights 1024 // from its live-in list. 1025 // MBB is the highest precomputed block in the trace. 1026 if (MBB) { 1027 TraceBlockInfo &TBI = BlockInfo[MBB->getNumber()]; 1028 for (LiveInReg &LI : TBI.LiveIns) { 1029 if (LI.Reg.isVirtual()) { 1030 // For virtual registers, the def latency is included. 1031 unsigned &Height = Heights[MTM.MRI->getVRegDef(LI.Reg)]; 1032 if (Height < LI.Height) 1033 Height = LI.Height; 1034 } else { 1035 // For register units, the def latency is not included because we don't 1036 // know the def yet. 1037 RegUnits[LI.Reg].Cycle = LI.Height; 1038 } 1039 } 1040 } 1041 1042 // Go through the trace blocks in bottom-up order. 1043 SmallVector<DataDep, 8> Deps; 1044 for (;!Stack.empty(); Stack.pop_back()) { 1045 MBB = Stack.back(); 1046 LLVM_DEBUG(dbgs() << "Heights for " << printMBBReference(*MBB) << ":\n"); 1047 TraceBlockInfo &TBI = BlockInfo[MBB->getNumber()]; 1048 TBI.HasValidInstrHeights = true; 1049 TBI.CriticalPath = 0; 1050 1051 LLVM_DEBUG({ 1052 dbgs() << format("%7u Instructions\n", TBI.InstrHeight); 1053 ArrayRef<unsigned> PRHeights = getProcResourceHeights(MBB->getNumber()); 1054 for (unsigned K = 0; K != PRHeights.size(); ++K) 1055 if (PRHeights[K]) { 1056 unsigned Factor = MTM.SchedModel.getResourceFactor(K); 1057 dbgs() << format("%6uc @ ", MTM.getCycles(PRHeights[K])) 1058 << MTM.SchedModel.getProcResource(K)->Name << " (" 1059 << PRHeights[K]/Factor << " ops x" << Factor << ")\n"; 1060 } 1061 }); 1062 1063 // Get dependencies from PHIs in the trace successor. 1064 const MachineBasicBlock *Succ = TBI.Succ; 1065 // If MBB is the last block in the trace, and it has a back-edge to the 1066 // loop header, get loop-carried dependencies from PHIs in the header. For 1067 // that purpose, pretend that all the loop header PHIs have height 0. 1068 if (!Succ) 1069 if (const MachineLoop *Loop = getLoopFor(MBB)) 1070 if (MBB->isSuccessor(Loop->getHeader())) 1071 Succ = Loop->getHeader(); 1072 1073 if (Succ) { 1074 for (const auto &PHI : *Succ) { 1075 if (!PHI.isPHI()) 1076 break; 1077 Deps.clear(); 1078 getPHIDeps(PHI, Deps, MBB, MTM.MRI); 1079 if (!Deps.empty()) { 1080 // Loop header PHI heights are all 0. 1081 unsigned Height = TBI.Succ ? Cycles.lookup(&PHI).Height : 0; 1082 LLVM_DEBUG(dbgs() << "pred\t" << Height << '\t' << PHI); 1083 if (pushDepHeight(Deps.front(), PHI, Height, Heights, MTM.SchedModel, 1084 MTM.TII)) 1085 addLiveIns(Deps.front().DefMI, Deps.front().DefOp, Stack); 1086 } 1087 } 1088 } 1089 1090 // Go through the block backwards. 1091 for (MachineBasicBlock::const_iterator BI = MBB->end(), BB = MBB->begin(); 1092 BI != BB;) { 1093 const MachineInstr &MI = *--BI; 1094 1095 // Find the MI height as determined by virtual register uses in the 1096 // trace below. 1097 unsigned Cycle = 0; 1098 MIHeightMap::iterator HeightI = Heights.find(&MI); 1099 if (HeightI != Heights.end()) { 1100 Cycle = HeightI->second; 1101 // We won't be seeing any more MI uses. 1102 Heights.erase(HeightI); 1103 } 1104 1105 // Don't process PHI deps. They depend on the specific predecessor, and 1106 // we'll get them when visiting the predecessor. 1107 Deps.clear(); 1108 bool HasPhysRegs = !MI.isPHI() && getDataDeps(MI, Deps, MTM.MRI); 1109 1110 // There may also be regunit dependencies to include in the height. 1111 if (HasPhysRegs) 1112 Cycle = updatePhysDepsUpwards(MI, Cycle, RegUnits, MTM.SchedModel, 1113 MTM.TII, MTM.TRI); 1114 1115 // Update the required height of any virtual registers read by MI. 1116 for (const DataDep &Dep : Deps) 1117 if (pushDepHeight(Dep, MI, Cycle, Heights, MTM.SchedModel, MTM.TII)) 1118 addLiveIns(Dep.DefMI, Dep.DefOp, Stack); 1119 1120 InstrCycles &MICycles = Cycles[&MI]; 1121 MICycles.Height = Cycle; 1122 if (!TBI.HasValidInstrDepths) { 1123 LLVM_DEBUG(dbgs() << Cycle << '\t' << MI); 1124 continue; 1125 } 1126 // Update critical path length. 1127 TBI.CriticalPath = std::max(TBI.CriticalPath, Cycle + MICycles.Depth); 1128 LLVM_DEBUG(dbgs() << TBI.CriticalPath << '\t' << Cycle << '\t' << MI); 1129 } 1130 1131 // Update virtual live-in heights. They were added by addLiveIns() with a 0 1132 // height because the final height isn't known until now. 1133 LLVM_DEBUG(dbgs() << printMBBReference(*MBB) << " Live-ins:"); 1134 for (LiveInReg &LIR : TBI.LiveIns) { 1135 const MachineInstr *DefMI = MTM.MRI->getVRegDef(LIR.Reg); 1136 LIR.Height = Heights.lookup(DefMI); 1137 LLVM_DEBUG(dbgs() << ' ' << printReg(LIR.Reg) << '@' << LIR.Height); 1138 } 1139 1140 // Transfer the live regunits to the live-in list. 1141 for (SparseSet<LiveRegUnit>::const_iterator 1142 RI = RegUnits.begin(), RE = RegUnits.end(); RI != RE; ++RI) { 1143 TBI.LiveIns.push_back(LiveInReg(RI->RegUnit, RI->Cycle)); 1144 LLVM_DEBUG(dbgs() << ' ' << printRegUnit(RI->RegUnit, MTM.TRI) << '@' 1145 << RI->Cycle); 1146 } 1147 LLVM_DEBUG(dbgs() << '\n'); 1148 1149 if (!TBI.HasValidInstrDepths) 1150 continue; 1151 // Add live-ins to the critical path length. 1152 TBI.CriticalPath = std::max(TBI.CriticalPath, 1153 computeCrossBlockCriticalPath(TBI)); 1154 LLVM_DEBUG(dbgs() << "Critical path: " << TBI.CriticalPath << '\n'); 1155 } 1156 } 1157 1158 MachineTraceMetrics::Trace 1159 MachineTraceMetrics::Ensemble::getTrace(const MachineBasicBlock *MBB) { 1160 TraceBlockInfo &TBI = BlockInfo[MBB->getNumber()]; 1161 1162 if (!TBI.hasValidDepth() || !TBI.hasValidHeight()) 1163 computeTrace(MBB); 1164 if (!TBI.HasValidInstrDepths) 1165 computeInstrDepths(MBB); 1166 if (!TBI.HasValidInstrHeights) 1167 computeInstrHeights(MBB); 1168 1169 return Trace(*this, TBI); 1170 } 1171 1172 unsigned 1173 MachineTraceMetrics::Trace::getInstrSlack(const MachineInstr &MI) const { 1174 assert(getBlockNum() == unsigned(MI.getParent()->getNumber()) && 1175 "MI must be in the trace center block"); 1176 InstrCycles Cyc = getInstrCycles(MI); 1177 return getCriticalPath() - (Cyc.Depth + Cyc.Height); 1178 } 1179 1180 unsigned 1181 MachineTraceMetrics::Trace::getPHIDepth(const MachineInstr &PHI) const { 1182 const MachineBasicBlock *MBB = TE.MTM.MF->getBlockNumbered(getBlockNum()); 1183 SmallVector<DataDep, 1> Deps; 1184 getPHIDeps(PHI, Deps, MBB, TE.MTM.MRI); 1185 assert(Deps.size() == 1 && "PHI doesn't have MBB as a predecessor"); 1186 DataDep &Dep = Deps.front(); 1187 unsigned DepCycle = getInstrCycles(*Dep.DefMI).Depth; 1188 // Add latency if DefMI is a real instruction. Transients get latency 0. 1189 if (!Dep.DefMI->isTransient()) 1190 DepCycle += TE.MTM.SchedModel.computeOperandLatency(Dep.DefMI, Dep.DefOp, 1191 &PHI, Dep.UseOp); 1192 return DepCycle; 1193 } 1194 1195 /// When bottom is set include instructions in current block in estimate. 1196 unsigned MachineTraceMetrics::Trace::getResourceDepth(bool Bottom) const { 1197 // Find the limiting processor resource. 1198 // Numbers have been pre-scaled to be comparable. 1199 unsigned PRMax = 0; 1200 ArrayRef<unsigned> PRDepths = TE.getProcResourceDepths(getBlockNum()); 1201 if (Bottom) { 1202 ArrayRef<unsigned> PRCycles = TE.MTM.getProcResourceCycles(getBlockNum()); 1203 for (unsigned K = 0; K != PRDepths.size(); ++K) 1204 PRMax = std::max(PRMax, PRDepths[K] + PRCycles[K]); 1205 } else { 1206 for (unsigned PRD : PRDepths) 1207 PRMax = std::max(PRMax, PRD); 1208 } 1209 // Convert to cycle count. 1210 PRMax = TE.MTM.getCycles(PRMax); 1211 1212 /// All instructions before current block 1213 unsigned Instrs = TBI.InstrDepth; 1214 // plus instructions in current block 1215 if (Bottom) 1216 Instrs += TE.MTM.BlockInfo[getBlockNum()].InstrCount; 1217 if (unsigned IW = TE.MTM.SchedModel.getIssueWidth()) 1218 Instrs /= IW; 1219 // Assume issue width 1 without a schedule model. 1220 return std::max(Instrs, PRMax); 1221 } 1222 1223 unsigned MachineTraceMetrics::Trace::getResourceLength( 1224 ArrayRef<const MachineBasicBlock *> Extrablocks, 1225 ArrayRef<const MCSchedClassDesc *> ExtraInstrs, 1226 ArrayRef<const MCSchedClassDesc *> RemoveInstrs) const { 1227 // Add up resources above and below the center block. 1228 ArrayRef<unsigned> PRDepths = TE.getProcResourceDepths(getBlockNum()); 1229 ArrayRef<unsigned> PRHeights = TE.getProcResourceHeights(getBlockNum()); 1230 unsigned PRMax = 0; 1231 1232 // Capture computing cycles from extra instructions 1233 auto extraCycles = [this](ArrayRef<const MCSchedClassDesc *> Instrs, 1234 unsigned ResourceIdx) 1235 ->unsigned { 1236 unsigned Cycles = 0; 1237 for (const MCSchedClassDesc *SC : Instrs) { 1238 if (!SC->isValid()) 1239 continue; 1240 for (TargetSchedModel::ProcResIter 1241 PI = TE.MTM.SchedModel.getWriteProcResBegin(SC), 1242 PE = TE.MTM.SchedModel.getWriteProcResEnd(SC); 1243 PI != PE; ++PI) { 1244 if (PI->ProcResourceIdx != ResourceIdx) 1245 continue; 1246 Cycles += 1247 (PI->Cycles * TE.MTM.SchedModel.getResourceFactor(ResourceIdx)); 1248 } 1249 } 1250 return Cycles; 1251 }; 1252 1253 for (unsigned K = 0; K != PRDepths.size(); ++K) { 1254 unsigned PRCycles = PRDepths[K] + PRHeights[K]; 1255 for (const MachineBasicBlock *MBB : Extrablocks) 1256 PRCycles += TE.MTM.getProcResourceCycles(MBB->getNumber())[K]; 1257 PRCycles += extraCycles(ExtraInstrs, K); 1258 PRCycles -= extraCycles(RemoveInstrs, K); 1259 PRMax = std::max(PRMax, PRCycles); 1260 } 1261 // Convert to cycle count. 1262 PRMax = TE.MTM.getCycles(PRMax); 1263 1264 // Instrs: #instructions in current trace outside current block. 1265 unsigned Instrs = TBI.InstrDepth + TBI.InstrHeight; 1266 // Add instruction count from the extra blocks. 1267 for (const MachineBasicBlock *MBB : Extrablocks) 1268 Instrs += TE.MTM.getResources(MBB)->InstrCount; 1269 Instrs += ExtraInstrs.size(); 1270 Instrs -= RemoveInstrs.size(); 1271 if (unsigned IW = TE.MTM.SchedModel.getIssueWidth()) 1272 Instrs /= IW; 1273 // Assume issue width 1 without a schedule model. 1274 return std::max(Instrs, PRMax); 1275 } 1276 1277 bool MachineTraceMetrics::Trace::isDepInTrace(const MachineInstr &DefMI, 1278 const MachineInstr &UseMI) const { 1279 if (DefMI.getParent() == UseMI.getParent()) 1280 return true; 1281 1282 const TraceBlockInfo &DepTBI = TE.BlockInfo[DefMI.getParent()->getNumber()]; 1283 const TraceBlockInfo &TBI = TE.BlockInfo[UseMI.getParent()->getNumber()]; 1284 1285 return DepTBI.isUsefulDominator(TBI); 1286 } 1287 1288 void MachineTraceMetrics::Ensemble::print(raw_ostream &OS) const { 1289 OS << getName() << " ensemble:\n"; 1290 for (unsigned i = 0, e = BlockInfo.size(); i != e; ++i) { 1291 OS << " %bb." << i << '\t'; 1292 BlockInfo[i].print(OS); 1293 OS << '\n'; 1294 } 1295 } 1296 1297 void MachineTraceMetrics::TraceBlockInfo::print(raw_ostream &OS) const { 1298 if (hasValidDepth()) { 1299 OS << "depth=" << InstrDepth; 1300 if (Pred) 1301 OS << " pred=" << printMBBReference(*Pred); 1302 else 1303 OS << " pred=null"; 1304 OS << " head=%bb." << Head; 1305 if (HasValidInstrDepths) 1306 OS << " +instrs"; 1307 } else 1308 OS << "depth invalid"; 1309 OS << ", "; 1310 if (hasValidHeight()) { 1311 OS << "height=" << InstrHeight; 1312 if (Succ) 1313 OS << " succ=" << printMBBReference(*Succ); 1314 else 1315 OS << " succ=null"; 1316 OS << " tail=%bb." << Tail; 1317 if (HasValidInstrHeights) 1318 OS << " +instrs"; 1319 } else 1320 OS << "height invalid"; 1321 if (HasValidInstrDepths && HasValidInstrHeights) 1322 OS << ", crit=" << CriticalPath; 1323 } 1324 1325 void MachineTraceMetrics::Trace::print(raw_ostream &OS) const { 1326 unsigned MBBNum = &TBI - &TE.BlockInfo[0]; 1327 1328 OS << TE.getName() << " trace %bb." << TBI.Head << " --> %bb." << MBBNum 1329 << " --> %bb." << TBI.Tail << ':'; 1330 if (TBI.hasValidHeight() && TBI.hasValidDepth()) 1331 OS << ' ' << getInstrCount() << " instrs."; 1332 if (TBI.HasValidInstrDepths && TBI.HasValidInstrHeights) 1333 OS << ' ' << TBI.CriticalPath << " cycles."; 1334 1335 const MachineTraceMetrics::TraceBlockInfo *Block = &TBI; 1336 OS << "\n%bb." << MBBNum; 1337 while (Block->hasValidDepth() && Block->Pred) { 1338 unsigned Num = Block->Pred->getNumber(); 1339 OS << " <- " << printMBBReference(*Block->Pred); 1340 Block = &TE.BlockInfo[Num]; 1341 } 1342 1343 Block = &TBI; 1344 OS << "\n "; 1345 while (Block->hasValidHeight() && Block->Succ) { 1346 unsigned Num = Block->Succ->getNumber(); 1347 OS << " -> " << printMBBReference(*Block->Succ); 1348 Block = &TE.BlockInfo[Num]; 1349 } 1350 OS << '\n'; 1351 } 1352