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