utils/TableGen/RegisterInfoEmitter.cpp

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