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