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