utils/TableGen/RegisterInfoEmitter.cpp

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