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 if 'display' in xml.attrib: 118 self.display = xml.attrib['display'].strip() 119 120 def get_c_name(self): 121 return get_c_name(self.name) 122 123 def get_c_typename(self): 124 if self.type in self.isa.enums: 125 return 'TYPE_ENUM' 126 if self.type in self.isa.bitsets: 127 return 'TYPE_BITSET' 128 return 'TYPE_' + self.type.upper() 129 130 def mask(self): 131 return ((1 << self.get_size()) - 1) << self.low 132 133 def get_size(self): 134 return 1 + self.high - self.low 135 136class BitSetAssertField(BitSetField): 137 """Similar to BitSetField, but for <assert/>s, which can be 138 used to specify that a certain bitpattern is expected in 139 place of (for example) unused bitfields 140 """ 141 def __init__(self, case, xml): 142 self.isa = case.bitset.isa 143 self.low, self.high = get_bitrange(xml) 144 self.name = case.bitset.name + '#assert' + str(len(case.fields)) 145 self.type = 'uint' 146 self.expr = None 147 self.display = None 148 149 match, dontcare, mask = extract_pattern(xml, case.bitset.name) 150 self.val = match >> self.low 151 152 assert dontcare == 0, "'x' (dontcare) is not valid in an assert" 153 154 def get_c_typename(self): 155 return 'TYPE_ASSERT' 156 157class BitSetDerivedField(BitSetField): 158 """Similar to BitSetField, but for derived fields 159 """ 160 def __init__(self, isa, xml): 161 self.isa = isa 162 self.low = 0 163 self.high = 0 164 # NOTE: a width should be provided for 'int' derived fields, ie. 165 # where sign extension is needed. We just repurpose the 'high' 166 # field for that to make '1 + high - low' work out 167 if 'width' in xml.attrib: 168 self.high = int(xml.attrib['width']) - 1 169 self.name = xml.attrib['name'] 170 self.type = xml.attrib['type'] 171 if 'expr' in xml.attrib: 172 self.expr = xml.attrib['expr'] 173 else: 174 e = isa.parse_one_expression(xml, self.name) 175 self.expr = e.name 176 self.display = None 177 if 'display' in xml.attrib: 178 self.display = xml.attrib['display'].strip() 179 180class BitSetCase(object): 181 """Class that encapsulates a single bitset case 182 """ 183 def __init__(self, bitset, xml, update_field_mask, expr=None): 184 self.bitset = bitset 185 if expr is not None: 186 self.name = bitset.name + '#case' + str(len(bitset.cases)) 187 else: 188 self.name = bitset.name + "#default" 189 self.expr = expr 190 self.fields = {} 191 192 for derived in xml.findall('derived'): 193 f = BitSetDerivedField(bitset.isa, derived) 194 self.fields[f.name] = f 195 196 for assrt in xml.findall('assert'): 197 f = BitSetAssertField(self, assrt) 198 update_field_mask(self, f) 199 self.fields[f.name] = f 200 201 for field in xml.findall('field'): 202 dbg("{}.{}".format(self.name, field.attrib['name'])) 203 f = BitSetField(bitset.isa, field) 204 update_field_mask(self, f) 205 self.fields[f.name] = f 206 207 self.display = None 208 for d in xml.findall('display'): 209 # Allow <display/> for empty display string: 210 if d.text is not None: 211 self.display = d.text.strip() 212 else: 213 self.display = '' 214 dbg("found display: '{}'".format(self.display)) 215 216 def get_c_name(self): 217 return get_c_name(self.name) 218 219class BitSetEncode(object): 220 """Additional data that may be associated with a root bitset node 221 to provide additional information needed to generate helpers 222 to encode the bitset, such as source data type and "opcode" 223 case prefix (ie. how to choose/enumerate which leaf node bitset 224 to use to encode the source data 225 """ 226 def __init__(self, xml): 227 self.type = None 228 if 'type' in xml.attrib: 229 self.type = xml.attrib['type'] 230 self.case_prefix = None 231 if 'case-prefix' in xml.attrib: 232 self.case_prefix = xml.attrib['case-prefix'] 233 # The encode element may also contain mappings from encode src 234 # to individual field names: 235 self.maps = {} 236 self.forced = {} 237 for map in xml.findall('map'): 238 name = map.attrib['name'] 239 self.maps[name] = map.text.strip() 240 if 'force' in map.attrib and map.attrib['force'] == 'true': 241 self.forced[name] = 'true' 242 243class BitSet(object): 244 """Class that encapsulates a single bitset rule 245 """ 246 def __init__(self, isa, xml): 247 self.isa = isa 248 self.xml = xml 249 self.name = xml.attrib['name'] 250 251 # Used for generated encoder, to de-duplicate encoding for 252 # similar instructions: 253 self.snippets = {} 254 255 if 'size' in xml.attrib: 256 assert('extends' not in xml.attrib) 257 self.size = int(xml.attrib['size']) 258 self.extends = None 259 else: 260 self.size = None 261 self.extends = xml.attrib['extends'] 262 263 self.encode = None 264 if xml.find('encode') is not None: 265 self.encode = BitSetEncode(xml.find('encode')) 266 267 self.gen_min = 0 268 self.gen_max = (1 << 32) - 1 269 270 for gen in xml.findall('gen'): 271 if 'min' in gen.attrib: 272 self.gen_min = int(gen.attrib['min']) 273 if 'max' in gen.attrib: 274 self.gen_max = int(gen.attrib['max']) 275 276 # Collect up the match/dontcare/mask bitmasks for 277 # this bitset case: 278 self.match = 0 279 self.dontcare = 0 280 self.mask = 0 281 self.field_mask = 0 282 283 self.cases = [] 284 285 # Helper to check for redefined bits: 286 def is_defined_bits(m): 287 return ((self.field_mask | self.mask | self.dontcare | self.match) & m) != 0 288 289 def update_default_bitmask_field(bs, field): 290 m = field.mask() 291 dbg("field: {}.{} => {:016x}".format(self.name, field.name, m)) 292 # For default case, we don't expect any bits to be doubly defined: 293 assert not is_defined_bits(m), "Redefined bits in field {}.{}: {}..{}".format( 294 self.name, field.name, field.low, field.high); 295 self.field_mask |= m 296 297 def update_override_bitmask_field(bs, field): 298 m = field.mask() 299 dbg("field: {}.{} => {:016x}".format(self.name, field.name, m)) 300 assert self.field_mask ^ ~m 301 302 dflt = BitSetCase(self, xml, update_default_bitmask_field) 303 304 for override in xml.findall('override'): 305 if 'expr' in override.attrib: 306 expr = override.attrib['expr'] 307 else: 308 e = isa.parse_one_expression(override, self.name) 309 expr = e.name 310 c = BitSetCase(self, override, update_override_bitmask_field, expr) 311 self.cases.append(c) 312 313 # Default case is expected to be the last one: 314 self.cases.append(dflt) 315 316 for pattern in xml.findall('pattern'): 317 match, dontcare, mask = extract_pattern(pattern, self.name, is_defined_bits) 318 319 self.match |= match 320 self.dontcare |= dontcare 321 self.mask |= mask 322 323 def get_pattern(self): 324 if self.extends is not None: 325 parent = self.isa.bitsets[self.extends] 326 ppat = parent.get_pattern() 327 pat = BitSetPattern(self) 328 329 assert ((ppat.defined_bits() & pat.defined_bits()) == 0), "bitset conflict in {}: {:x}".format(self.name, (ppat.defined_bits() & pat.defined_bits())) 330 331 return pat.merge(ppat) 332 333 return BitSetPattern(self) 334 335 def get_size(self): 336 if self.extends is not None: 337 parent = self.isa.bitsets[self.extends] 338 return parent.get_size() 339 return self.size 340 341 def get_gen_min(self): 342 if self.extends is not None: 343 parent = self.isa.bitsets[self.extends] 344 345 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) 346 347 return max(self.gen_min, parent.get_gen_min()) 348 return self.gen_min 349 350 def get_gen_max(self): 351 if self.extends is not None: 352 parent = self.isa.bitsets[self.extends] 353 354 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) 355 356 return min(self.gen_max, parent.get_gen_max()) 357 return self.gen_max 358 359 def has_gen_restriction(self): 360 return self.gen_min != 0 or self.gen_max != (1 << 32) - 1 361 362 def get_c_name(self): 363 return get_c_name(self.name) 364 365 def get_root(self): 366 if self.extends is not None: 367 return self.isa.bitsets[self.extends].get_root() 368 return self 369 370class BitSetEnum(object): 371 """Class that encapsulates an enum declaration 372 """ 373 def __init__(self, isa, xml): 374 self.isa = isa 375 self.name = xml.attrib['name'] 376 # Table mapping value to name 377 # TODO currently just mapping to 'display' name, but if we 378 # need more attributes then maybe need BitSetEnumValue? 379 self.values = {} 380 for value in xml.findall('value'): 381 self.values[value.attrib['val']] = value.attrib['display'] 382 383 def get_c_name(self): 384 return 'enum_' + get_c_name(self.name) 385 386class BitSetExpression(object): 387 """Class that encapsulates an <expr> declaration 388 """ 389 def __init__(self, isa, xml): 390 self.isa = isa 391 if 'name' in xml.attrib: 392 self.name = xml.attrib['name'] 393 else: 394 self.name = 'anon_' + str(isa.anon_expression_count) 395 isa.anon_expression_count = isa.anon_expression_count + 1 396 expr = xml.text.strip() 397 self.fieldnames = list(set(re.findall(r"{([a-zA-Z0-9_]+)}", expr))) 398 self.expr = re.sub(r"{([a-zA-Z0-9_]+)}", r"\1", expr) 399 dbg("'{}' -> '{}'".format(expr, self.expr)) 400 401 def get_c_name(self): 402 return 'expr_' + get_c_name(self.name) 403 404class ISA(object): 405 """Class that encapsulates all the parsed bitset rules 406 """ 407 def __init__(self, xmlpath): 408 self.base_path = os.path.dirname(xmlpath) 409 410 # Counter used to name inline (anonymous) expressions: 411 self.anon_expression_count = 0 412 413 # Table of (globally defined) expressions: 414 self.expressions = {} 415 416 # Table of enums: 417 self.enums = {} 418 419 # Table of toplevel bitset hierarchies: 420 self.roots = {} 421 422 # Table of leaf nodes of bitset hierarchies: 423 # Note that there may be multiple leaves for a particular name 424 # (distinguished by gen), so the values here are lists. 425 self.leafs = {} 426 427 # Table of all non-ambiguous bitsets (i.e. no per-gen ambiguity): 428 self.bitsets = {} 429 430 # Max needed bitsize for one instruction 431 self.bitsize = 0 432 433 root = ElementTree.parse(xmlpath).getroot() 434 self.parse_file(root) 435 self.validate_isa() 436 437 def parse_expressions(self, root): 438 e = None 439 for expr in root.findall('expr'): 440 e = BitSetExpression(self, expr) 441 self.expressions[e.name] = e 442 return e 443 444 def parse_one_expression(self, root, name): 445 assert len(root.findall('expr')) == 1, "expected a single expression in: {}".format(name) 446 return self.parse_expressions(root) 447 448 def parse_file(self, root): 449 # Handle imports up-front: 450 for imprt in root.findall('import'): 451 p = os.path.join(self.base_path, imprt.attrib['file']) 452 self.parse_file(ElementTree.parse(p)) 453 454 # Extract expressions: 455 self.parse_expressions(root) 456 457 # Extract enums: 458 for enum in root.findall('enum'): 459 e = BitSetEnum(self, enum) 460 self.enums[e.name] = e 461 462 # Extract bitsets: 463 for bitset in root.findall('bitset'): 464 b = BitSet(self, bitset) 465 if b.size is not None: 466 dbg("toplevel: " + b.name) 467 self.roots[b.name] = b 468 self.bitsize = max(self.bitsize, b.size) 469 else: 470 dbg("derived: " + b.name) 471 self.bitsets[b.name] = b 472 self.leafs.setdefault(b.name, []).append(b) 473 474 def validate_isa(self): 475 # Do one-time fixups 476 # Remove non-leaf nodes from the leafs table: 477 for name, bitsets in list(self.leafs.items()): 478 for bitset in bitsets: 479 if bitset.extends in self.leafs: 480 del self.leafs[bitset.extends] 481 482 # Fix multi-gen leaves in bitsets 483 for name, bitsets in self.leafs.items(): 484 if len(bitsets) == 1: 485 continue 486 487 del self.bitsets[name] 488 489 # Validate that all bitset fields have valid types, and in 490 # the case of bitset type, the sizes match: 491 builtin_types = ['branch', 'int', 'uint', 'hex', 'offset', 'uoffset', 'float', 'bool', 'enum'] 492 for bitset_name, bitset in self.bitsets.items(): 493 if bitset.extends is not None: 494 assert bitset.extends in self.bitsets, "{} extends invalid type: {}".format( 495 bitset_name, bitset.extends) 496 for case in bitset.cases: 497 for field_name, field in case.fields.items(): 498 if field.type == 'float': 499 assert field.get_size() == 32 or field.get_size() == 16 500 501 if not isinstance(field, BitSetDerivedField): 502 assert field.high < bitset.get_size(), \ 503 "{}.{}: invalid bit range: [{}, {}] is not in [{}, {}]".format( 504 bitset_name, field_name, field.low, field.high, 0, bitset.get_size() - 1) 505 506 if field.type in builtin_types: 507 continue 508 if field.type in self.enums: 509 continue 510 assert field.type in self.bitsets, "{}.{}: invalid type: {}".format( 511 bitset_name, field_name, field.type) 512 bs = self.bitsets[field.type] 513 assert field.get_size() == bs.get_size(), "{}.{}: invalid size: {} vs {}".format( 514 bitset_name, field_name, field.get_size(), bs.get_size()) 515 516 # Validate that all the leaf node bitsets have no remaining 517 # undefined bits 518 for name, bitsets in self.leafs.items(): 519 for bitset in bitsets: 520 pat = bitset.get_pattern() 521 sz = bitset.get_size() 522 assert ((pat.mask | pat.field_mask) == (1 << sz) - 1), "leaf bitset {} has undefined bits: {:x}".format( 523 bitset.name, ~(pat.mask | pat.field_mask) & ((1 << sz) - 1)) 524 525 # TODO somehow validating that only one bitset in a hierarchy 526 # matches any given bit pattern would be useful. 527 528 # TODO we should probably be able to look at the contexts where 529 # an expression is evaluated and verify that it doesn't have any 530 # {VARNAME} references that would be unresolved at evaluation time 531 532 def format(self): 533 ''' Generate format string used by printf(..) and friends ''' 534 parts = [] 535 words = self.bitsize / 32 536 537 for i in range(int(words)): 538 parts.append('%08x') 539 540 fmt = ''.join(parts) 541 542 return f"\"{fmt[1:]}\"" 543 544 def value(self): 545 ''' Generate format values used by printf(..) and friends ''' 546 parts = [] 547 words = self.bitsize / 32 548 549 for i in range(int(words) - 1, -1, -1): 550 parts.append('v[' + str(i) + ']') 551 552 return ', '.join(parts) 553 554 def split_bits(self, value, bitsize): 555 ''' Split `value` into a list of bitsize-bit integers ''' 556 mask, parts = (1 << bitsize) - 1, [] 557 words = self.bitsize / bitsize 558 559 while value: 560 parts.append(hex(value & mask)) 561 value >>= bitsize 562 563 # Add 'missing' words 564 while len(parts) < words: 565 parts.append('0x0') 566 567 return parts 568 569 # Returns all bitsets in the ISA, including all per-gen variants, in 570 # (name, bitset) pairs. 571 def all_bitsets(self): 572 for name, bitset in self.bitsets.items(): 573 yield name, bitset 574 for name, bitsets in self.leafs.items(): 575 if len(bitsets) == 1: 576 continue 577 for bitset in bitsets: 578 yield name, bitset 579