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