utils/TableGen/X86DisassemblerTables.cpp

   1 //===- X86DisassemblerTables.cpp - Disassembler tables ----------*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file is part of the X86 Disassembler Emitter.
  11 // It contains the implementation of the disassembler tables.
  12 // Documentation for the disassembler emitter in general can be found in
  13 //  X86DisasemblerEmitter.h.
  14 //
  15 //===----------------------------------------------------------------------===//
  16
  17 #include "X86DisassemblerShared.h"
  18 #include "X86DisassemblerTables.h"
  19
  20 #include "TableGenBackend.h"
  21 #include "llvm/Support/ErrorHandling.h"
  22 #include "llvm/Support/Format.h"
  23
  24 #include <string>
  25
  26 using namespace llvm;
  27 using namespace X86Disassembler;
  28
  29 /// inheritsFrom - Indicates whether all instructions in one class also belong
  30 ///   to another class.
  31 ///
  32 /// @param child  - The class that may be the subset
  33 /// @param parent - The class that may be the superset
  34 /// @return       - True if child is a subset of parent, false otherwise.
  35 static inline bool inheritsFrom(InstructionContext child,
  36                                 InstructionContext parent) {
  37   if (child == parent)
  38     return true;
  39
  40   switch (parent) {
  41   case IC:
  42     return true;
  43   case IC_64BIT:
  44     return(inheritsFrom(child, IC_64BIT_REXW)   ||
  45            inheritsFrom(child, IC_64BIT_OPSIZE) ||
  46            inheritsFrom(child, IC_64BIT_XD)     ||
  47            inheritsFrom(child, IC_64BIT_XS));
  48   case IC_OPSIZE:
  49     return(inheritsFrom(child, IC_64BIT_OPSIZE));
  50   case IC_XD:
  51     return(inheritsFrom(child, IC_64BIT_XD));
  52   case IC_XS:
  53     return(inheritsFrom(child, IC_64BIT_XS));
  54   case IC_64BIT_REXW:
  55     return(inheritsFrom(child, IC_64BIT_REXW_XS) ||
  56            inheritsFrom(child, IC_64BIT_REXW_XD) ||
  57            inheritsFrom(child, IC_64BIT_REXW_OPSIZE));
  58   case IC_64BIT_OPSIZE:
  59     return(inheritsFrom(child, IC_64BIT_REXW_OPSIZE));
  60   case IC_64BIT_XD:
  61     return(inheritsFrom(child, IC_64BIT_REXW_XD));
  62   case IC_64BIT_XS:
  63     return(inheritsFrom(child, IC_64BIT_REXW_XS));
  64   case IC_64BIT_REXW_XD:
  65     return false;
  66   case IC_64BIT_REXW_XS:
  67     return false;
  68   case IC_64BIT_REXW_OPSIZE:
  69     return false;
  70   default:
  71     return false;
  72   }
  73 }
  74
  75 /// outranks - Indicates whether, if an instruction has two different applicable
  76 ///   classes, which class should be preferred when performing decode.  This
  77 ///   imposes a total ordering (ties are resolved toward "lower")
  78 ///
  79 /// @param upper  - The class that may be preferable
  80 /// @param lower  - The class that may be less preferable
  81 /// @return       - True if upper is to be preferred, false otherwise.
  82 static inline bool outranks(InstructionContext upper,
  83                             InstructionContext lower) {
  84   assert(upper < IC_max);
  85   assert(lower < IC_max);
  86
  87 #define ENUM_ENTRY(n, r, d) r,
  88   static int ranks[IC_max] = {
  89     INSTRUCTION_CONTEXTS
  90   };
  91 #undef ENUM_ENTRY
  92
  93   return (ranks[upper] > ranks[lower]);
  94 }
  95
  96 /// stringForContext - Returns a string containing the name of a particular
  97 ///   InstructionContext, usually for diagnostic purposes.
  98 ///
  99 /// @param insnContext  - The instruction class to transform to a string.
 100 /// @return           - A statically-allocated string constant that contains the
 101 ///                     name of the instruction class.
 102 static inline const char* stringForContext(InstructionContext insnContext) {
 103   switch (insnContext) {
 104   default:
 105     llvm_unreachable("Unhandled instruction class");
 106 #define ENUM_ENTRY(n, r, d)   case n: return #n; break;
 107   INSTRUCTION_CONTEXTS
 108 #undef ENUM_ENTRY
 109   }
 110 }
 111
 112 /// stringForOperandType - Like stringForContext, but for OperandTypes.
 113 static inline const char* stringForOperandType(OperandType type) {
 114   switch (type) {
 115   default:
 116     llvm_unreachable("Unhandled type");
 117 #define ENUM_ENTRY(i, d) case i: return #i;
 118   TYPES
 119 #undef ENUM_ENTRY
 120   }
 121 }
 122
 123 /// stringForOperandEncoding - like stringForContext, but for
 124 ///   OperandEncodings.
 125 static inline const char* stringForOperandEncoding(OperandEncoding encoding) {
 126   switch (encoding) {
 127   default:
 128     llvm_unreachable("Unhandled encoding");
 129 #define ENUM_ENTRY(i, d) case i: return #i;
 130   ENCODINGS
 131 #undef ENUM_ENTRY
 132   }
 133 }
 134
 135 void DisassemblerTables::emitOneID(raw_ostream &o,
 136                                    uint32_t &i,
 137                                    InstrUID id,
 138                                    bool addComma) const {
 139   if (id)
 140     o.indent(i * 2) << format("0x%hx", id);
 141   else
 142     o.indent(i * 2) << 0;
 143
 144   if (addComma)
 145     o << ", ";
 146   else
 147     o << "  ";
 148
 149   o << "/* ";
 150   o << InstructionSpecifiers[id].name;
 151   o << "*/";
 152
 153   o << "\n";
 154 }
 155
 156 /// emitEmptyTable - Emits the modRMEmptyTable, which is used as a ID table by
 157 ///   all ModR/M decisions for instructions that are invalid for all possible
 158 ///   ModR/M byte values.
 159 ///
 160 /// @param o        - The output stream on which to emit the table.
 161 /// @param i        - The indentation level for that output stream.
 162 static void emitEmptyTable(raw_ostream &o, uint32_t &i)
 163 {
 164   o.indent(i * 2) << "InstrUID modRMEmptyTable[1] = { 0 };" << "\n";
 165   o << "\n";
 166 }
 167
 168 /// getDecisionType - Determines whether a ModRM decision with 255 entries can
 169 ///   be compacted by eliminating redundant information.
 170 ///
 171 /// @param decision - The decision to be compacted.
 172 /// @return         - The compactest available representation for the decision.
 173 static ModRMDecisionType getDecisionType(ModRMDecision &decision)
 174 {
 175   bool satisfiesOneEntry = true;
 176   bool satisfiesSplitRM = true;
 177
 178   uint16_t index;
 179
 180   for (index = 0; index < 256; ++index) {
 181     if (decision.instructionIDs[index] != decision.instructionIDs[0])
 182       satisfiesOneEntry = false;
 183
 184     if (((index & 0xc0) == 0xc0) &&
 185        (decision.instructionIDs[index] != decision.instructionIDs[0xc0]))
 186       satisfiesSplitRM = false;
 187
 188     if (((index & 0xc0) != 0xc0) &&
 189        (decision.instructionIDs[index] != decision.instructionIDs[0x00]))
 190       satisfiesSplitRM = false;
 191   }
 192
 193   if (satisfiesOneEntry)
 194     return MODRM_ONEENTRY;
 195
 196   if (satisfiesSplitRM)
 197     return MODRM_SPLITRM;
 198
 199   return MODRM_FULL;
 200 }
 201
 202 /// stringForDecisionType - Returns a statically-allocated string corresponding
 203 ///   to a particular decision type.
 204 ///
 205 /// @param dt - The decision type.
 206 /// @return   - A pointer to the statically-allocated string (e.g.,
 207 ///             "MODRM_ONEENTRY" for MODRM_ONEENTRY).
 208 static const char* stringForDecisionType(ModRMDecisionType dt)
 209 {
 210 #define ENUM_ENTRY(n) case n: return #n;
 211   switch (dt) {
 212     default:
 213       llvm_unreachable("Unknown decision type");
 214     MODRMTYPES
 215   };
 216 #undef ENUM_ENTRY
 217 }
 218
 219 /// stringForModifierType - Returns a statically-allocated string corresponding
 220 ///   to an opcode modifier type.
 221 ///
 222 /// @param mt - The modifier type.
 223 /// @return   - A pointer to the statically-allocated string (e.g.,
 224 ///             "MODIFIER_NONE" for MODIFIER_NONE).
 225 static const char* stringForModifierType(ModifierType mt)
 226 {
 227 #define ENUM_ENTRY(n) case n: return #n;
 228   switch(mt) {
 229     default:
 230       llvm_unreachable("Unknown modifier type");
 231     MODIFIER_TYPES
 232   };
 233 #undef ENUM_ENTRY
 234 }
 235
 236 DisassemblerTables::DisassemblerTables() {
 237   unsigned i;
 238
 239   for (i = 0; i < 4; i++) {
 240     Tables[i] = new ContextDecision;
 241     bzero(Tables[i], sizeof(ContextDecision));
 242   }
 243
 244   HasConflicts = false;
 245 }
 246
 247 DisassemblerTables::~DisassemblerTables() {
 248   unsigned i;
 249
 250   for (i = 0; i < 4; i++)
 251     delete Tables[i];
 252 }
 253
 254 void DisassemblerTables::emitModRMDecision(raw_ostream &o1,
 255                                            raw_ostream &o2,
 256                                            uint32_t &i1,
 257                                            uint32_t &i2,
 258                                            ModRMDecision &decision)
 259   const {
 260   static uint64_t sTableNumber = 0;
 261   uint64_t thisTableNumber = sTableNumber;
 262   ModRMDecisionType dt = getDecisionType(decision);
 263   uint16_t index;
 264
 265   if (dt == MODRM_ONEENTRY && decision.instructionIDs[0] == 0)
 266   {
 267     o2.indent(i2) << "{ /* ModRMDecision */" << "\n";
 268     i2++;
 269
 270     o2.indent(i2) << stringForDecisionType(dt) << "," << "\n";
 271     o2.indent(i2) << "modRMEmptyTable";
 272
 273     i2--;
 274     o2.indent(i2) << "}";
 275     return;
 276   }
 277
 278   o1.indent(i1) << "InstrUID modRMTable" << thisTableNumber;
 279
 280   switch (dt) {
 281     default:
 282       llvm_unreachable("Unknown decision type");
 283     case MODRM_ONEENTRY:
 284       o1 << "[1]";
 285       break;
 286     case MODRM_SPLITRM:
 287       o1 << "[2]";
 288       break;
 289     case MODRM_FULL:
 290       o1 << "[256]";
 291       break;
 292   }
 293
 294   o1 << " = {" << "\n";
 295   i1++;
 296
 297   switch (dt) {
 298     default:
 299       llvm_unreachable("Unknown decision type");
 300     case MODRM_ONEENTRY:
 301       emitOneID(o1, i1, decision.instructionIDs[0], false);
 302       break;
 303     case MODRM_SPLITRM:
 304       emitOneID(o1, i1, decision.instructionIDs[0x00], true); // mod = 0b00
 305       emitOneID(o1, i1, decision.instructionIDs[0xc0], false); // mod = 0b11
 306       break;
 307     case MODRM_FULL:
 308       for (index = 0; index < 256; ++index)
 309         emitOneID(o1, i1, decision.instructionIDs[index], index < 255);
 310       break;
 311   }
 312
 313   i1--;
 314   o1.indent(i1) << "};" << "\n";
 315   o1 << "\n";
 316
 317   o2.indent(i2) << "{ /* struct ModRMDecision */" << "\n";
 318   i2++;
 319
 320   o2.indent(i2) << stringForDecisionType(dt) << "," << "\n";
 321   o2.indent(i2) << "modRMTable" << sTableNumber << "\n";
 322
 323   i2--;
 324   o2.indent(i2) << "}";
 325
 326   ++sTableNumber;
 327 }
 328
 329 void DisassemblerTables::emitOpcodeDecision(
 330   raw_ostream &o1,
 331   raw_ostream &o2,
 332   uint32_t &i1,
 333   uint32_t &i2,
 334   OpcodeDecision &decision) const {
 335   uint16_t index;
 336
 337   o2.indent(i2) << "{ /* struct OpcodeDecision */" << "\n";
 338   i2++;
 339   o2.indent(i2) << "{" << "\n";
 340   i2++;
 341
 342   for (index = 0; index < 256; ++index) {
 343     o2.indent(i2);
 344
 345     o2 << "/* 0x" << format("%02hhx", index) << " */" << "\n";
 346
 347     emitModRMDecision(o1, o2, i1, i2, decision.modRMDecisions[index]);
 348
 349     if (index <  255)
 350       o2 << ",";
 351
 352     o2 << "\n";
 353   }
 354
 355   i2--;
 356   o2.indent(i2) << "}" << "\n";
 357   i2--;
 358   o2.indent(i2) << "}" << "\n";
 359 }
 360
 361 void DisassemblerTables::emitContextDecision(
 362   raw_ostream &o1,
 363   raw_ostream &o2,
 364   uint32_t &i1,
 365   uint32_t &i2,
 366   ContextDecision &decision,
 367   const char* name) const {
 368   o2.indent(i2) << "struct ContextDecision " << name << " = {" << "\n";
 369   i2++;
 370   o2.indent(i2) << "{ /* opcodeDecisions */" << "\n";
 371   i2++;
 372
 373   unsigned index;
 374
 375   for (index = 0; index < IC_max; ++index) {
 376     o2.indent(i2) << "/* ";
 377     o2 << stringForContext((InstructionContext)index);
 378     o2 << " */";
 379     o2 << "\n";
 380
 381     emitOpcodeDecision(o1, o2, i1, i2, decision.opcodeDecisions[index]);
 382
 383     if (index + 1 < IC_max)
 384       o2 << ", ";
 385   }
 386
 387   i2--;
 388   o2.indent(i2) << "}" << "\n";
 389   i2--;
 390   o2.indent(i2) << "};" << "\n";
 391 }
 392
 393 void DisassemblerTables::emitInstructionInfo(raw_ostream &o, uint32_t &i)
 394   const {
 395   o.indent(i * 2) << "struct InstructionSpecifier ";
 396   o << INSTRUCTIONS_STR << "[";
 397   o << InstructionSpecifiers.size();
 398   o << "] = {" << "\n";
 399
 400   i++;
 401
 402   uint16_t numInstructions = InstructionSpecifiers.size();
 403   uint16_t index, operandIndex;
 404
 405   for (index = 0; index < numInstructions; ++index) {
 406     o.indent(i * 2) << "{ /* " << index << " */" << "\n";
 407     i++;
 408
 409     o.indent(i * 2) <<
 410       stringForModifierType(InstructionSpecifiers[index].modifierType);
 411     o << "," << "\n";
 412
 413     o.indent(i * 2) << "0x";
 414     o << format("%02hhx", (uint16_t)InstructionSpecifiers[index].modifierBase);
 415     o << "," << "\n";
 416
 417     o.indent(i * 2) << "{" << "\n";
 418     i++;
 419
 420     for (operandIndex = 0; operandIndex < X86_MAX_OPERANDS; ++operandIndex) {
 421       o.indent(i * 2) << "{ ";
 422       o << stringForOperandEncoding(InstructionSpecifiers[index]
 423                                     .operands[operandIndex]
 424                                     .encoding);
 425       o << ", ";
 426       o << stringForOperandType(InstructionSpecifiers[index]
 427                                 .operands[operandIndex]
 428                                 .type);
 429       o << " }";
 430
 431       if (operandIndex < X86_MAX_OPERANDS - 1)
 432         o << ",";
 433
 434       o << "\n";
 435     }
 436
 437     i--;
 438     o.indent(i * 2) << "}," << "\n";
 439
 440     o.indent(i * 2) << "\"" << InstructionSpecifiers[index].name << "\"";
 441     o << "\n";
 442
 443     i--;
 444     o.indent(i * 2) << "}";
 445
 446     if (index + 1 < numInstructions)
 447       o << ",";
 448
 449     o << "\n";
 450   }
 451
 452   i--;
 453   o.indent(i * 2) << "};" << "\n";
 454 }
 455
 456 void DisassemblerTables::emitContextTable(raw_ostream &o, uint32_t &i) const {
 457   uint16_t index;
 458
 459   o.indent(i * 2) << "InstructionContext ";
 460   o << CONTEXTS_STR << "[256] = {" << "\n";
 461   i++;
 462
 463   for (index = 0; index < 256; ++index) {
 464     o.indent(i * 2);
 465
 466     if ((index & ATTR_64BIT) && (index & ATTR_REXW) && (index & ATTR_XS))
 467       o << "IC_64BIT_REXW_XS";
 468     else if ((index & ATTR_64BIT) && (index & ATTR_REXW) && (index & ATTR_XD))
 469       o << "IC_64BIT_REXW_XD";
 470     else if ((index & ATTR_64BIT) && (index & ATTR_REXW) &&
 471              (index & ATTR_OPSIZE))
 472       o << "IC_64BIT_REXW_OPSIZE";
 473     else if ((index & ATTR_64BIT) && (index & ATTR_XS))
 474       o << "IC_64BIT_XS";
 475     else if ((index & ATTR_64BIT) && (index & ATTR_XD))
 476       o << "IC_64BIT_XD";
 477     else if ((index & ATTR_64BIT) && (index & ATTR_OPSIZE))
 478       o << "IC_64BIT_OPSIZE";
 479     else if ((index & ATTR_64BIT) && (index & ATTR_REXW))
 480       o << "IC_64BIT_REXW";
 481     else if ((index & ATTR_64BIT))
 482       o << "IC_64BIT";
 483     else if (index & ATTR_XS)
 484       o << "IC_XS";
 485     else if (index & ATTR_XD)
 486       o << "IC_XD";
 487     else if (index & ATTR_OPSIZE)
 488       o << "IC_OPSIZE";
 489     else
 490       o << "IC";
 491
 492     if (index < 255)
 493       o << ",";
 494     else
 495       o << " ";
 496
 497     o << " /* " << index << " */";
 498
 499     o << "\n";
 500   }
 501
 502   i--;
 503   o.indent(i * 2) << "};" << "\n";
 504 }
 505
 506 void DisassemblerTables::emitContextDecisions(raw_ostream &o1,
 507                                             raw_ostream &o2,
 508                                             uint32_t &i1,
 509                                             uint32_t &i2)
 510   const {
 511   emitContextDecision(o1, o2, i1, i2, *Tables[0], ONEBYTE_STR);
 512   emitContextDecision(o1, o2, i1, i2, *Tables[1], TWOBYTE_STR);
 513   emitContextDecision(o1, o2, i1, i2, *Tables[2], THREEBYTE38_STR);
 514   emitContextDecision(o1, o2, i1, i2, *Tables[3], THREEBYTE3A_STR);
 515 }
 516
 517 void DisassemblerTables::emit(raw_ostream &o) const {
 518   uint32_t i1 = 0;
 519   uint32_t i2 = 0;
 520
 521   std::string s1;
 522   std::string s2;
 523
 524   raw_string_ostream o1(s1);
 525   raw_string_ostream o2(s2);
 526
 527   emitInstructionInfo(o, i2);
 528   o << "\n";
 529
 530   emitContextTable(o, i2);
 531   o << "\n";
 532
 533   emitEmptyTable(o1, i1);
 534   emitContextDecisions(o1, o2, i1, i2);
 535
 536   o << o1.str();
 537   o << "\n";
 538   o << o2.str();
 539   o << "\n";
 540   o << "\n";
 541 }
 542
 543 void DisassemblerTables::setTableFields(ModRMDecision     &decision,
 544                                         const ModRMFilter &filter,
 545                                         InstrUID          uid,
 546                                         uint8_t           opcode) {
 547   unsigned index;
 548
 549   for (index = 0; index < 256; ++index) {
 550     if (filter.accepts(index)) {
 551       if (decision.instructionIDs[index] == uid)
 552         continue;
 553
 554       if (decision.instructionIDs[index] != 0) {
 555         InstructionSpecifier &newInfo =
 556           InstructionSpecifiers[uid];
 557         InstructionSpecifier &previousInfo =
 558           InstructionSpecifiers[decision.instructionIDs[index]];
 559
 560         if(newInfo.filtered)
 561           continue; // filtered instructions get lowest priority
 562
 563         if(previousInfo.name == "NOOP")
 564           continue; // special case for XCHG32ar and NOOP
 565
 566         if (outranks(previousInfo.insnContext, newInfo.insnContext))
 567           continue;
 568
 569         if (previousInfo.insnContext == newInfo.insnContext &&
 570             !previousInfo.filtered) {
 571           errs() << "Error: Primary decode conflict: ";
 572           errs() << newInfo.name << " would overwrite " << previousInfo.name;
 573           errs() << "\n";
 574           errs() << "ModRM   " << index << "\n";
 575           errs() << "Opcode  " << (uint16_t)opcode << "\n";
 576           errs() << "Context " << stringForContext(newInfo.insnContext) << "\n";
 577           HasConflicts = true;
 578         }
 579       }
 580
 581       decision.instructionIDs[index] = uid;
 582     }
 583   }
 584 }
 585
 586 void DisassemblerTables::setTableFields(OpcodeType          type,
 587                                         InstructionContext  insnContext,
 588                                         uint8_t             opcode,
 589                                         const ModRMFilter   &filter,
 590                                         InstrUID            uid) {
 591   unsigned index;
 592
 593   ContextDecision &decision = *Tables[type];
 594
 595   for (index = 0; index < IC_max; ++index) {
 596     if (inheritsFrom((InstructionContext)index,
 597                      InstructionSpecifiers[uid].insnContext))
 598       setTableFields(decision.opcodeDecisions[index].modRMDecisions[opcode],
 599                      filter,
 600                      uid,
 601                      opcode);
 602   }
 603 }