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