1 //===--------------------- RegisterFile.cpp ---------------------*- C++ -*-===// 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 /// \file 9 /// 10 /// This file defines a register mapping file class. This class is responsible 11 /// for managing hardware register files and the tracking of data dependencies 12 /// between registers. 13 /// 14 //===----------------------------------------------------------------------===// 15 16 #include "llvm/MCA/HardwareUnits/RegisterFile.h" 17 #include "llvm/MCA/Instruction.h" 18 #include "llvm/Support/Debug.h" 19 20 #define DEBUG_TYPE "llvm-mca" 21 22 namespace llvm { 23 namespace mca { 24 25 const unsigned WriteRef::INVALID_IID = std::numeric_limits<unsigned>::max(); 26 27 WriteRef::WriteRef(unsigned SourceIndex, WriteState *WS) 28 : IID(SourceIndex), WriteBackCycle(), WriteResID(), RegisterID(), 29 Write(WS) {} 30 31 void WriteRef::commit() { 32 assert(Write && Write->isExecuted() && "Cannot commit before write back!"); 33 RegisterID = Write->getRegisterID(); 34 WriteResID = Write->getWriteResourceID(); 35 Write = nullptr; 36 } 37 38 void WriteRef::notifyExecuted(unsigned Cycle) { 39 assert(Write && Write->isExecuted() && "Not executed!"); 40 WriteBackCycle = Cycle; 41 } 42 43 bool WriteRef::hasKnownWriteBackCycle() const { 44 return isValid() && (!Write || Write->isExecuted()); 45 } 46 47 bool WriteRef::isWriteZero() const { 48 assert(isValid() && "Invalid null WriteState found!"); 49 return getWriteState()->isWriteZero(); 50 } 51 52 unsigned WriteRef::getWriteResourceID() const { 53 if (Write) 54 return Write->getWriteResourceID(); 55 return WriteResID; 56 } 57 58 MCPhysReg WriteRef::getRegisterID() const { 59 if (Write) 60 return Write->getRegisterID(); 61 return RegisterID; 62 } 63 64 RegisterFile::RegisterFile(const MCSchedModel &SM, const MCRegisterInfo &mri, 65 unsigned NumRegs) 66 : MRI(mri), 67 RegisterMappings(mri.getNumRegs(), {WriteRef(), RegisterRenamingInfo()}), 68 ZeroRegisters(mri.getNumRegs(), false), CurrentCycle() { 69 initialize(SM, NumRegs); 70 } 71 72 void RegisterFile::initialize(const MCSchedModel &SM, unsigned NumRegs) { 73 // Create a default register file that "sees" all the machine registers 74 // declared by the target. The number of physical registers in the default 75 // register file is set equal to `NumRegs`. A value of zero for `NumRegs` 76 // means: this register file has an unbounded number of physical registers. 77 RegisterFiles.emplace_back(NumRegs); 78 if (!SM.hasExtraProcessorInfo()) 79 return; 80 81 // For each user defined register file, allocate a RegisterMappingTracker 82 // object. The size of every register file, as well as the mapping between 83 // register files and register classes is specified via tablegen. 84 const MCExtraProcessorInfo &Info = SM.getExtraProcessorInfo(); 85 86 // Skip invalid register file at index 0. 87 for (unsigned I = 1, E = Info.NumRegisterFiles; I < E; ++I) { 88 const MCRegisterFileDesc &RF = Info.RegisterFiles[I]; 89 assert(RF.NumPhysRegs && "Invalid PRF with zero physical registers!"); 90 91 // The cost of a register definition is equivalent to the number of 92 // physical registers that are allocated at register renaming stage. 93 unsigned Length = RF.NumRegisterCostEntries; 94 const MCRegisterCostEntry *FirstElt = 95 &Info.RegisterCostTable[RF.RegisterCostEntryIdx]; 96 addRegisterFile(RF, ArrayRef<MCRegisterCostEntry>(FirstElt, Length)); 97 } 98 } 99 100 void RegisterFile::cycleStart() { 101 for (RegisterMappingTracker &RMT : RegisterFiles) 102 RMT.NumMoveEliminated = 0; 103 } 104 105 void RegisterFile::onInstructionExecuted(Instruction *IS) { 106 assert(IS && IS->isExecuted() && "Unexpected internal state found!"); 107 for (WriteState &WS : IS->getDefs()) { 108 if (WS.isEliminated()) 109 return; 110 111 MCPhysReg RegID = WS.getRegisterID(); 112 113 // This allows InstrPostProcess to remove register Defs 114 // by setting their RegisterID to 0. 115 if (!RegID) 116 continue; 117 118 assert(WS.getCyclesLeft() != UNKNOWN_CYCLES && 119 "The number of cycles should be known at this point!"); 120 assert(WS.getCyclesLeft() <= 0 && "Invalid cycles left for this write!"); 121 122 MCPhysReg RenameAs = RegisterMappings[RegID].second.RenameAs; 123 if (RenameAs && RenameAs != RegID) 124 RegID = RenameAs; 125 126 WriteRef &WR = RegisterMappings[RegID].first; 127 if (WR.getWriteState() == &WS) 128 WR.notifyExecuted(CurrentCycle); 129 130 for (MCSubRegIterator I(RegID, &MRI); I.isValid(); ++I) { 131 WriteRef &OtherWR = RegisterMappings[*I].first; 132 if (OtherWR.getWriteState() == &WS) 133 OtherWR.notifyExecuted(CurrentCycle); 134 } 135 136 if (!WS.clearsSuperRegisters()) 137 continue; 138 139 for (MCSuperRegIterator I(RegID, &MRI); I.isValid(); ++I) { 140 WriteRef &OtherWR = RegisterMappings[*I].first; 141 if (OtherWR.getWriteState() == &WS) 142 OtherWR.notifyExecuted(CurrentCycle); 143 } 144 } 145 } 146 147 void RegisterFile::addRegisterFile(const MCRegisterFileDesc &RF, 148 ArrayRef<MCRegisterCostEntry> Entries) { 149 // A default register file is always allocated at index #0. That register file 150 // is mainly used to count the total number of mappings created by all 151 // register files at runtime. Users can limit the number of available physical 152 // registers in register file #0 through the command line flag 153 // `-register-file-size`. 154 unsigned RegisterFileIndex = RegisterFiles.size(); 155 RegisterFiles.emplace_back(RF.NumPhysRegs, RF.MaxMovesEliminatedPerCycle, 156 RF.AllowZeroMoveEliminationOnly); 157 158 // Special case where there is no register class identifier in the set. 159 // An empty set of register classes means: this register file contains all 160 // the physical registers specified by the target. 161 // We optimistically assume that a register can be renamed at the cost of a 162 // single physical register. The constructor of RegisterFile ensures that 163 // a RegisterMapping exists for each logical register defined by the Target. 164 if (Entries.empty()) 165 return; 166 167 // Now update the cost of individual registers. 168 for (const MCRegisterCostEntry &RCE : Entries) { 169 const MCRegisterClass &RC = MRI.getRegClass(RCE.RegisterClassID); 170 for (const MCPhysReg Reg : RC) { 171 RegisterRenamingInfo &Entry = RegisterMappings[Reg].second; 172 IndexPlusCostPairTy &IPC = Entry.IndexPlusCost; 173 if (IPC.first && IPC.first != RegisterFileIndex) { 174 // The only register file that is allowed to overlap is the default 175 // register file at index #0. The analysis is inaccurate if register 176 // files overlap. 177 errs() << "warning: register " << MRI.getName(Reg) 178 << " defined in multiple register files."; 179 } 180 IPC = std::make_pair(RegisterFileIndex, RCE.Cost); 181 Entry.RenameAs = Reg; 182 Entry.AllowMoveElimination = RCE.AllowMoveElimination; 183 184 // Assume the same cost for each sub-register. 185 for (MCSubRegIterator I(Reg, &MRI); I.isValid(); ++I) { 186 RegisterRenamingInfo &OtherEntry = RegisterMappings[*I].second; 187 if (!OtherEntry.IndexPlusCost.first && 188 (!OtherEntry.RenameAs || 189 MRI.isSuperRegister(*I, OtherEntry.RenameAs))) { 190 OtherEntry.IndexPlusCost = IPC; 191 OtherEntry.RenameAs = Reg; 192 } 193 } 194 } 195 } 196 } 197 198 void RegisterFile::allocatePhysRegs(const RegisterRenamingInfo &Entry, 199 MutableArrayRef<unsigned> UsedPhysRegs) { 200 unsigned RegisterFileIndex = Entry.IndexPlusCost.first; 201 unsigned Cost = Entry.IndexPlusCost.second; 202 if (RegisterFileIndex) { 203 RegisterMappingTracker &RMT = RegisterFiles[RegisterFileIndex]; 204 RMT.NumUsedPhysRegs += Cost; 205 UsedPhysRegs[RegisterFileIndex] += Cost; 206 } 207 208 // Now update the default register mapping tracker. 209 RegisterFiles[0].NumUsedPhysRegs += Cost; 210 UsedPhysRegs[0] += Cost; 211 } 212 213 void RegisterFile::freePhysRegs(const RegisterRenamingInfo &Entry, 214 MutableArrayRef<unsigned> FreedPhysRegs) { 215 unsigned RegisterFileIndex = Entry.IndexPlusCost.first; 216 unsigned Cost = Entry.IndexPlusCost.second; 217 if (RegisterFileIndex) { 218 RegisterMappingTracker &RMT = RegisterFiles[RegisterFileIndex]; 219 RMT.NumUsedPhysRegs -= Cost; 220 FreedPhysRegs[RegisterFileIndex] += Cost; 221 } 222 223 // Now update the default register mapping tracker. 224 RegisterFiles[0].NumUsedPhysRegs -= Cost; 225 FreedPhysRegs[0] += Cost; 226 } 227 228 void RegisterFile::addRegisterWrite(WriteRef Write, 229 MutableArrayRef<unsigned> UsedPhysRegs) { 230 WriteState &WS = *Write.getWriteState(); 231 MCPhysReg RegID = WS.getRegisterID(); 232 233 // This allows InstrPostProcess to remove register Defs 234 // by setting their RegisterID to 0. 235 if (!RegID) 236 return; 237 238 LLVM_DEBUG({ 239 dbgs() << "[PRF] addRegisterWrite [ " << Write.getSourceIndex() << ", " 240 << MRI.getName(RegID) << "]\n"; 241 }); 242 243 // If RenameAs is equal to RegID, then RegID is subject to register renaming 244 // and false dependencies on RegID are all eliminated. 245 246 // If RenameAs references the invalid register, then we optimistically assume 247 // that it can be renamed. In the absence of tablegen descriptors for register 248 // files, RenameAs is always set to the invalid register ID. In all other 249 // cases, RenameAs must be either equal to RegID, or it must reference a 250 // super-register of RegID. 251 252 // If RenameAs is a super-register of RegID, then a write to RegID has always 253 // a false dependency on RenameAs. The only exception is for when the write 254 // implicitly clears the upper portion of the underlying register. 255 // If a write clears its super-registers, then it is renamed as `RenameAs`. 256 bool IsWriteZero = WS.isWriteZero(); 257 bool IsEliminated = WS.isEliminated(); 258 bool ShouldAllocatePhysRegs = !IsWriteZero && !IsEliminated; 259 const RegisterRenamingInfo &RRI = RegisterMappings[RegID].second; 260 WS.setPRF(RRI.IndexPlusCost.first); 261 262 if (RRI.RenameAs && RRI.RenameAs != RegID) { 263 RegID = RRI.RenameAs; 264 WriteRef &OtherWrite = RegisterMappings[RegID].first; 265 266 if (!WS.clearsSuperRegisters()) { 267 // The processor keeps the definition of `RegID` together with register 268 // `RenameAs`. Since this partial write is not renamed, no physical 269 // register is allocated. 270 ShouldAllocatePhysRegs = false; 271 272 WriteState *OtherWS = OtherWrite.getWriteState(); 273 if (OtherWS && (OtherWrite.getSourceIndex() != Write.getSourceIndex())) { 274 // This partial write has a false dependency on RenameAs. 275 assert(!IsEliminated && "Unexpected partial update!"); 276 OtherWS->addUser(OtherWrite.getSourceIndex(), &WS); 277 } 278 } 279 } 280 281 // Update zero registers. 282 MCPhysReg ZeroRegisterID = 283 WS.clearsSuperRegisters() ? RegID : WS.getRegisterID(); 284 ZeroRegisters.setBitVal(ZeroRegisterID, IsWriteZero); 285 for (MCSubRegIterator I(ZeroRegisterID, &MRI); I.isValid(); ++I) 286 ZeroRegisters.setBitVal(*I, IsWriteZero); 287 288 // If this move has been eliminated, then method tryEliminateMoveOrSwap should 289 // have already updated all the register mappings. 290 if (!IsEliminated) { 291 // Check if this is one of multiple writes performed by this 292 // instruction to register RegID. 293 const WriteRef &OtherWrite = RegisterMappings[RegID].first; 294 const WriteState *OtherWS = OtherWrite.getWriteState(); 295 if (OtherWS && OtherWrite.getSourceIndex() == Write.getSourceIndex()) { 296 if (OtherWS->getLatency() > WS.getLatency()) { 297 // Conservatively keep the slowest write on RegID. 298 if (ShouldAllocatePhysRegs) 299 allocatePhysRegs(RegisterMappings[RegID].second, UsedPhysRegs); 300 return; 301 } 302 } 303 304 // Update the mapping for register RegID including its sub-registers. 305 RegisterMappings[RegID].first = Write; 306 RegisterMappings[RegID].second.AliasRegID = 0U; 307 for (MCSubRegIterator I(RegID, &MRI); I.isValid(); ++I) { 308 RegisterMappings[*I].first = Write; 309 RegisterMappings[*I].second.AliasRegID = 0U; 310 } 311 312 // No physical registers are allocated for instructions that are optimized 313 // in hardware. For example, zero-latency data-dependency breaking 314 // instructions don't consume physical registers. 315 if (ShouldAllocatePhysRegs) 316 allocatePhysRegs(RegisterMappings[RegID].second, UsedPhysRegs); 317 } 318 319 if (!WS.clearsSuperRegisters()) 320 return; 321 322 for (MCSuperRegIterator I(RegID, &MRI); I.isValid(); ++I) { 323 if (!IsEliminated) { 324 RegisterMappings[*I].first = Write; 325 RegisterMappings[*I].second.AliasRegID = 0U; 326 } 327 328 ZeroRegisters.setBitVal(*I, IsWriteZero); 329 } 330 } 331 332 void RegisterFile::removeRegisterWrite( 333 const WriteState &WS, MutableArrayRef<unsigned> FreedPhysRegs) { 334 // Early exit if this write was eliminated. A write eliminated at register 335 // renaming stage generates an alias, and it is not added to the PRF. 336 if (WS.isEliminated()) 337 return; 338 339 MCPhysReg RegID = WS.getRegisterID(); 340 341 // This allows InstrPostProcess to remove register Defs 342 // by setting their RegisterID to 0. 343 if (!RegID) 344 return; 345 346 assert(WS.getCyclesLeft() != UNKNOWN_CYCLES && 347 "Invalidating a write of unknown cycles!"); 348 assert(WS.getCyclesLeft() <= 0 && "Invalid cycles left for this write!"); 349 350 bool ShouldFreePhysRegs = !WS.isWriteZero(); 351 MCPhysReg RenameAs = RegisterMappings[RegID].second.RenameAs; 352 if (RenameAs && RenameAs != RegID) { 353 RegID = RenameAs; 354 355 if (!WS.clearsSuperRegisters()) { 356 // Keep the definition of `RegID` together with register `RenameAs`. 357 ShouldFreePhysRegs = false; 358 } 359 } 360 361 if (ShouldFreePhysRegs) 362 freePhysRegs(RegisterMappings[RegID].second, FreedPhysRegs); 363 364 WriteRef &WR = RegisterMappings[RegID].first; 365 if (WR.getWriteState() == &WS) 366 WR.commit(); 367 368 for (MCSubRegIterator I(RegID, &MRI); I.isValid(); ++I) { 369 WriteRef &OtherWR = RegisterMappings[*I].first; 370 if (OtherWR.getWriteState() == &WS) 371 OtherWR.commit(); 372 } 373 374 if (!WS.clearsSuperRegisters()) 375 return; 376 377 for (MCSuperRegIterator I(RegID, &MRI); I.isValid(); ++I) { 378 WriteRef &OtherWR = RegisterMappings[*I].first; 379 if (OtherWR.getWriteState() == &WS) 380 OtherWR.commit(); 381 } 382 } 383 384 bool RegisterFile::canEliminateMove(const WriteState &WS, const ReadState &RS, 385 unsigned RegisterFileIndex) const { 386 const RegisterMapping &RMFrom = RegisterMappings[RS.getRegisterID()]; 387 const RegisterMapping &RMTo = RegisterMappings[WS.getRegisterID()]; 388 const RegisterMappingTracker &RMT = RegisterFiles[RegisterFileIndex]; 389 390 // From and To must be owned by the PRF at index `RegisterFileIndex`. 391 const RegisterRenamingInfo &RRIFrom = RMFrom.second; 392 if (RRIFrom.IndexPlusCost.first != RegisterFileIndex) 393 return false; 394 395 const RegisterRenamingInfo &RRITo = RMTo.second; 396 if (RRITo.IndexPlusCost.first != RegisterFileIndex) 397 return false; 398 399 // Early exit if the destination register is from a register class that 400 // doesn't allow move elimination. 401 if (!RegisterMappings[RRITo.RenameAs].second.AllowMoveElimination) 402 return false; 403 404 // We only allow move elimination for writes that update a full physical 405 // register. On X86, move elimination is possible with 32-bit general purpose 406 // registers because writes to those registers are not partial writes. If a 407 // register move is a partial write, then we conservatively assume that move 408 // elimination fails, since it would either trigger a partial update, or the 409 // issue of a merge opcode. 410 // 411 // Note that this constraint may be lifted in future. For example, we could 412 // make this model more flexible, and let users customize the set of registers 413 // (i.e. register classes) that allow move elimination. 414 // 415 // For now, we assume that there is a strong correlation between registers 416 // that allow move elimination, and how those same registers are renamed in 417 // hardware. 418 if (RRITo.RenameAs && RRITo.RenameAs != WS.getRegisterID()) 419 if (!WS.clearsSuperRegisters()) 420 return false; 421 422 bool IsZeroMove = ZeroRegisters[RS.getRegisterID()]; 423 return (!RMT.AllowZeroMoveEliminationOnly || IsZeroMove); 424 } 425 426 bool RegisterFile::tryEliminateMoveOrSwap(MutableArrayRef<WriteState> Writes, 427 MutableArrayRef<ReadState> Reads) { 428 if (Writes.size() != Reads.size()) 429 return false; 430 431 // This logic assumes that writes and reads are contributed by a register move 432 // or a register swap operation. In particular, it assumes a simple register 433 // move if there is only one write. It assumes a swap operation if there are 434 // exactly two writes. 435 if (Writes.empty() || Writes.size() > 2) 436 return false; 437 438 // All registers must be owned by the same PRF. 439 const RegisterRenamingInfo &RRInfo = 440 RegisterMappings[Writes[0].getRegisterID()].second; 441 unsigned RegisterFileIndex = RRInfo.IndexPlusCost.first; 442 RegisterMappingTracker &RMT = RegisterFiles[RegisterFileIndex]; 443 444 // Early exit if the PRF cannot eliminate more moves/xchg in this cycle. 445 if (RMT.MaxMoveEliminatedPerCycle && 446 (RMT.NumMoveEliminated + Writes.size()) > RMT.MaxMoveEliminatedPerCycle) 447 return false; 448 449 for (size_t I = 0, E = Writes.size(); I < E; ++I) { 450 const ReadState &RS = Reads[I]; 451 const WriteState &WS = Writes[E - (I + 1)]; 452 if (!canEliminateMove(WS, RS, RegisterFileIndex)) 453 return false; 454 } 455 456 for (size_t I = 0, E = Writes.size(); I < E; ++I) { 457 ReadState &RS = Reads[I]; 458 WriteState &WS = Writes[E - (I + 1)]; 459 460 const RegisterMapping &RMFrom = RegisterMappings[RS.getRegisterID()]; 461 const RegisterMapping &RMTo = RegisterMappings[WS.getRegisterID()]; 462 const RegisterRenamingInfo &RRIFrom = RMFrom.second; 463 const RegisterRenamingInfo &RRITo = RMTo.second; 464 465 // Construct an alias. 466 MCPhysReg AliasedReg = 467 RRIFrom.RenameAs ? RRIFrom.RenameAs : RS.getRegisterID(); 468 MCPhysReg AliasReg = RRITo.RenameAs ? RRITo.RenameAs : WS.getRegisterID(); 469 470 const RegisterRenamingInfo &RMAlias = RegisterMappings[AliasedReg].second; 471 if (RMAlias.AliasRegID) 472 AliasedReg = RMAlias.AliasRegID; 473 474 RegisterMappings[AliasReg].second.AliasRegID = AliasedReg; 475 for (MCSubRegIterator I(AliasReg, &MRI); I.isValid(); ++I) 476 RegisterMappings[*I].second.AliasRegID = AliasedReg; 477 478 if (ZeroRegisters[RS.getRegisterID()]) { 479 WS.setWriteZero(); 480 RS.setReadZero(); 481 } 482 483 WS.setEliminated(); 484 RMT.NumMoveEliminated++; 485 } 486 487 return true; 488 } 489 490 unsigned WriteRef::getWriteBackCycle() const { 491 assert(hasKnownWriteBackCycle() && "Instruction not executed!"); 492 assert((!Write || Write->getCyclesLeft() <= 0) && 493 "Inconsistent state found!"); 494 return WriteBackCycle; 495 } 496 497 unsigned RegisterFile::getElapsedCyclesFromWriteBack(const WriteRef &WR) const { 498 assert(WR.hasKnownWriteBackCycle() && "Write hasn't been committed yet!"); 499 return CurrentCycle - WR.getWriteBackCycle(); 500 } 501 502 void RegisterFile::collectWrites( 503 const MCSubtargetInfo &STI, const ReadState &RS, 504 SmallVectorImpl<WriteRef> &Writes, 505 SmallVectorImpl<WriteRef> &CommittedWrites) const { 506 const ReadDescriptor &RD = RS.getDescriptor(); 507 const MCSchedModel &SM = STI.getSchedModel(); 508 const MCSchedClassDesc *SC = SM.getSchedClassDesc(RD.SchedClassID); 509 MCPhysReg RegID = RS.getRegisterID(); 510 assert(RegID && RegID < RegisterMappings.size()); 511 LLVM_DEBUG(dbgs() << "[PRF] collecting writes for register " 512 << MRI.getName(RegID) << '\n'); 513 514 // Check if this is an alias. 515 const RegisterRenamingInfo &RRI = RegisterMappings[RegID].second; 516 if (RRI.AliasRegID) 517 RegID = RRI.AliasRegID; 518 519 const WriteRef &WR = RegisterMappings[RegID].first; 520 if (WR.getWriteState()) { 521 Writes.push_back(WR); 522 } else if (WR.hasKnownWriteBackCycle()) { 523 unsigned WriteResID = WR.getWriteResourceID(); 524 int ReadAdvance = STI.getReadAdvanceCycles(SC, RD.UseIndex, WriteResID); 525 if (ReadAdvance < 0) { 526 unsigned Elapsed = getElapsedCyclesFromWriteBack(WR); 527 if (Elapsed < static_cast<unsigned>(-ReadAdvance)) 528 CommittedWrites.push_back(WR); 529 } 530 } 531 532 // Handle potential partial register updates. 533 for (MCSubRegIterator I(RegID, &MRI); I.isValid(); ++I) { 534 const WriteRef &WR = RegisterMappings[*I].first; 535 if (WR.getWriteState()) { 536 Writes.push_back(WR); 537 } else if (WR.hasKnownWriteBackCycle()) { 538 unsigned WriteResID = WR.getWriteResourceID(); 539 int ReadAdvance = STI.getReadAdvanceCycles(SC, RD.UseIndex, WriteResID); 540 if (ReadAdvance < 0) { 541 unsigned Elapsed = getElapsedCyclesFromWriteBack(WR); 542 if (Elapsed < static_cast<unsigned>(-ReadAdvance)) 543 CommittedWrites.push_back(WR); 544 } 545 } 546 } 547 548 // Remove duplicate entries and resize the input vector. 549 if (Writes.size() > 1) { 550 sort(Writes, [](const WriteRef &Lhs, const WriteRef &Rhs) { 551 return Lhs.getWriteState() < Rhs.getWriteState(); 552 }); 553 auto It = std::unique(Writes.begin(), Writes.end()); 554 Writes.resize(std::distance(Writes.begin(), It)); 555 } 556 557 LLVM_DEBUG({ 558 for (const WriteRef &WR : Writes) { 559 const WriteState &WS = *WR.getWriteState(); 560 dbgs() << "[PRF] Found a dependent use of Register " 561 << MRI.getName(WS.getRegisterID()) << " (defined by instruction #" 562 << WR.getSourceIndex() << ")\n"; 563 } 564 }); 565 } 566 567 RegisterFile::RAWHazard 568 RegisterFile::checkRAWHazards(const MCSubtargetInfo &STI, 569 const ReadState &RS) const { 570 RAWHazard Hazard; 571 SmallVector<WriteRef, 4> Writes; 572 SmallVector<WriteRef, 4> CommittedWrites; 573 574 const MCSchedModel &SM = STI.getSchedModel(); 575 const ReadDescriptor &RD = RS.getDescriptor(); 576 const MCSchedClassDesc *SC = SM.getSchedClassDesc(RD.SchedClassID); 577 578 collectWrites(STI, RS, Writes, CommittedWrites); 579 for (const WriteRef &WR : Writes) { 580 const WriteState *WS = WR.getWriteState(); 581 unsigned WriteResID = WS->getWriteResourceID(); 582 int ReadAdvance = STI.getReadAdvanceCycles(SC, RD.UseIndex, WriteResID); 583 584 if (WS->getCyclesLeft() == UNKNOWN_CYCLES) { 585 if (Hazard.isValid()) 586 continue; 587 588 Hazard.RegisterID = WR.getRegisterID(); 589 Hazard.CyclesLeft = UNKNOWN_CYCLES; 590 continue; 591 } 592 593 int CyclesLeft = WS->getCyclesLeft() - ReadAdvance; 594 if (CyclesLeft > 0) { 595 if (Hazard.CyclesLeft < CyclesLeft) { 596 Hazard.RegisterID = WR.getRegisterID(); 597 Hazard.CyclesLeft = CyclesLeft; 598 } 599 } 600 } 601 Writes.clear(); 602 603 for (const WriteRef &WR : CommittedWrites) { 604 unsigned WriteResID = WR.getWriteResourceID(); 605 int NegReadAdvance = -STI.getReadAdvanceCycles(SC, RD.UseIndex, WriteResID); 606 int Elapsed = static_cast<int>(getElapsedCyclesFromWriteBack(WR)); 607 int CyclesLeft = NegReadAdvance - Elapsed; 608 assert(CyclesLeft > 0 && "Write should not be in the CommottedWrites set!"); 609 if (Hazard.CyclesLeft < CyclesLeft) { 610 Hazard.RegisterID = WR.getRegisterID(); 611 Hazard.CyclesLeft = CyclesLeft; 612 } 613 } 614 615 return Hazard; 616 } 617 618 void RegisterFile::addRegisterRead(ReadState &RS, 619 const MCSubtargetInfo &STI) const { 620 MCPhysReg RegID = RS.getRegisterID(); 621 const RegisterRenamingInfo &RRI = RegisterMappings[RegID].second; 622 RS.setPRF(RRI.IndexPlusCost.first); 623 if (RS.isIndependentFromDef()) 624 return; 625 626 if (ZeroRegisters[RS.getRegisterID()]) 627 RS.setReadZero(); 628 629 SmallVector<WriteRef, 4> DependentWrites; 630 SmallVector<WriteRef, 4> CompletedWrites; 631 collectWrites(STI, RS, DependentWrites, CompletedWrites); 632 RS.setDependentWrites(DependentWrites.size() + CompletedWrites.size()); 633 634 // We know that this read depends on all the writes in DependentWrites. 635 // For each write, check if we have ReadAdvance information, and use it 636 // to figure out in how many cycles this read will be available. 637 const ReadDescriptor &RD = RS.getDescriptor(); 638 const MCSchedModel &SM = STI.getSchedModel(); 639 const MCSchedClassDesc *SC = SM.getSchedClassDesc(RD.SchedClassID); 640 for (WriteRef &WR : DependentWrites) { 641 unsigned WriteResID = WR.getWriteResourceID(); 642 WriteState &WS = *WR.getWriteState(); 643 int ReadAdvance = STI.getReadAdvanceCycles(SC, RD.UseIndex, WriteResID); 644 WS.addUser(WR.getSourceIndex(), &RS, ReadAdvance); 645 } 646 647 for (WriteRef &WR : CompletedWrites) { 648 unsigned WriteResID = WR.getWriteResourceID(); 649 assert(WR.hasKnownWriteBackCycle() && "Invalid write!"); 650 assert(STI.getReadAdvanceCycles(SC, RD.UseIndex, WriteResID) < 0); 651 unsigned ReadAdvance = static_cast<unsigned>( 652 -STI.getReadAdvanceCycles(SC, RD.UseIndex, WriteResID)); 653 unsigned Elapsed = getElapsedCyclesFromWriteBack(WR); 654 assert(Elapsed < ReadAdvance && "Should not have been added to the set!"); 655 RS.writeStartEvent(WR.getSourceIndex(), WR.getRegisterID(), 656 ReadAdvance - Elapsed); 657 } 658 } 659 660 unsigned RegisterFile::isAvailable(ArrayRef<MCPhysReg> Regs) const { 661 SmallVector<unsigned, 4> NumPhysRegs(getNumRegisterFiles()); 662 663 // Find how many new mappings must be created for each register file. 664 for (const MCPhysReg RegID : Regs) { 665 const RegisterRenamingInfo &RRI = RegisterMappings[RegID].second; 666 const IndexPlusCostPairTy &Entry = RRI.IndexPlusCost; 667 if (Entry.first) 668 NumPhysRegs[Entry.first] += Entry.second; 669 NumPhysRegs[0] += Entry.second; 670 } 671 672 unsigned Response = 0; 673 for (unsigned I = 0, E = getNumRegisterFiles(); I < E; ++I) { 674 unsigned NumRegs = NumPhysRegs[I]; 675 if (!NumRegs) 676 continue; 677 678 const RegisterMappingTracker &RMT = RegisterFiles[I]; 679 if (!RMT.NumPhysRegs) { 680 // The register file has an unbounded number of microarchitectural 681 // registers. 682 continue; 683 } 684 685 if (RMT.NumPhysRegs < NumRegs) { 686 // The current register file is too small. This may occur if the number of 687 // microarchitectural registers in register file #0 was changed by the 688 // users via flag -reg-file-size. Alternatively, the scheduling model 689 // specified a too small number of registers for this register file. 690 LLVM_DEBUG( 691 dbgs() << "[PRF] Not enough registers in the register file.\n"); 692 693 // FIXME: Normalize the instruction register count to match the 694 // NumPhysRegs value. This is a highly unusual case, and is not expected 695 // to occur. This normalization is hiding an inconsistency in either the 696 // scheduling model or in the value that the user might have specified 697 // for NumPhysRegs. 698 NumRegs = RMT.NumPhysRegs; 699 } 700 701 if (RMT.NumPhysRegs < (RMT.NumUsedPhysRegs + NumRegs)) 702 Response |= (1U << I); 703 } 704 705 return Response; 706 } 707 708 #ifndef NDEBUG 709 void WriteRef::dump() const { 710 dbgs() << "IID=" << getSourceIndex() << ' '; 711 if (isValid()) 712 getWriteState()->dump(); 713 else 714 dbgs() << "(null)"; 715 } 716 717 void RegisterFile::dump() const { 718 for (unsigned I = 0, E = MRI.getNumRegs(); I < E; ++I) { 719 const RegisterMapping &RM = RegisterMappings[I]; 720 const RegisterRenamingInfo &RRI = RM.second; 721 if (ZeroRegisters[I]) { 722 dbgs() << MRI.getName(I) << ", " << I 723 << ", PRF=" << RRI.IndexPlusCost.first 724 << ", Cost=" << RRI.IndexPlusCost.second 725 << ", RenameAs=" << RRI.RenameAs << ", IsZero=" << ZeroRegisters[I] 726 << ","; 727 RM.first.dump(); 728 dbgs() << '\n'; 729 } 730 } 731 732 for (unsigned I = 0, E = getNumRegisterFiles(); I < E; ++I) { 733 dbgs() << "Register File #" << I; 734 const RegisterMappingTracker &RMT = RegisterFiles[I]; 735 dbgs() << "\n TotalMappings: " << RMT.NumPhysRegs 736 << "\n NumUsedMappings: " << RMT.NumUsedPhysRegs << '\n'; 737 } 738 } 739 #endif 740 741 } // namespace mca 742 } // namespace llvm 743