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