1 //===- TableGen.cpp - Top-Level TableGen implementation -------------------===//
3 // The LLVM Compiler Infrastructure
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.
8 //===----------------------------------------------------------------------===//
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.
16 //===----------------------------------------------------------------------===//
19 #include "Support/CommandLine.h"
20 #include "llvm/System/Signals.h"
21 #include "Support/FileUtilities.h"
22 #include "CodeEmitterGen.h"
23 #include "RegisterInfoEmitter.h"
24 #include "InstrInfoEmitter.h"
25 #include "InstrSelectorEmitter.h"
34 GenRegisterEnums, GenRegister, GenRegisterHeader,
35 GenInstrEnums, GenInstrs, GenInstrSelector,
42 Action(cl::desc("Action to perform:"),
43 cl::values(clEnumValN(PrintRecords, "print-records",
44 "Print all records to stdout (default)"),
45 clEnumValN(GenEmitter, "gen-emitter",
46 "Generate machine code emitter"),
47 clEnumValN(GenRegisterEnums, "gen-register-enums",
48 "Generate enum values for registers"),
49 clEnumValN(GenRegister, "gen-register-desc",
50 "Generate a register info description"),
51 clEnumValN(GenRegisterHeader, "gen-register-desc-header",
52 "Generate a register info description header"),
53 clEnumValN(GenInstrEnums, "gen-instr-enums",
54 "Generate enum values for instructions"),
55 clEnumValN(GenInstrs, "gen-instr-desc",
56 "Generate instruction descriptions"),
57 clEnumValN(GenInstrSelector, "gen-instr-selector",
58 "Generate an instruction selector"),
59 clEnumValN(PrintEnums, "print-enums",
60 "Print enum values for a class"),
61 clEnumValN(Parse, "parse",
62 "Interpret machine code (testing only)"),
66 Class("class", cl::desc("Print Enum list for this class"),
67 cl::value_desc("class name"));
70 OutputFilename("o", cl::desc("Output filename"), cl::value_desc("filename"),
74 InputFilename(cl::Positional, cl::desc("<input file>"), cl::init("-"));
77 IncludeDir("I", cl::desc("Directory of include files"),
78 cl::value_desc("directory"), cl::init(""));
82 void ParseFile(const std::string &Filename,
83 const std::string &IncludeDir);
86 RecordKeeper llvm::Records;
88 static Init *getBit(Record *R, unsigned BitNo) {
89 const std::vector<RecordVal> &V = R->getValues();
90 for (unsigned i = 0, e = V.size(); i != e; ++i)
91 if (V[i].getPrefix()) {
92 assert(dynamic_cast<BitsInit*>(V[i].getValue()) &&
93 "Can only handle fields of bits<> type!");
94 BitsInit *I = (BitsInit*)V[i].getValue();
95 if (BitNo < I->getNumBits())
96 return I->getBit(BitNo);
97 BitNo -= I->getNumBits();
100 std::cerr << "Cannot find requested bit!\n";
105 static unsigned getNumBits(Record *R) {
106 const std::vector<RecordVal> &V = R->getValues();
108 for (unsigned i = 0, e = V.size(); i != e; ++i)
109 if (V[i].getPrefix()) {
110 assert(dynamic_cast<BitsInit*>(V[i].getValue()) &&
111 "Can only handle fields of bits<> type!");
112 Num += ((BitsInit*)V[i].getValue())->getNumBits();
117 static bool BitsAreFixed(Record *I1, Record *I2, unsigned BitNo) {
118 return dynamic_cast<BitInit*>(getBit(I1, BitNo)) &&
119 dynamic_cast<BitInit*>(getBit(I2, BitNo));
122 static bool BitsAreEqual(Record *I1, Record *I2, unsigned BitNo) {
123 BitInit *Bit1 = dynamic_cast<BitInit*>(getBit(I1, BitNo));
124 BitInit *Bit2 = dynamic_cast<BitInit*>(getBit(I2, BitNo));
126 return Bit1 && Bit2 && Bit1->getValue() == Bit2->getValue();
129 static bool BitRangesEqual(Record *I1, Record *I2,
130 unsigned Start, unsigned End) {
131 for (unsigned i = Start; i != End; ++i)
132 if (!BitsAreEqual(I1, I2, i))
137 static unsigned getFirstFixedBit(Record *R, unsigned FirstFixedBit) {
138 // Look for the first bit of the pair that are required to be 0 or 1.
139 while (!dynamic_cast<BitInit*>(getBit(R, FirstFixedBit)))
141 return FirstFixedBit;
144 static void FindInstDifferences(Record *I1, Record *I2,
145 unsigned FirstFixedBit, unsigned MaxBits,
146 unsigned &FirstVaryingBitOverall,
147 unsigned &LastFixedBitOverall) {
148 // Compare the first instruction to the rest of the instructions, looking for
149 // fields that differ.
151 unsigned FirstVaryingBit = FirstFixedBit;
152 while (FirstVaryingBit < MaxBits && BitsAreEqual(I1, I2, FirstVaryingBit))
155 unsigned LastFixedBit = FirstVaryingBit;
156 while (LastFixedBit < MaxBits && BitsAreFixed(I1, I2, LastFixedBit))
159 if (FirstVaryingBit < FirstVaryingBitOverall)
160 FirstVaryingBitOverall = FirstVaryingBit;
161 if (LastFixedBit < LastFixedBitOverall)
162 LastFixedBitOverall = LastFixedBit;
165 static bool getBitValue(Record *R, unsigned BitNo) {
166 Init *I = getBit(R, BitNo);
167 assert(dynamic_cast<BitInit*>(I) && "Bit should be fixed!");
168 return ((BitInit*)I)->getValue();
171 struct BitComparator {
172 unsigned BitBegin, BitEnd;
173 BitComparator(unsigned B, unsigned E) : BitBegin(B), BitEnd(E) {}
175 bool operator()(Record *R1, Record *R2) { // Return true if R1 is less than R2
176 for (unsigned i = BitBegin; i != BitEnd; ++i) {
177 bool V1 = getBitValue(R1, i), V2 = getBitValue(R2, i);
187 static void PrintRange(std::vector<Record*>::iterator I,
188 std::vector<Record*>::iterator E) {
189 while (I != E) std::cerr << **I++;
192 static bool getMemoryBit(unsigned char *M, unsigned i) {
193 return (M[i/8] & (1 << (i&7))) != 0;
196 static unsigned getFirstFixedBitInSequence(std::vector<Record*>::iterator IB,
197 std::vector<Record*>::iterator IE,
199 unsigned FirstFixedBit = 0;
200 for (std::vector<Record*>::iterator I = IB; I != IE; ++I)
201 FirstFixedBit = std::max(FirstFixedBit, getFirstFixedBit(*I, StartBit));
202 return FirstFixedBit;
205 // ParseMachineCode - Try to split the vector of instructions (which is
206 // intentionally taken by-copy) in half, narrowing down the possible
207 // instructions that we may have found. Eventually, this list will get pared
208 // down to zero or one instruction, in which case we have a match or failure.
210 static Record *ParseMachineCode(std::vector<Record*>::iterator InstsB,
211 std::vector<Record*>::iterator InstsE,
213 assert(InstsB != InstsE && "Empty range?");
214 if (InstsB+1 == InstsE) {
215 // Only a single instruction, see if we match it...
216 Record *Inst = *InstsB;
217 for (unsigned i = 0, e = getNumBits(Inst); i != e; ++i)
218 if (BitInit *BI = dynamic_cast<BitInit*>(getBit(Inst, i)))
219 if (getMemoryBit(M, i) != BI->getValue())
220 throw std::string("Parse failed!\n");
224 unsigned MaxBits = ~0;
225 for (std::vector<Record*>::iterator I = InstsB; I != InstsE; ++I)
226 MaxBits = std::min(MaxBits, getNumBits(*I));
228 unsigned FirstFixedBit = getFirstFixedBitInSequence(InstsB, InstsE, 0);
229 unsigned FirstVaryingBit, LastFixedBit;
231 FirstVaryingBit = ~0;
233 for (std::vector<Record*>::iterator I = InstsB+1; I != InstsE; ++I)
234 FindInstDifferences(*InstsB, *I, FirstFixedBit, MaxBits,
235 FirstVaryingBit, LastFixedBit);
236 if (FirstVaryingBit == MaxBits) {
237 std::cerr << "ERROR: Could not find bit to distinguish between "
238 << "the following entries!\n";
239 PrintRange(InstsB, InstsE);
243 std::cerr << "FVB: " << FirstVaryingBit << " - " << LastFixedBit
244 << ": " << InstsE-InstsB << "\n";
247 FirstFixedBit = getFirstFixedBitInSequence(InstsB, InstsE, FirstVaryingBit);
248 } while (FirstVaryingBit != FirstFixedBit);
250 //std::cerr << "\n\nXXXXXXXXXXXXXXXXX\n\n";
251 //PrintRange(InstsB, InstsE);
253 // Sort the Insts list so that the entries have all of the bits in the range
254 // [FirstVaryingBit,LastFixedBit) sorted. These bits are all guaranteed to be
255 // set to either 0 or 1 (BitInit values), which simplifies things.
257 std::sort(InstsB, InstsE, BitComparator(FirstVaryingBit, LastFixedBit));
259 // Once the list is sorted by these bits, split the bit list into smaller
260 // lists, and recurse on each one.
262 std::vector<Record*>::iterator RangeBegin = InstsB;
264 while (RangeBegin != InstsE) {
265 std::vector<Record*>::iterator RangeEnd = RangeBegin+1;
266 while (RangeEnd != InstsE &&
267 BitRangesEqual(*RangeBegin, *RangeEnd, FirstVaryingBit, LastFixedBit))
270 // We just identified a range of equal instructions. If this range is the
271 // input range, we were not able to distinguish between the instructions in
272 // the set. Print an error and exit!
274 if (RangeBegin == InstsB && RangeEnd == InstsE) {
275 std::cerr << "Error: Could not distinguish among the following insts!:\n";
276 PrintRange(InstsB, InstsE);
281 std::cerr << "FVB: " << FirstVaryingBit << " - " << LastFixedBit
282 << ": [" << RangeEnd-RangeBegin << "] - ";
283 for (int i = LastFixedBit-1; i >= (int)FirstVaryingBit; --i)
284 std::cerr << (int)((BitInit*)getBit(*RangeBegin, i))->getValue() << " ";
288 if (Record *R = ParseMachineCode(RangeBegin, RangeEnd, M)) {
290 std::cerr << "Error: Multiple matches found:\n";
291 PrintRange(InstsB, InstsE);
294 assert(Match == 0 && "Multiple matches??");
297 RangeBegin = RangeEnd;
303 static void PrintValue(Record *I, unsigned char *Ptr, const RecordVal &Val) {
304 assert(dynamic_cast<BitsInit*>(Val.getValue()) &&
305 "Can only handle undefined bits<> types!");
306 BitsInit *BI = (BitsInit*)Val.getValue();
307 assert(BI->getNumBits() <= 32 && "Can only handle fields up to 32 bits!");
310 const std::vector<RecordVal> &Vals = I->getValues();
312 // Start by filling in fixed values...
313 for (unsigned i = 0, e = BI->getNumBits(); i != e; ++i)
314 if (BitInit *B = dynamic_cast<BitInit*>(BI->getBit(i)))
315 Value |= B->getValue() << i;
317 // Loop over all of the fields in the instruction adding in any
318 // contributions to this value (due to bit references).
321 for (unsigned f = 0, e = Vals.size(); f != e; ++f)
322 if (Vals[f].getPrefix()) {
323 BitsInit *FieldInitializer = (BitsInit*)Vals[f].getValue();
324 if (&Vals[f] == &Val) {
325 // Read the bits directly now...
326 for (unsigned i = 0, e = BI->getNumBits(); i != e; ++i)
327 Value |= getMemoryBit(Ptr, Offset+i) << i;
331 // Scan through the field looking for bit initializers of the current
333 for (unsigned i = 0, e = FieldInitializer->getNumBits(); i != e; ++i)
334 if (VarBitInit *VBI =
335 dynamic_cast<VarBitInit*>(FieldInitializer->getBit(i))) {
336 TypedInit *TI = VBI->getVariable();
337 if (VarInit *VI = dynamic_cast<VarInit*>(TI)) {
338 if (VI->getName() == Val.getName())
339 Value |= getMemoryBit(Ptr, Offset+i) << VBI->getBitNum();
340 } else if (FieldInit *FI = dynamic_cast<FieldInit*>(TI)) {
341 // FIXME: implement this!
342 std::cerr << "FIELD INIT not implemented yet!\n";
345 Offset += FieldInitializer->getNumBits();
348 std::cout << "0x" << std::hex << Value << std::dec;
351 static void PrintInstruction(Record *I, unsigned char *Ptr) {
352 std::cout << "Inst " << getNumBits(I)/8 << " bytes: "
353 << "\t" << I->getName() << "\t" << *I->getValue("Name")->getValue()
356 const std::vector<RecordVal> &Vals = I->getValues();
357 for (unsigned i = 0, e = Vals.size(); i != e; ++i)
358 if (!Vals[i].getValue()->isComplete()) {
359 std::cout << Vals[i].getName() << "=";
360 PrintValue(I, Ptr, Vals[i]);
364 std::cout << "\n";// << *I;
367 static void ParseMachineCode() {
369 unsigned char Buffer[] = {
371 0x89, 0xE5, // mov EBP, ESP
372 //0x83, 0xEC, 0x08, // sub ESP, 0x8
373 0xE8, 1, 2, 3, 4, // call +0x04030201
374 0x89, 0xEC, // mov ESP, EBP
379 0x89, 0xF6, // mov ESI, ESI
380 0x68, 1, 2, 3, 4, // push 0x04030201
382 0xFF, 0xD0, // call EAX
383 0xB8, 1, 2, 3, 4, // mov EAX, 0x04030201
384 0x85, 0xC0, // test EAX, EAX
390 unsigned char Buffer[] = { 0xbf, 0xe0, 0x20, 0x1f, 0x1, 0x0, 0x0, 0x1,
391 0x0, 0x0, 0x0, 0x0, 0xc1, 0x0, 0x20, 0x1, 0x1,
392 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0,
393 0x0, 0x0, 0x0, 0x0, 0x0, 0x40, 0x0, 0x0, 0x0, 0x1,
394 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0,
395 0x0, 0x0, 0xaf, 0xe8, 0x20, 0x17
399 std::vector<Record*> Insts = Records.getAllDerivedDefinitions("Instruction");
401 unsigned char *BuffPtr = Buffer;
403 Record *R = ParseMachineCode(Insts.begin(), Insts.end(), BuffPtr);
404 PrintInstruction(R, BuffPtr);
406 unsigned Bits = getNumBits(R);
407 assert((Bits & 7) == 0 && "Instruction is not an even number of bytes!");
412 int main(int argc, char **argv) {
413 cl::ParseCommandLineOptions(argc, argv);
414 ParseFile(InputFilename, IncludeDir);
416 std::ostream *Out = &std::cout;
417 if (OutputFilename != "-") {
418 Out = new std::ofstream(OutputFilename.c_str());
421 std::cerr << argv[0] << ": error opening " << OutputFilename << "!\n";
425 // Make sure the file gets removed if *gasp* tablegen crashes...
426 RemoveFileOnSignal(OutputFilename);
432 *Out << Records; // No argument, dump all contents
438 CodeEmitterGen(Records).run(*Out);
441 case GenRegisterEnums:
442 RegisterInfoEmitter(Records).runEnums(*Out);
445 RegisterInfoEmitter(Records).run(*Out);
447 case GenRegisterHeader:
448 RegisterInfoEmitter(Records).runHeader(*Out);
452 InstrInfoEmitter(Records).runEnums(*Out);
455 InstrInfoEmitter(Records).run(*Out);
457 case GenInstrSelector:
458 InstrSelectorEmitter(Records).run(*Out);
462 std::vector<Record*> Recs = Records.getAllDerivedDefinitions(Class);
463 for (unsigned i = 0, e = Recs.size(); i != e; ++i)
464 *Out << Recs[i]->getName() << ", ";
469 assert(1 && "Invalid Action");
472 } catch (const std::string &Error) {
473 std::cerr << Error << "\n";
474 if (Out != &std::cout) {
475 delete Out; // Close the file
476 std::remove(OutputFilename.c_str()); // Remove the file, it's broken
481 if (Out != &std::cout) {
482 delete Out; // Close the file