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