Regular instructions golden file test.

src/trusted/validator_ragel/compress_regular_instructions.py

Index: src/trusted/validator_ragel/compress_regular_instructions.py
===================================================================
--- src/trusted/validator_ragel/compress_regular_instructions.py	(revision 0)
+++ src/trusted/validator_ragel/compress_regular_instructions.py	(revision 0)
@@ -0,0 +1,1428 @@
+# 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.
+
+Each rule is applied only when all variants are accepted by validator.
+The following compression rules are present:
+
+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]
+
+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]
+
+1b. Compress ModR/M register only.
+  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]
+
+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]
+
+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]
+
+2b. Compress ModR/M register-only with opcode extension.
+  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]
+
+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.  We use mnemonic name 'mmalt'
+# to represent the "evil mirror" of the 'mm0' 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)                     ],
+  'mmalt': [ 'mm{}'.format(N) for N in range(8)                     ],
+  'st(0)': [ 'st({})'.format(N) for N in range(8)                   ],
+   '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 instructions require particular value to
+# 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 registers' into validator and then
+# 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
+    # Note that iteration order is aligned with ACCEPTABLE_X86_64_INPUTS array
+    # above.
+    for bit, initial_rr in enumerate(validator.ALL_REGISTERS + [None]):
+      valid, final_rr = validator_inst.ValidateAndGetFinalRestrictedRegister(
+          bundle, len(instruction), initial_rr)
+      if valid:
+        # final_rr should not depend on input_rr
+        assert valid_inputs == 0 or known_final_rr == final_rr
+        valid_inputs |= 1 << bit
+        known_final_rr = final_rr
+    # 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 True, [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()
+    self.trace = []
+
+
+  def ReceiveInstruction(self, bytes):
+    self.total_instructions += 1
+    result, notes = ValidateInstruction(bytes, self.validator)
+    if result:
+      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])
+      # 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 simplify
+      # compression.
+      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] ){' + str(bytes) + '} .* )' +
+              hex(bytes) + '(.*)',
+              '\\1%eip\\2' if options.bitness == 32 else '\\1%rip\\2',
+              dis[0]);
+      dis[0] = 'Instruction: ' + dis[0]
+      dis += notes
+      self.output.add('; '.join(dis))
+
+
+  def RecordTrace(self, compressor_nr, instruction):
+    self.trace.append((compressor_nr, instruction))
+
+
+# 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 = re.compile(regex)
+    self.subst = subst
+    self.replacements = [] if replacements is None else replacements
+
+
+def CompressionTemplate(instruction, match, mark):
+  """ Replace all match groups with the mark. """
+  pos = 0
+  format_str = ''
+  for group in range(1, len(match.groups())):
+    format_str += instruction[pos:match.start(group)] + mark
+    pos = match.end(group)
+  return format_str + instruction[pos:match.start(len(match.groups()))]
+
+
+def CompressOneMatch(instructions, instruction, match, compressor):
+  format_str = CompressionTemplate(instruction, match, '{}')
+  subset = set()
+  for replacement in compressor.replacements:
+    replacement_str = format_str.format(*replacement)
+    if not replacement_str in instructions:
+      return (False, instructions)
+    subset.add(replacement_str)
+  instructions -= subset
+  instructions.add((format_str + '{}').format(*compressor.subst))
+  return (True, instructions)
+
+
+def CompressOneInstruction(instructions, compressors, split, cache):
+  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:
+    if instruction in cache:
+      compressors_list = cache[instruction]
+      for compressor_nr, match, compressor in compressors_list:
+        result, instructions = CompressOneMatch(
+            instructions, instruction, match, compressor)
+        if result:
+          return (instructions, compressor_nr, instruction)
+    else:
+      compressors_list = []
+      for compressor_nr, compressor in enumerate(compressors):
+        match = compressor.regex.match(instruction)
+        if match:
+          compressors_list.append((compressor_nr, match, compressor))
+          result, instructions = CompressOneMatch(
+              instructions, instruction, match, compressor)
+          if result:
+            return (instructions, compressor_nr, instruction)
+      cache[instruction] = compressors_list
+  return (instructions, False, False)
+
+
+def Compressed(instructions, compressors, show_progress):
+  split = ''
+  cache = {}
+  while True:
+    instructions, rule, split = CompressOneInstruction(
+        instructions, compressors, split, cache)
+    if rule is False: break
+    show_progress(rule, split)
+  return instructions
+
+
+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
+      worker_state.output = Compressed(set(worker_state.output),
+                                       compressors,
+                                       worker_state.RecordTrace)
+  except Exception as e:
+    traceback.print_exc() # because multiprocessing imap swallows traceback
+    raise
+
+  return (
+      prefix,
+      worker_state.total_instructions,
+      worker_state.num_valid,
+      worker_state.output,
+      worker_state.trace)
+
+
+def ParseOptions():
+  parser = optparse.OptionParser(usage='%prog [options] xmlfile')
+
+  parser.add_option('--bitness',
+                    choices=['32', '64'],
+                    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()
+  options.bitness = int(options.bitness)
+
+  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\\(0\\)'] = 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 AddModRMCompressor(regex, subst, subst_register, subst_memory,
+                       rm, reg=None, writes_to='rm', opcode_bits=0,
+                       memory_accessed=True, register_write='ignore',
+                       index_r8=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)

[halyavin, 2013/11/08 15:35:19]

regsiter->register

[khim, 2013/11/12 10:14:56]

This comment is removed

+
+  Args:
+    regex: regular expression 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
+    rm: rm operand kind (see REGISTERS array)
+    reg: reg operand kind (see REGISTERS array) or None if reg is not used
+    writes_to: three-state selector
+      'reg'  - instruction uses rm as source, reg as destination
+      'rm'   - instruction uses reg as source, rm as destination
+      'both' - instruction writes to both reg and rm
+    opcode_bits: opcode extensions code (used when reg is None)
+    memory_accessed: True if instruction accesses memory
+    register_write: three-state selector
+      'sandbox' - instruction can be used to produce "restricted register"
+      'protect' - instruction can damage output, protect "special registers"
+      'ignore'  - instruction does not affect it's operands (e.g. test) or
+                  is used with non-GP registers (X87, MMX, XMM, etc)
+  Internal:
+    index_r8: must not be set by external users (used to create two compressors
+              in 64-bit mode with index == %rax..%rdi or index == %r8..%r14)
+  Returns:
+    None
+  """
+
+  # Expand RR_NOTES section in regex.
+  if options.bitness == 32:
+    base = 'eax'
+    index = 'eax'
+    expanded_regex = re.sub('{RR_NOTES}', '', regex)
+  else:
+    base = 'r8' if '8' in rm or rm == 'mmalt' else 'rax'
+    index = 'r8' if index_r8 else 'rax'
+    input = 'r8d' if index_r8 else 'eax'
+    if register_write == 'sandbox':
+      output_regs = reg if writes_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 opcode_bits should not be used
+  assert reg is None or opcode_bits == 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)

[halyavin, 2013/11/08 15:35:19]

It is better to have context-independent language.

[halyavin, 2013/11/08 15:35:19]

Create a single array and join it via '|'.join(...).

[khim, 2013/11/12 10:14:56]

Not sure why, but this language is removed, we are now processing only one
instruction variant which simplifies logic and makes test 30% faster.

[khim, 2013/11/12 10:14:56]

This logic is also removed

+    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)

[halyavin, 2013/11/08 15:35:19]

It makes sense to extract this template language into separate function.

[khim, 2013/11/12 10:14:56]

Language is removed: we accept all variants here now but since a single
comparison later will reject them difference in speed is negligible.

+  # 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 memory_accessed:
+      input_note = '[%eax..%edi]' if index == 'rax' else '[%r8d..%r15d]'
+    else:
+      input_note = 'any_nonspecial'
+    if register_write == 'sandbox':
+      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, writes_to, opcode_bits, index_r8,
+                memory_accessed, register_write)
+  if output_key in AddModRMCompressor.replacements:
+    replacements = AddModRMCompressor.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:
+      AddModRMCompressor(
+          regex, subst, subst_register, subst_memory,
+          reg=reg, rm=rm, writes_to=writes_to, opcode_bits=opcode_bits,
+          index_r8=True, memory_accessed=memory_accessed,
+          register_write=register_write)
+    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(0xff, -1, -1)
+                  if byte & 0x38 == opcode_bits << 3]
+  else:
+    byte_range = range(0xff, -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 writes_to == 'reg' else reg_text)
+        replacement.append(reg_text if writes_to == 'reg' else rm_text)
+      if options.bitness == 64:
+        replacement.append('any_nonspecial')
+        output = reg_text if writes_to == 'reg' else rm_text
+        replacement.append(output if register_write == 'sandbox' else None)
+        if register_write == 'protect' and output in X86_64_BASE_REGISTERS:
+          continue
+        if register_write == 'sandbox' and output == '%r15d':
+          continue
+        if writes_to == 'both' 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 writes_to == 'reg' else reg_text)
+          replacement.append(reg_text if writes_to == 'reg' else rm_text)
+        if options.bitness == 64:
+          replacement.append('any_nonspecial')
+          output = reg_text if writes_to == 'reg' else None
+          replacement.append(output if register_write == 'sandbox' else None)
+          if memory_accessed and base_text not in X86_64_BASE_REGISTERS:
+            continue
+          if register_write == 'protect' and output in X86_64_BASE_REGISTERS:
+            continue
+          if register_write == 'sandbox' and output == '%r15d':
+            continue
+          if writes_to == 'both' 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(0x100):
+          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 writes_to == 'reg' else reg_text)
+            replacement.append(reg_text if writes_to == 'reg' else rm_text)
+          if options.bitness == 64:
+            if not memory_accessed or index_text == 'any_nonspecial':
+              replacement.append('any_nonspecial')
+            else:
+              replacement.append('%' + REGISTERS[input][index_field])
+            # Currently xchg can not used used for sandboxing
+            output = reg_text if writes_to == 'reg' else None
+            replacement.append(output if register_write == 'sandbox' else None)
+            if memory_accessed:
+              if base_text not in X86_64_BASE_REGISTERS: continue
+              if index_text in X86_64_BASE_REGISTERS - set(['%r15']): continue
+            if register_write == 'protect' and output in X86_64_BASE_REGISTERS:
+              continue
+            if register_write == 'sandbox' and output == '%r15d':
+              continue
+            if (writes_to == 'both' 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)
+  AddModRMCompressor.replacements[output_key] = (
+      main_compressor.replacements,
+      register_compressor.replacements,
+      memory_compressor.replacements
+  )
+  if options.bitness == 64 and not index_r8:
+    AddModRMCompressor(
+        regex, subst, subst_register, subst_memory,
+        reg=reg, rm=rm, writes_to=writes_to, opcode_bits=opcode_bits,
+        index_r8=True, memory_accessed=memory_accessed,
+        register_write=register_write)
+# Replacements cache.
+AddModRMCompressor.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', 'mmalt', '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','mmalt'), ( 'r8d',  'mm0'), ( 'eax', 'mmalt'),
+      ( 'rax',  'mm0'), ( 'rax','mmalt'), (  'r8',  'mm0'), (  'r8', 'mmalt'),
+      ( 'mm0',  'eax'), ('mmalt', 'eax'), ( 'mm0',  'r8d'), ('mmalt',  'r8d'),
+      ( 'mm0',  'rax'), ('mmalt', 'rax'), ( 'mm0',   'r8'), ('mmalt',   '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'), ('mmalt', 'mm0'), ( 'mm0','mmalt'), ('mmalt','mmalt'),
+      ( 'mm0', 'xmm0'), ('mmalt','xmm0'), ( 'mm0', 'xmm8'), ('mmalt', 'xmm8'),
+      ('xmm0',  'mm0'), ('xmm8',  'mm0'), ('xmm0','mmalt'), ('xmm8', 'mmalt'),
+      ('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'):
+        AddModRMCompressor(
+          '.*?' + 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, writes_to='reg', memory_accessed=False,
+          register_write='sandbox' if reg in ('eax', 'r8d') else 'protect')
+      # Normal instructions with two operands (rm to reg).
+      AddModRMCompressor(
+        '.*?' + 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, writes_to='reg')
+      # Normal instructions with two operands (reg to rm).
+      AddModRMCompressor(
+        '.*?' + 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, writes_to='rm')
+      # There are few more forms in 64 bit case (rm to reg).
+      if options.bitness == 64 and reg in ('eax', 'r8d'):
+        # Zero-extending version.
+        AddModRMCompressor(
+          '.*?' + 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, writes_to='reg', register_write='sandbox')
+      # More forms in 64 bit case (reg to rm).
+      if options.bitness == 64 and rm in ('eax', 'r8d'):
+        # Zero-extending version.
+        AddModRMCompressor(
+          '.*?' + 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, writes_to='rm', register_write='sandbox')
+        # Zero-extending xchg/xadd.
+        AddModRMCompressor(
+          '.*?' + 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, writes_to='both', register_write='sandbox')
+      # 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).
+        AddModRMCompressor(
+          '.*?' + 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, writes_to='reg', register_write='protect')
+      # 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).
+        AddModRMCompressor(
+          '.*?' + 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, writes_to='rm', register_write='protect')
+        # Dangerous xchg/xadd.
+        AddModRMCompressor(
+          '.*?' + 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, writes_to='both', register_write='protect')
+    # 3DNow! instructions.  Additional byte is opcode extension.
+    AddModRMCompressor(
+      '.*?' + 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, writes_to='reg')
+
+  # 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_bits in xrange(8):
+      XX_byte_mark = 'XX/' + str(opcode_bits)
+      # 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_bits) + '})'
+      else:
+        bytes = '({RM_SIB_BYTES/' + str(opcode_bits) + '})'
+      if options.bitness == 64:
+        # No memory access (e.g. prefetch)
+        AddModRMCompressor(
+          '.*?' + 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, memory_accessed=False, opcode_bits=opcode_bits)
+      for extra_bytes in ('', ' 00', ' 00 00', ' 00 00 00 00'):
+        # Part of opcode is encoded in ModR/M
+        AddModRMCompressor(
+          '.*?' + 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, opcode_bits=opcode_bits)
+        # More forms in 64 bit case.
+        if options.bitness == 64 and rm in ('eax', 'r8d'):
+          # Zero-extending version.
+          AddModRMCompressor(
+            '.*?' + 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, opcode_bits=opcode_bits, register_write='sandbox')
+        # 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.
+          AddModRMCompressor(
+            '.*?' + 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, opcode_bits=opcode_bits, register_write='protect')
+
+  # 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(
+            '.*?[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(
+            '.*?[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(
+              '.*?[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(
+              '.*?[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(
+      '.*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(
+        '.*(XX/1)  bswap.*ax.*()', ('c[8..f]', ''), [('XX/1', )]))
+  else:
+    compressors.append(Compressor(
+        '.*(XX/1)  bswap.*ax.*()', ('c[89abef]', ''), [('XX/1', )]))
+    compressors.append(Compressor(
+        '.*(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(
+          '.* (?: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(
+        '.*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(0x01, 0x100) 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(
+            '.*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(0x01, 0x100) 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))]))
+
+  # "and $e0" and similar are used to align %rsp.  All negative values are
+  # accepted by validator and there are 127 of these.
+  # Consolidate them into one line.
+  if options.bitness == 64:
+    compressors.append(Compressor(
+        '.*(?:81|83) (?:e4|e5) (80) (?:00 00 00 |) and \\$0x(80),%r[bs]p.*()',
+        ('[80..ff]', '[80..ff]', ' # alignment and'),
+        [('{:02x}'.format(i), '{:02x}'.format(i)) for i in range(0x80, 0x100)]))
+
+  # 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(
+          '.*  \\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(
+                '.*  \\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': 'mmalt',
+      '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(
+                    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(
+        '.*(\\[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
+  format_str = CompressionTemplate(instruction, match, '{{{}}}')
+  replacements = sorted(format_str.format(*replacement)
+                        for replacement in compressor.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,
+                                       compressors,
+                                       ShowProgress)):
+    print instruction
+
+  print >> sys.stderr, total, 'instructions were processed'
+  print >> sys.stderr, num_valid, 'valid instructions'
+
+
+if __name__ == '__main__':
+  main()