utils/TableGen/TableGen.cpp

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