2 #include "Support/CommandLine.h"
3 #include "CodeEmitterGen.h"
15 Action(cl::desc("Action to perform:"),
16 cl::values(clEnumValN(PrintRecords, "print-records",
17 "Print all records to stdout"),
18 clEnumValN(GenEmitter, "gen-emitter",
19 "Generate machine code emitter"),
20 clEnumValN(PrintEnums, "print-enums",
21 "Print enum values for a class"),
22 clEnumValN(Parse, "parse",
23 "Interpret machine code (testing only)"),
27 Class("class", cl::desc("Print Enum list for this class"));
35 static Init *getBit(Record *R, unsigned BitNo) {
36 const std::vector<RecordVal> &V = R->getValues();
37 for (unsigned i = 0, e = V.size(); i != e; ++i)
38 if (V[i].getPrefix()) {
39 assert(dynamic_cast<BitsInit*>(V[i].getValue()) &&
40 "Can only handle fields of bits<> type!");
41 BitsInit *I = (BitsInit*)V[i].getValue();
42 if (BitNo < I->getNumBits())
43 return I->getBit(BitNo);
44 BitNo -= I->getNumBits();
47 std::cerr << "Cannot find requested bit!\n";
52 static unsigned getNumBits(Record *R) {
53 const std::vector<RecordVal> &V = R->getValues();
55 for (unsigned i = 0, e = V.size(); i != e; ++i)
56 if (V[i].getPrefix()) {
57 assert(dynamic_cast<BitsInit*>(V[i].getValue()) &&
58 "Can only handle fields of bits<> type!");
59 Num += ((BitsInit*)V[i].getValue())->getNumBits();
64 static bool BitsAreFixed(Record *I1, Record *I2, unsigned BitNo) {
65 return dynamic_cast<BitInit*>(getBit(I1, BitNo)) &&
66 dynamic_cast<BitInit*>(getBit(I2, BitNo));
69 static bool BitsAreEqual(Record *I1, Record *I2, unsigned BitNo) {
70 BitInit *Bit1 = dynamic_cast<BitInit*>(getBit(I1, BitNo));
71 BitInit *Bit2 = dynamic_cast<BitInit*>(getBit(I2, BitNo));
73 return Bit1 && Bit2 && Bit1->getValue() == Bit2->getValue();
76 static bool BitRangesEqual(Record *I1, Record *I2,
77 unsigned Start, unsigned End) {
78 for (unsigned i = Start; i != End; ++i)
79 if (!BitsAreEqual(I1, I2, i))
84 static unsigned getFirstFixedBit(Record *R, unsigned FirstFixedBit) {
85 // Look for the first bit of the pair that are required to be 0 or 1.
86 while (!dynamic_cast<BitInit*>(getBit(R, FirstFixedBit)))
91 static void FindInstDifferences(Record *I1, Record *I2,
92 unsigned FirstFixedBit, unsigned MaxBits,
93 unsigned &FirstVaryingBitOverall,
94 unsigned &LastFixedBitOverall) {
95 // Compare the first instruction to the rest of the instructions, looking for
96 // fields that differ.
98 unsigned FirstVaryingBit = FirstFixedBit;
99 while (FirstVaryingBit < MaxBits && BitsAreEqual(I1, I2, FirstVaryingBit))
102 unsigned LastFixedBit = FirstVaryingBit;
103 while (LastFixedBit < MaxBits && BitsAreFixed(I1, I2, LastFixedBit))
106 if (FirstVaryingBit < FirstVaryingBitOverall)
107 FirstVaryingBitOverall = FirstVaryingBit;
108 if (LastFixedBit < LastFixedBitOverall)
109 LastFixedBitOverall = LastFixedBit;
112 static bool getBitValue(Record *R, unsigned BitNo) {
113 Init *I = getBit(R, BitNo);
114 assert(dynamic_cast<BitInit*>(I) && "Bit should be fixed!");
115 return ((BitInit*)I)->getValue();
118 struct BitComparator {
119 unsigned BitBegin, BitEnd;
120 BitComparator(unsigned B, unsigned E) : BitBegin(B), BitEnd(E) {}
122 bool operator()(Record *R1, Record *R2) { // Return true if R1 is less than R2
123 for (unsigned i = BitBegin; i != BitEnd; ++i) {
124 bool V1 = getBitValue(R1, i), V2 = getBitValue(R2, i);
134 static void PrintRange(std::vector<Record*>::iterator I,
135 std::vector<Record*>::iterator E) {
136 while (I != E) std::cerr << **I++;
139 static bool getMemoryBit(unsigned char *M, unsigned i) {
140 return (M[i/8] & (1 << (i&7))) != 0;
143 static unsigned getFirstFixedBitInSequence(std::vector<Record*>::iterator IB,
144 std::vector<Record*>::iterator IE,
146 unsigned FirstFixedBit = 0;
147 for (std::vector<Record*>::iterator I = IB; I != IE; ++I)
148 FirstFixedBit = std::max(FirstFixedBit, getFirstFixedBit(*I, StartBit));
149 return FirstFixedBit;
152 // ParseMachineCode - Try to split the vector of instructions (which is
153 // intentially taken by-copy) in half, narrowing down the possible instructions
154 // that we may have found. Eventually, this list will get pared down to zero or
155 // one instruction, in which case we have a match or failure.
157 static Record *ParseMachineCode(std::vector<Record*>::iterator InstsB,
158 std::vector<Record*>::iterator InstsE,
160 assert(InstsB != InstsE && "Empty range?");
161 if (InstsB+1 == InstsE) {
162 // Only a single instruction, see if we match it...
163 Record *Inst = *InstsB;
164 for (unsigned i = 0, e = getNumBits(Inst); i != e; ++i)
165 if (BitInit *BI = dynamic_cast<BitInit*>(getBit(Inst, i)))
166 if (getMemoryBit(M, i) != BI->getValue())
171 unsigned MaxBits = ~0;
172 for (std::vector<Record*>::iterator I = InstsB; I != InstsE; ++I)
173 MaxBits = std::min(MaxBits, getNumBits(*I));
175 unsigned FirstFixedBit = getFirstFixedBitInSequence(InstsB, InstsE, 0);
176 unsigned FirstVaryingBit, LastFixedBit;
178 FirstVaryingBit = ~0;
180 for (std::vector<Record*>::iterator I = InstsB+1; I != InstsE; ++I)
181 FindInstDifferences(*InstsB, *I, FirstFixedBit, MaxBits,
182 FirstVaryingBit, LastFixedBit);
183 if (FirstVaryingBit == MaxBits) {
184 std::cerr << "ERROR: Could not find bit to distinguish between "
185 << "the following entries!\n";
186 PrintRange(InstsB, InstsE);
190 std::cerr << "FVB: " << FirstVaryingBit << " - " << LastFixedBit
191 << ": " << InstsE-InstsB << "\n";
194 FirstFixedBit = getFirstFixedBitInSequence(InstsB, InstsE, FirstVaryingBit);
195 } while (FirstVaryingBit != FirstFixedBit);
197 //std::cerr << "\n\nXXXXXXXXXXXXXXXXX\n\n";
198 //PrintRange(InstsB, InstsE);
200 // Sort the Insts list so that the entries have all of the bits in the range
201 // [FirstVaryingBit,LastFixedBit) sorted. These bits are all guaranteed to be
202 // set to either 0 or 1 (BitInit values), which simplifies things.
204 std::sort(InstsB, InstsE, BitComparator(FirstVaryingBit, LastFixedBit));
206 // Once the list is sorted by these bits, split the bit list into smaller
207 // lists, and recurse on each one.
209 std::vector<Record*>::iterator RangeBegin = InstsB;
211 while (RangeBegin != InstsE) {
212 std::vector<Record*>::iterator RangeEnd = RangeBegin+1;
213 while (RangeEnd != InstsE &&
214 BitRangesEqual(*RangeBegin, *RangeEnd, FirstVaryingBit, LastFixedBit))
217 // We just identified a range of equal instructions. If this range is the
218 // input range, we were not able to distinguish between the instructions in
219 // the set. Print an error and exit!
221 if (RangeBegin == InstsB && RangeEnd == InstsE) {
222 std::cerr << "Error: Could not distinguish among the following insts!:\n";
223 PrintRange(InstsB, InstsE);
228 std::cerr << "FVB: " << FirstVaryingBit << " - " << LastFixedBit
229 << ": [" << RangeEnd-RangeBegin << "] - ";
230 for (int i = LastFixedBit-1; i >= (int)FirstVaryingBit; --i)
231 std::cerr << (int)((BitInit*)getBit(*RangeBegin, i))->getValue() << " ";
235 if (Record *R = ParseMachineCode(RangeBegin, RangeEnd, M)) {
237 std::cerr << "Error: Multiple matches found:\n";
238 PrintRange(InstsB, InstsE);
241 assert(Match == 0 && "Multiple matches??");
244 RangeBegin = RangeEnd;
250 static void PrintValue(Record *I, unsigned char *Ptr, const RecordVal &Val) {
251 assert(dynamic_cast<BitsInit*>(Val.getValue()) &&
252 "Can only handle undefined bits<> types!");
253 BitsInit *BI = (BitsInit*)Val.getValue();
254 assert(BI->getNumBits() <= 32 && "Can only handle fields up to 32 bits!");
257 const std::vector<RecordVal> &Vals = I->getValues();
259 // Start by filling in fixed values...
260 for (unsigned i = 0, e = BI->getNumBits(); i != e; ++i)
261 if (BitInit *B = dynamic_cast<BitInit*>(BI->getBit(i)))
262 Value |= B->getValue() << i;
264 // Loop over all of the fields in the instruction adding in any
265 // contributions to this value (due to bit references).
268 for (unsigned f = 0, e = Vals.size(); f != e; ++f)
269 if (Vals[f].getPrefix()) {
270 BitsInit *FieldInitializer = (BitsInit*)Vals[f].getValue();
271 if (&Vals[f] == &Val) {
272 // Read the bits directly now...
273 for (unsigned i = 0, e = BI->getNumBits(); i != e; ++i)
274 Value |= getMemoryBit(Ptr, Offset+i) << i;
278 // Scan through the field looking for bit initializers of the current
280 for (unsigned i = 0, e = FieldInitializer->getNumBits(); i != e; ++i)
281 if (VarBitInit *VBI =
282 dynamic_cast<VarBitInit*>(FieldInitializer->getBit(i))) {
283 TypedInit *TI = VBI->getVariable();
284 if (VarInit *VI = dynamic_cast<VarInit*>(TI)) {
285 if (VI->getName() == Val.getName())
286 Value |= getMemoryBit(Ptr, Offset+i) << VBI->getBitNum();
287 } else if (FieldInit *FI = dynamic_cast<FieldInit*>(TI)) {
288 // FIXME: implement this!
289 std::cerr << "FIELD INIT not implemented yet!\n";
292 Offset += FieldInitializer->getNumBits();
295 std::cout << "0x" << std::hex << Value << std::dec;
298 static void PrintInstruction(Record *I, unsigned char *Ptr) {
299 std::cout << "Inst " << getNumBits(I)/8 << " bytes: "
300 << "\t" << I->getName() << "\t" << *I->getValue("Name")->getValue()
303 const std::vector<RecordVal> &Vals = I->getValues();
304 for (unsigned i = 0, e = Vals.size(); i != e; ++i)
305 if (!Vals[i].getValue()->isComplete()) {
306 std::cout << Vals[i].getName() << "=";
307 PrintValue(I, Ptr, Vals[i]);
311 std::cout << "\n";// << *I;
314 static void ParseMachineCode() {
316 unsigned char Buffer[] = {
318 0x89, 0xE5, // mov EBP, ESP
319 //0x83, 0xEC, 0x08, // sub ESP, 0x8
320 0xE8, 1, 2, 3, 4, // call +0x04030201
321 0x89, 0xEC, // mov ESP, EBP
326 0x89, 0xF6, // mov ESI, ESI
327 0x68, 1, 2, 3, 4, // push 0x04030201
329 0xFF, 0xD0, // call EAX
330 0xB8, 1, 2, 3, 4, // mov EAX, 0x04030201
331 0x85, 0xC0, // test EAX, EAX
337 unsigned char Buffer[] = { 0xbf, 0xe0, 0x20, 0x1f, 0x1, 0x0, 0x0, 0x1,
338 0x0, 0x0, 0x0, 0x0, 0xc1, 0x0, 0x20, 0x1, 0x1,
339 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0,
340 0x0, 0x0, 0x0, 0x0, 0x0, 0x40, 0x0, 0x0, 0x0, 0x1,
341 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0,
342 0x0, 0x0, 0xaf, 0xe8, 0x20, 0x17
346 std::vector<Record*> Insts;
348 const std::map<std::string, Record*> &Defs = Records.getDefs();
349 Record *Inst = Records.getClass("Instruction");
350 assert(Inst && "Couldn't find Instruction class!");
352 for (std::map<std::string, Record*>::const_iterator I = Defs.begin(),
353 E = Defs.end(); I != E; ++I)
354 if (I->second->isSubClassOf(Inst))
355 Insts.push_back(I->second);
357 unsigned char *BuffPtr = Buffer;
359 Record *R = ParseMachineCode(Insts.begin(), Insts.end(), BuffPtr);
361 std::cout << "Parse failed!\n";
364 PrintInstruction(R, BuffPtr);
366 unsigned Bits = getNumBits(R);
367 assert((Bits & 7) == 0 && "Instruction is not an even number of bytes!");
373 int main(int argc, char **argv) {
374 cl::ParseCommandLineOptions(argc, argv);
378 case Parse: ParseMachineCode(); break;
380 CodeEmitterGen(Records).createEmitter(std::cout);
383 std::cout << Records; // No argument, dump all contents
386 Record *R = Records.getClass(Class);
388 std::cerr << "Cannot find class '" << Class << "'!\n";
392 const std::map<std::string, Record*> &Defs = Records.getDefs();
393 for (std::map<std::string, Record*>::const_iterator I = Defs.begin(),
394 E = Defs.end(); I != E; ++I) {
395 if (I->second->isSubClassOf(R)) {
396 std::cout << I->first << ", ";