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