TableGen.cpp revision 227b6d00dd1faee07c921c7e2256e0fca737d2e5 
1//===- TableGen.cpp - Top-Level TableGen implementation -------------------===//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file was developed by the LLVM research group and is distributed under
6// the University of Illinois Open Source License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// TableGen is a tool which can be used to build up a description of something,
11// then invoke one or more "tablegen backends" to emit information about the
12// description in some predefined format.  In practice, this is used by the LLVM
13// code generators to automate generation of a code generator through a
14// high-level description of the target.
15//
16//===----------------------------------------------------------------------===//
17
18#include "Record.h"
19#include "llvm/Support/CommandLine.h"
20#include "llvm/System/Signals.h"
21#include "llvm/Support/FileUtilities.h"
22#include "CodeEmitterGen.h"
23#include "RegisterInfoEmitter.h"
24#include "InstrInfoEmitter.h"
25#include "AsmWriterEmitter.h"
26#include "InstrSelectorEmitter.h"
27#include <algorithm>
28#include <cstdio>
29#include <fstream>
30using namespace llvm;
31
32enum ActionType {
33  PrintRecords,
34  GenEmitter,
35  GenRegisterEnums, GenRegister, GenRegisterHeader,
36  GenInstrEnums, GenInstrs, GenAsmWriter, GenInstrSelector,
37  PrintEnums,
38  Parse
39};
40
41namespace {
42  cl::opt<ActionType>
43  Action(cl::desc("Action to perform:"),
44         cl::values(clEnumValN(PrintRecords, "print-records",
45                               "Print all records to stdout (default)"),
46                    clEnumValN(GenEmitter, "gen-emitter",
47                               "Generate machine code emitter"),
48                    clEnumValN(GenRegisterEnums, "gen-register-enums",
49                               "Generate enum values for registers"),
50                    clEnumValN(GenRegister, "gen-register-desc",
51                               "Generate a register info description"),
52                    clEnumValN(GenRegisterHeader, "gen-register-desc-header",
53                               "Generate a register info description header"),
54                    clEnumValN(GenInstrEnums, "gen-instr-enums",
55                               "Generate enum values for instructions"),
56                    clEnumValN(GenInstrs, "gen-instr-desc",
57                               "Generate instruction descriptions"),
58                    clEnumValN(GenAsmWriter, "gen-asm-writer",
59                               "Generate assembly writer"),
60                    clEnumValN(GenInstrSelector, "gen-instr-selector",
61                               "Generate an instruction selector"),
62                    clEnumValN(PrintEnums, "print-enums",
63                               "Print enum values for a class"),
64                    clEnumValN(Parse, "parse",
65                               "Interpret machine code (testing only)"),
66                    clEnumValEnd));
67
68  cl::opt<std::string>
69  Class("class", cl::desc("Print Enum list for this class"),
70        cl::value_desc("class name"));
71
72  cl::opt<std::string>
73  OutputFilename("o", cl::desc("Output filename"), cl::value_desc("filename"),
74                 cl::init("-"));
75
76  cl::opt<std::string>
77  InputFilename(cl::Positional, cl::desc("<input file>"), cl::init("-"));
78
79  cl::opt<std::string>
80  IncludeDir("I", cl::desc("Directory of include files"),
81                  cl::value_desc("directory"), cl::init(""));
82}
83
84namespace llvm {
85  void ParseFile(const std::string &Filename,
86                 const std::string &IncludeDir);
87}
88
89RecordKeeper llvm::Records;
90
91static Init *getBit(Record *R, unsigned BitNo) {
92  const std::vector<RecordVal> &V = R->getValues();
93  for (unsigned i = 0, e = V.size(); i != e; ++i)
94    if (V[i].getPrefix()) {
95      assert(dynamic_cast<BitsInit*>(V[i].getValue()) &&
96	     "Can only handle fields of bits<> type!");
97      BitsInit *I = (BitsInit*)V[i].getValue();
98      if (BitNo < I->getNumBits())
99	return I->getBit(BitNo);
100      BitNo -= I->getNumBits();
101    }
102
103  std::cerr << "Cannot find requested bit!\n";
104  exit(1);
105  return 0;
106}
107
108static unsigned getNumBits(Record *R) {
109  const std::vector<RecordVal> &V = R->getValues();
110  unsigned Num = 0;
111  for (unsigned i = 0, e = V.size(); i != e; ++i)
112    if (V[i].getPrefix()) {
113      assert(dynamic_cast<BitsInit*>(V[i].getValue()) &&
114	     "Can only handle fields of bits<> type!");
115      Num += ((BitsInit*)V[i].getValue())->getNumBits();
116    }
117  return Num;
118}
119
120static bool BitsAreFixed(Record *I1, Record *I2, unsigned BitNo) {
121  return dynamic_cast<BitInit*>(getBit(I1, BitNo)) &&
122         dynamic_cast<BitInit*>(getBit(I2, BitNo));
123}
124
125static bool BitsAreEqual(Record *I1, Record *I2, unsigned BitNo) {
126  BitInit *Bit1 = dynamic_cast<BitInit*>(getBit(I1, BitNo));
127  BitInit *Bit2 = dynamic_cast<BitInit*>(getBit(I2, BitNo));
128
129  return Bit1 && Bit2 && Bit1->getValue() == Bit2->getValue();
130}
131
132static bool BitRangesEqual(Record *I1, Record *I2,
133			   unsigned Start, unsigned End) {
134  for (unsigned i = Start; i != End; ++i)
135    if (!BitsAreEqual(I1, I2, i))
136      return false;
137  return true;
138}
139
140static unsigned getFirstFixedBit(Record *R, unsigned FirstFixedBit) {
141  // Look for the first bit of the pair that are required to be 0 or 1.
142  while (!dynamic_cast<BitInit*>(getBit(R, FirstFixedBit)))
143    ++FirstFixedBit;
144  return FirstFixedBit;
145}
146
147static void FindInstDifferences(Record *I1, Record *I2,
148				unsigned FirstFixedBit, unsigned MaxBits,
149				unsigned &FirstVaryingBitOverall,
150				unsigned &LastFixedBitOverall) {
151  // Compare the first instruction to the rest of the instructions, looking for
152  // fields that differ.
153  //
154  unsigned FirstVaryingBit = FirstFixedBit;
155  while (FirstVaryingBit < MaxBits && BitsAreEqual(I1, I2, FirstVaryingBit))
156    ++FirstVaryingBit;
157
158  unsigned LastFixedBit = FirstVaryingBit;
159  while (LastFixedBit < MaxBits && BitsAreFixed(I1, I2, LastFixedBit))
160    ++LastFixedBit;
161
162  if (FirstVaryingBit < FirstVaryingBitOverall)
163    FirstVaryingBitOverall = FirstVaryingBit;
164  if (LastFixedBit < LastFixedBitOverall)
165    LastFixedBitOverall = LastFixedBit;
166}
167
168static bool getBitValue(Record *R, unsigned BitNo) {
169  Init *I = getBit(R, BitNo);
170  assert(dynamic_cast<BitInit*>(I) && "Bit should be fixed!");
171  return ((BitInit*)I)->getValue();
172}
173
174struct BitComparator {
175  unsigned BitBegin, BitEnd;
176  BitComparator(unsigned B, unsigned E) : BitBegin(B), BitEnd(E) {}
177
178  bool operator()(Record *R1, Record *R2) { // Return true if R1 is less than R2
179    for (unsigned i = BitBegin; i != BitEnd; ++i) {
180      bool V1 = getBitValue(R1, i), V2 = getBitValue(R2, i);
181      if (V1 < V2)
182	return true;
183      else if (V2 < V1)
184	return false;
185    }
186    return false;
187  }
188};
189
190static void PrintRange(std::vector<Record*>::iterator I,
191		       std::vector<Record*>::iterator E) {
192  while (I != E) std::cerr << **I++;
193}
194
195static bool getMemoryBit(unsigned char *M, unsigned i) {
196  return (M[i/8] & (1 << (i&7))) != 0;
197}
198
199static unsigned getFirstFixedBitInSequence(std::vector<Record*>::iterator IB,
200					   std::vector<Record*>::iterator IE,
201					   unsigned StartBit) {
202  unsigned FirstFixedBit = 0;
203  for (std::vector<Record*>::iterator I = IB; I != IE; ++I)
204    FirstFixedBit = std::max(FirstFixedBit, getFirstFixedBit(*I, StartBit));
205  return FirstFixedBit;
206}
207
208// ParseMachineCode - Try to split the vector of instructions (which is
209// intentionally taken by-copy) in half, narrowing down the possible
210// instructions that we may have found.  Eventually, this list will get pared
211// down to zero or one instruction, in which case we have a match or failure.
212//
213static Record *ParseMachineCode(std::vector<Record*>::iterator InstsB,
214				std::vector<Record*>::iterator InstsE,
215				unsigned char *M) {
216  assert(InstsB != InstsE && "Empty range?");
217  if (InstsB+1 == InstsE) {
218    // Only a single instruction, see if we match it...
219    Record *Inst = *InstsB;
220    for (unsigned i = 0, e = getNumBits(Inst); i != e; ++i)
221      if (BitInit *BI = dynamic_cast<BitInit*>(getBit(Inst, i)))
222	if (getMemoryBit(M, i) != BI->getValue())
223	  throw std::string("Parse failed!\n");
224    return Inst;
225  }
226
227  unsigned MaxBits = ~0;
228  for (std::vector<Record*>::iterator I = InstsB; I != InstsE; ++I)
229    MaxBits = std::min(MaxBits, getNumBits(*I));
230
231  unsigned FirstFixedBit = getFirstFixedBitInSequence(InstsB, InstsE, 0);
232  unsigned FirstVaryingBit, LastFixedBit;
233  do {
234    FirstVaryingBit = ~0;
235    LastFixedBit = ~0;
236    for (std::vector<Record*>::iterator I = InstsB+1; I != InstsE; ++I)
237      FindInstDifferences(*InstsB, *I, FirstFixedBit, MaxBits,
238			  FirstVaryingBit, LastFixedBit);
239    if (FirstVaryingBit == MaxBits) {
240      std::cerr << "ERROR: Could not find bit to distinguish between "
241		<< "the following entries!\n";
242      PrintRange(InstsB, InstsE);
243    }
244
245#if 0
246    std::cerr << "FVB: " << FirstVaryingBit << " - " << LastFixedBit
247	      << ": " << InstsE-InstsB << "\n";
248#endif
249
250    FirstFixedBit = getFirstFixedBitInSequence(InstsB, InstsE, FirstVaryingBit);
251  } while (FirstVaryingBit != FirstFixedBit);
252
253  //std::cerr << "\n\nXXXXXXXXXXXXXXXXX\n\n";
254  //PrintRange(InstsB, InstsE);
255
256  // Sort the Insts list so that the entries have all of the bits in the range
257  // [FirstVaryingBit,LastFixedBit) sorted.  These bits are all guaranteed to be
258  // set to either 0 or 1 (BitInit values), which simplifies things.
259  //
260  std::sort(InstsB, InstsE, BitComparator(FirstVaryingBit, LastFixedBit));
261
262  // Once the list is sorted by these bits, split the bit list into smaller
263  // lists, and recurse on each one.
264  //
265  std::vector<Record*>::iterator RangeBegin = InstsB;
266  Record *Match = 0;
267  while (RangeBegin != InstsE) {
268    std::vector<Record*>::iterator RangeEnd = RangeBegin+1;
269    while (RangeEnd != InstsE &&
270          BitRangesEqual(*RangeBegin, *RangeEnd, FirstVaryingBit, LastFixedBit))
271      ++RangeEnd;
272
273    // We just identified a range of equal instructions.  If this range is the
274    // input range, we were not able to distinguish between the instructions in
275    // the set.  Print an error and exit!
276    //
277    if (RangeBegin == InstsB && RangeEnd == InstsE) {
278      std::cerr << "Error: Could not distinguish among the following insts!:\n";
279      PrintRange(InstsB, InstsE);
280      exit(1);
281    }
282
283#if 0
284    std::cerr << "FVB: " << FirstVaryingBit << " - " << LastFixedBit
285	      << ": [" << RangeEnd-RangeBegin << "] - ";
286    for (int i = LastFixedBit-1; i >= (int)FirstVaryingBit; --i)
287      std::cerr << (int)((BitInit*)getBit(*RangeBegin, i))->getValue() << " ";
288    std::cerr << "\n";
289#endif
290
291    if (Record *R = ParseMachineCode(RangeBegin, RangeEnd, M)) {
292      if (Match) {
293	std::cerr << "Error: Multiple matches found:\n";
294	PrintRange(InstsB, InstsE);
295      }
296
297      assert(Match == 0 && "Multiple matches??");
298      Match = R;
299    }
300    RangeBegin = RangeEnd;
301  }
302
303  return Match;
304}
305
306static void PrintValue(Record *I, unsigned char *Ptr, const RecordVal &Val) {
307  assert(dynamic_cast<BitsInit*>(Val.getValue()) &&
308	 "Can only handle undefined bits<> types!");
309  BitsInit *BI = (BitsInit*)Val.getValue();
310  assert(BI->getNumBits() <= 32 && "Can only handle fields up to 32 bits!");
311
312  unsigned Value = 0;
313  const std::vector<RecordVal> &Vals = I->getValues();
314
315  // Start by filling in fixed values...
316  for (unsigned i = 0, e = BI->getNumBits(); i != e; ++i)
317    if (BitInit *B = dynamic_cast<BitInit*>(BI->getBit(i)))
318      Value |= B->getValue() << i;
319
320  // Loop over all of the fields in the instruction adding in any
321  // contributions to this value (due to bit references).
322  //
323  unsigned Offset = 0;
324  for (unsigned f = 0, e = Vals.size(); f != e; ++f)
325    if (Vals[f].getPrefix()) {
326      BitsInit *FieldInitializer = (BitsInit*)Vals[f].getValue();
327      if (&Vals[f] == &Val) {
328	// Read the bits directly now...
329	for (unsigned i = 0, e = BI->getNumBits(); i != e; ++i)
330	  Value |= getMemoryBit(Ptr, Offset+i) << i;
331	break;
332      }
333
334      // Scan through the field looking for bit initializers of the current
335      // variable...
336      for (unsigned i = 0, e = FieldInitializer->getNumBits(); i != e; ++i)
337	if (VarBitInit *VBI =
338	    dynamic_cast<VarBitInit*>(FieldInitializer->getBit(i))) {
339          TypedInit *TI = VBI->getVariable();
340          if (VarInit *VI = dynamic_cast<VarInit*>(TI)) {
341            if (VI->getName() == Val.getName())
342              Value |= getMemoryBit(Ptr, Offset+i) << VBI->getBitNum();
343          } else if (FieldInit *FI = dynamic_cast<FieldInit*>(TI)) {
344            // FIXME: implement this!
345            std::cerr << "FIELD INIT not implemented yet!\n";
346          }
347	}
348      Offset += FieldInitializer->getNumBits();
349    }
350
351  std::cout << "0x" << std::hex << Value << std::dec;
352}
353
354static void PrintInstruction(Record *I, unsigned char *Ptr) {
355  std::cout << "Inst " << getNumBits(I)/8 << " bytes: "
356	    << "\t" << I->getName() << "\t" << *I->getValue("Name")->getValue()
357	    << "\t";
358
359  const std::vector<RecordVal> &Vals = I->getValues();
360  for (unsigned i = 0, e = Vals.size(); i != e; ++i)
361    if (!Vals[i].getValue()->isComplete()) {
362      std::cout << Vals[i].getName() << "=";
363      PrintValue(I, Ptr, Vals[i]);
364      std::cout << "\t";
365    }
366
367  std::cout << "\n";// << *I;
368}
369
370static void ParseMachineCode() {
371  // X86 code
372  unsigned char Buffer[] = {
373                             0x55,             // push EBP
374			     0x89, 0xE5,       // mov EBP, ESP
375			     //0x83, 0xEC, 0x08, // sub ESP, 0x8
376			     0xE8, 1, 2, 3, 4, // call +0x04030201
377			     0x89, 0xEC,       // mov ESP, EBP
378			     0x5D,             // pop EBP
379			     0xC3,             // ret
380			     0x90,             // nop
381			     0xC9,             // leave
382			     0x89, 0xF6,       // mov ESI, ESI
383			     0x68, 1, 2, 3, 4, // push 0x04030201
384			     0x5e,             // pop ESI
385			     0xFF, 0xD0,       // call EAX
386			     0xB8, 1, 2, 3, 4, // mov EAX, 0x04030201
387			     0x85, 0xC0,       // test EAX, EAX
388			     0xF4,             // hlt
389  };
390
391#if 0
392  // SparcV9 code
393  unsigned char Buffer[] = { 0xbf, 0xe0, 0x20, 0x1f, 0x1, 0x0, 0x0, 0x1,
394                             0x0, 0x0, 0x0, 0x0, 0xc1, 0x0, 0x20, 0x1, 0x1,
395                             0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0,
396                             0x0, 0x0, 0x0, 0x0, 0x0, 0x40, 0x0, 0x0, 0x0, 0x1,
397                             0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0,
398                             0x0, 0x0, 0xaf, 0xe8, 0x20, 0x17
399  };
400#endif
401
402  std::vector<Record*> Insts = Records.getAllDerivedDefinitions("Instruction");
403
404  unsigned char *BuffPtr = Buffer;
405  while (1) {
406    Record *R = ParseMachineCode(Insts.begin(), Insts.end(), BuffPtr);
407    PrintInstruction(R, BuffPtr);
408
409    unsigned Bits = getNumBits(R);
410    assert((Bits & 7) == 0 && "Instruction is not an even number of bytes!");
411    BuffPtr += Bits/8;
412  }
413}
414
415int main(int argc, char **argv) {
416  cl::ParseCommandLineOptions(argc, argv);
417  ParseFile(InputFilename, IncludeDir);
418
419  std::ostream *Out = &std::cout;
420  if (OutputFilename != "-") {
421    Out = new std::ofstream(OutputFilename.c_str());
422
423    if (!Out->good()) {
424      std::cerr << argv[0] << ": error opening " << OutputFilename << "!\n";
425      return 1;
426    }
427
428    // Make sure the file gets removed if *gasp* tablegen crashes...
429    sys::RemoveFileOnSignal(sys::Path(OutputFilename));
430  }
431
432  try {
433    switch (Action) {
434    case PrintRecords:
435      *Out << Records;           // No argument, dump all contents
436      break;
437    case Parse:
438      ParseMachineCode();
439      break;
440    case GenEmitter:
441      CodeEmitterGen(Records).run(*Out);
442      break;
443
444    case GenRegisterEnums:
445      RegisterInfoEmitter(Records).runEnums(*Out);
446      break;
447    case GenRegister:
448      RegisterInfoEmitter(Records).run(*Out);
449      break;
450    case GenRegisterHeader:
451      RegisterInfoEmitter(Records).runHeader(*Out);
452      break;
453
454    case GenInstrEnums:
455      InstrInfoEmitter(Records).runEnums(*Out);
456      break;
457    case GenInstrs:
458      InstrInfoEmitter(Records).run(*Out);
459      break;
460
461    case GenAsmWriter:
462      AsmWriterEmitter(Records).run(*Out);
463      break;
464
465    case GenInstrSelector:
466      InstrSelectorEmitter(Records).run(*Out);
467      break;
468    case PrintEnums:
469    {
470      std::vector<Record*> Recs = Records.getAllDerivedDefinitions(Class);
471      for (unsigned i = 0, e = Recs.size(); i != e; ++i)
472        *Out << Recs[i]->getName() << ", ";
473      *Out << "\n";
474      break;
475    }
476    default:
477      assert(1 && "Invalid Action");
478      return 1;
479    }
480  } catch (const std::string &Error) {
481    std::cerr << argv[0] << ": " << Error << "\n";
482    if (Out != &std::cout) {
483      delete Out;                             // Close the file
484      std::remove(OutputFilename.c_str());    // Remove the file, it's broken
485    }
486    return 1;
487  } catch (...) {
488    std::cerr << argv[0] << ": Unknown unexpected exception occurred.\n";
489    if (Out != &std::cout) {
490      delete Out;                             // Close the file
491      std::remove(OutputFilename.c_str());    // Remove the file, it's broken
492    }
493    return 2;
494  }
495
496  if (Out != &std::cout) {
497    delete Out;                               // Close the file
498  }
499  return 0;
500}
501