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