Re: [RFC PATCH 28/66] Hexagon generater phase 4 - Decode tree

["Philippe Mathieu-Daudé" <philmd@redhat.com>]

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>