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