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