utils/TableGen/TableGen.cpp

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