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         global decode_function
 316         return decode_function + '_extract_' + self.name
 317
 318     def output_extract(self):
 319         output('static void ', self.extract_name(), '(',
 320                self.base.struct_name(), ' *a, ', insntype, ' insn)\n{\n')
 321         for n, f in self.fields.items():
 322             output('    a->', n, ' = ', f.str_extract(), ';\n')
 323         output('}\n\n')
 324 # end Format
 325
 326
 327 class Pattern(General):
 328     """Class representing an instruction pattern"""
 329
 330     def output_decl(self):
 331         global translate_scope
 332         global translate_prefix
 333         output('typedef ', self.base.base.struct_name(),
 334                ' arg_', self.name, ';\n')
 335         output(translate_scope, 'bool ', translate_prefix, '_', self.name,
 336                '(DisasContext *ctx, arg_', self.name, ' *a);\n')
 337
 338     def output_code(self, i, extracted, outerbits, outermask):
 339         global translate_prefix
 340         ind = str_indent(i)
 341         arg = self.base.base.name
 342         output(ind, '/* ', self.file, ':', str(self.lineno), ' */\n')
 343         if not extracted:
 344             output(ind, self.base.extract_name(), '(&u.f_', arg, ', insn);\n')
 345         for n, f in self.fields.items():
 346             output(ind, 'u.f_', arg, '.', n, ' = ', f.str_extract(), ';\n')
 347         output(ind, 'if (', translate_prefix, '_', self.name,
 348                '(ctx, &u.f_', arg, ')) return true;\n')
 349 # end Pattern
 350
 351
 352 class MultiPattern(General):
 353     """Class representing an overlapping set of instruction patterns"""
 354
 355     def __init__(self, lineno, pats, fixb, fixm, udfm):
 356         self.file = input_file
 357         self.lineno = lineno
 358         self.pats = pats
 359         self.base = None
 360         self.fixedbits = fixb
 361         self.fixedmask = fixm
 362         self.undefmask = udfm
 363
 364     def __str__(self):
 365         r = "{"
 366         for p in self.pats:
 367            r = r + ' ' + str(p)
 368         return r + "}"
 369
 370     def output_decl(self):
 371         for p in self.pats:
 372             p.output_decl()
 373
 374     def output_code(self, i, extracted, outerbits, outermask):
 375         global translate_prefix
 376         ind = str_indent(i)
 377         for p in self.pats:
 378             if outermask != p.fixedmask:
 379                 innermask = p.fixedmask & ~outermask
 380                 innerbits = p.fixedbits & ~outermask
 381                 output(ind, 'if ((insn & ',
 382                        '0x{0:08x}) == 0x{1:08x}'.format(innermask, innerbits),
 383                        ') {\n')
 384                 output(ind, '    /* ',
 385                        str_match_bits(p.fixedbits, p.fixedmask), ' */\n')
 386                 p.output_code(i + 4, extracted, p.fixedbits, p.fixedmask)
 387                 output(ind, '}\n')
 388             else:
 389                 p.output_code(i, extracted, p.fixedbits, p.fixedmask)
 390 #end MultiPattern
 391
 392
 393 def parse_field(lineno, name, toks):
 394     """Parse one instruction field from TOKS at LINENO"""
 395     global fields
 396     global re_ident
 397     global insnwidth
 398
 399     # A "simple" field will have only one entry;
 400     # a "multifield" will have several.
 401     subs = []
 402     width = 0
 403     func = None
 404     for t in toks:
 405         if re_fullmatch('!function=' + re_ident, t):
 406             if func:
 407                 error(lineno, 'duplicate function')
 408             func = t.split('=')
 409             func = func[1]
 410             continue
 411
 412         if re_fullmatch('[0-9]+:s[0-9]+', t):
 413             # Signed field extract
 414             subtoks = t.split(':s')
 415             sign = True
 416         elif re_fullmatch('[0-9]+:[0-9]+', t):
 417             # Unsigned field extract
 418             subtoks = t.split(':')
 419             sign = False
 420         else:
 421             error(lineno, 'invalid field token "{0}"'.format(t))
 422         po = int(subtoks[0])
 423         le = int(subtoks[1])
 424         if po + le > insnwidth:
 425             error(lineno, 'field {0} too large'.format(t))
 426         f = Field(sign, po, le)
 427         subs.append(f)
 428         width += le
 429
 430     if width > insnwidth:
 431         error(lineno, 'field too large')
 432     if len(subs) == 1:
 433         f = subs[0]
 434     else:
 435         mask = 0
 436         for s in subs:
 437             if mask & s.mask:
 438                 error(lineno, 'field components overlap')
 439             mask |= s.mask
 440         f = MultiField(subs, mask)
 441     if func:
 442         f = FunctionField(func, f)
 443
 444     if name in fields:
 445         error(lineno, 'duplicate field', name)
 446     fields[name] = f
 447 # end parse_field
 448
 449
 450 def parse_arguments(lineno, name, toks):
 451     """Parse one argument set from TOKS at LINENO"""
 452     global arguments
 453     global re_ident
 454
 455     flds = []
 456     extern = False
 457     for t in toks:
 458         if re_fullmatch('!extern', t):
 459             extern = True
 460             continue
 461         if not re_fullmatch(re_ident, t):
 462             error(lineno, 'invalid argument set token "{0}"'.format(t))
 463         if t in flds:
 464             error(lineno, 'duplicate argument "{0}"'.format(t))
 465         flds.append(t)
 466
 467     if name in arguments:
 468         error(lineno, 'duplicate argument set', name)
 469     arguments[name] = Arguments(name, flds, extern)
 470 # end parse_arguments
 471
 472
 473 def lookup_field(lineno, name):
 474     global fields
 475     if name in fields:
 476         return fields[name]
 477     error(lineno, 'undefined field', name)
 478
 479
 480 def add_field(lineno, flds, new_name, f):
 481     if new_name in flds:
 482         error(lineno, 'duplicate field', new_name)
 483     flds[new_name] = f
 484     return flds
 485
 486
 487 def add_field_byname(lineno, flds, new_name, old_name):
 488     return add_field(lineno, flds, new_name, lookup_field(lineno, old_name))
 489
 490
 491 def infer_argument_set(flds):
 492     global arguments
 493     global decode_function
 494
 495     for arg in arguments.values():
 496         if eq_fields_for_args(flds, arg.fields):
 497             return arg
 498
 499     name = decode_function + str(len(arguments))
 500     arg = Arguments(name, flds.keys(), False)
 501     arguments[name] = arg
 502     return arg
 503
 504
 505 def infer_format(arg, fieldmask, flds):
 506     global arguments
 507     global formats
 508     global decode_function
 509
 510     const_flds = {}
 511     var_flds = {}
 512     for n, c in flds.items():
 513         if c is ConstField:
 514             const_flds[n] = c
 515         else:
 516             var_flds[n] = c
 517
 518     # Look for an existing format with the same argument set and fields
 519     for fmt in formats.values():
 520         if arg and fmt.base != arg:
 521             continue
 522         if fieldmask != fmt.fieldmask:
 523             continue
 524         if not eq_fields_for_fmts(flds, fmt.fields):
 525             continue
 526         return (fmt, const_flds)
 527
 528     name = decode_function + '_Fmt_' + str(len(formats))
 529     if not arg:
 530         arg = infer_argument_set(flds)
 531
 532     fmt = Format(name, 0, arg, 0, 0, 0, fieldmask, var_flds)
 533     formats[name] = fmt
 534
 535     return (fmt, const_flds)
 536 # end infer_format
 537
 538
 539 def parse_generic(lineno, is_format, name, toks):
 540     """Parse one instruction format from TOKS at LINENO"""
 541     global fields
 542     global arguments
 543     global formats
 544     global patterns
 545     global allpatterns
 546     global re_ident
 547     global insnwidth
 548     global insnmask
 549
 550     fixedmask = 0
 551     fixedbits = 0
 552     undefmask = 0
 553     width = 0
 554     flds = {}
 555     arg = None
 556     fmt = None
 557     for t in toks:
 558         # '&Foo' gives a format an explcit argument set.
 559         if t[0] == '&':
 560             tt = t[1:]
 561             if arg:
 562                 error(lineno, 'multiple argument sets')
 563             if tt in arguments:
 564                 arg = arguments[tt]
 565             else:
 566                 error(lineno, 'undefined argument set', t)
 567             continue
 568
 569         # '@Foo' gives a pattern an explicit format.
 570         if t[0] == '@':
 571             tt = t[1:]
 572             if fmt:
 573                 error(lineno, 'multiple formats')
 574             if tt in formats:
 575                 fmt = formats[tt]
 576             else:
 577                 error(lineno, 'undefined format', t)
 578             continue
 579
 580         # '%Foo' imports a field.
 581         if t[0] == '%':
 582             tt = t[1:]
 583             flds = add_field_byname(lineno, flds, tt, tt)
 584             continue
 585
 586         # 'Foo=%Bar' imports a field with a different name.
 587         if re_fullmatch(re_ident + '=%' + re_ident, t):
 588             (fname, iname) = t.split('=%')
 589             flds = add_field_byname(lineno, flds, fname, iname)
 590             continue
 591
 592         # 'Foo=number' sets an argument field to a constant value
 593         if re_fullmatch(re_ident + '=[+-]?[0-9]+', t):
 594             (fname, value) = t.split('=')
 595             value = int(value)
 596             flds = add_field(lineno, flds, fname, ConstField(value))
 597             continue
 598
 599         # Pattern of 0s, 1s, dots and dashes indicate required zeros,
 600         # required ones, or dont-cares.
 601         if re_fullmatch('[01.-]+', t):
 602             shift = len(t)
 603             fms = t.replace('0', '1')
 604             fms = fms.replace('.', '0')
 605             fms = fms.replace('-', '0')
 606             fbs = t.replace('.', '0')
 607             fbs = fbs.replace('-', '0')
 608             ubm = t.replace('1', '0')
 609             ubm = ubm.replace('.', '0')
 610             ubm = ubm.replace('-', '1')
 611             fms = int(fms, 2)
 612             fbs = int(fbs, 2)
 613             ubm = int(ubm, 2)
 614             fixedbits = (fixedbits << shift) | fbs
 615             fixedmask = (fixedmask << shift) | fms
 616             undefmask = (undefmask << shift) | ubm
 617         # Otherwise, fieldname:fieldwidth
 618         elif re_fullmatch(re_ident + ':s?[0-9]+', t):
 619             (fname, flen) = t.split(':')
 620             sign = False
 621             if flen[0] == 's':
 622                 sign = True
 623                 flen = flen[1:]
 624             shift = int(flen, 10)
 625             if shift + width > insnwidth:
 626                 error(lineno, 'field {0} exceeds insnwidth'.format(fname))
 627             f = Field(sign, insnwidth - width - shift, shift)
 628             flds = add_field(lineno, flds, fname, f)
 629             fixedbits <<= shift
 630             fixedmask <<= shift
 631             undefmask <<= shift
 632         else:
 633             error(lineno, 'invalid token "{0}"'.format(t))
 634         width += shift
 635
 636     # We should have filled in all of the bits of the instruction.
 637     if not (is_format and width == 0) and width != insnwidth:
 638         error(lineno, 'definition has {0} bits'.format(width))
 639
 640     # Do not check for fields overlaping fields; one valid usage
 641     # is to be able to duplicate fields via import.
 642     fieldmask = 0
 643     for f in flds.values():
 644         fieldmask |= f.mask
 645
 646     # Fix up what we've parsed to match either a format or a pattern.
 647     if is_format:
 648         # Formats cannot reference formats.
 649         if fmt:
 650             error(lineno, 'format referencing format')
 651         # If an argument set is given, then there should be no fields
 652         # without a place to store it.
 653         if arg:
 654             for f in flds.keys():
 655                 if f not in arg.fields:
 656                     error(lineno, 'field {0} not in argument set {1}'
 657                                   .format(f, arg.name))
 658         else:
 659             arg = infer_argument_set(flds)
 660         if name in formats:
 661             error(lineno, 'duplicate format name', name)
 662         fmt = Format(name, lineno, arg, fixedbits, fixedmask,
 663                      undefmask, fieldmask, flds)
 664         formats[name] = fmt
 665     else:
 666         # Patterns can reference a format ...
 667         if fmt:
 668             # ... but not an argument simultaneously
 669             if arg:
 670                 error(lineno, 'pattern specifies both format and argument set')
 671             if fixedmask & fmt.fixedmask:
 672                 error(lineno, 'pattern fixed bits overlap format fixed bits')
 673             fieldmask |= fmt.fieldmask
 674             fixedbits |= fmt.fixedbits
 675             fixedmask |= fmt.fixedmask
 676             undefmask |= fmt.undefmask
 677         else:
 678             (fmt, flds) = infer_format(arg, fieldmask, flds)
 679         arg = fmt.base
 680         for f in flds.keys():
 681             if f not in arg.fields:
 682                 error(lineno, 'field {0} not in argument set {1}'
 683                               .format(f, arg.name))
 684             if f in fmt.fields.keys():
 685                 error(lineno, 'field {0} set by format and pattern'.format(f))
 686         for f in arg.fields:
 687             if f not in flds.keys() and f not in fmt.fields.keys():
 688                 error(lineno, 'field {0} not initialized'.format(f))
 689         pat = Pattern(name, lineno, fmt, fixedbits, fixedmask,
 690                       undefmask, fieldmask, flds)
 691         patterns.append(pat)
 692         allpatterns.append(pat)
 693
 694     # Validate the masks that we have assembled.
 695     if fieldmask & fixedmask:
 696         error(lineno, 'fieldmask overlaps fixedmask (0x{0:08x} & 0x{1:08x})'
 697                       .format(fieldmask, fixedmask))
 698     if fieldmask & undefmask:
 699         error(lineno, 'fieldmask overlaps undefmask (0x{0:08x} & 0x{1:08x})'
 700                       .format(fieldmask, undefmask))
 701     if fixedmask & undefmask:
 702         error(lineno, 'fixedmask overlaps undefmask (0x{0:08x} & 0x{1:08x})'
 703                       .format(fixedmask, undefmask))
 704     if not is_format:
 705         allbits = fieldmask | fixedmask | undefmask
 706         if allbits != insnmask:
 707             error(lineno, 'bits left unspecified (0x{0:08x})'
 708                           .format(allbits ^ insnmask))
 709 # end parse_general
 710
 711 def build_multi_pattern(lineno, pats):
 712     """Validate the Patterns going into a MultiPattern."""
 713     global patterns
 714     global insnmask
 715
 716     if len(pats) < 2:
 717         error(lineno, 'less than two patterns within braces')
 718
 719     fixedmask = insnmask
 720     undefmask = insnmask
 721
 722     # Collect fixed/undefmask for all of the children.
 723     # Move the defining lineno back to that of the first child.
 724     for p in pats:
 725         fixedmask &= p.fixedmask
 726         undefmask &= p.undefmask
 727         if p.lineno < lineno:
 728             lineno = p.lineno
 729
 730     repeat = True
 731     while repeat:
 732         if fixedmask == 0:
 733             error(lineno, 'no overlap in patterns within braces')
 734         fixedbits = None
 735         for p in pats:
 736             thisbits = p.fixedbits & fixedmask
 737             if fixedbits is None:
 738                 fixedbits = thisbits
 739             elif fixedbits != thisbits:
 740                 fixedmask &= ~(fixedbits ^ thisbits)
 741                 break
 742         else:
 743             repeat = False
 744
 745     mp = MultiPattern(lineno, pats, fixedbits, fixedmask, undefmask)
 746     patterns.append(mp)
 747 # end build_multi_pattern
 748
 749 def parse_file(f):
 750     """Parse all of the patterns within a file"""
 751
 752     global patterns
 753
 754     # Read all of the lines of the file.  Concatenate lines
 755     # ending in backslash; discard empty lines and comments.
 756     toks = []
 757     lineno = 0
 758     nesting = 0
 759     saved_pats = []
 760
 761     for line in f:
 762         lineno += 1
 763
 764         # Expand and strip spaces, to find indent.
 765         line = line.rstrip()
 766         line = line.expandtabs()
 767         len1 = len(line)
 768         line = line.lstrip()
 769         len2 = len(line)
 770
 771         # Discard comments
 772         end = line.find('#')
 773         if end >= 0:
 774             line = line[:end]
 775
 776         t = line.split()
 777         if len(toks) != 0:
 778             # Next line after continuation
 779             toks.extend(t)
 780         else:
 781             # Allow completely blank lines.
 782             if len1 == 0:
 783                 continue
 784             indent = len1 - len2
 785             # Empty line due to comment.
 786             if len(t) == 0:
 787                 # Indentation must be correct, even for comment lines.
 788                 if indent != nesting:
 789                     error(lineno, 'indentation ', indent, ' != ', nesting)
 790                 continue
 791             start_lineno = lineno
 792             toks = t
 793
 794         # Continuation?
 795         if toks[-1] == '\\':
 796             toks.pop()
 797             continue
 798
 799         name = toks[0]
 800         del toks[0]
 801
 802         # End nesting?
 803         if name == '}':
 804             if nesting == 0:
 805                 error(start_lineno, 'mismatched close brace')
 806             if len(toks) != 0:
 807                 error(start_lineno, 'extra tokens after close brace')
 808             nesting -= 2
 809             if indent != nesting:
 810                 error(start_lineno, 'indentation ', indent, ' != ', nesting)
 811             pats = patterns
 812             patterns = saved_pats.pop()
 813             build_multi_pattern(lineno, pats)
 814             toks = []
 815             continue
 816
 817         # Everything else should have current indentation.
 818         if indent != nesting:
 819             error(start_lineno, 'indentation ', indent, ' != ', nesting)
 820
 821         # Start nesting?
 822         if name == '{':
 823             if len(toks) != 0:
 824                 error(start_lineno, 'extra tokens after open brace')
 825             saved_pats.append(patterns)
 826             patterns = []
 827             nesting += 2
 828             toks = []
 829             continue
 830
 831         # Determine the type of object needing to be parsed.
 832         if name[0] == '%':
 833             parse_field(start_lineno, name[1:], toks)
 834         elif name[0] == '&':
 835             parse_arguments(start_lineno, name[1:], toks)
 836         elif name[0] == '@':
 837             parse_generic(start_lineno, True, name[1:], toks)
 838         else:
 839             parse_generic(start_lineno, False, name, toks)
 840         toks = []
 841 # end parse_file
 842
 843
 844 class Tree:
 845     """Class representing a node in a decode tree"""
 846
 847     def __init__(self, fm, tm):
 848         self.fixedmask = fm
 849         self.thismask = tm
 850         self.subs = []
 851         self.base = None
 852
 853     def str1(self, i):
 854         ind = str_indent(i)
 855         r = '{0}{1:08x}'.format(ind, self.fixedmask)
 856         if self.format:
 857             r += ' ' + self.format.name
 858         r += ' [\n'
 859         for (b, s) in self.subs:
 860             r += '{0}  {1:08x}:\n'.format(ind, b)
 861             r += s.str1(i + 4) + '\n'
 862         r += ind + ']'
 863         return r
 864
 865     def __str__(self):
 866         return self.str1(0)
 867
 868     def output_code(self, i, extracted, outerbits, outermask):
 869         ind = str_indent(i)
 870
 871         # If we identified all nodes below have the same format,
 872         # extract the fields now.
 873         if not extracted and self.base:
 874             output(ind, self.base.extract_name(),
 875                    '(&u.f_', self.base.base.name, ', insn);\n')
 876             extracted = True
 877
 878         # Attempt to aid the compiler in producing compact switch statements.
 879         # If the bits in the mask are contiguous, extract them.
 880         sh = is_contiguous(self.thismask)
 881         if sh > 0:
 882             # Propagate SH down into the local functions.
 883             def str_switch(b, sh=sh):
 884                 return '(insn >> {0}) & 0x{1:x}'.format(sh, b >> sh)
 885
 886             def str_case(b, sh=sh):
 887                 return '0x{0:x}'.format(b >> sh)
 888         else:
 889             def str_switch(b):
 890                 return 'insn & 0x{0:08x}'.format(b)
 891
 892             def str_case(b):
 893                 return '0x{0:08x}'.format(b)
 894
 895         output(ind, 'switch (', str_switch(self.thismask), ') {\n')
 896         for b, s in sorted(self.subs):
 897             assert (self.thismask & ~s.fixedmask) == 0
 898             innermask = outermask | self.thismask
 899             innerbits = outerbits | b
 900             output(ind, 'case ', str_case(b), ':\n')
 901             output(ind, '    /* ',
 902                    str_match_bits(innerbits, innermask), ' */\n')
 903             s.output_code(i + 4, extracted, innerbits, innermask)
 904             output(ind, '    return false;\n')
 905         output(ind, '}\n')
 906 # end Tree
 907
 908
 909 def build_tree(pats, outerbits, outermask):
 910     # Find the intersection of all remaining fixedmask.
 911     innermask = ~outermask & insnmask
 912     for i in pats:
 913         innermask &= i.fixedmask
 914
 915     if innermask == 0:
 916         text = 'overlapping patterns:'
 917         for p in pats:
 918             text += '\n' + p.file + ':' + str(p.lineno) + ': ' + str(p)
 919         error_with_file(pats[0].file, pats[0].lineno, text)
 920
 921     fullmask = outermask | innermask
 922
 923     # Sort each element of pats into the bin selected by the mask.
 924     bins = {}
 925     for i in pats:
 926         fb = i.fixedbits & innermask
 927         if fb in bins:
 928             bins[fb].append(i)
 929         else:
 930             bins[fb] = [i]
 931
 932     # We must recurse if any bin has more than one element or if
 933     # the single element in the bin has not been fully matched.
 934     t = Tree(fullmask, innermask)
 935
 936     for b, l in bins.items():
 937         s = l[0]
 938         if len(l) > 1 or s.fixedmask & ~fullmask != 0:
 939             s = build_tree(l, b | outerbits, fullmask)
 940         t.subs.append((b, s))
 941
 942     return t
 943 # end build_tree
 944
 945
 946 def prop_format(tree):
 947     """Propagate Format objects into the decode tree"""
 948
 949     # Depth first search.
 950     for (b, s) in tree.subs:
 951         if isinstance(s, Tree):
 952             prop_format(s)
 953
 954     # If all entries in SUBS have the same format, then
 955     # propagate that into the tree.
 956     f = None
 957     for (b, s) in tree.subs:
 958         if f is None:
 959             f = s.base
 960             if f is None:
 961                 return
 962         if f is not s.base:
 963             return
 964     tree.base = f
 965 # end prop_format
 966
 967
 968 def main():
 969     global arguments
 970     global formats
 971     global patterns
 972     global allpatterns
 973     global translate_scope
 974     global translate_prefix
 975     global output_fd
 976     global output_file
 977     global input_file
 978     global insnwidth
 979     global insntype
 980     global insnmask
 981     global decode_function
 982
 983     decode_scope = 'static '
 984
 985     long_opts = ['decode=', 'translate=', 'output=', 'insnwidth=',
 986                  'static-decode=']
 987     try:
 988         (opts, args) = getopt.getopt(sys.argv[1:], 'o:w:', long_opts)
 989     except getopt.GetoptError as err:
 990         error(0, err)
 991     for o, a in opts:
 992         if o in ('-o', '--output'):
 993             output_file = a
 994         elif o == '--decode':
 995             decode_function = a
 996             decode_scope = ''
 997         elif o == '--static-decode':
 998             decode_function = a
 999         elif o == '--translate':
1000             translate_prefix = a
1001             translate_scope = ''
1002         elif o in ('-w', '--insnwidth'):
1003             insnwidth = int(a)
1004             if insnwidth == 16:
1005                 insntype = 'uint16_t'
1006                 insnmask = 0xffff
1007             elif insnwidth != 32:
1008                 error(0, 'cannot handle insns of width', insnwidth)
1009         else:
1010             assert False, 'unhandled option'
1011
1012     if len(args) < 1:
1013         error(0, 'missing input file')
1014     for filename in args:
1015         input_file = filename
1016         f = open(filename, 'r')
1017         parse_file(f)
1018         f.close()
1019
1020     t = build_tree(patterns, 0, 0)
1021     prop_format(t)
1022
1023     if output_file:
1024         output_fd = open(output_file, 'w')
1025     else:
1026         output_fd = sys.stdout
1027
1028     output_autogen()
1029     for n in sorted(arguments.keys()):
1030         f = arguments[n]
1031         f.output_def()
1032
1033     # A single translate function can be invoked for different patterns.
1034     # Make sure that the argument sets are the same, and declare the
1035     # function only once.
1036     out_pats = {}
1037     for i in allpatterns:
1038         if i.name in out_pats:
1039             p = out_pats[i.name]
1040             if i.base.base != p.base.base:
1041                 error(0, i.name, ' has conflicting argument sets')
1042         else:
1043             i.output_decl()
1044             out_pats[i.name] = i
1045     output('\n')
1046
1047     for n in sorted(formats.keys()):
1048         f = formats[n]
1049         f.output_extract()
1050
1051     output(decode_scope, 'bool ', decode_function,
1052            '(DisasContext *ctx, ', insntype, ' insn)\n{\n')
1053
1054     i4 = str_indent(4)
1055
1056     if len(allpatterns) != 0:
1057         output(i4, 'union {\n')
1058         for n in sorted(arguments.keys()):
1059             f = arguments[n]
1060             output(i4, i4, f.struct_name(), ' f_', f.name, ';\n')
1061         output(i4, '} u;\n\n')
1062         t.output_code(4, False, 0, 0)
1063
1064     output(i4, 'return false;\n')
1065     output('}\n')
1066
1067     if output_file:
1068         output_fd.close()
1069 # end main
1070
1071
1072 if __name__ == '__main__':
1073     main()