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