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