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