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 if xml.find('meta') is not None: 292 self.meta = xml.find('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_value(self): 424 return self.value 425 426class BitSetEnum(object): 427 """Class that encapsulates an enum declaration 428 """ 429 def __init__(self, isa, xml): 430 self.isa = isa 431 self.name = xml.attrib['name'] 432 433 # Table mapping value to name 434 self.values = {} 435 for value in xml.findall('value'): 436 v = BitSetEnumValue(self, value) 437 self.values[v.get_value()] = v 438 439 def get_c_name(self): 440 return 'enum_' + get_c_name(self.name) 441 442class BitSetExpression(object): 443 """Class that encapsulates an <expr> declaration 444 """ 445 def __init__(self, isa, xml): 446 self.isa = isa 447 if 'name' in xml.attrib: 448 self.name = xml.attrib['name'] 449 else: 450 self.name = 'anon_' + str(isa.anon_expression_count) 451 isa.anon_expression_count = isa.anon_expression_count + 1 452 expr = xml.text.strip() 453 self.fieldnames = list(set(re.findall(r"{([a-zA-Z0-9_]+)}", expr))) 454 self.expr = re.sub(r"{([a-zA-Z0-9_]+)}", r"\1", expr) 455 dbg("'{}' -> '{}'".format(expr, self.expr)) 456 457 def get_c_name(self): 458 return 'expr_' + get_c_name(self.name) 459 460class ISA(object): 461 """Class that encapsulates all the parsed bitset rules 462 """ 463 def __init__(self, xmlpath): 464 self.base_path = os.path.dirname(xmlpath) 465 466 # Counter used to name inline (anonymous) expressions: 467 self.anon_expression_count = 0 468 469 # Table of (globally defined) expressions: 470 self.expressions = {} 471 472 # Table of templates: 473 self.templates = {} 474 475 # Table of enums: 476 self.enums = {} 477 478 # Table of toplevel bitset hierarchies: 479 self.roots = {} 480 481 # Table of leaf nodes of bitset hierarchies: 482 # Note that there may be multiple leaves for a particular name 483 # (distinguished by gen), so the values here are lists. 484 self.leafs = {} 485 486 # Table of all non-ambiguous bitsets (i.e. no per-gen ambiguity): 487 self.bitsets = {} 488 489 # Max needed bitsize for one instruction 490 self.bitsize = 0 491 492 root = ElementTree.parse(xmlpath).getroot() 493 self.parse_file(root) 494 self.validate_isa() 495 496 def parse_expressions(self, root): 497 e = None 498 for expr in root.findall('expr'): 499 e = BitSetExpression(self, expr) 500 self.expressions[e.name] = e 501 return e 502 503 def parse_one_expression(self, root, name): 504 assert len(root.findall('expr')) == 1, "expected a single expression in: {}".format(name) 505 return self.parse_expressions(root) 506 507 def parse_file(self, root): 508 # Handle imports up-front: 509 for imprt in root.findall('import'): 510 p = os.path.join(self.base_path, imprt.attrib['file']) 511 self.parse_file(ElementTree.parse(p)) 512 513 # Extract expressions: 514 self.parse_expressions(root) 515 516 # Extract templates: 517 for template in root.findall('template'): 518 t = BitSetTemplate(self, template) 519 self.templates[t.name] = t 520 521 # Extract enums: 522 for enum in root.findall('enum'): 523 e = BitSetEnum(self, enum) 524 self.enums[e.name] = e 525 526 # Extract bitsets: 527 for bitset in root.findall('bitset'): 528 b = BitSet(self, bitset) 529 if b.size is not None: 530 dbg("toplevel: " + b.name) 531 self.roots[b.name] = b 532 self.bitsize = max(self.bitsize, b.size) 533 else: 534 dbg("derived: " + b.name) 535 self.bitsets[b.name] = b 536 self.leafs.setdefault(b.name, []).append(b) 537 538 # Resolve all templates: 539 for _, bitset in self.bitsets.items(): 540 for case in bitset.cases: 541 if case.display: 542 case.display = self.resolve_templates(case.display) 543 544 def validate_isa(self): 545 # We only support multiples of 32 bits for now 546 assert self.bitsize % 32 == 0 547 548 # Do one-time fixups 549 # Remove non-leaf nodes from the leafs table: 550 for name, bitsets in list(self.leafs.items()): 551 for bitset in bitsets: 552 if bitset.extends in self.leafs: 553 del self.leafs[bitset.extends] 554 555 # Fix multi-gen leaves in bitsets 556 for name, bitsets in self.leafs.items(): 557 if len(bitsets) == 1: 558 continue 559 560 del self.bitsets[name] 561 562 # Validate that all bitset fields have valid types, and in 563 # the case of bitset type, the sizes match: 564 builtin_types = ['branch', 'absbranch', 'int', 'uint', 'hex', 'offset', 'uoffset', 'float', 'bool', 'bool_inv', 'enum', 'custom'] 565 for bitset_name, bitset in self.bitsets.items(): 566 if bitset.extends is not None: 567 assert bitset.extends in self.bitsets, "{} extends invalid type: {}".format( 568 bitset_name, bitset.extends) 569 for case in bitset.cases: 570 for field_name, field in case.fields.items(): 571 if field.type == 'float': 572 assert field.get_size() == 32 or field.get_size() == 16 573 574 if not isinstance(field, BitSetDerivedField): 575 assert field.high < bitset.get_size(), \ 576 "{}.{}: invalid bit range: [{}, {}] is not in [{}, {}]".format( 577 bitset_name, field_name, field.low, field.high, 0, bitset.get_size() - 1) 578 579 if field.type in builtin_types: 580 continue 581 if field.type in self.enums: 582 continue 583 assert field.type in self.bitsets, "{}.{}: invalid type: {}".format( 584 bitset_name, field_name, field.type) 585 bs = self.bitsets[field.type] 586 assert field.get_size() == bs.get_size(), "{}.{}: invalid size: {} vs {}".format( 587 bitset_name, field_name, field.get_size(), bs.get_size()) 588 589 # Validate that all the leaf node bitsets have no remaining 590 # undefined bits 591 for name, bitsets in self.leafs.items(): 592 for bitset in bitsets: 593 pat = bitset.get_pattern() 594 sz = bitset.get_size() 595 assert ((pat.mask | pat.field_mask) == (1 << sz) - 1), "leaf bitset {} has undefined bits: {:x}".format( 596 bitset.name, ~(pat.mask | pat.field_mask) & ((1 << sz) - 1)) 597 598 # TODO somehow validating that only one bitset in a hierarchy 599 # matches any given bit pattern would be useful. 600 601 # TODO we should probably be able to look at the contexts where 602 # an expression is evaluated and verify that it doesn't have any 603 # {VARNAME} references that would be unresolved at evaluation time 604 605 def format(self): 606 ''' Generate format string used by printf(..) and friends ''' 607 parts = [] 608 words = self.bitsize / 32 609 610 for i in range(int(words)): 611 parts.append('%08x') 612 613 fmt = ''.join(parts) 614 615 return f"\"{fmt[1:]}\"" 616 617 def value(self): 618 ''' Generate format values used by printf(..) and friends ''' 619 parts = [] 620 words = self.bitsize / 32 621 622 for i in range(int(words) - 1, -1, -1): 623 parts.append('v[' + str(i) + ']') 624 625 return ', '.join(parts) 626 627 def split_bits(self, value, bitsize): 628 ''' Split `value` into a list of bitsize-bit integers ''' 629 mask, parts = (1 << bitsize) - 1, [] 630 words = self.bitsize / bitsize 631 632 while value: 633 parts.append(hex(value & mask)) 634 value >>= bitsize 635 636 # Add 'missing' words 637 while len(parts) < words: 638 parts.append('0x0') 639 640 return parts 641 642 # Returns all bitsets in the ISA, including all per-gen variants, in 643 # (name, bitset) pairs. 644 def all_bitsets(self): 645 for name, bitset in self.bitsets.items(): 646 yield name, bitset 647 for name, bitsets in self.leafs.items(): 648 if len(bitsets) == 1: 649 continue 650 for bitset in bitsets: 651 yield name, bitset 652 653 def resolve_templates(self, display_string): 654 matches = re.findall(r'\{([^\}]+)\}', display_string) 655 for m in matches: 656 if m in self.templates: 657 display_string = display_string.replace("{" + m + "}", self.templates[m].display) 658 659 return display_string 660 661 def instructions(self): 662 instr = [] 663 664 for _, root in self.roots.items(): 665 for _, leafs in self.leafs.items(): 666 for leaf in leafs: 667 if leaf.get_root() == root: 668 if not leaf.get_c_name().startswith('__'): 669 instr.append(leaf) 670 671 return instr 672