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