scripts/decodetree.py

   1 #!/usr/bin/env python3
   2 # Copyright (c) 2018 Linaro Limited
   3 #
   4 # This library is free software; you can redistribute it and/or
   5 # modify it under the terms of the GNU Lesser General Public
   6 # License as published by the Free Software Foundation; either
   7 # version 2 of the License, or (at your option) any later version.
   8 #
   9 # This library is distributed in the hope that it will be useful,
  10 # but WITHOUT ANY WARRANTY; without even the implied warranty of
  11 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12 # Lesser General Public License for more details.
  13 #
  14 # You should have received a copy of the GNU Lesser General Public
  15 # License along with this library; if not, see <http://www.gnu.org/licenses/>.
  16 #
  17
  18 #
  19 # Generate a decoding tree from a specification file.
  20 # See the syntax and semantics in docs/devel/decodetree.rst.
  21 #
  22
  23 import os
  24 import re
  25 import sys
  26 import getopt
  27
  28 insnwidth = 32
  29 insnmask = 0xffffffff
  30 variablewidth = False
  31 fields = {}
  32 arguments = {}
  33 formats = {}
  34 allpatterns = []
  35 anyextern = False
  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     prefix = ''
  54     if file:
  55         prefix += '{0}:'.format(file)
  56     if lineno:
  57         prefix += '{0}:'.format(lineno)
  58     if prefix:
  59         prefix += ' '
  60     print(prefix, end='error: ', file=sys.stderr)
  61     print(*args, file=sys.stderr)
  62
  63     if output_file and output_fd:
  64         output_fd.close()
  65         os.remove(output_file)
  66     exit(1)
  67 # end error_with_file
  68
  69
  70 def error(lineno, *args):
  71     error_with_file(input_file, lineno, *args)
  72 # end error
  73
  74
  75 def output(*args):
  76     global output_fd
  77     for a in args:
  78         output_fd.write(a)
  79
  80
  81 def output_autogen():
  82     output('/* This file is autogenerated by scripts/decodetree.py.  */\n\n')
  83
  84
  85 def str_indent(c):
  86     """Return a string with C spaces"""
  87     return ' ' * c
  88
  89
  90 def str_fields(fields):
  91     """Return a string uniquely identifing FIELDS"""
  92     r = ''
  93     for n in sorted(fields.keys()):
  94         r += '_' + n
  95     return r[1:]
  96
  97
  98 def str_match_bits(bits, mask):
  99     """Return a string pretty-printing BITS/MASK"""
 100     global insnwidth
 101
 102     i = 1 << (insnwidth - 1)
 103     space = 0x01010100
 104     r = ''
 105     while i != 0:
 106         if i & mask:
 107             if i & bits:
 108                 r += '1'
 109             else:
 110                 r += '0'
 111         else:
 112             r += '.'
 113         if i & space:
 114             r += ' '
 115         i >>= 1
 116     return r
 117
 118
 119 def is_pow2(x):
 120     """Return true iff X is equal to a power of 2."""
 121     return (x & (x - 1)) == 0
 122
 123
 124 def ctz(x):
 125     """Return the number of times 2 factors into X."""
 126     assert x != 0
 127     r = 0
 128     while ((x >> r) & 1) == 0:
 129         r += 1
 130     return r
 131
 132
 133 def is_contiguous(bits):
 134     if bits == 0:
 135         return -1
 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
 374     # Normal patterns do not have children.
 375     def build_tree(self):
 376         return
 377     def prop_masks(self):
 378         return
 379     def prop_format(self):
 380         return
 381     def prop_width(self):
 382         return
 383
 384 # end Pattern
 385
 386
 387 class MultiPattern(General):
 388     """Class representing a set of instruction patterns"""
 389
 390     def __init__(self, lineno):
 391         self.file = input_file
 392         self.lineno = lineno
 393         self.pats = []
 394         self.base = None
 395         self.fixedbits = 0
 396         self.fixedmask = 0
 397         self.undefmask = 0
 398         self.width = None
 399
 400     def __str__(self):
 401         r = 'group'
 402         if self.fixedbits is not None:
 403             r += ' ' + str_match_bits(self.fixedbits, self.fixedmask)
 404         return r
 405
 406     def output_decl(self):
 407         for p in self.pats:
 408             p.output_decl()
 409
 410     def prop_masks(self):
 411         global insnmask
 412
 413         fixedmask = insnmask
 414         undefmask = insnmask
 415
 416         # Collect fixedmask/undefmask for all of the children.
 417         for p in self.pats:
 418             p.prop_masks()
 419             fixedmask &= p.fixedmask
 420             undefmask &= p.undefmask
 421
 422         # Widen fixedmask until all fixedbits match
 423         repeat = True
 424         fixedbits = 0
 425         while repeat and fixedmask != 0:
 426             fixedbits = None
 427             for p in self.pats:
 428                 thisbits = p.fixedbits & fixedmask
 429                 if fixedbits is None:
 430                     fixedbits = thisbits
 431                 elif fixedbits != thisbits:
 432                     fixedmask &= ~(fixedbits ^ thisbits)
 433                     break
 434             else:
 435                 repeat = False
 436
 437         self.fixedbits = fixedbits
 438         self.fixedmask = fixedmask
 439         self.undefmask = undefmask
 440
 441     def build_tree(self):
 442         for p in self.pats:
 443             p.build_tree()
 444
 445     def prop_format(self):
 446         for p in self.pats:
 447             p.build_tree()
 448
 449     def prop_width(self):
 450         width = None
 451         for p in self.pats:
 452             p.prop_width()
 453             if width is None:
 454                 width = p.width
 455             elif width != p.width:
 456                 error_with_file(self.file, self.lineno,
 457                                 'width mismatch in patterns within braces')
 458         self.width = width
 459
 460 # end MultiPattern
 461
 462
 463 class IncMultiPattern(MultiPattern):
 464     """Class representing an overlapping set of instruction patterns"""
 465
 466     def output_code(self, i, extracted, outerbits, outermask):
 467         global translate_prefix
 468         ind = str_indent(i)
 469         for p in self.pats:
 470             if outermask != p.fixedmask:
 471                 innermask = p.fixedmask & ~outermask
 472                 innerbits = p.fixedbits & ~outermask
 473                 output(ind, 'if ((insn & ',
 474                        '0x{0:08x}) == 0x{1:08x}'.format(innermask, innerbits),
 475                        ') {\n')
 476                 output(ind, '    /* ',
 477                        str_match_bits(p.fixedbits, p.fixedmask), ' */\n')
 478                 p.output_code(i + 4, extracted, p.fixedbits, p.fixedmask)
 479                 output(ind, '}\n')
 480             else:
 481                 p.output_code(i, extracted, p.fixedbits, p.fixedmask)
 482 #end IncMultiPattern
 483
 484
 485 class Tree:
 486     """Class representing a node in a decode tree"""
 487
 488     def __init__(self, fm, tm):
 489         self.fixedmask = fm
 490         self.thismask = tm
 491         self.subs = []
 492         self.base = None
 493
 494     def str1(self, i):
 495         ind = str_indent(i)
 496         r = '{0}{1:08x}'.format(ind, self.fixedmask)
 497         if self.format:
 498             r += ' ' + self.format.name
 499         r += ' [\n'
 500         for (b, s) in self.subs:
 501             r += '{0}  {1:08x}:\n'.format(ind, b)
 502             r += s.str1(i + 4) + '\n'
 503         r += ind + ']'
 504         return r
 505
 506     def __str__(self):
 507         return self.str1(0)
 508
 509     def output_code(self, i, extracted, outerbits, outermask):
 510         ind = str_indent(i)
 511
 512         # If we identified all nodes below have the same format,
 513         # extract the fields now.
 514         if not extracted and self.base:
 515             output(ind, self.base.extract_name(),
 516                    '(ctx, &u.f_', self.base.base.name, ', insn);\n')
 517             extracted = True
 518
 519         # Attempt to aid the compiler in producing compact switch statements.
 520         # If the bits in the mask are contiguous, extract them.
 521         sh = is_contiguous(self.thismask)
 522         if sh > 0:
 523             # Propagate SH down into the local functions.
 524             def str_switch(b, sh=sh):
 525                 return '(insn >> {0}) & 0x{1:x}'.format(sh, b >> sh)
 526
 527             def str_case(b, sh=sh):
 528                 return '0x{0:x}'.format(b >> sh)
 529         else:
 530             def str_switch(b):
 531                 return 'insn & 0x{0:08x}'.format(b)
 532
 533             def str_case(b):
 534                 return '0x{0:08x}'.format(b)
 535
 536         output(ind, 'switch (', str_switch(self.thismask), ') {\n')
 537         for b, s in sorted(self.subs):
 538             assert (self.thismask & ~s.fixedmask) == 0
 539             innermask = outermask | self.thismask
 540             innerbits = outerbits | b
 541             output(ind, 'case ', str_case(b), ':\n')
 542             output(ind, '    /* ',
 543                    str_match_bits(innerbits, innermask), ' */\n')
 544             s.output_code(i + 4, extracted, innerbits, innermask)
 545             output(ind, '    return false;\n')
 546         output(ind, '}\n')
 547 # end Tree
 548
 549
 550 class ExcMultiPattern(MultiPattern):
 551     """Class representing a non-overlapping set of instruction patterns"""
 552
 553     def output_code(self, i, extracted, outerbits, outermask):
 554         # Defer everything to our decomposed Tree node
 555         self.tree.output_code(i, extracted, outerbits, outermask)
 556
 557     @staticmethod
 558     def __build_tree(pats, outerbits, outermask):
 559         # Find the intersection of all remaining fixedmask.
 560         innermask = ~outermask & insnmask
 561         for i in pats:
 562             innermask &= i.fixedmask
 563
 564         if innermask == 0:
 565             # Edge condition: One pattern covers the entire insnmask
 566             if len(pats) == 1:
 567                 t = Tree(outermask, innermask)
 568                 t.subs.append((0, pats[0]))
 569                 return t
 570
 571             text = 'overlapping patterns:'
 572             for p in pats:
 573                 text += '\n' + p.file + ':' + str(p.lineno) + ': ' + str(p)
 574             error_with_file(pats[0].file, pats[0].lineno, text)
 575
 576         fullmask = outermask | innermask
 577
 578         # Sort each element of pats into the bin selected by the mask.
 579         bins = {}
 580         for i in pats:
 581             fb = i.fixedbits & innermask
 582             if fb in bins:
 583                 bins[fb].append(i)
 584             else:
 585                 bins[fb] = [i]
 586
 587         # We must recurse if any bin has more than one element or if
 588         # the single element in the bin has not been fully matched.
 589         t = Tree(fullmask, innermask)
 590
 591         for b, l in bins.items():
 592             s = l[0]
 593             if len(l) > 1 or s.fixedmask & ~fullmask != 0:
 594                 s = ExcMultiPattern.__build_tree(l, b | outerbits, fullmask)
 595             t.subs.append((b, s))
 596
 597         return t
 598
 599     def build_tree(self):
 600         super().prop_format()
 601         self.tree = self.__build_tree(self.pats, self.fixedbits,
 602                                       self.fixedmask)
 603
 604     @staticmethod
 605     def __prop_format(tree):
 606         """Propagate Format objects into the decode tree"""
 607
 608         # Depth first search.
 609         for (b, s) in tree.subs:
 610             if isinstance(s, Tree):
 611                 ExcMultiPattern.__prop_format(s)
 612
 613         # If all entries in SUBS have the same format, then
 614         # propagate that into the tree.
 615         f = None
 616         for (b, s) in tree.subs:
 617             if f is None:
 618                 f = s.base
 619                 if f is None:
 620                     return
 621             if f is not s.base:
 622                 return
 623         tree.base = f
 624
 625     def prop_format(self):
 626         super().prop_format()
 627         self.__prop_format(self.tree)
 628
 629 # end ExcMultiPattern
 630
 631
 632 def parse_field(lineno, name, toks):
 633     """Parse one instruction field from TOKS at LINENO"""
 634     global fields
 635     global re_ident
 636     global insnwidth
 637
 638     # A "simple" field will have only one entry;
 639     # a "multifield" will have several.
 640     subs = []
 641     width = 0
 642     func = None
 643     for t in toks:
 644         if re.fullmatch('!function=' + re_ident, t):
 645             if func:
 646                 error(lineno, 'duplicate function')
 647             func = t.split('=')
 648             func = func[1]
 649             continue
 650
 651         if re.fullmatch('[0-9]+:s[0-9]+', t):
 652             # Signed field extract
 653             subtoks = t.split(':s')
 654             sign = True
 655         elif re.fullmatch('[0-9]+:[0-9]+', t):
 656             # Unsigned field extract
 657             subtoks = t.split(':')
 658             sign = False
 659         else:
 660             error(lineno, 'invalid field token "{0}"'.format(t))
 661         po = int(subtoks[0])
 662         le = int(subtoks[1])
 663         if po + le > insnwidth:
 664             error(lineno, 'field {0} too large'.format(t))
 665         f = Field(sign, po, le)
 666         subs.append(f)
 667         width += le
 668
 669     if width > insnwidth:
 670         error(lineno, 'field too large')
 671     if len(subs) == 0:
 672         if func:
 673             f = ParameterField(func)
 674         else:
 675             error(lineno, 'field with no value')
 676     else:
 677         if len(subs) == 1:
 678             f = subs[0]
 679         else:
 680             mask = 0
 681             for s in subs:
 682                 if mask & s.mask:
 683                     error(lineno, 'field components overlap')
 684                 mask |= s.mask
 685             f = MultiField(subs, mask)
 686         if func:
 687             f = FunctionField(func, f)
 688
 689     if name in fields:
 690         error(lineno, 'duplicate field', name)
 691     fields[name] = f
 692 # end parse_field
 693
 694
 695 def parse_arguments(lineno, name, toks):
 696     """Parse one argument set from TOKS at LINENO"""
 697     global arguments
 698     global re_ident
 699     global anyextern
 700
 701     flds = []
 702     extern = False
 703     for t in toks:
 704         if re.fullmatch('!extern', t):
 705             extern = True
 706             anyextern = True
 707             continue
 708         if not re.fullmatch(re_ident, t):
 709             error(lineno, 'invalid argument set token "{0}"'.format(t))
 710         if t in flds:
 711             error(lineno, 'duplicate argument "{0}"'.format(t))
 712         flds.append(t)
 713
 714     if name in arguments:
 715         error(lineno, 'duplicate argument set', name)
 716     arguments[name] = Arguments(name, flds, extern)
 717 # end parse_arguments
 718
 719
 720 def lookup_field(lineno, name):
 721     global fields
 722     if name in fields:
 723         return fields[name]
 724     error(lineno, 'undefined field', name)
 725
 726
 727 def add_field(lineno, flds, new_name, f):
 728     if new_name in flds:
 729         error(lineno, 'duplicate field', new_name)
 730     flds[new_name] = f
 731     return flds
 732
 733
 734 def add_field_byname(lineno, flds, new_name, old_name):
 735     return add_field(lineno, flds, new_name, lookup_field(lineno, old_name))
 736
 737
 738 def infer_argument_set(flds):
 739     global arguments
 740     global decode_function
 741
 742     for arg in arguments.values():
 743         if eq_fields_for_args(flds, arg.fields):
 744             return arg
 745
 746     name = decode_function + str(len(arguments))
 747     arg = Arguments(name, flds.keys(), False)
 748     arguments[name] = arg
 749     return arg
 750
 751
 752 def infer_format(arg, fieldmask, flds, width):
 753     global arguments
 754     global formats
 755     global decode_function
 756
 757     const_flds = {}
 758     var_flds = {}
 759     for n, c in flds.items():
 760         if c is ConstField:
 761             const_flds[n] = c
 762         else:
 763             var_flds[n] = c
 764
 765     # Look for an existing format with the same argument set and fields
 766     for fmt in formats.values():
 767         if arg and fmt.base != arg:
 768             continue
 769         if fieldmask != fmt.fieldmask:
 770             continue
 771         if width != fmt.width:
 772             continue
 773         if not eq_fields_for_fmts(flds, fmt.fields):
 774             continue
 775         return (fmt, const_flds)
 776
 777     name = decode_function + '_Fmt_' + str(len(formats))
 778     if not arg:
 779         arg = infer_argument_set(flds)
 780
 781     fmt = Format(name, 0, arg, 0, 0, 0, fieldmask, var_flds, width)
 782     formats[name] = fmt
 783
 784     return (fmt, const_flds)
 785 # end infer_format
 786
 787
 788 def parse_generic(lineno, parent_pat, name, toks):
 789     """Parse one instruction format from TOKS at LINENO"""
 790     global fields
 791     global arguments
 792     global formats
 793     global allpatterns
 794     global re_ident
 795     global insnwidth
 796     global insnmask
 797     global variablewidth
 798
 799     is_format = parent_pat is None
 800
 801     fixedmask = 0
 802     fixedbits = 0
 803     undefmask = 0
 804     width = 0
 805     flds = {}
 806     arg = None
 807     fmt = None
 808     for t in toks:
 809         # '&Foo' gives a format an explcit argument set.
 810         if t[0] == '&':
 811             tt = t[1:]
 812             if arg:
 813                 error(lineno, 'multiple argument sets')
 814             if tt in arguments:
 815                 arg = arguments[tt]
 816             else:
 817                 error(lineno, 'undefined argument set', t)
 818             continue
 819
 820         # '@Foo' gives a pattern an explicit format.
 821         if t[0] == '@':
 822             tt = t[1:]
 823             if fmt:
 824                 error(lineno, 'multiple formats')
 825             if tt in formats:
 826                 fmt = formats[tt]
 827             else:
 828                 error(lineno, 'undefined format', t)
 829             continue
 830
 831         # '%Foo' imports a field.
 832         if t[0] == '%':
 833             tt = t[1:]
 834             flds = add_field_byname(lineno, flds, tt, tt)
 835             continue
 836
 837         # 'Foo=%Bar' imports a field with a different name.
 838         if re.fullmatch(re_ident + '=%' + re_ident, t):
 839             (fname, iname) = t.split('=%')
 840             flds = add_field_byname(lineno, flds, fname, iname)
 841             continue
 842
 843         # 'Foo=number' sets an argument field to a constant value
 844         if re.fullmatch(re_ident + '=[+-]?[0-9]+', t):
 845             (fname, value) = t.split('=')
 846             value = int(value)
 847             flds = add_field(lineno, flds, fname, ConstField(value))
 848             continue
 849
 850         # Pattern of 0s, 1s, dots and dashes indicate required zeros,
 851         # required ones, or dont-cares.
 852         if re.fullmatch('[01.-]+', t):
 853             shift = len(t)
 854             fms = t.replace('0', '1')
 855             fms = fms.replace('.', '0')
 856             fms = fms.replace('-', '0')
 857             fbs = t.replace('.', '0')
 858             fbs = fbs.replace('-', '0')
 859             ubm = t.replace('1', '0')
 860             ubm = ubm.replace('.', '0')
 861             ubm = ubm.replace('-', '1')
 862             fms = int(fms, 2)
 863             fbs = int(fbs, 2)
 864             ubm = int(ubm, 2)
 865             fixedbits = (fixedbits << shift) | fbs
 866             fixedmask = (fixedmask << shift) | fms
 867             undefmask = (undefmask << shift) | ubm
 868         # Otherwise, fieldname:fieldwidth
 869         elif re.fullmatch(re_ident + ':s?[0-9]+', t):
 870             (fname, flen) = t.split(':')
 871             sign = False
 872             if flen[0] == 's':
 873                 sign = True
 874                 flen = flen[1:]
 875             shift = int(flen, 10)
 876             if shift + width > insnwidth:
 877                 error(lineno, 'field {0} exceeds insnwidth'.format(fname))
 878             f = Field(sign, insnwidth - width - shift, shift)
 879             flds = add_field(lineno, flds, fname, f)
 880             fixedbits <<= shift
 881             fixedmask <<= shift
 882             undefmask <<= shift
 883         else:
 884             error(lineno, 'invalid token "{0}"'.format(t))
 885         width += shift
 886
 887     if variablewidth and width < insnwidth and width % 8 == 0:
 888         shift = insnwidth - width
 889         fixedbits <<= shift
 890         fixedmask <<= shift
 891         undefmask <<= shift
 892         undefmask |= (1 << shift) - 1
 893
 894     # We should have filled in all of the bits of the instruction.
 895     elif not (is_format and width == 0) and width != insnwidth:
 896         error(lineno, 'definition has {0} bits'.format(width))
 897
 898     # Do not check for fields overlaping fields; one valid usage
 899     # is to be able to duplicate fields via import.
 900     fieldmask = 0
 901     for f in flds.values():
 902         fieldmask |= f.mask
 903
 904     # Fix up what we've parsed to match either a format or a pattern.
 905     if is_format:
 906         # Formats cannot reference formats.
 907         if fmt:
 908             error(lineno, 'format referencing format')
 909         # If an argument set is given, then there should be no fields
 910         # without a place to store it.
 911         if arg:
 912             for f in flds.keys():
 913                 if f not in arg.fields:
 914                     error(lineno, 'field {0} not in argument set {1}'
 915                                   .format(f, arg.name))
 916         else:
 917             arg = infer_argument_set(flds)
 918         if name in formats:
 919             error(lineno, 'duplicate format name', name)
 920         fmt = Format(name, lineno, arg, fixedbits, fixedmask,
 921                      undefmask, fieldmask, flds, width)
 922         formats[name] = fmt
 923     else:
 924         # Patterns can reference a format ...
 925         if fmt:
 926             # ... but not an argument simultaneously
 927             if arg:
 928                 error(lineno, 'pattern specifies both format and argument set')
 929             if fixedmask & fmt.fixedmask:
 930                 error(lineno, 'pattern fixed bits overlap format fixed bits')
 931             if width != fmt.width:
 932                 error(lineno, 'pattern uses format of different width')
 933             fieldmask |= fmt.fieldmask
 934             fixedbits |= fmt.fixedbits
 935             fixedmask |= fmt.fixedmask
 936             undefmask |= fmt.undefmask
 937         else:
 938             (fmt, flds) = infer_format(arg, fieldmask, flds, width)
 939         arg = fmt.base
 940         for f in flds.keys():
 941             if f not in arg.fields:
 942                 error(lineno, 'field {0} not in argument set {1}'
 943                               .format(f, arg.name))
 944             if f in fmt.fields.keys():
 945                 error(lineno, 'field {0} set by format and pattern'.format(f))
 946         for f in arg.fields:
 947             if f not in flds.keys() and f not in fmt.fields.keys():
 948                 error(lineno, 'field {0} not initialized'.format(f))
 949         pat = Pattern(name, lineno, fmt, fixedbits, fixedmask,
 950                       undefmask, fieldmask, flds, width)
 951         parent_pat.pats.append(pat)
 952         allpatterns.append(pat)
 953
 954     # Validate the masks that we have assembled.
 955     if fieldmask & fixedmask:
 956         error(lineno, 'fieldmask overlaps fixedmask (0x{0:08x} & 0x{1:08x})'
 957                       .format(fieldmask, fixedmask))
 958     if fieldmask & undefmask:
 959         error(lineno, 'fieldmask overlaps undefmask (0x{0:08x} & 0x{1:08x})'
 960                       .format(fieldmask, undefmask))
 961     if fixedmask & undefmask:
 962         error(lineno, 'fixedmask overlaps undefmask (0x{0:08x} & 0x{1:08x})'
 963                       .format(fixedmask, undefmask))
 964     if not is_format:
 965         allbits = fieldmask | fixedmask | undefmask
 966         if allbits != insnmask:
 967             error(lineno, 'bits left unspecified (0x{0:08x})'
 968                           .format(allbits ^ insnmask))
 969 # end parse_general
 970
 971
 972 def parse_file(f, parent_pat):
 973     """Parse all of the patterns within a file"""
 974
 975     # Read all of the lines of the file.  Concatenate lines
 976     # ending in backslash; discard empty lines and comments.
 977     toks = []
 978     lineno = 0
 979     nesting = 0
 980     nesting_pats = []
 981
 982     for line in f:
 983         lineno += 1
 984
 985         # Expand and strip spaces, to find indent.
 986         line = line.rstrip()
 987         line = line.expandtabs()
 988         len1 = len(line)
 989         line = line.lstrip()
 990         len2 = len(line)
 991
 992         # Discard comments
 993         end = line.find('#')
 994         if end >= 0:
 995             line = line[:end]
 996
 997         t = line.split()
 998         if len(toks) != 0:
 999             # Next line after continuation
1000             toks.extend(t)
1001         else:
1002             # Allow completely blank lines.
1003             if len1 == 0:
1004                 continue
1005             indent = len1 - len2
1006             # Empty line due to comment.
1007             if len(t) == 0:
1008                 # Indentation must be correct, even for comment lines.
1009                 if indent != nesting:
1010                     error(lineno, 'indentation ', indent, ' != ', nesting)
1011                 continue
1012             start_lineno = lineno
1013             toks = t
1014
1015         # Continuation?
1016         if toks[-1] == '\\':
1017             toks.pop()
1018             continue
1019
1020         name = toks[0]
1021         del toks[0]
1022
1023         # End nesting?
1024         if name == '}' or name == ']':
1025             if len(toks) != 0:
1026                 error(start_lineno, 'extra tokens after close brace')
1027
1028             # Make sure { } and [ ] nest properly.
1029             if (name == '}') != isinstance(parent_pat, IncMultiPattern):
1030                 error(lineno, 'mismatched close brace')
1031
1032             try:
1033                 parent_pat = nesting_pats.pop()
1034             except:
1035                 error(lineno, 'extra close brace')
1036
1037             nesting -= 2
1038             if indent != nesting:
1039                 error(lineno, 'indentation ', indent, ' != ', nesting)
1040
1041             toks = []
1042             continue
1043
1044         # Everything else should have current indentation.
1045         if indent != nesting:
1046             error(start_lineno, 'indentation ', indent, ' != ', nesting)
1047
1048         # Start nesting?
1049         if name == '{' or name == '[':
1050             if len(toks) != 0:
1051                 error(start_lineno, 'extra tokens after open brace')
1052
1053             if name == '{':
1054                 nested_pat = IncMultiPattern(start_lineno)
1055             else:
1056                 nested_pat = ExcMultiPattern(start_lineno)
1057             parent_pat.pats.append(nested_pat)
1058             nesting_pats.append(parent_pat)
1059             parent_pat = nested_pat
1060
1061             nesting += 2
1062             toks = []
1063             continue
1064
1065         # Determine the type of object needing to be parsed.
1066         if name[0] == '%':
1067             parse_field(start_lineno, name[1:], toks)
1068         elif name[0] == '&':
1069             parse_arguments(start_lineno, name[1:], toks)
1070         elif name[0] == '@':
1071             parse_generic(start_lineno, None, name[1:], toks)
1072         else:
1073             parse_generic(start_lineno, parent_pat, name, toks)
1074         toks = []
1075
1076     if nesting != 0:
1077         error(lineno, 'missing close brace')
1078 # end parse_file
1079
1080
1081 class SizeTree:
1082     """Class representing a node in a size decode tree"""
1083
1084     def __init__(self, m, w):
1085         self.mask = m
1086         self.subs = []
1087         self.base = None
1088         self.width = w
1089
1090     def str1(self, i):
1091         ind = str_indent(i)
1092         r = '{0}{1:08x}'.format(ind, self.mask)
1093         r += ' [\n'
1094         for (b, s) in self.subs:
1095             r += '{0}  {1:08x}:\n'.format(ind, b)
1096             r += s.str1(i + 4) + '\n'
1097         r += ind + ']'
1098         return r
1099
1100     def __str__(self):
1101         return self.str1(0)
1102
1103     def output_code(self, i, extracted, outerbits, outermask):
1104         ind = str_indent(i)
1105
1106         # If we need to load more bytes to test, do so now.
1107         if extracted < self.width:
1108             output(ind, 'insn = ', decode_function,
1109                    '_load_bytes(ctx, insn, {0}, {1});\n'
1110                    .format(extracted // 8, self.width // 8));
1111             extracted = self.width
1112
1113         # Attempt to aid the compiler in producing compact switch statements.
1114         # If the bits in the mask are contiguous, extract them.
1115         sh = is_contiguous(self.mask)
1116         if sh > 0:
1117             # Propagate SH down into the local functions.
1118             def str_switch(b, sh=sh):
1119                 return '(insn >> {0}) & 0x{1:x}'.format(sh, b >> sh)
1120
1121             def str_case(b, sh=sh):
1122                 return '0x{0:x}'.format(b >> sh)
1123         else:
1124             def str_switch(b):
1125                 return 'insn & 0x{0:08x}'.format(b)
1126
1127             def str_case(b):
1128                 return '0x{0:08x}'.format(b)
1129
1130         output(ind, 'switch (', str_switch(self.mask), ') {\n')
1131         for b, s in sorted(self.subs):
1132             innermask = outermask | self.mask
1133             innerbits = outerbits | b
1134             output(ind, 'case ', str_case(b), ':\n')
1135             output(ind, '    /* ',
1136                    str_match_bits(innerbits, innermask), ' */\n')
1137             s.output_code(i + 4, extracted, innerbits, innermask)
1138         output(ind, '}\n')
1139         output(ind, 'return insn;\n')
1140 # end SizeTree
1141
1142 class SizeLeaf:
1143     """Class representing a leaf node in a size decode tree"""
1144
1145     def __init__(self, m, w):
1146         self.mask = m
1147         self.width = w
1148
1149     def str1(self, i):
1150         ind = str_indent(i)
1151         return '{0}{1:08x}'.format(ind, self.mask)
1152
1153     def __str__(self):
1154         return self.str1(0)
1155
1156     def output_code(self, i, extracted, outerbits, outermask):
1157         global decode_function
1158         ind = str_indent(i)
1159
1160         # If we need to load more bytes, do so now.
1161         if extracted < self.width:
1162             output(ind, 'insn = ', decode_function,
1163                    '_load_bytes(ctx, insn, {0}, {1});\n'
1164                    .format(extracted // 8, self.width // 8));
1165             extracted = self.width
1166         output(ind, 'return insn;\n')
1167 # end SizeLeaf
1168
1169
1170 def build_size_tree(pats, width, outerbits, outermask):
1171     global insnwidth
1172
1173     # Collect the mask of bits that are fixed in this width
1174     innermask = 0xff << (insnwidth - width)
1175     innermask &= ~outermask
1176     minwidth = None
1177     onewidth = True
1178     for i in pats:
1179         innermask &= i.fixedmask
1180         if minwidth is None:
1181             minwidth = i.width
1182         elif minwidth != i.width:
1183             onewidth = False;
1184             if minwidth < i.width:
1185                 minwidth = i.width
1186
1187     if onewidth:
1188         return SizeLeaf(innermask, minwidth)
1189
1190     if innermask == 0:
1191         if width < minwidth:
1192             return build_size_tree(pats, width + 8, outerbits, outermask)
1193
1194         pnames = []
1195         for p in pats:
1196             pnames.append(p.name + ':' + p.file + ':' + str(p.lineno))
1197         error_with_file(pats[0].file, pats[0].lineno,
1198                         'overlapping patterns size {0}:'.format(width), pnames)
1199
1200     bins = {}
1201     for i in pats:
1202         fb = i.fixedbits & innermask
1203         if fb in bins:
1204             bins[fb].append(i)
1205         else:
1206             bins[fb] = [i]
1207
1208     fullmask = outermask | innermask
1209     lens = sorted(bins.keys())
1210     if len(lens) == 1:
1211         b = lens[0]
1212         return build_size_tree(bins[b], width + 8, b | outerbits, fullmask)
1213
1214     r = SizeTree(innermask, width)
1215     for b, l in bins.items():
1216         s = build_size_tree(l, width, b | outerbits, fullmask)
1217         r.subs.append((b, s))
1218     return r
1219 # end build_size_tree
1220
1221
1222 def prop_size(tree):
1223     """Propagate minimum widths up the decode size tree"""
1224
1225     if isinstance(tree, SizeTree):
1226         min = None
1227         for (b, s) in tree.subs:
1228             width = prop_size(s)
1229             if min is None or min > width:
1230                 min = width
1231         assert min >= tree.width
1232         tree.width = min
1233     else:
1234         min = tree.width
1235     return min
1236 # end prop_size
1237
1238
1239 def main():
1240     global arguments
1241     global formats
1242     global allpatterns
1243     global translate_scope
1244     global translate_prefix
1245     global output_fd
1246     global output_file
1247     global input_file
1248     global insnwidth
1249     global insntype
1250     global insnmask
1251     global decode_function
1252     global variablewidth
1253     global anyextern
1254
1255     decode_scope = 'static '
1256
1257     long_opts = ['decode=', 'translate=', 'output=', 'insnwidth=',
1258                  'static-decode=', 'varinsnwidth=']
1259     try:
1260         (opts, args) = getopt.getopt(sys.argv[1:], 'o:vw:', long_opts)
1261     except getopt.GetoptError as err:
1262         error(0, err)
1263     for o, a in opts:
1264         if o in ('-o', '--output'):
1265             output_file = a
1266         elif o == '--decode':
1267             decode_function = a
1268             decode_scope = ''
1269         elif o == '--static-decode':
1270             decode_function = a
1271         elif o == '--translate':
1272             translate_prefix = a
1273             translate_scope = ''
1274         elif o in ('-w', '--insnwidth', '--varinsnwidth'):
1275             if o == '--varinsnwidth':
1276                 variablewidth = True
1277             insnwidth = int(a)
1278             if insnwidth == 16:
1279                 insntype = 'uint16_t'
1280                 insnmask = 0xffff
1281             elif insnwidth != 32:
1282                 error(0, 'cannot handle insns of width', insnwidth)
1283         else:
1284             assert False, 'unhandled option'
1285
1286     if len(args) < 1:
1287         error(0, 'missing input file')
1288
1289     toppat = ExcMultiPattern(0)
1290
1291     for filename in args:
1292         input_file = filename
1293         f = open(filename, 'r')
1294         parse_file(f, toppat)
1295         f.close()
1296
1297     # We do not want to compute masks for toppat, because those masks
1298     # are used as a starting point for build_tree.  For toppat, we must
1299     # insist that decode begins from naught.
1300     for i in toppat.pats:
1301         i.prop_masks()
1302
1303     toppat.build_tree()
1304     toppat.prop_format()
1305
1306     if variablewidth:
1307         for i in toppat.pats:
1308             i.prop_width()
1309         stree = build_size_tree(toppat.pats, 8, 0, 0)
1310         prop_size(stree)
1311
1312     if output_file:
1313         output_fd = open(output_file, 'w')
1314     else:
1315         output_fd = sys.stdout
1316
1317     output_autogen()
1318     for n in sorted(arguments.keys()):
1319         f = arguments[n]
1320         f.output_def()
1321
1322     # A single translate function can be invoked for different patterns.
1323     # Make sure that the argument sets are the same, and declare the
1324     # function only once.
1325     #
1326     # If we're sharing formats, we're likely also sharing trans_* functions,
1327     # but we can't tell which ones.  Prevent issues from the compiler by
1328     # suppressing redundant declaration warnings.
1329     if anyextern:
1330         output("#pragma GCC diagnostic push\n",
1331                "#pragma GCC diagnostic ignored \"-Wredundant-decls\"\n",
1332                "#ifdef __clang__\n"
1333                "#  pragma GCC diagnostic ignored \"-Wtypedef-redefinition\"\n",
1334                "#endif\n\n")
1335
1336     out_pats = {}
1337     for i in allpatterns:
1338         if i.name in out_pats:
1339             p = out_pats[i.name]
1340             if i.base.base != p.base.base:
1341                 error(0, i.name, ' has conflicting argument sets')
1342         else:
1343             i.output_decl()
1344             out_pats[i.name] = i
1345     output('\n')
1346
1347     if anyextern:
1348         output("#pragma GCC diagnostic pop\n\n")
1349
1350     for n in sorted(formats.keys()):
1351         f = formats[n]
1352         f.output_extract()
1353
1354     output(decode_scope, 'bool ', decode_function,
1355            '(DisasContext *ctx, ', insntype, ' insn)\n{\n')
1356
1357     i4 = str_indent(4)
1358
1359     if len(allpatterns) != 0:
1360         output(i4, 'union {\n')
1361         for n in sorted(arguments.keys()):
1362             f = arguments[n]
1363             output(i4, i4, f.struct_name(), ' f_', f.name, ';\n')
1364         output(i4, '} u;\n\n')
1365         toppat.output_code(4, False, 0, 0)
1366
1367     output(i4, 'return false;\n')
1368     output('}\n')
1369
1370     if variablewidth:
1371         output('\n', decode_scope, insntype, ' ', decode_function,
1372                '_load(DisasContext *ctx)\n{\n',
1373                '    ', insntype, ' insn = 0;\n\n')
1374         stree.output_code(4, 0, 0, 0)
1375         output('}\n')
1376
1377     if output_file:
1378         output_fd.close()
1379 # end main
1380
1381
1382 if __name__ == '__main__':
1383     main()