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