target/hexagon/dectree.py

   1 #!/usr/bin/env python3
   2
   3 ##
   4 ##  Copyright(c) 2019-2023 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 = {
  27     tag: "".join(reversed(iset.iset[tag]["enc"].replace(" ", "")))
  28     for tag in iset.tags
  29     if iset.iset[tag]["enc"] != "MISSING ENCODING"
  30 }
  31
  32 enc_classes = set([iset.iset[tag]["enc_class"] for tag in encs.keys()])
  33 subinsn_enc_classes = set(
  34     [enc_class for enc_class in enc_classes if enc_class.startswith("SUBINSN_")]
  35 )
  36 ext_enc_classes = set(
  37     [
  38         enc_class
  39         for enc_class in enc_classes
  40         if enc_class not in ("NORMAL", "16BIT") and not enc_class.startswith("SUBINSN_")
  41     ]
  42 )
  43
  44 try:
  45     subinsn_groupings = iset.subinsn_groupings
  46 except AttributeError:
  47     subinsn_groupings = {}
  48
  49 for tag, subinsn_grouping in subinsn_groupings.items():
  50     encs[tag] = "".join(reversed(subinsn_grouping["enc"].replace(" ", "")))
  51
  52 dectree_normal = {"leaves": set()}
  53 dectree_16bit = {"leaves": set()}
  54 dectree_subinsn_groupings = {"leaves": set()}
  55 dectree_subinsns = {name: {"leaves": set()} for name in subinsn_enc_classes}
  56 dectree_extensions = {name: {"leaves": set()} for name in ext_enc_classes}
  57
  58 for tag in encs.keys():
  59     if tag in subinsn_groupings:
  60         dectree_subinsn_groupings["leaves"].add(tag)
  61         continue
  62     enc_class = iset.iset[tag]["enc_class"]
  63     if enc_class.startswith("SUBINSN_"):
  64         if len(encs[tag]) != 32:
  65             encs[tag] = encs[tag] + "0" * (32 - len(encs[tag]))
  66         dectree_subinsns[enc_class]["leaves"].add(tag)
  67     elif enc_class == "16BIT":
  68         if len(encs[tag]) != 16:
  69             raise Exception(
  70                 'Tag "{}" has enc_class "{}" and not an encoding '
  71                 + "width of 16 bits!".format(tag, enc_class)
  72             )
  73         dectree_16bit["leaves"].add(tag)
  74     else:
  75         if len(encs[tag]) != 32:
  76             raise Exception(
  77                 'Tag "{}" has enc_class "{}" and not an encoding '
  78                 + "width of 32 bits!".format(tag, enc_class)
  79             )
  80         if enc_class == "NORMAL":
  81             dectree_normal["leaves"].add(tag)
  82         else:
  83             dectree_extensions[enc_class]["leaves"].add(tag)
  84
  85 faketags = set()
  86 for tag, enc in iset.enc_ext_spaces.items():
  87     faketags.add(tag)
  88     encs[tag] = "".join(reversed(enc.replace(" ", "")))
  89     dectree_normal["leaves"].add(tag)
  90
  91 faketags |= set(subinsn_groupings.keys())
  92
  93
  94 def every_bit_counts(bitset):
  95     for i in range(1, len(next(iter(bitset)))):
  96         if len(set([bits[:i] + bits[i + 1 :] for bits in bitset])) == len(bitset):
  97             return False
  98     return True
  99
 100
 101 def auto_separate(node):
 102     tags = node["leaves"]
 103     if len(tags) <= 1:
 104         return
 105     enc_width = len(encs[next(iter(tags))])
 106     opcode_bit_for_all = [
 107         all([encs[tag][i] in "01" for tag in tags]) for i in range(enc_width)
 108     ]
 109     opcode_bit_is_0_for_all = [
 110         opcode_bit_for_all[i] and all([encs[tag][i] == "0" for tag in tags])
 111         for i in range(enc_width)
 112     ]
 113     opcode_bit_is_1_for_all = [
 114         opcode_bit_for_all[i] and all([encs[tag][i] == "1" for tag in tags])
 115         for i in range(enc_width)
 116     ]
 117     differentiator_opcode_bit = [
 118         opcode_bit_for_all[i]
 119         and not (opcode_bit_is_0_for_all[i] or opcode_bit_is_1_for_all[i])
 120         for i in range(enc_width)
 121     ]
 122     best_width = 0
 123     for width in range(4, 0, -1):
 124         for lsb in range(enc_width - width, -1, -1):
 125             bitset = set([encs[tag][lsb : lsb + width] for tag in tags])
 126             if all(differentiator_opcode_bit[lsb : lsb + width]) and (
 127                 len(bitset) == len(tags) or every_bit_counts(bitset)
 128             ):
 129                 best_width = width
 130                 best_lsb = lsb
 131                 caught_all_tags = len(bitset) == len(tags)
 132                 break
 133         if best_width != 0:
 134             break
 135     if best_width == 0:
 136         raise Exception(
 137             "Could not find a way to differentiate the encodings "
 138             + "of the following tags:\n{}".format("\n".join(tags))
 139         )
 140     if caught_all_tags:
 141         for width in range(1, best_width):
 142             for lsb in range(enc_width - width, -1, -1):
 143                 bitset = set([encs[tag][lsb : lsb + width] for tag in tags])
 144                 if all(differentiator_opcode_bit[lsb : lsb + width]) and len(
 145                     bitset
 146                 ) == len(tags):
 147                     best_width = width
 148                     best_lsb = lsb
 149                     break
 150             else:
 151                 continue
 152             break
 153     node["separator_lsb"] = best_lsb
 154     node["separator_width"] = best_width
 155     node["children"] = []
 156     for value in range(2**best_width):
 157         child = {}
 158         bits = "".join(reversed("{:0{}b}".format(value, best_width)))
 159         child["leaves"] = set(
 160             [tag for tag in tags if encs[tag][best_lsb : best_lsb + best_width] == bits]
 161         )
 162         node["children"].append(child)
 163     for child in node["children"]:
 164         auto_separate(child)
 165
 166
 167 auto_separate(dectree_normal)
 168 auto_separate(dectree_16bit)
 169 if subinsn_groupings:
 170     auto_separate(dectree_subinsn_groupings)
 171 for dectree_subinsn in dectree_subinsns.values():
 172     auto_separate(dectree_subinsn)
 173 for dectree_ext in dectree_extensions.values():
 174     auto_separate(dectree_ext)
 175
 176 for tag in faketags:
 177     del encs[tag]
 178
 179
 180 def table_name(parents, node):
 181     path = parents + [node]
 182     root = path[0]
 183     tag = next(iter(node["leaves"]))
 184     if tag in subinsn_groupings:
 185         enc_width = len(subinsn_groupings[tag]["enc"].replace(" ", ""))
 186     else:
 187         tag = next(iter(node["leaves"] - faketags))
 188         enc_width = len(encs[tag])
 189     determining_bits = ["_"] * enc_width
 190     for parent, child in zip(path[:-1], path[1:]):
 191         lsb = parent["separator_lsb"]
 192         width = parent["separator_width"]
 193         value = parent["children"].index(child)
 194         determining_bits[lsb : lsb + width] = list(
 195             reversed("{:0{}b}".format(value, width))
 196         )
 197     if tag in subinsn_groupings:
 198         name = "DECODE_ROOT_EE"
 199     else:
 200         enc_class = iset.iset[tag]["enc_class"]
 201         if enc_class in ext_enc_classes:
 202             name = "DECODE_EXT_{}".format(enc_class)
 203         elif enc_class in subinsn_enc_classes:
 204             name = "DECODE_SUBINSN_{}".format(enc_class)
 205         else:
 206             name = "DECODE_ROOT_{}".format(enc_width)
 207     if node != root:
 208         name += "_" + "".join(reversed(determining_bits))
 209     return name
 210
 211
 212 def print_node(f, node, parents):
 213     if len(node["leaves"]) <= 1:
 214         return
 215     name = table_name(parents, node)
 216     lsb = node["separator_lsb"]
 217     width = node["separator_width"]
 218     print(
 219         "DECODE_NEW_TABLE({},{},DECODE_SEPARATOR_BITS({},{}))".format(
 220             name, 2**width, lsb, width
 221         ),
 222         file=f,
 223     )
 224     for child in node["children"]:
 225         if len(child["leaves"]) == 0:
 226             print("INVALID()", file=f)
 227         elif len(child["leaves"]) == 1:
 228             (tag,) = child["leaves"]
 229             if tag in subinsn_groupings:
 230                 class_a = subinsn_groupings[tag]["class_a"]
 231                 class_b = subinsn_groupings[tag]["class_b"]
 232                 enc = subinsn_groupings[tag]["enc"].replace(" ", "")
 233                 if "RESERVED" in tag:
 234                     print("INVALID()", file=f)
 235                 else:
 236                     print(
 237                         'SUBINSNS({},{},{},"{}")'.format(tag, class_a, class_b, enc),
 238                         file=f,
 239                     )
 240             elif tag in iset.enc_ext_spaces:
 241                 enc = iset.enc_ext_spaces[tag].replace(" ", "")
 242                 print('EXTSPACE({},"{}")'.format(tag, enc), file=f)
 243             else:
 244                 enc = "".join(reversed(encs[tag]))
 245                 print('TERMINAL({},"{}")'.format(tag, enc), file=f)
 246         else:
 247             print("TABLE_LINK({})".format(table_name(parents + [node], child)), file=f)
 248     print(
 249         "DECODE_END_TABLE({},{},DECODE_SEPARATOR_BITS({},{}))".format(
 250             name, 2**width, lsb, width
 251         ),
 252         file=f,
 253     )
 254     print(file=f)
 255     parents.append(node)
 256     for child in node["children"]:
 257         print_node(f, child, parents)
 258     parents.pop()
 259
 260
 261 def print_tree(f, tree):
 262     print_node(f, tree, [])
 263
 264
 265 def print_match_info(f):
 266     for tag in sorted(encs.keys(), key=iset.tags.index):
 267         enc = "".join(reversed(encs[tag]))
 268         mask = int(re.sub(r"[^1]", r"0", enc.replace("0", "1")), 2)
 269         match = int(re.sub(r"[^01]", r"0", enc), 2)
 270         suffix = ""
 271         print(
 272             "DECODE{}_MATCH_INFO({},0x{:x}U,0x{:x}U)".format(suffix, tag, mask, match),
 273             file=f,
 274         )
 275
 276
 277 regre = re.compile(r"((?<!DUP)[MNORCPQXSGVZA])([stuvwxyzdefg]+)([.]?[LlHh]?)(\d+S?)")
 278 immre = re.compile(r"[#]([rRsSuUm])(\d+)(?:[:](\d+))?")
 279
 280
 281 def ordered_unique(l):
 282     return sorted(set(l), key=l.index)
 283
 284
 285 implicit_registers = {"SP": 29, "FP": 30, "LR": 31}
 286
 287 num_registers = {"R": 32, "V": 32}
 288
 289
 290 def print_op_info(f):
 291     for tag in sorted(encs.keys(), key=iset.tags.index):
 292         enc = encs[tag]
 293         print(file=f)
 294         print("DECODE_OPINFO({},".format(tag), file=f)
 295         regs = ordered_unique(regre.findall(iset.iset[tag]["syntax"]))
 296         imms = ordered_unique(immre.findall(iset.iset[tag]["syntax"]))
 297         regno = 0
 298         for reg in regs:
 299             reg_type = reg[0]
 300             reg_letter = reg[1][0]
 301             reg_num_choices = int(reg[3].rstrip("S"))
 302             reg_mapping = reg[0] + "".join(["_" for letter in reg[1]]) + reg[3]
 303             reg_enc_fields = re.findall(reg_letter + "+", enc)
 304             if len(reg_enc_fields) == 0:
 305                 raise Exception('Tag "{}" missing register field!'.format(tag))
 306             if len(reg_enc_fields) > 1:
 307                 raise Exception('Tag "{}" has split register field!'.format(tag))
 308             reg_enc_field = reg_enc_fields[0]
 309             if 2 ** len(reg_enc_field) != reg_num_choices:
 310                 raise Exception(
 311                     'Tag "{}" has incorrect register field width!'.format(tag)
 312                 )
 313             print(
 314                 "        DECODE_REG({},{},{})".format(
 315                     regno, len(reg_enc_field), enc.index(reg_enc_field)
 316                 ),
 317                 file=f,
 318             )
 319             if reg_type in num_registers and reg_num_choices != num_registers[reg_type]:
 320                 print(
 321                     "        DECODE_MAPPED_REG({},{})".format(regno, reg_mapping),
 322                     file=f,
 323                 )
 324             regno += 1
 325
 326         def implicit_register_key(reg):
 327             return implicit_registers[reg]
 328
 329         for reg in sorted(
 330             set(
 331                 [
 332                     r
 333                     for r in (
 334                         iset.iset[tag]["rregs"].split(",")
 335                         + iset.iset[tag]["wregs"].split(",")
 336                     )
 337                     if r in implicit_registers
 338                 ]
 339             ),
 340             key=implicit_register_key,
 341         ):
 342             print(
 343                 "        DECODE_IMPL_REG({},{})".format(regno, implicit_registers[reg]),
 344                 file=f,
 345             )
 346             regno += 1
 347         if imms and imms[0][0].isupper():
 348             imms = reversed(imms)
 349         for imm in imms:
 350             if imm[0].isupper():
 351                 immno = 1
 352             else:
 353                 immno = 0
 354             imm_type = imm[0]
 355             imm_width = int(imm[1])
 356             imm_shift = imm[2]
 357             if imm_shift:
 358                 imm_shift = int(imm_shift)
 359             else:
 360                 imm_shift = 0
 361             if imm_type.islower():
 362                 imm_letter = "i"
 363             else:
 364                 imm_letter = "I"
 365             remainder = imm_width
 366             for m in reversed(list(re.finditer(imm_letter + "+", enc))):
 367                 remainder -= m.end() - m.start()
 368                 print(
 369                     "        DECODE_IMM({},{},{},{})".format(
 370                         immno, m.end() - m.start(), m.start(), remainder
 371                     ),
 372                     file=f,
 373                 )
 374             if remainder != 0:
 375                 if imm[2]:
 376                     imm[2] = ":" + imm[2]
 377                 raise Exception(
 378                     'Tag "{}" has an incorrect number of '
 379                     + 'encoding bits for immediate "{}"'.format(tag, "".join(imm))
 380                 )
 381             if imm_type.lower() in "sr":
 382                 print("        DECODE_IMM_SXT({},{})".format(immno, imm_width), file=f)
 383             if imm_type.lower() == "n":
 384                 print("        DECODE_IMM_NEG({},{})".format(immno, imm_width), file=f)
 385             if imm_shift:
 386                 print(
 387                     "        DECODE_IMM_SHIFT({},{})".format(immno, imm_shift), file=f
 388                 )
 389         print(")", file=f)
 390
 391
 392 if __name__ == "__main__":
 393     with open(sys.argv[1], "w") as f:
 394         print_tree(f, dectree_normal)
 395         print_tree(f, dectree_16bit)
 396         if subinsn_groupings:
 397             print_tree(f, dectree_subinsn_groupings)
 398         for name, dectree_subinsn in sorted(dectree_subinsns.items()):
 399             print_tree(f, dectree_subinsn)
 400         for name, dectree_ext in sorted(dectree_extensions.items()):
 401             print_tree(f, dectree_ext)
 402         print_match_info(f)
 403         print_op_info(f)