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      << "  unsigned getSubRegIndex(unsigned RegNo, unsigned SubRegNo) 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
 106 bool 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
 116 static 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     errs() << "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
 137 static 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     errs() << "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
 159 class RegisterSorter {
 160 private:
 161   std::map<Record*, std::set<Record*>, LessRecord> &RegisterSubRegs;
 162
 163 public:
 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 //
 175 void RegisterInfoEmitter::run(raw_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 EVT " << 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         errs() << "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         errs() << "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         errs() << "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\",\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     OS << Reg.getName() << "\",\t";
 780     if (RegisterAliases.count(Reg.TheDef))
 781       OS << Reg.getName() << "_AliasSet,\t";
 782     else
 783       OS << "Empty_AliasSet,\t";
 784     if (RegisterSubRegs.count(Reg.TheDef))
 785       OS << Reg.getName() << "_SubRegsSet,\t";
 786     else
 787       OS << "Empty_SubRegsSet,\t";
 788     if (RegisterSuperRegs.count(Reg.TheDef))
 789       OS << Reg.getName() << "_SuperRegsSet },\n";
 790     else
 791       OS << "Empty_SuperRegsSet },\n";
 792   }
 793   OS << "  };\n";      // End of register descriptors...
 794   OS << "}\n\n";       // End of anonymous namespace...
 795
 796   std::string ClassName = Target.getName() + "GenRegisterInfo";
 797
 798   // Calculate the mapping of subregister+index pairs to physical registers.
 799   std::vector<Record*> SubRegs = Records.getAllDerivedDefinitions("SubRegSet");
 800   for (unsigned i = 0, e = SubRegs.size(); i != e; ++i) {
 801     int subRegIndex = SubRegs[i]->getValueAsInt("index");
 802     std::vector<Record*> From = SubRegs[i]->getValueAsListOfDefs("From");
 803     std::vector<Record*> To   = SubRegs[i]->getValueAsListOfDefs("To");
 804
 805     if (From.size() != To.size()) {
 806       errs() << "Error: register list and sub-register list not of equal length"
 807              << " in SubRegSet\n";
 808       exit(1);
 809     }
 810
 811     // For each entry in from/to vectors, insert the to register at index
 812     for (unsigned ii = 0, ee = From.size(); ii != ee; ++ii)
 813       SubRegVectors[From[ii]].push_back(std::make_pair(subRegIndex, To[ii]));
 814   }
 815
 816   // Emit the subregister + index mapping function based on the information
 817   // calculated above.
 818   OS << "unsigned " << ClassName
 819      << "::getSubReg(unsigned RegNo, unsigned Index) const {\n"
 820      << "  switch (RegNo) {\n"
 821      << "  default:\n    return 0;\n";
 822   for (std::map<Record*, std::vector<std::pair<int, Record*> > >::iterator
 823         I = SubRegVectors.begin(), E = SubRegVectors.end(); I != E; ++I) {
 824     OS << "  case " << getQualifiedName(I->first) << ":\n";
 825     OS << "    switch (Index) {\n";
 826     OS << "    default: return 0;\n";
 827     for (unsigned i = 0, e = I->second.size(); i != e; ++i)
 828       OS << "    case " << (I->second)[i].first << ": return "
 829          << getQualifiedName((I->second)[i].second) << ";\n";
 830     OS << "    };\n" << "    break;\n";
 831   }
 832   OS << "  };\n";
 833   OS << "  return 0;\n";
 834   OS << "}\n\n";
 835
 836   OS << "unsigned " << ClassName
 837      << "::getSubRegIndex(unsigned RegNo, unsigned SubRegNo) const {\n"
 838      << "  switch (RegNo) {\n"
 839      << "  default:\n    return 0;\n";
 840   for (std::map<Record*, std::vector<std::pair<int, Record*> > >::iterator
 841         I = SubRegVectors.begin(), E = SubRegVectors.end(); I != E; ++I) {
 842     OS << "  case " << getQualifiedName(I->first) << ":\n";
 843     for (unsigned i = 0, e = I->second.size(); i != e; ++i)
 844       OS << "    if (SubRegNo == "
 845          << getQualifiedName((I->second)[i].second)
 846          << ")  return " << (I->second)[i].first << ";\n";
 847     OS << "    return 0;\n";
 848   }
 849   OS << "  };\n";
 850   OS << "  return 0;\n";
 851   OS << "}\n\n";
 852
 853   // Emit the constructor of the class...
 854   OS << ClassName << "::" << ClassName
 855      << "(int CallFrameSetupOpcode, int CallFrameDestroyOpcode)\n"
 856      << "  : TargetRegisterInfo(RegisterDescriptors, " << Registers.size()+1
 857      << ", RegisterClasses, RegisterClasses+" << RegisterClasses.size() <<",\n "
 858      << "                 CallFrameSetupOpcode, CallFrameDestroyOpcode,\n"
 859      << "                 SubregHashTable, SubregHashTableSize,\n"
 860      << "                 SuperregHashTable, SuperregHashTableSize,\n"
 861      << "                 AliasesHashTable, AliasesHashTableSize) {\n"
 862      << "}\n\n";
 863
 864   // Collect all information about dwarf register numbers
 865
 866   // First, just pull all provided information to the map
 867   unsigned maxLength = 0;
 868   for (unsigned i = 0, e = Registers.size(); i != e; ++i) {
 869     Record *Reg = Registers[i].TheDef;
 870     std::vector<int64_t> RegNums = Reg->getValueAsListOfInts("DwarfNumbers");
 871     maxLength = std::max((size_t)maxLength, RegNums.size());
 872     if (DwarfRegNums.count(Reg))
 873       errs() << "Warning: DWARF numbers for register " << getQualifiedName(Reg)
 874              << "specified multiple times\n";
 875     DwarfRegNums[Reg] = RegNums;
 876   }
 877
 878   // Now we know maximal length of number list. Append -1's, where needed
 879   for (DwarfRegNumsMapTy::iterator
 880        I = DwarfRegNums.begin(), E = DwarfRegNums.end(); I != E; ++I)
 881     for (unsigned i = I->second.size(), e = maxLength; i != e; ++i)
 882       I->second.push_back(-1);
 883
 884   // Emit information about the dwarf register numbers.
 885   OS << "int " << ClassName << "::getDwarfRegNumFull(unsigned RegNum, "
 886      << "unsigned Flavour) const {\n"
 887      << "  switch (Flavour) {\n"
 888      << "  default:\n"
 889      << "    assert(0 && \"Unknown DWARF flavour\");\n"
 890      << "    return -1;\n";
 891
 892   for (unsigned i = 0, e = maxLength; i != e; ++i) {
 893     OS << "  case " << i << ":\n"
 894        << "    switch (RegNum) {\n"
 895        << "    default:\n"
 896        << "      assert(0 && \"Invalid RegNum\");\n"
 897        << "      return -1;\n";
 898
 899     // Sort by name to get a stable order.
 900
 901
 902     for (DwarfRegNumsMapTy::iterator
 903            I = DwarfRegNums.begin(), E = DwarfRegNums.end(); I != E; ++I) {
 904       int RegNo = I->second[i];
 905       if (RegNo != -2)
 906         OS << "    case " << getQualifiedName(I->first) << ":\n"
 907            << "      return " << RegNo << ";\n";
 908       else
 909         OS << "    case " << getQualifiedName(I->first) << ":\n"
 910            << "      assert(0 && \"Invalid register for this mode\");\n"
 911            << "      return -1;\n";
 912     }
 913     OS << "    };\n";
 914   }
 915
 916   OS << "  };\n}\n\n";
 917
 918   OS << "} // End llvm namespace \n";
 919 }