From patchwork Fri Feb 28 16:43:25 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Taylor Simpson X-Patchwork-Id: 11412919 Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id E5F7A14B4 for ; Fri, 28 Feb 2020 17:02:30 +0000 (UTC) Received: from lists.gnu.org (lists.gnu.org [209.51.188.17]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by mail.kernel.org (Postfix) with ESMTPS id A98A72467B for ; Fri, 28 Feb 2020 17:02:30 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=fail reason="signature verification failed" (1024-bit key) header.d=quicinc.com header.i=@quicinc.com header.b="yZ345A+q" DMARC-Filter: OpenDMARC Filter v1.3.2 mail.kernel.org A98A72467B Authentication-Results: mail.kernel.org; dmarc=fail (p=none dis=none) header.from=quicinc.com Authentication-Results: mail.kernel.org; spf=pass smtp.mailfrom=qemu-devel-bounces+patchwork-qemu-devel=patchwork.kernel.org@nongnu.org Received: from localhost ([::1]:50888 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1j7j1w-0006bw-1E for patchwork-qemu-devel@patchwork.kernel.org; Fri, 28 Feb 2020 12:02:29 -0500 Received: from eggs.gnu.org ([2001:470:142:3::10]:57881) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1j7iko-00037W-Qo for qemu-devel@nongnu.org; Fri, 28 Feb 2020 11:44:49 -0500 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1j7ikl-0005fW-SW for qemu-devel@nongnu.org; Fri, 28 Feb 2020 11:44:46 -0500 Received: from alexa-out-sd-02.qualcomm.com ([199.106.114.39]:27026) by eggs.gnu.org with esmtps (TLS1.0:RSA_AES_256_CBC_SHA1:32) (Exim 4.71) (envelope-from ) id 1j7ikl-0005U4-LM for qemu-devel@nongnu.org; Fri, 28 Feb 2020 11:44:43 -0500 DKIM-Signature: v=1; a=rsa-sha256; c=simple/simple; d=quicinc.com; i=@quicinc.com; q=dns/txt; s=qcdkim; t=1582908283; x=1614444283; h=from:to:cc:subject:date:message-id:in-reply-to: references:mime-version:content-transfer-encoding; bh=sd/X9qB+amUWsCBfLOpii2/fzjKFqs6vrbVq8DtdJ8Y=; b=yZ345A+qDCBlxAoRnWbHsBg+2L8jdiocCvU+v9f0mF8EtSd9XaYqyuJX +1YmAiurtOMP7JWAiO4cFDB8AsPUw4bl/8xp/g325XhbvKNLgsoZ20HCb ZF/PjD1e/lDnybu5bYmzm0MmZO0A0Dp5lG0lL3YnOVb7l/Wc2mupVtgIO o=; Received: from unknown (HELO ironmsg-SD-alpha.qualcomm.com) ([10.53.140.30]) by alexa-out-sd-02.qualcomm.com with ESMTP; 28 Feb 2020 08:44:31 -0800 Received: from vu-tsimpson-aus.qualcomm.com (HELO vu-tsimpson1-aus.qualcomm.com) ([10.222.150.1]) by ironmsg-SD-alpha.qualcomm.com with ESMTP; 28 Feb 2020 08:44:30 -0800 Received: by vu-tsimpson1-aus.qualcomm.com (Postfix, from userid 47164) id 4CF9C1110; Fri, 28 Feb 2020 10:44:30 -0600 (CST) From: Taylor Simpson To: qemu-devel@nongnu.org Subject: [RFC PATCH v2 29/67] Hexagon generater phase 4 - Decode tree Date: Fri, 28 Feb 2020 10:43:25 -0600 Message-Id: <1582908244-304-30-git-send-email-tsimpson@quicinc.com> X-Mailer: git-send-email 2.7.4 In-Reply-To: <1582908244-304-1-git-send-email-tsimpson@quicinc.com> References: <1582908244-304-1-git-send-email-tsimpson@quicinc.com> MIME-Version: 1.0 X-detected-operating-system: by eggs.gnu.org: FreeBSD 9.x [fuzzy] X-Received-From: 199.106.114.39 X-BeenThere: qemu-devel@nongnu.org X-Mailman-Version: 2.1.23 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Cc: riku.voipio@iki.fi, richard.henderson@linaro.org, laurent@vivier.eu, Taylor Simpson , philmd@redhat.com, aleksandar.m.mail@gmail.com Errors-To: qemu-devel-bounces+patchwork-qemu-devel=patchwork.kernel.org@nongnu.org Sender: "Qemu-devel" Python script that emits the decode tree in dectree_generated.h. Tested-by: Philippe Mathieu-Daudé --- target/hexagon/dectree.py | 353 ++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 353 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..2b9c82b --- /dev/null +++ b/target/hexagon/dectree.py @@ -0,0 +1,353 @@ +#!/usr/bin/env python3 + +## +## Copyright(c) 2019-2020 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 . +## + +import io +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'((? 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 = io.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())