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 RegisterFile::RegisterFile(const MCSchedModel &SM, const MCRegisterInfo &mri, 26 unsigned NumRegs) 27 : MRI(mri), 28 RegisterMappings(mri.getNumRegs(), {WriteRef(), RegisterRenamingInfo()}), 29 ZeroRegisters(mri.getNumRegs(), false) { 30 initialize(SM, NumRegs); 31 } 32 33 void RegisterFile::initialize(const MCSchedModel &SM, unsigned NumRegs) { 34 // Create a default register file that "sees" all the machine registers 35 // declared by the target. The number of physical registers in the default 36 // register file is set equal to `NumRegs`. A value of zero for `NumRegs` 37 // means: this register file has an unbounded number of physical registers. 38 RegisterFiles.emplace_back(NumRegs); 39 if (!SM.hasExtraProcessorInfo()) 40 return; 41 42 // For each user defined register file, allocate a RegisterMappingTracker 43 // object. The size of every register file, as well as the mapping between 44 // register files and register classes is specified via tablegen. 45 const MCExtraProcessorInfo &Info = SM.getExtraProcessorInfo(); 46 47 // Skip invalid register file at index 0. 48 for (unsigned I = 1, E = Info.NumRegisterFiles; I < E; ++I) { 49 const MCRegisterFileDesc &RF = Info.RegisterFiles[I]; 50 assert(RF.NumPhysRegs && "Invalid PRF with zero physical registers!"); 51 52 // The cost of a register definition is equivalent to the number of 53 // physical registers that are allocated at register renaming stage. 54 unsigned Length = RF.NumRegisterCostEntries; 55 const MCRegisterCostEntry *FirstElt = 56 &Info.RegisterCostTable[RF.RegisterCostEntryIdx]; 57 addRegisterFile(RF, ArrayRef<MCRegisterCostEntry>(FirstElt, Length)); 58 } 59 } 60 61 void RegisterFile::cycleStart() { 62 for (RegisterMappingTracker &RMT : RegisterFiles) 63 RMT.NumMoveEliminated = 0; 64 } 65 66 void RegisterFile::addRegisterFile(const MCRegisterFileDesc &RF, 67 ArrayRef<MCRegisterCostEntry> Entries) { 68 // A default register file is always allocated at index #0. That register file 69 // is mainly used to count the total number of mappings created by all 70 // register files at runtime. Users can limit the number of available physical 71 // registers in register file #0 through the command line flag 72 // `-register-file-size`. 73 unsigned RegisterFileIndex = RegisterFiles.size(); 74 RegisterFiles.emplace_back(RF.NumPhysRegs, RF.MaxMovesEliminatedPerCycle, 75 RF.AllowZeroMoveEliminationOnly); 76 77 // Special case where there is no register class identifier in the set. 78 // An empty set of register classes means: this register file contains all 79 // the physical registers specified by the target. 80 // We optimistically assume that a register can be renamed at the cost of a 81 // single physical register. The constructor of RegisterFile ensures that 82 // a RegisterMapping exists for each logical register defined by the Target. 83 if (Entries.empty()) 84 return; 85 86 // Now update the cost of individual registers. 87 for (const MCRegisterCostEntry &RCE : Entries) { 88 const MCRegisterClass &RC = MRI.getRegClass(RCE.RegisterClassID); 89 for (const MCPhysReg Reg : RC) { 90 RegisterRenamingInfo &Entry = RegisterMappings[Reg].second; 91 IndexPlusCostPairTy &IPC = Entry.IndexPlusCost; 92 if (IPC.first && IPC.first != RegisterFileIndex) { 93 // The only register file that is allowed to overlap is the default 94 // register file at index #0. The analysis is inaccurate if register 95 // files overlap. 96 errs() << "warning: register " << MRI.getName(Reg) 97 << " defined in multiple register files."; 98 } 99 IPC = std::make_pair(RegisterFileIndex, RCE.Cost); 100 Entry.RenameAs = Reg; 101 Entry.AllowMoveElimination = RCE.AllowMoveElimination; 102 103 // Assume the same cost for each sub-register. 104 for (MCSubRegIterator I(Reg, &MRI); I.isValid(); ++I) { 105 RegisterRenamingInfo &OtherEntry = RegisterMappings[*I].second; 106 if (!OtherEntry.IndexPlusCost.first && 107 (!OtherEntry.RenameAs || 108 MRI.isSuperRegister(*I, OtherEntry.RenameAs))) { 109 OtherEntry.IndexPlusCost = IPC; 110 OtherEntry.RenameAs = Reg; 111 } 112 } 113 } 114 } 115 } 116 117 void RegisterFile::allocatePhysRegs(const RegisterRenamingInfo &Entry, 118 MutableArrayRef<unsigned> UsedPhysRegs) { 119 unsigned RegisterFileIndex = Entry.IndexPlusCost.first; 120 unsigned Cost = Entry.IndexPlusCost.second; 121 if (RegisterFileIndex) { 122 RegisterMappingTracker &RMT = RegisterFiles[RegisterFileIndex]; 123 RMT.NumUsedPhysRegs += Cost; 124 UsedPhysRegs[RegisterFileIndex] += Cost; 125 } 126 127 // Now update the default register mapping tracker. 128 RegisterFiles[0].NumUsedPhysRegs += Cost; 129 UsedPhysRegs[0] += Cost; 130 } 131 132 void RegisterFile::freePhysRegs(const RegisterRenamingInfo &Entry, 133 MutableArrayRef<unsigned> FreedPhysRegs) { 134 unsigned RegisterFileIndex = Entry.IndexPlusCost.first; 135 unsigned Cost = Entry.IndexPlusCost.second; 136 if (RegisterFileIndex) { 137 RegisterMappingTracker &RMT = RegisterFiles[RegisterFileIndex]; 138 RMT.NumUsedPhysRegs -= Cost; 139 FreedPhysRegs[RegisterFileIndex] += Cost; 140 } 141 142 // Now update the default register mapping tracker. 143 RegisterFiles[0].NumUsedPhysRegs -= Cost; 144 FreedPhysRegs[0] += Cost; 145 } 146 147 void RegisterFile::addRegisterWrite(WriteRef Write, 148 MutableArrayRef<unsigned> UsedPhysRegs) { 149 WriteState &WS = *Write.getWriteState(); 150 MCPhysReg RegID = WS.getRegisterID(); 151 assert(RegID && "Adding an invalid register definition?"); 152 153 LLVM_DEBUG({ 154 dbgs() << "RegisterFile: addRegisterWrite [ " << Write.getSourceIndex() 155 << ", " << MRI.getName(RegID) << "]\n"; 156 }); 157 158 // If RenameAs is equal to RegID, then RegID is subject to register renaming 159 // and false dependencies on RegID are all eliminated. 160 161 // If RenameAs references the invalid register, then we optimistically assume 162 // that it can be renamed. In the absence of tablegen descriptors for register 163 // files, RenameAs is always set to the invalid register ID. In all other 164 // cases, RenameAs must be either equal to RegID, or it must reference a 165 // super-register of RegID. 166 167 // If RenameAs is a super-register of RegID, then a write to RegID has always 168 // a false dependency on RenameAs. The only exception is for when the write 169 // implicitly clears the upper portion of the underlying register. 170 // If a write clears its super-registers, then it is renamed as `RenameAs`. 171 bool IsWriteZero = WS.isWriteZero(); 172 bool IsEliminated = WS.isEliminated(); 173 bool ShouldAllocatePhysRegs = !IsWriteZero && !IsEliminated; 174 const RegisterRenamingInfo &RRI = RegisterMappings[RegID].second; 175 WS.setPRF(RRI.IndexPlusCost.first); 176 177 if (RRI.RenameAs && RRI.RenameAs != RegID) { 178 RegID = RRI.RenameAs; 179 WriteRef &OtherWrite = RegisterMappings[RegID].first; 180 181 if (!WS.clearsSuperRegisters()) { 182 // The processor keeps the definition of `RegID` together with register 183 // `RenameAs`. Since this partial write is not renamed, no physical 184 // register is allocated. 185 ShouldAllocatePhysRegs = false; 186 187 WriteState *OtherWS = OtherWrite.getWriteState(); 188 if (OtherWS && (OtherWrite.getSourceIndex() != Write.getSourceIndex())) { 189 // This partial write has a false dependency on RenameAs. 190 assert(!IsEliminated && "Unexpected partial update!"); 191 OtherWS->addUser(OtherWrite.getSourceIndex(), &WS); 192 } 193 } 194 } 195 196 // Update zero registers. 197 MCPhysReg ZeroRegisterID = 198 WS.clearsSuperRegisters() ? RegID : WS.getRegisterID(); 199 if (IsWriteZero) { 200 ZeroRegisters.setBit(ZeroRegisterID); 201 for (MCSubRegIterator I(ZeroRegisterID, &MRI); I.isValid(); ++I) 202 ZeroRegisters.setBit(*I); 203 } else { 204 ZeroRegisters.clearBit(ZeroRegisterID); 205 for (MCSubRegIterator I(ZeroRegisterID, &MRI); I.isValid(); ++I) 206 ZeroRegisters.clearBit(*I); 207 } 208 209 // If this is move has been eliminated, then the call to tryEliminateMove 210 // should have already updated all the register mappings. 211 if (!IsEliminated) { 212 // Update the mapping for register RegID including its sub-registers. 213 RegisterMappings[RegID].first = Write; 214 RegisterMappings[RegID].second.AliasRegID = 0U; 215 for (MCSubRegIterator I(RegID, &MRI); I.isValid(); ++I) { 216 RegisterMappings[*I].first = Write; 217 RegisterMappings[*I].second.AliasRegID = 0U; 218 } 219 220 // No physical registers are allocated for instructions that are optimized 221 // in hardware. For example, zero-latency data-dependency breaking 222 // instructions don't consume physical registers. 223 if (ShouldAllocatePhysRegs) 224 allocatePhysRegs(RegisterMappings[RegID].second, UsedPhysRegs); 225 } 226 227 if (!WS.clearsSuperRegisters()) 228 return; 229 230 for (MCSuperRegIterator I(RegID, &MRI); I.isValid(); ++I) { 231 if (!IsEliminated) { 232 RegisterMappings[*I].first = Write; 233 RegisterMappings[*I].second.AliasRegID = 0U; 234 } 235 236 if (IsWriteZero) 237 ZeroRegisters.setBit(*I); 238 else 239 ZeroRegisters.clearBit(*I); 240 } 241 } 242 243 void RegisterFile::removeRegisterWrite( 244 const WriteState &WS, MutableArrayRef<unsigned> FreedPhysRegs) { 245 // Early exit if this write was eliminated. A write eliminated at register 246 // renaming stage generates an alias, and it is not added to the PRF. 247 if (WS.isEliminated()) 248 return; 249 250 MCPhysReg RegID = WS.getRegisterID(); 251 252 assert(RegID != 0 && "Invalidating an already invalid register?"); 253 assert(WS.getCyclesLeft() != UNKNOWN_CYCLES && 254 "Invalidating a write of unknown cycles!"); 255 assert(WS.getCyclesLeft() <= 0 && "Invalid cycles left for this write!"); 256 257 bool ShouldFreePhysRegs = !WS.isWriteZero(); 258 MCPhysReg RenameAs = RegisterMappings[RegID].second.RenameAs; 259 if (RenameAs && RenameAs != RegID) { 260 RegID = RenameAs; 261 262 if (!WS.clearsSuperRegisters()) { 263 // Keep the definition of `RegID` together with register `RenameAs`. 264 ShouldFreePhysRegs = false; 265 } 266 } 267 268 if (ShouldFreePhysRegs) 269 freePhysRegs(RegisterMappings[RegID].second, FreedPhysRegs); 270 271 WriteRef &WR = RegisterMappings[RegID].first; 272 if (WR.getWriteState() == &WS) 273 WR.invalidate(); 274 275 for (MCSubRegIterator I(RegID, &MRI); I.isValid(); ++I) { 276 WriteRef &OtherWR = RegisterMappings[*I].first; 277 if (OtherWR.getWriteState() == &WS) 278 OtherWR.invalidate(); 279 } 280 281 if (!WS.clearsSuperRegisters()) 282 return; 283 284 for (MCSuperRegIterator I(RegID, &MRI); I.isValid(); ++I) { 285 WriteRef &OtherWR = RegisterMappings[*I].first; 286 if (OtherWR.getWriteState() == &WS) 287 OtherWR.invalidate(); 288 } 289 } 290 291 bool RegisterFile::tryEliminateMove(WriteState &WS, ReadState &RS) { 292 const RegisterMapping &RMFrom = RegisterMappings[RS.getRegisterID()]; 293 const RegisterMapping &RMTo = RegisterMappings[WS.getRegisterID()]; 294 295 // From and To must be owned by the same PRF. 296 const RegisterRenamingInfo &RRIFrom = RMFrom.second; 297 const RegisterRenamingInfo &RRITo = RMTo.second; 298 unsigned RegisterFileIndex = RRIFrom.IndexPlusCost.first; 299 if (RegisterFileIndex != RRITo.IndexPlusCost.first) 300 return false; 301 302 // We only allow move elimination for writes that update a full physical 303 // register. On X86, move elimination is possible with 32-bit general purpose 304 // registers because writes to those registers are not partial writes. If a 305 // register move is a partial write, then we conservatively assume that move 306 // elimination fails, since it would either trigger a partial update, or the 307 // issue of a merge opcode. 308 // 309 // Note that this constraint may be lifted in future. For example, we could 310 // make this model more flexible, and let users customize the set of registers 311 // (i.e. register classes) that allow move elimination. 312 // 313 // For now, we assume that there is a strong correlation between registers 314 // that allow move elimination, and how those same registers are renamed in 315 // hardware. 316 if (RRITo.RenameAs && RRITo.RenameAs != WS.getRegisterID()) { 317 // Early exit if the PRF doesn't support move elimination for this register. 318 if (!RegisterMappings[RRITo.RenameAs].second.AllowMoveElimination) 319 return false; 320 if (!WS.clearsSuperRegisters()) 321 return false; 322 } 323 324 RegisterMappingTracker &RMT = RegisterFiles[RegisterFileIndex]; 325 if (RMT.MaxMoveEliminatedPerCycle && 326 RMT.NumMoveEliminated == RMT.MaxMoveEliminatedPerCycle) 327 return false; 328 329 bool IsZeroMove = ZeroRegisters[RS.getRegisterID()]; 330 if (RMT.AllowZeroMoveEliminationOnly && !IsZeroMove) 331 return false; 332 333 // Construct an alias. 334 MCPhysReg AliasedReg = 335 RRIFrom.RenameAs ? RRIFrom.RenameAs : RS.getRegisterID(); 336 MCPhysReg AliasReg = RRITo.RenameAs ? RRITo.RenameAs : WS.getRegisterID(); 337 338 const RegisterRenamingInfo &RMAlias = RegisterMappings[AliasedReg].second; 339 if (RMAlias.AliasRegID) 340 AliasedReg = RMAlias.AliasRegID; 341 342 RegisterMappings[AliasReg].second.AliasRegID = AliasedReg; 343 for (MCSubRegIterator I(AliasReg, &MRI); I.isValid(); ++I) 344 RegisterMappings[*I].second.AliasRegID = AliasedReg; 345 346 if (IsZeroMove) { 347 WS.setWriteZero(); 348 RS.setReadZero(); 349 } 350 WS.setEliminated(); 351 RMT.NumMoveEliminated++; 352 353 return true; 354 } 355 356 void RegisterFile::collectWrites(const ReadState &RS, 357 SmallVectorImpl<WriteRef> &Writes) const { 358 MCPhysReg RegID = RS.getRegisterID(); 359 assert(RegID && RegID < RegisterMappings.size()); 360 LLVM_DEBUG(dbgs() << "RegisterFile: collecting writes for register " 361 << MRI.getName(RegID) << '\n'); 362 363 // Check if this is an alias. 364 const RegisterRenamingInfo &RRI = RegisterMappings[RegID].second; 365 if (RRI.AliasRegID) 366 RegID = RRI.AliasRegID; 367 368 const WriteRef &WR = RegisterMappings[RegID].first; 369 if (WR.isValid()) 370 Writes.push_back(WR); 371 372 // Handle potential partial register updates. 373 for (MCSubRegIterator I(RegID, &MRI); I.isValid(); ++I) { 374 const WriteRef &WR = RegisterMappings[*I].first; 375 if (WR.isValid()) 376 Writes.push_back(WR); 377 } 378 379 // Remove duplicate entries and resize the input vector. 380 if (Writes.size() > 1) { 381 sort(Writes, [](const WriteRef &Lhs, const WriteRef &Rhs) { 382 return Lhs.getWriteState() < Rhs.getWriteState(); 383 }); 384 auto It = std::unique(Writes.begin(), Writes.end()); 385 Writes.resize(std::distance(Writes.begin(), It)); 386 } 387 388 LLVM_DEBUG({ 389 for (const WriteRef &WR : Writes) { 390 const WriteState &WS = *WR.getWriteState(); 391 dbgs() << "[PRF] Found a dependent use of Register " 392 << MRI.getName(WS.getRegisterID()) << " (defined by instruction #" 393 << WR.getSourceIndex() << ")\n"; 394 } 395 }); 396 } 397 398 void RegisterFile::addRegisterRead(ReadState &RS, 399 const MCSubtargetInfo &STI) const { 400 MCPhysReg RegID = RS.getRegisterID(); 401 const RegisterRenamingInfo &RRI = RegisterMappings[RegID].second; 402 RS.setPRF(RRI.IndexPlusCost.first); 403 if (RS.isIndependentFromDef()) 404 return; 405 406 if (ZeroRegisters[RS.getRegisterID()]) 407 RS.setReadZero(); 408 409 SmallVector<WriteRef, 4> DependentWrites; 410 collectWrites(RS, DependentWrites); 411 RS.setDependentWrites(DependentWrites.size()); 412 413 // We know that this read depends on all the writes in DependentWrites. 414 // For each write, check if we have ReadAdvance information, and use it 415 // to figure out in how many cycles this read becomes available. 416 const ReadDescriptor &RD = RS.getDescriptor(); 417 const MCSchedModel &SM = STI.getSchedModel(); 418 const MCSchedClassDesc *SC = SM.getSchedClassDesc(RD.SchedClassID); 419 for (WriteRef &WR : DependentWrites) { 420 WriteState &WS = *WR.getWriteState(); 421 unsigned WriteResID = WS.getWriteResourceID(); 422 int ReadAdvance = STI.getReadAdvanceCycles(SC, RD.UseIndex, WriteResID); 423 WS.addUser(WR.getSourceIndex(), &RS, ReadAdvance); 424 } 425 } 426 427 unsigned RegisterFile::isAvailable(ArrayRef<MCPhysReg> Regs) const { 428 SmallVector<unsigned, 4> NumPhysRegs(getNumRegisterFiles()); 429 430 // Find how many new mappings must be created for each register file. 431 for (const MCPhysReg RegID : Regs) { 432 const RegisterRenamingInfo &RRI = RegisterMappings[RegID].second; 433 const IndexPlusCostPairTy &Entry = RRI.IndexPlusCost; 434 if (Entry.first) 435 NumPhysRegs[Entry.first] += Entry.second; 436 NumPhysRegs[0] += Entry.second; 437 } 438 439 unsigned Response = 0; 440 for (unsigned I = 0, E = getNumRegisterFiles(); I < E; ++I) { 441 unsigned NumRegs = NumPhysRegs[I]; 442 if (!NumRegs) 443 continue; 444 445 const RegisterMappingTracker &RMT = RegisterFiles[I]; 446 if (!RMT.NumPhysRegs) { 447 // The register file has an unbounded number of microarchitectural 448 // registers. 449 continue; 450 } 451 452 if (RMT.NumPhysRegs < NumRegs) { 453 // The current register file is too small. This may occur if the number of 454 // microarchitectural registers in register file #0 was changed by the 455 // users via flag -reg-file-size. Alternatively, the scheduling model 456 // specified a too small number of registers for this register file. 457 LLVM_DEBUG(dbgs() << "Not enough registers in the register file.\n"); 458 459 // FIXME: Normalize the instruction register count to match the 460 // NumPhysRegs value. This is a highly unusual case, and is not expected 461 // to occur. This normalization is hiding an inconsistency in either the 462 // scheduling model or in the value that the user might have specified 463 // for NumPhysRegs. 464 NumRegs = RMT.NumPhysRegs; 465 } 466 467 if (RMT.NumPhysRegs < (RMT.NumUsedPhysRegs + NumRegs)) 468 Response |= (1U << I); 469 } 470 471 return Response; 472 } 473 474 #ifndef NDEBUG 475 void RegisterFile::dump() const { 476 for (unsigned I = 0, E = MRI.getNumRegs(); I < E; ++I) { 477 const RegisterMapping &RM = RegisterMappings[I]; 478 const RegisterRenamingInfo &RRI = RM.second; 479 if (ZeroRegisters[I]) { 480 dbgs() << MRI.getName(I) << ", " << I 481 << ", PRF=" << RRI.IndexPlusCost.first 482 << ", Cost=" << RRI.IndexPlusCost.second 483 << ", RenameAs=" << RRI.RenameAs << ", IsZero=" << ZeroRegisters[I] 484 << ","; 485 RM.first.dump(); 486 dbgs() << '\n'; 487 } 488 } 489 490 for (unsigned I = 0, E = getNumRegisterFiles(); I < E; ++I) { 491 dbgs() << "Register File #" << I; 492 const RegisterMappingTracker &RMT = RegisterFiles[I]; 493 dbgs() << "\n TotalMappings: " << RMT.NumPhysRegs 494 << "\n NumUsedMappings: " << RMT.NumUsedPhysRegs << '\n'; 495 } 496 } 497 #endif 498 499 } // namespace mca 500 } // namespace llvm 501