utils/TableGen/TableGen.cpp

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