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