LLVM  14.0.0git
RegisterFile.cpp
Go to the documentation of this file.
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 
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 
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 
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 
59  if (Write)
60  return Write->getRegisterID();
61  return RegisterID;
62 }
63 
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.
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 
101  for (RegisterMappingTracker &RMT : RegisterFiles)
102  RMT.NumMoveEliminated = 0;
103 }
104 
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,
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();
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 
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 
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 
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 
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 
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 
498  assert(WR.hasKnownWriteBackCycle() && "Write hasn't been committed yet!");
499  return CurrentCycle - WR.getWriteBackCycle();
500 }
501 
503  const MCSubtargetInfo &STI, const ReadState &RS,
505  SmallVectorImpl<WriteRef> &CommittedWrites) const {
506  const ReadDescriptor &RD = RS.getDescriptor();
507  const MCSchedModel &SM = STI.getSchedModel();
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 
569  const ReadState &RS) const {
570  RAWHazard Hazard;
572  SmallVector<WriteRef, 4> CommittedWrites;
573 
574  const MCSchedModel &SM = STI.getSchedModel();
575  const ReadDescriptor &RD = RS.getDescriptor();
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 
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();
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 
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
llvm::mca::ReadDescriptor::UseIndex
unsigned UseIndex
Definition: Instruction.h:170
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
Reg
unsigned Reg
Definition: MachineSink.cpp:1566
llvm::MCRegisterInfo::getName
const char * getName(MCRegister RegNo) const
Return the human-readable symbolic target-specific name for the specified physical register.
Definition: MCRegisterInfo.h:485
llvm::mca::RegisterFile::getElapsedCyclesFromWriteBack
unsigned getElapsedCyclesFromWriteBack(const WriteRef &WR) const
Definition: RegisterFile.cpp:497
llvm::mca::ReadDescriptor::SchedClassID
unsigned SchedClassID
Definition: Instruction.h:175
llvm::mca::RegisterFile::tryEliminateMoveOrSwap
bool tryEliminateMoveOrSwap(MutableArrayRef< WriteState > Writes, MutableArrayRef< ReadState > Reads)
Definition: RegisterFile.cpp:426
llvm::MCSubtargetInfo::getSchedModel
const MCSchedModel & getSchedModel() const
Get the machine model for this subtarget's CPU.
Definition: MCSubtargetInfo.h:162
llvm::mca::RegisterFile::removeRegisterWrite
void removeRegisterWrite(const WriteState &WS, MutableArrayRef< unsigned > FreedPhysRegs)
Definition: RegisterFile.cpp:332
llvm::mca::WriteState::setEliminated
void setEliminated()
Definition: Instruction.h:305
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1168
llvm::mca::RegisterFile::checkRAWHazards
RAWHazard checkRAWHazards(const MCSubtargetInfo &STI, const ReadState &RS) const
Definition: RegisterFile.cpp:568
llvm::MCRegisterInfo::getNumRegs
unsigned getNumRegs() const
Return the number of registers this target has (useful for sizing arrays holding per register informa...
Definition: MCRegisterInfo.h:491
llvm::MCRegisterFileDesc::MaxMovesEliminatedPerCycle
uint16_t MaxMovesEliminatedPerCycle
Definition: MCSchedule.h:166
llvm::mca::WriteRef::getWriteState
const WriteState * getWriteState() const
Definition: RegisterFile.h:56
llvm::mca::RegisterFile::RAWHazard::CyclesLeft
int CyclesLeft
Definition: RegisterFile.h:241
llvm::mca::WriteState::dump
void dump() const
Definition: Instruction.cpp:125
llvm::mca::WriteRef::getRegisterID
MCPhysReg getRegisterID() const
Definition: RegisterFile.cpp:58
llvm::MCRegisterFileDesc::RegisterCostEntryIdx
uint16_t RegisterCostEntryIdx
Definition: MCSchedule.h:163
llvm::errs
raw_fd_ostream & errs()
This returns a reference to a raw_ostream for standard error.
Definition: raw_ostream.cpp:892
llvm::mca::Instruction
An instruction propagated through the simulated instruction pipeline.
Definition: Instruction.h:569
llvm::MCRegisterFileDesc
A register file descriptor.
Definition: MCSchedule.h:158
llvm::mca::RegisterFile::RAWHazard
Definition: RegisterFile.h:239
llvm::mca::WriteRef::getSourceIndex
unsigned getSourceIndex() const
Definition: RegisterFile.h:53
llvm::mca::InstructionBase::getDefs
SmallVectorImpl< WriteState > & getDefs()
Definition: Instruction.h:524
llvm::ArrayRef::empty
bool empty() const
empty - Check if the array is empty.
Definition: ArrayRef.h:160
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
llvm::mca::RegisterFile::cycleStart
void cycleStart()
Definition: RegisterFile.cpp:100
llvm::MCRegisterClass
MCRegisterClass - Base class of TargetRegisterClass.
Definition: MCRegisterInfo.h:31
llvm::mca::WriteState::setWriteZero
void setWriteZero()
Definition: Instruction.h:304
Instruction.h
llvm::mca::RegisterFile::getNumRegisterFiles
unsigned getNumRegisterFiles() const
Definition: RegisterFile.h:293
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
llvm::mca::RegisterFile::isAvailable
unsigned isAvailable(ArrayRef< MCPhysReg > Regs) const
Definition: RegisterFile.cpp:660
llvm::MCRegisterFileDesc::NumRegisterCostEntries
uint16_t NumRegisterCostEntries
Definition: MCSchedule.h:161
llvm::MCRegisterInfo::getRegClass
const MCRegisterClass & getRegClass(unsigned i) const
Returns the register class associated with the enumeration value.
Definition: MCRegisterInfo.h:543
llvm::mca::WriteState::isExecuted
bool isExecuted() const
Definition: Instruction.h:298
llvm::MutableArrayRef
MutableArrayRef - Represent a mutable reference to an array (0 or more elements consecutively in memo...
Definition: ArrayRef.h:307
llvm::PPCISD::SC
@ SC
CHAIN = SC CHAIN, Imm128 - System call.
Definition: PPCISelLowering.h:410
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::MCSchedModel::getExtraProcessorInfo
const MCExtraProcessorInfo & getExtraProcessorInfo() const
Definition: MCSchedule.h:323
llvm::MCSchedClassDesc
Summarize the scheduling resources required for an instruction of a particular scheduling class.
Definition: MCSchedule.h:110
llvm::mca::WriteState::setPRF
void setPRF(unsigned PRF)
Definition: Instruction.h:311
llvm::mca::ReadState
Tracks register operand latency in cycles.
Definition: Instruction.h:326
llvm::SmallVectorImpl::resize
void resize(size_type N)
Definition: SmallVector.h:606
llvm::mca::WriteState::getCyclesLeft
int getCyclesLeft() const
Definition: Instruction.h:258
Info
Analysis containing CSE Info
Definition: CSEInfo.cpp:27
llvm::mca::WriteState::addUser
void addUser(unsigned IID, ReadState *Use, int ReadAdvance)
Definition: Instruction.cpp:72
llvm::mca::WriteState::getLatency
unsigned getLatency() const
Definition: Instruction.h:263
llvm::mca::RegisterFile::RegisterFile
RegisterFile(const MCSchedModel &SM, const MCRegisterInfo &mri, unsigned NumRegs=0)
Definition: RegisterFile.cpp:64
llvm::mca::WriteRef
A reference to a register write.
Definition: RegisterFile.h:38
llvm::mca::WriteRef::getWriteBackCycle
unsigned getWriteBackCycle() const
Definition: RegisterFile.cpp:490
llvm::mca::RegisterFile::RAWHazard::isValid
bool isValid() const
Definition: RegisterFile.h:244
llvm::mca::Instruction::isExecuted
bool isExecuted() const
Definition: Instruction.h:655
llvm::mca::RegisterFile::canEliminateMove
bool canEliminateMove(const WriteState &WS, const ReadState &RS, unsigned PRFIndex) const
Definition: RegisterFile.cpp:384
llvm::mca::WriteRef::isWriteZero
bool isWriteZero() const
Definition: RegisterFile.cpp:47
llvm::mca::ReadState::setPRF
void setPRF(unsigned ID)
Definition: Instruction.h:383
llvm::mca::WriteState::isWriteZero
bool isWriteZero() const
Definition: Instruction.h:288
llvm::mca::WriteRef::hasKnownWriteBackCycle
bool hasKnownWriteBackCycle() const
Definition: RegisterFile.cpp:43
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::MCPhysReg
uint16_t MCPhysReg
An unsigned integer type large enough to represent all physical registers, but not necessarily virtua...
Definition: MCRegister.h:20
llvm::MCSchedModel::hasExtraProcessorInfo
bool hasExtraProcessorInfo() const
Definition: MCSchedule.h:316
llvm::mca::WriteState::getRegisterID
MCPhysReg getRegisterID() const
Definition: Instruction.h:260
llvm::APInt::setBitVal
void setBitVal(unsigned BitPosition, bool BitValue)
Set a given bit to a given value.
Definition: APInt.h:1285
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::mca::WriteRef::WriteRef
WriteRef()
Definition: RegisterFile.h:48
llvm::mca::WriteState::clearsSuperRegisters
bool clearsSuperRegisters() const
Definition: Instruction.h:287
llvm::MCRegisterCostEntry
Specify the cost of a register definition in terms of number of physical register allocated at regist...
Definition: MCSchedule.h:143
llvm::mca::UNKNOWN_CYCLES
constexpr int UNKNOWN_CYCLES
Definition: Instruction.h:34
llvm::MCSuperRegIterator
MCSuperRegIterator enumerates all super-registers of Reg.
Definition: MCRegisterInfo.h:641
llvm::MCRegisterFileDesc::NumPhysRegs
uint16_t NumPhysRegs
Definition: MCSchedule.h:160
llvm::mca::ReadState::isIndependentFromDef
bool isIndependentFromDef() const
Definition: Instruction.h:371
llvm::mca::ReadState::getRegisterID
MCPhysReg getRegisterID() const
Definition: Instruction.h:363
llvm::AArch64::RM
@ RM
Definition: AArch64ISelLowering.h:472
llvm::mca::ReadState::setDependentWrites
void setDependentWrites(unsigned Writes)
Definition: Instruction.h:376
llvm::ArrayRef
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:32
llvm::mca::RegisterFile::RAWHazard::RegisterID
MCPhysReg RegisterID
Definition: RegisterFile.h:240
llvm::mca::WriteRef::getWriteResourceID
unsigned getWriteResourceID() const
Definition: RegisterFile.cpp:52
if
if(llvm_vc STREQUAL "") set(fake_version_inc "$
Definition: CMakeLists.txt:14
llvm::mca::RegisterFile::onInstructionExecuted
void onInstructionExecuted(Instruction *IS)
Definition: RegisterFile.cpp:105
llvm::MCRegisterInfo
MCRegisterInfo base class - We assume that the target defines a static array of MCRegisterDesc object...
Definition: MCRegisterInfo.h:135
MRI
unsigned const MachineRegisterInfo * MRI
Definition: AArch64AdvSIMDScalarPass.cpp:105
llvm::mca::RegisterFile::addRegisterRead
void addRegisterRead(ReadState &RS, const MCSubtargetInfo &STI) const
Definition: RegisterFile.cpp:618
llvm::mca::WriteState::getWriteResourceID
unsigned getWriteResourceID() const
Definition: Instruction.h:259
llvm::mca::ReadState::writeStartEvent
void writeStartEvent(unsigned IID, MCPhysReg RegID, unsigned Cycles)
Definition: Instruction.cpp:30
llvm::MCRegisterFileDesc::AllowZeroMoveEliminationOnly
bool AllowZeroMoveEliminationOnly
Definition: MCSchedule.h:169
llvm::mca::ReadDescriptor
A register read descriptor.
Definition: Instruction.h:163
uint16_t
llvm::mca::RegisterFile::collectWrites
void collectWrites(const MCSubtargetInfo &STI, const ReadState &RS, SmallVectorImpl< WriteRef > &Writes, SmallVectorImpl< WriteRef > &CommittedWrites) const
Definition: RegisterFile.cpp:502
llvm::mca::WriteRef::dump
void dump() const
Definition: RegisterFile.cpp:709
llvm::mca::ReadState::setReadZero
void setReadZero()
Definition: Instruction.h:382
llvm::sort
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1488
llvm::mca::RegisterFile::addRegisterWrite
void addRegisterWrite(WriteRef Write, MutableArrayRef< unsigned > UsedPhysRegs)
Definition: RegisterFile.cpp:228
llvm::mca::WriteRef::isValid
bool isValid() const
Definition: RegisterFile.h:66
llvm::MCSchedModel
Machine model for scheduling, bundling, and heuristics.
Definition: MCSchedule.h:245
llvm::unique
auto unique(Range &&R, Predicate P)
Definition: STLExtras.h:1700
llvm::mca::ReadState::getDescriptor
const ReadDescriptor & getDescriptor() const
Definition: Instruction.h:361
llvm::MCSubRegIterator
MCSubRegIterator enumerates all sub-registers of Reg.
Definition: MCRegisterInfo.h:594
llvm::MCRegisterInfo::isSuperRegister
bool isSuperRegister(MCRegister RegA, MCRegister RegB) const
Returns true if RegB is a super-register of RegA.
Definition: MCRegisterInfo.h:656
llvm::MCSubtargetInfo::getReadAdvanceCycles
int getReadAdvanceCycles(const MCSchedClassDesc *SC, unsigned UseIdx, unsigned WriteResID) const
Definition: MCSubtargetInfo.h:183
llvm::ArrayRef::size
size_t size() const
size - Get the array size.
Definition: ArrayRef.h:165
llvm::max
Align max(MaybeAlign Lhs, Align Rhs)
Definition: Alignment.h:340
llvm::MCSchedModel::getSchedClassDesc
const MCSchedClassDesc * getSchedClassDesc(unsigned SchedClassIdx) const
Definition: MCSchedule.h:347
llvm::SmallVectorImpl
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:43
RegisterFile.h
llvm::MCSubtargetInfo
Generic base class for all target subtargets.
Definition: MCSubtargetInfo.h:75
llvm::mca::WriteState
Tracks uses of a register definition (e.g.
Definition: Instruction.h:197
Debug.h
llvm::mca::WriteState::isEliminated
bool isEliminated() const
Definition: Instruction.h:289
llvm::mca::WriteRef::notifyExecuted
void notifyExecuted(unsigned Cycle)
Definition: RegisterFile.cpp:38
llvm::MCExtraProcessorInfo
Provide extra details about the machine processor.
Definition: MCSchedule.h:178
llvm::mca::RegisterFile::dump
void dump() const
Definition: RegisterFile.cpp:717
llvm::mca::WriteRef::commit
void commit()
Definition: RegisterFile.cpp:31
llvm::SmallVectorImpl::emplace_back
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:908