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