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
20import io
21import re
22
23import sys
24import iset
25
26encs = {tag : ''.join(reversed(iset.iset[tag]['enc'].replace(' ', '')))
27    for tag in iset.tags if iset.iset[tag]['enc'] != 'MISSING ENCODING'}
28
29enc_classes = set([iset.iset[tag]['enc_class'] for tag in encs.keys()])
30subinsn_enc_classes = \
31    set([enc_class for enc_class in enc_classes \
32        if enc_class.startswith('SUBINSN_')])
33ext_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
38try:
39    subinsn_groupings = iset.subinsn_groupings
40except AttributeError:
41    subinsn_groupings = {}
42
43for (tag, subinsn_grouping) in subinsn_groupings.items():
44    encs[tag] = ''.join(reversed(subinsn_grouping['enc'].replace(' ', '')))
45
46dectree_normal = {'leaves' : set()}
47dectree_16bit = {'leaves' : set()}
48dectree_subinsn_groupings = {'leaves' : set()}
49dectree_subinsns = {name : {'leaves' : set()} for name in subinsn_enc_classes}
50dectree_extensions = {name : {'leaves' : set()} for name in ext_enc_classes}
51
52for 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
75faketags = set()
76for (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
81faketags |= set(subinsn_groupings.keys())
82
83def 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
89def 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
148auto_separate(dectree_normal)
149auto_separate(dectree_16bit)
150if subinsn_groupings:
151    auto_separate(dectree_subinsn_groupings)
152for dectree_subinsn in dectree_subinsns.values():
153    auto_separate(dectree_subinsn)
154for dectree_ext in dectree_extensions.values():
155    auto_separate(dectree_ext)
156
157for tag in faketags:
158    del encs[tag]
159
160def 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
190def 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
229def print_tree(f, tree):
230    print_node(f, tree, [])
231
232def 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
241regre = re.compile(
242    r'((?<!DUP)[MNORCPQXSGVZA])([stuvwxyzdefg]+)([.]?[LlHh]?)(\d+S?)')
243immre = re.compile(r'[#]([rRsSuUm])(\d+)(?:[:](\d+))?')
244
245def ordered_unique(l):
246    return sorted(set(l), key=l.index)
247
248implicit_registers = {
249    'SP' : 29,
250    'FP' : 30,
251    'LR' : 31
252}
253
254num_registers = {
255    'R' : 32,
256    'V' : 32
257}
258
259def 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
340if __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)
352