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