1 //===--------------------- RegisterFile.cpp ---------------------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
11 /// This file defines a register mapping file class. This class is responsible
12 /// for managing hardware register files and the tracking of data dependencies
13 /// between registers.
15 //===----------------------------------------------------------------------===//
17 #include "llvm/MCA/HardwareUnits/RegisterFile.h"
18 #include "llvm/MCA/Instruction.h"
19 #include "llvm/Support/Debug.h"
21 #define DEBUG_TYPE "llvm-mca"
26 RegisterFile::RegisterFile(const MCSchedModel &SM, const MCRegisterInfo &mri,
29 RegisterMappings(mri.getNumRegs(), {WriteRef(), RegisterRenamingInfo()}),
30 ZeroRegisters(mri.getNumRegs(), false) {
31 initialize(SM, NumRegs);
34 void RegisterFile::initialize(const MCSchedModel &SM, unsigned NumRegs) {
35 // Create a default register file that "sees" all the machine registers
36 // declared by the target. The number of physical registers in the default
37 // register file is set equal to `NumRegs`. A value of zero for `NumRegs`
38 // means: this register file has an unbounded number of physical registers.
39 RegisterFiles.emplace_back(NumRegs);
40 if (!SM.hasExtraProcessorInfo())
43 // For each user defined register file, allocate a RegisterMappingTracker
44 // object. The size of every register file, as well as the mapping between
45 // register files and register classes is specified via tablegen.
46 const MCExtraProcessorInfo &Info = SM.getExtraProcessorInfo();
48 // Skip invalid register file at index 0.
49 for (unsigned I = 1, E = Info.NumRegisterFiles; I < E; ++I) {
50 const MCRegisterFileDesc &RF = Info.RegisterFiles[I];
51 assert(RF.NumPhysRegs && "Invalid PRF with zero physical registers!");
53 // The cost of a register definition is equivalent to the number of
54 // physical registers that are allocated at register renaming stage.
55 unsigned Length = RF.NumRegisterCostEntries;
56 const MCRegisterCostEntry *FirstElt =
57 &Info.RegisterCostTable[RF.RegisterCostEntryIdx];
58 addRegisterFile(RF, ArrayRef<MCRegisterCostEntry>(FirstElt, Length));
62 void RegisterFile::cycleStart() {
63 for (RegisterMappingTracker &RMT : RegisterFiles)
64 RMT.NumMoveEliminated = 0;
67 void RegisterFile::addRegisterFile(const MCRegisterFileDesc &RF,
68 ArrayRef<MCRegisterCostEntry> Entries) {
69 // A default register file is always allocated at index #0. That register file
70 // is mainly used to count the total number of mappings created by all
71 // register files at runtime. Users can limit the number of available physical
72 // registers in register file #0 through the command line flag
73 // `-register-file-size`.
74 unsigned RegisterFileIndex = RegisterFiles.size();
75 RegisterFiles.emplace_back(RF.NumPhysRegs, RF.MaxMovesEliminatedPerCycle,
76 RF.AllowZeroMoveEliminationOnly);
78 // Special case where there is no register class identifier in the set.
79 // An empty set of register classes means: this register file contains all
80 // the physical registers specified by the target.
81 // We optimistically assume that a register can be renamed at the cost of a
82 // single physical register. The constructor of RegisterFile ensures that
83 // a RegisterMapping exists for each logical register defined by the Target.
87 // Now update the cost of individual registers.
88 for (const MCRegisterCostEntry &RCE : Entries) {
89 const MCRegisterClass &RC = MRI.getRegClass(RCE.RegisterClassID);
90 for (const MCPhysReg Reg : RC) {
91 RegisterRenamingInfo &Entry = RegisterMappings[Reg].second;
92 IndexPlusCostPairTy &IPC = Entry.IndexPlusCost;
93 if (IPC.first && IPC.first != RegisterFileIndex) {
94 // The only register file that is allowed to overlap is the default
95 // register file at index #0. The analysis is inaccurate if register
97 errs() << "warning: register " << MRI.getName(Reg)
98 << " defined in multiple register files.";
100 IPC = std::make_pair(RegisterFileIndex, RCE.Cost);
101 Entry.RenameAs = Reg;
102 Entry.AllowMoveElimination = RCE.AllowMoveElimination;
104 // Assume the same cost for each sub-register.
105 for (MCSubRegIterator I(Reg, &MRI); I.isValid(); ++I) {
106 RegisterRenamingInfo &OtherEntry = RegisterMappings[*I].second;
107 if (!OtherEntry.IndexPlusCost.first &&
108 (!OtherEntry.RenameAs ||
109 MRI.isSuperRegister(*I, OtherEntry.RenameAs))) {
110 OtherEntry.IndexPlusCost = IPC;
111 OtherEntry.RenameAs = Reg;
118 void RegisterFile::allocatePhysRegs(const RegisterRenamingInfo &Entry,
119 MutableArrayRef<unsigned> UsedPhysRegs) {
120 unsigned RegisterFileIndex = Entry.IndexPlusCost.first;
121 unsigned Cost = Entry.IndexPlusCost.second;
122 if (RegisterFileIndex) {
123 RegisterMappingTracker &RMT = RegisterFiles[RegisterFileIndex];
124 RMT.NumUsedPhysRegs += Cost;
125 UsedPhysRegs[RegisterFileIndex] += Cost;
128 // Now update the default register mapping tracker.
129 RegisterFiles[0].NumUsedPhysRegs += Cost;
130 UsedPhysRegs[0] += Cost;
133 void RegisterFile::freePhysRegs(const RegisterRenamingInfo &Entry,
134 MutableArrayRef<unsigned> FreedPhysRegs) {
135 unsigned RegisterFileIndex = Entry.IndexPlusCost.first;
136 unsigned Cost = Entry.IndexPlusCost.second;
137 if (RegisterFileIndex) {
138 RegisterMappingTracker &RMT = RegisterFiles[RegisterFileIndex];
139 RMT.NumUsedPhysRegs -= Cost;
140 FreedPhysRegs[RegisterFileIndex] += Cost;
143 // Now update the default register mapping tracker.
144 RegisterFiles[0].NumUsedPhysRegs -= Cost;
145 FreedPhysRegs[0] += Cost;
148 void RegisterFile::addRegisterWrite(WriteRef Write,
149 MutableArrayRef<unsigned> UsedPhysRegs) {
150 WriteState &WS = *Write.getWriteState();
151 unsigned RegID = WS.getRegisterID();
152 assert(RegID && "Adding an invalid register definition?");
155 dbgs() << "RegisterFile: addRegisterWrite [ " << Write.getSourceIndex()
156 << ", " << MRI.getName(RegID) << "]\n";
159 // If RenameAs is equal to RegID, then RegID is subject to register renaming
160 // and false dependencies on RegID are all eliminated.
162 // If RenameAs references the invalid register, then we optimistically assume
163 // that it can be renamed. In the absence of tablegen descriptors for register
164 // files, RenameAs is always set to the invalid register ID. In all other
165 // cases, RenameAs must be either equal to RegID, or it must reference a
166 // super-register of RegID.
168 // If RenameAs is a super-register of RegID, then a write to RegID has always
169 // a false dependency on RenameAs. The only exception is for when the write
170 // implicitly clears the upper portion of the underlying register.
171 // If a write clears its super-registers, then it is renamed as `RenameAs`.
172 bool IsWriteZero = WS.isWriteZero();
173 bool IsEliminated = WS.isEliminated();
174 bool ShouldAllocatePhysRegs = !IsWriteZero && !IsEliminated;
175 const RegisterRenamingInfo &RRI = RegisterMappings[RegID].second;
176 WS.setPRF(RRI.IndexPlusCost.first);
178 if (RRI.RenameAs && RRI.RenameAs != RegID) {
179 RegID = RRI.RenameAs;
180 WriteRef &OtherWrite = RegisterMappings[RegID].first;
182 if (!WS.clearsSuperRegisters()) {
183 // The processor keeps the definition of `RegID` together with register
184 // `RenameAs`. Since this partial write is not renamed, no physical
185 // register is allocated.
186 ShouldAllocatePhysRegs = false;
188 WriteState *OtherWS = OtherWrite.getWriteState();
189 if (OtherWS && (OtherWrite.getSourceIndex() != Write.getSourceIndex())) {
190 // This partial write has a false dependency on RenameAs.
191 assert(!IsEliminated && "Unexpected partial update!");
192 OtherWS->addUser(&WS);
197 // Update zero registers.
198 unsigned ZeroRegisterID =
199 WS.clearsSuperRegisters() ? RegID : WS.getRegisterID();
201 ZeroRegisters.setBit(ZeroRegisterID);
202 for (MCSubRegIterator I(ZeroRegisterID, &MRI); I.isValid(); ++I)
203 ZeroRegisters.setBit(*I);
205 ZeroRegisters.clearBit(ZeroRegisterID);
206 for (MCSubRegIterator I(ZeroRegisterID, &MRI); I.isValid(); ++I)
207 ZeroRegisters.clearBit(*I);
210 // If this is move has been eliminated, then the call to tryEliminateMove
211 // should have already updated all the register mappings.
213 // Update the mapping for register RegID including its sub-registers.
214 RegisterMappings[RegID].first = Write;
215 RegisterMappings[RegID].second.AliasRegID = 0U;
216 for (MCSubRegIterator I(RegID, &MRI); I.isValid(); ++I) {
217 RegisterMappings[*I].first = Write;
218 RegisterMappings[*I].second.AliasRegID = 0U;
221 // No physical registers are allocated for instructions that are optimized
222 // in hardware. For example, zero-latency data-dependency breaking
223 // instructions don't consume physical registers.
224 if (ShouldAllocatePhysRegs)
225 allocatePhysRegs(RegisterMappings[RegID].second, UsedPhysRegs);
228 if (!WS.clearsSuperRegisters())
231 for (MCSuperRegIterator I(RegID, &MRI); I.isValid(); ++I) {
233 RegisterMappings[*I].first = Write;
234 RegisterMappings[*I].second.AliasRegID = 0U;
238 ZeroRegisters.setBit(*I);
240 ZeroRegisters.clearBit(*I);
244 void RegisterFile::removeRegisterWrite(
245 const WriteState &WS, MutableArrayRef<unsigned> FreedPhysRegs) {
246 // Early exit if this write was eliminated. A write eliminated at register
247 // renaming stage generates an alias, and it is not added to the PRF.
248 if (WS.isEliminated())
251 unsigned RegID = WS.getRegisterID();
253 assert(RegID != 0 && "Invalidating an already invalid register?");
254 assert(WS.getCyclesLeft() != UNKNOWN_CYCLES &&
255 "Invalidating a write of unknown cycles!");
256 assert(WS.getCyclesLeft() <= 0 && "Invalid cycles left for this write!");
258 bool ShouldFreePhysRegs = !WS.isWriteZero();
259 unsigned RenameAs = RegisterMappings[RegID].second.RenameAs;
260 if (RenameAs && RenameAs != RegID) {
263 if (!WS.clearsSuperRegisters()) {
264 // Keep the definition of `RegID` together with register `RenameAs`.
265 ShouldFreePhysRegs = false;
269 if (ShouldFreePhysRegs)
270 freePhysRegs(RegisterMappings[RegID].second, FreedPhysRegs);
272 WriteRef &WR = RegisterMappings[RegID].first;
273 if (WR.getWriteState() == &WS)
276 for (MCSubRegIterator I(RegID, &MRI); I.isValid(); ++I) {
277 WriteRef &OtherWR = RegisterMappings[*I].first;
278 if (OtherWR.getWriteState() == &WS)
279 OtherWR.invalidate();
282 if (!WS.clearsSuperRegisters())
285 for (MCSuperRegIterator I(RegID, &MRI); I.isValid(); ++I) {
286 WriteRef &OtherWR = RegisterMappings[*I].first;
287 if (OtherWR.getWriteState() == &WS)
288 OtherWR.invalidate();
292 bool RegisterFile::tryEliminateMove(WriteState &WS, ReadState &RS) {
293 const RegisterMapping &RMFrom = RegisterMappings[RS.getRegisterID()];
294 const RegisterMapping &RMTo = RegisterMappings[WS.getRegisterID()];
296 // From and To must be owned by the same PRF.
297 const RegisterRenamingInfo &RRIFrom = RMFrom.second;
298 const RegisterRenamingInfo &RRITo = RMTo.second;
299 unsigned RegisterFileIndex = RRIFrom.IndexPlusCost.first;
300 if (RegisterFileIndex != RRITo.IndexPlusCost.first)
303 // We only allow move elimination for writes that update a full physical
304 // register. On X86, move elimination is possible with 32-bit general purpose
305 // registers because writes to those registers are not partial writes. If a
306 // register move is a partial write, then we conservatively assume that move
307 // elimination fails, since it would either trigger a partial update, or the
308 // issue of a merge opcode.
310 // Note that this constraint may be lifted in future. For example, we could
311 // make this model more flexible, and let users customize the set of registers
312 // (i.e. register classes) that allow move elimination.
314 // For now, we assume that there is a strong correlation between registers
315 // that allow move elimination, and how those same registers are renamed in
317 if (RRITo.RenameAs && RRITo.RenameAs != WS.getRegisterID()) {
318 // Early exit if the PRF doesn't support move elimination for this register.
319 if (!RegisterMappings[RRITo.RenameAs].second.AllowMoveElimination)
321 if (!WS.clearsSuperRegisters())
325 RegisterMappingTracker &RMT = RegisterFiles[RegisterFileIndex];
326 if (RMT.MaxMoveEliminatedPerCycle &&
327 RMT.NumMoveEliminated == RMT.MaxMoveEliminatedPerCycle)
330 bool IsZeroMove = ZeroRegisters[RS.getRegisterID()];
331 if (RMT.AllowZeroMoveEliminationOnly && !IsZeroMove)
334 MCPhysReg FromReg = RS.getRegisterID();
335 MCPhysReg ToReg = WS.getRegisterID();
337 // Construct an alias.
338 MCPhysReg AliasReg = FromReg;
339 if (RRIFrom.RenameAs)
340 AliasReg = RRIFrom.RenameAs;
342 const RegisterRenamingInfo &RMAlias = RegisterMappings[AliasReg].second;
343 if (RMAlias.AliasRegID)
344 AliasReg = RMAlias.AliasRegID;
346 if (AliasReg != ToReg) {
347 RegisterMappings[ToReg].second.AliasRegID = AliasReg;
348 for (MCSubRegIterator I(ToReg, &MRI); I.isValid(); ++I)
349 RegisterMappings[*I].second.AliasRegID = AliasReg;
352 RMT.NumMoveEliminated++;
362 void RegisterFile::collectWrites(const ReadState &RS,
363 SmallVectorImpl<WriteRef> &Writes) const {
364 unsigned RegID = RS.getRegisterID();
365 assert(RegID && RegID < RegisterMappings.size());
366 LLVM_DEBUG(dbgs() << "RegisterFile: collecting writes for register "
367 << MRI.getName(RegID) << '\n');
369 // Check if this is an alias.
370 const RegisterRenamingInfo &RRI = RegisterMappings[RegID].second;
372 RegID = RRI.AliasRegID;
374 const WriteRef &WR = RegisterMappings[RegID].first;
376 Writes.push_back(WR);
378 // Handle potential partial register updates.
379 for (MCSubRegIterator I(RegID, &MRI); I.isValid(); ++I) {
380 const WriteRef &WR = RegisterMappings[*I].first;
382 Writes.push_back(WR);
385 // Remove duplicate entries and resize the input vector.
386 if (Writes.size() > 1) {
387 sort(Writes, [](const WriteRef &Lhs, const WriteRef &Rhs) {
388 return Lhs.getWriteState() < Rhs.getWriteState();
390 auto It = std::unique(Writes.begin(), Writes.end());
391 Writes.resize(std::distance(Writes.begin(), It));
395 for (const WriteRef &WR : Writes) {
396 const WriteState &WS = *WR.getWriteState();
397 dbgs() << "[PRF] Found a dependent use of Register "
398 << MRI.getName(WS.getRegisterID()) << " (defined by instruction #"
399 << WR.getSourceIndex() << ")\n";
404 void RegisterFile::addRegisterRead(ReadState &RS,
405 SmallVectorImpl<WriteRef> &Defs) const {
406 unsigned RegID = RS.getRegisterID();
407 const RegisterRenamingInfo &RRI = RegisterMappings[RegID].second;
408 RS.setPRF(RRI.IndexPlusCost.first);
409 if (RS.isIndependentFromDef())
412 if (ZeroRegisters[RS.getRegisterID()])
414 collectWrites(RS, Defs);
415 RS.setDependentWrites(Defs.size());
418 unsigned RegisterFile::isAvailable(ArrayRef<unsigned> Regs) const {
419 SmallVector<unsigned, 4> NumPhysRegs(getNumRegisterFiles());
421 // Find how many new mappings must be created for each register file.
422 for (const unsigned RegID : Regs) {
423 const RegisterRenamingInfo &RRI = RegisterMappings[RegID].second;
424 const IndexPlusCostPairTy &Entry = RRI.IndexPlusCost;
426 NumPhysRegs[Entry.first] += Entry.second;
427 NumPhysRegs[0] += Entry.second;
430 unsigned Response = 0;
431 for (unsigned I = 0, E = getNumRegisterFiles(); I < E; ++I) {
432 unsigned NumRegs = NumPhysRegs[I];
436 const RegisterMappingTracker &RMT = RegisterFiles[I];
437 if (!RMT.NumPhysRegs) {
438 // The register file has an unbounded number of microarchitectural
443 if (RMT.NumPhysRegs < NumRegs) {
444 // The current register file is too small. This may occur if the number of
445 // microarchitectural registers in register file #0 was changed by the
446 // users via flag -reg-file-size. Alternatively, the scheduling model
447 // specified a too small number of registers for this register file.
448 LLVM_DEBUG(dbgs() << "Not enough registers in the register file.\n");
450 // FIXME: Normalize the instruction register count to match the
451 // NumPhysRegs value. This is a highly unusual case, and is not expected
452 // to occur. This normalization is hiding an inconsistency in either the
453 // scheduling model or in the value that the user might have specified
455 NumRegs = RMT.NumPhysRegs;
458 if (RMT.NumPhysRegs < (RMT.NumUsedPhysRegs + NumRegs))
459 Response |= (1U << I);
466 void RegisterFile::dump() const {
467 for (unsigned I = 0, E = MRI.getNumRegs(); I < E; ++I) {
468 const RegisterMapping &RM = RegisterMappings[I];
469 const RegisterRenamingInfo &RRI = RM.second;
470 if (ZeroRegisters[I]) {
471 dbgs() << MRI.getName(I) << ", " << I
472 << ", PRF=" << RRI.IndexPlusCost.first
473 << ", Cost=" << RRI.IndexPlusCost.second
474 << ", RenameAs=" << RRI.RenameAs << ", IsZero=" << ZeroRegisters[I]
481 for (unsigned I = 0, E = getNumRegisterFiles(); I < E; ++I) {
482 dbgs() << "Register File #" << I;
483 const RegisterMappingTracker &RMT = RegisterFiles[I];
484 dbgs() << "\n TotalMappings: " << RMT.NumPhysRegs
485 << "\n NumUsedMappings: " << RMT.NumUsedPhysRegs << '\n';