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