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