1# 2# Copyright © 2020 Google, Inc. 3# 4# Permission is hereby granted, free of charge, to any person obtaining a 5# copy of this software and associated documentation files (the "Software"), 6# to deal in the Software without restriction, including without limitation 7# the rights to use, copy, modify, merge, publish, distribute, sublicense, 8# and/or sell copies of the Software, and to permit persons to whom the 9# Software is furnished to do so, subject to the following conditions: 10# 11# The above copyright notice and this permission notice (including the next 12# paragraph) shall be included in all copies or substantial portions of the 13# Software. 14# 15# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 16# IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 17# FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL 18# THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 19# LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING 20# FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS 21# IN THE SOFTWARE. 22 23from xml.etree import ElementTree 24import os 25import re 26 27def dbg(str): 28 if False: 29 print(str) 30 31class BitSetPattern(object): 32 """Class that encapsulated the pattern matching, ie. 33 the match/dontcare/mask bitmasks. The following 34 rules should hold 35 36 (match ^ dontcare) == 0 37 (match || dontcare) == mask 38 39 For a leaf node, the mask should be (1 << size) - 1 40 (ie. all bits set) 41 """ 42 def __init__(self, bitset): 43 self.match = bitset.match 44 self.dontcare = bitset.dontcare 45 self.mask = bitset.mask 46 self.field_mask = bitset.field_mask 47 48 def merge(self, pattern): 49 p = BitSetPattern(pattern) 50 p.match = p.match | self.match 51 p.dontcare = p.dontcare | self.dontcare 52 p.mask = p.mask | self.mask 53 p.field_mask = p.field_mask | self.field_mask 54 return p 55 56 def defined_bits(self): 57 return self.match | self.dontcare | self.mask | self.field_mask 58 59def get_bitrange(field): 60 if 'pos' in field.attrib: 61 assert('low' not in field.attrib) 62 assert('high' not in field.attrib) 63 low = int(field.attrib['pos']) 64 high = low 65 else: 66 low = int(field.attrib['low']) 67 high = int(field.attrib['high']) 68 assert low <= high 69 return low, high 70 71def extract_pattern(xml, name, is_defined_bits=None): 72 low, high = get_bitrange(xml) 73 mask = ((1 << (1 + high - low)) - 1) << low 74 75 patstr = xml.text.strip() 76 77 assert (len(patstr) == (1 + high - low)), "Invalid {} length in {}: {}..{}".format(xml.tag, name, low, high) 78 if is_defined_bits is not None: 79 assert not is_defined_bits(mask), "Redefined bits in {} {}: {}..{}".format(xml.tag, name, low, high) 80 81 match = 0 82 dontcare = 0 83 84 for n in range(0, len(patstr)): 85 match = match << 1 86 dontcare = dontcare << 1 87 if patstr[n] == '1': 88 match |= 1 89 elif patstr[n] == 'x': 90 dontcare |= 1 91 elif patstr[n] != '0': 92 assert 0, "Invalid {} character in {}: {}".format(xml.tag, name, patstr[n]) 93 94 dbg("{}: {}.{} => {:016x} / {:016x} / {:016x}".format(xml.tag, name, patstr, match << low, dontcare << low, mask)) 95 96 return match << low, dontcare << low, mask 97 98def get_c_name(name): 99 return name.lower().replace('#', '__').replace('-', '_').replace('.', '_') 100 101class BitSetField(object): 102 """Class that encapsulates a field defined in a bitset 103 """ 104 def __init__(self, isa, xml): 105 self.isa = isa 106 self.low, self.high = get_bitrange(xml) 107 self.name = xml.attrib['name'] 108 self.type = xml.attrib['type'] 109 self.params = [] 110 for param in xml.findall('param'): 111 aas = name = param.attrib['name'] 112 if 'as' in param.attrib: 113 aas = param.attrib['as'] 114 self.params.append([name, aas]) 115 self.expr = None 116 self.display = None 117 self.call = 'call' in xml.attrib and xml.attrib['call'] == 'true' 118 if 'display' in xml.attrib: 119 self.display = xml.attrib['display'].strip() 120 121 def get_c_name(self): 122 return get_c_name(self.name) 123 124 def get_c_typename(self): 125 if self.type in self.isa.enums: 126 return 'TYPE_ENUM' 127 if self.type in self.isa.bitsets: 128 return 'TYPE_BITSET' 129 return 'TYPE_' + self.type.upper() 130 131 def mask(self): 132 return ((1 << self.get_size()) - 1) << self.low 133 134 def get_size(self): 135 return 1 + self.high - self.low 136 137class BitSetAssertField(BitSetField): 138 """Similar to BitSetField, but for <assert/>s, which can be 139 used to specify that a certain bitpattern is expected in 140 place of (for example) unused bitfields 141 """ 142 def __init__(self, case, xml): 143 self.isa = case.bitset.isa 144 self.low, self.high = get_bitrange(xml) 145 self.name = case.bitset.name + '#assert' + str(len(case.fields)) 146 self.type = 'uint' 147 self.expr = None 148 self.display = None 149 150 match, dontcare, mask = extract_pattern(xml, case.bitset.name) 151 self.val = match >> self.low 152 153 assert dontcare == 0, "'x' (dontcare) is not valid in an assert" 154 155 def get_c_typename(self): 156 return 'TYPE_ASSERT' 157 158class BitSetDerivedField(BitSetField): 159 """Similar to BitSetField, but for derived fields 160 """ 161 def __init__(self, isa, xml): 162 self.isa = isa 163 self.low = 0 164 self.high = 0 165 # NOTE: a width should be provided for 'int' derived fields, ie. 166 # where sign extension is needed. We just repurpose the 'high' 167 # field for that to make '1 + high - low' work out 168 if 'width' in xml.attrib: 169 self.high = int(xml.attrib['width']) - 1 170 self.name = xml.attrib['name'] 171 self.type = xml.attrib['type'] 172 if 'expr' in xml.attrib: 173 self.expr = xml.attrib['expr'] 174 else: 175 e = isa.parse_one_expression(xml, self.name) 176 self.expr = e.name 177 self.display = None 178 if 'display' in xml.attrib: 179 self.display = xml.attrib['display'].strip() 180 self.call = 'call' in xml.attrib and xml.attrib['call'] == 'true' 181 182class BitSetCase(object): 183 """Class that encapsulates a single bitset case 184 """ 185 def __init__(self, bitset, xml, update_field_mask, expr=None): 186 self.bitset = bitset 187 if expr is not None: 188 self.name = bitset.name + '#case' + str(len(bitset.cases)) 189 else: 190 self.name = bitset.name + "#default" 191 self.expr = expr 192 self.fields = {} 193 194 for derived in xml.findall('derived'): 195 f = BitSetDerivedField(bitset.isa, derived) 196 self.fields[f.name] = f 197 198 for assrt in xml.findall('assert'): 199 f = BitSetAssertField(self, assrt) 200 update_field_mask(self, f) 201 self.fields[f.name] = f 202 203 for field in xml.findall('field'): 204 dbg("{}.{}".format(self.name, field.attrib['name'])) 205 f = BitSetField(bitset.isa, field) 206 update_field_mask(self, f) 207 self.fields[f.name] = f 208 209 self.display = None 210 for d in xml.findall('display'): 211 # Allow <display/> for empty display string: 212 if d.text is not None: 213 self.display = d.text.strip() 214 else: 215 self.display = '' 216 dbg("found display: '{}'".format(self.display)) 217 218 def get_c_name(self): 219 return get_c_name(self.name) 220 221class BitSetEncode(object): 222 """Additional data that may be associated with a root bitset node 223 to provide additional information needed to generate helpers 224 to encode the bitset, such as source data type and "opcode" 225 case prefix (ie. how to choose/enumerate which leaf node bitset 226 to use to encode the source data 227 """ 228 def __init__(self, xml): 229 self.type = None 230 if 'type' in xml.attrib: 231 self.type = xml.attrib['type'] 232 self.case_prefix = None 233 if 'case-prefix' in xml.attrib: 234 self.case_prefix = xml.attrib['case-prefix'] 235 # The encode element may also contain mappings from encode src 236 # to individual field names: 237 self.maps = {} 238 self.forced = {} 239 for map in xml.findall('map'): 240 name = map.attrib['name'] 241 self.maps[name] = map.text.strip() 242 if 'force' in map.attrib and map.attrib['force'] == 'true': 243 self.forced[name] = 'true' 244 245class BitSetDecode(object): 246 """Additional data that may be associated with a root bitset node 247 to provide additional information needed to generate helpers 248 to decode the bitset. 249 """ 250 def __init__(self, xml): 251 pass 252 253class BitSet(object): 254 """Class that encapsulates a single bitset rule 255 """ 256 def __init__(self, isa, xml): 257 self.isa = isa 258 self.xml = xml 259 self.name = xml.attrib['name'] 260 self.display_name = xml.attrib['displayname'] if 'displayname' in xml.attrib else self.name 261 self.meta = {} 262 263 # Used for generated encoder, to de-duplicate encoding for 264 # similar instructions: 265 self.snippets = {} 266 267 if 'size' in xml.attrib: 268 assert('extends' not in xml.attrib) 269 self.size = int(xml.attrib['size']) 270 self.extends = None 271 else: 272 self.size = None 273 self.extends = xml.attrib['extends'] 274 275 self.encode = None 276 if xml.find('encode') is not None: 277 self.encode = BitSetEncode(xml.find('encode')) 278 self.decode = None 279 if xml.find('decode') is not None: 280 self.decode = BitSetDecode(xml.find('encode')) 281 282 self.gen_min = 0 283 self.gen_max = (1 << 32) - 1 284 285 for gen in xml.findall('gen'): 286 if 'min' in gen.attrib: 287 self.gen_min = int(gen.attrib['min']) 288 if 'max' in gen.attrib: 289 self.gen_max = int(gen.attrib['max']) 290 291 for meta in xml.findall('meta'): 292 self.meta.update(meta.attrib) 293 294 # Collect up the match/dontcare/mask bitmasks for 295 # this bitset case: 296 self.match = 0 297 self.dontcare = 0 298 self.mask = 0 299 self.field_mask = 0 300 301 self.cases = [] 302 303 # Helper to check for redefined bits: 304 def is_defined_bits(m): 305 return ((self.field_mask | self.mask | self.dontcare | self.match) & m) != 0 306 307 def update_default_bitmask_field(bs, field): 308 m = field.mask() 309 dbg("field: {}.{} => {:016x}".format(self.name, field.name, m)) 310 # For default case, we don't expect any bits to be doubly defined: 311 assert not is_defined_bits(m), "Redefined bits in field {}.{}: {}..{}".format( 312 self.name, field.name, field.low, field.high) 313 self.field_mask |= m 314 315 def update_override_bitmask_field(bs, field): 316 m = field.mask() 317 dbg("field: {}.{} => {:016x}".format(self.name, field.name, m)) 318 assert self.field_mask ^ ~m 319 320 dflt = BitSetCase(self, xml, update_default_bitmask_field) 321 322 for override in xml.findall('override'): 323 if 'expr' in override.attrib: 324 expr = override.attrib['expr'] 325 else: 326 e = isa.parse_one_expression(override, self.name) 327 expr = e.name 328 c = BitSetCase(self, override, update_override_bitmask_field, expr) 329 self.cases.append(c) 330 331 # Default case is expected to be the last one: 332 self.cases.append(dflt) 333 334 for pattern in xml.findall('pattern'): 335 match, dontcare, mask = extract_pattern(pattern, self.name, is_defined_bits) 336 337 self.match |= match 338 self.dontcare |= dontcare 339 self.mask |= mask 340 341 def get_pattern(self): 342 if self.extends is not None: 343 parent = self.isa.bitsets[self.extends] 344 ppat = parent.get_pattern() 345 pat = BitSetPattern(self) 346 347 assert ((ppat.defined_bits() & pat.defined_bits()) == 0), "bitset conflict in {}: {:x}".format(self.name, (ppat.defined_bits() & pat.defined_bits())) 348 349 return pat.merge(ppat) 350 351 return BitSetPattern(self) 352 353 def get_size(self): 354 if self.extends is not None: 355 parent = self.isa.bitsets[self.extends] 356 return parent.get_size() 357 return self.size 358 359 def get_gen_min(self): 360 if self.extends is not None: 361 parent = self.isa.bitsets[self.extends] 362 363 assert (self.gen_min == 0) or (self.gen_min >= parent.get_gen_min()), "bitset {} should not have min gen lower than the parent's one".format(self.name) 364 365 return max(self.gen_min, parent.get_gen_min()) 366 return self.gen_min 367 368 def get_gen_max(self): 369 if self.extends is not None: 370 parent = self.isa.bitsets[self.extends] 371 372 assert (self.gen_max == (1 << 32) - 1) or (self.gen_max <= parent.get_gen_max()), "bitset {} should not have max gen higher than the parent's one".format(self.name) 373 374 return min(self.gen_max, parent.get_gen_max()) 375 return self.gen_max 376 377 def has_gen_restriction(self): 378 return self.gen_min != 0 or self.gen_max != (1 << 32) - 1 379 380 def get_c_name(self): 381 return get_c_name(self.name) 382 383 def get_root(self): 384 if self.extends is not None: 385 return self.isa.bitsets[self.extends].get_root() 386 return self 387 388 def get_meta(self): 389 meta = {} 390 391 if self.extends is not None: 392 meta = self.isa.bitsets[self.extends].get_meta() 393 394 if self.meta: 395 meta.update(self.meta) 396 397 return meta 398 399class BitSetTemplate(object): 400 """Class that encapsulates a template declaration 401 """ 402 def __init__(self, isa, xml): 403 self.isa = isa 404 self.name = xml.attrib['name'] 405 self.display = xml.text.strip() 406 dbg("found template '{}: {}'".format(self.name, self.display)) 407 408class BitSetEnumValue(object): 409 """Class that encapsulates an enum value 410 """ 411 def __init__(self, isa, xml): 412 self.isa = isa 413 self.displayname = xml.attrib['display'] 414 self.value = xml.attrib['val'] 415 self.name = xml.attrib.get('name') 416 417 def __str__(self): 418 return self.displayname 419 420 def get_name(self): 421 return self.name or self.displayname 422 423 def get_displayname(self): 424 return self.displayname or self.name 425 426 def get_value(self): 427 return self.value 428 429class BitSetEnum(object): 430 """Class that encapsulates an enum declaration 431 """ 432 def __init__(self, isa, xml): 433 self.isa = isa 434 self.name = xml.attrib['name'] 435 436 # Table mapping value to name 437 self.values = {} 438 for value in xml.findall('value'): 439 v = BitSetEnumValue(self, value) 440 self.values[v.get_value()] = v 441 442 def get_c_name(self): 443 return 'enum_' + get_c_name(self.name) 444 445class BitSetExpression(object): 446 """Class that encapsulates an <expr> declaration 447 """ 448 def __init__(self, isa, xml): 449 self.isa = isa 450 if 'name' in xml.attrib: 451 self.name = xml.attrib['name'] 452 else: 453 self.name = 'anon_' + str(isa.anon_expression_count) 454 isa.anon_expression_count = isa.anon_expression_count + 1 455 expr = xml.text.strip() 456 self.fieldnames = list(set(re.findall(r"{([a-zA-Z0-9_]+)}", expr))) 457 self.expr = re.sub(r"{([a-zA-Z0-9_]+)}", r"\1", expr) 458 dbg("'{}' -> '{}'".format(expr, self.expr)) 459 460 def get_c_name(self): 461 return 'expr_' + get_c_name(self.name) 462 463class ISA(object): 464 """Class that encapsulates all the parsed bitset rules 465 """ 466 def __init__(self, xmlpath): 467 self.base_path = os.path.dirname(xmlpath) 468 469 # Counter used to name inline (anonymous) expressions: 470 self.anon_expression_count = 0 471 472 # Table of (globally defined) expressions: 473 self.expressions = {} 474 475 # Table of templates: 476 self.templates = {} 477 478 # Table of enums: 479 self.enums = {} 480 481 # Table of toplevel bitset hierarchies: 482 self.roots = {} 483 484 # Table of leaf nodes of bitset hierarchies: 485 # Note that there may be multiple leaves for a particular name 486 # (distinguished by gen), so the values here are lists. 487 self.leafs = {} 488 489 # Table of all non-ambiguous bitsets (i.e. no per-gen ambiguity): 490 self.bitsets = {} 491 492 # Max needed bitsize for one instruction 493 self.bitsize = 0 494 495 root = ElementTree.parse(xmlpath).getroot() 496 self.parse_file(root) 497 self.validate_isa() 498 499 def parse_expressions(self, root): 500 e = None 501 for expr in root.findall('expr'): 502 e = BitSetExpression(self, expr) 503 self.expressions[e.name] = e 504 return e 505 506 def parse_one_expression(self, root, name): 507 assert len(root.findall('expr')) == 1, "expected a single expression in: {}".format(name) 508 return self.parse_expressions(root) 509 510 def parse_file(self, root): 511 # Handle imports up-front: 512 for imprt in root.findall('import'): 513 p = os.path.join(self.base_path, imprt.attrib['file']) 514 self.parse_file(ElementTree.parse(p)) 515 516 # Extract expressions: 517 self.parse_expressions(root) 518 519 # Extract templates: 520 for template in root.findall('template'): 521 t = BitSetTemplate(self, template) 522 self.templates[t.name] = t 523 524 # Extract enums: 525 for enum in root.findall('enum'): 526 e = BitSetEnum(self, enum) 527 self.enums[e.name] = e 528 529 # Extract bitsets: 530 for bitset in root.findall('bitset'): 531 b = BitSet(self, bitset) 532 if b.size is not None: 533 dbg("toplevel: " + b.name) 534 self.roots[b.name] = b 535 self.bitsize = max(self.bitsize, b.size) 536 else: 537 dbg("derived: " + b.name) 538 self.bitsets[b.name] = b 539 self.leafs.setdefault(b.name, []).append(b) 540 541 # Resolve all templates: 542 for _, bitset in self.bitsets.items(): 543 for case in bitset.cases: 544 if case.display: 545 case.display = self.resolve_templates(case.display) 546 547 def validate_isa(self): 548 # We only support multiples of 32 bits for now 549 assert self.bitsize % 32 == 0 550 551 # Do one-time fixups 552 # Remove non-leaf nodes from the leafs table: 553 for name, bitsets in list(self.leafs.items()): 554 for bitset in bitsets: 555 if bitset.extends in self.leafs: 556 del self.leafs[bitset.extends] 557 558 # Fix multi-gen leaves in bitsets 559 for name, bitsets in self.leafs.items(): 560 if len(bitsets) == 1: 561 continue 562 563 del self.bitsets[name] 564 565 # Validate that all bitset fields have valid types, and in 566 # the case of bitset type, the sizes match: 567 builtin_types = ['branch', 'absbranch', 'int', 'uint', 'hex', 'offset', 'uoffset', 'float', 'bool', 'bool_inv', 'enum', 'custom'] 568 for bitset_name, bitset in self.bitsets.items(): 569 if bitset.extends is not None: 570 assert bitset.extends in self.bitsets, "{} extends invalid type: {}".format( 571 bitset_name, bitset.extends) 572 for case in bitset.cases: 573 for field_name, field in case.fields.items(): 574 if field.type == 'float': 575 assert field.get_size() == 32 or field.get_size() == 16 576 577 if not isinstance(field, BitSetDerivedField): 578 assert field.high < bitset.get_size(), \ 579 "{}.{}: invalid bit range: [{}, {}] is not in [{}, {}]".format( 580 bitset_name, field_name, field.low, field.high, 0, bitset.get_size() - 1) 581 582 if field.type in builtin_types: 583 continue 584 if field.type in self.enums: 585 continue 586 assert field.type in self.bitsets, "{}.{}: invalid type: {}".format( 587 bitset_name, field_name, field.type) 588 bs = self.bitsets[field.type] 589 assert field.get_size() == bs.get_size(), "{}.{}: invalid size: {} vs {}".format( 590 bitset_name, field_name, field.get_size(), bs.get_size()) 591 592 # Validate that all the leaf node bitsets have no remaining 593 # undefined bits 594 for name, bitsets in self.leafs.items(): 595 for bitset in bitsets: 596 pat = bitset.get_pattern() 597 sz = bitset.get_size() 598 assert ((pat.mask | pat.field_mask) == (1 << sz) - 1), "leaf bitset {} has undefined bits: {:x}".format( 599 bitset.name, ~(pat.mask | pat.field_mask) & ((1 << sz) - 1)) 600 601 # TODO somehow validating that only one bitset in a hierarchy 602 # matches any given bit pattern would be useful. 603 604 # TODO we should probably be able to look at the contexts where 605 # an expression is evaluated and verify that it doesn't have any 606 # {VARNAME} references that would be unresolved at evaluation time 607 608 def format(self): 609 ''' Generate format string used by printf(..) and friends ''' 610 parts = [] 611 words = self.bitsize / 32 612 613 for i in range(int(words)): 614 parts.append('%08x') 615 616 fmt = ''.join(parts) 617 618 return f"\"{fmt[1:]}\"" 619 620 def value(self): 621 ''' Generate format values used by printf(..) and friends ''' 622 parts = [] 623 words = self.bitsize / 32 624 625 for i in range(int(words) - 1, -1, -1): 626 parts.append('v[' + str(i) + ']') 627 628 return ', '.join(parts) 629 630 def split_bits(self, value, bitsize): 631 ''' Split `value` into a list of bitsize-bit integers ''' 632 mask, parts = (1 << bitsize) - 1, [] 633 words = self.bitsize / bitsize 634 635 while value: 636 parts.append(hex(value & mask)) 637 value >>= bitsize 638 639 # Add 'missing' words 640 while len(parts) < words: 641 parts.append('0x0') 642 643 return parts 644 645 # Returns all bitsets in the ISA, including all per-gen variants, in 646 # (name, bitset) pairs. 647 def all_bitsets(self): 648 for name, bitset in self.bitsets.items(): 649 yield name, bitset 650 for name, bitsets in self.leafs.items(): 651 if len(bitsets) == 1: 652 continue 653 for bitset in bitsets: 654 yield name, bitset 655 656 def resolve_templates(self, display_string): 657 matches = re.findall(r'\{([^\}]+)\}', display_string) 658 for m in matches: 659 if m in self.templates: 660 display_string = display_string.replace("{" + m + "}", self.templates[m].display) 661 662 return display_string 663 664 def instructions(self): 665 instr = [] 666 667 for _, root in self.roots.items(): 668 for _, leafs in self.leafs.items(): 669 for leaf in leafs: 670 if leaf.get_root() == root: 671 if not leaf.get_c_name().startswith('__'): 672 instr.append(leaf) 673 674 return instr 675