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