• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 //===--------------------- RegisterFile.cpp ---------------------*- C++ -*-===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 /// \file
10 ///
11 /// This file defines a register mapping file class.  This class is responsible
12 /// for managing hardware register files and the tracking of data dependencies
13 /// between registers.
14 ///
15 //===----------------------------------------------------------------------===//
16 
17 #include "RegisterFile.h"
18 #include "Instruction.h"
19 #include "llvm/Support/Debug.h"
20 
21 using namespace llvm;
22 
23 #define DEBUG_TYPE "llvm-mca"
24 
25 namespace mca {
26 
RegisterFile(const llvm::MCSchedModel & SM,const llvm::MCRegisterInfo & mri,unsigned NumRegs)27 RegisterFile::RegisterFile(const llvm::MCSchedModel &SM,
28                            const llvm::MCRegisterInfo &mri, unsigned NumRegs)
29     : MRI(mri), RegisterMappings(mri.getNumRegs(),
30                                  {WriteRef(), {IndexPlusCostPairTy(0, 1), 0}}) {
31   initialize(SM, NumRegs);
32 }
33 
initialize(const MCSchedModel & SM,unsigned NumRegs)34 void RegisterFile::initialize(const MCSchedModel &SM, unsigned NumRegs) {
35   // Create a default register file that "sees" all the machine registers
36   // declared by the target. The number of physical registers in the default
37   // register file is set equal to `NumRegs`. A value of zero for `NumRegs`
38   // means: this register file has an unbounded number of physical registers.
39   addRegisterFile({} /* all registers */, NumRegs);
40   if (!SM.hasExtraProcessorInfo())
41     return;
42 
43   // For each user defined register file, allocate a RegisterMappingTracker
44   // object. The size of every register file, as well as the mapping between
45   // register files and register classes is specified via tablegen.
46   const MCExtraProcessorInfo &Info = SM.getExtraProcessorInfo();
47   for (unsigned I = 0, E = Info.NumRegisterFiles; I < E; ++I) {
48     const MCRegisterFileDesc &RF = Info.RegisterFiles[I];
49     // Skip invalid register files with zero physical registers.
50     unsigned Length = RF.NumRegisterCostEntries;
51     if (!RF.NumPhysRegs)
52       continue;
53     // The cost of a register definition is equivalent to the number of
54     // physical registers that are allocated at register renaming stage.
55     const MCRegisterCostEntry *FirstElt =
56         &Info.RegisterCostTable[RF.RegisterCostEntryIdx];
57     addRegisterFile(ArrayRef<MCRegisterCostEntry>(FirstElt, Length),
58                     RF.NumPhysRegs);
59   }
60 }
61 
addRegisterFile(ArrayRef<MCRegisterCostEntry> Entries,unsigned NumPhysRegs)62 void RegisterFile::addRegisterFile(ArrayRef<MCRegisterCostEntry> Entries,
63                                    unsigned NumPhysRegs) {
64   // A default register file is always allocated at index #0. That register file
65   // is mainly used to count the total number of mappings created by all
66   // register files at runtime. Users can limit the number of available physical
67   // registers in register file #0 through the command line flag
68   // `-register-file-size`.
69   unsigned RegisterFileIndex = RegisterFiles.size();
70   RegisterFiles.emplace_back(NumPhysRegs);
71 
72   // Special case where there is no register class identifier in the set.
73   // An empty set of register classes means: this register file contains all
74   // the physical registers specified by the target.
75   // We optimistically assume that a register can be renamed at the cost of a
76   // single physical register. The constructor of RegisterFile ensures that
77   // a RegisterMapping exists for each logical register defined by the Target.
78   if (Entries.empty())
79     return;
80 
81   // Now update the cost of individual registers.
82   for (const MCRegisterCostEntry &RCE : Entries) {
83     const MCRegisterClass &RC = MRI.getRegClass(RCE.RegisterClassID);
84     for (const MCPhysReg Reg : RC) {
85       RegisterRenamingInfo &Entry = RegisterMappings[Reg].second;
86       IndexPlusCostPairTy &IPC = Entry.IndexPlusCost;
87       if (IPC.first && IPC.first != RegisterFileIndex) {
88         // The only register file that is allowed to overlap is the default
89         // register file at index #0. The analysis is inaccurate if register
90         // files overlap.
91         errs() << "warning: register " << MRI.getName(Reg)
92                << " defined in multiple register files.";
93       }
94       IPC = std::make_pair(RegisterFileIndex, RCE.Cost);
95       Entry.RenameAs = Reg;
96 
97       // Assume the same cost for each sub-register.
98       for (MCSubRegIterator I(Reg, &MRI); I.isValid(); ++I) {
99         RegisterRenamingInfo &OtherEntry = RegisterMappings[*I].second;
100         if (!OtherEntry.IndexPlusCost.first &&
101             (!OtherEntry.RenameAs ||
102              MRI.isSuperRegister(*I, OtherEntry.RenameAs))) {
103           OtherEntry.IndexPlusCost = IPC;
104           OtherEntry.RenameAs = Reg;
105         }
106       }
107     }
108   }
109 }
110 
allocatePhysRegs(const RegisterRenamingInfo & Entry,MutableArrayRef<unsigned> UsedPhysRegs)111 void RegisterFile::allocatePhysRegs(const RegisterRenamingInfo &Entry,
112                                     MutableArrayRef<unsigned> UsedPhysRegs) {
113   unsigned RegisterFileIndex = Entry.IndexPlusCost.first;
114   unsigned Cost = Entry.IndexPlusCost.second;
115   if (RegisterFileIndex) {
116     RegisterMappingTracker &RMT = RegisterFiles[RegisterFileIndex];
117     RMT.NumUsedPhysRegs += Cost;
118     UsedPhysRegs[RegisterFileIndex] += Cost;
119   }
120 
121   // Now update the default register mapping tracker.
122   RegisterFiles[0].NumUsedPhysRegs += Cost;
123   UsedPhysRegs[0] += Cost;
124 }
125 
freePhysRegs(const RegisterRenamingInfo & Entry,MutableArrayRef<unsigned> FreedPhysRegs)126 void RegisterFile::freePhysRegs(const RegisterRenamingInfo &Entry,
127                                 MutableArrayRef<unsigned> FreedPhysRegs) {
128   unsigned RegisterFileIndex = Entry.IndexPlusCost.first;
129   unsigned Cost = Entry.IndexPlusCost.second;
130   if (RegisterFileIndex) {
131     RegisterMappingTracker &RMT = RegisterFiles[RegisterFileIndex];
132     RMT.NumUsedPhysRegs -= Cost;
133     FreedPhysRegs[RegisterFileIndex] += Cost;
134   }
135 
136   // Now update the default register mapping tracker.
137   RegisterFiles[0].NumUsedPhysRegs -= Cost;
138   FreedPhysRegs[0] += Cost;
139 }
140 
addRegisterWrite(WriteRef Write,MutableArrayRef<unsigned> UsedPhysRegs,bool ShouldAllocatePhysRegs)141 void RegisterFile::addRegisterWrite(WriteRef Write,
142                                     MutableArrayRef<unsigned> UsedPhysRegs,
143                                     bool ShouldAllocatePhysRegs) {
144   WriteState &WS = *Write.getWriteState();
145   unsigned RegID = WS.getRegisterID();
146   assert(RegID && "Adding an invalid register definition?");
147 
148   LLVM_DEBUG({
149     dbgs() << "RegisterFile: addRegisterWrite [ " << Write.getSourceIndex()
150            << ", " << MRI.getName(RegID) << "]\n";
151   });
152 
153   // If RenameAs is equal to RegID, then RegID is subject to register renaming
154   // and false dependencies on RegID are all eliminated.
155 
156   // If RenameAs references the invalid register, then we optimistically assume
157   // that it can be renamed. In the absence of tablegen descriptors for register
158   // files, RenameAs is always set to the invalid register ID.  In all other
159   // cases, RenameAs must be either equal to RegID, or it must reference a
160   // super-register of RegID.
161 
162   // If RenameAs is a super-register of RegID, then a write to RegID has always
163   // a false dependency on RenameAs. The only exception is for when the write
164   // implicitly clears the upper portion of the underlying register.
165   // If a write clears its super-registers, then it is renamed as `RenameAs`.
166   const RegisterRenamingInfo &RRI = RegisterMappings[RegID].second;
167   if (RRI.RenameAs && RRI.RenameAs != RegID) {
168     RegID = RRI.RenameAs;
169     const WriteRef &OtherWrite = RegisterMappings[RegID].first;
170 
171     if (!WS.clearsSuperRegisters()) {
172       // The processor keeps the definition of `RegID` together with register
173       // `RenameAs`. Since this partial write is not renamed, no physical
174       // register is allocated.
175       ShouldAllocatePhysRegs = false;
176 
177       if (OtherWrite.getSourceIndex() != Write.getSourceIndex()) {
178         // This partial write has a false dependency on RenameAs.
179         WS.setDependentWrite(OtherWrite.getWriteState());
180       }
181     }
182   }
183 
184   // Update the mapping for register RegID including its sub-registers.
185   RegisterMappings[RegID].first = Write;
186   for (MCSubRegIterator I(RegID, &MRI); I.isValid(); ++I)
187     RegisterMappings[*I].first = Write;
188 
189   // No physical registers are allocated for instructions that are optimized in
190   // hardware. For example, zero-latency data-dependency breaking instructions
191   // don't consume physical registers.
192   if (ShouldAllocatePhysRegs)
193     allocatePhysRegs(RegisterMappings[RegID].second, UsedPhysRegs);
194 
195   if (!WS.clearsSuperRegisters())
196     return;
197 
198   for (MCSuperRegIterator I(RegID, &MRI); I.isValid(); ++I)
199     RegisterMappings[*I].first = Write;
200 }
201 
removeRegisterWrite(const WriteState & WS,MutableArrayRef<unsigned> FreedPhysRegs,bool ShouldFreePhysRegs)202 void RegisterFile::removeRegisterWrite(const WriteState &WS,
203                                        MutableArrayRef<unsigned> FreedPhysRegs,
204                                        bool ShouldFreePhysRegs) {
205   unsigned RegID = WS.getRegisterID();
206 
207   assert(RegID != 0 && "Invalidating an already invalid register?");
208   assert(WS.getCyclesLeft() != UNKNOWN_CYCLES &&
209          "Invalidating a write of unknown cycles!");
210   assert(WS.getCyclesLeft() <= 0 && "Invalid cycles left for this write!");
211 
212   unsigned RenameAs = RegisterMappings[RegID].second.RenameAs;
213   if (RenameAs && RenameAs != RegID) {
214     RegID = RenameAs;
215 
216     if (!WS.clearsSuperRegisters()) {
217       // Keep the definition of `RegID` together with register `RenameAs`.
218       ShouldFreePhysRegs = false;
219     }
220   }
221 
222   if (ShouldFreePhysRegs)
223     freePhysRegs(RegisterMappings[RegID].second, FreedPhysRegs);
224 
225   WriteRef &WR = RegisterMappings[RegID].first;
226   if (WR.getWriteState() == &WS)
227     WR.invalidate();
228 
229   for (MCSubRegIterator I(RegID, &MRI); I.isValid(); ++I) {
230     WriteRef &OtherWR = RegisterMappings[*I].first;
231     if (OtherWR.getWriteState() == &WS)
232       OtherWR.invalidate();
233   }
234 
235   if (!WS.clearsSuperRegisters())
236     return;
237 
238   for (MCSuperRegIterator I(RegID, &MRI); I.isValid(); ++I) {
239     WriteRef &OtherWR = RegisterMappings[*I].first;
240     if (OtherWR.getWriteState() == &WS)
241       OtherWR.invalidate();
242   }
243 }
244 
collectWrites(SmallVectorImpl<WriteRef> & Writes,unsigned RegID) const245 void RegisterFile::collectWrites(SmallVectorImpl<WriteRef> &Writes,
246                                  unsigned RegID) const {
247   assert(RegID && RegID < RegisterMappings.size());
248   LLVM_DEBUG(dbgs() << "RegisterFile: collecting writes for register "
249                     << MRI.getName(RegID) << '\n');
250   const WriteRef &WR = RegisterMappings[RegID].first;
251   if (WR.isValid())
252     Writes.push_back(WR);
253 
254   // Handle potential partial register updates.
255   for (MCSubRegIterator I(RegID, &MRI); I.isValid(); ++I) {
256     const WriteRef &WR = RegisterMappings[*I].first;
257     if (WR.isValid())
258       Writes.push_back(WR);
259   }
260 
261   // Remove duplicate entries and resize the input vector.
262   llvm::sort(Writes.begin(), Writes.end(),
263              [](const WriteRef &Lhs, const WriteRef &Rhs) {
264                return Lhs.getWriteState() < Rhs.getWriteState();
265              });
266   auto It = std::unique(Writes.begin(), Writes.end());
267   Writes.resize(std::distance(Writes.begin(), It));
268 
269   LLVM_DEBUG({
270     for (const WriteRef &WR : Writes) {
271       const WriteState &WS = *WR.getWriteState();
272       dbgs() << "[PRF] Found a dependent use of Register "
273              << MRI.getName(WS.getRegisterID()) << " (defined by intruction #"
274              << WR.getSourceIndex() << ")\n";
275     }
276   });
277 }
278 
isAvailable(ArrayRef<unsigned> Regs) const279 unsigned RegisterFile::isAvailable(ArrayRef<unsigned> Regs) const {
280   SmallVector<unsigned, 4> NumPhysRegs(getNumRegisterFiles());
281 
282   // Find how many new mappings must be created for each register file.
283   for (const unsigned RegID : Regs) {
284     const RegisterRenamingInfo &RRI = RegisterMappings[RegID].second;
285     const IndexPlusCostPairTy &Entry = RRI.IndexPlusCost;
286     if (Entry.first)
287       NumPhysRegs[Entry.first] += Entry.second;
288     NumPhysRegs[0] += Entry.second;
289   }
290 
291   unsigned Response = 0;
292   for (unsigned I = 0, E = getNumRegisterFiles(); I < E; ++I) {
293     unsigned NumRegs = NumPhysRegs[I];
294     if (!NumRegs)
295       continue;
296 
297     const RegisterMappingTracker &RMT = RegisterFiles[I];
298     if (!RMT.NumPhysRegs) {
299       // The register file has an unbounded number of microarchitectural
300       // registers.
301       continue;
302     }
303 
304     if (RMT.NumPhysRegs < NumRegs) {
305       // The current register file is too small. This may occur if the number of
306       // microarchitectural registers in register file #0 was changed by the
307       // users via flag -reg-file-size. Alternatively, the scheduling model
308       // specified a too small number of registers for this register file.
309       report_fatal_error(
310           "Not enough microarchitectural registers in the register file");
311     }
312 
313     if (RMT.NumPhysRegs < (RMT.NumUsedPhysRegs + NumRegs))
314       Response |= (1U << I);
315   }
316 
317   return Response;
318 }
319 
320 #ifndef NDEBUG
dump() const321 void RegisterFile::dump() const {
322   for (unsigned I = 0, E = MRI.getNumRegs(); I < E; ++I) {
323     const RegisterMapping &RM = RegisterMappings[I];
324     if (!RM.first.getWriteState())
325       continue;
326     const RegisterRenamingInfo &RRI = RM.second;
327     dbgs() << MRI.getName(I) << ", " << I << ", PRF=" << RRI.IndexPlusCost.first
328            << ", Cost=" << RRI.IndexPlusCost.second
329            << ", RenameAs=" << RRI.RenameAs << ", ";
330     RM.first.dump();
331     dbgs() << '\n';
332   }
333 
334   for (unsigned I = 0, E = getNumRegisterFiles(); I < E; ++I) {
335     dbgs() << "Register File #" << I;
336     const RegisterMappingTracker &RMT = RegisterFiles[I];
337     dbgs() << "\n  TotalMappings:        " << RMT.NumPhysRegs
338            << "\n  NumUsedMappings:      " << RMT.NumUsedPhysRegs << '\n';
339   }
340 }
341 #endif
342 
343 } // namespace mca
344