utils/TableGen/TableGen.cpp

   1 #include "Record.h"
   2 #include "Support/CommandLine.h"
   3 #include "CodeEmitterGen.h"
   4 #include <algorithm>
   5
   6 enum ActionType {
   7   PrintRecords,
   8   GenEmitter,
   9   PrintEnums,
  10   Parse,
  11 };
  12
  13 namespace {
  14   cl::opt<ActionType>
  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)"),
  24                     0));
  25
  26   cl::opt<std::string>
  27   Class("class", cl::desc("Print Enum list for this class"));
  28 }
  29
  30
  31 void ParseFile();
  32
  33 RecordKeeper Records;
  34
  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();
  45     }
  46
  47   std::cerr << "Cannot find requested bit!\n";
  48   abort();
  49   return 0;
  50 }
  51
  52 static unsigned getNumBits(Record *R) {
  53   const std::vector<RecordVal> &V = R->getValues();
  54   unsigned Num = 0;
  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();
  60     }
  61   return Num;
  62 }
  63
  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));
  67 }
  68
  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));
  72
  73   return Bit1 && Bit2 && Bit1->getValue() == Bit2->getValue();
  74 }
  75
  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))
  80       return false;
  81   return true;
  82 }
  83
  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)))
  87     ++FirstFixedBit;
  88   return FirstFixedBit;
  89 }
  90
  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.
  97   //
  98   unsigned FirstVaryingBit = FirstFixedBit;
  99   while (FirstVaryingBit < MaxBits && BitsAreEqual(I1, I2, FirstVaryingBit))
 100     ++FirstVaryingBit;
 101
 102   unsigned LastFixedBit = FirstVaryingBit;
 103   while (LastFixedBit < MaxBits && BitsAreFixed(I1, I2, LastFixedBit))
 104     ++LastFixedBit;
 105
 106   if (FirstVaryingBit < FirstVaryingBitOverall)
 107     FirstVaryingBitOverall = FirstVaryingBit;
 108   if (LastFixedBit < LastFixedBitOverall)
 109     LastFixedBitOverall = LastFixedBit;
 110 }
 111
 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();
 116 }
 117
 118 struct BitComparator {
 119   unsigned BitBegin, BitEnd;
 120   BitComparator(unsigned B, unsigned E) : BitBegin(B), BitEnd(E) {}
 121
 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);
 125       if (V1 < V2)
 126         return true;
 127       else if (V2 < V1)
 128         return false;
 129     }
 130     return false;
 131   }
 132 };
 133
 134 static void PrintRange(std::vector<Record*>::iterator I,
 135                        std::vector<Record*>::iterator E) {
 136   while (I != E) std::cerr << **I++;
 137 }
 138
 139 static bool getMemoryBit(unsigned char *M, unsigned i) {
 140   return (M[i/8] & (1 << (i&7))) != 0;
 141 }
 142
 143 static unsigned getFirstFixedBitInSequence(std::vector<Record*>::iterator IB,
 144                                            std::vector<Record*>::iterator IE,
 145                                            unsigned StartBit) {
 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;
 150 }
 151
 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.
 156 //
 157 static Record *ParseMachineCode(std::vector<Record*>::iterator InstsB,
 158                                 std::vector<Record*>::iterator InstsE,
 159                                 unsigned char *M) {
 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())
 167           return 0;
 168     return Inst;
 169   }
 170
 171   unsigned MaxBits = ~0;
 172   for (std::vector<Record*>::iterator I = InstsB; I != InstsE; ++I)
 173     MaxBits = std::min(MaxBits, getNumBits(*I));
 174
 175   unsigned FirstFixedBit = getFirstFixedBitInSequence(InstsB, InstsE, 0);
 176   unsigned FirstVaryingBit, LastFixedBit;
 177   do {
 178     FirstVaryingBit = ~0;
 179     LastFixedBit = ~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);
 187     }
 188
 189 #if 0
 190     std::cerr << "FVB: " << FirstVaryingBit << " - " << LastFixedBit
 191               << ": " << InstsE-InstsB << "\n";
 192 #endif
 193
 194     FirstFixedBit = getFirstFixedBitInSequence(InstsB, InstsE, FirstVaryingBit);
 195   } while (FirstVaryingBit != FirstFixedBit);
 196
 197   //std::cerr << "\n\nXXXXXXXXXXXXXXXXX\n\n";
 198   //PrintRange(InstsB, InstsE);
 199
 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.
 203   //
 204   std::sort(InstsB, InstsE, BitComparator(FirstVaryingBit, LastFixedBit));
 205
 206   // Once the list is sorted by these bits, split the bit list into smaller
 207   // lists, and recurse on each one.
 208   //
 209   std::vector<Record*>::iterator RangeBegin = InstsB;
 210   Record *Match = 0;
 211   while (RangeBegin != InstsE) {
 212     std::vector<Record*>::iterator RangeEnd = RangeBegin+1;
 213     while (RangeEnd != InstsE &&
 214           BitRangesEqual(*RangeBegin, *RangeEnd, FirstVaryingBit, LastFixedBit))
 215       ++RangeEnd;
 216
 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!
 220     //
 221     if (RangeBegin == InstsB && RangeEnd == InstsE) {
 222       std::cerr << "Error: Could not distinguish among the following insts!:\n";
 223       PrintRange(InstsB, InstsE);
 224       abort();
 225     }
 226
 227 #if 0
 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() << " ";
 232     std::cerr << "\n";
 233 #endif
 234
 235     if (Record *R = ParseMachineCode(RangeBegin, RangeEnd, M)) {
 236       if (Match) {
 237         std::cerr << "Error: Multiple matches found:\n";
 238         PrintRange(InstsB, InstsE);
 239       }
 240
 241       assert(Match == 0 && "Multiple matches??");
 242       Match = R;
 243     }
 244     RangeBegin = RangeEnd;
 245   }
 246
 247   return Match;
 248 }
 249
 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!");
 255
 256   unsigned Value = 0;
 257   const std::vector<RecordVal> &Vals = I->getValues();
 258
 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;
 263
 264   // Loop over all of the fields in the instruction adding in any
 265   // contributions to this value (due to bit references).
 266   //
 267   unsigned Offset = 0;
 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;
 275         break;
 276       }
 277
 278       // Scan through the field looking for bit initializers of the current
 279       // variable...
 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";
 290           }
 291         }
 292       Offset += FieldInitializer->getNumBits();
 293     }
 294
 295   std::cout << "0x" << std::hex << Value << std::dec;
 296 }
 297
 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()
 301             << "\t";
 302
 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]);
 308       std::cout << "\t";
 309     }
 310
 311   std::cout << "\n";// << *I;
 312 }
 313
 314 static void ParseMachineCode() {
 315   // X86 code
 316   unsigned char Buffer[] = {
 317                              0x55,             // push EBP
 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
 322                              0x5D,             // pop EBP
 323                              0xC3,             // ret
 324                              0x90,             // nop
 325                              0xC9,             // leave
 326                              0x89, 0xF6,       // mov ESI, ESI
 327                              0x68, 1, 2, 3, 4, // push 0x04030201
 328                              0x5e,             // pop ESI
 329                              0xFF, 0xD0,       // call EAX
 330                              0xB8, 1, 2, 3, 4, // mov EAX, 0x04030201
 331                              0x85, 0xC0,       // test EAX, EAX
 332                              0xF4,             // hlt
 333   };
 334
 335 #if 0
 336   // SparcV9 code
 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
 343   };
 344 #endif
 345
 346   std::vector<Record*> Insts;
 347
 348   const std::map<std::string, Record*> &Defs = Records.getDefs();
 349   Record *Inst = Records.getClass("Instruction");
 350   assert(Inst && "Couldn't find Instruction class!");
 351
 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);
 356
 357   unsigned char *BuffPtr = Buffer;
 358   while (1) {
 359     Record *R = ParseMachineCode(Insts.begin(), Insts.end(), BuffPtr);
 360     if (R == 0) {
 361       std::cout << "Parse failed!\n";
 362       return;
 363     }
 364     PrintInstruction(R, BuffPtr);
 365
 366     unsigned Bits = getNumBits(R);
 367     assert((Bits & 7) == 0 && "Instruction is not an even number of bytes!");
 368     BuffPtr += Bits/8;
 369   }
 370 }
 371
 372
 373 int main(int argc, char **argv) {
 374   cl::ParseCommandLineOptions(argc, argv);
 375   ParseFile();
 376
 377   switch (Action) {
 378   case Parse: ParseMachineCode(); break;
 379   case GenEmitter:
 380     CodeEmitterGen(Records).createEmitter(std::cout);
 381     break;
 382   case PrintRecords:
 383     std::cout << Records;           // No argument, dump all contents
 384     break;
 385   case PrintEnums:
 386     Record *R = Records.getClass(Class);
 387     if (R == 0) {
 388       std::cerr << "Cannot find class '" << Class << "'!\n";
 389       abort();
 390     }
 391
 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 << ", ";
 397       }
 398     }
 399     std::cout << "\n";
 400     break;
 401   }
 402   return 0;
 403 }