scripts/decodetree.py

   1 #!/usr/bin/env python
   2 # Copyright (c) 2018 Linaro Limited
   3 #
   4 # This library is free software; you can redistribute it and/or
   5 # modify it under the terms of the GNU Lesser General Public
   6 # License as published by the Free Software Foundation; either
   7 # version 2 of the License, or (at your option) any later version.
   8 #
   9 # This library is distributed in the hope that it will be useful,
  10 # but WITHOUT ANY WARRANTY; without even the implied warranty of
  11 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12 # Lesser General Public License for more details.
  13 #
  14 # You should have received a copy of the GNU Lesser General Public
  15 # License along with this library; if not, see <http://www.gnu.org/licenses/>.
  16 #
  17
  18 #
  19 # Generate a decoding tree from a specification file.
  20 # See the syntax and semantics in docs/devel/decodetree.rst.
  21 #
  22
  23 import os
  24 import re
  25 import sys
  26 import getopt
  27
  28 insnwidth = 32
  29 insnmask = 0xffffffff
  30 fields = {}
  31 arguments = {}
  32 formats = {}
  33 patterns = []
  34
  35 translate_prefix = 'trans'
  36 translate_scope = 'static '
  37 input_file = ''
  38 output_file = None
  39 output_fd = None
  40 insntype = 'uint32_t'
  41 decode_function = 'decode'
  42
  43 re_ident = '[a-zA-Z][a-zA-Z0-9_]*'
  44
  45
  46 def error_with_file(file, lineno, *args):
  47     """Print an error message from file:line and args and exit."""
  48     global output_file
  49     global output_fd
  50
  51     if lineno:
  52         r = '{0}:{1}: error:'.format(file, lineno)
  53     elif input_file:
  54         r = '{0}: error:'.format(file)
  55     else:
  56         r = 'error:'
  57     for a in args:
  58         r += ' ' + str(a)
  59     r += '\n'
  60     sys.stderr.write(r)
  61     if output_file and output_fd:
  62         output_fd.close()
  63         os.remove(output_file)
  64     exit(1)
  65
  66 def error(lineno, *args):
  67     error_with_file(input_file, lineno, args)
  68
  69 def output(*args):
  70     global output_fd
  71     for a in args:
  72         output_fd.write(a)
  73
  74
  75 if sys.version_info >= (3, 4):
  76     re_fullmatch = re.fullmatch
  77 else:
  78     def re_fullmatch(pat, str):
  79         return re.match('^' + pat + '$', str)
  80
  81
  82 def output_autogen():
  83     output('/* This file is autogenerated by scripts/decodetree.py.  */\n\n')
  84
  85
  86 def str_indent(c):
  87     """Return a string with C spaces"""
  88     return ' ' * c
  89
  90
  91 def str_fields(fields):
  92     """Return a string uniquely identifing FIELDS"""
  93     r = ''
  94     for n in sorted(fields.keys()):
  95         r += '_' + n
  96     return r[1:]
  97
  98
  99 def str_match_bits(bits, mask):
 100     """Return a string pretty-printing BITS/MASK"""
 101     global insnwidth
 102
 103     i = 1 << (insnwidth - 1)
 104     space = 0x01010100
 105     r = ''
 106     while i != 0:
 107         if i & mask:
 108             if i & bits:
 109                 r += '1'
 110             else:
 111                 r += '0'
 112         else:
 113             r += '.'
 114         if i & space:
 115             r += ' '
 116         i >>= 1
 117     return r
 118
 119
 120 def is_pow2(x):
 121     """Return true iff X is equal to a power of 2."""
 122     return (x & (x - 1)) == 0
 123
 124
 125 def ctz(x):
 126     """Return the number of times 2 factors into X."""
 127     r = 0
 128     while ((x >> r) & 1) == 0:
 129         r += 1
 130     return r
 131
 132
 133 def is_contiguous(bits):
 134     shift = ctz(bits)
 135     if is_pow2((bits >> shift) + 1):
 136         return shift
 137     else:
 138         return -1
 139
 140
 141 def eq_fields_for_args(flds_a, flds_b):
 142     if len(flds_a) != len(flds_b):
 143         return False
 144     for k, a in flds_a.items():
 145         if k not in flds_b:
 146             return False
 147     return True
 148
 149
 150 def eq_fields_for_fmts(flds_a, flds_b):
 151     if len(flds_a) != len(flds_b):
 152         return False
 153     for k, a in flds_a.items():
 154         if k not in flds_b:
 155             return False
 156         b = flds_b[k]
 157         if a.__class__ != b.__class__ or a != b:
 158             return False
 159     return True
 160
 161
 162 class Field:
 163     """Class representing a simple instruction field"""
 164     def __init__(self, sign, pos, len):
 165         self.sign = sign
 166         self.pos = pos
 167         self.len = len
 168         self.mask = ((1 << len) - 1) << pos
 169
 170     def __str__(self):
 171         if self.sign:
 172             s = 's'
 173         else:
 174             s = ''
 175         return str(self.pos) + ':' + s + str(self.len)
 176
 177     def str_extract(self):
 178         if self.sign:
 179             extr = 'sextract32'
 180         else:
 181             extr = 'extract32'
 182         return '{0}(insn, {1}, {2})'.format(extr, self.pos, self.len)
 183
 184     def __eq__(self, other):
 185         return self.sign == other.sign and self.sign == other.sign
 186
 187     def __ne__(self, other):
 188         return not self.__eq__(other)
 189 # end Field
 190
 191
 192 class MultiField:
 193     """Class representing a compound instruction field"""
 194     def __init__(self, subs, mask):
 195         self.subs = subs
 196         self.sign = subs[0].sign
 197         self.mask = mask
 198
 199     def __str__(self):
 200         return str(self.subs)
 201
 202     def str_extract(self):
 203         ret = '0'
 204         pos = 0
 205         for f in reversed(self.subs):
 206             if pos == 0:
 207                 ret = f.str_extract()
 208             else:
 209                 ret = 'deposit32({0}, {1}, {2}, {3})' \
 210                       .format(ret, pos, 32 - pos, f.str_extract())
 211             pos += f.len
 212         return ret
 213
 214     def __ne__(self, other):
 215         if len(self.subs) != len(other.subs):
 216             return True
 217         for a, b in zip(self.subs, other.subs):
 218             if a.__class__ != b.__class__ or a != b:
 219                 return True
 220         return False
 221
 222     def __eq__(self, other):
 223         return not self.__ne__(other)
 224 # end MultiField
 225
 226
 227 class ConstField:
 228     """Class representing an argument field with constant value"""
 229     def __init__(self, value):
 230         self.value = value
 231         self.mask = 0
 232         self.sign = value < 0
 233
 234     def __str__(self):
 235         return str(self.value)
 236
 237     def str_extract(self):
 238         return str(self.value)
 239
 240     def __cmp__(self, other):
 241         return self.value - other.value
 242 # end ConstField
 243
 244
 245 class FunctionField:
 246     """Class representing a field passed through an expander"""
 247     def __init__(self, func, base):
 248         self.mask = base.mask
 249         self.sign = base.sign
 250         self.base = base
 251         self.func = func
 252
 253     def __str__(self):
 254         return self.func + '(' + str(self.base) + ')'
 255
 256     def str_extract(self):
 257         return self.func + '(' + self.base.str_extract() + ')'
 258
 259     def __eq__(self, other):
 260         return self.func == other.func and self.base == other.base
 261
 262     def __ne__(self, other):
 263         return not self.__eq__(other)
 264 # end FunctionField
 265
 266
 267 class Arguments:
 268     """Class representing the extracted fields of a format"""
 269     def __init__(self, nm, flds, extern):
 270         self.name = nm
 271         self.extern = extern
 272         self.fields = sorted(flds)
 273
 274     def __str__(self):
 275         return self.name + ' ' + str(self.fields)
 276
 277     def struct_name(self):
 278         return 'arg_' + self.name
 279
 280     def output_def(self):
 281         if not self.extern:
 282             output('typedef struct {\n')
 283             for n in self.fields:
 284                 output('    int ', n, ';\n')
 285             output('} ', self.struct_name(), ';\n\n')
 286 # end Arguments
 287
 288
 289 class General:
 290     """Common code between instruction formats and instruction patterns"""
 291     def __init__(self, name, lineno, base, fixb, fixm, udfm, fldm, flds):
 292         self.name = name
 293         self.file = input_file
 294         self.lineno = lineno
 295         self.base = base
 296         self.fixedbits = fixb
 297         self.fixedmask = fixm
 298         self.undefmask = udfm
 299         self.fieldmask = fldm
 300         self.fields = flds
 301
 302     def __str__(self):
 303         r = self.name
 304         if self.base:
 305             r = r + ' ' + self.base.name
 306         else:
 307             r = r + ' ' + str(self.fields)
 308         r = r + ' ' + str_match_bits(self.fixedbits, self.fixedmask)
 309         return r
 310
 311     def str1(self, i):
 312         return str_indent(i) + self.__str__()
 313 # end General
 314
 315
 316 class Format(General):
 317     """Class representing an instruction format"""
 318
 319     def extract_name(self):
 320         return 'extract_' + self.name
 321
 322     def output_extract(self):
 323         output('static void ', self.extract_name(), '(',
 324                self.base.struct_name(), ' *a, ', insntype, ' insn)\n{\n')
 325         for n, f in self.fields.items():
 326             output('    a->', n, ' = ', f.str_extract(), ';\n')
 327         output('}\n\n')
 328 # end Format
 329
 330
 331 class Pattern(General):
 332     """Class representing an instruction pattern"""
 333
 334     def output_decl(self):
 335         global translate_scope
 336         global translate_prefix
 337         output('typedef ', self.base.base.struct_name(),
 338                ' arg_', self.name, ';\n')
 339         output(translate_scope, 'bool ', translate_prefix, '_', self.name,
 340                '(DisasContext *ctx, arg_', self.name, ' *a);\n')
 341
 342     def output_code(self, i, extracted, outerbits, outermask):
 343         global translate_prefix
 344         ind = str_indent(i)
 345         arg = self.base.base.name
 346         output(ind, '/* ', self.file, ':', str(self.lineno), ' */\n')
 347         if not extracted:
 348             output(ind, self.base.extract_name(), '(&u.f_', arg, ', insn);\n')
 349         for n, f in self.fields.items():
 350             output(ind, 'u.f_', arg, '.', n, ' = ', f.str_extract(), ';\n')
 351         output(ind, 'return ', translate_prefix, '_', self.name,
 352                '(ctx, &u.f_', arg, ');\n')
 353 # end Pattern
 354
 355
 356 def parse_field(lineno, name, toks):
 357     """Parse one instruction field from TOKS at LINENO"""
 358     global fields
 359     global re_ident
 360     global insnwidth
 361
 362     # A "simple" field will have only one entry;
 363     # a "multifield" will have several.
 364     subs = []
 365     width = 0
 366     func = None
 367     for t in toks:
 368         if re_fullmatch('!function=' + re_ident, t):
 369             if func:
 370                 error(lineno, 'duplicate function')
 371             func = t.split('=')
 372             func = func[1]
 373             continue
 374
 375         if re_fullmatch('[0-9]+:s[0-9]+', t):
 376             # Signed field extract
 377             subtoks = t.split(':s')
 378             sign = True
 379         elif re_fullmatch('[0-9]+:[0-9]+', t):
 380             # Unsigned field extract
 381             subtoks = t.split(':')
 382             sign = False
 383         else:
 384             error(lineno, 'invalid field token "{0}"'.format(t))
 385         po = int(subtoks[0])
 386         le = int(subtoks[1])
 387         if po + le > insnwidth:
 388             error(lineno, 'field {0} too large'.format(t))
 389         f = Field(sign, po, le)
 390         subs.append(f)
 391         width += le
 392
 393     if width > insnwidth:
 394         error(lineno, 'field too large')
 395     if len(subs) == 1:
 396         f = subs[0]
 397     else:
 398         mask = 0
 399         for s in subs:
 400             if mask & s.mask:
 401                 error(lineno, 'field components overlap')
 402             mask |= s.mask
 403         f = MultiField(subs, mask)
 404     if func:
 405         f = FunctionField(func, f)
 406
 407     if name in fields:
 408         error(lineno, 'duplicate field', name)
 409     fields[name] = f
 410 # end parse_field
 411
 412
 413 def parse_arguments(lineno, name, toks):
 414     """Parse one argument set from TOKS at LINENO"""
 415     global arguments
 416     global re_ident
 417
 418     flds = []
 419     extern = False
 420     for t in toks:
 421         if re_fullmatch('!extern', t):
 422             extern = True
 423             continue
 424         if not re_fullmatch(re_ident, t):
 425             error(lineno, 'invalid argument set token "{0}"'.format(t))
 426         if t in flds:
 427             error(lineno, 'duplicate argument "{0}"'.format(t))
 428         flds.append(t)
 429
 430     if name in arguments:
 431         error(lineno, 'duplicate argument set', name)
 432     arguments[name] = Arguments(name, flds, extern)
 433 # end parse_arguments
 434
 435
 436 def lookup_field(lineno, name):
 437     global fields
 438     if name in fields:
 439         return fields[name]
 440     error(lineno, 'undefined field', name)
 441
 442
 443 def add_field(lineno, flds, new_name, f):
 444     if new_name in flds:
 445         error(lineno, 'duplicate field', new_name)
 446     flds[new_name] = f
 447     return flds
 448
 449
 450 def add_field_byname(lineno, flds, new_name, old_name):
 451     return add_field(lineno, flds, new_name, lookup_field(lineno, old_name))
 452
 453
 454 def infer_argument_set(flds):
 455     global arguments
 456     global decode_function
 457
 458     for arg in arguments.values():
 459         if eq_fields_for_args(flds, arg.fields):
 460             return arg
 461
 462     name = decode_function + str(len(arguments))
 463     arg = Arguments(name, flds.keys(), False)
 464     arguments[name] = arg
 465     return arg
 466
 467
 468 def infer_format(arg, fieldmask, flds):
 469     global arguments
 470     global formats
 471     global decode_function
 472
 473     const_flds = {}
 474     var_flds = {}
 475     for n, c in flds.items():
 476         if c is ConstField:
 477             const_flds[n] = c
 478         else:
 479             var_flds[n] = c
 480
 481     # Look for an existing format with the same argument set and fields
 482     for fmt in formats.values():
 483         if arg and fmt.base != arg:
 484             continue
 485         if fieldmask != fmt.fieldmask:
 486             continue
 487         if not eq_fields_for_fmts(flds, fmt.fields):
 488             continue
 489         return (fmt, const_flds)
 490
 491     name = decode_function + '_Fmt_' + str(len(formats))
 492     if not arg:
 493         arg = infer_argument_set(flds)
 494
 495     fmt = Format(name, 0, arg, 0, 0, 0, fieldmask, var_flds)
 496     formats[name] = fmt
 497
 498     return (fmt, const_flds)
 499 # end infer_format
 500
 501
 502 def parse_generic(lineno, is_format, name, toks):
 503     """Parse one instruction format from TOKS at LINENO"""
 504     global fields
 505     global arguments
 506     global formats
 507     global patterns
 508     global re_ident
 509     global insnwidth
 510     global insnmask
 511
 512     fixedmask = 0
 513     fixedbits = 0
 514     undefmask = 0
 515     width = 0
 516     flds = {}
 517     arg = None
 518     fmt = None
 519     for t in toks:
 520         # '&Foo' gives a format an explcit argument set.
 521         if t[0] == '&':
 522             tt = t[1:]
 523             if arg:
 524                 error(lineno, 'multiple argument sets')
 525             if tt in arguments:
 526                 arg = arguments[tt]
 527             else:
 528                 error(lineno, 'undefined argument set', t)
 529             continue
 530
 531         # '@Foo' gives a pattern an explicit format.
 532         if t[0] == '@':
 533             tt = t[1:]
 534             if fmt:
 535                 error(lineno, 'multiple formats')
 536             if tt in formats:
 537                 fmt = formats[tt]
 538             else:
 539                 error(lineno, 'undefined format', t)
 540             continue
 541
 542         # '%Foo' imports a field.
 543         if t[0] == '%':
 544             tt = t[1:]
 545             flds = add_field_byname(lineno, flds, tt, tt)
 546             continue
 547
 548         # 'Foo=%Bar' imports a field with a different name.
 549         if re_fullmatch(re_ident + '=%' + re_ident, t):
 550             (fname, iname) = t.split('=%')
 551             flds = add_field_byname(lineno, flds, fname, iname)
 552             continue
 553
 554         # 'Foo=number' sets an argument field to a constant value
 555         if re_fullmatch(re_ident + '=[0-9]+', t):
 556             (fname, value) = t.split('=')
 557             value = int(value)
 558             flds = add_field(lineno, flds, fname, ConstField(value))
 559             continue
 560
 561         # Pattern of 0s, 1s, dots and dashes indicate required zeros,
 562         # required ones, or dont-cares.
 563         if re_fullmatch('[01.-]+', t):
 564             shift = len(t)
 565             fms = t.replace('0', '1')
 566             fms = fms.replace('.', '0')
 567             fms = fms.replace('-', '0')
 568             fbs = t.replace('.', '0')
 569             fbs = fbs.replace('-', '0')
 570             ubm = t.replace('1', '0')
 571             ubm = ubm.replace('.', '0')
 572             ubm = ubm.replace('-', '1')
 573             fms = int(fms, 2)
 574             fbs = int(fbs, 2)
 575             ubm = int(ubm, 2)
 576             fixedbits = (fixedbits << shift) | fbs
 577             fixedmask = (fixedmask << shift) | fms
 578             undefmask = (undefmask << shift) | ubm
 579         # Otherwise, fieldname:fieldwidth
 580         elif re_fullmatch(re_ident + ':s?[0-9]+', t):
 581             (fname, flen) = t.split(':')
 582             sign = False
 583             if flen[0] == 's':
 584                 sign = True
 585                 flen = flen[1:]
 586             shift = int(flen, 10)
 587             f = Field(sign, insnwidth - width - shift, shift)
 588             flds = add_field(lineno, flds, fname, f)
 589             fixedbits <<= shift
 590             fixedmask <<= shift
 591             undefmask <<= shift
 592         else:
 593             error(lineno, 'invalid token "{0}"'.format(t))
 594         width += shift
 595
 596     # We should have filled in all of the bits of the instruction.
 597     if not (is_format and width == 0) and width != insnwidth:
 598         error(lineno, 'definition has {0} bits'.format(width))
 599
 600     # Do not check for fields overlaping fields; one valid usage
 601     # is to be able to duplicate fields via import.
 602     fieldmask = 0
 603     for f in flds.values():
 604         fieldmask |= f.mask
 605
 606     # Fix up what we've parsed to match either a format or a pattern.
 607     if is_format:
 608         # Formats cannot reference formats.
 609         if fmt:
 610             error(lineno, 'format referencing format')
 611         # If an argument set is given, then there should be no fields
 612         # without a place to store it.
 613         if arg:
 614             for f in flds.keys():
 615                 if f not in arg.fields:
 616                     error(lineno, 'field {0} not in argument set {1}'
 617                                   .format(f, arg.name))
 618         else:
 619             arg = infer_argument_set(flds)
 620         if name in formats:
 621             error(lineno, 'duplicate format name', name)
 622         fmt = Format(name, lineno, arg, fixedbits, fixedmask,
 623                      undefmask, fieldmask, flds)
 624         formats[name] = fmt
 625     else:
 626         # Patterns can reference a format ...
 627         if fmt:
 628             # ... but not an argument simultaneously
 629             if arg:
 630                 error(lineno, 'pattern specifies both format and argument set')
 631             if fixedmask & fmt.fixedmask:
 632                 error(lineno, 'pattern fixed bits overlap format fixed bits')
 633             fieldmask |= fmt.fieldmask
 634             fixedbits |= fmt.fixedbits
 635             fixedmask |= fmt.fixedmask
 636             undefmask |= fmt.undefmask
 637         else:
 638             (fmt, flds) = infer_format(arg, fieldmask, flds)
 639         arg = fmt.base
 640         for f in flds.keys():
 641             if f not in arg.fields:
 642                 error(lineno, 'field {0} not in argument set {1}'
 643                               .format(f, arg.name))
 644             if f in fmt.fields.keys():
 645                 error(lineno, 'field {0} set by format and pattern'.format(f))
 646         for f in arg.fields:
 647             if f not in flds.keys() and f not in fmt.fields.keys():
 648                 error(lineno, 'field {0} not initialized'.format(f))
 649         pat = Pattern(name, lineno, fmt, fixedbits, fixedmask,
 650                       undefmask, fieldmask, flds)
 651         patterns.append(pat)
 652
 653     # Validate the masks that we have assembled.
 654     if fieldmask & fixedmask:
 655         error(lineno, 'fieldmask overlaps fixedmask (0x{0:08x} & 0x{1:08x})'
 656                       .format(fieldmask, fixedmask))
 657     if fieldmask & undefmask:
 658         error(lineno, 'fieldmask overlaps undefmask (0x{0:08x} & 0x{1:08x})'
 659                       .format(fieldmask, undefmask))
 660     if fixedmask & undefmask:
 661         error(lineno, 'fixedmask overlaps undefmask (0x{0:08x} & 0x{1:08x})'
 662                       .format(fixedmask, undefmask))
 663     if not is_format:
 664         allbits = fieldmask | fixedmask | undefmask
 665         if allbits != insnmask:
 666             error(lineno, 'bits left unspecified (0x{0:08x})'
 667                           .format(allbits ^ insnmask))
 668 # end parse_general
 669
 670
 671 def parse_file(f):
 672     """Parse all of the patterns within a file"""
 673
 674     # Read all of the lines of the file.  Concatenate lines
 675     # ending in backslash; discard empty lines and comments.
 676     toks = []
 677     lineno = 0
 678     for line in f:
 679         lineno += 1
 680
 681         # Discard comments
 682         end = line.find('#')
 683         if end >= 0:
 684             line = line[:end]
 685
 686         t = line.split()
 687         if len(toks) != 0:
 688             # Next line after continuation
 689             toks.extend(t)
 690         elif len(t) == 0:
 691             # Empty line
 692             continue
 693         else:
 694             toks = t
 695
 696         # Continuation?
 697         if toks[-1] == '\\':
 698             toks.pop()
 699             continue
 700
 701         if len(toks) < 2:
 702             error(lineno, 'short line')
 703
 704         name = toks[0]
 705         del toks[0]
 706
 707         # Determine the type of object needing to be parsed.
 708         if name[0] == '%':
 709             parse_field(lineno, name[1:], toks)
 710         elif name[0] == '&':
 711             parse_arguments(lineno, name[1:], toks)
 712         elif name[0] == '@':
 713             parse_generic(lineno, True, name[1:], toks)
 714         else:
 715             parse_generic(lineno, False, name, toks)
 716         toks = []
 717 # end parse_file
 718
 719
 720 class Tree:
 721     """Class representing a node in a decode tree"""
 722
 723     def __init__(self, fm, tm):
 724         self.fixedmask = fm
 725         self.thismask = tm
 726         self.subs = []
 727         self.base = None
 728
 729     def str1(self, i):
 730         ind = str_indent(i)
 731         r = '{0}{1:08x}'.format(ind, self.fixedmask)
 732         if self.format:
 733             r += ' ' + self.format.name
 734         r += ' [\n'
 735         for (b, s) in self.subs:
 736             r += '{0}  {1:08x}:\n'.format(ind, b)
 737             r += s.str1(i + 4) + '\n'
 738         r += ind + ']'
 739         return r
 740
 741     def __str__(self):
 742         return self.str1(0)
 743
 744     def output_code(self, i, extracted, outerbits, outermask):
 745         ind = str_indent(i)
 746
 747         # If we identified all nodes below have the same format,
 748         # extract the fields now.
 749         if not extracted and self.base:
 750             output(ind, self.base.extract_name(),
 751                    '(&u.f_', self.base.base.name, ', insn);\n')
 752             extracted = True
 753
 754         # Attempt to aid the compiler in producing compact switch statements.
 755         # If the bits in the mask are contiguous, extract them.
 756         sh = is_contiguous(self.thismask)
 757         if sh > 0:
 758             # Propagate SH down into the local functions.
 759             def str_switch(b, sh=sh):
 760                 return '(insn >> {0}) & 0x{1:x}'.format(sh, b >> sh)
 761
 762             def str_case(b, sh=sh):
 763                 return '0x{0:x}'.format(b >> sh)
 764         else:
 765             def str_switch(b):
 766                 return 'insn & 0x{0:08x}'.format(b)
 767
 768             def str_case(b):
 769                 return '0x{0:08x}'.format(b)
 770
 771         output(ind, 'switch (', str_switch(self.thismask), ') {\n')
 772         for b, s in sorted(self.subs):
 773             assert (self.thismask & ~s.fixedmask) == 0
 774             innermask = outermask | self.thismask
 775             innerbits = outerbits | b
 776             output(ind, 'case ', str_case(b), ':\n')
 777             output(ind, '    /* ',
 778                    str_match_bits(innerbits, innermask), ' */\n')
 779             s.output_code(i + 4, extracted, innerbits, innermask)
 780         output(ind, '}\n')
 781         output(ind, 'return false;\n')
 782 # end Tree
 783
 784
 785 def build_tree(pats, outerbits, outermask):
 786     # Find the intersection of all remaining fixedmask.
 787     innermask = ~outermask & insnmask
 788     for i in pats:
 789         innermask &= i.fixedmask
 790
 791     if innermask == 0:
 792         pnames = []
 793         for p in pats:
 794             pnames.append(p.name + ':' + p.file + ':' + str(p.lineno))
 795         error_with_file(pats[0].file, pats[0].lineno,
 796                         'overlapping patterns:', pnames)
 797
 798     fullmask = outermask | innermask
 799
 800     # Sort each element of pats into the bin selected by the mask.
 801     bins = {}
 802     for i in pats:
 803         fb = i.fixedbits & innermask
 804         if fb in bins:
 805             bins[fb].append(i)
 806         else:
 807             bins[fb] = [i]
 808
 809     # We must recurse if any bin has more than one element or if
 810     # the single element in the bin has not been fully matched.
 811     t = Tree(fullmask, innermask)
 812
 813     for b, l in bins.items():
 814         s = l[0]
 815         if len(l) > 1 or s.fixedmask & ~fullmask != 0:
 816             s = build_tree(l, b | outerbits, fullmask)
 817         t.subs.append((b, s))
 818
 819     return t
 820 # end build_tree
 821
 822
 823 def prop_format(tree):
 824     """Propagate Format objects into the decode tree"""
 825
 826     # Depth first search.
 827     for (b, s) in tree.subs:
 828         if isinstance(s, Tree):
 829             prop_format(s)
 830
 831     # If all entries in SUBS have the same format, then
 832     # propagate that into the tree.
 833     f = None
 834     for (b, s) in tree.subs:
 835         if f is None:
 836             f = s.base
 837             if f is None:
 838                 return
 839         if f is not s.base:
 840             return
 841     tree.base = f
 842 # end prop_format
 843
 844
 845 def main():
 846     global arguments
 847     global formats
 848     global patterns
 849     global translate_scope
 850     global translate_prefix
 851     global output_fd
 852     global output_file
 853     global input_file
 854     global insnwidth
 855     global insntype
 856     global insnmask
 857     global decode_function
 858
 859     decode_scope = 'static '
 860
 861     long_opts = ['decode=', 'translate=', 'output=', 'insnwidth=']
 862     try:
 863         (opts, args) = getopt.getopt(sys.argv[1:], 'o:w:', long_opts)
 864     except getopt.GetoptError as err:
 865         error(0, err)
 866     for o, a in opts:
 867         if o in ('-o', '--output'):
 868             output_file = a
 869         elif o == '--decode':
 870             decode_function = a
 871             decode_scope = ''
 872         elif o == '--translate':
 873             translate_prefix = a
 874             translate_scope = ''
 875         elif o in ('-w', '--insnwidth'):
 876             insnwidth = int(a)
 877             if insnwidth == 16:
 878                 insntype = 'uint16_t'
 879                 insnmask = 0xffff
 880             elif insnwidth != 32:
 881                 error(0, 'cannot handle insns of width', insnwidth)
 882         else:
 883             assert False, 'unhandled option'
 884
 885     if len(args) < 1:
 886         error(0, 'missing input file')
 887     for filename in args:
 888         input_file = filename
 889         f = open(filename, 'r')
 890         parse_file(f)
 891         f.close()
 892
 893     t = build_tree(patterns, 0, 0)
 894     prop_format(t)
 895
 896     if output_file:
 897         output_fd = open(output_file, 'w')
 898     else:
 899         output_fd = sys.stdout
 900
 901     output_autogen()
 902     for n in sorted(arguments.keys()):
 903         f = arguments[n]
 904         f.output_def()
 905
 906     # A single translate function can be invoked for different patterns.
 907     # Make sure that the argument sets are the same, and declare the
 908     # function only once.
 909     out_pats = {}
 910     for i in patterns:
 911         if i.name in out_pats:
 912             p = out_pats[i.name]
 913             if i.base.base != p.base.base:
 914                 error(0, i.name, ' has conflicting argument sets')
 915         else:
 916             i.output_decl()
 917             out_pats[i.name] = i
 918     output('\n')
 919
 920     for n in sorted(formats.keys()):
 921         f = formats[n]
 922         f.output_extract()
 923
 924     output(decode_scope, 'bool ', decode_function,
 925            '(DisasContext *ctx, ', insntype, ' insn)\n{\n')
 926
 927     i4 = str_indent(4)
 928     output(i4, 'union {\n')
 929     for n in sorted(arguments.keys()):
 930         f = arguments[n]
 931         output(i4, i4, f.struct_name(), ' f_', f.name, ';\n')
 932     output(i4, '} u;\n\n')
 933
 934     t.output_code(4, False, 0, 0)
 935
 936     output('}\n')
 937
 938     if output_file:
 939         output_fd.close()
 940 # end main
 941
 942
 943 if __name__ == '__main__':
 944     main()