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 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 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 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 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 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 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 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 245 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 279 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 321 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