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