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