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