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