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