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