support/tools/TableGen/TableGen.cpp

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