| # |
| # Copyright © 2020 Google, Inc. |
| # |
| # Permission is hereby granted, free of charge, to any person obtaining a |
| # copy of this software and associated documentation files (the "Software"), |
| # to deal in the Software without restriction, including without limitation |
| # the rights to use, copy, modify, merge, publish, distribute, sublicense, |
| # and/or sell copies of the Software, and to permit persons to whom the |
| # Software is furnished to do so, subject to the following conditions: |
| # |
| # The above copyright notice and this permission notice (including the next |
| # paragraph) shall be included in all copies or substantial portions of the |
| # Software. |
| # |
| # THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR |
| # IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, |
| # FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL |
| # THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER |
| # LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING |
| # FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS |
| # IN THE SOFTWARE. |
| |
| from xml.etree import ElementTree |
| import os |
| import re |
| |
| def dbg(str): |
| if False: |
| print(str) |
| |
| class BitSetPattern(object): |
| """Class that encapsulated the pattern matching, ie. |
| the match/dontcare/mask bitmasks. The following |
| rules should hold |
| |
| (match ^ dontcare) == 0 |
| (match || dontcare) == mask |
| |
| For a leaf node, the mask should be (1 << size) - 1 |
| (ie. all bits set) |
| """ |
| def __init__(self, bitset): |
| self.match = bitset.match |
| self.dontcare = bitset.dontcare |
| self.mask = bitset.mask |
| self.field_mask = bitset.field_mask |
| |
| def merge(self, pattern): |
| p = BitSetPattern(pattern) |
| p.match = p.match | self.match |
| p.dontcare = p.dontcare | self.dontcare |
| p.mask = p.mask | self.mask |
| p.field_mask = p.field_mask | self.field_mask |
| return p |
| |
| def defined_bits(self): |
| return self.match | self.dontcare | self.mask | self.field_mask |
| |
| def get_bitrange(field): |
| if 'pos' in field.attrib: |
| assert('low' not in field.attrib) |
| assert('high' not in field.attrib) |
| low = int(field.attrib['pos']) |
| high = low |
| else: |
| low = int(field.attrib['low']) |
| high = int(field.attrib['high']) |
| assert low <= high |
| return low, high |
| |
| def extract_pattern(xml, name, is_defined_bits=None): |
| low, high = get_bitrange(xml) |
| mask = ((1 << (1 + high - low)) - 1) << low |
| |
| patstr = xml.text.strip() |
| |
| assert (len(patstr) == (1 + high - low)), "Invalid {} length in {}: {}..{}".format(xml.tag, name, low, high) |
| if is_defined_bits is not None: |
| assert not is_defined_bits(mask), "Redefined bits in {} {}: {}..{}".format(xml.tag, name, low, high) |
| |
| match = 0 |
| dontcare = 0 |
| |
| for n in range(0, len(patstr)): |
| match = match << 1 |
| dontcare = dontcare << 1 |
| if patstr[n] == '1': |
| match |= 1 |
| elif patstr[n] == 'x': |
| dontcare |= 1 |
| elif patstr[n] != '0': |
| assert 0, "Invalid {} character in {}: {}".format(xml.tag, name, patstr[n]) |
| |
| dbg("{}: {}.{} => {:016x} / {:016x} / {:016x}".format(xml.tag, name, patstr, match << low, dontcare << low, mask)) |
| |
| return match << low, dontcare << low, mask |
| |
| def get_c_name(name): |
| return name.lower().replace('#', '__').replace('-', '_').replace('.', '_') |
| |
| class BitSetField(object): |
| """Class that encapsulates a field defined in a bitset |
| """ |
| def __init__(self, isa, xml): |
| self.isa = isa |
| self.low, self.high = get_bitrange(xml) |
| self.name = xml.attrib['name'] |
| self.type = xml.attrib['type'] |
| self.params = [] |
| for param in xml.findall('param'): |
| aas = name = param.attrib['name'] |
| if 'as' in param.attrib: |
| aas = param.attrib['as'] |
| self.params.append([name, aas]) |
| self.expr = None |
| self.display = None |
| self.call = 'call' in xml.attrib and xml.attrib['call'] == 'true' |
| if 'display' in xml.attrib: |
| self.display = xml.attrib['display'].strip() |
| |
| def get_c_name(self): |
| return get_c_name(self.name) |
| |
| def get_c_typename(self): |
| if self.type in self.isa.enums: |
| return 'TYPE_ENUM' |
| if self.type in self.isa.bitsets: |
| return 'TYPE_BITSET' |
| return 'TYPE_' + self.type.upper() |
| |
| def mask(self): |
| return ((1 << self.get_size()) - 1) << self.low |
| |
| def get_size(self): |
| return 1 + self.high - self.low |
| |
| class BitSetAssertField(BitSetField): |
| """Similar to BitSetField, but for <assert/>s, which can be |
| used to specify that a certain bitpattern is expected in |
| place of (for example) unused bitfields |
| """ |
| def __init__(self, case, xml): |
| self.isa = case.bitset.isa |
| self.low, self.high = get_bitrange(xml) |
| self.name = case.bitset.name + '#assert' + str(len(case.fields)) |
| self.type = 'uint' |
| self.expr = None |
| self.display = None |
| |
| match, dontcare, mask = extract_pattern(xml, case.bitset.name) |
| self.val = match >> self.low |
| |
| assert dontcare == 0, "'x' (dontcare) is not valid in an assert" |
| |
| def get_c_typename(self): |
| return 'TYPE_ASSERT' |
| |
| class BitSetDerivedField(BitSetField): |
| """Similar to BitSetField, but for derived fields |
| """ |
| def __init__(self, isa, xml): |
| self.isa = isa |
| self.low = 0 |
| self.high = 0 |
| # NOTE: a width should be provided for 'int' derived fields, ie. |
| # where sign extension is needed. We just repurpose the 'high' |
| # field for that to make '1 + high - low' work out |
| if 'width' in xml.attrib: |
| self.high = int(xml.attrib['width']) - 1 |
| self.name = xml.attrib['name'] |
| self.type = xml.attrib['type'] |
| if 'expr' in xml.attrib: |
| self.expr = xml.attrib['expr'] |
| else: |
| e = isa.parse_one_expression(xml, self.name) |
| self.expr = e.name |
| self.display = None |
| if 'display' in xml.attrib: |
| self.display = xml.attrib['display'].strip() |
| self.call = 'call' in xml.attrib and xml.attrib['call'] == 'true' |
| |
| class BitSetCase(object): |
| """Class that encapsulates a single bitset case |
| """ |
| def __init__(self, bitset, xml, update_field_mask, expr=None): |
| self.bitset = bitset |
| if expr is not None: |
| self.name = bitset.name + '#case' + str(len(bitset.cases)) |
| else: |
| self.name = bitset.name + "#default" |
| self.expr = expr |
| self.fields = {} |
| |
| for derived in xml.findall('derived'): |
| f = BitSetDerivedField(bitset.isa, derived) |
| self.fields[f.name] = f |
| |
| for assrt in xml.findall('assert'): |
| f = BitSetAssertField(self, assrt) |
| update_field_mask(self, f) |
| self.fields[f.name] = f |
| |
| for field in xml.findall('field'): |
| dbg("{}.{}".format(self.name, field.attrib['name'])) |
| f = BitSetField(bitset.isa, field) |
| update_field_mask(self, f) |
| self.fields[f.name] = f |
| |
| self.display = None |
| for d in xml.findall('display'): |
| # Allow <display/> for empty display string: |
| if d.text is not None: |
| self.display = d.text.strip() |
| else: |
| self.display = '' |
| dbg("found display: '{}'".format(self.display)) |
| |
| def get_c_name(self): |
| return get_c_name(self.name) |
| |
| class BitSetEncode(object): |
| """Additional data that may be associated with a root bitset node |
| to provide additional information needed to generate helpers |
| to encode the bitset, such as source data type and "opcode" |
| case prefix (ie. how to choose/enumerate which leaf node bitset |
| to use to encode the source data |
| """ |
| def __init__(self, xml): |
| self.type = None |
| if 'type' in xml.attrib: |
| self.type = xml.attrib['type'] |
| self.case_prefix = None |
| if 'case-prefix' in xml.attrib: |
| self.case_prefix = xml.attrib['case-prefix'] |
| # The encode element may also contain mappings from encode src |
| # to individual field names: |
| self.maps = {} |
| self.forced = {} |
| for map in xml.findall('map'): |
| name = map.attrib['name'] |
| self.maps[name] = map.text.strip() |
| if 'force' in map.attrib and map.attrib['force'] == 'true': |
| self.forced[name] = 'true' |
| |
| class BitSetDecode(object): |
| """Additional data that may be associated with a root bitset node |
| to provide additional information needed to generate helpers |
| to decode the bitset. |
| """ |
| def __init__(self, xml): |
| pass |
| |
| class BitSet(object): |
| """Class that encapsulates a single bitset rule |
| """ |
| def __init__(self, isa, xml): |
| self.isa = isa |
| self.xml = xml |
| self.name = xml.attrib['name'] |
| self.display_name = xml.attrib['displayname'] if 'displayname' in xml.attrib else self.name |
| self.meta = {} |
| |
| # Used for generated encoder, to de-duplicate encoding for |
| # similar instructions: |
| self.snippets = {} |
| |
| if 'size' in xml.attrib: |
| assert('extends' not in xml.attrib) |
| self.size = int(xml.attrib['size']) |
| self.extends = None |
| else: |
| self.size = None |
| self.extends = xml.attrib['extends'] |
| |
| self.encode = None |
| if xml.find('encode') is not None: |
| self.encode = BitSetEncode(xml.find('encode')) |
| self.decode = None |
| if xml.find('decode') is not None: |
| self.decode = BitSetDecode(xml.find('encode')) |
| |
| self.gen_min = 0 |
| self.gen_max = (1 << 32) - 1 |
| |
| for gen in xml.findall('gen'): |
| if 'min' in gen.attrib: |
| self.gen_min = int(gen.attrib['min']) |
| if 'max' in gen.attrib: |
| self.gen_max = int(gen.attrib['max']) |
| |
| for meta in xml.findall('meta'): |
| self.meta.update(meta.attrib) |
| |
| # Collect up the match/dontcare/mask bitmasks for |
| # this bitset case: |
| self.match = 0 |
| self.dontcare = 0 |
| self.mask = 0 |
| self.field_mask = 0 |
| |
| self.cases = [] |
| |
| # Helper to check for redefined bits: |
| def is_defined_bits(m): |
| return ((self.field_mask | self.mask | self.dontcare | self.match) & m) != 0 |
| |
| def update_default_bitmask_field(bs, field): |
| m = field.mask() |
| dbg("field: {}.{} => {:016x}".format(self.name, field.name, m)) |
| # For default case, we don't expect any bits to be doubly defined: |
| assert not is_defined_bits(m), "Redefined bits in field {}.{}: {}..{}".format( |
| self.name, field.name, field.low, field.high) |
| self.field_mask |= m |
| |
| def update_override_bitmask_field(bs, field): |
| m = field.mask() |
| dbg("field: {}.{} => {:016x}".format(self.name, field.name, m)) |
| assert self.field_mask ^ ~m |
| |
| dflt = BitSetCase(self, xml, update_default_bitmask_field) |
| |
| for override in xml.findall('override'): |
| if 'expr' in override.attrib: |
| expr = override.attrib['expr'] |
| else: |
| e = isa.parse_one_expression(override, self.name) |
| expr = e.name |
| c = BitSetCase(self, override, update_override_bitmask_field, expr) |
| self.cases.append(c) |
| |
| # Default case is expected to be the last one: |
| self.cases.append(dflt) |
| |
| for pattern in xml.findall('pattern'): |
| match, dontcare, mask = extract_pattern(pattern, self.name, is_defined_bits) |
| |
| self.match |= match |
| self.dontcare |= dontcare |
| self.mask |= mask |
| |
| def get_pattern(self): |
| if self.extends is not None: |
| parent = self.isa.bitsets[self.extends] |
| ppat = parent.get_pattern() |
| pat = BitSetPattern(self) |
| |
| assert ((ppat.defined_bits() & pat.defined_bits()) == 0), "bitset conflict in {}: {:x}".format(self.name, (ppat.defined_bits() & pat.defined_bits())) |
| |
| return pat.merge(ppat) |
| |
| return BitSetPattern(self) |
| |
| def get_size(self): |
| if self.extends is not None: |
| parent = self.isa.bitsets[self.extends] |
| return parent.get_size() |
| return self.size |
| |
| def get_gen_min(self): |
| if self.extends is not None: |
| parent = self.isa.bitsets[self.extends] |
| |
| assert (self.gen_min == 0) or (self.gen_min >= parent.get_gen_min()), "bitset {} should not have min gen lower than the parent's one".format(self.name) |
| |
| return max(self.gen_min, parent.get_gen_min()) |
| return self.gen_min |
| |
| def get_gen_max(self): |
| if self.extends is not None: |
| parent = self.isa.bitsets[self.extends] |
| |
| assert (self.gen_max == (1 << 32) - 1) or (self.gen_max <= parent.get_gen_max()), "bitset {} should not have max gen higher than the parent's one".format(self.name) |
| |
| return min(self.gen_max, parent.get_gen_max()) |
| return self.gen_max |
| |
| def has_gen_restriction(self): |
| return self.gen_min != 0 or self.gen_max != (1 << 32) - 1 |
| |
| def get_c_name(self): |
| return get_c_name(self.name) |
| |
| def get_root(self): |
| if self.extends is not None: |
| return self.isa.bitsets[self.extends].get_root() |
| return self |
| |
| def get_meta(self): |
| meta = {} |
| |
| if self.extends is not None: |
| meta = self.isa.bitsets[self.extends].get_meta() |
| |
| if self.meta: |
| meta.update(self.meta) |
| |
| return meta |
| |
| class BitSetTemplate(object): |
| """Class that encapsulates a template declaration |
| """ |
| def __init__(self, isa, xml): |
| self.isa = isa |
| self.name = xml.attrib['name'] |
| self.display = xml.text.strip() |
| dbg("found template '{}: {}'".format(self.name, self.display)) |
| |
| class BitSetEnumValue(object): |
| """Class that encapsulates an enum value |
| """ |
| def __init__(self, isa, xml): |
| self.isa = isa |
| self.displayname = xml.attrib['display'] |
| self.value = xml.attrib['val'] |
| self.name = xml.attrib.get('name') |
| |
| def __str__(self): |
| return self.displayname |
| |
| def get_name(self): |
| return self.name or self.displayname |
| |
| def get_displayname(self): |
| return self.displayname or self.name |
| |
| def get_value(self): |
| return self.value |
| |
| class BitSetEnum(object): |
| """Class that encapsulates an enum declaration |
| """ |
| def __init__(self, isa, xml): |
| self.isa = isa |
| self.name = xml.attrib['name'] |
| |
| # Table mapping value to name |
| self.values = {} |
| for value in xml.findall('value'): |
| v = BitSetEnumValue(self, value) |
| self.values[v.get_value()] = v |
| |
| def get_c_name(self): |
| return 'enum_' + get_c_name(self.name) |
| |
| class BitSetExpression(object): |
| """Class that encapsulates an <expr> declaration |
| """ |
| def __init__(self, isa, xml): |
| self.isa = isa |
| if 'name' in xml.attrib: |
| self.name = xml.attrib['name'] |
| else: |
| self.name = 'anon_' + str(isa.anon_expression_count) |
| isa.anon_expression_count = isa.anon_expression_count + 1 |
| expr = xml.text.strip() |
| self.fieldnames = list(set(re.findall(r"{([a-zA-Z0-9_]+)}", expr))) |
| self.expr = re.sub(r"{([a-zA-Z0-9_]+)}", r"\1", expr) |
| dbg("'{}' -> '{}'".format(expr, self.expr)) |
| |
| def get_c_name(self): |
| return 'expr_' + get_c_name(self.name) |
| |
| class ISA(object): |
| """Class that encapsulates all the parsed bitset rules |
| """ |
| def __init__(self, xmlpath): |
| self.base_path = os.path.dirname(xmlpath) |
| |
| # Counter used to name inline (anonymous) expressions: |
| self.anon_expression_count = 0 |
| |
| # Table of (globally defined) expressions: |
| self.expressions = {} |
| |
| # Table of templates: |
| self.templates = {} |
| |
| # Table of enums: |
| self.enums = {} |
| |
| # Table of toplevel bitset hierarchies: |
| self.roots = {} |
| |
| # Table of leaf nodes of bitset hierarchies: |
| # Note that there may be multiple leaves for a particular name |
| # (distinguished by gen), so the values here are lists. |
| self.leafs = {} |
| |
| # Table of all non-ambiguous bitsets (i.e. no per-gen ambiguity): |
| self.bitsets = {} |
| |
| # Max needed bitsize for one instruction |
| self.bitsize = 0 |
| |
| root = ElementTree.parse(xmlpath).getroot() |
| self.parse_file(root) |
| self.validate_isa() |
| |
| def parse_expressions(self, root): |
| e = None |
| for expr in root.findall('expr'): |
| e = BitSetExpression(self, expr) |
| self.expressions[e.name] = e |
| return e |
| |
| def parse_one_expression(self, root, name): |
| assert len(root.findall('expr')) == 1, "expected a single expression in: {}".format(name) |
| return self.parse_expressions(root) |
| |
| def parse_file(self, root): |
| # Handle imports up-front: |
| for imprt in root.findall('import'): |
| p = os.path.join(self.base_path, imprt.attrib['file']) |
| self.parse_file(ElementTree.parse(p)) |
| |
| # Extract expressions: |
| self.parse_expressions(root) |
| |
| # Extract templates: |
| for template in root.findall('template'): |
| t = BitSetTemplate(self, template) |
| self.templates[t.name] = t |
| |
| # Extract enums: |
| for enum in root.findall('enum'): |
| e = BitSetEnum(self, enum) |
| self.enums[e.name] = e |
| |
| # Extract bitsets: |
| for bitset in root.findall('bitset'): |
| b = BitSet(self, bitset) |
| if b.size is not None: |
| dbg("toplevel: " + b.name) |
| self.roots[b.name] = b |
| self.bitsize = max(self.bitsize, b.size) |
| else: |
| dbg("derived: " + b.name) |
| self.bitsets[b.name] = b |
| self.leafs.setdefault(b.name, []).append(b) |
| |
| # Resolve all templates: |
| for _, bitset in self.bitsets.items(): |
| for case in bitset.cases: |
| if case.display: |
| case.display = self.resolve_templates(case.display) |
| |
| def validate_isa(self): |
| # We only support multiples of 32 bits for now |
| assert self.bitsize % 32 == 0 |
| |
| # Do one-time fixups |
| # Remove non-leaf nodes from the leafs table: |
| for name, bitsets in list(self.leafs.items()): |
| for bitset in bitsets: |
| if bitset.extends in self.leafs: |
| del self.leafs[bitset.extends] |
| |
| # Fix multi-gen leaves in bitsets |
| for name, bitsets in self.leafs.items(): |
| if len(bitsets) == 1: |
| continue |
| |
| del self.bitsets[name] |
| |
| # Validate that all bitset fields have valid types, and in |
| # the case of bitset type, the sizes match: |
| builtin_types = ['branch', 'absbranch', 'int', 'uint', 'hex', 'offset', 'uoffset', 'float', 'bool', 'bool_inv', 'enum', 'custom'] |
| for bitset_name, bitset in self.bitsets.items(): |
| if bitset.extends is not None: |
| assert bitset.extends in self.bitsets, "{} extends invalid type: {}".format( |
| bitset_name, bitset.extends) |
| for case in bitset.cases: |
| for field_name, field in case.fields.items(): |
| if field.type == 'float': |
| assert field.get_size() == 32 or field.get_size() == 16 |
| |
| if not isinstance(field, BitSetDerivedField): |
| assert field.high < bitset.get_size(), \ |
| "{}.{}: invalid bit range: [{}, {}] is not in [{}, {}]".format( |
| bitset_name, field_name, field.low, field.high, 0, bitset.get_size() - 1) |
| |
| if field.type in builtin_types: |
| continue |
| if field.type in self.enums: |
| continue |
| assert field.type in self.bitsets, "{}.{}: invalid type: {}".format( |
| bitset_name, field_name, field.type) |
| bs = self.bitsets[field.type] |
| assert field.get_size() == bs.get_size(), "{}.{}: invalid size: {} vs {}".format( |
| bitset_name, field_name, field.get_size(), bs.get_size()) |
| |
| # Validate that all the leaf node bitsets have no remaining |
| # undefined bits |
| for name, bitsets in self.leafs.items(): |
| for bitset in bitsets: |
| pat = bitset.get_pattern() |
| sz = bitset.get_size() |
| assert ((pat.mask | pat.field_mask) == (1 << sz) - 1), "leaf bitset {} has undefined bits: {:x}".format( |
| bitset.name, ~(pat.mask | pat.field_mask) & ((1 << sz) - 1)) |
| |
| # TODO somehow validating that only one bitset in a hierarchy |
| # matches any given bit pattern would be useful. |
| |
| # TODO we should probably be able to look at the contexts where |
| # an expression is evaluated and verify that it doesn't have any |
| # {VARNAME} references that would be unresolved at evaluation time |
| |
| def format(self): |
| ''' Generate format string used by printf(..) and friends ''' |
| parts = [] |
| words = self.bitsize / 32 |
| |
| for i in range(int(words)): |
| parts.append('%08x') |
| |
| fmt = ''.join(parts) |
| |
| return f"\"{fmt[1:]}\"" |
| |
| def value(self): |
| ''' Generate format values used by printf(..) and friends ''' |
| parts = [] |
| words = self.bitsize / 32 |
| |
| for i in range(int(words) - 1, -1, -1): |
| parts.append('v[' + str(i) + ']') |
| |
| return ', '.join(parts) |
| |
| def split_bits(self, value, bitsize): |
| ''' Split `value` into a list of bitsize-bit integers ''' |
| mask, parts = (1 << bitsize) - 1, [] |
| words = self.bitsize / bitsize |
| |
| while value: |
| parts.append(hex(value & mask)) |
| value >>= bitsize |
| |
| # Add 'missing' words |
| while len(parts) < words: |
| parts.append('0x0') |
| |
| return parts |
| |
| # Returns all bitsets in the ISA, including all per-gen variants, in |
| # (name, bitset) pairs. |
| def all_bitsets(self): |
| for name, bitset in self.bitsets.items(): |
| yield name, bitset |
| for name, bitsets in self.leafs.items(): |
| if len(bitsets) == 1: |
| continue |
| for bitset in bitsets: |
| yield name, bitset |
| |
| def resolve_templates(self, display_string): |
| matches = re.findall(r'\{([^\}]+)\}', display_string) |
| for m in matches: |
| if m in self.templates: |
| display_string = display_string.replace("{" + m + "}", self.templates[m].display) |
| |
| return display_string |
| |
| def instructions(self): |
| instr = [] |
| |
| for _, root in self.roots.items(): |
| for _, leafs in self.leafs.items(): |
| for leaf in leafs: |
| if leaf.get_root() == root: |
| if not leaf.get_c_name().startswith('__'): |
| instr.append(leaf) |
| |
| return instr |
