X86DisassemblerTables.cpp revision 208954 
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 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 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) << "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) << "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
456void 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
506void 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
517void 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
543void 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
586void 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}
604