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