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