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