utils/TableGen/TableGen.cpp

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