1 //===- TableGen.cpp - Top-Level TableGen implementation -------------------===//
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.
9 //===----------------------------------------------------------------------===//
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"
26 GenRegisterEnums, GenRegister, GenRegisterHeader,
27 GenInstrEnums, GenInstrs, GenInstrSelector,
34 Action(cl::desc("Action to perform:"),
35 cl::values(clEnumValN(PrintRecords, "print-records",
36 "Print all records to stdout (default)"),
37 clEnumValN(GenEmitter, "gen-emitter",
38 "Generate machine code emitter"),
39 clEnumValN(GenRegisterEnums, "gen-register-enums",
40 "Generate enum values for registers"),
41 clEnumValN(GenRegister, "gen-register-desc",
42 "Generate a register info description"),
43 clEnumValN(GenRegisterHeader, "gen-register-desc-header",
44 "Generate a register info description header"),
45 clEnumValN(GenInstrEnums, "gen-instr-enums",
46 "Generate enum values for instructions"),
47 clEnumValN(GenInstrs, "gen-instr-desc",
48 "Generate instruction descriptions"),
49 clEnumValN(GenInstrSelector, "gen-instr-selector",
50 "Generate an instruction selector"),
51 clEnumValN(PrintEnums, "print-enums",
52 "Print enum values for a class"),
53 clEnumValN(Parse, "parse",
54 "Interpret machine code (testing only)"),
58 Class("class", cl::desc("Print Enum list for this class"),
59 cl::value_desc("class name"));
62 OutputFilename("o", cl::desc("Output filename"), cl::value_desc("filename"),
66 InputFilename(cl::Positional, cl::desc("<input file>"), cl::init("-"));
69 IncludeDir("I", cl::desc("Directory of include files"),
70 cl::value_desc("directory"), cl::init(""));
74 void ParseFile(const std::string &Filename, const std::string & IncludeDir);
78 static Init *getBit(Record *R, unsigned BitNo) {
79 const std::vector<RecordVal> &V = R->getValues();
80 for (unsigned i = 0, e = V.size(); i != e; ++i)
81 if (V[i].getPrefix()) {
82 assert(dynamic_cast<BitsInit*>(V[i].getValue()) &&
83 "Can only handle fields of bits<> type!");
84 BitsInit *I = (BitsInit*)V[i].getValue();
85 if (BitNo < I->getNumBits())
86 return I->getBit(BitNo);
87 BitNo -= I->getNumBits();
90 std::cerr << "Cannot find requested bit!\n";
95 static unsigned getNumBits(Record *R) {
96 const std::vector<RecordVal> &V = R->getValues();
98 for (unsigned i = 0, e = V.size(); i != e; ++i)
99 if (V[i].getPrefix()) {
100 assert(dynamic_cast<BitsInit*>(V[i].getValue()) &&
101 "Can only handle fields of bits<> type!");
102 Num += ((BitsInit*)V[i].getValue())->getNumBits();
107 static bool BitsAreFixed(Record *I1, Record *I2, unsigned BitNo) {
108 return dynamic_cast<BitInit*>(getBit(I1, BitNo)) &&
109 dynamic_cast<BitInit*>(getBit(I2, BitNo));
112 static bool BitsAreEqual(Record *I1, Record *I2, unsigned BitNo) {
113 BitInit *Bit1 = dynamic_cast<BitInit*>(getBit(I1, BitNo));
114 BitInit *Bit2 = dynamic_cast<BitInit*>(getBit(I2, BitNo));
116 return Bit1 && Bit2 && Bit1->getValue() == Bit2->getValue();
119 static bool BitRangesEqual(Record *I1, Record *I2,
120 unsigned Start, unsigned End) {
121 for (unsigned i = Start; i != End; ++i)
122 if (!BitsAreEqual(I1, I2, i))
127 static unsigned getFirstFixedBit(Record *R, unsigned FirstFixedBit) {
128 // Look for the first bit of the pair that are required to be 0 or 1.
129 while (!dynamic_cast<BitInit*>(getBit(R, FirstFixedBit)))
131 return FirstFixedBit;
134 static void FindInstDifferences(Record *I1, Record *I2,
135 unsigned FirstFixedBit, unsigned MaxBits,
136 unsigned &FirstVaryingBitOverall,
137 unsigned &LastFixedBitOverall) {
138 // Compare the first instruction to the rest of the instructions, looking for
139 // fields that differ.
141 unsigned FirstVaryingBit = FirstFixedBit;
142 while (FirstVaryingBit < MaxBits && BitsAreEqual(I1, I2, FirstVaryingBit))
145 unsigned LastFixedBit = FirstVaryingBit;
146 while (LastFixedBit < MaxBits && BitsAreFixed(I1, I2, LastFixedBit))
149 if (FirstVaryingBit < FirstVaryingBitOverall)
150 FirstVaryingBitOverall = FirstVaryingBit;
151 if (LastFixedBit < LastFixedBitOverall)
152 LastFixedBitOverall = LastFixedBit;
155 static bool getBitValue(Record *R, unsigned BitNo) {
156 Init *I = getBit(R, BitNo);
157 assert(dynamic_cast<BitInit*>(I) && "Bit should be fixed!");
158 return ((BitInit*)I)->getValue();
161 struct BitComparator {
162 unsigned BitBegin, BitEnd;
163 BitComparator(unsigned B, unsigned E) : BitBegin(B), BitEnd(E) {}
165 bool operator()(Record *R1, Record *R2) { // Return true if R1 is less than R2
166 for (unsigned i = BitBegin; i != BitEnd; ++i) {
167 bool V1 = getBitValue(R1, i), V2 = getBitValue(R2, i);
177 static void PrintRange(std::vector<Record*>::iterator I,
178 std::vector<Record*>::iterator E) {
179 while (I != E) std::cerr << **I++;
182 static bool getMemoryBit(unsigned char *M, unsigned i) {
183 return (M[i/8] & (1 << (i&7))) != 0;
186 static unsigned getFirstFixedBitInSequence(std::vector<Record*>::iterator IB,
187 std::vector<Record*>::iterator IE,
189 unsigned FirstFixedBit = 0;
190 for (std::vector<Record*>::iterator I = IB; I != IE; ++I)
191 FirstFixedBit = std::max(FirstFixedBit, getFirstFixedBit(*I, StartBit));
192 return FirstFixedBit;
195 // ParseMachineCode - Try to split the vector of instructions (which is
196 // intentionally taken by-copy) in half, narrowing down the possible
197 // instructions that we may have found. Eventually, this list will get pared
198 // down to zero or one instruction, in which case we have a match or failure.
200 static Record *ParseMachineCode(std::vector<Record*>::iterator InstsB,
201 std::vector<Record*>::iterator InstsE,
203 assert(InstsB != InstsE && "Empty range?");
204 if (InstsB+1 == InstsE) {
205 // Only a single instruction, see if we match it...
206 Record *Inst = *InstsB;
207 for (unsigned i = 0, e = getNumBits(Inst); i != e; ++i)
208 if (BitInit *BI = dynamic_cast<BitInit*>(getBit(Inst, i)))
209 if (getMemoryBit(M, i) != BI->getValue())
210 throw std::string("Parse failed!\n");
214 unsigned MaxBits = ~0;
215 for (std::vector<Record*>::iterator I = InstsB; I != InstsE; ++I)
216 MaxBits = std::min(MaxBits, getNumBits(*I));
218 unsigned FirstFixedBit = getFirstFixedBitInSequence(InstsB, InstsE, 0);
219 unsigned FirstVaryingBit, LastFixedBit;
221 FirstVaryingBit = ~0;
223 for (std::vector<Record*>::iterator I = InstsB+1; I != InstsE; ++I)
224 FindInstDifferences(*InstsB, *I, FirstFixedBit, MaxBits,
225 FirstVaryingBit, LastFixedBit);
226 if (FirstVaryingBit == MaxBits) {
227 std::cerr << "ERROR: Could not find bit to distinguish between "
228 << "the following entries!\n";
229 PrintRange(InstsB, InstsE);
233 std::cerr << "FVB: " << FirstVaryingBit << " - " << LastFixedBit
234 << ": " << InstsE-InstsB << "\n";
237 FirstFixedBit = getFirstFixedBitInSequence(InstsB, InstsE, FirstVaryingBit);
238 } while (FirstVaryingBit != FirstFixedBit);
240 //std::cerr << "\n\nXXXXXXXXXXXXXXXXX\n\n";
241 //PrintRange(InstsB, InstsE);
243 // Sort the Insts list so that the entries have all of the bits in the range
244 // [FirstVaryingBit,LastFixedBit) sorted. These bits are all guaranteed to be
245 // set to either 0 or 1 (BitInit values), which simplifies things.
247 std::sort(InstsB, InstsE, BitComparator(FirstVaryingBit, LastFixedBit));
249 // Once the list is sorted by these bits, split the bit list into smaller
250 // lists, and recurse on each one.
252 std::vector<Record*>::iterator RangeBegin = InstsB;
254 while (RangeBegin != InstsE) {
255 std::vector<Record*>::iterator RangeEnd = RangeBegin+1;
256 while (RangeEnd != InstsE &&
257 BitRangesEqual(*RangeBegin, *RangeEnd, FirstVaryingBit, LastFixedBit))
260 // We just identified a range of equal instructions. If this range is the
261 // input range, we were not able to distinguish between the instructions in
262 // the set. Print an error and exit!
264 if (RangeBegin == InstsB && RangeEnd == InstsE) {
265 std::cerr << "Error: Could not distinguish among the following insts!:\n";
266 PrintRange(InstsB, InstsE);
271 std::cerr << "FVB: " << FirstVaryingBit << " - " << LastFixedBit
272 << ": [" << RangeEnd-RangeBegin << "] - ";
273 for (int i = LastFixedBit-1; i >= (int)FirstVaryingBit; --i)
274 std::cerr << (int)((BitInit*)getBit(*RangeBegin, i))->getValue() << " ";
278 if (Record *R = ParseMachineCode(RangeBegin, RangeEnd, M)) {
280 std::cerr << "Error: Multiple matches found:\n";
281 PrintRange(InstsB, InstsE);
284 assert(Match == 0 && "Multiple matches??");
287 RangeBegin = RangeEnd;
293 static void PrintValue(Record *I, unsigned char *Ptr, const RecordVal &Val) {
294 assert(dynamic_cast<BitsInit*>(Val.getValue()) &&
295 "Can only handle undefined bits<> types!");
296 BitsInit *BI = (BitsInit*)Val.getValue();
297 assert(BI->getNumBits() <= 32 && "Can only handle fields up to 32 bits!");
300 const std::vector<RecordVal> &Vals = I->getValues();
302 // Start by filling in fixed values...
303 for (unsigned i = 0, e = BI->getNumBits(); i != e; ++i)
304 if (BitInit *B = dynamic_cast<BitInit*>(BI->getBit(i)))
305 Value |= B->getValue() << i;
307 // Loop over all of the fields in the instruction adding in any
308 // contributions to this value (due to bit references).
311 for (unsigned f = 0, e = Vals.size(); f != e; ++f)
312 if (Vals[f].getPrefix()) {
313 BitsInit *FieldInitializer = (BitsInit*)Vals[f].getValue();
314 if (&Vals[f] == &Val) {
315 // Read the bits directly now...
316 for (unsigned i = 0, e = BI->getNumBits(); i != e; ++i)
317 Value |= getMemoryBit(Ptr, Offset+i) << i;
321 // Scan through the field looking for bit initializers of the current
323 for (unsigned i = 0, e = FieldInitializer->getNumBits(); i != e; ++i)
324 if (VarBitInit *VBI =
325 dynamic_cast<VarBitInit*>(FieldInitializer->getBit(i))) {
326 TypedInit *TI = VBI->getVariable();
327 if (VarInit *VI = dynamic_cast<VarInit*>(TI)) {
328 if (VI->getName() == Val.getName())
329 Value |= getMemoryBit(Ptr, Offset+i) << VBI->getBitNum();
330 } else if (FieldInit *FI = dynamic_cast<FieldInit*>(TI)) {
331 // FIXME: implement this!
332 std::cerr << "FIELD INIT not implemented yet!\n";
335 Offset += FieldInitializer->getNumBits();
338 std::cout << "0x" << std::hex << Value << std::dec;
341 static void PrintInstruction(Record *I, unsigned char *Ptr) {
342 std::cout << "Inst " << getNumBits(I)/8 << " bytes: "
343 << "\t" << I->getName() << "\t" << *I->getValue("Name")->getValue()
346 const std::vector<RecordVal> &Vals = I->getValues();
347 for (unsigned i = 0, e = Vals.size(); i != e; ++i)
348 if (!Vals[i].getValue()->isComplete()) {
349 std::cout << Vals[i].getName() << "=";
350 PrintValue(I, Ptr, Vals[i]);
354 std::cout << "\n";// << *I;
357 static void ParseMachineCode() {
359 unsigned char Buffer[] = {
361 0x89, 0xE5, // mov EBP, ESP
362 //0x83, 0xEC, 0x08, // sub ESP, 0x8
363 0xE8, 1, 2, 3, 4, // call +0x04030201
364 0x89, 0xEC, // mov ESP, EBP
369 0x89, 0xF6, // mov ESI, ESI
370 0x68, 1, 2, 3, 4, // push 0x04030201
372 0xFF, 0xD0, // call EAX
373 0xB8, 1, 2, 3, 4, // mov EAX, 0x04030201
374 0x85, 0xC0, // test EAX, EAX
380 unsigned char Buffer[] = { 0xbf, 0xe0, 0x20, 0x1f, 0x1, 0x0, 0x0, 0x1,
381 0x0, 0x0, 0x0, 0x0, 0xc1, 0x0, 0x20, 0x1, 0x1,
382 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0,
383 0x0, 0x0, 0x0, 0x0, 0x0, 0x40, 0x0, 0x0, 0x0, 0x1,
384 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0,
385 0x0, 0x0, 0xaf, 0xe8, 0x20, 0x17
389 std::vector<Record*> Insts = Records.getAllDerivedDefinitions("Instruction");
391 unsigned char *BuffPtr = Buffer;
393 Record *R = ParseMachineCode(Insts.begin(), Insts.end(), BuffPtr);
394 PrintInstruction(R, BuffPtr);
396 unsigned Bits = getNumBits(R);
397 assert((Bits & 7) == 0 && "Instruction is not an even number of bytes!");
403 int main(int argc, char **argv) {
404 cl::ParseCommandLineOptions(argc, argv);
405 ParseFile(InputFilename, IncludeDir);
407 std::ostream *Out = &std::cout;
408 if (OutputFilename != "-") {
409 // Output to a .tmp file, because we don't actually want to overwrite the
410 // output file unless the generated file is different or the specified file
412 Out = new std::ofstream((OutputFilename+".tmp").c_str());
415 std::cerr << argv[0] << ": error opening " << OutputFilename << ".tmp!\n";
419 // Make sure the file gets removed if *gasp* tablegen crashes...
420 RemoveFileOnSignal(OutputFilename+".tmp");
426 *Out << Records; // No argument, dump all contents
432 CodeEmitterGen(Records).run(*Out);
435 case GenRegisterEnums:
436 RegisterInfoEmitter(Records).runEnums(*Out);
439 RegisterInfoEmitter(Records).run(*Out);
441 case GenRegisterHeader:
442 RegisterInfoEmitter(Records).runHeader(*Out);
446 InstrInfoEmitter(Records).runEnums(*Out);
449 InstrInfoEmitter(Records).run(*Out);
451 case GenInstrSelector:
452 InstrSelectorEmitter(Records).run(*Out);
455 std::vector<Record*> Recs = Records.getAllDerivedDefinitions(Class);
456 for (unsigned i = 0, e = Recs.size(); i != e; ++i)
457 *Out << Recs[i] << ", ";
461 } catch (const std::string &Error) {
462 std::cerr << Error << "\n";
463 if (Out != &std::cout) {
464 delete Out; // Close the file
465 std::remove(OutputFilename.c_str()); // Remove the file, it's broken
470 if (Out != &std::cout) {
471 delete Out; // Close the file
473 // Now that we have generated the result, check to see if we either don't
474 // have the requested file, or if the requested file is different than the
475 // file we generated. If so, move the generated file over the requested
476 // file. Otherwise, just remove the file we just generated, so 'make'
477 // doesn't try to regenerate tons of dependencies.
479 MoveFileOverIfUpdated(OutputFilename+".tmp", OutputFilename);