target/hexagon/dectree.py

   1 #!/usr/bin/env python3
   2
   3 ##
   4 ##  Copyright(c) 2019-2021 Qualcomm Innovation Center, Inc. All Rights Reserved.
   5 ##
   6 ##  This program is free software; you can redistribute it and/or modify
   7 ##  it under the terms of the GNU General Public License as published by
   8 ##  the Free Software Foundation; either version 2 of the License, or
   9 ##  (at your option) any later version.
  10 ##
  11 ##  This program is distributed in the hope that it will be useful,
  12 ##  but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 ##  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 ##  GNU General Public License for more details.
  15 ##
  16 ##  You should have received a copy of the GNU General Public License
  17 ##  along with this program; if not, see <http://www.gnu.org/licenses/>.
  18 ##
  19
  20 import io
  21 import re
  22
  23 import sys
  24 import iset
  25
  26 encs = {tag : ''.join(reversed(iset.iset[tag]['enc'].replace(' ', '')))
  27     for tag in iset.tags if iset.iset[tag]['enc'] != 'MISSING ENCODING'}
  28
  29 enc_classes = set([iset.iset[tag]['enc_class'] for tag in encs.keys()])
  30 subinsn_enc_classes = \
  31     set([enc_class for enc_class in enc_classes \
  32         if enc_class.startswith('SUBINSN_')])
  33 ext_enc_classes = \
  34     set([enc_class for enc_class in enc_classes \
  35         if enc_class not in ('NORMAL', '16BIT') and \
  36            not enc_class.startswith('SUBINSN_')])
  37
  38 try:
  39     subinsn_groupings = iset.subinsn_groupings
  40 except AttributeError:
  41     subinsn_groupings = {}
  42
  43 for (tag, subinsn_grouping) in subinsn_groupings.items():
  44     encs[tag] = ''.join(reversed(subinsn_grouping['enc'].replace(' ', '')))
  45
  46 dectree_normal = {'leaves' : set()}
  47 dectree_16bit = {'leaves' : set()}
  48 dectree_subinsn_groupings = {'leaves' : set()}
  49 dectree_subinsns = {name : {'leaves' : set()} for name in subinsn_enc_classes}
  50 dectree_extensions = {name : {'leaves' : set()} for name in ext_enc_classes}
  51
  52 for tag in encs.keys():
  53     if tag in subinsn_groupings:
  54         dectree_subinsn_groupings['leaves'].add(tag)
  55         continue
  56     enc_class = iset.iset[tag]['enc_class']
  57     if enc_class.startswith('SUBINSN_'):
  58         if len(encs[tag]) != 32:
  59             encs[tag] = encs[tag] + '0' * (32 - len(encs[tag]))
  60         dectree_subinsns[enc_class]['leaves'].add(tag)
  61     elif  enc_class == '16BIT':
  62         if len(encs[tag]) != 16:
  63             raise Exception('Tag "{}" has enc_class "{}" and not an encoding ' +
  64                             'width of 16 bits!'.format(tag, enc_class))
  65         dectree_16bit['leaves'].add(tag)
  66     else:
  67         if len(encs[tag]) != 32:
  68             raise Exception('Tag "{}" has enc_class "{}" and not an encoding ' +
  69                             'width of 32 bits!'.format(tag, enc_class))
  70         if enc_class == 'NORMAL':
  71             dectree_normal['leaves'].add(tag)
  72         else:
  73             dectree_extensions[enc_class]['leaves'].add(tag)
  74
  75 faketags = set()
  76 for (tag, enc) in iset.enc_ext_spaces.items():
  77     faketags.add(tag)
  78     encs[tag] = ''.join(reversed(enc.replace(' ', '')))
  79     dectree_normal['leaves'].add(tag)
  80
  81 faketags |= set(subinsn_groupings.keys())
  82
  83 def every_bit_counts(bitset):
  84     for i in range(1, len(next(iter(bitset)))):
  85         if len(set([bits[:i] + bits[i+1:] for bits in bitset])) == len(bitset):
  86             return False
  87     return True
  88
  89 def auto_separate(node):
  90     tags = node['leaves']
  91     if len(tags) <= 1:
  92         return
  93     enc_width = len(encs[next(iter(tags))])
  94     opcode_bit_for_all = \
  95         [all([encs[tag][i] in '01' \
  96             for tag in tags]) for i in range(enc_width)]
  97     opcode_bit_is_0_for_all = \
  98         [opcode_bit_for_all[i] and all([encs[tag][i] == '0' \
  99             for tag in tags]) for i in range(enc_width)]
 100     opcode_bit_is_1_for_all = \
 101         [opcode_bit_for_all[i] and all([encs[tag][i] == '1' \
 102             for tag in tags]) for i in range(enc_width)]
 103     differentiator_opcode_bit = \
 104         [opcode_bit_for_all[i] and \
 105          not (opcode_bit_is_0_for_all[i] or \
 106          opcode_bit_is_1_for_all[i]) \
 107             for i in range(enc_width)]
 108     best_width = 0
 109     for width in range(4, 0, -1):
 110         for lsb in range(enc_width - width, -1, -1):
 111             bitset = set([encs[tag][lsb:lsb+width] for tag in tags])
 112             if all(differentiator_opcode_bit[lsb:lsb+width]) and \
 113                 (len(bitset) == len(tags) or every_bit_counts(bitset)):
 114                 best_width = width
 115                 best_lsb = lsb
 116                 caught_all_tags = len(bitset) == len(tags)
 117                 break
 118         if best_width != 0:
 119             break
 120     if best_width == 0:
 121         raise Exception('Could not find a way to differentiate the encodings ' +
 122                          'of the following tags:\n{}'.format('\n'.join(tags)))
 123     if caught_all_tags:
 124         for width in range(1, best_width):
 125             for lsb in range(enc_width - width, -1, -1):
 126                 bitset = set([encs[tag][lsb:lsb+width] for tag in tags])
 127                 if all(differentiator_opcode_bit[lsb:lsb+width]) and \
 128                     len(bitset) == len(tags):
 129                     best_width = width
 130                     best_lsb = lsb
 131                     break
 132             else:
 133                 continue
 134             break
 135     node['separator_lsb'] = best_lsb
 136     node['separator_width'] = best_width
 137     node['children'] = []
 138     for value in range(2 ** best_width):
 139         child = {}
 140         bits = ''.join(reversed('{:0{}b}'.format(value, best_width)))
 141         child['leaves'] = \
 142             set([tag for tag in tags \
 143                 if encs[tag][best_lsb:best_lsb+best_width] == bits])
 144         node['children'].append(child)
 145     for child in node['children']:
 146         auto_separate(child)
 147
 148 auto_separate(dectree_normal)
 149 auto_separate(dectree_16bit)
 150 if subinsn_groupings:
 151     auto_separate(dectree_subinsn_groupings)
 152 for dectree_subinsn in dectree_subinsns.values():
 153     auto_separate(dectree_subinsn)
 154 for dectree_ext in dectree_extensions.values():
 155     auto_separate(dectree_ext)
 156
 157 for tag in faketags:
 158     del encs[tag]
 159
 160 def table_name(parents, node):
 161     path = parents + [node]
 162     root = path[0]
 163     tag = next(iter(node['leaves']))
 164     if tag in subinsn_groupings:
 165         enc_width = len(subinsn_groupings[tag]['enc'].replace(' ', ''))
 166     else:
 167         tag = next(iter(node['leaves'] - faketags))
 168         enc_width = len(encs[tag])
 169     determining_bits = ['_'] * enc_width
 170     for (parent, child) in zip(path[:-1], path[1:]):
 171         lsb = parent['separator_lsb']
 172         width = parent['separator_width']
 173         value = parent['children'].index(child)
 174         determining_bits[lsb:lsb+width] = \
 175             list(reversed('{:0{}b}'.format(value, width)))
 176     if tag in subinsn_groupings:
 177         name = 'DECODE_ROOT_EE'
 178     else:
 179         enc_class = iset.iset[tag]['enc_class']
 180         if enc_class in ext_enc_classes:
 181             name = 'DECODE_EXT_{}'.format(enc_class)
 182         elif enc_class in subinsn_enc_classes:
 183             name = 'DECODE_SUBINSN_{}'.format(enc_class)
 184         else:
 185             name = 'DECODE_ROOT_{}'.format(enc_width)
 186     if node != root:
 187         name += '_' + ''.join(reversed(determining_bits))
 188     return name
 189
 190 def print_node(f, node, parents):
 191     if len(node['leaves']) <= 1:
 192         return
 193     name = table_name(parents, node)
 194     lsb = node['separator_lsb']
 195     width = node['separator_width']
 196     print('DECODE_NEW_TABLE({},{},DECODE_SEPARATOR_BITS({},{}))'.\
 197         format(name, 2 ** width, lsb, width), file=f)
 198     for child in node['children']:
 199         if len(child['leaves']) == 0:
 200             print('INVALID()', file=f)
 201         elif len(child['leaves']) == 1:
 202             (tag,) = child['leaves']
 203             if tag in subinsn_groupings:
 204                 class_a = subinsn_groupings[tag]['class_a']
 205                 class_b = subinsn_groupings[tag]['class_b']
 206                 enc = subinsn_groupings[tag]['enc'].replace(' ', '')
 207                 if 'RESERVED' in tag:
 208                     print('INVALID()', file=f)
 209                 else:
 210                     print('SUBINSNS({},{},{},"{}")'.\
 211                         format(tag, class_a, class_b, enc), file=f)
 212             elif tag in iset.enc_ext_spaces:
 213                 enc = iset.enc_ext_spaces[tag].replace(' ', '')
 214                 print('EXTSPACE({},"{}")'.format(tag, enc), file=f)
 215             else:
 216                 enc = ''.join(reversed(encs[tag]))
 217                 print('TERMINAL({},"{}")'.format(tag, enc), file=f)
 218         else:
 219             print('TABLE_LINK({})'.format(table_name(parents + [node], child)),
 220                   file=f)
 221     print('DECODE_END_TABLE({},{},DECODE_SEPARATOR_BITS({},{}))'.\
 222         format(name, 2 ** width, lsb, width), file=f)
 223     print(file=f)
 224     parents.append(node)
 225     for child in node['children']:
 226         print_node(f, child, parents)
 227     parents.pop()
 228
 229 def print_tree(f, tree):
 230     print_node(f, tree, [])
 231
 232 def print_match_info(f):
 233     for tag in sorted(encs.keys(), key=iset.tags.index):
 234         enc = ''.join(reversed(encs[tag]))
 235         mask = int(re.sub(r'[^1]', r'0', enc.replace('0', '1')), 2)
 236         match = int(re.sub(r'[^01]', r'0', enc), 2)
 237         suffix = ''
 238         print('DECODE{}_MATCH_INFO({},0x{:x}U,0x{:x}U)'.\
 239             format(suffix, tag, mask, match), file=f)
 240
 241 regre = re.compile(
 242     r'((?<!DUP)[MNORCPQXSGVZA])([stuvwxyzdefg]+)([.]?[LlHh]?)(\d+S?)')
 243 immre = re.compile(r'[#]([rRsSuUm])(\d+)(?:[:](\d+))?')
 244
 245 def ordered_unique(l):
 246     return sorted(set(l), key=l.index)
 247
 248 implicit_registers = {
 249     'SP' : 29,
 250     'FP' : 30,
 251     'LR' : 31
 252 }
 253
 254 num_registers = {
 255     'R' : 32,
 256     'V' : 32
 257 }
 258
 259 def print_op_info(f):
 260     for tag in sorted(encs.keys(), key=iset.tags.index):
 261         enc = encs[tag]
 262         print(file=f)
 263         print('DECODE_OPINFO({},'.format(tag), file=f)
 264         regs = ordered_unique(regre.findall(iset.iset[tag]['syntax']))
 265         imms = ordered_unique(immre.findall(iset.iset[tag]['syntax']))
 266         regno = 0
 267         for reg in regs:
 268             reg_type = reg[0]
 269             reg_letter = reg[1][0]
 270             reg_num_choices = int(reg[3].rstrip('S'))
 271             reg_mapping = reg[0] + ''.join(['_' for letter in reg[1]]) + reg[3]
 272             reg_enc_fields = re.findall(reg_letter + '+', enc)
 273             if len(reg_enc_fields) == 0:
 274                 raise Exception('Tag "{}" missing register field!'.format(tag))
 275             if len(reg_enc_fields) > 1:
 276                 raise Exception('Tag "{}" has split register field!'.\
 277                     format(tag))
 278             reg_enc_field = reg_enc_fields[0]
 279             if 2 ** len(reg_enc_field) != reg_num_choices:
 280                 raise Exception('Tag "{}" has incorrect register field width!'.\
 281                     format(tag))
 282             print('        DECODE_REG({},{},{})'.\
 283                 format(regno, len(reg_enc_field), enc.index(reg_enc_field)),
 284                        file=f)
 285             if reg_type in num_registers and \
 286                 reg_num_choices != num_registers[reg_type]:
 287                 print('        DECODE_MAPPED_REG({},{})'.\
 288                     format(regno, reg_mapping), file=f)
 289             regno += 1
 290         def implicit_register_key(reg):
 291             return implicit_registers[reg]
 292         for reg in sorted(
 293             set([r for r in (iset.iset[tag]['rregs'].split(',') + \
 294                 iset.iset[tag]['wregs'].split(',')) \
 295                     if r in implicit_registers]), key=implicit_register_key):
 296             print('        DECODE_IMPL_REG({},{})'.\
 297                 format(regno, implicit_registers[reg]), file=f)
 298             regno += 1
 299         if imms and imms[0][0].isupper():
 300             imms = reversed(imms)
 301         for imm in imms:
 302             if imm[0].isupper():
 303                 immno = 1
 304             else:
 305                 immno = 0
 306             imm_type = imm[0]
 307             imm_width = int(imm[1])
 308             imm_shift = imm[2]
 309             if imm_shift:
 310                 imm_shift = int(imm_shift)
 311             else:
 312                 imm_shift = 0
 313             if imm_type.islower():
 314                 imm_letter = 'i'
 315             else:
 316                 imm_letter = 'I'
 317             remainder = imm_width
 318             for m in reversed(list(re.finditer(imm_letter + '+', enc))):
 319                 remainder -= m.end() - m.start()
 320                 print('        DECODE_IMM({},{},{},{})'.\
 321                     format(immno, m.end() - m.start(), m.start(), remainder),
 322                         file=f)
 323             if remainder != 0:
 324                 if imm[2]:
 325                     imm[2] = ':' + imm[2]
 326                 raise Exception('Tag "{}" has an incorrect number of ' + \
 327                     'encoding bits for immediate "{}"'.\
 328                     format(tag, ''.join(imm)))
 329             if imm_type.lower() in 'sr':
 330                 print('        DECODE_IMM_SXT({},{})'.\
 331                     format(immno, imm_width), file=f)
 332             if imm_type.lower() == 'n':
 333                 print('        DECODE_IMM_NEG({},{})'.\
 334                     format(immno, imm_width), file=f)
 335             if imm_shift:
 336                 print('        DECODE_IMM_SHIFT({},{})'.\
 337                     format(immno, imm_shift), file=f)
 338         print(')', file=f)
 339
 340 if __name__ == '__main__':
 341     with open(sys.argv[1], 'w') as f:
 342         print_tree(f, dectree_normal)
 343         print_tree(f, dectree_16bit)
 344         if subinsn_groupings:
 345             print_tree(f, dectree_subinsn_groupings)
 346         for (name, dectree_subinsn) in sorted(dectree_subinsns.items()):
 347             print_tree(f, dectree_subinsn)
 348         for (name, dectree_ext) in sorted(dectree_extensions.items()):
 349             print_tree(f, dectree_ext)
 350         print_match_info(f)
 351         print_op_info(f)