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