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