RegisterInfoEmitter.cpp revision 7afcc6aa270ca51e502de9f826ecdf61568a73b9
1//===- RegisterInfoEmitter.cpp - Generate a Register File Desc. -*- 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// 10// This tablegen backend is responsible for emitting a description of a target 11// register file for a code generator. It uses instances of the Register, 12// RegisterAliases, and RegisterClass classes to gather this information. 13// 14//===----------------------------------------------------------------------===// 15 16#include "RegisterInfoEmitter.h" 17#include "CodeGenTarget.h" 18#include "CodeGenRegisters.h" 19#include "Record.h" 20#include "llvm/ADT/StringExtras.h" 21#include "llvm/ADT/STLExtras.h" 22#include "llvm/Support/Streams.h" 23#include <set> 24#include <algorithm> 25using namespace llvm; 26 27// runEnums - Print out enum values for all of the registers. 28void RegisterInfoEmitter::runEnums(std::ostream &OS) { 29 CodeGenTarget Target; 30 const std::vector<CodeGenRegister> &Registers = Target.getRegisters(); 31 32 std::string Namespace = Registers[0].TheDef->getValueAsString("Namespace"); 33 34 EmitSourceFileHeader("Target Register Enum Values", OS); 35 OS << "namespace llvm {\n\n"; 36 37 if (!Namespace.empty()) 38 OS << "namespace " << Namespace << " {\n"; 39 OS << " enum {\n NoRegister,\n"; 40 41 for (unsigned i = 0, e = Registers.size(); i != e; ++i) 42 OS << " " << Registers[i].getName() << ", \t// " << i+1 << "\n"; 43 OS << " NUM_TARGET_REGS \t// " << Registers.size()+1 << "\n"; 44 OS << " };\n"; 45 if (!Namespace.empty()) 46 OS << "}\n"; 47 OS << "} // End llvm namespace \n"; 48} 49 50void RegisterInfoEmitter::runHeader(std::ostream &OS) { 51 EmitSourceFileHeader("Register Information Header Fragment", OS); 52 CodeGenTarget Target; 53 const std::string &TargetName = Target.getName(); 54 std::string ClassName = TargetName + "GenRegisterInfo"; 55 56 OS << "#include \"llvm/Target/TargetRegisterInfo.h\"\n"; 57 OS << "#include <string>\n\n"; 58 59 OS << "namespace llvm {\n\n"; 60 61 OS << "struct " << ClassName << " : public TargetRegisterInfo {\n" 62 << " explicit " << ClassName 63 << "(int CallFrameSetupOpcode = -1, int CallFrameDestroyOpcode = -1);\n" 64 << " virtual int getDwarfRegNumFull(unsigned RegNum, " 65 << "unsigned Flavour) const;\n" 66 << " virtual int getDwarfRegNum(unsigned RegNum, bool isEH) const = 0;\n" 67 << " virtual bool needsStackRealignment(const MachineFunction &) const\n" 68 << " { return false; }\n" 69 << " unsigned getSubReg(unsigned RegNo, unsigned Index) const;\n" 70 << "};\n\n"; 71 72 const std::vector<CodeGenRegisterClass> &RegisterClasses = 73 Target.getRegisterClasses(); 74 75 if (!RegisterClasses.empty()) { 76 OS << "namespace " << RegisterClasses[0].Namespace 77 << " { // Register classes\n"; 78 79 OS << " enum {\n"; 80 for (unsigned i = 0, e = RegisterClasses.size(); i != e; ++i) { 81 if (i) OS << ",\n"; 82 OS << " " << RegisterClasses[i].getName() << "RegClassID"; 83 OS << " = " << (i+1); 84 } 85 OS << "\n };\n\n"; 86 87 for (unsigned i = 0, e = RegisterClasses.size(); i != e; ++i) { 88 const std::string &Name = RegisterClasses[i].getName(); 89 90 // Output the register class definition. 91 OS << " struct " << Name << "Class : public TargetRegisterClass {\n" 92 << " " << Name << "Class();\n" 93 << RegisterClasses[i].MethodProtos << " };\n"; 94 95 // Output the extern for the instance. 96 OS << " extern " << Name << "Class\t" << Name << "RegClass;\n"; 97 // Output the extern for the pointer to the instance (should remove). 98 OS << " static TargetRegisterClass * const "<< Name <<"RegisterClass = &" 99 << Name << "RegClass;\n"; 100 } 101 OS << "} // end of namespace " << TargetName << "\n\n"; 102 } 103 OS << "} // End llvm namespace \n"; 104} 105 106bool isSubRegisterClass(const CodeGenRegisterClass &RC, 107 std::set<Record*> &RegSet) { 108 for (unsigned i = 0, e = RC.Elements.size(); i != e; ++i) { 109 Record *Reg = RC.Elements[i]; 110 if (!RegSet.count(Reg)) 111 return false; 112 } 113 return true; 114} 115 116static void addSuperReg(Record *R, Record *S, 117 std::map<Record*, std::set<Record*>, LessRecord> &SubRegs, 118 std::map<Record*, std::set<Record*>, LessRecord> &SuperRegs, 119 std::map<Record*, std::set<Record*>, LessRecord> &Aliases) { 120 if (R == S) { 121 cerr << "Error: recursive sub-register relationship between" 122 << " register " << getQualifiedName(R) 123 << " and its sub-registers?\n"; 124 abort(); 125 } 126 if (!SuperRegs[R].insert(S).second) 127 return; 128 SubRegs[S].insert(R); 129 Aliases[R].insert(S); 130 Aliases[S].insert(R); 131 if (SuperRegs.count(S)) 132 for (std::set<Record*>::iterator I = SuperRegs[S].begin(), 133 E = SuperRegs[S].end(); I != E; ++I) 134 addSuperReg(R, *I, SubRegs, SuperRegs, Aliases); 135} 136 137static void addSubSuperReg(Record *R, Record *S, 138 std::map<Record*, std::set<Record*>, LessRecord> &SubRegs, 139 std::map<Record*, std::set<Record*>, LessRecord> &SuperRegs, 140 std::map<Record*, std::set<Record*>, LessRecord> &Aliases) { 141 if (R == S) { 142 cerr << "Error: recursive sub-register relationship between" 143 << " register " << getQualifiedName(R) 144 << " and its sub-registers?\n"; 145 abort(); 146 } 147 148 if (!SubRegs[R].insert(S).second) 149 return; 150 addSuperReg(S, R, SubRegs, SuperRegs, Aliases); 151 Aliases[R].insert(S); 152 Aliases[S].insert(R); 153 if (SubRegs.count(S)) 154 for (std::set<Record*>::iterator I = SubRegs[S].begin(), 155 E = SubRegs[S].end(); I != E; ++I) 156 addSubSuperReg(R, *I, SubRegs, SuperRegs, Aliases); 157} 158 159class RegisterSorter { 160private: 161 std::map<Record*, std::set<Record*>, LessRecord> &RegisterSubRegs; 162 163public: 164 RegisterSorter(std::map<Record*, std::set<Record*>, LessRecord> &RS) 165 : RegisterSubRegs(RS) {}; 166 167 bool operator()(Record *RegA, Record *RegB) { 168 // B is sub-register of A. 169 return RegisterSubRegs.count(RegA) && RegisterSubRegs[RegA].count(RegB); 170 } 171}; 172 173// RegisterInfoEmitter::run - Main register file description emitter. 174// 175void RegisterInfoEmitter::run(std::ostream &OS) { 176 CodeGenTarget Target; 177 EmitSourceFileHeader("Register Information Source Fragment", OS); 178 179 OS << "namespace llvm {\n\n"; 180 181 // Start out by emitting each of the register classes... to do this, we build 182 // a set of registers which belong to a register class, this is to ensure that 183 // each register is only in a single register class. 184 // 185 const std::vector<CodeGenRegisterClass> &RegisterClasses = 186 Target.getRegisterClasses(); 187 188 // Loop over all of the register classes... emitting each one. 189 OS << "namespace { // Register classes...\n"; 190 191 // RegClassesBelongedTo - Keep track of which register classes each reg 192 // belongs to. 193 std::multimap<Record*, const CodeGenRegisterClass*> RegClassesBelongedTo; 194 195 // Emit the register enum value arrays for each RegisterClass 196 for (unsigned rc = 0, e = RegisterClasses.size(); rc != e; ++rc) { 197 const CodeGenRegisterClass &RC = RegisterClasses[rc]; 198 199 // Give the register class a legal C name if it's anonymous. 200 std::string Name = RC.TheDef->getName(); 201 202 // Emit the register list now. 203 OS << " // " << Name << " Register Class...\n" 204 << " static const unsigned " << Name 205 << "[] = {\n "; 206 for (unsigned i = 0, e = RC.Elements.size(); i != e; ++i) { 207 Record *Reg = RC.Elements[i]; 208 OS << getQualifiedName(Reg) << ", "; 209 210 // Keep track of which regclasses this register is in. 211 RegClassesBelongedTo.insert(std::make_pair(Reg, &RC)); 212 } 213 OS << "\n };\n\n"; 214 } 215 216 // Emit the ValueType arrays for each RegisterClass 217 for (unsigned rc = 0, e = RegisterClasses.size(); rc != e; ++rc) { 218 const CodeGenRegisterClass &RC = RegisterClasses[rc]; 219 220 // Give the register class a legal C name if it's anonymous. 221 std::string Name = RC.TheDef->getName() + "VTs"; 222 223 // Emit the register list now. 224 OS << " // " << Name 225 << " Register Class Value Types...\n" 226 << " static const MVT " << Name 227 << "[] = {\n "; 228 for (unsigned i = 0, e = RC.VTs.size(); i != e; ++i) 229 OS << getEnumName(RC.VTs[i]) << ", "; 230 OS << "MVT::Other\n };\n\n"; 231 } 232 OS << "} // end anonymous namespace\n\n"; 233 234 // Now that all of the structs have been emitted, emit the instances. 235 if (!RegisterClasses.empty()) { 236 OS << "namespace " << RegisterClasses[0].Namespace 237 << " { // Register class instances\n"; 238 for (unsigned i = 0, e = RegisterClasses.size(); i != e; ++i) 239 OS << " " << RegisterClasses[i].getName() << "Class\t" 240 << RegisterClasses[i].getName() << "RegClass;\n"; 241 242 std::map<unsigned, std::set<unsigned> > SuperClassMap; 243 std::map<unsigned, std::set<unsigned> > SuperRegClassMap; 244 OS << "\n"; 245 246 // Emit the sub-register classes for each RegisterClass 247 for (unsigned rc = 0, e = RegisterClasses.size(); rc != e; ++rc) { 248 const CodeGenRegisterClass &RC = RegisterClasses[rc]; 249 250 // Give the register class a legal C name if it's anonymous. 251 std::string Name = RC.TheDef->getName(); 252 253 OS << " // " << Name 254 << " Sub-register Classes...\n" 255 << " static const TargetRegisterClass* const " 256 << Name << "SubRegClasses [] = {\n "; 257 258 bool Empty = true; 259 260 for (unsigned subrc = 0, subrcMax = RC.SubRegClasses.size(); 261 subrc != subrcMax; ++subrc) { 262 unsigned rc2 = 0, e2 = RegisterClasses.size(); 263 for (; rc2 != e2; ++rc2) { 264 const CodeGenRegisterClass &RC2 = RegisterClasses[rc2]; 265 if (RC.SubRegClasses[subrc]->getName() == RC2.getName()) { 266 if (!Empty) 267 OS << ", "; 268 OS << "&" << getQualifiedName(RC2.TheDef) << "RegClass"; 269 Empty = false; 270 271 std::map<unsigned, std::set<unsigned> >::iterator SCMI = 272 SuperRegClassMap.find(rc2); 273 if (SCMI == SuperRegClassMap.end()) { 274 SuperRegClassMap.insert(std::make_pair(rc2, 275 std::set<unsigned>())); 276 SCMI = SuperRegClassMap.find(rc2); 277 } 278 SCMI->second.insert(rc); 279 break; 280 } 281 } 282 if (rc2 == e2) 283 throw "Register Class member '" + 284 RC.SubRegClasses[subrc]->getName() + 285 "' is not a valid RegisterClass!"; 286 } 287 288 OS << (!Empty ? ", " : "") << "NULL"; 289 OS << "\n };\n\n"; 290 } 291 292 // Emit the super-register classes for each RegisterClass 293 for (unsigned rc = 0, e = RegisterClasses.size(); rc != e; ++rc) { 294 const CodeGenRegisterClass &RC = RegisterClasses[rc]; 295 296 // Give the register class a legal C name if it's anonymous. 297 std::string Name = RC.TheDef->getName(); 298 299 OS << " // " << Name 300 << " Super-register Classes...\n" 301 << " static const TargetRegisterClass* const " 302 << Name << "SuperRegClasses [] = {\n "; 303 304 bool Empty = true; 305 std::map<unsigned, std::set<unsigned> >::iterator I = 306 SuperRegClassMap.find(rc); 307 if (I != SuperRegClassMap.end()) { 308 for (std::set<unsigned>::iterator II = I->second.begin(), 309 EE = I->second.end(); II != EE; ++II) { 310 const CodeGenRegisterClass &RC2 = RegisterClasses[*II]; 311 if (!Empty) 312 OS << ", "; 313 OS << "&" << getQualifiedName(RC2.TheDef) << "RegClass"; 314 Empty = false; 315 } 316 } 317 318 OS << (!Empty ? ", " : "") << "NULL"; 319 OS << "\n };\n\n"; 320 } 321 322 // Emit the sub-classes array for each RegisterClass 323 for (unsigned rc = 0, e = RegisterClasses.size(); rc != e; ++rc) { 324 const CodeGenRegisterClass &RC = RegisterClasses[rc]; 325 326 // Give the register class a legal C name if it's anonymous. 327 std::string Name = RC.TheDef->getName(); 328 329 std::set<Record*> RegSet; 330 for (unsigned i = 0, e = RC.Elements.size(); i != e; ++i) { 331 Record *Reg = RC.Elements[i]; 332 RegSet.insert(Reg); 333 } 334 335 OS << " // " << Name 336 << " Register Class sub-classes...\n" 337 << " static const TargetRegisterClass* const " 338 << Name << "Subclasses [] = {\n "; 339 340 bool Empty = true; 341 for (unsigned rc2 = 0, e2 = RegisterClasses.size(); rc2 != e2; ++rc2) { 342 const CodeGenRegisterClass &RC2 = RegisterClasses[rc2]; 343 344 // RC2 is a sub-class of RC if it is a valid replacement for any 345 // instruction operand where an RC register is required. It must satisfy 346 // these conditions: 347 // 348 // 1. All RC2 registers are also in RC. 349 // 2. The RC2 spill size must not be smaller that the RC spill size. 350 // 3. RC2 spill alignment must be compatible with RC. 351 // 352 // Sub-classes are used to determine if a virtual register can be used 353 // as an instruction operand, or if it must be copied first. 354 355 if (rc == rc2 || RC2.Elements.size() > RC.Elements.size() || 356 (RC.SpillAlignment && RC2.SpillAlignment % RC.SpillAlignment) || 357 RC.SpillSize > RC2.SpillSize || !isSubRegisterClass(RC2, RegSet)) 358 continue; 359 360 if (!Empty) OS << ", "; 361 OS << "&" << getQualifiedName(RC2.TheDef) << "RegClass"; 362 Empty = false; 363 364 std::map<unsigned, std::set<unsigned> >::iterator SCMI = 365 SuperClassMap.find(rc2); 366 if (SCMI == SuperClassMap.end()) { 367 SuperClassMap.insert(std::make_pair(rc2, std::set<unsigned>())); 368 SCMI = SuperClassMap.find(rc2); 369 } 370 SCMI->second.insert(rc); 371 } 372 373 OS << (!Empty ? ", " : "") << "NULL"; 374 OS << "\n };\n\n"; 375 } 376 377 for (unsigned rc = 0, e = RegisterClasses.size(); rc != e; ++rc) { 378 const CodeGenRegisterClass &RC = RegisterClasses[rc]; 379 380 // Give the register class a legal C name if it's anonymous. 381 std::string Name = RC.TheDef->getName(); 382 383 OS << " // " << Name 384 << " Register Class super-classes...\n" 385 << " static const TargetRegisterClass* const " 386 << Name << "Superclasses [] = {\n "; 387 388 bool Empty = true; 389 std::map<unsigned, std::set<unsigned> >::iterator I = 390 SuperClassMap.find(rc); 391 if (I != SuperClassMap.end()) { 392 for (std::set<unsigned>::iterator II = I->second.begin(), 393 EE = I->second.end(); II != EE; ++II) { 394 const CodeGenRegisterClass &RC2 = RegisterClasses[*II]; 395 if (!Empty) OS << ", "; 396 OS << "&" << getQualifiedName(RC2.TheDef) << "RegClass"; 397 Empty = false; 398 } 399 } 400 401 OS << (!Empty ? ", " : "") << "NULL"; 402 OS << "\n };\n\n"; 403 } 404 405 406 for (unsigned i = 0, e = RegisterClasses.size(); i != e; ++i) { 407 const CodeGenRegisterClass &RC = RegisterClasses[i]; 408 OS << RC.MethodBodies << "\n"; 409 OS << RC.getName() << "Class::" << RC.getName() 410 << "Class() : TargetRegisterClass(" 411 << RC.getName() + "RegClassID" << ", " 412 << '\"' << RC.getName() << "\", " 413 << RC.getName() + "VTs" << ", " 414 << RC.getName() + "Subclasses" << ", " 415 << RC.getName() + "Superclasses" << ", " 416 << RC.getName() + "SubRegClasses" << ", " 417 << RC.getName() + "SuperRegClasses" << ", " 418 << RC.SpillSize/8 << ", " 419 << RC.SpillAlignment/8 << ", " 420 << RC.CopyCost << ", " 421 << RC.getName() << ", " << RC.getName() << " + " << RC.Elements.size() 422 << ") {}\n"; 423 } 424 425 OS << "}\n"; 426 } 427 428 OS << "\nnamespace {\n"; 429 OS << " const TargetRegisterClass* const RegisterClasses[] = {\n"; 430 for (unsigned i = 0, e = RegisterClasses.size(); i != e; ++i) 431 OS << " &" << getQualifiedName(RegisterClasses[i].TheDef) 432 << "RegClass,\n"; 433 OS << " };\n"; 434 435 // Emit register sub-registers / super-registers, aliases... 436 std::map<Record*, std::set<Record*>, LessRecord> RegisterSubRegs; 437 std::map<Record*, std::set<Record*>, LessRecord> RegisterSuperRegs; 438 std::map<Record*, std::set<Record*>, LessRecord> RegisterAliases; 439 std::map<Record*, std::vector<std::pair<int, Record*> > > SubRegVectors; 440 typedef std::map<Record*, std::vector<int64_t>, LessRecord> DwarfRegNumsMapTy; 441 DwarfRegNumsMapTy DwarfRegNums; 442 443 const std::vector<CodeGenRegister> &Regs = Target.getRegisters(); 444 445 for (unsigned i = 0, e = Regs.size(); i != e; ++i) { 446 Record *R = Regs[i].TheDef; 447 std::vector<Record*> LI = Regs[i].TheDef->getValueAsListOfDefs("Aliases"); 448 // Add information that R aliases all of the elements in the list... and 449 // that everything in the list aliases R. 450 for (unsigned j = 0, e = LI.size(); j != e; ++j) { 451 Record *Reg = LI[j]; 452 if (RegisterAliases[R].count(Reg)) 453 cerr << "Warning: register alias between " << getQualifiedName(R) 454 << " and " << getQualifiedName(Reg) 455 << " specified multiple times!\n"; 456 RegisterAliases[R].insert(Reg); 457 458 if (RegisterAliases[Reg].count(R)) 459 cerr << "Warning: register alias between " << getQualifiedName(R) 460 << " and " << getQualifiedName(Reg) 461 << " specified multiple times!\n"; 462 RegisterAliases[Reg].insert(R); 463 } 464 } 465 466 // Process sub-register sets. 467 for (unsigned i = 0, e = Regs.size(); i != e; ++i) { 468 Record *R = Regs[i].TheDef; 469 std::vector<Record*> LI = Regs[i].TheDef->getValueAsListOfDefs("SubRegs"); 470 // Process sub-register set and add aliases information. 471 for (unsigned j = 0, e = LI.size(); j != e; ++j) { 472 Record *SubReg = LI[j]; 473 if (RegisterSubRegs[R].count(SubReg)) 474 cerr << "Warning: register " << getQualifiedName(SubReg) 475 << " specified as a sub-register of " << getQualifiedName(R) 476 << " multiple times!\n"; 477 addSubSuperReg(R, SubReg, RegisterSubRegs, RegisterSuperRegs, 478 RegisterAliases); 479 } 480 } 481 482 // Print the SubregHashTable, a simple quadratically probed 483 // hash table for determining if a register is a subregister 484 // of another register. 485 unsigned NumSubRegs = 0; 486 std::map<Record*, unsigned> RegNo; 487 for (unsigned i = 0, e = Regs.size(); i != e; ++i) { 488 RegNo[Regs[i].TheDef] = i; 489 NumSubRegs += RegisterSubRegs[Regs[i].TheDef].size(); 490 } 491 492 unsigned SubregHashTableSize = 2 * NextPowerOf2(2 * NumSubRegs); 493 unsigned* SubregHashTable = new unsigned[2 * SubregHashTableSize]; 494 std::fill(SubregHashTable, SubregHashTable + 2 * SubregHashTableSize, ~0U); 495 496 unsigned hashMisses = 0; 497 498 for (unsigned i = 0, e = Regs.size(); i != e; ++i) { 499 Record* R = Regs[i].TheDef; 500 for (std::set<Record*>::iterator I = RegisterSubRegs[R].begin(), 501 E = RegisterSubRegs[R].end(); I != E; ++I) { 502 Record* RJ = *I; 503 // We have to increase the indices of both registers by one when 504 // computing the hash because, in the generated code, there 505 // will be an extra empty slot at register 0. 506 size_t index = ((i+1) + (RegNo[RJ]+1) * 37) & (SubregHashTableSize-1); 507 unsigned ProbeAmt = 2; 508 while (SubregHashTable[index*2] != ~0U && 509 SubregHashTable[index*2+1] != ~0U) { 510 index = (index + ProbeAmt) & (SubregHashTableSize-1); 511 ProbeAmt += 2; 512 513 hashMisses++; 514 } 515 516 SubregHashTable[index*2] = i; 517 SubregHashTable[index*2+1] = RegNo[RJ]; 518 } 519 } 520 521 OS << "\n\n // Number of hash collisions: " << hashMisses << "\n"; 522 523 if (SubregHashTableSize) { 524 std::string Namespace = Regs[0].TheDef->getValueAsString("Namespace"); 525 526 OS << " const unsigned SubregHashTable[] = { "; 527 for (unsigned i = 0; i < SubregHashTableSize - 1; ++i) { 528 if (i != 0) 529 // Insert spaces for nice formatting. 530 OS << " "; 531 532 if (SubregHashTable[2*i] != ~0U) { 533 OS << getQualifiedName(Regs[SubregHashTable[2*i]].TheDef) << ", " 534 << getQualifiedName(Regs[SubregHashTable[2*i+1]].TheDef) << ", \n"; 535 } else { 536 OS << Namespace << "::NoRegister, " << Namespace << "::NoRegister, \n"; 537 } 538 } 539 540 unsigned Idx = SubregHashTableSize*2-2; 541 if (SubregHashTable[Idx] != ~0U) { 542 OS << " " 543 << getQualifiedName(Regs[SubregHashTable[Idx]].TheDef) << ", " 544 << getQualifiedName(Regs[SubregHashTable[Idx+1]].TheDef) << " };\n"; 545 } else { 546 OS << Namespace << "::NoRegister, " << Namespace << "::NoRegister };\n"; 547 } 548 549 OS << " const unsigned SubregHashTableSize = " 550 << SubregHashTableSize << ";\n"; 551 } else { 552 OS << " const unsigned SubregHashTable[] = { ~0U, ~0U };\n" 553 << " const unsigned SubregHashTableSize = 1;\n"; 554 } 555 556 delete [] SubregHashTable; 557 558 559 // Print the SuperregHashTable, a simple quadratically probed 560 // hash table for determining if a register is a super-register 561 // of another register. 562 unsigned NumSupRegs = 0; 563 RegNo.clear(); 564 for (unsigned i = 0, e = Regs.size(); i != e; ++i) { 565 RegNo[Regs[i].TheDef] = i; 566 NumSupRegs += RegisterSuperRegs[Regs[i].TheDef].size(); 567 } 568 569 unsigned SuperregHashTableSize = 2 * NextPowerOf2(2 * NumSupRegs); 570 unsigned* SuperregHashTable = new unsigned[2 * SuperregHashTableSize]; 571 std::fill(SuperregHashTable, SuperregHashTable + 2 * SuperregHashTableSize, ~0U); 572 573 hashMisses = 0; 574 575 for (unsigned i = 0, e = Regs.size(); i != e; ++i) { 576 Record* R = Regs[i].TheDef; 577 for (std::set<Record*>::iterator I = RegisterSuperRegs[R].begin(), 578 E = RegisterSuperRegs[R].end(); I != E; ++I) { 579 Record* RJ = *I; 580 // We have to increase the indices of both registers by one when 581 // computing the hash because, in the generated code, there 582 // will be an extra empty slot at register 0. 583 size_t index = ((i+1) + (RegNo[RJ]+1) * 37) & (SuperregHashTableSize-1); 584 unsigned ProbeAmt = 2; 585 while (SuperregHashTable[index*2] != ~0U && 586 SuperregHashTable[index*2+1] != ~0U) { 587 index = (index + ProbeAmt) & (SuperregHashTableSize-1); 588 ProbeAmt += 2; 589 590 hashMisses++; 591 } 592 593 SuperregHashTable[index*2] = i; 594 SuperregHashTable[index*2+1] = RegNo[RJ]; 595 } 596 } 597 598 OS << "\n\n // Number of hash collisions: " << hashMisses << "\n"; 599 600 if (SuperregHashTableSize) { 601 std::string Namespace = Regs[0].TheDef->getValueAsString("Namespace"); 602 603 OS << " const unsigned SuperregHashTable[] = { "; 604 for (unsigned i = 0; i < SuperregHashTableSize - 1; ++i) { 605 if (i != 0) 606 // Insert spaces for nice formatting. 607 OS << " "; 608 609 if (SuperregHashTable[2*i] != ~0U) { 610 OS << getQualifiedName(Regs[SuperregHashTable[2*i]].TheDef) << ", " 611 << getQualifiedName(Regs[SuperregHashTable[2*i+1]].TheDef) << ", \n"; 612 } else { 613 OS << Namespace << "::NoRegister, " << Namespace << "::NoRegister, \n"; 614 } 615 } 616 617 unsigned Idx = SuperregHashTableSize*2-2; 618 if (SuperregHashTable[Idx] != ~0U) { 619 OS << " " 620 << getQualifiedName(Regs[SuperregHashTable[Idx]].TheDef) << ", " 621 << getQualifiedName(Regs[SuperregHashTable[Idx+1]].TheDef) << " };\n"; 622 } else { 623 OS << Namespace << "::NoRegister, " << Namespace << "::NoRegister };\n"; 624 } 625 626 OS << " const unsigned SuperregHashTableSize = " 627 << SuperregHashTableSize << ";\n"; 628 } else { 629 OS << " const unsigned SuperregHashTable[] = { ~0U, ~0U };\n" 630 << " const unsigned SuperregHashTableSize = 1;\n"; 631 } 632 633 delete [] SuperregHashTable; 634 635 636 // Print the AliasHashTable, a simple quadratically probed 637 // hash table for determining if a register aliases another register. 638 unsigned NumAliases = 0; 639 RegNo.clear(); 640 for (unsigned i = 0, e = Regs.size(); i != e; ++i) { 641 RegNo[Regs[i].TheDef] = i; 642 NumAliases += RegisterAliases[Regs[i].TheDef].size(); 643 } 644 645 unsigned AliasesHashTableSize = 2 * NextPowerOf2(2 * NumAliases); 646 unsigned* AliasesHashTable = new unsigned[2 * AliasesHashTableSize]; 647 std::fill(AliasesHashTable, AliasesHashTable + 2 * AliasesHashTableSize, ~0U); 648 649 hashMisses = 0; 650 651 for (unsigned i = 0, e = Regs.size(); i != e; ++i) { 652 Record* R = Regs[i].TheDef; 653 for (std::set<Record*>::iterator I = RegisterAliases[R].begin(), 654 E = RegisterAliases[R].end(); I != E; ++I) { 655 Record* RJ = *I; 656 // We have to increase the indices of both registers by one when 657 // computing the hash because, in the generated code, there 658 // will be an extra empty slot at register 0. 659 size_t index = ((i+1) + (RegNo[RJ]+1) * 37) & (AliasesHashTableSize-1); 660 unsigned ProbeAmt = 2; 661 while (AliasesHashTable[index*2] != ~0U && 662 AliasesHashTable[index*2+1] != ~0U) { 663 index = (index + ProbeAmt) & (AliasesHashTableSize-1); 664 ProbeAmt += 2; 665 666 hashMisses++; 667 } 668 669 AliasesHashTable[index*2] = i; 670 AliasesHashTable[index*2+1] = RegNo[RJ]; 671 } 672 } 673 674 OS << "\n\n // Number of hash collisions: " << hashMisses << "\n"; 675 676 if (AliasesHashTableSize) { 677 std::string Namespace = Regs[0].TheDef->getValueAsString("Namespace"); 678 679 OS << " const unsigned AliasesHashTable[] = { "; 680 for (unsigned i = 0; i < AliasesHashTableSize - 1; ++i) { 681 if (i != 0) 682 // Insert spaces for nice formatting. 683 OS << " "; 684 685 if (AliasesHashTable[2*i] != ~0U) { 686 OS << getQualifiedName(Regs[AliasesHashTable[2*i]].TheDef) << ", " 687 << getQualifiedName(Regs[AliasesHashTable[2*i+1]].TheDef) << ", \n"; 688 } else { 689 OS << Namespace << "::NoRegister, " << Namespace << "::NoRegister, \n"; 690 } 691 } 692 693 unsigned Idx = AliasesHashTableSize*2-2; 694 if (AliasesHashTable[Idx] != ~0U) { 695 OS << " " 696 << getQualifiedName(Regs[AliasesHashTable[Idx]].TheDef) << ", " 697 << getQualifiedName(Regs[AliasesHashTable[Idx+1]].TheDef) << " };\n"; 698 } else { 699 OS << Namespace << "::NoRegister, " << Namespace << "::NoRegister };\n"; 700 } 701 702 OS << " const unsigned AliasesHashTableSize = " 703 << AliasesHashTableSize << ";\n"; 704 } else { 705 OS << " const unsigned AliasesHashTable[] = { ~0U, ~0U };\n" 706 << " const unsigned AliasesHashTableSize = 1;\n"; 707 } 708 709 delete [] AliasesHashTable; 710 711 if (!RegisterAliases.empty()) 712 OS << "\n\n // Register Alias Sets...\n"; 713 714 // Emit the empty alias list 715 OS << " const unsigned Empty_AliasSet[] = { 0 };\n"; 716 // Loop over all of the registers which have aliases, emitting the alias list 717 // to memory. 718 for (std::map<Record*, std::set<Record*>, LessRecord >::iterator 719 I = RegisterAliases.begin(), E = RegisterAliases.end(); I != E; ++I) { 720 OS << " const unsigned " << I->first->getName() << "_AliasSet[] = { "; 721 for (std::set<Record*>::iterator ASI = I->second.begin(), 722 E = I->second.end(); ASI != E; ++ASI) 723 OS << getQualifiedName(*ASI) << ", "; 724 OS << "0 };\n"; 725 } 726 727 if (!RegisterSubRegs.empty()) 728 OS << "\n\n // Register Sub-registers Sets...\n"; 729 730 // Emit the empty sub-registers list 731 OS << " const unsigned Empty_SubRegsSet[] = { 0 };\n"; 732 // Loop over all of the registers which have sub-registers, emitting the 733 // sub-registers list to memory. 734 for (std::map<Record*, std::set<Record*>, LessRecord>::iterator 735 I = RegisterSubRegs.begin(), E = RegisterSubRegs.end(); I != E; ++I) { 736 OS << " const unsigned " << I->first->getName() << "_SubRegsSet[] = { "; 737 std::vector<Record*> SubRegsVector; 738 for (std::set<Record*>::iterator ASI = I->second.begin(), 739 E = I->second.end(); ASI != E; ++ASI) 740 SubRegsVector.push_back(*ASI); 741 RegisterSorter RS(RegisterSubRegs); 742 std::stable_sort(SubRegsVector.begin(), SubRegsVector.end(), RS); 743 for (unsigned i = 0, e = SubRegsVector.size(); i != e; ++i) 744 OS << getQualifiedName(SubRegsVector[i]) << ", "; 745 OS << "0 };\n"; 746 } 747 748 if (!RegisterSuperRegs.empty()) 749 OS << "\n\n // Register Super-registers Sets...\n"; 750 751 // Emit the empty super-registers list 752 OS << " const unsigned Empty_SuperRegsSet[] = { 0 };\n"; 753 // Loop over all of the registers which have super-registers, emitting the 754 // super-registers list to memory. 755 for (std::map<Record*, std::set<Record*>, LessRecord >::iterator 756 I = RegisterSuperRegs.begin(), E = RegisterSuperRegs.end(); I != E; ++I) { 757 OS << " const unsigned " << I->first->getName() << "_SuperRegsSet[] = { "; 758 759 std::vector<Record*> SuperRegsVector; 760 for (std::set<Record*>::iterator ASI = I->second.begin(), 761 E = I->second.end(); ASI != E; ++ASI) 762 SuperRegsVector.push_back(*ASI); 763 RegisterSorter RS(RegisterSubRegs); 764 std::stable_sort(SuperRegsVector.begin(), SuperRegsVector.end(), RS); 765 for (unsigned i = 0, e = SuperRegsVector.size(); i != e; ++i) 766 OS << getQualifiedName(SuperRegsVector[i]) << ", "; 767 OS << "0 };\n"; 768 } 769 770 OS<<"\n const TargetRegisterDesc RegisterDescriptors[] = { // Descriptors\n"; 771 OS << " { \"NOREG\",\t\"NOREG\",\t0,\t0,\t0 },\n"; 772 773 // Now that register alias and sub-registers sets have been emitted, emit the 774 // register descriptors now. 775 const std::vector<CodeGenRegister> &Registers = Target.getRegisters(); 776 for (unsigned i = 0, e = Registers.size(); i != e; ++i) { 777 const CodeGenRegister &Reg = Registers[i]; 778 OS << " { \""; 779 if (!Reg.TheDef->getValueAsString("AsmName").empty()) 780 OS << Reg.TheDef->getValueAsString("AsmName"); 781 else 782 OS << Reg.getName(); 783 OS << "\",\t\""; 784 OS << Reg.getName() << "\",\t"; 785 if (RegisterAliases.count(Reg.TheDef)) 786 OS << Reg.getName() << "_AliasSet,\t"; 787 else 788 OS << "Empty_AliasSet,\t"; 789 if (RegisterSubRegs.count(Reg.TheDef)) 790 OS << Reg.getName() << "_SubRegsSet,\t"; 791 else 792 OS << "Empty_SubRegsSet,\t"; 793 if (RegisterSuperRegs.count(Reg.TheDef)) 794 OS << Reg.getName() << "_SuperRegsSet },\n"; 795 else 796 OS << "Empty_SuperRegsSet },\n"; 797 } 798 OS << " };\n"; // End of register descriptors... 799 OS << "}\n\n"; // End of anonymous namespace... 800 801 std::string ClassName = Target.getName() + "GenRegisterInfo"; 802 803 // Calculate the mapping of subregister+index pairs to physical registers. 804 std::vector<Record*> SubRegs = Records.getAllDerivedDefinitions("SubRegSet"); 805 for (unsigned i = 0, e = SubRegs.size(); i != e; ++i) { 806 int subRegIndex = SubRegs[i]->getValueAsInt("index"); 807 std::vector<Record*> From = SubRegs[i]->getValueAsListOfDefs("From"); 808 std::vector<Record*> To = SubRegs[i]->getValueAsListOfDefs("To"); 809 810 if (From.size() != To.size()) { 811 cerr << "Error: register list and sub-register list not of equal length" 812 << " in SubRegSet\n"; 813 exit(1); 814 } 815 816 // For each entry in from/to vectors, insert the to register at index 817 for (unsigned ii = 0, ee = From.size(); ii != ee; ++ii) 818 SubRegVectors[From[ii]].push_back(std::make_pair(subRegIndex, To[ii])); 819 } 820 821 // Emit the subregister + index mapping function based on the information 822 // calculated above. 823 OS << "unsigned " << ClassName 824 << "::getSubReg(unsigned RegNo, unsigned Index) const {\n" 825 << " switch (RegNo) {\n" 826 << " default:\n return 0;\n"; 827 for (std::map<Record*, std::vector<std::pair<int, Record*> > >::iterator 828 I = SubRegVectors.begin(), E = SubRegVectors.end(); I != E; ++I) { 829 OS << " case " << getQualifiedName(I->first) << ":\n"; 830 OS << " switch (Index) {\n"; 831 OS << " default: return 0;\n"; 832 for (unsigned i = 0, e = I->second.size(); i != e; ++i) 833 OS << " case " << (I->second)[i].first << ": return " 834 << getQualifiedName((I->second)[i].second) << ";\n"; 835 OS << " };\n" << " break;\n"; 836 } 837 OS << " };\n"; 838 OS << " return 0;\n"; 839 OS << "}\n\n"; 840 841 // Emit the constructor of the class... 842 OS << ClassName << "::" << ClassName 843 << "(int CallFrameSetupOpcode, int CallFrameDestroyOpcode)\n" 844 << " : TargetRegisterInfo(RegisterDescriptors, " << Registers.size()+1 845 << ", RegisterClasses, RegisterClasses+" << RegisterClasses.size() <<",\n " 846 << " CallFrameSetupOpcode, CallFrameDestroyOpcode,\n" 847 << " SubregHashTable, SubregHashTableSize,\n" 848 << " SuperregHashTable, SuperregHashTableSize,\n" 849 << " AliasesHashTable, AliasesHashTableSize) {\n" 850 << "}\n\n"; 851 852 // Collect all information about dwarf register numbers 853 854 // First, just pull all provided information to the map 855 unsigned maxLength = 0; 856 for (unsigned i = 0, e = Registers.size(); i != e; ++i) { 857 Record *Reg = Registers[i].TheDef; 858 std::vector<int64_t> RegNums = Reg->getValueAsListOfInts("DwarfNumbers"); 859 maxLength = std::max((size_t)maxLength, RegNums.size()); 860 if (DwarfRegNums.count(Reg)) 861 cerr << "Warning: DWARF numbers for register " << getQualifiedName(Reg) 862 << "specified multiple times\n"; 863 DwarfRegNums[Reg] = RegNums; 864 } 865 866 // Now we know maximal length of number list. Append -1's, where needed 867 for (DwarfRegNumsMapTy::iterator 868 I = DwarfRegNums.begin(), E = DwarfRegNums.end(); I != E; ++I) 869 for (unsigned i = I->second.size(), e = maxLength; i != e; ++i) 870 I->second.push_back(-1); 871 872 // Emit information about the dwarf register numbers. 873 OS << "int " << ClassName << "::getDwarfRegNumFull(unsigned RegNum, " 874 << "unsigned Flavour) const {\n" 875 << " switch (Flavour) {\n" 876 << " default:\n" 877 << " assert(0 && \"Unknown DWARF flavour\");\n" 878 << " return -1;\n"; 879 880 for (unsigned i = 0, e = maxLength; i != e; ++i) { 881 OS << " case " << i << ":\n" 882 << " switch (RegNum) {\n" 883 << " default:\n" 884 << " assert(0 && \"Invalid RegNum\");\n" 885 << " return -1;\n"; 886 887 // Sort by name to get a stable order. 888 889 890 for (DwarfRegNumsMapTy::iterator 891 I = DwarfRegNums.begin(), E = DwarfRegNums.end(); I != E; ++I) { 892 int RegNo = I->second[i]; 893 if (RegNo != -2) 894 OS << " case " << getQualifiedName(I->first) << ":\n" 895 << " return " << RegNo << ";\n"; 896 else 897 OS << " case " << getQualifiedName(I->first) << ":\n" 898 << " assert(0 && \"Invalid register for this mode\");\n" 899 << " return -1;\n"; 900 } 901 OS << " };\n"; 902 } 903 904 OS << " };\n}\n\n"; 905 906 OS << "} // End llvm namespace \n"; 907} 908