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