TableGen.cpp revision ea3e5e56fdc56e5c2ddafb36eab26676e137dfa0
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 "llvm/Support/CommandLine.h" 20#include "llvm/System/Signals.h" 21#include "llvm/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> 30using namespace llvm; 31 32enum ActionType { 33 PrintRecords, 34 GenEmitter, 35 GenRegisterEnums, GenRegister, GenRegisterHeader, 36 GenInstrEnums, GenInstrs, GenAsmWriter, GenInstrSelector, 37 PrintEnums, 38 Parse 39}; 40 41namespace { 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 84namespace llvm { 85 void ParseFile(const std::string &Filename, 86 const std::string &IncludeDir); 87} 88 89RecordKeeper llvm::Records; 90 91static 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 108static 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 120static 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 125static 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 132static 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 140static 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 147static 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 168static 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 174struct 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 190static void PrintRange(std::vector<Record*>::iterator I, 191 std::vector<Record*>::iterator E) { 192 while (I != E) std::cerr << **I++; 193} 194 195static bool getMemoryBit(unsigned char *M, unsigned i) { 196 return (M[i/8] & (1 << (i&7))) != 0; 197} 198 199static 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// 213static 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 306static 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 354static 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 370static 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 415int 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(sys::Path(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 << argv[0] << ": " << 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 } catch (...) { 488 std::cerr << argv[0] << ": Unknown unexpected exception occurred.\n"; 489 if (Out != &std::cout) { 490 delete Out; // Close the file 491 std::remove(OutputFilename.c_str()); // Remove the file, it's broken 492 } 493 return 2; 494 } 495 496 if (Out != &std::cout) { 497 delete Out; // Close the file 498 } 499 return 0; 500} 501