Regular instructions golden file test.

src/trusted/validator_ragel/compress_regular_instructions.py

+# Copyright (c) 2013 The Native Client Authors. All rights reserved.
+# Use of this source code is governed by a BSD-style license that can be
+# found in the LICENSE file.
+
+"""
+Traverse the validator's DFA, collect all "normal" instruction and then
+compress output.  Note: "anybyte fields" (immediates and displacements)
+are always filled with zeros.  Otherwise processing of sextillions (sic!)
+of possibilities will take too long.
+
+The following compression rules are present:

[halyavin, 2013/11/06 12:11:51]

Rules are applied only when all variants are accepted by validator. The
following ...

[khim, 2013/11/06 21:28:28]

Done.

+
+1. Compress ModR/M (+SIB & displacement).
+  Instruction: 00 00  add %al,(%rax)
+  ...
+  Instruction: 00 ff  add %bh,%bh
+    becomes
+  Instruction: 00 XX  add [%al..%bh],[%al..%bh or memory]
+
+  Only applies if all possibilities are accepted by validator.
+
+1a. Compress ModR/M (+SIB & displacement) memory-only.
+  Instruction: f0 01 00  lock add %eax,(%eax)
+  ...
+  Instruction: f0 01 bf 00 00 00 00  lock add %edi,0x0(%edi)
+    becomes
+  Instruction: f0 01 XX  lock add [%eax..edi],[memory]
+
+  Only applies if all possible memory accesses are accepted by validator.
+
+1b. Compress ModR/M (+SIB & displacement) register only

[halyavin, 2013/11/06 12:11:51]

There is no SIB & displacement for registers.

[khim, 2013/11/06 21:28:28]

Done.

+  Instruction: 66 0f 50 c0  movmskpd %xmm0,%eax
+  ...
+  Instruction: 66 0f 50 ff  movmskpd %xmm7,%edi
+    becomes
+  Instruction: 66 0f 50 XX  movmskpd [%xmm0..%xmm7],[%eax..edi]
+
+  Only applies if all possible register accesses are accepted by validator.
+
+2. Compress ModR/M (+SIB & displacement) with opcode extension.
+  Instruction: 0f 90 00  seto (%eax)
+  ...
+  Instruction: 0f 90 c7  seto %bh
+    becomes
+  Instruction: 0f 90 XX/0  seto [%al..%bh or memory]
+
+  Only applies if all possibilities are accepted by validator.
+
+2a. Compress ModR/M (+SIB & displacement) memory-only with opcode extension.
+  Instruction: f0 ff 00  lock incl (%eax)
+  ...
+  Instruction: f0 ff 84 ff 00 00 00 00  lock incl 0x0(%edi,%edi,8)
+    becomes
+  Instruction: f0 ff XX/1  lock decl [memory]
+
+  Only applies if all possibile memory accesses are accepted by validator.
+
+2b. Compress ModR/M (+SIB & displacement) register-only with opcode extension.

[halyavin, 2013/11/06 12:11:51]

There is no SIB & displacement for registers.

[khim, 2013/11/06 21:28:28]

Done.

+  Instruction: 0f 71 d0 00  psrlw $0x0,%mm0
+  ...
+  Instruction: 0f 71 d7 00  psrlw $0x0,%mm7
+    becomes
+  Instruction: 66 0f 71 XX/2 00  psrlw $0x0,[%mm0..%mm7]
+
+  Only applies if all possible register accesses are accepted by validator.
+
+3. Compress register-in-opcode.
+  Instruction: d9 c0  fld %st(0)
+  ...
+  Instruction: d9 c7  fld %st(7)
+    becomes
+  Instruction: Instruction: d9 c[0..7]  fld [%st(0)..%st(7)]
+
+  Only applies if all possible register accesses are accepted by validator.
+
+4. Special compressor for "set" instruction.
+  Instruction: 0f 90 XX/0  seto [%al..%bh or memory]
+  ...
+  Instruction: 0f 90 XX/7  seto [%al..%bh or memory]
+    becomes
+  Instruction: 0f 90 XX  seto [%al..%bh or memory]
+"""
+
+import itertools
+import multiprocessing
+import optparse
+import os
+import re
+import subprocess
+import sys
+import tempfile
+import traceback
+
+import dfa_parser
+import dfa_traversal
+import validator
+
+
+# Register names in 'natual' order (as defined by IA32/x86-64 ABI)
+#
+# X86-64 ABI splits all registers in groups of 8 because it uses 3-bit field
+# in opcode, ModR/M, and/or SIB bytes to encode them.
+#
+# In most cases there are 16 registers of a given kind and two such groups,
+# but there are couple of exceptions:
+#   1. There are 20 8-bit registers and three groups (two of them overlap)
+#   2. There are eight X87 and MMX registers thus two groups are identical
+#
+# We use typical register from a group to name the whole group.  Most groups
+# use first register, but 'spl' group uses fifth register because it's first
+# four registers are the same as 'al' group.
+REGISTERS = {
+     'al': [  'al',  'cl',  'dl',  'bl',  'ah',  'ch',  'dh',  'bh' ],
+    'spl': [  'al',  'cl',  'dl',  'bl', 'spl', 'bpl', 'sil', 'dil' ],
+     'ax': [  'ax',  'cx',  'dx',  'bx',  'sp',  'bp',  'si',  'di' ],
+    'eax': [ 'eax', 'ecx', 'edx', 'ebx', 'esp', 'ebp', 'esi', 'edi' ],
+    'rax': [ 'rax', 'rcx', 'rdx', 'rbx', 'rsp', 'rbp', 'rsi', 'rdi' ],
+    'r8b': [ 'r{}b'.format(N) for N in range(8,16)                  ],
+    'r8w': [ 'r{}w'.format(N) for N in range(8,16)                  ],
+    'r8d': [ 'r{}d'.format(N) for N in range(8,16)                  ],
+     'r8': [ 'r{}'.format(N) for N in range(8,16)                   ],
+    'mm0': [ 'mm{}'.format(N) for N in range(8)                     ],
+    'mm8': [ 'mm{}'.format(N) for N in range(8)                     ],

[halyavin, 2013/11/06 12:11:51]

'mm_alt'

[khim, 2013/11/06 21:28:28]

Done.

+  'st(0)': [ 'st({})'.format(N) for N in range(8)                   ],
+  'st(8)': [ 'st({})'.format(N) for N in range(8)                   ],

[halyavin, 2013/11/06 12:11:51]

'st_alt(0)'

[khim, 2013/11/06 21:28:28]

Removed instead. If we no longer have predictable names for all the second
groups then st(8) is just not needed.

+   'xmm0': [ 'xmm{}'.format(N) for N in range(8)                    ],
+   'xmm8': [ 'xmm{}'.format(N) for N in range(8,16)                 ],
+   'ymm0': [ 'ymm{}'.format(N) for N in range(8)                    ],
+   'ymm8': [ 'ymm{}'.format(N) for N in range(8,16)                 ]
+}
+
+
+NOP = 0x90
+
+
+def PadToBundleSize(bytes):
+  assert len(bytes) <= validator.BUNDLE_SIZE
+  return bytes + [NOP] * (validator.BUNDLE_SIZE - len(bytes))
+
+
+# In x86-64 mode we have so-called 'restricted register' which is used to
+# tie two groups together.  Some instruction require particular value to

[halyavin, 2013/11/06 12:11:51]

Some instructions

[khim, 2013/11/06 21:28:28]

Done.

+# be stored in this variable, while some accept any non-special restricted
+# register (%ebp and %esp are special because they can only be accepted by
+# a few 'special' instructions).
+#
+# You can find more details in the "NaCl SFI model on x86-64 systems" manual.
+#
+# We try to feed all possible 'restricted register' into validator and then

[halyavin, 2013/11/06 12:11:51]

restricted registers

[khim, 2013/11/06 21:28:28]

Done.

+# classify the instruction using this map.  If set of acceptable 'restricted
+# registers' is not here, then it's an error in validator.
+ACCEPTABLE_X86_64_INPUTS = {
+  0x00001: 'input_rr=%eax',
+  0x00002: 'input_rr=%ecx',
+  0x00004: 'input_rr=%edx',
+  0x00008: 'input_rr=%ebx',
+  0x00010: 'input_rr=%esp',
+  0x00020: 'input_rr=%ebp',
+  0x00040: 'input_rr=%esi',
+  0x00080: 'input_rr=%edi',
+  0x00100: 'input_rr=%r8d',
+  0x00200: 'input_rr=%r9d',
+  0x00400: 'input_rr=%r10d',
+  0x00800: 'input_rr=%r11d',
+  0x01000: 'input_rr=%r12d',
+  0x02000: 'input_rr=%r13d',
+  0x04000: 'input_rr=%r14d',
+  0x08000: 'input_rr=%r15d',
+  0x1ffcf: 'input_rr=any_nonspecial'
+}
+
+# Any instruction must produce either None or one of fifteen registers as an
+# output 'restricted register' value.  'r15d' is NOT acceptable as an output.
+ACCEPTABLE_X86_64_OUTPUT_REGISTERS = tuple(
+    '%' + reg for reg in (REGISTERS['eax'] + REGISTERS['r8d'])[0:-1])
+
+
+def ValidateInstruction(instruction, validator_inst):
+  bundle = ''.join(map(chr, PadToBundleSize(instruction)))
+  if options.bitness == 32:
+    result = validator_inst.ValidateChunk(bundle, bitness=32)
+    return result
+  else:
+    valid_inputs = 0
+    known_final_rr = None
+    output_rr = None
+    bit_position = 1
+    # Note that iteration order is aligned with CCEPTABLE_X86_64_INPUTS array

[halyavin, 2013/11/06 14:23:24]

ACCEPTABLE_X86_64_INPUTS

[khim, 2013/11/06 21:28:28]

Done.

+    # above.
+    for initial_rr in validator.ALL_REGISTERS + [None]:
+      valid, final_rr = validator_inst.ValidateAndGetFinalRestrictedRegister(
+          bundle, len(instruction), initial_rr)
+      if valid:
+        # final_rr should not depent on input_rr

[halyavin, 2013/11/06 14:23:24]

depend

[khim, 2013/11/06 21:28:28]

Done.

+        assert valid_inputs == 0 or known_final_rr == final_rr
+        valid_inputs |= bit_position
+        known_final_rr = final_rr
+      bit_position += bit_position
+    # If nothing is accepted then instruction is not valid.  Easy and simple.
+    if valid_inputs == 0: return False
+    # If returned value in unacceptable we'll get IndexError here and this
+    # test will fail
+    if known_final_rr is not None:
+      output_rr = ACCEPTABLE_X86_64_OUTPUT_REGISTERS[known_final_rr]
+    # If collected valid_inputs are unacceptable we'll get KeyError here and
+    # this test will fail
+    return [ACCEPTABLE_X86_64_INPUTS[valid_inputs],
+            'output_rr={}'.format(output_rr)]
+
+
+class WorkerState(object):
+  def __init__(self, prefix, validator):
+    self.total_instructions = 0
+    self.num_valid = 0
+    self.validator = validator
+    self.output = set()
+
+  def ReceiveInstruction(self, bytes):
+    self.total_instructions += 1
+    result = ValidateInstruction(bytes, self.validator)
+    if result is not False:
+      self.num_valid += 1
+      dis = self.validator.DisassembleChunk(
+          ''.join(map(chr, bytes)),
+          bitness=options.bitness)
+      for line_nr in xrange(len(dis)):
+        dis[line_nr] = str(dis[line_nr])
+        assert dis[line_nr][0:17] == 'Instruction(0x' + str(line_nr) + ': '
+        assert dis[line_nr][-1:] == ')'
+        dis[line_nr] = dis[line_nr][17:-1]
+      # If %rip is involved then comment will be different depending on the
+      # instruction length.  Eliminate it.
+      if '(%rip)' in dis[0]:
+        dis[0] = re.sub(' # 0x[ 0-9a-fA-F]*', '', dis[0])

[halyavin, 2013/11/06 14:23:24]

0x[ ]*[0-9a-fA-F]*

[khim, 2013/11/06 21:28:28]

Done.

+      # Absolute addressing is allowed in 32-bit mode and completely forbidden

[halyavin, 2013/11/06 14:23:24]

Zero displacements are represented as 0x0 for all instructions except jumps
where they disassembled as non-zero due to %eip/%rip-relative addressing. We
replace this displacement with %eip/%rip to increase compression.

[khim, 2013/11/06 21:28:28]

Done.

+      # in 64-bit mode, but all instructions except jumps use truly absolute
+      # addressing with base address == 0x0, jump instructions use offset from
+      # the instruction pointer (%eip or %rip).  And position of the instruction
+      # pointer depends on the instruction length.  Eliminate it.
+      if ' 0x' in dis[0] and ' 0x0' not in dis[0]:
+        for bytes in xrange(1, 16):
+          dis[0] = re.sub(
+              '(' + '[0-9a-fA-F][0-9a-fA-F] ' * bytes + ' .* )'
+              '0x' + str(bytes) + '(.*)',
+              '\\1%eip\\2' if options.bitness == 32 else '\\1%rip\\2',
+              dis[0]);
+      dis[0] = 'Instruction: ' + dis[0]
+      if result is not True:
+        dis += result
+      self.output.add('; '.join(dis))
+
+
+# Compressor has three slots: regex (which picks apart given instruction),
+# subst (which is used to denote compressed version) and replacements (which
+# are used to generate set of instructions from a given code).
+#
+# Example compressor:
+#   regex = '.*?[0-9a-fA-F]([0-7])  \\w* (%e(?:[abcd]x|[sb]p|[sd]i)).*()'
+#   subst = ('[0-7]', '[%eax..%edi]', ' # register in opcode')
+#   replacements = ((0, '%eax'), (1, '%ecx'), (2, '%edx'), (3, '%ebx')
+#                   (4, '%esp'), (5, '%ebp'), (6, '%esi'), (7, '%edi'))
+#
+# When faced with instriuction '40  inc %eax' it will capture the following
+# pieces of said instruction: '4[0]  inc [%eax]'.
+#
+# Then it will produce the following eight instructions:
+#   '40  inc %eax'
+#   '41  inc %ecx'
+#   '42  inc %edx'
+#   '43  inc %ebx'
+#   '44  inc %esp'
+#   '45  inc %ebp'
+#   '46  inc %esi'
+#   '47  inc %edi'
+#
+# If all these instructions can be found in a set of instructions then
+# compressor will remove them from said set and will insert one replacement
+# "compressed instruction" '4[0-7]  inc [%eax..%edi] # register in opcode'.
+#
+# Note that last group is only used in the replacement.  It's used to grab marks
+# added by previous compressors and to replace them with a new mark.
+class Compressor(object):
+  __slots__ = [
+    'regex',
+    'subst',
+    'replacements'
+  ]
+
+  def __init__(self, regex, subst, replacements=None):
+    self.regex = regex
+    self.subst = subst
+    self.replacements = [] if replacements is None else replacements
+
+
+def Compressed(instructions, show_progress=None):

[halyavin, 2013/11/06 14:23:24]

We better to create method that collects trace.

[khim, 2013/11/06 21:28:28]

Done.

+  split = None

[halyavin, 2013/11/06 14:23:24]

Use empty string for initial value.

[khim, 2013/11/06 21:28:28]

Not sure what's wrong with None (we don't yet HAVE a split, right?), but
whatever.

Done.

+  rule = True
+  if not show_progress:
+    trace = []
+  while rule is not False:
+    def CompressOneInstruction(instructions , split):
+      sorted_instructions = (sorted(i for i in instructions if i > split) +
+                             sorted(i for i in instructions if i < split))
+      for instruction in sorted_instructions:
+        for compressor_nr, compressor in enumerate(compressors):
+          match = compressor.regex.match(instruction)
+          if match:
+            pos = 0
+            format_str = ''
+            for group in range(1, len(match.groups())):
+              format_str += instruction[pos:match.start(group)] + '{}'
+              pos = match.end(group)
+            format_str += instruction[pos:match.start(len(match.groups()))]

[halyavin, 2013/11/06 14:23:24]

Extract these 5 lines to a function.

[khim, 2013/11/06 21:28:28]

Done.

+            subset = set()
+            for replacement in compressor.replacements:
+              replacement_str = format_str.format(*replacement)
+              if not replacement_str in instructions: break
+              subset.add(replacement_str)
+            else:
+              instructions -= subset
+              instructions.add((format_str + '{}').format(*compressor.subst))
+              return (instructions, compressor_nr, instruction)
+      return (instructions, False, False)
+    instructions, rule, split = CompressOneInstruction(instructions, split)
+    if rule is not False:
+      if show_progress:
+        show_progress(rule, split)
+      else:
+        trace.append((rule, split))
+  if show_progress:
+    return instructions
+  else:
+    return instructions, trace
+
+
+def Worker((prefix, state_index)):
+  worker_state = WorkerState(prefix, worker_validator)
+
+  try:
+    dfa_traversal.TraverseTree(
+        dfa.states[state_index],
+        final_callback=worker_state.ReceiveInstruction,
+        prefix=prefix,
+        anyfield=0)
+    if (prefix[0] != 0x0f or prefix[1] != 0x0f): # Skip 3DNow! instructions
+      output, trace = Compressed(set(worker_state.output))
+    else:
+      output = worker_state.output
+      trace = []
+  except Exception as e:
+    traceback.print_exc() # because multiprocessing imap swallows traceback
+    raise
+
+  return (
+      prefix,
+      worker_state.total_instructions,
+      worker_state.num_valid,
+      output,
+      trace)
+
+
+def ParseOptions():
+  parser = optparse.OptionParser(usage='%prog [options] xmlfile')
+
+  parser.add_option('--bitness',
+                    type=int,
+                    help='The subarchitecture: 32 or 64')
+  parser.add_option('--validator_dll',
+                    help='Path to librdfa_validator_dll')
+  parser.add_option('--decoder_dll',
+                    help='Path to librdfa_decoder_dll')
+
+  options, args = parser.parse_args()
+
+  if options.bitness not in [32, 64]:
+    parser.error('specify --bitness 32 or --bitness 64')
+
+  if len(args) != 1:
+    parser.error('specify one xml file')
+
+  (xml_file, ) = args
+
+  return options, xml_file
+
+
+# Version suitable for use in regular expressions
+REGISTERS_RE = REGISTERS.copy()
+REGISTERS_RE['st(0)'] = [ 'st\\({}\\)'.format(N) for N in range(8) ]
+REGISTERS_RE['st(8)'] = REGISTERS_RE['st(0)']

[halyavin, 2013/11/06 14:23:24]

st(8)->st_alt

[khim, 2013/11/06 21:28:28]

Removed

+REGISTERS_RE['st\\(0\\)'] = REGISTERS_RE['st(0)']
+REGISTERS_RE['st\\(8\\)'] = REGISTERS_RE['st(0)']
+
+# Index names in 'natual' order (as defined by IA32/x86-64 ABI)
+INDEXES = {
+  'eax': [  'eax',  'ecx',  'edx',  'ebx',  'eiz',  'ebp',  'esi',  'edi' ],
+  'rax': [  'rax',  'rcx',  'rdx',  'rbx',  'riz',  'rbp',  'rsi',  'rdi' ],
+   'r8': [   'r8',   'r9',  'r10',  'r11',  'r12',  'r13',  'r14',  'r15' ]
+}
+# Register which can not be used as base in 64-bit mode in all incarnations
+X86_64_BASE_REGISTERS = set([
+  '%spl', '%bpl', '%r15b',  '%sp',  '%bp', '%r15w',
+  '%esp', '%ebp', '%r15d', '%rsp', '%rbp', '%r15',
+  '%rip'
+])
+
+def AddModRM_Compressor(regex, subst, subst_register, subst_memory,
+                        reg=None, rm=None, rm_to_reg=False, start_byte=0,
+                        index_r8=False, input_rr=True, output_rr=False):
+  """Adds three compressors to the list of compressors:
+    main_compressors (register <-> register or memory instructions)
+    register_compressors (register <-> register instructions)
+    memory_compressors (regsiter <-> memory instructions)
+
+  Args:
+    regex: regular expressions for the compressor
+    subst: replacement for register <-> register or memory instructions
+    subst_register: replacement for register <-> register instructions
+    subst_memory: replacement for regsiter <-> memory instructions
+    reg: reg operand kind (see REGISTERS array) or None
+    rm: rm operand kind (see REGISTERS array)
+    rm_to_reg: three-state selector
+      True - instruction uses rm as source, reg as destination
+      False - instruction uses reg as source, rm as destination
+      None - instruction either uses both symmetrically (e.g. test or xchg)
+    start_byte: first valid byte ModR/M byte (used when reg is None)
+    input_rr: True if instruction accesses memory
+    output_rr: three-state selector
+      True - instruction can be used to produce "restricted register"
+      False - instruction does not affect it's operands (e.g. test)
+      None - instruction can damage output but can not be used to restrict it
+  Internal:
+    index_r8: must be called in False position (used to create two compressors
+              in 64-bit mode with index == %rax..%rdi or index == %r8..%r14)
+  Returns:
+    None
+  """
+
+  if options.bitness == 32:
+    base = 'eax'
+    index = 'eax'
+    expanded_regex = re.sub('{RR_NOTES}', '', regex)
+  else:
+    base = 'r8' if rm[0:2] == 'r8' or rm[-1] == '8' else 'rax'
+    index = 'r8' if index_r8 else 'rax'
+    input = 'r8d' if index_r8 else 'eax'
+    if output_rr:
+      output_regs = reg if rm_to_reg else rm
+      assert output_regs in ('eax', 'r8d')
+      expanded_regex = re.sub('{RR_NOTES}', '; input_rr=((?:%{'+ input +
+        '}|any_nonspecial)); output_rr=(%{' +  output_regs + '}|None)', regex)
+    else:
+      expanded_regex = re.sub('{RR_NOTES}', '; input_rr=((?:%{' + input +
+        '}|any_nonspecial)); output_rr=(None)', regex)
+  if 'RM_BYTE' in regex:
+    address_regex = '(?:0x0|(?:0x0)?\\((?:%{' + base + '})?\\))'
+  else:
+    address_regex = (
+      '(?:0x0|(?:0x0)?\\((?:%{' + base + '})?(?:,(?:%{' + index + '}))?'
+      '(?:,(?:1|2|4|8))?\\))')
+
+  # We need to process either modrm or reg
+  assert rm is not None or reg is not None
+  # If both modrm and reg are given then ModR/M
+  assert reg is None or start_byte == 0
+  # Replace RM_BYTE placeholders.
+  # Handle only cases without displacement.
+  expanded_regex = re.sub('{RM_BYTE}', '[0-9a-fA-F][0-9a-fA-F]', expanded_regex)
+  expanded_regex = re.sub('{RM_BYTE/0}', '[048cC][0-7]', expanded_regex)
+  expanded_regex = re.sub('{RM_BYTE/1}', '[048cC][89a-fA-F]', expanded_regex)
+  expanded_regex = re.sub('{RM_BYTE/2}', '[159dD][0-7]', expanded_regex)
+  expanded_regex = re.sub('{RM_BYTE/3}', '[159dD][89a-fA-F]', expanded_regex)
+  expanded_regex = re.sub('{RM_BYTE/4}', '[26aAeE][0-7]', expanded_regex)
+  expanded_regex = re.sub('{RM_BYTE/5}', '[26aAeE][89a-fA-F]', expanded_regex)
+  expanded_regex = re.sub('{RM_BYTE/6}', '[37bBfF][0-7]', expanded_regex)
+  expanded_regex = re.sub('{RM_BYTE/7}', '[37bBfF][89a-fA-F]', expanded_regex)
+  register_regex = expanded_regex
+  # Replace RM_SIB_BYTES placeholders.
+  # Handle only cases without displacement.
+  expanded_regex = re.sub(
+       '{RM_SIB_BYTES}', '[0-b][4c] [0-9a-fA-F][0-9a-fA-F]', expanded_regex)
+  expanded_regex = re.sub(
+       '{RM_SIB_BYTES/0}', '[048]4 [0-9a-fA-F][0-9a-fA-F]', expanded_regex)
+  expanded_regex = re.sub(
+       '{RM_SIB_BYTES/1}', '[048][cC] [0-9a-fA-F][0-9a-fA-F]', expanded_regex)
+  expanded_regex = re.sub(
+       '{RM_SIB_BYTES/2}', '[159]4 [0-9a-fA-F][0-9a-fA-F]', expanded_regex)
+  expanded_regex = re.sub(
+       '{RM_SIB_BYTES/3}', '[159][cC] [0-9a-fA-F][0-9a-fA-F]', expanded_regex)
+  expanded_regex = re.sub(
+       '{RM_SIB_BYTES/4}', '[26aA]4 [0-9a-fA-F][0-9a-fA-F]', expanded_regex)
+  expanded_regex = re.sub(
+       '{RM_SIB_BYTES/5}', '[26aA][cC] [0-9a-fA-F][0-9a-fA-F]', expanded_regex)
+  expanded_regex = re.sub(
+       '{RM_SIB_BYTES/6}', '[37bB]4 [0-9a-fA-F][0-9a-fA-F]', expanded_regex)
+  expanded_regex = re.sub(
+      '{RM_SIB_BYTES/7}', '[37bB][cC] [0-9a-fA-F][0-9a-fA-F]', expanded_regex)
+  register_regex = re.sub(
+      '{RM_SIB_BYTES}', '[c-fC-F][0-9a-fA-F]', register_regex)
+  register_regex = re.sub('{RM_SIB_BYTES/0}', '[cC][0-7]', register_regex)
+  register_regex = re.sub('{RM_SIB_BYTES/1}', '[cC][8-9a-fA-F]', register_regex)
+  register_regex = re.sub('{RM_SIB_BYTES/2}', '[dD][0-7]', register_regex)
+  register_regex = re.sub('{RM_SIB_BYTES/3}', '[dD][8-9a-fA-F]', register_regex)
+  register_regex = re.sub('{RM_SIB_BYTES/4}', '[eE][0-7]', register_regex)
+  register_regex = re.sub('{RM_SIB_BYTES/5}', '[eE][8-9a-fA-F]', register_regex)
+  register_regex = re.sub('{RM_SIB_BYTES/6}', '[fF][0-7]', register_regex)
+  register_regex = re.sub('{RM_SIB_BYTES/7}', '[fF][8-9a-fA-F]', register_regex)
+  # Replace register placeholders
+  for register, value in REGISTERS_RE.iteritems():
+    expanded_regex = re.sub('{%' + register + '}',
+        '(?:%' + '|%'.join(value) + '|' + address_regex +')', expanded_regex)
+    register_regex = re.sub('{%' + register + '}',
+        '(?:%' + '|%'.join(value) +')', register_regex)
+  for register, value in REGISTERS_RE.iteritems():
+    expanded_regex = re.sub('{' + register + '}',
+        '(?:' + '|'.join(value) + ')', expanded_regex)
+    register_regex = re.sub('{' + register + '}',
+        '(?:' + '|'.join(value) + ')', register_regex)
+  expanded_regex = re.compile(expanded_regex)
+  register_regex = re.compile(register_regex)
+  # Add index_rr and output_rr fields if we are dealing with 64-bit case
+  if options.bitness == 32:
+    subst_fixed = subst
+    subst_register_fixed = subst_register
+    subst_memory_fixed = subst_memory
+  else:
+    if input_rr:
+      input_note = '[%eax..%edi]' if index == 'rax' else '[%r8d..%r15d]'
+    else:
+      input_note = 'any_nonspecial'
+    if output_rr:
+      output_note = '[%eax..%edi]' if output_regs == 'eax' else '[%r8d..%r14d]'
+    else:
+      output_note = None
+    subst_fixed = subst[0:-1] + (input_note, output_note) + subst[-1:]
+    subst_register_fixed = subst_register[0:-1] + (
+        'any_nonspecial', output_note) + subst_register[-1:]
+    subst_memory_fixed = subst_memory[0:-1] + (input_note,
+        output_note) + subst_memory[-1:]
+  # If we already have replacements in cache then wejust reuse them.
+  output_key = (reg, rm, rm_to_reg, start_byte, index_r8, input_rr, output_rr)
+  if output_key in AddModRM_Compressor.replacements:
+    replacements = AddModRM_Compressor.replacements[output_key]
+    main_compressors.append(
+        Compressor(expanded_regex, subst_fixed, replacements[0]))
+    register_compressors.append(
+        Compressor(register_regex, subst_register_fixed, replacements[1]))
+    memory_compressors.append(
+        Compressor(expanded_regex, subst_memory_fixed, replacements[2]))
+    if options.bitness == 64 and not index_r8:
+      AddModRM_Compressor(
+          regex, subst, subst_register, subst_memory,
+          reg=reg, rm=rm, rm_to_reg=rm_to_reg, start_byte=start_byte,
+          index_r8=True, input_rr=input_rr, output_rr=output_rr)
+    return
+  # It can be memory only instruction, register only one or both
+  main_compressor = Compressor(expanded_regex, subst_fixed)
+  register_compressor = Compressor(register_regex, subst_register_fixed)
+  memory_compressor = Compressor(expanded_regex, subst_memory_fixed)
+
+  # Generation time!  Use reversed ranges to check unlikely cases first.
+  if reg is None:
+    # reg field is used as opcode extension
+    byte_range = [byte
+                  for byte in range(255, -1, -1)
+                  if byte & 0x38 == start_byte]
+  else:
+    byte_range = range(255, -1, -1)
+
+  for modrm in byte_range:
+    # Parse ModRM
+    mod_field = (modrm & 0xc0) >> 6
+    reg_field = (modrm & 0x38) >> 3
+    rm_field  = (modrm & 0x07)
+    if reg is not None:
+      reg_text = '%' + REGISTERS[reg][reg_field]
+    # If mod == 3 then it's register-to-register instruction
+    if mod_field == 3:
+      bytes = '{:02x}'.format(modrm)
+      rm_text = '%' + REGISTERS[rm][rm_field]
+      replacement = [bytes]
+      if reg is None:
+        replacement.append(rm_text)
+      else:
+        replacement.append(rm_text if rm_to_reg else reg_text)
+        replacement.append(reg_text if rm_to_reg else rm_text)
+      if options.bitness == 64:
+        replacement.append('any_nonspecial')
+        output = reg_text if rm_to_reg else rm_text
+        if output_rr:
+          replacement.append(output)
+        else:
+          replacement.append(None)
+        if output_rr is None and output in X86_64_BASE_REGISTERS: continue
+        if output_rr is True and output == '%r15d': continue
+        if rm_to_reg is None and reg_text in X86_64_BASE_REGISTERS: continue
+      replacement = tuple(replacement)
+      main_compressor.replacements.append(replacement)
+      register_compressor.replacements.append(replacement)
+    # If mod != 3 then it's register-to-memory instruction
+    else:
+      # If RM field != %rsp then there are no index
+      if rm_field != validator.REG_RSP:
+        base_text = '%' + REGISTERS[base][rm_field]
+        # If RM field == %rbp and MOD fiels is zero then it's absolute address
+        if mod_field == 0 and rm_field == validator.REG_RBP:
+          bytes = '{:02x} 00 00 00 00'.format(modrm)
+          rm_text = '0x0' if options.bitness == 32 else '0x0(%rip)'
+          base_text = '%rip'
+        # Memory access with just a base register
+        elif mod_field == 0:
+          bytes = '{:02x}'.format(modrm)
+          rm_text = '({})'.format(base_text)
+        # Memory access with base and 8bit offset
+        elif mod_field == 1:
+          bytes = '{:02x} 00'.format(modrm)
+          rm_text = '0x0({})'.format(base_text)
+        # Memory access with base and 32bit offset
+        else: # mod_field == 2
+          bytes = '{:02x} 00 00 00 00'.format(modrm)
+          rm_text = '0x0({})'.format(base_text)
+        replacement = [bytes]
+        if reg is None:
+          replacement.append(rm_text)
+        else:
+          replacement.append(rm_text if rm_to_reg else reg_text)
+          replacement.append(reg_text if rm_to_reg else rm_text)
+        if options.bitness == 64:
+          replacement.append('any_nonspecial')
+          output = reg_text if rm_to_reg else None
+          if output_rr:
+            replacement.append(output)
+          else:
+            replacement.append(None)
+          if input_rr and base_text not in X86_64_BASE_REGISTERS: continue
+          if output_rr is None and output in X86_64_BASE_REGISTERS: continue
+          if output_rr is True and output == '%r15d': continue
+          if rm_to_reg is None and reg_text in X86_64_BASE_REGISTERS: continue
+        replacement = tuple(replacement)
+        main_compressor.replacements.append(replacement)
+        memory_compressor.replacements.append(replacement)
+      else:
+        # If RM field == %rsp then we have SIB byte
+        for sib in xrange(256):
+          scale_field = (sib & 0xc0) >> 6
+          index_field = (sib & 0x38) >> 3
+          base_field  = (sib & 0x07)
+          index_text = '%' + INDEXES[index][index_field]
+          base_text = '%' + REGISTERS[base][base_field]
+          scale_text = pow(2, scale_field)
+          # If BASE is %rbp and MOD == 0 then index with 32bit offset is used
+          if mod_field == 0 and base_field == validator.REG_RBP:
+            bytes = '{:02x} {:02x} 00 00 00 00'.format(modrm, sib)
+            if (options.bitness == 32 or
+                index_field != validator.REG_RSP or
+                scale_field != 0 or index[0:2] == 'r8'):
+              rm_text = '0x0(,{},{})'.format(index_text, scale_text)
+            else:
+              rm_text = '0x0'
+            base_text = ''
+          # Memory access with base and index (no offset)
+          elif mod_field == 0:
+            bytes = '{:02x} {:02x}'.format(modrm, sib)
+            rm_text = '({},{},{})'.format(base_text, index_text, scale_text)
+          # Memory access with base, index and 8bit offset
+          elif mod_field == 1:
+            bytes = '{:02x} {:02x} 00'.format(modrm, sib)
+            rm_text = '0x0({},{},{})'.format(base_text, index_text, scale_text)
+          # Memory access with base, index and 32bit offset
+          elif mod_field == 2:
+            bytes = '{:02x} {:02x} 00 00 00 00'.format(modrm, sib)
+            rm_text = '0x0({},{},{})'.format(base_text, index_text, scale_text)
+          # Pretty-printing of access via %rsp
+          if (scale_field == 0 and index != 'r8' and
+              base_field == validator.REG_RSP and
+              index_field == validator.REG_RSP):
+            #index_text = 'any_nonspecial'
+            rm_text = ('0x0({})' if mod_field else '({})').format(base_text)
+          if index_text == "%riz":
+            index_text = 'any_nonspecial'
+          replacement = [bytes]
+          if reg is None:
+            replacement.append(rm_text)
+          else:
+            replacement.append(rm_text if rm_to_reg else reg_text)
+            replacement.append(reg_text if rm_to_reg else rm_text)
+          if options.bitness == 64:
+            if not input_rr or index_text == 'any_nonspecial':
+              replacement.append('any_nonspecial')
+            else:
+              replacement.append('%' + REGISTERS[input][index_field])
+            output = reg_text if rm_to_reg else None
+            replacement.append(output if output_rr else None)
+            if input_rr:
+              if base_text not in X86_64_BASE_REGISTERS: continue
+              if index_text in X86_64_BASE_REGISTERS - set(['%r15']): continue
+            if output_rr is None and output in X86_64_BASE_REGISTERS: continue
+            if output_rr is True and output == '%r15d': continue
+            if rm_to_reg is None and reg_text in X86_64_BASE_REGISTERS: continue
+          replacement = tuple(replacement)
+          main_compressor.replacements.append(replacement)
+          memory_compressor.replacements.append(replacement)
+
+  assert len(main_compressor.replacements) > 1
+  assert len(register_compressor.replacements) > 1
+  assert len(memory_compressor.replacements) > 1
+  main_compressor.replacements = tuple(main_compressor.replacements)
+  register_compressor.replacements = tuple(register_compressor.replacements)
+  memory_compressor.replacements = tuple(memory_compressor.replacements)
+  main_compressors.append(main_compressor)
+  register_compressors.append(register_compressor)
+  memory_compressors.append(memory_compressor)
+  AddModRM_Compressor.replacements[output_key] = (
+      main_compressor.replacements,
+      register_compressor.replacements,
+      memory_compressor.replacements
+  )
+  if options.bitness == 64 and not index_r8:
+    AddModRM_Compressor(
+        regex, subst, subst_register, subst_memory,
+        reg=reg, rm=rm, rm_to_reg=rm_to_reg, start_byte=start_byte,
+        index_r8=True, input_rr=input_rr, output_rr=output_rr)
+# Replacements cache.
+AddModRM_Compressor.replacements = {}
+
+
+def PrepareCompressors():
+  global compressors
+  global main_compressors
+  global register_compressors
+  global memory_compressors
+
+  # "Larger" compressors should be tried first, then "smaller" ones.
+  main_compressors = []
+  register_compressors = []
+  memory_compressors = []
+  extra_compressors = []
+
+  if options.bitness == 32:
+    register_kinds = ('al', 'ax', 'eax', 'mm0', 'xmm0', 'ymm0')
+    register_kind_pairs = (
+      (  'al',   'al'),
+      (  'ax',   'al'),
+      (  'ax',   'ax'),
+      ( 'eax',   'al'),
+      ( 'eax',   'ax'),
+      ( 'eax',  'eax'),
+      ( 'eax',  'mm0'),
+      ( 'mm0',  'eax'),
+      ( 'eax', 'xmm0'),
+      ('xmm0',  'eax'),
+      ( 'mm0',  'mm0'),
+      ( 'mm0', 'xmm0'),
+      ('xmm0',  'mm0'),
+      ('xmm0', 'xmm0'),
+      ('xmm0', 'ymm0'),
+      ('ymm0', 'xmm0'),
+      ('ymm0', 'ymm0')
+    )
+  else:
+    register_kinds = ('al', 'spl', 'ax', 'eax', 'rax', 'mm0', 'xmm0', 'ymm0',
+                      'r8b', 'r8w', 'r8d', 'r8', 'mm8', 'xmm8', 'ymm8')
+    register_kind_pairs = (
+      (  'al',   'al'),
+      ( 'spl',  'spl'), ( 'spl',  'r8b'), ( 'r8b',  'spl'), ( 'r8b',  'r8b'),
+      (  'ax',   'al'),
+      (  'ax',  'spl'), (  'ax',  'r8b'), ( 'r8w',  'spl'), ( 'r8w',  'r8b'),
+      (  'ax',   'ax'), (  'ax',  'r8w'), ( 'r8w',   'ax'), ( 'r8w',  'r8w'),
+      ( 'eax',   'al'),
+      ( 'eax',  'spl'), ( 'eax',  'r8b'), ( 'r8d',  'spl'), ( 'r8d',  'r8b'),
+      ( 'eax',   'ax'), ( 'eax',  'r8w'), ( 'r8d',   'ax'), ( 'r8d',  'r8w'),
+      ( 'eax',  'eax'), ( 'eax',  'r8d'), ( 'r8d',  'eax'), ( 'r8d',  'r8d'),
+      ( 'rax',   'al'),
+      ( 'rax',  'spl'), ( 'rax',  'r8b'), (  'r8',  'spl'), (  'r8',  'r8b'),
+      ( 'rax',   'ax'), ( 'rax',  'r8w'), (  'r8',   'ax'), (  'r8',  'r8w'),
+      ( 'rax',  'eax'), ( 'rax',  'r8d'), (  'r8',  'eax'), (  'r8',  'r8d'),
+      ( 'rax',  'rax'), ( 'rax',   'r8'), (  'r8',  'rax'), (  'r8',   'r8'),
+      ( 'eax',  'mm0'), ( 'eax',  'mm8'), ( 'r8d',  'mm0'), ( 'eax',  'mm8'),
+      ( 'rax',  'mm0'), ( 'rax',  'mm8'), (  'r8',  'mm0'), (  'r8',  'mm8'),
+      ( 'mm0',  'eax'), ( 'mm8',  'eax'), ( 'mm0',  'r8d'), ( 'mm8',  'r8d'),
+      ( 'mm0',  'rax'), ( 'mm8',  'rax'), ( 'mm0',   'r8'), ( 'mm8',   'r8'),
+      ( 'eax', 'xmm0'), ( 'eax', 'xmm8'), ( 'r8d', 'xmm0'), ( 'r8d', 'xmm8'),
+      ( 'rax', 'xmm0'), ( 'rax', 'xmm8'), (  'r8', 'xmm0'), (  'r8', 'xmm8'),
+      ('xmm0',  'eax'), ('xmm0',  'r8d'), ('xmm8',  'eax'), ('xmm8',  'r8d'),
+      ('xmm0',  'rax'), ('xmm0',   'r8'), ('xmm8',  'rax'), ('xmm8',   'r8'),
+      ( 'mm0',  'mm0'), ( 'mm8',  'mm0'), ( 'mm0',  'mm8'), ( 'mm8',  'mm8'),
+      ( 'mm0', 'xmm0'), ( 'mm8', 'xmm0'), ( 'mm0', 'xmm8'), ( 'mm8', 'xmm8'),
+      ('xmm0',  'mm0'), ('xmm8',  'mm0'), ('xmm0',  'mm8'), ('xmm8',  'mm8'),
+      ('xmm0', 'xmm0'), ('xmm0', 'xmm8'), ('xmm8', 'xmm0'), ('xmm8', 'xmm8'),
+      ('xmm0', 'ymm0'), ('xmm0', 'ymm8'), ('xmm8', 'ymm0'), ('xmm8', 'ymm8'),
+      ('ymm0', 'xmm0'), ('ymm0', 'xmm8'), ('ymm8', 'xmm0'), ('ymm8', 'xmm8'),
+      ('ymm0', 'ymm0'), ('ymm0', 'ymm8'), ('ymm8', 'ymm0'), ('ymm8', 'ymm8')
+    )
+
+  # Largest compressors: both reg and rm fields are used
+  for reg, rm in register_kind_pairs:
+    start_reg = REGISTERS[reg][0]
+    end_reg = REGISTERS[reg][-1 if reg[0:2] != 'r8' else -2]
+    start_rm = REGISTERS[rm][0]
+    end_rm = REGISTERS[rm][-1 if rm[0:2] != 'r8' else -2]
+    # First instruction uses just ModR/M byte in 32bit mode but both
+    # ModR/M in 64bit mode.  Both approaches will work in both cases,
+    # this is just an optimization to avoid needless work.
+    if options.bitness == 32:
+      bytes = '({RM_BYTE})'
+    else:
+      bytes = '({RM_SIB_BYTES})'
+    for extra_bytes in ('', ' 00', ' 00 00', ' 00 00 00 00'):
+      # Lea in 64 bit mode is truly unique instruction for now
+      if options.bitness == 64 and reg in ('eax', 'r8d', 'rax', 'r8'):
+        AddModRM_Compressor(
+          '.*?' + bytes + extra_bytes +
+              '  (?:lock )?\\w* (?:\\$0x0,|\\$0x0,\\$0x0,|%cl,|%xmm0,)?'
+              '({%' + rm + '}),(%{' + reg + '}).*{RR_NOTES}()',
+          ('XX', '[%{}..%{} or memory]'.format(start_rm, end_rm),
+              '[%{}..%{}]'.format(start_reg, end_reg), ' # lea'),
+          ('XX', '[%{}..%{}]'.format(start_rm, end_rm),
+              '[%{}..%{}]'.format(start_reg, end_reg), ' # rm to reg; lea'),
+          ('XX', '[memory]', '[%{}..%{}]'.format(start_reg, end_reg), ' # lea'),
+          reg=reg, rm=rm, rm_to_reg=True, input_rr=False,
+          output_rr=True if reg in ('eax', 'r8d') else None)
+      # Normal instructions with two operands (rm to reg).
+      AddModRM_Compressor(
+        '.*?' + bytes + extra_bytes +
+            '  (?:lock )?\\w* (?:\\$0x0,|\\$0x0,\\$0x0,|%cl,|%xmm0,)?'
+            '({%' + rm + '}),(%{' + reg + '}).*{RR_NOTES}()',
+        ('XX', '[%{}..%{} or memory]'.format(start_rm, end_rm),
+            '[%{}..%{}]'.format(start_reg, end_reg), ''),
+        ('XX', '[%{}..%{}]'.format(start_rm, end_rm),
+            '[%{}..%{}]'.format(start_reg, end_reg), ' # rm to reg'),
+        ('XX', '[memory]', '[%{}..%{}]'.format(start_reg, end_reg), ''),
+        reg=reg, rm=rm, rm_to_reg=True)
+      # Normal instructions with two operands (reg to rm).
+      AddModRM_Compressor(
+        '.*?' + bytes + extra_bytes +
+            '  (?:lock )?\\w* (?:\\$0x0,|%cl,)?'
+            '(%{' + reg + '}),({%' + rm + '}).*{RR_NOTES}()',
+        ('XX', '[%{}..%{}]'.format(start_reg, end_reg),
+            '[%{}..%{} or memory]'.format(start_rm, end_rm), ''),
+        ('XX', '[%{}..%{}]'.format(start_reg, end_reg),
+            '[%{}..%{}]'.format(start_rm, end_rm), ' # reg to rm'),
+        ('XX', '[%{}..%{}]'.format(start_reg, end_reg), '[memory]', ''),
+        reg=reg, rm=rm, rm_to_reg=False)
+      # There are few more forms in 64 bit case (rm to reg).
+      if options.bitness == 64 and reg in ('eax', 'r8d'):
+        # Zero-extending version.
+        AddModRM_Compressor(
+          '.*?' + bytes + extra_bytes +
+              '  (?:lock )?\\w* (?:\\$0x0,|\\$0x0,\\$0x0,|%cl,|%xmm0,)?'
+              '({%' + rm + '}),(%{' + reg + '}).*{RR_NOTES}()',
+          ('XX', '[%{}..%{} or memory]'.format(start_rm, end_rm),
+              '[%{}..%{}]'.format(start_reg, end_reg), ''),
+          ('XX', '[%{}..%{}]'.format(start_rm, end_rm),
+              '[%{}..%{}]'.format(start_reg, end_reg), ' # rm to reg'),
+          ('XX', '[memory]', '[%{}..%{}]'.format(start_reg, end_reg), ''),
+          reg=reg, rm=rm, rm_to_reg=True, output_rr=True)
+      # More forms in 64 bit case (reg to rm).
+      if options.bitness == 64 and rm in ('eax', 'r8d'):
+        # Zero-extending version.
+        AddModRM_Compressor(
+          '.*?' + bytes + extra_bytes +
+              '  (?:lock )?\\w* (?:\\$0x0,|%cl,)?'
+              '(%{' + reg + '}),({%' + rm + '}).*{RR_NOTES}()',
+          ('XX', '[%{}..%{}]'.format(start_reg, end_reg),
+              '[%{}..%{} or memory]'.format(start_rm, end_rm), ''),
+          ('XX', '[%{}..%{}]'.format(start_reg, end_reg),
+              '[%{}..%{}]'.format(start_rm, end_rm), ' # reg to rm'),
+          ('XX', '[%{}..%{}]'.format(start_reg, end_reg), '[memory]', ''),
+          reg=reg, rm=rm, rm_to_reg=False, output_rr=True)
+        # Zero-extending xchg/xadd.
+        AddModRM_Compressor(
+          '.*?' + bytes + extra_bytes +
+              '  (?:lock )?\\w* (?:\\$0x0,|%cl,)?'
+              '(%{' + reg + '}),({%' + rm + '}).*{RR_NOTES}()',
+          ('XX', '[%{}..%{}]'.format(start_reg, end_reg),
+              '[%{}..%{} or memory]'.format(start_rm, end_rm),
+              ' # write to both'),
+          ('XX', '[%{}..%{}]'.format(start_reg, end_reg),
+              '[%{}..%{}]'.format(start_rm, end_rm),
+              ' # reg to rm; write to both'),
+          ('XX', '[%{}..%{}]'.format(start_reg, end_reg), '[memory]',
+              ' # write to both'),
+          reg=reg, rm=rm, rm_to_reg=None, output_rr=True)
+      # Still more forms for 64 bit case (rm to reg).
+      if options.bitness == 64 and reg in ('al', 'spl', 'ax', 'eax', 'rax',
+                                           'r8b', 'r8w', 'r8d', 'r8'):
+        # Dangerous instructions (rm to reg).
+        AddModRM_Compressor(
+          '.*?' + bytes + extra_bytes +
+              '  (?:lock )?\\w* (?:\\$0x0,|\\$0x0,\\$0x0,|%cl,|%xmm0,)?'
+              '({%' + rm + '}),(%{' + reg + '}).*{RR_NOTES}()',
+          ('XX', '[%{}..%{} or memory]'.format(start_rm, end_rm),
+              '[%{}..%{}]'.format(start_reg, end_reg), ''),
+          ('XX', '[%{}..%{}]'.format(start_rm, end_rm),
+              '[%{}..%{}]'.format(start_reg, end_reg), ' # rm to reg'),
+          ('XX', '[memory]', '[%{}..%{}]'.format(start_reg, end_reg), ''),
+          reg=reg, rm=rm, rm_to_reg=True, output_rr=None)
+      # Still more forms for 64 bit case (reg to rm).
+      if options.bitness == 64 and rm in ('al', 'spl', 'ax', 'eax', 'rax',
+                                          'r8b', 'r8w', 'r8d', 'r8'):
+        # Dangerous instructions (reg to rm).
+        AddModRM_Compressor(
+          '.*?' + bytes + extra_bytes +
+              '  (?:lock )?\\w* (?:\\$0x0,|%cl,)?'
+              '(%{' + reg + '}),({%' + rm + '}).*{RR_NOTES}()',
+          ('XX', '[%{}..%{}]'.format(start_reg, end_reg),
+              '[%{}..%{} or memory]'.format(start_rm, end_rm), ''),
+          ('XX', '[%{}..%{}]'.format(start_reg, end_reg),
+              '[%{}..%{}]'.format(start_rm, end_rm), ' # reg to rm'),
+          ('XX', '[%{}..%{}]'.format(start_reg, end_reg), '[memory]', ''),
+          reg=reg, rm=rm, rm_to_reg=False, output_rr=None)
+        # Dangerous xchg/xadd.
+        AddModRM_Compressor(
+          '.*?' + bytes + extra_bytes +
+              '  (?:lock )?\\w* (?:\\$0x0,|%cl,)?'
+              '(%{' + reg + '}),({%' + rm + '}).*{RR_NOTES}()',
+          ('XX', '[%{}..%{}]'.format(start_reg, end_reg),
+              '[%{}..%{} or memory]'.format(start_rm, end_rm),
+              ' # write to both'),
+          ('XX', '[%{}..%{}]'.format(start_reg, end_reg),
+              '[%{}..%{}]'.format(start_rm, end_rm),
+              ' # reg to rm; write to both'),
+          ('XX', '[%{}..%{}]'.format(start_reg, end_reg), '[memory]',
+              ' # write to both'),
+          reg=reg, rm=rm, rm_to_reg=None, output_rr=None)
+    # 3DNow! instructions.  Additional byte is opcode extension.
+    AddModRM_Compressor(
+      '.*?' + bytes + ' [0-9a-fA-F][0-9a-fA-F]  \\w* '
+          '({%' + rm + '}),(%{' + reg + '}).*{RR_NOTES}()',
+      ('XX', '[%{}..%{} or memory]'.format(start_rm, end_rm),
+          '[%{}..%{}]'.format(start_reg, end_reg), ''),
+      ('XX', '[%{}..%{}]'.format(start_rm, end_rm),
+          '[%{}..%{}]'.format(start_reg, end_reg), ' # reg to rm'),
+      ('XX', '[memory]', '[%{}..%{}]'.format(start_reg, end_reg), ''),
+      reg=reg, rm=rm, rm_to_reg=True)
+
+  # Smaller compressors: only rm field is used.
+  for rm in register_kinds:
+    start_rm = REGISTERS[rm][0]
+    end_rm = REGISTERS[rm][-1 if rm[0:2] != 'r8' else -2]
+    for opcode in xrange(8):
+      XX_byte_mark = 'XX/' + str(opcode)
+      start_byte = opcode * 8
+      # First instruction uses just ModR/M byte in 32bit mode but both
+      # ModR/M in 64bit mode.  Both approaches will work in both cases,
+      # this is just an optimization to avoid needless work.
+      if options.bitness == 32:
+        bytes = '({RM_BYTE/' + str(opcode) + '})'
+      else:
+        bytes = '({RM_SIB_BYTES/' + str(opcode) + '})'
+      if options.bitness == 64:
+        # No memory access (e.g. prefetch)
+        AddModRM_Compressor(
+          '.*?' + bytes + '  ?\\w* (?:\\$0x0,|%cl,)?({%' + rm + '}).*'
+          '{RR_NOTES}()',
+          (XX_byte_mark, '[%{}..%{} or memory]'.format(start_rm, end_rm), ''),
+          (XX_byte_mark, '[%{}..%{}]'.format(start_rm, end_rm), ''),
+          (XX_byte_mark, '[memory]', ''),
+          reg=None, rm=rm, input_rr=False, start_byte=start_byte)
+      for extra_bytes in ('', ' 00', ' 00 00', ' 00 00 00 00'):
+        # Part of opcode is encoded in ModR/M
+        AddModRM_Compressor(
+          '.*?' + bytes + extra_bytes +
+              '  (?:lock )?\\w* (?:\\$0x0,|%cl,)?'
+              '({%' + rm + '}).*{RR_NOTES}()',
+          (XX_byte_mark, '[%{}..%{} or memory]'.format(start_rm, end_rm), ''),
+          (XX_byte_mark, '[%{}..%{}]'.format(start_rm, end_rm), ''),
+          (XX_byte_mark, '[memory]', ''),
+          reg=None, rm=rm, start_byte=start_byte)
+        # More forms in 64 bit case.
+        if options.bitness == 64 and rm in ('eax', 'r8d'):
+          # Zero-extending version.
+          AddModRM_Compressor(
+            '.*?' + bytes + extra_bytes +
+                '  (?:lock )?\\w* (?:\\$0x0,|%cl,)?'
+                '({%' + rm + '}).*{RR_NOTES}()',
+            (XX_byte_mark, '[%{}..%{} or memory]'.format(start_rm, end_rm), ''),
+            (XX_byte_mark, '[%{}..%{}]'.format(start_rm, end_rm), ''),
+            (XX_byte_mark, '[memory]', ''),
+            reg=None, rm=rm, start_byte=start_byte, output_rr=True)
+        # Still more forms for 64 bit case (reg to rm).
+        if options.bitness == 64 and rm in ('al', 'spl', 'ax', 'eax', 'rax',
+                                            'r8b', 'r8w', 'r8d', 'r8'):
+          # Dangerous instructions.
+          AddModRM_Compressor(
+            '.*?' + bytes + extra_bytes +
+                '  (?:lock )?\\w* (?:\\$0x0,|%cl,)?'
+                '({%' + rm + '}).*{RR_NOTES}()',
+            (XX_byte_mark, '[%{}..%{} or memory]'.format(start_rm, end_rm), ''),
+            (XX_byte_mark, '[%{}..%{}]'.format(start_rm, end_rm), ''),
+            (XX_byte_mark, '[memory]', ''),
+            reg=None, rm=rm, start_byte=start_byte, output_rr=None)
+
+  # Even smaller compressors: only low 3 bits of opcode are used.
+  for reg in register_kinds + ('st(0)',):
+    start_reg = REGISTERS[reg][0]
+    end_reg = REGISTERS[reg][-1 if reg[0:2] != 'r8' else -2]
+    for opcode in xrange(8):
+      for extra_bytes in ('', ' 00', ' 00 00', ' 00 00 00 00'):
+        for text1, text2, nibble in (
+          ('[0..7]', '[8..f]', xrange(8)),
+          ('[012367]', '[89abef]', (0, 1, 2, 3, 6, 7)),
+          ('[0..6]', '[8..e]', xrange(7))
+        ):
+          # Operand is encoded in opcode
+          extra_compressors.append(Compressor(re.compile(
+            '.*?[0-9a-fA-F]([0-7])' + extra_bytes +
+            '  \\w* (?:\\$0x0,|%ax,|%st,)?'
+            '(%(?:' + '|'.join(REGISTERS_RE[reg]) + ')).*()'),
+            (text1, '[%{}..%{}]'.format(start_reg, end_reg), ''),
+            tuple(('{:x}'.format(n), '%' + REGISTERS[reg][n])
+                  for n in nibble)))
+          extra_compressors.append(Compressor(re.compile(
+            '.*?[0-9a-fA-F]([89a-fA-F])' + extra_bytes +
+            '  \\w* (?:\\$0x0,|%ax,|%st,)?'
+            '(%(?:' + '|'.join(REGISTERS_RE[reg]) + ')).*()'),
+            (text2, '[%{}..%{}]'.format(start_reg, end_reg), ''),
+            tuple(('{:x}'.format(n + 8), '%' + REGISTERS[reg][n])
+                   for n in nibble)))
+          # Another version for 64 bit case
+          if options.bitness == 64 and reg in ('eax', 'r8d'):
+            # Operand is encoded in opcode and output
+            extra_compressors.append(Compressor(re.compile(
+              '.*?[0-9a-fA-F]([0-7])' + extra_bytes +
+              '  \\w* (?:\\$0x0,|%ax,|%st,)?'
+              '(%(?:' + '|'.join(REGISTERS_RE[reg]) + ')).*'
+              'output_rr=(%(?:'+ '|'.join(REGISTERS_RE[reg]) + ')).*()'),
+              tuple([text1] + ['[%{}..%{}]'.format(start_reg, end_reg)] * 2 +
+                    ['']),
+              tuple(['{:x}'.format(n)] + ['%' + REGISTERS[reg][n]] * 2
+                     for n in nibble)))
+            extra_compressors.append(Compressor(re.compile(
+              '.*?[0-9a-fA-F]([89a-fA-F])' + extra_bytes +
+              '  \\w* (?:\\$0x0,|%ax,|%st,)?'
+              '(%(?:' + '|'.join(REGISTERS_RE[reg]) + ')).*'
+              'output_rr=(%(?:'+ '|'.join(REGISTERS_RE[reg]) + ')).*()'),
+              tuple([text2] + ['[%{}..%{}]'.format(start_reg, end_reg)] * 2 +
+                    ['']),
+              tuple(['{:x}'.format(n + 8)] + ['%' + REGISTERS[reg][n]] * 2
+                     for n in nibble)))
+  compressors = (main_compressors + memory_compressors + register_compressors +
+      extra_compressors)
+
+  # Special compressors: will handle some cosmetic issues.
+  #
+  # SETxx ignores reg field and thus are described as many separate instructions
+  compressors.append(Compressor(
+      re.compile('.*0f 9[0-9a-fA-F] XX(/[0-7])  set.*()'), ('', ''),
+      [('/' + str(i), ) for i in range(8)]))
+  # BSWAP is described with opcode "0f c8+r", not "0f /1" in manual
+  if options.bitness == 32:
+    compressors.append(Compressor(
+        re.compile('.*(XX/1)  bswap.*ax.*()'), ('c[8..f]', ''), [('XX/1', )]))
+  else:
+    compressors.append(Compressor(
+        re.compile('.*(XX/1)  bswap.*ax.*()'), ('c[89abef]', ''), [('XX/1', )]))
+    compressors.append(Compressor(
+        re.compile('.*(XX/1)  bswap.*r8.*()'), ('c[8..e]', ''), [('XX/1', )]))
+  # Add mark '# write to both' to certain versions of CMPXCHG, XADD, and XCHG
+  if options.bitness == 64:
+    compressors.append(Compressor(
+          re.compile('.* (?:cmpxchg|xadd|xchg).*%al\\.\\.%bh[^#]*()$'),
+          (' # write to both', ), ((), )))
+  # "and $0xe0,[%eax..%edi]" is treated specially which means that we list all
+  # versions of and "[$0x1..$0xff],[%eax..%edi]" separately here.
+  # Without this rule these ands comprise 2/3 of the whole output!
+  if options.bitness == 32:
+    compressors.append(Compressor(
+        re.compile('.*83 (e0 01  and \\$0x1,%eax)()'),
+        ('XX/4 00  and[l]? $0x0,[%eax..%edi or memory]', ' # special and'),
+        [('e{} {:02x}  and $0x{:x},%{}'.format(r, i, i, REGISTERS['eax'][r]), )
+         for i in range(1, 256) for r in range(8)] +
+        [('XX/4 00  and[l]? $0x0,[%eax..%edi or memory]', )]))
+  else:
+    for reg in ('eax', 'r8d'):
+      start_reg = REGISTERS[reg][0]
+      end_reg = REGISTERS[reg][-1 if reg[0:2] != 'r8' else -2]
+      for index_reg in ('eax', 'r8d'):
+        start_index = REGISTERS[index_reg][0]
+        end_index = REGISTERS[index_reg][-1]
+        compressors.append(Compressor(
+            re.compile('.*83 (e0 01  and \\$0x1,%' + reg + ').*'
+                       'input_rr=(any_nonspecial); output_rr=(%' + reg + ')()'),
+            ('XX/4 00  and[l]? $0x0,[%{}..%{} or memory]'.format(start_reg,
+             end_reg), '[%{}..%{}]'.format(start_index, end_index),
+             '[%{}..%{}]'.format(start_reg, end_reg),
+             ' # special and'),
+            [('e{} {:02x}  and $0x{:x},%{}'.format(r, i, i, REGISTERS[reg][r]),
+              'any_nonspecial', '%' + REGISTERS[reg][r])
+             for i in range(1, 256) for r in range(7 + (reg == 'eax'))] +
+            [('XX/4 00  and[l]? $0x0,[%{}..%{} or memory]'.format(start_reg,
+              end_reg), '[%{}..%{}]'.format(start_index, end_index),
+              '[%{}..%{}]'.format(start_reg, end_reg))]))
+  # Merge memory and non-memory access
+  if options.bitness == 32:
+    letters_and_registers = (('b', 'al', ''), ('w', 'ax', ''), ('l', 'eax', ''))
+  else:
+    letters_and_registers = (
+       ('b',  'al', 'eax'), ('b', 'spl', 'eax'), ('b', 'r8b', 'r8d'),
+       ('w',  'ax', 'eax'), ('w', 'r8w', 'r8d'),
+       ('l', 'eax', 'eax'), ('l', 'r8d', 'r8d'),
+       ('q', 'rax', 'eax'), ('q',  'r8', 'r8d')
+    )
+  for letter, reg, out_reg in letters_and_registers:
+    start_reg = REGISTERS[reg][0]
+    end_reg = REGISTERS[reg][-1 if reg[0:2] != 'r8' else -2]
+    all_regs = '[%{}..%{}]'.format(start_reg, end_reg)
+    regs_mark = '[%{}..%{} or memory]'.format(start_reg, end_reg)
+    if options.bitness == 64:
+      start_out = REGISTERS[out_reg][0]
+      end_out = REGISTERS[out_reg][-1 if out_reg[0:2] != 'r8' else -2]
+      out_regs = '[%{}..%{}]'.format(start_out, end_out)
+    for notes in ('', ' # rm to reg', ' # reg to rm'):
+      compressors.append(Compressor(
+          re.compile('.*  \\w*(' + letter + ') .*(\\[memory]).*()()'),
+          ('[{}]?'.format(letter), regs_mark, '', ''),
+          ((letter, '[memory]', ''), ('', all_regs, notes))))
+      if options.bitness == 64:
+        for index_reg in ('eax', 'r8d'):
+          start_index = REGISTERS[index_reg][0]
+          end_index = REGISTERS[index_reg][-1]
+          index_regs = '[%{}..%{}]'.format(start_index, end_index)
+          for output_rrs in ((None, out_regs), (out_regs, None), (None, None)):
+            compressors.append(Compressor(
+                re.compile('.*  \\w*(' + letter + ') .*(\\[memory]).*; '
+                'input_rr=(\\[%[a-z0-9]*..%[a-z0-9]*\\]); '
+                'output_rr=(\\[%[a-z0-9]*..%[a-z0-9]*\\]|None)()()'),
+                ('[{}]?'.format(letter), regs_mark, index_regs,
+                 output_rrs[0] if output_rrs[0] is not None else output_rrs[1],
+                 '', ''),
+                ((letter, '[memory]', index_regs, output_rrs[0], ''),
+                 ('', all_regs, 'any_nonspecial', output_rrs[1], notes))))
+
+  # REX compressors
+  if options.bitness == 64:
+    # First pretty complex set of compressors to combine versions of REX with
+    # three lowest bits in different states.
+    register_kind_pairs = (
+      (  None,   None),
+      (  'al',   'al'), (  'al',  None), (None,   'al'),
+      (  'ax',   'al'), (  'al',  'ax'),
+      (  'ax',   'ax'), (  'ax',  None), (None,   'ax'),
+      ( 'eax',   'al'), (  'al', 'eax'),
+      ( 'eax',   'ax'), (  'ax', 'eax'),
+      ( 'eax',  'eax'), ( 'eax',  None), (None,  'eax'),
+      ( 'rax',   'al'), (  'al', 'rax'),
+      ( 'rax',   'ax'), (  'ax', 'rax'),
+      ( 'rax',  'eax'), ( 'eax', 'rax'),
+      ( 'rax',  'rax'), ( 'rax',  None), (None,  'rax'),
+      ( 'eax',  'mm0'), ( 'mm0', 'eax'),
+      ( 'rax',  'mm0'), ( 'mm0', 'rax'),
+      ( 'mm0',  'eax'), ( 'eax', 'mm0'),
+      ( 'mm0',  'rax'), ( 'rax', 'mm0'),
+      ( 'eax', 'xmm0'),
+      ( 'rax', 'xmm0'),
+      ('xmm0',  'eax'),
+      ('xmm0',  'rax'),
+      ( 'mm0',  'mm0'), ( 'mm0',  None), (None,  'mm0'),
+      ( 'mm0', 'xmm0'),
+      ('xmm0',  'mm0'),
+      ('xmm0', 'xmm0'),
+      ('xmm0', 'ymm0'), ('xmm0',  None), (None, 'xmm0'),
+      ('ymm0', 'xmm0'),
+      ('ymm0', 'ymm0'), ('ymm0',  None), (None, 'ymm0'),
+    )
+    r8 = {
+      'al': 'r8b',
+      'ax': 'r8w',
+      'eax': 'r8d',
+      'rax': 'r8',
+      'mm0': 'mm8',
+      'xmm0': 'xmm8',
+      'ymm0': 'ymm8'
+    }
+    for reg, rm in register_kind_pairs:
+      for last_reg, last_rm in ((-1, -1), (-1, -2), (-2, -1), (-2, -2)):
+        if reg:
+          start_reg = REGISTERS[reg][0]
+          start_reg8 = REGISTERS[r8[reg]][0]
+          end_reg = REGISTERS[reg][-1]
+          end_reg0 = 'dil' if reg == 'al' else end_reg
+          end_reg8 = REGISTERS[r8[reg]][last_reg]
+          reg_regex = '\\[(%' + start_reg + '\\.\\.%' + end_reg + ')]'
+          reg_regex0 = '\\[(%' + start_reg + '\\.\\.%' + end_reg0 + ')]'
+        elif last_reg == -2:
+          continue
+        if rm:
+          start_rm = REGISTERS[rm][0]
+          start_rm8 = REGISTERS[r8[rm]][0]
+          end_rm = REGISTERS[rm][-1]
+          end_rm0 = 'dil' if rm == 'al' else end_rm
+          end_rm8 = REGISTERS[r8[rm]][last_rm]
+          rm_regex = ('\\[(%' + start_rm + '\\.\\.%' + end_rm + ')'
+                      '(?: or memory)?]')
+          rm_regex0 = ('\\[(%' + start_rm + '\\.\\.%' + end_rm0 + ')'
+                       '(?: or memory)?]')
+        elif last_rm == -2:
+          continue
+        for rexw in (True, False):
+          for input_rr in (True, False):
+            for output_rr in (True, False) if reg or rm else (None, ):
+              for rm_to_reg in (True, False) if reg and rm else (None, ):
+                # Legacy prefixes
+                regex = '.*:(?: 26| 2e| 36| 3e| 64| 65| 66| 67| f0| f2| f3)*'
+                # REX
+                regex += '( 48).*' if rexw else '( 40|).*'
+                # Replacement text
+                replacement_tuple = (
+                    ' [REX:48..4f]' if rexw else ' [REX:40..47]?', )
+                if reg:
+                  replacement_regs = '%{}..%{}'.format(start_reg, end_reg8)
+                if rm:
+                  replacement_rms = '%{}..%{}'.format(start_rm, end_rm8)
+                # Instruction arguments
+                if not reg and not rm:
+                  pass
+                elif not reg and rm:
+                  if rexw:
+                    regex += rm_regex0 + '.*'
+                  else:
+                    regex += rm_regex + '.*'
+                  replacement_tuple += (replacement_rms, )
+                elif reg and not rm:
+                  if rexw:
+                    regex += reg_regex0 + '.*'
+                  else:
+                    regex += reg_regex + '.*'
+                  replacement_tuple += (replacement_regs, )
+                elif rm_to_reg:
+                  if rexw:
+                    regex += rm_regex0 + ',' + reg_regex0 + '.*'
+                  else:
+                    regex += rm_regex + ',' + reg_regex + '.*'
+                  replacement_tuple += (replacement_rms, replacement_regs)
+                else:
+                  if rexw:
+                    regex += reg_regex0 + ',' + rm_regex0 + '.*'
+                  else:
+                    regex += reg_regex + ',' + rm_regex + '.*'
+                  replacement_tuple += (replacement_regs, replacement_rms)
+                # Input and output restricted registers
+                if input_rr:
+                  regex += 'input_rr=\\[(%eax\\.\\.%edi)].*'
+                  replacement_tuple += ('%eax..%r15d', )
+                if output_rr:
+                  regex += 'output_rr=\\[(%eax\\.\\.%edi)].*'
+                  replacement_tuple += ('%eax..%r14d', )
+                regex += '()'
+                replacement_tuple += ('', )
+                # Replacement cases
+                replacement_tuples = ()
+                for byte in (range(0x48, 0x50)
+                             if rexw
+                             else range(0x40, 0x48) + ['']):
+                  replacement_case = (
+                      ' {:02x}'.format(byte) if byte else byte, )
+                  if byte:
+                    if rm:
+                      if byte & 0x1:
+                        replacement_rms = '%{}..%{}'.format(start_rm8, end_rm8)
+                      else:
+                        replacement_rms = '%{}..%{}'.format(start_rm, end_rm0)
+                    if byte & 0x2:
+                      replacement_index = '%r8d..%r15d'
+                    else:
+                      replacement_index = '%eax..%edi'
+                    if reg:
+                      if byte & 0x4:
+                        replacement_regs = '%{}..%{}'.format(start_reg8,
+                                                             end_reg8)
+                      else:
+                        replacement_regs = '%{}..%{}'.format(start_reg,
+                                                             end_reg0)
+                  else:
+                    if rm:
+                      replacement_rms = '%{}..%{}'.format(start_rm, end_rm)
+                    replacement_index = '%eax..%edi'
+                    if reg:
+                      replacement_regs = '%{}..%{}'.format(start_reg, end_reg)
+                  if not reg and not rm:
+                    pass
+                  elif not reg and rm:
+                    replacement_case += (replacement_rms, )
+                    if byte:
+                      final_rr = '%r8d..%r14d' if byte & 0x1 else '%eax..%edi'
+                    else:
+                      final_rr = '%eax..%edi'
+                  elif reg and not rm:
+                    replacement_case += (replacement_regs, )
+                    if byte:
+                      final_rr = '%r8d..%r14d' if byte & 0x4 else '%eax..%edi'
+                    else:
+                      final_rr = '%eax..%edi'
+                  elif rm_to_reg:
+                    replacement_case += (replacement_rms, replacement_regs)
+                    if byte:
+                      final_rr = '%r8d..%r14d' if byte & 0x4 else '%eax..%edi'
+                    else:
+                      final_rr = '%eax..%edi'
+                  else:
+                    replacement_case += (replacement_regs, replacement_rms)
+                    if byte:
+                      final_rr = '%r8d..%r14d' if byte & 0x1 else '%eax..%edi'
+                    else:
+                      final_rr = '%eax..%edi'
+                  if input_rr: replacement_case += (replacement_index, )
+                  if output_rr: replacement_case += (final_rr, )
+                  replacement_tuples += (replacement_case, )
+                compressors.append(Compressor(
+                    re.compile(regex), replacement_tuple, replacement_tuples))
+    # This is pretty simple compressor to combine two lines with different REX.W
+    # bits (only if they are otherwise identical).
+    compressors.append(Compressor(
+        re.compile('.*(\\[REX:40\\.\\.47]\\?).*()'), ('[REX:40..4f]?', ''),
+        (('[REX:40..47]?', ), ('[REX:48..4f]', ))))
+
+
+def ShowProgress(rule, instruction):
+  if rule not in ShowProgress.rules_shown:
+    first_print = True
+    ShowProgress.rules_shown[rule]=len(ShowProgress.rules_shown)
+  else:
+    first_print = False
+  print >> sys.stderr, '-------- Compressed --------'
+  print >> sys.stderr, 'Rule:', ShowProgress.rules_shown[rule]
+  print >> sys.stderr, '--------'
+  compressor = compressors[rule]
+  match = compressor.regex.match(instruction)
+  assert match
+  pos = 0
+  format_str = ''
+  for group in range(1, len(match.groups())):
+    format_str += instruction[pos:match.start(group)] + '{{{}}}'
+    pos = match.end(group)
+  format_str += instruction[pos:match.start(len(match.groups()))]
+  replacements = []
+  for replacement in compressor.replacements:
+    replacements.append(format_str.format(*replacement))

[halyavin, 2013/11/06 14:23:24]

Replace with for expression.

[khim, 2013/11/06 21:28:28]

Done.

+  replacements = sorted(replacements)
+  if len(compressor.replacements) <= 4 or first_print:
+    for replacement in replacements:
+      print >> sys.stderr, replacement
+  else:
+    print >> sys.stderr, replacements[0]
+    print >> sys.stderr, "..."
+    print >> sys.stderr, replacements[-1]
+  print >> sys.stderr, '--------'
+  print >> sys.stderr, 'Compressed', (
+      format_str + '{}').format(*compressor.subst)
+ShowProgress.rules_shown = {}
+
+
+def main():
+  # We are keeping these global to share state graph and compressors
+  # between workers spawned by multiprocess. Passing them every time is slow.
+  global options, xml_file
+  global dfa
+  global worker_validator
+  options, xml_file = ParseOptions()
+  dfa = dfa_parser.ParseXml(xml_file)
+  worker_validator = validator.Validator(
+      validator_dll=options.validator_dll,
+      decoder_dll=options.decoder_dll)
+  PrepareCompressors()
+
+  assert dfa.initial_state.is_accepting
+  assert not dfa.initial_state.any_byte
+
+  print >> sys.stderr, len(dfa.states), 'states'
+
+  num_suffixes = dfa_traversal.GetNumSuffixes(dfa.initial_state)
+
+  # We can't just write 'num_suffixes[dfa.initial_state]' because
+  # initial state is accepting.
+  total_instructions = sum(
+      num_suffixes[t.to_state]
+      for t in dfa.initial_state.forward_transitions.values())
+  print >> sys.stderr, total_instructions, 'regular instructions total'
+
+  tasks = dfa_traversal.CreateTraversalTasks(dfa.states, dfa.initial_state)
+  print >> sys.stderr, len(tasks), 'tasks'
+
+  pool = multiprocessing.Pool()
+
+  results = pool.imap(Worker, tasks)
+
+  total = 0
+  num_valid = 0
+  full_output = set()
+  for prefix, count, valid_count, output, trace in results:
+    print >> sys.stderr, 'Prefix:', ', '.join(map(hex, prefix))
+    total += count
+    num_valid += valid_count
+    full_output |= output
+    for rule, instruction in trace:
+      ShowProgress(rule, instruction)
+  for instruction in sorted(Compressed(full_output, ShowProgress)):
+    print instruction
+
+  print >> sys.stderr, total, 'instructions were processed'
+  print >> sys.stderr, num_valid, 'valid instructions'
+
+
+if __name__ == '__main__':
+  main()