utils/TableGen/TableGen.cpp

   1 #include "Record.h"
   2 #include "Support/CommandLine.h"
   3 #include "Support/Signals.h"
   4 #include "CodeEmitterGen.h"
   5 #include <algorithm>
   6 #include <fstream>
   7
   8 enum ActionType {
   9   PrintRecords,
  10   GenEmitter,
  11   PrintEnums,
  12   Parse,
  13 };
  14
  15 namespace {
  16   cl::opt<ActionType>
  17   Action(cl::desc("Action to perform:"),
  18          cl::values(clEnumValN(PrintRecords, "print-records",
  19                                "Print all records to stdout (default)"),
  20                     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>
  29   Class("class", cl::desc("Print Enum list for this class"),
  30         cl::value_desc("class name"));
  31
  32   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("-"));
  38 }
  39
  40
  41 void ParseFile(const std::string &Filename);
  42
  43 RecordKeeper Records;
  44
  45 static 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
  62 static 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
  74 static 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
  79 static 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
  86 static 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
  94 static 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
 101 static 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
 122 static 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
 128 struct 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
 144 static void PrintRange(std::vector<Record*>::iterator I,
 145                        std::vector<Record*>::iterator E) {
 146   while (I != E) std::cerr << **I++;
 147 }
 148
 149 static bool getMemoryBit(unsigned char *M, unsigned i) {
 150   return (M[i/8] & (1 << (i&7))) != 0;
 151 }
 152
 153 static 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 //
 167 static 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
 237 #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
 245     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
 260 static 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()) {
 280       BitsInit *FieldInitializer = (BitsInit*)Vals[f].getValue();
 281       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...
 290       for (unsigned i = 0, e = FieldInitializer->getNumBits(); i != e; ++i)
 291         if (VarBitInit *VBI =
 292             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           }
 301         }
 302       Offset += FieldInitializer->getNumBits();
 303     }
 304
 305   std::cout << "0x" << std::hex << Value << std::dec;
 306 }
 307
 308 static 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
 324 static void ParseMachineCode() {
 325   // X86 code
 326   unsigned char Buffer[] = {
 327                              0x55,             // push EBP
 328                              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
 337                              0x68, 1, 2, 3, 4, // push 0x04030201
 338                              0x5e,             // pop ESI
 339                              0xFF, 0xD0,       // call EAX
 340                              0xB8, 1, 2, 3, 4, // mov EAX, 0x04030201
 341                              0x85, 0xC0,       // test EAX, EAX
 342                              0xF4,             // hlt
 343   };
 344
 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
 356   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
 383 int main(int argc, char **argv) {
 384   cl::ParseCommandLineOptions(argc, argv);
 385   ParseFile(InputFilename);
 386
 387   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
 400   int ErrorCode = 0;
 401
 402   switch (Action) {
 403   case Parse: ParseMachineCode(); break;
 404   case GenEmitter:
 405     ErrorCode = CodeEmitterGen(Records).run(*Out);
 406     break;
 407   case PrintRecords:
 408     *Out << Records;           // No argument, dump all contents
 409     break;
 410   case PrintEnums:
 411     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)) {
 421         *Out << I->first << ", ";
 422       }
 423     }
 424     *Out << "\n";
 425     break;
 426   }
 427
 428   if (Out != &std::cout) delete Out;
 429   return ErrorCode;
 430 }