| Message ID | 1581381644-13678-29-git-send-email-tsimpson@quicinc.com |
|---|---|
| State | New |
| Headers | show |
| Series | Hexagon patch series | expand |
On 2/11/20 1:40 AM, Taylor Simpson wrote: > Python script that emits the decode tree in dectree_generated.h. > > Signed-off-by: Taylor Simpson <tsimpson@quicinc.com> > --- > target/hexagon/dectree.py | 354 ++++++++++++++++++++++++++++++++++++++++++++++ > 1 file changed, 354 insertions(+) > create mode 100755 target/hexagon/dectree.py > > diff --git a/target/hexagon/dectree.py b/target/hexagon/dectree.py > new file mode 100755 > index 0000000..a0435c9 > --- /dev/null > +++ b/target/hexagon/dectree.py > @@ -0,0 +1,354 @@ > +#!/usr/bin/env python python3 > + > +from __future__ import print_function Not needed anymore. > +## > +## Copyright (c) 2019 Qualcomm Innovation Center, Inc. All Rights Reserved. > +## > +## This program is free software; you can redistribute it and/or modify > +## it under the terms of the GNU General Public License as published by > +## the Free Software Foundation; either version 2 of the License, or > +## (at your option) any later version. > +## > +## This program 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 General Public License for more details. > +## > +## You should have received a copy of the GNU General Public License > +## along with this program; if not, see <http://www.gnu.org/licenses/>. > +## > + > +import cStringIO > +import re > + > +import sys > +sys.path.insert(0, sys.argv[1]) > +import iset > + > +encs = {tag : ''.join(reversed(iset.iset[tag]['enc'].replace(' ', ''))) > + for tag in iset.tags if iset.iset[tag]['enc'] != 'MISSING ENCODING'} > + > +enc_classes = set([iset.iset[tag]['enc_class'] for tag in encs.keys()]) > +subinsn_enc_classes = \ > + set([enc_class for enc_class in enc_classes \ > + if enc_class.startswith('SUBINSN_')]) > +ext_enc_classes = \ > + set([enc_class for enc_class in enc_classes \ > + if enc_class not in ('NORMAL', '16BIT') and \ > + not enc_class.startswith('SUBINSN_')]) > + > +try: > + subinsn_groupings = iset.subinsn_groupings > +except AttributeError: > + subinsn_groupings = {} > + > +for (tag, subinsn_grouping) in subinsn_groupings.items(): > + encs[tag] = ''.join(reversed(subinsn_grouping['enc'].replace(' ', ''))) > + > +dectree_normal = {'leaves' : set()} > +dectree_16bit = {'leaves' : set()} > +dectree_subinsn_groupings = {'leaves' : set()} > +dectree_subinsns = {name : {'leaves' : set()} for name in subinsn_enc_classes} > +dectree_extensions = {name : {'leaves' : set()} for name in ext_enc_classes} > + > +for tag in encs.keys(): > + if tag in subinsn_groupings: > + dectree_subinsn_groupings['leaves'].add(tag) > + continue > + enc_class = iset.iset[tag]['enc_class'] > + if enc_class.startswith('SUBINSN_'): > + if len(encs[tag]) != 32: > + encs[tag] = encs[tag] + '0' * (32 - len(encs[tag])) > + dectree_subinsns[enc_class]['leaves'].add(tag) > + elif enc_class == '16BIT': > + if len(encs[tag]) != 16: > + raise Exception('Tag "{}" has enc_class "{}" and not an encoding ' + > + 'width of 16 bits!'.format(tag, enc_class)) > + dectree_16bit['leaves'].add(tag) > + else: > + if len(encs[tag]) != 32: > + raise Exception('Tag "{}" has enc_class "{}" and not an encoding ' + > + 'width of 32 bits!'.format(tag, enc_class)) > + if enc_class == 'NORMAL': > + dectree_normal['leaves'].add(tag) > + else: > + dectree_extensions[enc_class]['leaves'].add(tag) > + > +faketags = set() > +for (tag, enc) in iset.enc_ext_spaces.items(): > + faketags.add(tag) > + encs[tag] = ''.join(reversed(enc.replace(' ', ''))) > + dectree_normal['leaves'].add(tag) > + > +faketags |= set(subinsn_groupings.keys()) > + > +def every_bit_counts(bitset): > + for i in range(1, len(next(iter(bitset)))): > + if len(set([bits[:i] + bits[i+1:] for bits in bitset])) == len(bitset): > + return False > + return True > + > +def auto_separate(node): > + tags = node['leaves'] > + if len(tags) <= 1: > + return > + enc_width = len(encs[next(iter(tags))]) > + opcode_bit_for_all = \ > + [all([encs[tag][i] in '01' \ > + for tag in tags]) for i in range(enc_width)] > + opcode_bit_is_0_for_all = \ > + [opcode_bit_for_all[i] and all([encs[tag][i] == '0' \ > + for tag in tags]) for i in range(enc_width)] > + opcode_bit_is_1_for_all = \ > + [opcode_bit_for_all[i] and all([encs[tag][i] == '1' \ > + for tag in tags]) for i in range(enc_width)] > + differentiator_opcode_bit = \ > + [opcode_bit_for_all[i] and \ > + not (opcode_bit_is_0_for_all[i] or \ > + opcode_bit_is_1_for_all[i]) \ > + for i in range(enc_width)] > + best_width = 0 > + for width in range(4, 0, -1): > + for lsb in range(enc_width - width, -1, -1): > + bitset = set([encs[tag][lsb:lsb+width] for tag in tags]) > + if all(differentiator_opcode_bit[lsb:lsb+width]) and \ > + (len(bitset) == len(tags) or every_bit_counts(bitset)): > + best_width = width > + best_lsb = lsb > + caught_all_tags = len(bitset) == len(tags) > + break > + if best_width != 0: > + break > + if best_width == 0: > + raise Exception('Could not find a way to differentiate the encodings ' + > + 'of the following tags:\n{}'.format('\n'.join(tags))) > + if caught_all_tags: > + for width in range(1, best_width): > + for lsb in range(enc_width - width, -1, -1): > + bitset = set([encs[tag][lsb:lsb+width] for tag in tags]) > + if all(differentiator_opcode_bit[lsb:lsb+width]) and \ > + len(bitset) == len(tags): > + best_width = width > + best_lsb = lsb > + break > + else: > + continue > + break > + node['separator_lsb'] = best_lsb > + node['separator_width'] = best_width > + node['children'] = [] > + for value in range(2 ** best_width): > + child = {} > + bits = ''.join(reversed('{:0{}b}'.format(value, best_width))) > + child['leaves'] = \ > + set([tag for tag in tags \ > + if encs[tag][best_lsb:best_lsb+best_width] == bits]) > + node['children'].append(child) > + for child in node['children']: > + auto_separate(child) > + > +auto_separate(dectree_normal) > +auto_separate(dectree_16bit) > +if subinsn_groupings: > + auto_separate(dectree_subinsn_groupings) > +for dectree_subinsn in dectree_subinsns.values(): > + auto_separate(dectree_subinsn) > +for dectree_ext in dectree_extensions.values(): > + auto_separate(dectree_ext) > + > +for tag in faketags: > + del encs[tag] > + > +def table_name(parents, node): > + path = parents + [node] > + root = path[0] > + tag = next(iter(node['leaves'])) > + if tag in subinsn_groupings: > + enc_width = len(subinsn_groupings[tag]['enc'].replace(' ', '')) > + else: > + tag = next(iter(node['leaves'] - faketags)) > + enc_width = len(encs[tag]) > + determining_bits = ['_'] * enc_width > + for (parent, child) in zip(path[:-1], path[1:]): > + lsb = parent['separator_lsb'] > + width = parent['separator_width'] > + value = parent['children'].index(child) > + determining_bits[lsb:lsb+width] = \ > + list(reversed('{:0{}b}'.format(value, width))) > + if tag in subinsn_groupings: > + name = 'DECODE_ROOT_EE' > + else: > + enc_class = iset.iset[tag]['enc_class'] > + if enc_class in ext_enc_classes: > + name = 'DECODE_EXT_{}'.format(enc_class) > + elif enc_class in subinsn_enc_classes: > + name = 'DECODE_SUBINSN_{}'.format(enc_class) > + else: > + name = 'DECODE_ROOT_{}'.format(enc_width) > + if node != root: > + name += '_' + ''.join(reversed(determining_bits)) > + return name > + > +def print_node(f, node, parents): > + if len(node['leaves']) <= 1: > + return > + name = table_name(parents, node) > + lsb = node['separator_lsb'] > + width = node['separator_width'] > + print('DECODE_NEW_TABLE({},{},DECODE_SEPARATOR_BITS({},{}))'.\ > + format(name, 2 ** width, lsb, width), file=f) > + for child in node['children']: > + if len(child['leaves']) == 0: > + print('INVALID()', file=f) > + elif len(child['leaves']) == 1: > + (tag,) = child['leaves'] > + if tag in subinsn_groupings: > + class_a = subinsn_groupings[tag]['class_a'] > + class_b = subinsn_groupings[tag]['class_b'] > + enc = subinsn_groupings[tag]['enc'].replace(' ', '') > + if 'RESERVED' in tag: > + print('INVALID()', file=f) > + else: > + print('SUBINSNS({},{},{},"{}")'.\ > + format(tag, class_a, class_b, enc), file=f) > + elif tag in iset.enc_ext_spaces: > + enc = iset.enc_ext_spaces[tag].replace(' ', '') > + print('EXTSPACE({},"{}")'.format(tag, enc), file=f) > + else: > + enc = ''.join(reversed(encs[tag])) > + print('TERMINAL({},"{}")'.format(tag, enc), file=f) > + else: > + print('TABLE_LINK({})'.format(table_name(parents + [node], child)), > + file=f) > + print('DECODE_END_TABLE({},{},DECODE_SEPARATOR_BITS({},{}))'.\ > + format(name, 2 ** width, lsb, width), file=f) > + print(file=f) > + parents.append(node) > + for child in node['children']: > + print_node(f, child, parents) > + parents.pop() > + > +def print_tree(f, tree): > + print_node(f, tree, []) > + > +def print_match_info(f): > + for tag in sorted(encs.keys(), key=iset.tags.index): > + enc = ''.join(reversed(encs[tag])) > + mask = int(re.sub(r'[^1]', r'0', enc.replace('0', '1')), 2) > + match = int(re.sub(r'[^01]', r'0', enc), 2) > + suffix = '' > + print('DECODE{}_MATCH_INFO({},0x{:x}U,0x{:x}U)'.\ > + format(suffix, tag, mask, match), file=f) > + > +regre = re.compile( > + r'((?<!DUP)[MNORCPQXSGVZA])([stuvwxyzdefg]+)([.]?[LlHh]?)(\d+S?)') > +immre = re.compile(r'[#]([rRsSuUm])(\d+)(?:[:](\d+))?') > + > +def ordered_unique(l): > + return sorted(set(l), key=l.index) > + > +implicit_registers = { > + 'SP' : 29, > + 'FP' : 30, > + 'LR' : 31 > +} > + > +num_registers = { > + 'R' : 32, > + 'V' : 32 > +} > + > +def print_op_info(f): > + for tag in sorted(encs.keys(), key=iset.tags.index): > + enc = encs[tag] > + print(file=f) > + print('DECODE_OPINFO({},'.format(tag), file=f) > + regs = ordered_unique(regre.findall(iset.iset[tag]['syntax'])) > + imms = ordered_unique(immre.findall(iset.iset[tag]['syntax'])) > + regno = 0 > + for reg in regs: > + reg_type = reg[0] > + reg_letter = reg[1][0] > + reg_num_choices = int(reg[3].rstrip('S')) > + reg_mapping = reg[0] + ''.join(['_' for letter in reg[1]]) + reg[3] > + reg_enc_fields = re.findall(reg_letter + '+', enc) > + if len(reg_enc_fields) == 0: > + raise Exception('Tag "{}" missing register field!'.format(tag)) > + if len(reg_enc_fields) > 1: > + raise Exception('Tag "{}" has split register field!'.\ > + format(tag)) > + reg_enc_field = reg_enc_fields[0] > + if 2 ** len(reg_enc_field) != reg_num_choices: > + raise Exception('Tag "{}" has incorrect register field width!'.\ > + format(tag)) > + print(' DECODE_REG({},{},{})'.\ > + format(regno, len(reg_enc_field), enc.index(reg_enc_field)), > + file=f) > + if reg_type in num_registers and \ > + reg_num_choices != num_registers[reg_type]: > + print(' DECODE_MAPPED_REG({},{})'.\ > + format(regno, reg_mapping), file=f) > + regno += 1 > + def implicit_register_key(reg): > + return implicit_registers[reg] > + for reg in sorted( > + set([r for r in (iset.iset[tag]['rregs'].split(',') + \ > + iset.iset[tag]['wregs'].split(',')) \ > + if r in implicit_registers]), key=implicit_register_key): > + print(' DECODE_IMPL_REG({},{})'.\ > + format(regno, implicit_registers[reg]), file=f) > + regno += 1 > + if imms and imms[0][0].isupper(): > + imms = reversed(imms) > + for imm in imms: > + if imm[0].isupper(): > + immno = 1 > + else: > + immno = 0 > + imm_type = imm[0] > + imm_width = int(imm[1]) > + imm_shift = imm[2] > + if imm_shift: > + imm_shift = int(imm_shift) > + else: > + imm_shift = 0 > + if imm_type.islower(): > + imm_letter = 'i' > + else: > + imm_letter = 'I' > + remainder = imm_width > + for m in reversed(list(re.finditer(imm_letter + '+', enc))): > + remainder -= m.end() - m.start() > + print(' DECODE_IMM({},{},{},{})'.\ > + format(immno, m.end() - m.start(), m.start(), remainder), > + file=f) > + if remainder != 0: > + if imm[2]: > + imm[2] = ':' + imm[2] > + raise Exception('Tag "{}" has an incorrect number of ' + \ > + 'encoding bits for immediate "{}"'.\ > + format(tag, ''.join(imm))) > + if imm_type.lower() in 'sr': > + print(' DECODE_IMM_SXT({},{})'.\ > + format(immno, imm_width), file=f) > + if imm_type.lower() == 'n': > + print(' DECODE_IMM_NEG({},{})'.\ > + format(immno, imm_width), file=f) > + if imm_shift: > + print(' DECODE_IMM_SHIFT({},{})'.\ > + format(immno, imm_shift), file=f) > + print(')', file=f) > + > +if __name__ == '__main__': > + f = cStringIO.StringIO() > + print_tree(f, dectree_normal) > + print_tree(f, dectree_16bit) > + if subinsn_groupings: > + print_tree(f, dectree_subinsn_groupings) > + for (name, dectree_subinsn) in sorted(dectree_subinsns.items()): > + print_tree(f, dectree_subinsn) > + for (name, dectree_ext) in sorted(dectree_extensions.items()): > + print_tree(f, dectree_ext) > + print_match_info(f) > + print_op_info(f) > + open('dectree_generated.h', 'w').write(f.getvalue()) > Tested-by: Philippe Mathieu-Daudé <philmd@redhat.com>
On 2/11/20 8:37 AM, Philippe Mathieu-Daudé wrote: > On 2/11/20 1:40 AM, Taylor Simpson wrote: >> Python script that emits the decode tree in dectree_generated.h. >> >> Signed-off-by: Taylor Simpson <tsimpson@quicinc.com> >> --- >> target/hexagon/dectree.py | 354 >> ++++++++++++++++++++++++++++++++++++++++++++++ >> 1 file changed, 354 insertions(+) >> create mode 100755 target/hexagon/dectree.py >> >> diff --git a/target/hexagon/dectree.py b/target/hexagon/dectree.py >> new file mode 100755 >> index 0000000..a0435c9 >> --- /dev/null >> +++ b/target/hexagon/dectree.py >> @@ -0,0 +1,354 @@ >> +#!/usr/bin/env python > > python3 > >> + >> +from __future__ import print_function > > Not needed anymore. > >> +## >> +## Copyright (c) 2019 Qualcomm Innovation Center, Inc. All Rights >> Reserved. >> +## >> +## This program is free software; you can redistribute it and/or modify >> +## it under the terms of the GNU General Public License as published by >> +## the Free Software Foundation; either version 2 of the License, or >> +## (at your option) any later version. >> +## >> +## This program 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 General Public License for more details. >> +## >> +## You should have received a copy of the GNU General Public License >> +## along with this program; if not, see <http://www.gnu.org/licenses/>. >> +## >> + >> +import cStringIO Another Python 3 failure: GEN Hexagon decode tree Traceback (most recent call last): File "target/hexagon/dectree.py", line 20, in <module> import cStringIO ModuleNotFoundError: No module named 'cStringIO' >> +import re >> + >> +import sys >> +sys.path.insert(0, sys.argv[1]) >> +import iset >> + >> +encs = {tag : ''.join(reversed(iset.iset[tag]['enc'].replace(' ', ''))) >> + for tag in iset.tags if iset.iset[tag]['enc'] != 'MISSING ENCODING'} >> + >> +enc_classes = set([iset.iset[tag]['enc_class'] for tag in encs.keys()]) >> +subinsn_enc_classes = \ >> + set([enc_class for enc_class in enc_classes \ >> + if enc_class.startswith('SUBINSN_')]) >> +ext_enc_classes = \ >> + set([enc_class for enc_class in enc_classes \ >> + if enc_class not in ('NORMAL', '16BIT') and \ >> + not enc_class.startswith('SUBINSN_')]) >> + >> +try: >> + subinsn_groupings = iset.subinsn_groupings >> +except AttributeError: >> + subinsn_groupings = {} >> + >> +for (tag, subinsn_grouping) in subinsn_groupings.items(): >> + encs[tag] = ''.join(reversed(subinsn_grouping['enc'].replace(' ', >> ''))) >> + >> +dectree_normal = {'leaves' : set()} >> +dectree_16bit = {'leaves' : set()} >> +dectree_subinsn_groupings = {'leaves' : set()} >> +dectree_subinsns = {name : {'leaves' : set()} for name in >> subinsn_enc_classes} >> +dectree_extensions = {name : {'leaves' : set()} for name in >> ext_enc_classes} >> + >> +for tag in encs.keys(): >> + if tag in subinsn_groupings: >> + dectree_subinsn_groupings['leaves'].add(tag) >> + continue >> + enc_class = iset.iset[tag]['enc_class'] >> + if enc_class.startswith('SUBINSN_'): >> + if len(encs[tag]) != 32: >> + encs[tag] = encs[tag] + '0' * (32 - len(encs[tag])) >> + dectree_subinsns[enc_class]['leaves'].add(tag) >> + elif enc_class == '16BIT': >> + if len(encs[tag]) != 16: >> + raise Exception('Tag "{}" has enc_class "{}" and not an >> encoding ' + >> + 'width of 16 bits!'.format(tag, enc_class)) >> + dectree_16bit['leaves'].add(tag) >> + else: >> + if len(encs[tag]) != 32: >> + raise Exception('Tag "{}" has enc_class "{}" and not an >> encoding ' + >> + 'width of 32 bits!'.format(tag, enc_class)) >> + if enc_class == 'NORMAL': >> + dectree_normal['leaves'].add(tag) >> + else: >> + dectree_extensions[enc_class]['leaves'].add(tag) >> + >> +faketags = set() >> +for (tag, enc) in iset.enc_ext_spaces.items(): >> + faketags.add(tag) >> + encs[tag] = ''.join(reversed(enc.replace(' ', ''))) >> + dectree_normal['leaves'].add(tag) >> + >> +faketags |= set(subinsn_groupings.keys()) >> + >> +def every_bit_counts(bitset): >> + for i in range(1, len(next(iter(bitset)))): >> + if len(set([bits[:i] + bits[i+1:] for bits in bitset])) == >> len(bitset): >> + return False >> + return True >> + >> +def auto_separate(node): >> + tags = node['leaves'] >> + if len(tags) <= 1: >> + return >> + enc_width = len(encs[next(iter(tags))]) >> + opcode_bit_for_all = \ >> + [all([encs[tag][i] in '01' \ >> + for tag in tags]) for i in range(enc_width)] >> + opcode_bit_is_0_for_all = \ >> + [opcode_bit_for_all[i] and all([encs[tag][i] == '0' \ >> + for tag in tags]) for i in range(enc_width)] >> + opcode_bit_is_1_for_all = \ >> + [opcode_bit_for_all[i] and all([encs[tag][i] == '1' \ >> + for tag in tags]) for i in range(enc_width)] >> + differentiator_opcode_bit = \ >> + [opcode_bit_for_all[i] and \ >> + not (opcode_bit_is_0_for_all[i] or \ >> + opcode_bit_is_1_for_all[i]) \ >> + for i in range(enc_width)] >> + best_width = 0 >> + for width in range(4, 0, -1): >> + for lsb in range(enc_width - width, -1, -1): >> + bitset = set([encs[tag][lsb:lsb+width] for tag in tags]) >> + if all(differentiator_opcode_bit[lsb:lsb+width]) and \ >> + (len(bitset) == len(tags) or every_bit_counts(bitset)): >> + best_width = width >> + best_lsb = lsb >> + caught_all_tags = len(bitset) == len(tags) >> + break >> + if best_width != 0: >> + break >> + if best_width == 0: >> + raise Exception('Could not find a way to differentiate the >> encodings ' + >> + 'of the following >> tags:\n{}'.format('\n'.join(tags))) >> + if caught_all_tags: >> + for width in range(1, best_width): >> + for lsb in range(enc_width - width, -1, -1): >> + bitset = set([encs[tag][lsb:lsb+width] for tag in tags]) >> + if all(differentiator_opcode_bit[lsb:lsb+width]) and \ >> + len(bitset) == len(tags): >> + best_width = width >> + best_lsb = lsb >> + break >> + else: >> + continue >> + break >> + node['separator_lsb'] = best_lsb >> + node['separator_width'] = best_width >> + node['children'] = [] >> + for value in range(2 ** best_width): >> + child = {} >> + bits = ''.join(reversed('{:0{}b}'.format(value, best_width))) >> + child['leaves'] = \ >> + set([tag for tag in tags \ >> + if encs[tag][best_lsb:best_lsb+best_width] == bits]) >> + node['children'].append(child) >> + for child in node['children']: >> + auto_separate(child) >> + >> +auto_separate(dectree_normal) >> +auto_separate(dectree_16bit) >> +if subinsn_groupings: >> + auto_separate(dectree_subinsn_groupings) >> +for dectree_subinsn in dectree_subinsns.values(): >> + auto_separate(dectree_subinsn) >> +for dectree_ext in dectree_extensions.values(): >> + auto_separate(dectree_ext) >> + >> +for tag in faketags: >> + del encs[tag] >> + >> +def table_name(parents, node): >> + path = parents + [node] >> + root = path[0] >> + tag = next(iter(node['leaves'])) >> + if tag in subinsn_groupings: >> + enc_width = len(subinsn_groupings[tag]['enc'].replace(' ', '')) >> + else: >> + tag = next(iter(node['leaves'] - faketags)) >> + enc_width = len(encs[tag]) >> + determining_bits = ['_'] * enc_width >> + for (parent, child) in zip(path[:-1], path[1:]): >> + lsb = parent['separator_lsb'] >> + width = parent['separator_width'] >> + value = parent['children'].index(child) >> + determining_bits[lsb:lsb+width] = \ >> + list(reversed('{:0{}b}'.format(value, width))) >> + if tag in subinsn_groupings: >> + name = 'DECODE_ROOT_EE' >> + else: >> + enc_class = iset.iset[tag]['enc_class'] >> + if enc_class in ext_enc_classes: >> + name = 'DECODE_EXT_{}'.format(enc_class) >> + elif enc_class in subinsn_enc_classes: >> + name = 'DECODE_SUBINSN_{}'.format(enc_class) >> + else: >> + name = 'DECODE_ROOT_{}'.format(enc_width) >> + if node != root: >> + name += '_' + ''.join(reversed(determining_bits)) >> + return name >> + >> +def print_node(f, node, parents): >> + if len(node['leaves']) <= 1: >> + return >> + name = table_name(parents, node) >> + lsb = node['separator_lsb'] >> + width = node['separator_width'] >> + print('DECODE_NEW_TABLE({},{},DECODE_SEPARATOR_BITS({},{}))'.\ >> + format(name, 2 ** width, lsb, width), file=f) >> + for child in node['children']: >> + if len(child['leaves']) == 0: >> + print('INVALID()', file=f) >> + elif len(child['leaves']) == 1: >> + (tag,) = child['leaves'] >> + if tag in subinsn_groupings: >> + class_a = subinsn_groupings[tag]['class_a'] >> + class_b = subinsn_groupings[tag]['class_b'] >> + enc = subinsn_groupings[tag]['enc'].replace(' ', '') >> + if 'RESERVED' in tag: >> + print('INVALID()', file=f) >> + else: >> + print('SUBINSNS({},{},{},"{}")'.\ >> + format(tag, class_a, class_b, enc), file=f) >> + elif tag in iset.enc_ext_spaces: >> + enc = iset.enc_ext_spaces[tag].replace(' ', '') >> + print('EXTSPACE({},"{}")'.format(tag, enc), file=f) >> + else: >> + enc = ''.join(reversed(encs[tag])) >> + print('TERMINAL({},"{}")'.format(tag, enc), file=f) >> + else: >> + print('TABLE_LINK({})'.format(table_name(parents + >> [node], child)), >> + file=f) >> + print('DECODE_END_TABLE({},{},DECODE_SEPARATOR_BITS({},{}))'.\ >> + format(name, 2 ** width, lsb, width), file=f) >> + print(file=f) >> + parents.append(node) >> + for child in node['children']: >> + print_node(f, child, parents) >> + parents.pop() >> + >> +def print_tree(f, tree): >> + print_node(f, tree, []) >> + >> +def print_match_info(f): >> + for tag in sorted(encs.keys(), key=iset.tags.index): >> + enc = ''.join(reversed(encs[tag])) >> + mask = int(re.sub(r'[^1]', r'0', enc.replace('0', '1')), 2) >> + match = int(re.sub(r'[^01]', r'0', enc), 2) >> + suffix = '' >> + print('DECODE{}_MATCH_INFO({},0x{:x}U,0x{:x}U)'.\ >> + format(suffix, tag, mask, match), file=f) >> + >> +regre = re.compile( >> + r'((?<!DUP)[MNORCPQXSGVZA])([stuvwxyzdefg]+)([.]?[LlHh]?)(\d+S?)') >> +immre = re.compile(r'[#]([rRsSuUm])(\d+)(?:[:](\d+))?') >> + >> +def ordered_unique(l): >> + return sorted(set(l), key=l.index) >> + >> +implicit_registers = { >> + 'SP' : 29, >> + 'FP' : 30, >> + 'LR' : 31 >> +} >> + >> +num_registers = { >> + 'R' : 32, >> + 'V' : 32 >> +} >> + >> +def print_op_info(f): >> + for tag in sorted(encs.keys(), key=iset.tags.index): >> + enc = encs[tag] >> + print(file=f) >> + print('DECODE_OPINFO({},'.format(tag), file=f) >> + regs = ordered_unique(regre.findall(iset.iset[tag]['syntax'])) >> + imms = ordered_unique(immre.findall(iset.iset[tag]['syntax'])) >> + regno = 0 >> + for reg in regs: >> + reg_type = reg[0] >> + reg_letter = reg[1][0] >> + reg_num_choices = int(reg[3].rstrip('S')) >> + reg_mapping = reg[0] + ''.join(['_' for letter in >> reg[1]]) + reg[3] >> + reg_enc_fields = re.findall(reg_letter + '+', enc) >> + if len(reg_enc_fields) == 0: >> + raise Exception('Tag "{}" missing register >> field!'.format(tag)) >> + if len(reg_enc_fields) > 1: >> + raise Exception('Tag "{}" has split register field!'.\ >> + format(tag)) >> + reg_enc_field = reg_enc_fields[0] >> + if 2 ** len(reg_enc_field) != reg_num_choices: >> + raise Exception('Tag "{}" has incorrect register >> field width!'.\ >> + format(tag)) >> + print(' DECODE_REG({},{},{})'.\ >> + format(regno, len(reg_enc_field), >> enc.index(reg_enc_field)), >> + file=f) >> + if reg_type in num_registers and \ >> + reg_num_choices != num_registers[reg_type]: >> + print(' DECODE_MAPPED_REG({},{})'.\ >> + format(regno, reg_mapping), file=f) >> + regno += 1 >> + def implicit_register_key(reg): >> + return implicit_registers[reg] >> + for reg in sorted( >> + set([r for r in (iset.iset[tag]['rregs'].split(',') + \ >> + iset.iset[tag]['wregs'].split(',')) \ >> + if r in implicit_registers]), >> key=implicit_register_key): >> + print(' DECODE_IMPL_REG({},{})'.\ >> + format(regno, implicit_registers[reg]), file=f) >> + regno += 1 >> + if imms and imms[0][0].isupper(): >> + imms = reversed(imms) >> + for imm in imms: >> + if imm[0].isupper(): >> + immno = 1 >> + else: >> + immno = 0 >> + imm_type = imm[0] >> + imm_width = int(imm[1]) >> + imm_shift = imm[2] >> + if imm_shift: >> + imm_shift = int(imm_shift) >> + else: >> + imm_shift = 0 >> + if imm_type.islower(): >> + imm_letter = 'i' >> + else: >> + imm_letter = 'I' >> + remainder = imm_width >> + for m in reversed(list(re.finditer(imm_letter + '+', enc))): >> + remainder -= m.end() - m.start() >> + print(' DECODE_IMM({},{},{},{})'.\ >> + format(immno, m.end() - m.start(), m.start(), >> remainder), >> + file=f) >> + if remainder != 0: >> + if imm[2]: >> + imm[2] = ':' + imm[2] >> + raise Exception('Tag "{}" has an incorrect number of >> ' + \ >> + 'encoding bits for immediate "{}"'.\ >> + format(tag, ''.join(imm))) >> + if imm_type.lower() in 'sr': >> + print(' DECODE_IMM_SXT({},{})'.\ >> + format(immno, imm_width), file=f) >> + if imm_type.lower() == 'n': >> + print(' DECODE_IMM_NEG({},{})'.\ >> + format(immno, imm_width), file=f) >> + if imm_shift: >> + print(' DECODE_IMM_SHIFT({},{})'.\ >> + format(immno, imm_shift), file=f) >> + print(')', file=f) >> + >> +if __name__ == '__main__': >> + f = cStringIO.StringIO() >> + print_tree(f, dectree_normal) >> + print_tree(f, dectree_16bit) >> + if subinsn_groupings: >> + print_tree(f, dectree_subinsn_groupings) >> + for (name, dectree_subinsn) in sorted(dectree_subinsns.items()): >> + print_tree(f, dectree_subinsn) >> + for (name, dectree_ext) in sorted(dectree_extensions.items()): >> + print_tree(f, dectree_ext) >> + print_match_info(f) >> + print_op_info(f) >> + open('dectree_generated.h', 'w').write(f.getvalue()) >> > > Tested-by: Philippe Mathieu-Daudé <philmd@redhat.com>
diff --git a/target/hexagon/dectree.py b/target/hexagon/dectree.py new file mode 100755 index 0000000..a0435c9 --- /dev/null +++ b/target/hexagon/dectree.py @@ -0,0 +1,354 @@ +#!/usr/bin/env python + +from __future__ import print_function +## +## Copyright (c) 2019 Qualcomm Innovation Center, Inc. All Rights Reserved. +## +## This program is free software; you can redistribute it and/or modify +## it under the terms of the GNU General Public License as published by +## the Free Software Foundation; either version 2 of the License, or +## (at your option) any later version. +## +## This program 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 General Public License for more details. +## +## You should have received a copy of the GNU General Public License +## along with this program; if not, see <http://www.gnu.org/licenses/>. +## + +import cStringIO +import re + +import sys +sys.path.insert(0, sys.argv[1]) +import iset + +encs = {tag : ''.join(reversed(iset.iset[tag]['enc'].replace(' ', ''))) + for tag in iset.tags if iset.iset[tag]['enc'] != 'MISSING ENCODING'} + +enc_classes = set([iset.iset[tag]['enc_class'] for tag in encs.keys()]) +subinsn_enc_classes = \ + set([enc_class for enc_class in enc_classes \ + if enc_class.startswith('SUBINSN_')]) +ext_enc_classes = \ + set([enc_class for enc_class in enc_classes \ + if enc_class not in ('NORMAL', '16BIT') and \ + not enc_class.startswith('SUBINSN_')]) + +try: + subinsn_groupings = iset.subinsn_groupings +except AttributeError: + subinsn_groupings = {} + +for (tag, subinsn_grouping) in subinsn_groupings.items(): + encs[tag] = ''.join(reversed(subinsn_grouping['enc'].replace(' ', ''))) + +dectree_normal = {'leaves' : set()} +dectree_16bit = {'leaves' : set()} +dectree_subinsn_groupings = {'leaves' : set()} +dectree_subinsns = {name : {'leaves' : set()} for name in subinsn_enc_classes} +dectree_extensions = {name : {'leaves' : set()} for name in ext_enc_classes} + +for tag in encs.keys(): + if tag in subinsn_groupings: + dectree_subinsn_groupings['leaves'].add(tag) + continue + enc_class = iset.iset[tag]['enc_class'] + if enc_class.startswith('SUBINSN_'): + if len(encs[tag]) != 32: + encs[tag] = encs[tag] + '0' * (32 - len(encs[tag])) + dectree_subinsns[enc_class]['leaves'].add(tag) + elif enc_class == '16BIT': + if len(encs[tag]) != 16: + raise Exception('Tag "{}" has enc_class "{}" and not an encoding ' + + 'width of 16 bits!'.format(tag, enc_class)) + dectree_16bit['leaves'].add(tag) + else: + if len(encs[tag]) != 32: + raise Exception('Tag "{}" has enc_class "{}" and not an encoding ' + + 'width of 32 bits!'.format(tag, enc_class)) + if enc_class == 'NORMAL': + dectree_normal['leaves'].add(tag) + else: + dectree_extensions[enc_class]['leaves'].add(tag) + +faketags = set() +for (tag, enc) in iset.enc_ext_spaces.items(): + faketags.add(tag) + encs[tag] = ''.join(reversed(enc.replace(' ', ''))) + dectree_normal['leaves'].add(tag) + +faketags |= set(subinsn_groupings.keys()) + +def every_bit_counts(bitset): + for i in range(1, len(next(iter(bitset)))): + if len(set([bits[:i] + bits[i+1:] for bits in bitset])) == len(bitset): + return False + return True + +def auto_separate(node): + tags = node['leaves'] + if len(tags) <= 1: + return + enc_width = len(encs[next(iter(tags))]) + opcode_bit_for_all = \ + [all([encs[tag][i] in '01' \ + for tag in tags]) for i in range(enc_width)] + opcode_bit_is_0_for_all = \ + [opcode_bit_for_all[i] and all([encs[tag][i] == '0' \ + for tag in tags]) for i in range(enc_width)] + opcode_bit_is_1_for_all = \ + [opcode_bit_for_all[i] and all([encs[tag][i] == '1' \ + for tag in tags]) for i in range(enc_width)] + differentiator_opcode_bit = \ + [opcode_bit_for_all[i] and \ + not (opcode_bit_is_0_for_all[i] or \ + opcode_bit_is_1_for_all[i]) \ + for i in range(enc_width)] + best_width = 0 + for width in range(4, 0, -1): + for lsb in range(enc_width - width, -1, -1): + bitset = set([encs[tag][lsb:lsb+width] for tag in tags]) + if all(differentiator_opcode_bit[lsb:lsb+width]) and \ + (len(bitset) == len(tags) or every_bit_counts(bitset)): + best_width = width + best_lsb = lsb + caught_all_tags = len(bitset) == len(tags) + break + if best_width != 0: + break + if best_width == 0: + raise Exception('Could not find a way to differentiate the encodings ' + + 'of the following tags:\n{}'.format('\n'.join(tags))) + if caught_all_tags: + for width in range(1, best_width): + for lsb in range(enc_width - width, -1, -1): + bitset = set([encs[tag][lsb:lsb+width] for tag in tags]) + if all(differentiator_opcode_bit[lsb:lsb+width]) and \ + len(bitset) == len(tags): + best_width = width + best_lsb = lsb + break + else: + continue + break + node['separator_lsb'] = best_lsb + node['separator_width'] = best_width + node['children'] = [] + for value in range(2 ** best_width): + child = {} + bits = ''.join(reversed('{:0{}b}'.format(value, best_width))) + child['leaves'] = \ + set([tag for tag in tags \ + if encs[tag][best_lsb:best_lsb+best_width] == bits]) + node['children'].append(child) + for child in node['children']: + auto_separate(child) + +auto_separate(dectree_normal) +auto_separate(dectree_16bit) +if subinsn_groupings: + auto_separate(dectree_subinsn_groupings) +for dectree_subinsn in dectree_subinsns.values(): + auto_separate(dectree_subinsn) +for dectree_ext in dectree_extensions.values(): + auto_separate(dectree_ext) + +for tag in faketags: + del encs[tag] + +def table_name(parents, node): + path = parents + [node] + root = path[0] + tag = next(iter(node['leaves'])) + if tag in subinsn_groupings: + enc_width = len(subinsn_groupings[tag]['enc'].replace(' ', '')) + else: + tag = next(iter(node['leaves'] - faketags)) + enc_width = len(encs[tag]) + determining_bits = ['_'] * enc_width + for (parent, child) in zip(path[:-1], path[1:]): + lsb = parent['separator_lsb'] + width = parent['separator_width'] + value = parent['children'].index(child) + determining_bits[lsb:lsb+width] = \ + list(reversed('{:0{}b}'.format(value, width))) + if tag in subinsn_groupings: + name = 'DECODE_ROOT_EE' + else: + enc_class = iset.iset[tag]['enc_class'] + if enc_class in ext_enc_classes: + name = 'DECODE_EXT_{}'.format(enc_class) + elif enc_class in subinsn_enc_classes: + name = 'DECODE_SUBINSN_{}'.format(enc_class) + else: + name = 'DECODE_ROOT_{}'.format(enc_width) + if node != root: + name += '_' + ''.join(reversed(determining_bits)) + return name + +def print_node(f, node, parents): + if len(node['leaves']) <= 1: + return + name = table_name(parents, node) + lsb = node['separator_lsb'] + width = node['separator_width'] + print('DECODE_NEW_TABLE({},{},DECODE_SEPARATOR_BITS({},{}))'.\ + format(name, 2 ** width, lsb, width), file=f) + for child in node['children']: + if len(child['leaves']) == 0: + print('INVALID()', file=f) + elif len(child['leaves']) == 1: + (tag,) = child['leaves'] + if tag in subinsn_groupings: + class_a = subinsn_groupings[tag]['class_a'] + class_b = subinsn_groupings[tag]['class_b'] + enc = subinsn_groupings[tag]['enc'].replace(' ', '') + if 'RESERVED' in tag: + print('INVALID()', file=f) + else: + print('SUBINSNS({},{},{},"{}")'.\ + format(tag, class_a, class_b, enc), file=f) + elif tag in iset.enc_ext_spaces: + enc = iset.enc_ext_spaces[tag].replace(' ', '') + print('EXTSPACE({},"{}")'.format(tag, enc), file=f) + else: + enc = ''.join(reversed(encs[tag])) + print('TERMINAL({},"{}")'.format(tag, enc), file=f) + else: + print('TABLE_LINK({})'.format(table_name(parents + [node], child)), + file=f) + print('DECODE_END_TABLE({},{},DECODE_SEPARATOR_BITS({},{}))'.\ + format(name, 2 ** width, lsb, width), file=f) + print(file=f) + parents.append(node) + for child in node['children']: + print_node(f, child, parents) + parents.pop() + +def print_tree(f, tree): + print_node(f, tree, []) + +def print_match_info(f): + for tag in sorted(encs.keys(), key=iset.tags.index): + enc = ''.join(reversed(encs[tag])) + mask = int(re.sub(r'[^1]', r'0', enc.replace('0', '1')), 2) + match = int(re.sub(r'[^01]', r'0', enc), 2) + suffix = '' + print('DECODE{}_MATCH_INFO({},0x{:x}U,0x{:x}U)'.\ + format(suffix, tag, mask, match), file=f) + +regre = re.compile( + r'((?<!DUP)[MNORCPQXSGVZA])([stuvwxyzdefg]+)([.]?[LlHh]?)(\d+S?)') +immre = re.compile(r'[#]([rRsSuUm])(\d+)(?:[:](\d+))?') + +def ordered_unique(l): + return sorted(set(l), key=l.index) + +implicit_registers = { + 'SP' : 29, + 'FP' : 30, + 'LR' : 31 +} + +num_registers = { + 'R' : 32, + 'V' : 32 +} + +def print_op_info(f): + for tag in sorted(encs.keys(), key=iset.tags.index): + enc = encs[tag] + print(file=f) + print('DECODE_OPINFO({},'.format(tag), file=f) + regs = ordered_unique(regre.findall(iset.iset[tag]['syntax'])) + imms = ordered_unique(immre.findall(iset.iset[tag]['syntax'])) + regno = 0 + for reg in regs: + reg_type = reg[0] + reg_letter = reg[1][0] + reg_num_choices = int(reg[3].rstrip('S')) + reg_mapping = reg[0] + ''.join(['_' for letter in reg[1]]) + reg[3] + reg_enc_fields = re.findall(reg_letter + '+', enc) + if len(reg_enc_fields) == 0: + raise Exception('Tag "{}" missing register field!'.format(tag)) + if len(reg_enc_fields) > 1: + raise Exception('Tag "{}" has split register field!'.\ + format(tag)) + reg_enc_field = reg_enc_fields[0] + if 2 ** len(reg_enc_field) != reg_num_choices: + raise Exception('Tag "{}" has incorrect register field width!'.\ + format(tag)) + print(' DECODE_REG({},{},{})'.\ + format(regno, len(reg_enc_field), enc.index(reg_enc_field)), + file=f) + if reg_type in num_registers and \ + reg_num_choices != num_registers[reg_type]: + print(' DECODE_MAPPED_REG({},{})'.\ + format(regno, reg_mapping), file=f) + regno += 1 + def implicit_register_key(reg): + return implicit_registers[reg] + for reg in sorted( + set([r for r in (iset.iset[tag]['rregs'].split(',') + \ + iset.iset[tag]['wregs'].split(',')) \ + if r in implicit_registers]), key=implicit_register_key): + print(' DECODE_IMPL_REG({},{})'.\ + format(regno, implicit_registers[reg]), file=f) + regno += 1 + if imms and imms[0][0].isupper(): + imms = reversed(imms) + for imm in imms: + if imm[0].isupper(): + immno = 1 + else: + immno = 0 + imm_type = imm[0] + imm_width = int(imm[1]) + imm_shift = imm[2] + if imm_shift: + imm_shift = int(imm_shift) + else: + imm_shift = 0 + if imm_type.islower(): + imm_letter = 'i' + else: + imm_letter = 'I' + remainder = imm_width + for m in reversed(list(re.finditer(imm_letter + '+', enc))): + remainder -= m.end() - m.start() + print(' DECODE_IMM({},{},{},{})'.\ + format(immno, m.end() - m.start(), m.start(), remainder), + file=f) + if remainder != 0: + if imm[2]: + imm[2] = ':' + imm[2] + raise Exception('Tag "{}" has an incorrect number of ' + \ + 'encoding bits for immediate "{}"'.\ + format(tag, ''.join(imm))) + if imm_type.lower() in 'sr': + print(' DECODE_IMM_SXT({},{})'.\ + format(immno, imm_width), file=f) + if imm_type.lower() == 'n': + print(' DECODE_IMM_NEG({},{})'.\ + format(immno, imm_width), file=f) + if imm_shift: + print(' DECODE_IMM_SHIFT({},{})'.\ + format(immno, imm_shift), file=f) + print(')', file=f) + +if __name__ == '__main__': + f = cStringIO.StringIO() + print_tree(f, dectree_normal) + print_tree(f, dectree_16bit) + if subinsn_groupings: + print_tree(f, dectree_subinsn_groupings) + for (name, dectree_subinsn) in sorted(dectree_subinsns.items()): + print_tree(f, dectree_subinsn) + for (name, dectree_ext) in sorted(dectree_extensions.items()): + print_tree(f, dectree_ext) + print_match_info(f) + print_op_info(f) + open('dectree_generated.h', 'w').write(f.getvalue())
Python script that emits the decode tree in dectree_generated.h. Signed-off-by: Taylor Simpson <tsimpson@quicinc.com> --- target/hexagon/dectree.py | 354 ++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 354 insertions(+) create mode 100755 target/hexagon/dectree.py