dectree.py (13570B)
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)