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 using namespace llvm;
  25 using namespace X86Disassembler;
  26
  27 /// inheritsFrom - Indicates whether all instructions in one class also belong
  28 ///   to another class.
  29 ///
  30 /// @param child  - The class that may be the subset
  31 /// @param parent - The class that may be the superset
  32 /// @return       - True if child is a subset of parent, false otherwise.
  33 static inline bool inheritsFrom(InstructionContext child,
  34                                 InstructionContext parent) {
  35   if (child == parent)
  36     return true;
  37
  38   switch (parent) {
  39   case IC:
  40     return true;
  41   case IC_64BIT:
  42     return(inheritsFrom(child, IC_64BIT_REXW)   ||
  43            inheritsFrom(child, IC_64BIT_OPSIZE) ||
  44            inheritsFrom(child, IC_64BIT_XD)     ||
  45            inheritsFrom(child, IC_64BIT_XS));
  46   case IC_OPSIZE:
  47     return(inheritsFrom(child, IC_64BIT_OPSIZE));
  48   case IC_XD:
  49     return(inheritsFrom(child, IC_64BIT_XD));
  50   case IC_XS:
  51     return(inheritsFrom(child, IC_64BIT_XS));
  52   case IC_64BIT_REXW:
  53     return(inheritsFrom(child, IC_64BIT_REXW_XS) ||
  54            inheritsFrom(child, IC_64BIT_REXW_XD) ||
  55            inheritsFrom(child, IC_64BIT_REXW_OPSIZE));
  56   case IC_64BIT_OPSIZE:
  57     return(inheritsFrom(child, IC_64BIT_REXW_OPSIZE));
  58   case IC_64BIT_XD:
  59     return(inheritsFrom(child, IC_64BIT_REXW_XD));
  60   case IC_64BIT_XS:
  61     return(inheritsFrom(child, IC_64BIT_REXW_XS));
  62   case IC_64BIT_REXW_XD:
  63     return false;
  64   case IC_64BIT_REXW_XS:
  65     return false;
  66   case IC_64BIT_REXW_OPSIZE:
  67     return false;
  68   default:
  69     return false;
  70   }
  71 }
  72
  73 /// outranks - Indicates whether, if an instruction has two different applicable
  74 ///   classes, which class should be preferred when performing decode.  This
  75 ///   imposes a total ordering (ties are resolved toward "lower")
  76 ///
  77 /// @param upper  - The class that may be preferable
  78 /// @param lower  - The class that may be less preferable
  79 /// @return       - True if upper is to be preferred, false otherwise.
  80 static inline bool outranks(InstructionContext upper,
  81                             InstructionContext lower) {
  82   assert(upper < IC_max);
  83   assert(lower < IC_max);
  84
  85 #define ENUM_ENTRY(n, r, d) r,
  86   static int ranks[IC_max] = {
  87     INSTRUCTION_CONTEXTS
  88   };
  89 #undef ENUM_ENTRY
  90
  91   return (ranks[upper] > ranks[lower]);
  92 }
  93
  94 /// stringForContext - Returns a string containing the name of a particular
  95 ///   InstructionContext, usually for diagnostic purposes.
  96 ///
  97 /// @param insnContext  - The instruction class to transform to a string.
  98 /// @return           - A statically-allocated string constant that contains the
  99 ///                     name of the instruction class.
 100 static inline const char* stringForContext(InstructionContext insnContext) {
 101   switch (insnContext) {
 102   default:
 103     llvm_unreachable("Unhandled instruction class");
 104 #define ENUM_ENTRY(n, r, d)   case n: return #n; break;
 105   INSTRUCTION_CONTEXTS
 106 #undef ENUM_ENTRY
 107   }
 108
 109   return 0;
 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) << "static const 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     memset(Tables[i], 0, 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) << "static const 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) << "static const 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) << "static const struct InstructionSpecifier ";
 396   o << INSTRUCTIONS_STR "[" << InstructionSpecifiers.size() << "] = {\n";
 397
 398   i++;
 399
 400   uint16_t numInstructions = InstructionSpecifiers.size();
 401   uint16_t index, operandIndex;
 402
 403   for (index = 0; index < numInstructions; ++index) {
 404     o.indent(i * 2) << "{ /* " << index << " */" << "\n";
 405     i++;
 406
 407     o.indent(i * 2) <<
 408       stringForModifierType(InstructionSpecifiers[index].modifierType);
 409     o << "," << "\n";
 410
 411     o.indent(i * 2) << "0x";
 412     o << format("%02hhx", (uint16_t)InstructionSpecifiers[index].modifierBase);
 413     o << "," << "\n";
 414
 415     o.indent(i * 2) << "{" << "\n";
 416     i++;
 417
 418     for (operandIndex = 0; operandIndex < X86_MAX_OPERANDS; ++operandIndex) {
 419       o.indent(i * 2) << "{ ";
 420       o << stringForOperandEncoding(InstructionSpecifiers[index]
 421                                     .operands[operandIndex]
 422                                     .encoding);
 423       o << ", ";
 424       o << stringForOperandType(InstructionSpecifiers[index]
 425                                 .operands[operandIndex]
 426                                 .type);
 427       o << " }";
 428
 429       if (operandIndex < X86_MAX_OPERANDS - 1)
 430         o << ",";
 431
 432       o << "\n";
 433     }
 434
 435     i--;
 436     o.indent(i * 2) << "}," << "\n";
 437
 438     o.indent(i * 2) << "\"" << InstructionSpecifiers[index].name << "\"";
 439     o << "\n";
 440
 441     i--;
 442     o.indent(i * 2) << "}";
 443
 444     if (index + 1 < numInstructions)
 445       o << ",";
 446
 447     o << "\n";
 448   }
 449
 450   i--;
 451   o.indent(i * 2) << "};" << "\n";
 452 }
 453
 454 void DisassemblerTables::emitContextTable(raw_ostream &o, uint32_t &i) const {
 455   uint16_t index;
 456
 457   o.indent(i * 2) << "static const InstructionContext " CONTEXTS_STR
 458                      "[256] = {\n";
 459   i++;
 460
 461   for (index = 0; index < 256; ++index) {
 462     o.indent(i * 2);
 463
 464     if ((index & ATTR_64BIT) && (index & ATTR_REXW) && (index & ATTR_XS))
 465       o << "IC_64BIT_REXW_XS";
 466     else if ((index & ATTR_64BIT) && (index & ATTR_REXW) && (index & ATTR_XD))
 467       o << "IC_64BIT_REXW_XD";
 468     else if ((index & ATTR_64BIT) && (index & ATTR_REXW) &&
 469              (index & ATTR_OPSIZE))
 470       o << "IC_64BIT_REXW_OPSIZE";
 471     else if ((index & ATTR_64BIT) && (index & ATTR_XS))
 472       o << "IC_64BIT_XS";
 473     else if ((index & ATTR_64BIT) && (index & ATTR_XD))
 474       o << "IC_64BIT_XD";
 475     else if ((index & ATTR_64BIT) && (index & ATTR_OPSIZE))
 476       o << "IC_64BIT_OPSIZE";
 477     else if ((index & ATTR_64BIT) && (index & ATTR_REXW))
 478       o << "IC_64BIT_REXW";
 479     else if ((index & ATTR_64BIT))
 480       o << "IC_64BIT";
 481     else if (index & ATTR_XS)
 482       o << "IC_XS";
 483     else if (index & ATTR_XD)
 484       o << "IC_XD";
 485     else if (index & ATTR_OPSIZE)
 486       o << "IC_OPSIZE";
 487     else
 488       o << "IC";
 489
 490     if (index < 255)
 491       o << ",";
 492     else
 493       o << " ";
 494
 495     o << " /* " << index << " */";
 496
 497     o << "\n";
 498   }
 499
 500   i--;
 501   o.indent(i * 2) << "};" << "\n";
 502 }
 503
 504 void DisassemblerTables::emitContextDecisions(raw_ostream &o1,
 505                                             raw_ostream &o2,
 506                                             uint32_t &i1,
 507                                             uint32_t &i2)
 508   const {
 509   emitContextDecision(o1, o2, i1, i2, *Tables[0], ONEBYTE_STR);
 510   emitContextDecision(o1, o2, i1, i2, *Tables[1], TWOBYTE_STR);
 511   emitContextDecision(o1, o2, i1, i2, *Tables[2], THREEBYTE38_STR);
 512   emitContextDecision(o1, o2, i1, i2, *Tables[3], THREEBYTE3A_STR);
 513 }
 514
 515 void DisassemblerTables::emit(raw_ostream &o) const {
 516   uint32_t i1 = 0;
 517   uint32_t i2 = 0;
 518
 519   std::string s1;
 520   std::string s2;
 521
 522   raw_string_ostream o1(s1);
 523   raw_string_ostream o2(s2);
 524
 525   emitInstructionInfo(o, i2);
 526   o << "\n";
 527
 528   emitContextTable(o, i2);
 529   o << "\n";
 530
 531   emitEmptyTable(o1, i1);
 532   emitContextDecisions(o1, o2, i1, i2);
 533
 534   o << o1.str();
 535   o << "\n";
 536   o << o2.str();
 537   o << "\n";
 538   o << "\n";
 539 }
 540
 541 void DisassemblerTables::setTableFields(ModRMDecision     &decision,
 542                                         const ModRMFilter &filter,
 543                                         InstrUID          uid,
 544                                         uint8_t           opcode) {
 545   unsigned index;
 546
 547   for (index = 0; index < 256; ++index) {
 548     if (filter.accepts(index)) {
 549       if (decision.instructionIDs[index] == uid)
 550         continue;
 551
 552       if (decision.instructionIDs[index] != 0) {
 553         InstructionSpecifier &newInfo =
 554           InstructionSpecifiers[uid];
 555         InstructionSpecifier &previousInfo =
 556           InstructionSpecifiers[decision.instructionIDs[index]];
 557
 558         if(newInfo.filtered)
 559           continue; // filtered instructions get lowest priority
 560
 561         if(previousInfo.name == "NOOP")
 562           continue; // special case for XCHG32ar and NOOP
 563
 564         if (outranks(previousInfo.insnContext, newInfo.insnContext))
 565           continue;
 566
 567         if (previousInfo.insnContext == newInfo.insnContext &&
 568             !previousInfo.filtered) {
 569           errs() << "Error: Primary decode conflict: ";
 570           errs() << newInfo.name << " would overwrite " << previousInfo.name;
 571           errs() << "\n";
 572           errs() << "ModRM   " << index << "\n";
 573           errs() << "Opcode  " << (uint16_t)opcode << "\n";
 574           errs() << "Context " << stringForContext(newInfo.insnContext) << "\n";
 575           HasConflicts = true;
 576         }
 577       }
 578
 579       decision.instructionIDs[index] = uid;
 580     }
 581   }
 582 }
 583
 584 void DisassemblerTables::setTableFields(OpcodeType          type,
 585                                         InstructionContext  insnContext,
 586                                         uint8_t             opcode,
 587                                         const ModRMFilter   &filter,
 588                                         InstrUID            uid) {
 589   unsigned index;
 590
 591   ContextDecision &decision = *Tables[type];
 592
 593   for (index = 0; index < IC_max; ++index) {
 594     if (inheritsFrom((InstructionContext)index,
 595                      InstructionSpecifiers[uid].insnContext))
 596       setTableFields(decision.opcodeDecisions[index].modRMDecisions[opcode],
 597                      filter,
 598                      uid,
 599                      opcode);
 600   }
 601 }