scripts/decodetree.py

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