| #!/usr/bin/env python3 | |
| # Copyright (c) 2018 Linaro Limited | |
| # | |
| # This library is free software; you can redistribute it and/or | |
| # modify it under the terms of the GNU Lesser General Public | |
| # License as published by the Free Software Foundation; either | |
| # version 2.1 of the License, or (at your option) any later version. | |
| # | |
| # This library is distributed in the hope that it will be useful, | |
| # but WITHOUT ANY WARRANTY; without even the implied warranty of | |
| # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
| # Lesser General Public License for more details. | |
| # | |
| # You should have received a copy of the GNU Lesser General Public | |
| # License along with this library; if not, see <http://www.gnu.org/licenses/>. | |
| # | |
| # | |
| # Generate a decoding tree from a specification file. | |
| # See the syntax and semantics in docs/devel/decodetree.rst. | |
| # | |
| import io | |
| import os | |
| import re | |
| import sys | |
| import getopt | |
| insnwidth = 32 | |
| bitop_width = 32 | |
| insnmask = 0xffffffff | |
| variablewidth = False | |
| fields = {} | |
| arguments = {} | |
| formats = {} | |
| allpatterns = [] | |
| anyextern = False | |
| translate_prefix = 'trans' | |
| translate_scope = 'static ' | |
| input_file = '' | |
| output_file = None | |
| output_fd = None | |
| insntype = 'uint32_t' | |
| decode_function = 'decode' | |
| # An identifier for C. | |
| re_C_ident = '[a-zA-Z][a-zA-Z0-9_]*' | |
| # Identifiers for Arguments, Fields, Formats and Patterns. | |
| re_arg_ident = '&[a-zA-Z0-9_]*' | |
| re_fld_ident = '%[a-zA-Z0-9_]*' | |
| re_fmt_ident = '@[a-zA-Z0-9_]*' | |
| re_pat_ident = '[a-zA-Z0-9_]*' | |
| def error_with_file(file, lineno, *args): | |
| """Print an error message from file:line and args and exit.""" | |
| global output_file | |
| global output_fd | |
| prefix = '' | |
| if file: | |
| prefix += f'{file}:' | |
| if lineno: | |
| prefix += f'{lineno}:' | |
| if prefix: | |
| prefix += ' ' | |
| print(prefix, end='error: ', file=sys.stderr) | |
| print(*args, file=sys.stderr) | |
| if output_file and output_fd: | |
| output_fd.close() | |
| os.remove(output_file) | |
| exit(1) | |
| # end error_with_file | |
| def error(lineno, *args): | |
| error_with_file(input_file, lineno, *args) | |
| # end error | |
| def output(*args): | |
| global output_fd | |
| for a in args: | |
| output_fd.write(a) | |
| def output_autogen(): | |
| output('/* This file is autogenerated by scripts/decodetree.py. */\n\n') | |
| def str_indent(c): | |
| """Return a string with C spaces""" | |
| return ' ' * c | |
| def str_fields(fields): | |
| """Return a string uniquely identifying FIELDS""" | |
| r = '' | |
| for n in sorted(fields.keys()): | |
| r += '_' + n | |
| return r[1:] | |
| def whex(val): | |
| """Return a hex string for val padded for insnwidth""" | |
| global insnwidth | |
| return f'0x{val:0{insnwidth // 4}x}' | |
| def whexC(val): | |
| """Return a hex string for val padded for insnwidth, | |
| and with the proper suffix for a C constant.""" | |
| suffix = '' | |
| if val >= 0x100000000: | |
| suffix = 'ull' | |
| elif val >= 0x80000000: | |
| suffix = 'u' | |
| return whex(val) + suffix | |
| def str_match_bits(bits, mask): | |
| """Return a string pretty-printing BITS/MASK""" | |
| global insnwidth | |
| i = 1 << (insnwidth - 1) | |
| space = 0x01010100 | |
| r = '' | |
| while i != 0: | |
| if i & mask: | |
| if i & bits: | |
| r += '1' | |
| else: | |
| r += '0' | |
| else: | |
| r += '.' | |
| if i & space: | |
| r += ' ' | |
| i >>= 1 | |
| return r | |
| def is_pow2(x): | |
| """Return true iff X is equal to a power of 2.""" | |
| return (x & (x - 1)) == 0 | |
| def ctz(x): | |
| """Return the number of times 2 factors into X.""" | |
| assert x != 0 | |
| r = 0 | |
| while ((x >> r) & 1) == 0: | |
| r += 1 | |
| return r | |
| def is_contiguous(bits): | |
| if bits == 0: | |
| return -1 | |
| shift = ctz(bits) | |
| if is_pow2((bits >> shift) + 1): | |
| return shift | |
| else: | |
| return -1 | |
| def eq_fields_for_args(flds_a, arg): | |
| if len(flds_a) != len(arg.fields): | |
| return False | |
| # Only allow inference on default types | |
| for t in arg.types: | |
| if t != 'int': | |
| return False | |
| for k, a in flds_a.items(): | |
| if k not in arg.fields: | |
| return False | |
| return True | |
| def eq_fields_for_fmts(flds_a, flds_b): | |
| if len(flds_a) != len(flds_b): | |
| return False | |
| for k, a in flds_a.items(): | |
| if k not in flds_b: | |
| return False | |
| b = flds_b[k] | |
| if a.__class__ != b.__class__ or a != b: | |
| return False | |
| return True | |
| class Field: | |
| """Class representing a simple instruction field""" | |
| def __init__(self, sign, pos, len): | |
| self.sign = sign | |
| self.pos = pos | |
| self.len = len | |
| self.mask = ((1 << len) - 1) << pos | |
| def __str__(self): | |
| if self.sign: | |
| s = 's' | |
| else: | |
| s = '' | |
| return str(self.pos) + ':' + s + str(self.len) | |
| def str_extract(self): | |
| global bitop_width | |
| s = 's' if self.sign else '' | |
| return f'{s}extract{bitop_width}(insn, {self.pos}, {self.len})' | |
| def __eq__(self, other): | |
| return self.sign == other.sign and self.mask == other.mask | |
| def __ne__(self, other): | |
| return not self.__eq__(other) | |
| # end Field | |
| class MultiField: | |
| """Class representing a compound instruction field""" | |
| def __init__(self, subs, mask): | |
| self.subs = subs | |
| self.sign = subs[0].sign | |
| self.mask = mask | |
| def __str__(self): | |
| return str(self.subs) | |
| def str_extract(self): | |
| global bitop_width | |
| ret = '0' | |
| pos = 0 | |
| for f in reversed(self.subs): | |
| ext = f.str_extract() | |
| if pos == 0: | |
| ret = ext | |
| else: | |
| ret = f'deposit{bitop_width}({ret}, {pos}, {bitop_width - pos}, {ext})' | |
| pos += f.len | |
| return ret | |
| def __ne__(self, other): | |
| if len(self.subs) != len(other.subs): | |
| return True | |
| for a, b in zip(self.subs, other.subs): | |
| if a.__class__ != b.__class__ or a != b: | |
| return True | |
| return False | |
| def __eq__(self, other): | |
| return not self.__ne__(other) | |
| # end MultiField | |
| class ConstField: | |
| """Class representing an argument field with constant value""" | |
| def __init__(self, value): | |
| self.value = value | |
| self.mask = 0 | |
| self.sign = value < 0 | |
| def __str__(self): | |
| return str(self.value) | |
| def str_extract(self): | |
| return str(self.value) | |
| def __cmp__(self, other): | |
| return self.value - other.value | |
| # end ConstField | |
| class FunctionField: | |
| """Class representing a field passed through a function""" | |
| def __init__(self, func, base): | |
| self.mask = base.mask | |
| self.sign = base.sign | |
| self.base = base | |
| self.func = func | |
| def __str__(self): | |
| return self.func + '(' + str(self.base) + ')' | |
| def str_extract(self): | |
| return self.func + '(ctx, ' + self.base.str_extract() + ')' | |
| def __eq__(self, other): | |
| return self.func == other.func and self.base == other.base | |
| def __ne__(self, other): | |
| return not self.__eq__(other) | |
| # end FunctionField | |
| class ParameterField: | |
| """Class representing a pseudo-field read from a function""" | |
| def __init__(self, func): | |
| self.mask = 0 | |
| self.sign = 0 | |
| self.func = func | |
| def __str__(self): | |
| return self.func | |
| def str_extract(self): | |
| return self.func + '(ctx)' | |
| def __eq__(self, other): | |
| return self.func == other.func | |
| def __ne__(self, other): | |
| return not self.__eq__(other) | |
| # end ParameterField | |
| class Arguments: | |
| """Class representing the extracted fields of a format""" | |
| def __init__(self, nm, flds, types, extern): | |
| self.name = nm | |
| self.extern = extern | |
| self.fields = flds | |
| self.types = types | |
| def __str__(self): | |
| return self.name + ' ' + str(self.fields) | |
| def struct_name(self): | |
| return 'arg_' + self.name | |
| def output_def(self): | |
| if not self.extern: | |
| output('typedef struct {\n') | |
| for (n, t) in zip(self.fields, self.types): | |
| output(f' {t} {n};\n') | |
| output('} ', self.struct_name(), ';\n\n') | |
| # end Arguments | |
| class General: | |
| """Common code between instruction formats and instruction patterns""" | |
| def __init__(self, name, lineno, base, fixb, fixm, udfm, fldm, flds, w): | |
| self.name = name | |
| self.file = input_file | |
| self.lineno = lineno | |
| self.base = base | |
| self.fixedbits = fixb | |
| self.fixedmask = fixm | |
| self.undefmask = udfm | |
| self.fieldmask = fldm | |
| self.fields = flds | |
| self.width = w | |
| def __str__(self): | |
| return self.name + ' ' + str_match_bits(self.fixedbits, self.fixedmask) | |
| def str1(self, i): | |
| return str_indent(i) + self.__str__() | |
| # end General | |
| class Format(General): | |
| """Class representing an instruction format""" | |
| def extract_name(self): | |
| global decode_function | |
| return decode_function + '_extract_' + self.name | |
| def output_extract(self): | |
| output('static void ', self.extract_name(), '(DisasContext *ctx, ', | |
| self.base.struct_name(), ' *a, ', insntype, ' insn)\n{\n') | |
| for n, f in self.fields.items(): | |
| output(' a->', n, ' = ', f.str_extract(), ';\n') | |
| output('}\n\n') | |
| # end Format | |
| class Pattern(General): | |
| """Class representing an instruction pattern""" | |
| def output_decl(self): | |
| global translate_scope | |
| global translate_prefix | |
| output('typedef ', self.base.base.struct_name(), | |
| ' arg_', self.name, ';\n') | |
| output(translate_scope, 'bool ', translate_prefix, '_', self.name, | |
| '(DisasContext *ctx, arg_', self.name, ' *a);\n') | |
| def output_code(self, i, extracted, outerbits, outermask): | |
| global translate_prefix | |
| ind = str_indent(i) | |
| arg = self.base.base.name | |
| output(ind, '/* ', self.file, ':', str(self.lineno), ' */\n') | |
| if not extracted: | |
| output(ind, self.base.extract_name(), | |
| '(ctx, &u.f_', arg, ', insn);\n') | |
| for n, f in self.fields.items(): | |
| output(ind, 'u.f_', arg, '.', n, ' = ', f.str_extract(), ';\n') | |
| output(ind, 'if (', translate_prefix, '_', self.name, | |
| '(ctx, &u.f_', arg, ')) return true;\n') | |
| # Normal patterns do not have children. | |
| def build_tree(self): | |
| return | |
| def prop_masks(self): | |
| return | |
| def prop_format(self): | |
| return | |
| def prop_width(self): | |
| return | |
| # end Pattern | |
| class MultiPattern(General): | |
| """Class representing a set of instruction patterns""" | |
| def __init__(self, lineno): | |
| self.file = input_file | |
| self.lineno = lineno | |
| self.pats = [] | |
| self.base = None | |
| self.fixedbits = 0 | |
| self.fixedmask = 0 | |
| self.undefmask = 0 | |
| self.width = None | |
| def __str__(self): | |
| r = 'group' | |
| if self.fixedbits is not None: | |
| r += ' ' + str_match_bits(self.fixedbits, self.fixedmask) | |
| return r | |
| def output_decl(self): | |
| for p in self.pats: | |
| p.output_decl() | |
| def prop_masks(self): | |
| global insnmask | |
| fixedmask = insnmask | |
| undefmask = insnmask | |
| # Collect fixedmask/undefmask for all of the children. | |
| for p in self.pats: | |
| p.prop_masks() | |
| fixedmask &= p.fixedmask | |
| undefmask &= p.undefmask | |
| # Widen fixedmask until all fixedbits match | |
| repeat = True | |
| fixedbits = 0 | |
| while repeat and fixedmask != 0: | |
| fixedbits = None | |
| for p in self.pats: | |
| thisbits = p.fixedbits & fixedmask | |
| if fixedbits is None: | |
| fixedbits = thisbits | |
| elif fixedbits != thisbits: | |
| fixedmask &= ~(fixedbits ^ thisbits) | |
| break | |
| else: | |
| repeat = False | |
| self.fixedbits = fixedbits | |
| self.fixedmask = fixedmask | |
| self.undefmask = undefmask | |
| def build_tree(self): | |
| for p in self.pats: | |
| p.build_tree() | |
| def prop_format(self): | |
| for p in self.pats: | |
| p.build_tree() | |
| def prop_width(self): | |
| width = None | |
| for p in self.pats: | |
| p.prop_width() | |
| if width is None: | |
| width = p.width | |
| elif width != p.width: | |
| error_with_file(self.file, self.lineno, | |
| 'width mismatch in patterns within braces') | |
| self.width = width | |
| # end MultiPattern | |
| class IncMultiPattern(MultiPattern): | |
| """Class representing an overlapping set of instruction patterns""" | |
| def output_code(self, i, extracted, outerbits, outermask): | |
| global translate_prefix | |
| ind = str_indent(i) | |
| for p in self.pats: | |
| if outermask != p.fixedmask: | |
| innermask = p.fixedmask & ~outermask | |
| innerbits = p.fixedbits & ~outermask | |
| output(ind, f'if ((insn & {whexC(innermask)}) == {whexC(innerbits)}) {{\n') | |
| output(ind, f' /* {str_match_bits(p.fixedbits, p.fixedmask)} */\n') | |
| p.output_code(i + 4, extracted, p.fixedbits, p.fixedmask) | |
| output(ind, '}\n') | |
| else: | |
| p.output_code(i, extracted, p.fixedbits, p.fixedmask) | |
| #end IncMultiPattern | |
| class Tree: | |
| """Class representing a node in a decode tree""" | |
| def __init__(self, fm, tm): | |
| self.fixedmask = fm | |
| self.thismask = tm | |
| self.subs = [] | |
| self.base = None | |
| def str1(self, i): | |
| ind = str_indent(i) | |
| r = ind + whex(self.fixedmask) | |
| if self.format: | |
| r += ' ' + self.format.name | |
| r += ' [\n' | |
| for (b, s) in self.subs: | |
| r += ind + f' {whex(b)}:\n' | |
| r += s.str1(i + 4) + '\n' | |
| r += ind + ']' | |
| return r | |
| def __str__(self): | |
| return self.str1(0) | |
| def output_code(self, i, extracted, outerbits, outermask): | |
| ind = str_indent(i) | |
| # If we identified all nodes below have the same format, | |
| # extract the fields now. | |
| if not extracted and self.base: | |
| output(ind, self.base.extract_name(), | |
| '(ctx, &u.f_', self.base.base.name, ', insn);\n') | |
| extracted = True | |
| # Attempt to aid the compiler in producing compact switch statements. | |
| # If the bits in the mask are contiguous, extract them. | |
| sh = is_contiguous(self.thismask) | |
| if sh > 0: | |
| # Propagate SH down into the local functions. | |
| def str_switch(b, sh=sh): | |
| return f'(insn >> {sh}) & {b >> sh:#x}' | |
| def str_case(b, sh=sh): | |
| return hex(b >> sh) | |
| else: | |
| def str_switch(b): | |
| return f'insn & {whexC(b)}' | |
| def str_case(b): | |
| return whexC(b) | |
| output(ind, 'switch (', str_switch(self.thismask), ') {\n') | |
| for b, s in sorted(self.subs): | |
| assert (self.thismask & ~s.fixedmask) == 0 | |
| innermask = outermask | self.thismask | |
| innerbits = outerbits | b | |
| output(ind, 'case ', str_case(b), ':\n') | |
| output(ind, ' /* ', | |
| str_match_bits(innerbits, innermask), ' */\n') | |
| s.output_code(i + 4, extracted, innerbits, innermask) | |
| output(ind, ' break;\n') | |
| output(ind, '}\n') | |
| # end Tree | |
| class ExcMultiPattern(MultiPattern): | |
| """Class representing a non-overlapping set of instruction patterns""" | |
| def output_code(self, i, extracted, outerbits, outermask): | |
| # Defer everything to our decomposed Tree node | |
| self.tree.output_code(i, extracted, outerbits, outermask) | |
| @staticmethod | |
| def __build_tree(pats, outerbits, outermask): | |
| # Find the intersection of all remaining fixedmask. | |
| innermask = ~outermask & insnmask | |
| for i in pats: | |
| innermask &= i.fixedmask | |
| if innermask == 0: | |
| # Edge condition: One pattern covers the entire insnmask | |
| if len(pats) == 1: | |
| t = Tree(outermask, innermask) | |
| t.subs.append((0, pats[0])) | |
| return t | |
| text = 'overlapping patterns:' | |
| for p in pats: | |
| text += '\n' + p.file + ':' + str(p.lineno) + ': ' + str(p) | |
| error_with_file(pats[0].file, pats[0].lineno, text) | |
| fullmask = outermask | innermask | |
| # Sort each element of pats into the bin selected by the mask. | |
| bins = {} | |
| for i in pats: | |
| fb = i.fixedbits & innermask | |
| if fb in bins: | |
| bins[fb].append(i) | |
| else: | |
| bins[fb] = [i] | |
| # We must recurse if any bin has more than one element or if | |
| # the single element in the bin has not been fully matched. | |
| t = Tree(fullmask, innermask) | |
| for b, l in bins.items(): | |
| s = l[0] | |
| if len(l) > 1 or s.fixedmask & ~fullmask != 0: | |
| s = ExcMultiPattern.__build_tree(l, b | outerbits, fullmask) | |
| t.subs.append((b, s)) | |
| return t | |
| def build_tree(self): | |
| super().prop_format() | |
| self.tree = self.__build_tree(self.pats, self.fixedbits, | |
| self.fixedmask) | |
| @staticmethod | |
| def __prop_format(tree): | |
| """Propagate Format objects into the decode tree""" | |
| # Depth first search. | |
| for (b, s) in tree.subs: | |
| if isinstance(s, Tree): | |
| ExcMultiPattern.__prop_format(s) | |
| # If all entries in SUBS have the same format, then | |
| # propagate that into the tree. | |
| f = None | |
| for (b, s) in tree.subs: | |
| if f is None: | |
| f = s.base | |
| if f is None: | |
| return | |
| if f is not s.base: | |
| return | |
| tree.base = f | |
| def prop_format(self): | |
| super().prop_format() | |
| self.__prop_format(self.tree) | |
| # end ExcMultiPattern | |
| def parse_field(lineno, name, toks): | |
| """Parse one instruction field from TOKS at LINENO""" | |
| global fields | |
| global insnwidth | |
| # A "simple" field will have only one entry; | |
| # a "multifield" will have several. | |
| subs = [] | |
| width = 0 | |
| func = None | |
| for t in toks: | |
| if re.match('^!function=', t): | |
| if func: | |
| error(lineno, 'duplicate function') | |
| func = t.split('=') | |
| func = func[1] | |
| continue | |
| if re.fullmatch('[0-9]+:s[0-9]+', t): | |
| # Signed field extract | |
| subtoks = t.split(':s') | |
| sign = True | |
| elif re.fullmatch('[0-9]+:[0-9]+', t): | |
| # Unsigned field extract | |
| subtoks = t.split(':') | |
| sign = False | |
| else: | |
| error(lineno, f'invalid field token "{t}"') | |
| po = int(subtoks[0]) | |
| le = int(subtoks[1]) | |
| if po + le > insnwidth: | |
| error(lineno, f'field {t} too large') | |
| f = Field(sign, po, le) | |
| subs.append(f) | |
| width += le | |
| if width > insnwidth: | |
| error(lineno, 'field too large') | |
| if len(subs) == 0: | |
| if func: | |
| f = ParameterField(func) | |
| else: | |
| error(lineno, 'field with no value') | |
| else: | |
| if len(subs) == 1: | |
| f = subs[0] | |
| else: | |
| mask = 0 | |
| for s in subs: | |
| if mask & s.mask: | |
| error(lineno, 'field components overlap') | |
| mask |= s.mask | |
| f = MultiField(subs, mask) | |
| if func: | |
| f = FunctionField(func, f) | |
| if name in fields: | |
| error(lineno, 'duplicate field', name) | |
| fields[name] = f | |
| # end parse_field | |
| def parse_arguments(lineno, name, toks): | |
| """Parse one argument set from TOKS at LINENO""" | |
| global arguments | |
| global re_C_ident | |
| global anyextern | |
| flds = [] | |
| types = [] | |
| extern = False | |
| for n in toks: | |
| if re.fullmatch('!extern', n): | |
| extern = True | |
| anyextern = True | |
| continue | |
| if re.fullmatch(re_C_ident + ':' + re_C_ident, n): | |
| (n, t) = n.split(':') | |
| elif re.fullmatch(re_C_ident, n): | |
| t = 'int' | |
| else: | |
| error(lineno, f'invalid argument set token "{n}"') | |
| if n in flds: | |
| error(lineno, f'duplicate argument "{n}"') | |
| flds.append(n) | |
| types.append(t) | |
| if name in arguments: | |
| error(lineno, 'duplicate argument set', name) | |
| arguments[name] = Arguments(name, flds, types, extern) | |
| # end parse_arguments | |
| def lookup_field(lineno, name): | |
| global fields | |
| if name in fields: | |
| return fields[name] | |
| error(lineno, 'undefined field', name) | |
| def add_field(lineno, flds, new_name, f): | |
| if new_name in flds: | |
| error(lineno, 'duplicate field', new_name) | |
| flds[new_name] = f | |
| return flds | |
| def add_field_byname(lineno, flds, new_name, old_name): | |
| return add_field(lineno, flds, new_name, lookup_field(lineno, old_name)) | |
| def infer_argument_set(flds): | |
| global arguments | |
| global decode_function | |
| for arg in arguments.values(): | |
| if eq_fields_for_args(flds, arg): | |
| return arg | |
| name = decode_function + str(len(arguments)) | |
| arg = Arguments(name, flds.keys(), ['int'] * len(flds), False) | |
| arguments[name] = arg | |
| return arg | |
| def infer_format(arg, fieldmask, flds, width): | |
| global arguments | |
| global formats | |
| global decode_function | |
| const_flds = {} | |
| var_flds = {} | |
| for n, c in flds.items(): | |
| if c is ConstField: | |
| const_flds[n] = c | |
| else: | |
| var_flds[n] = c | |
| # Look for an existing format with the same argument set and fields | |
| for fmt in formats.values(): | |
| if arg and fmt.base != arg: | |
| continue | |
| if fieldmask != fmt.fieldmask: | |
| continue | |
| if width != fmt.width: | |
| continue | |
| if not eq_fields_for_fmts(flds, fmt.fields): | |
| continue | |
| return (fmt, const_flds) | |
| name = decode_function + '_Fmt_' + str(len(formats)) | |
| if not arg: | |
| arg = infer_argument_set(flds) | |
| fmt = Format(name, 0, arg, 0, 0, 0, fieldmask, var_flds, width) | |
| formats[name] = fmt | |
| return (fmt, const_flds) | |
| # end infer_format | |
| def parse_generic(lineno, parent_pat, name, toks): | |
| """Parse one instruction format from TOKS at LINENO""" | |
| global fields | |
| global arguments | |
| global formats | |
| global allpatterns | |
| global re_arg_ident | |
| global re_fld_ident | |
| global re_fmt_ident | |
| global re_C_ident | |
| global insnwidth | |
| global insnmask | |
| global variablewidth | |
| is_format = parent_pat is None | |
| fixedmask = 0 | |
| fixedbits = 0 | |
| undefmask = 0 | |
| width = 0 | |
| flds = {} | |
| arg = None | |
| fmt = None | |
| for t in toks: | |
| # '&Foo' gives a format an explicit argument set. | |
| if re.fullmatch(re_arg_ident, t): | |
| tt = t[1:] | |
| if arg: | |
| error(lineno, 'multiple argument sets') | |
| if tt in arguments: | |
| arg = arguments[tt] | |
| else: | |
| error(lineno, 'undefined argument set', t) | |
| continue | |
| # '@Foo' gives a pattern an explicit format. | |
| if re.fullmatch(re_fmt_ident, t): | |
| tt = t[1:] | |
| if fmt: | |
| error(lineno, 'multiple formats') | |
| if tt in formats: | |
| fmt = formats[tt] | |
| else: | |
| error(lineno, 'undefined format', t) | |
| continue | |
| # '%Foo' imports a field. | |
| if re.fullmatch(re_fld_ident, t): | |
| tt = t[1:] | |
| flds = add_field_byname(lineno, flds, tt, tt) | |
| continue | |
| # 'Foo=%Bar' imports a field with a different name. | |
| if re.fullmatch(re_C_ident + '=' + re_fld_ident, t): | |
| (fname, iname) = t.split('=%') | |
| flds = add_field_byname(lineno, flds, fname, iname) | |
| continue | |
| # 'Foo=number' sets an argument field to a constant value | |
| if re.fullmatch(re_C_ident + '=[+-]?[0-9]+', t): | |
| (fname, value) = t.split('=') | |
| value = int(value) | |
| flds = add_field(lineno, flds, fname, ConstField(value)) | |
| continue | |
| # Pattern of 0s, 1s, dots and dashes indicate required zeros, | |
| # required ones, or dont-cares. | |
| if re.fullmatch('[01.-]+', t): | |
| shift = len(t) | |
| fms = t.replace('0', '1') | |
| fms = fms.replace('.', '0') | |
| fms = fms.replace('-', '0') | |
| fbs = t.replace('.', '0') | |
| fbs = fbs.replace('-', '0') | |
| ubm = t.replace('1', '0') | |
| ubm = ubm.replace('.', '0') | |
| ubm = ubm.replace('-', '1') | |
| fms = int(fms, 2) | |
| fbs = int(fbs, 2) | |
| ubm = int(ubm, 2) | |
| fixedbits = (fixedbits << shift) | fbs | |
| fixedmask = (fixedmask << shift) | fms | |
| undefmask = (undefmask << shift) | ubm | |
| # Otherwise, fieldname:fieldwidth | |
| elif re.fullmatch(re_C_ident + ':s?[0-9]+', t): | |
| (fname, flen) = t.split(':') | |
| sign = False | |
| if flen[0] == 's': | |
| sign = True | |
| flen = flen[1:] | |
| shift = int(flen, 10) | |
| if shift + width > insnwidth: | |
| error(lineno, f'field {fname} exceeds insnwidth') | |
| f = Field(sign, insnwidth - width - shift, shift) | |
| flds = add_field(lineno, flds, fname, f) | |
| fixedbits <<= shift | |
| fixedmask <<= shift | |
| undefmask <<= shift | |
| else: | |
| error(lineno, f'invalid token "{t}"') | |
| width += shift | |
| if variablewidth and width < insnwidth and width % 8 == 0: | |
| shift = insnwidth - width | |
| fixedbits <<= shift | |
| fixedmask <<= shift | |
| undefmask <<= shift | |
| undefmask |= (1 << shift) - 1 | |
| # We should have filled in all of the bits of the instruction. | |
| elif not (is_format and width == 0) and width != insnwidth: | |
| error(lineno, f'definition has {width} bits') | |
| # Do not check for fields overlapping fields; one valid usage | |
| # is to be able to duplicate fields via import. | |
| fieldmask = 0 | |
| for f in flds.values(): | |
| fieldmask |= f.mask | |
| # Fix up what we've parsed to match either a format or a pattern. | |
| if is_format: | |
| # Formats cannot reference formats. | |
| if fmt: | |
| error(lineno, 'format referencing format') | |
| # If an argument set is given, then there should be no fields | |
| # without a place to store it. | |
| if arg: | |
| for f in flds.keys(): | |
| if f not in arg.fields: | |
| error(lineno, f'field {f} not in argument set {arg.name}') | |
| else: | |
| arg = infer_argument_set(flds) | |
| if name in formats: | |
| error(lineno, 'duplicate format name', name) | |
| fmt = Format(name, lineno, arg, fixedbits, fixedmask, | |
| undefmask, fieldmask, flds, width) | |
| formats[name] = fmt | |
| else: | |
| # Patterns can reference a format ... | |
| if fmt: | |
| # ... but not an argument simultaneously | |
| if arg: | |
| error(lineno, 'pattern specifies both format and argument set') | |
| if fixedmask & fmt.fixedmask: | |
| error(lineno, 'pattern fixed bits overlap format fixed bits') | |
| if width != fmt.width: | |
| error(lineno, 'pattern uses format of different width') | |
| fieldmask |= fmt.fieldmask | |
| fixedbits |= fmt.fixedbits | |
| fixedmask |= fmt.fixedmask | |
| undefmask |= fmt.undefmask | |
| else: | |
| (fmt, flds) = infer_format(arg, fieldmask, flds, width) | |
| arg = fmt.base | |
| for f in flds.keys(): | |
| if f not in arg.fields: | |
| error(lineno, f'field {f} not in argument set {arg.name}') | |
| if f in fmt.fields.keys(): | |
| error(lineno, f'field {f} set by format and pattern') | |
| for f in arg.fields: | |
| if f not in flds.keys() and f not in fmt.fields.keys(): | |
| error(lineno, f'field {f} not initialized') | |
| pat = Pattern(name, lineno, fmt, fixedbits, fixedmask, | |
| undefmask, fieldmask, flds, width) | |
| parent_pat.pats.append(pat) | |
| allpatterns.append(pat) | |
| # Validate the masks that we have assembled. | |
| if fieldmask & fixedmask: | |
| error(lineno, 'fieldmask overlaps fixedmask ', | |
| f'({whex(fieldmask)} & {whex(fixedmask)})') | |
| if fieldmask & undefmask: | |
| error(lineno, 'fieldmask overlaps undefmask ', | |
| f'({whex(fieldmask)} & {whex(undefmask)})') | |
| if fixedmask & undefmask: | |
| error(lineno, 'fixedmask overlaps undefmask ', | |
| f'({whex(fixedmask)} & {whex(undefmask)})') | |
| if not is_format: | |
| allbits = fieldmask | fixedmask | undefmask | |
| if allbits != insnmask: | |
| error(lineno, 'bits left unspecified ', | |
| f'({whex(allbits ^ insnmask)})') | |
| # end parse_general | |
| def parse_file(f, parent_pat): | |
| """Parse all of the patterns within a file""" | |
| global re_arg_ident | |
| global re_fld_ident | |
| global re_fmt_ident | |
| global re_pat_ident | |
| # Read all of the lines of the file. Concatenate lines | |
| # ending in backslash; discard empty lines and comments. | |
| toks = [] | |
| lineno = 0 | |
| nesting = 0 | |
| nesting_pats = [] | |
| for line in f: | |
| lineno += 1 | |
| # Expand and strip spaces, to find indent. | |
| line = line.rstrip() | |
| line = line.expandtabs() | |
| len1 = len(line) | |
| line = line.lstrip() | |
| len2 = len(line) | |
| # Discard comments | |
| end = line.find('#') | |
| if end >= 0: | |
| line = line[:end] | |
| t = line.split() | |
| if len(toks) != 0: | |
| # Next line after continuation | |
| toks.extend(t) | |
| else: | |
| # Allow completely blank lines. | |
| if len1 == 0: | |
| continue | |
| indent = len1 - len2 | |
| # Empty line due to comment. | |
| if len(t) == 0: | |
| # Indentation must be correct, even for comment lines. | |
| if indent != nesting: | |
| error(lineno, 'indentation ', indent, ' != ', nesting) | |
| continue | |
| start_lineno = lineno | |
| toks = t | |
| # Continuation? | |
| if toks[-1] == '\\': | |
| toks.pop() | |
| continue | |
| name = toks[0] | |
| del toks[0] | |
| # End nesting? | |
| if name == '}' or name == ']': | |
| if len(toks) != 0: | |
| error(start_lineno, 'extra tokens after close brace') | |
| # Make sure { } and [ ] nest properly. | |
| if (name == '}') != isinstance(parent_pat, IncMultiPattern): | |
| error(lineno, 'mismatched close brace') | |
| try: | |
| parent_pat = nesting_pats.pop() | |
| except: | |
| error(lineno, 'extra close brace') | |
| nesting -= 2 | |
| if indent != nesting: | |
| error(lineno, 'indentation ', indent, ' != ', nesting) | |
| toks = [] | |
| continue | |
| # Everything else should have current indentation. | |
| if indent != nesting: | |
| error(start_lineno, 'indentation ', indent, ' != ', nesting) | |
| # Start nesting? | |
| if name == '{' or name == '[': | |
| if len(toks) != 0: | |
| error(start_lineno, 'extra tokens after open brace') | |
| if name == '{': | |
| nested_pat = IncMultiPattern(start_lineno) | |
| else: | |
| nested_pat = ExcMultiPattern(start_lineno) | |
| parent_pat.pats.append(nested_pat) | |
| nesting_pats.append(parent_pat) | |
| parent_pat = nested_pat | |
| nesting += 2 | |
| toks = [] | |
| continue | |
| # Determine the type of object needing to be parsed. | |
| if re.fullmatch(re_fld_ident, name): | |
| parse_field(start_lineno, name[1:], toks) | |
| elif re.fullmatch(re_arg_ident, name): | |
| parse_arguments(start_lineno, name[1:], toks) | |
| elif re.fullmatch(re_fmt_ident, name): | |
| parse_generic(start_lineno, None, name[1:], toks) | |
| elif re.fullmatch(re_pat_ident, name): | |
| parse_generic(start_lineno, parent_pat, name, toks) | |
| else: | |
| error(lineno, f'invalid token "{name}"') | |
| toks = [] | |
| if nesting != 0: | |
| error(lineno, 'missing close brace') | |
| # end parse_file | |
| class SizeTree: | |
| """Class representing a node in a size decode tree""" | |
| def __init__(self, m, w): | |
| self.mask = m | |
| self.subs = [] | |
| self.base = None | |
| self.width = w | |
| def str1(self, i): | |
| ind = str_indent(i) | |
| r = ind + whex(self.mask) + ' [\n' | |
| for (b, s) in self.subs: | |
| r += ind + f' {whex(b)}:\n' | |
| r += s.str1(i + 4) + '\n' | |
| r += ind + ']' | |
| return r | |
| def __str__(self): | |
| return self.str1(0) | |
| def output_code(self, i, extracted, outerbits, outermask): | |
| ind = str_indent(i) | |
| # If we need to load more bytes to test, do so now. | |
| if extracted < self.width: | |
| output(ind, f'insn = {decode_function}_load_bytes', | |
| f'(ctx, insn, {extracted // 8}, {self.width // 8});\n') | |
| extracted = self.width | |
| # Attempt to aid the compiler in producing compact switch statements. | |
| # If the bits in the mask are contiguous, extract them. | |
| sh = is_contiguous(self.mask) | |
| if sh > 0: | |
| # Propagate SH down into the local functions. | |
| def str_switch(b, sh=sh): | |
| return f'(insn >> {sh}) & {b >> sh:#x}' | |
| def str_case(b, sh=sh): | |
| return hex(b >> sh) | |
| else: | |
| def str_switch(b): | |
| return f'insn & {whexC(b)}' | |
| def str_case(b): | |
| return whexC(b) | |
| output(ind, 'switch (', str_switch(self.mask), ') {\n') | |
| for b, s in sorted(self.subs): | |
| innermask = outermask | self.mask | |
| innerbits = outerbits | b | |
| output(ind, 'case ', str_case(b), ':\n') | |
| output(ind, ' /* ', | |
| str_match_bits(innerbits, innermask), ' */\n') | |
| s.output_code(i + 4, extracted, innerbits, innermask) | |
| output(ind, '}\n') | |
| output(ind, 'return insn;\n') | |
| # end SizeTree | |
| class SizeLeaf: | |
| """Class representing a leaf node in a size decode tree""" | |
| def __init__(self, m, w): | |
| self.mask = m | |
| self.width = w | |
| def str1(self, i): | |
| return str_indent(i) + whex(self.mask) | |
| def __str__(self): | |
| return self.str1(0) | |
| def output_code(self, i, extracted, outerbits, outermask): | |
| global decode_function | |
| ind = str_indent(i) | |
| # If we need to load more bytes, do so now. | |
| if extracted < self.width: | |
| output(ind, f'insn = {decode_function}_load_bytes', | |
| f'(ctx, insn, {extracted // 8}, {self.width // 8});\n') | |
| extracted = self.width | |
| output(ind, 'return insn;\n') | |
| # end SizeLeaf | |
| def build_size_tree(pats, width, outerbits, outermask): | |
| global insnwidth | |
| # Collect the mask of bits that are fixed in this width | |
| innermask = 0xff << (insnwidth - width) | |
| innermask &= ~outermask | |
| minwidth = None | |
| onewidth = True | |
| for i in pats: | |
| innermask &= i.fixedmask | |
| if minwidth is None: | |
| minwidth = i.width | |
| elif minwidth != i.width: | |
| onewidth = False; | |
| if minwidth < i.width: | |
| minwidth = i.width | |
| if onewidth: | |
| return SizeLeaf(innermask, minwidth) | |
| if innermask == 0: | |
| if width < minwidth: | |
| return build_size_tree(pats, width + 8, outerbits, outermask) | |
| pnames = [] | |
| for p in pats: | |
| pnames.append(p.name + ':' + p.file + ':' + str(p.lineno)) | |
| error_with_file(pats[0].file, pats[0].lineno, | |
| f'overlapping patterns size {width}:', pnames) | |
| bins = {} | |
| for i in pats: | |
| fb = i.fixedbits & innermask | |
| if fb in bins: | |
| bins[fb].append(i) | |
| else: | |
| bins[fb] = [i] | |
| fullmask = outermask | innermask | |
| lens = sorted(bins.keys()) | |
| if len(lens) == 1: | |
| b = lens[0] | |
| return build_size_tree(bins[b], width + 8, b | outerbits, fullmask) | |
| r = SizeTree(innermask, width) | |
| for b, l in bins.items(): | |
| s = build_size_tree(l, width, b | outerbits, fullmask) | |
| r.subs.append((b, s)) | |
| return r | |
| # end build_size_tree | |
| def prop_size(tree): | |
| """Propagate minimum widths up the decode size tree""" | |
| if isinstance(tree, SizeTree): | |
| min = None | |
| for (b, s) in tree.subs: | |
| width = prop_size(s) | |
| if min is None or min > width: | |
| min = width | |
| assert min >= tree.width | |
| tree.width = min | |
| else: | |
| min = tree.width | |
| return min | |
| # end prop_size | |
| def main(): | |
| global arguments | |
| global formats | |
| global allpatterns | |
| global translate_scope | |
| global translate_prefix | |
| global output_fd | |
| global output_file | |
| global input_file | |
| global insnwidth | |
| global insntype | |
| global insnmask | |
| global decode_function | |
| global bitop_width | |
| global variablewidth | |
| global anyextern | |
| decode_scope = 'static ' | |
| long_opts = ['decode=', 'translate=', 'output=', 'insnwidth=', | |
| 'static-decode=', 'varinsnwidth='] | |
| try: | |
| (opts, args) = getopt.gnu_getopt(sys.argv[1:], 'o:vw:', long_opts) | |
| except getopt.GetoptError as err: | |
| error(0, err) | |
| for o, a in opts: | |
| if o in ('-o', '--output'): | |
| output_file = a | |
| elif o == '--decode': | |
| decode_function = a | |
| decode_scope = '' | |
| elif o == '--static-decode': | |
| decode_function = a | |
| elif o == '--translate': | |
| translate_prefix = a | |
| translate_scope = '' | |
| elif o in ('-w', '--insnwidth', '--varinsnwidth'): | |
| if o == '--varinsnwidth': | |
| variablewidth = True | |
| insnwidth = int(a) | |
| if insnwidth == 16: | |
| insntype = 'uint16_t' | |
| insnmask = 0xffff | |
| elif insnwidth == 64: | |
| insntype = 'uint64_t' | |
| insnmask = 0xffffffffffffffff | |
| bitop_width = 64 | |
| elif insnwidth != 32: | |
| error(0, 'cannot handle insns of width', insnwidth) | |
| else: | |
| assert False, 'unhandled option' | |
| if len(args) < 1: | |
| error(0, 'missing input file') | |
| toppat = ExcMultiPattern(0) | |
| for filename in args: | |
| input_file = filename | |
| f = open(filename, 'rt', encoding='utf-8') | |
| parse_file(f, toppat) | |
| f.close() | |
| # We do not want to compute masks for toppat, because those masks | |
| # are used as a starting point for build_tree. For toppat, we must | |
| # insist that decode begins from naught. | |
| for i in toppat.pats: | |
| i.prop_masks() | |
| toppat.build_tree() | |
| toppat.prop_format() | |
| if variablewidth: | |
| for i in toppat.pats: | |
| i.prop_width() | |
| stree = build_size_tree(toppat.pats, 8, 0, 0) | |
| prop_size(stree) | |
| if output_file: | |
| output_fd = open(output_file, 'wt', encoding='utf-8') | |
| else: | |
| output_fd = io.TextIOWrapper(sys.stdout.buffer, | |
| encoding=sys.stdout.encoding, | |
| errors="ignore") | |
| output_autogen() | |
| for n in sorted(arguments.keys()): | |
| f = arguments[n] | |
| f.output_def() | |
| # A single translate function can be invoked for different patterns. | |
| # Make sure that the argument sets are the same, and declare the | |
| # function only once. | |
| # | |
| # If we're sharing formats, we're likely also sharing trans_* functions, | |
| # but we can't tell which ones. Prevent issues from the compiler by | |
| # suppressing redundant declaration warnings. | |
| if anyextern: | |
| output("#pragma GCC diagnostic push\n", | |
| "#pragma GCC diagnostic ignored \"-Wredundant-decls\"\n", | |
| "#ifdef __clang__\n" | |
| "# pragma GCC diagnostic ignored \"-Wtypedef-redefinition\"\n", | |
| "#endif\n\n") | |
| out_pats = {} | |
| for i in allpatterns: | |
| if i.name in out_pats: | |
| p = out_pats[i.name] | |
| if i.base.base != p.base.base: | |
| error(0, i.name, ' has conflicting argument sets') | |
| else: | |
| i.output_decl() | |
| out_pats[i.name] = i | |
| output('\n') | |
| if anyextern: | |
| output("#pragma GCC diagnostic pop\n\n") | |
| for n in sorted(formats.keys()): | |
| f = formats[n] | |
| f.output_extract() | |
| output(decode_scope, 'bool ', decode_function, | |
| '(DisasContext *ctx, ', insntype, ' insn)\n{\n') | |
| i4 = str_indent(4) | |
| if len(allpatterns) != 0: | |
| output(i4, 'union {\n') | |
| for n in sorted(arguments.keys()): | |
| f = arguments[n] | |
| output(i4, i4, f.struct_name(), ' f_', f.name, ';\n') | |
| output(i4, '} u;\n\n') | |
| toppat.output_code(4, False, 0, 0) | |
| output(i4, 'return false;\n') | |
| output('}\n') | |
| if variablewidth: | |
| output('\n', decode_scope, insntype, ' ', decode_function, | |
| '_load(DisasContext *ctx)\n{\n', | |
| ' ', insntype, ' insn = 0;\n\n') | |
| stree.output_code(4, 0, 0, 0) | |
| output('}\n') | |
| if output_file: | |
| output_fd.close() | |
| # end main | |
| if __name__ == '__main__': | |
| main() |