X86DisassemblerTables.cpp revision 218893 
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
24using namespace llvm;
25using 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.
33static 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.
80static 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.
100static 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.
113static 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.
125static 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
135void 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.
162static 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.
173static 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).
208static 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).
225static 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
236DisassemblerTables::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
247DisassemblerTables::~DisassemblerTables() {
248  unsigned i;
249
250  for (i = 0; i < 4; i++)
251    delete Tables[i];
252}
253
254void 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
329void 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
361void 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
393void 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
454void 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
504void 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
515void 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
541void 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
584void 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}
602