1#!/usr/bin/env python 2# Copyright (c) 2018 Linaro Limited 3# 4# This library is free software; you can redistribute it and/or 5# modify it under the terms of the GNU Lesser General Public 6# License as published by the Free Software Foundation; either 7# version 2 of the License, or (at your option) any later version. 8# 9# This library is distributed in the hope that it will be useful, 10# but WITHOUT ANY WARRANTY; without even the implied warranty of 11# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 12# Lesser General Public License for more details. 13# 14# You should have received a copy of the GNU Lesser General Public 15# License along with this library; if not, see <http://www.gnu.org/licenses/>. 16# 17 18# 19# Generate a decoding tree from a specification file. 20# See the syntax and semantics in docs/devel/decodetree.rst. 21# 22 23import os 24import re 25import sys 26import getopt 27 28insnwidth = 32 29insnmask = 0xffffffff 30fields = {} 31arguments = {} 32formats = {} 33patterns = [] 34allpatterns = [] 35 36translate_prefix = 'trans' 37translate_scope = 'static ' 38input_file = '' 39output_file = None 40output_fd = None 41insntype = 'uint32_t' 42decode_function = 'decode' 43 44re_ident = '[a-zA-Z][a-zA-Z0-9_]*' 45 46 47def error_with_file(file, lineno, *args): 48 """Print an error message from file:line and args and exit.""" 49 global output_file 50 global output_fd 51 52 if lineno: 53 r = '{0}:{1}: error:'.format(file, lineno) 54 elif input_file: 55 r = '{0}: error:'.format(file) 56 else: 57 r = 'error:' 58 for a in args: 59 r += ' ' + str(a) 60 r += '\n' 61 sys.stderr.write(r) 62 if output_file and output_fd: 63 output_fd.close() 64 os.remove(output_file) 65 exit(1) 66 67def error(lineno, *args): 68 error_with_file(input_file, lineno, args) 69 70def output(*args): 71 global output_fd 72 for a in args: 73 output_fd.write(a) 74 75 76if sys.version_info >= (3, 4): 77 re_fullmatch = re.fullmatch 78else: 79 def re_fullmatch(pat, str): 80 return re.match('^' + pat + '$', str) 81 82 83def output_autogen(): 84 output('/* This file is autogenerated by scripts/decodetree.py. */\n\n') 85 86 87def str_indent(c): 88 """Return a string with C spaces""" 89 return ' ' * c 90 91 92def str_fields(fields): 93 """Return a string uniquely identifing FIELDS""" 94 r = '' 95 for n in sorted(fields.keys()): 96 r += '_' + n 97 return r[1:] 98 99 100def str_match_bits(bits, mask): 101 """Return a string pretty-printing BITS/MASK""" 102 global insnwidth 103 104 i = 1 << (insnwidth - 1) 105 space = 0x01010100 106 r = '' 107 while i != 0: 108 if i & mask: 109 if i & bits: 110 r += '1' 111 else: 112 r += '0' 113 else: 114 r += '.' 115 if i & space: 116 r += ' ' 117 i >>= 1 118 return r 119 120 121def is_pow2(x): 122 """Return true iff X is equal to a power of 2.""" 123 return (x & (x - 1)) == 0 124 125 126def ctz(x): 127 """Return the number of times 2 factors into X.""" 128 r = 0 129 while ((x >> r) & 1) == 0: 130 r += 1 131 return r 132 133 134def is_contiguous(bits): 135 shift = ctz(bits) 136 if is_pow2((bits >> shift) + 1): 137 return shift 138 else: 139 return -1 140 141 142def eq_fields_for_args(flds_a, flds_b): 143 if len(flds_a) != len(flds_b): 144 return False 145 for k, a in flds_a.items(): 146 if k not in flds_b: 147 return False 148 return True 149 150 151def eq_fields_for_fmts(flds_a, flds_b): 152 if len(flds_a) != len(flds_b): 153 return False 154 for k, a in flds_a.items(): 155 if k not in flds_b: 156 return False 157 b = flds_b[k] 158 if a.__class__ != b.__class__ or a != b: 159 return False 160 return True 161 162 163class Field: 164 """Class representing a simple instruction field""" 165 def __init__(self, sign, pos, len): 166 self.sign = sign 167 self.pos = pos 168 self.len = len 169 self.mask = ((1 << len) - 1) << pos 170 171 def __str__(self): 172 if self.sign: 173 s = 's' 174 else: 175 s = '' 176 return str(self.pos) + ':' + s + str(self.len) 177 178 def str_extract(self): 179 if self.sign: 180 extr = 'sextract32' 181 else: 182 extr = 'extract32' 183 return '{0}(insn, {1}, {2})'.format(extr, self.pos, self.len) 184 185 def __eq__(self, other): 186 return self.sign == other.sign and self.sign == other.sign 187 188 def __ne__(self, other): 189 return not self.__eq__(other) 190# end Field 191 192 193class MultiField: 194 """Class representing a compound instruction field""" 195 def __init__(self, subs, mask): 196 self.subs = subs 197 self.sign = subs[0].sign 198 self.mask = mask 199 200 def __str__(self): 201 return str(self.subs) 202 203 def str_extract(self): 204 ret = '0' 205 pos = 0 206 for f in reversed(self.subs): 207 if pos == 0: 208 ret = f.str_extract() 209 else: 210 ret = 'deposit32({0}, {1}, {2}, {3})' \ 211 .format(ret, pos, 32 - pos, f.str_extract()) 212 pos += f.len 213 return ret 214 215 def __ne__(self, other): 216 if len(self.subs) != len(other.subs): 217 return True 218 for a, b in zip(self.subs, other.subs): 219 if a.__class__ != b.__class__ or a != b: 220 return True 221 return False 222 223 def __eq__(self, other): 224 return not self.__ne__(other) 225# end MultiField 226 227 228class ConstField: 229 """Class representing an argument field with constant value""" 230 def __init__(self, value): 231 self.value = value 232 self.mask = 0 233 self.sign = value < 0 234 235 def __str__(self): 236 return str(self.value) 237 238 def str_extract(self): 239 return str(self.value) 240 241 def __cmp__(self, other): 242 return self.value - other.value 243# end ConstField 244 245 246class FunctionField: 247 """Class representing a field passed through an expander""" 248 def __init__(self, func, base): 249 self.mask = base.mask 250 self.sign = base.sign 251 self.base = base 252 self.func = func 253 254 def __str__(self): 255 return self.func + '(' + str(self.base) + ')' 256 257 def str_extract(self): 258 return self.func + '(' + self.base.str_extract() + ')' 259 260 def __eq__(self, other): 261 return self.func == other.func and self.base == other.base 262 263 def __ne__(self, other): 264 return not self.__eq__(other) 265# end FunctionField 266 267 268class Arguments: 269 """Class representing the extracted fields of a format""" 270 def __init__(self, nm, flds, extern): 271 self.name = nm 272 self.extern = extern 273 self.fields = sorted(flds) 274 275 def __str__(self): 276 return self.name + ' ' + str(self.fields) 277 278 def struct_name(self): 279 return 'arg_' + self.name 280 281 def output_def(self): 282 if not self.extern: 283 output('typedef struct {\n') 284 for n in self.fields: 285 output(' int ', n, ';\n') 286 output('} ', self.struct_name(), ';\n\n') 287# end Arguments 288 289 290class General: 291 """Common code between instruction formats and instruction patterns""" 292 def __init__(self, name, lineno, base, fixb, fixm, udfm, fldm, flds): 293 self.name = name 294 self.file = input_file 295 self.lineno = lineno 296 self.base = base 297 self.fixedbits = fixb 298 self.fixedmask = fixm 299 self.undefmask = udfm 300 self.fieldmask = fldm 301 self.fields = flds 302 303 def __str__(self): 304 return self.name + ' ' + str_match_bits(self.fixedbits, self.fixedmask) 305 306 def str1(self, i): 307 return str_indent(i) + self.__str__() 308# end General 309 310 311class Format(General): 312 """Class representing an instruction format""" 313 314 def extract_name(self): 315 global decode_function 316 return decode_function + '_extract_' + self.name 317 318 def output_extract(self): 319 output('static void ', self.extract_name(), '(', 320 self.base.struct_name(), ' *a, ', insntype, ' insn)\n{\n') 321 for n, f in self.fields.items(): 322 output(' a->', n, ' = ', f.str_extract(), ';\n') 323 output('}\n\n') 324# end Format 325 326 327class Pattern(General): 328 """Class representing an instruction pattern""" 329 330 def output_decl(self): 331 global translate_scope 332 global translate_prefix 333 output('typedef ', self.base.base.struct_name(), 334 ' arg_', self.name, ';\n') 335 output(translate_scope, 'bool ', translate_prefix, '_', self.name, 336 '(DisasContext *ctx, arg_', self.name, ' *a);\n') 337 338 def output_code(self, i, extracted, outerbits, outermask): 339 global translate_prefix 340 ind = str_indent(i) 341 arg = self.base.base.name 342 output(ind, '/* ', self.file, ':', str(self.lineno), ' */\n') 343 if not extracted: 344 output(ind, self.base.extract_name(), '(&u.f_', arg, ', insn);\n') 345 for n, f in self.fields.items(): 346 output(ind, 'u.f_', arg, '.', n, ' = ', f.str_extract(), ';\n') 347 output(ind, 'if (', translate_prefix, '_', self.name, 348 '(ctx, &u.f_', arg, ')) return true;\n') 349# end Pattern 350 351 352class MultiPattern(General): 353 """Class representing an overlapping set of instruction patterns""" 354 355 def __init__(self, lineno, pats, fixb, fixm, udfm): 356 self.file = input_file 357 self.lineno = lineno 358 self.pats = pats 359 self.base = None 360 self.fixedbits = fixb 361 self.fixedmask = fixm 362 self.undefmask = udfm 363 364 def __str__(self): 365 r = "{" 366 for p in self.pats: 367 r = r + ' ' + str(p) 368 return r + "}" 369 370 def output_decl(self): 371 for p in self.pats: 372 p.output_decl() 373 374 def output_code(self, i, extracted, outerbits, outermask): 375 global translate_prefix 376 ind = str_indent(i) 377 for p in self.pats: 378 if outermask != p.fixedmask: 379 innermask = p.fixedmask & ~outermask 380 innerbits = p.fixedbits & ~outermask 381 output(ind, 'if ((insn & ', 382 '0x{0:08x}) == 0x{1:08x}'.format(innermask, innerbits), 383 ') {\n') 384 output(ind, ' /* ', 385 str_match_bits(p.fixedbits, p.fixedmask), ' */\n') 386 p.output_code(i + 4, extracted, p.fixedbits, p.fixedmask) 387 output(ind, '}\n') 388 else: 389 p.output_code(i, extracted, p.fixedbits, p.fixedmask) 390#end MultiPattern 391 392 393def parse_field(lineno, name, toks): 394 """Parse one instruction field from TOKS at LINENO""" 395 global fields 396 global re_ident 397 global insnwidth 398 399 # A "simple" field will have only one entry; 400 # a "multifield" will have several. 401 subs = [] 402 width = 0 403 func = None 404 for t in toks: 405 if re_fullmatch('!function=' + re_ident, t): 406 if func: 407 error(lineno, 'duplicate function') 408 func = t.split('=') 409 func = func[1] 410 continue 411 412 if re_fullmatch('[0-9]+:s[0-9]+', t): 413 # Signed field extract 414 subtoks = t.split(':s') 415 sign = True 416 elif re_fullmatch('[0-9]+:[0-9]+', t): 417 # Unsigned field extract 418 subtoks = t.split(':') 419 sign = False 420 else: 421 error(lineno, 'invalid field token "{0}"'.format(t)) 422 po = int(subtoks[0]) 423 le = int(subtoks[1]) 424 if po + le > insnwidth: 425 error(lineno, 'field {0} too large'.format(t)) 426 f = Field(sign, po, le) 427 subs.append(f) 428 width += le 429 430 if width > insnwidth: 431 error(lineno, 'field too large') 432 if len(subs) == 1: 433 f = subs[0] 434 else: 435 mask = 0 436 for s in subs: 437 if mask & s.mask: 438 error(lineno, 'field components overlap') 439 mask |= s.mask 440 f = MultiField(subs, mask) 441 if func: 442 f = FunctionField(func, f) 443 444 if name in fields: 445 error(lineno, 'duplicate field', name) 446 fields[name] = f 447# end parse_field 448 449 450def parse_arguments(lineno, name, toks): 451 """Parse one argument set from TOKS at LINENO""" 452 global arguments 453 global re_ident 454 455 flds = [] 456 extern = False 457 for t in toks: 458 if re_fullmatch('!extern', t): 459 extern = True 460 continue 461 if not re_fullmatch(re_ident, t): 462 error(lineno, 'invalid argument set token "{0}"'.format(t)) 463 if t in flds: 464 error(lineno, 'duplicate argument "{0}"'.format(t)) 465 flds.append(t) 466 467 if name in arguments: 468 error(lineno, 'duplicate argument set', name) 469 arguments[name] = Arguments(name, flds, extern) 470# end parse_arguments 471 472 473def lookup_field(lineno, name): 474 global fields 475 if name in fields: 476 return fields[name] 477 error(lineno, 'undefined field', name) 478 479 480def add_field(lineno, flds, new_name, f): 481 if new_name in flds: 482 error(lineno, 'duplicate field', new_name) 483 flds[new_name] = f 484 return flds 485 486 487def add_field_byname(lineno, flds, new_name, old_name): 488 return add_field(lineno, flds, new_name, lookup_field(lineno, old_name)) 489 490 491def infer_argument_set(flds): 492 global arguments 493 global decode_function 494 495 for arg in arguments.values(): 496 if eq_fields_for_args(flds, arg.fields): 497 return arg 498 499 name = decode_function + str(len(arguments)) 500 arg = Arguments(name, flds.keys(), False) 501 arguments[name] = arg 502 return arg 503 504 505def infer_format(arg, fieldmask, flds): 506 global arguments 507 global formats 508 global decode_function 509 510 const_flds = {} 511 var_flds = {} 512 for n, c in flds.items(): 513 if c is ConstField: 514 const_flds[n] = c 515 else: 516 var_flds[n] = c 517 518 # Look for an existing format with the same argument set and fields 519 for fmt in formats.values(): 520 if arg and fmt.base != arg: 521 continue 522 if fieldmask != fmt.fieldmask: 523 continue 524 if not eq_fields_for_fmts(flds, fmt.fields): 525 continue 526 return (fmt, const_flds) 527 528 name = decode_function + '_Fmt_' + str(len(formats)) 529 if not arg: 530 arg = infer_argument_set(flds) 531 532 fmt = Format(name, 0, arg, 0, 0, 0, fieldmask, var_flds) 533 formats[name] = fmt 534 535 return (fmt, const_flds) 536# end infer_format 537 538 539def parse_generic(lineno, is_format, name, toks): 540 """Parse one instruction format from TOKS at LINENO""" 541 global fields 542 global arguments 543 global formats 544 global patterns 545 global allpatterns 546 global re_ident 547 global insnwidth 548 global insnmask 549 550 fixedmask = 0 551 fixedbits = 0 552 undefmask = 0 553 width = 0 554 flds = {} 555 arg = None 556 fmt = None 557 for t in toks: 558 # '&Foo' gives a format an explcit argument set. 559 if t[0] == '&': 560 tt = t[1:] 561 if arg: 562 error(lineno, 'multiple argument sets') 563 if tt in arguments: 564 arg = arguments[tt] 565 else: 566 error(lineno, 'undefined argument set', t) 567 continue 568 569 # '@Foo' gives a pattern an explicit format. 570 if t[0] == '@': 571 tt = t[1:] 572 if fmt: 573 error(lineno, 'multiple formats') 574 if tt in formats: 575 fmt = formats[tt] 576 else: 577 error(lineno, 'undefined format', t) 578 continue 579 580 # '%Foo' imports a field. 581 if t[0] == '%': 582 tt = t[1:] 583 flds = add_field_byname(lineno, flds, tt, tt) 584 continue 585 586 # 'Foo=%Bar' imports a field with a different name. 587 if re_fullmatch(re_ident + '=%' + re_ident, t): 588 (fname, iname) = t.split('=%') 589 flds = add_field_byname(lineno, flds, fname, iname) 590 continue 591 592 # 'Foo=number' sets an argument field to a constant value 593 if re_fullmatch(re_ident + '=[+-]?[0-9]+', t): 594 (fname, value) = t.split('=') 595 value = int(value) 596 flds = add_field(lineno, flds, fname, ConstField(value)) 597 continue 598 599 # Pattern of 0s, 1s, dots and dashes indicate required zeros, 600 # required ones, or dont-cares. 601 if re_fullmatch('[01.-]+', t): 602 shift = len(t) 603 fms = t.replace('0', '1') 604 fms = fms.replace('.', '0') 605 fms = fms.replace('-', '0') 606 fbs = t.replace('.', '0') 607 fbs = fbs.replace('-', '0') 608 ubm = t.replace('1', '0') 609 ubm = ubm.replace('.', '0') 610 ubm = ubm.replace('-', '1') 611 fms = int(fms, 2) 612 fbs = int(fbs, 2) 613 ubm = int(ubm, 2) 614 fixedbits = (fixedbits << shift) | fbs 615 fixedmask = (fixedmask << shift) | fms 616 undefmask = (undefmask << shift) | ubm 617 # Otherwise, fieldname:fieldwidth 618 elif re_fullmatch(re_ident + ':s?[0-9]+', t): 619 (fname, flen) = t.split(':') 620 sign = False 621 if flen[0] == 's': 622 sign = True 623 flen = flen[1:] 624 shift = int(flen, 10) 625 if shift + width > insnwidth: 626 error(lineno, 'field {0} exceeds insnwidth'.format(fname)) 627 f = Field(sign, insnwidth - width - shift, shift) 628 flds = add_field(lineno, flds, fname, f) 629 fixedbits <<= shift 630 fixedmask <<= shift 631 undefmask <<= shift 632 else: 633 error(lineno, 'invalid token "{0}"'.format(t)) 634 width += shift 635 636 # We should have filled in all of the bits of the instruction. 637 if not (is_format and width == 0) and width != insnwidth: 638 error(lineno, 'definition has {0} bits'.format(width)) 639 640 # Do not check for fields overlaping fields; one valid usage 641 # is to be able to duplicate fields via import. 642 fieldmask = 0 643 for f in flds.values(): 644 fieldmask |= f.mask 645 646 # Fix up what we've parsed to match either a format or a pattern. 647 if is_format: 648 # Formats cannot reference formats. 649 if fmt: 650 error(lineno, 'format referencing format') 651 # If an argument set is given, then there should be no fields 652 # without a place to store it. 653 if arg: 654 for f in flds.keys(): 655 if f not in arg.fields: 656 error(lineno, 'field {0} not in argument set {1}' 657 .format(f, arg.name)) 658 else: 659 arg = infer_argument_set(flds) 660 if name in formats: 661 error(lineno, 'duplicate format name', name) 662 fmt = Format(name, lineno, arg, fixedbits, fixedmask, 663 undefmask, fieldmask, flds) 664 formats[name] = fmt 665 else: 666 # Patterns can reference a format ... 667 if fmt: 668 # ... but not an argument simultaneously 669 if arg: 670 error(lineno, 'pattern specifies both format and argument set') 671 if fixedmask & fmt.fixedmask: 672 error(lineno, 'pattern fixed bits overlap format fixed bits') 673 fieldmask |= fmt.fieldmask 674 fixedbits |= fmt.fixedbits 675 fixedmask |= fmt.fixedmask 676 undefmask |= fmt.undefmask 677 else: 678 (fmt, flds) = infer_format(arg, fieldmask, flds) 679 arg = fmt.base 680 for f in flds.keys(): 681 if f not in arg.fields: 682 error(lineno, 'field {0} not in argument set {1}' 683 .format(f, arg.name)) 684 if f in fmt.fields.keys(): 685 error(lineno, 'field {0} set by format and pattern'.format(f)) 686 for f in arg.fields: 687 if f not in flds.keys() and f not in fmt.fields.keys(): 688 error(lineno, 'field {0} not initialized'.format(f)) 689 pat = Pattern(name, lineno, fmt, fixedbits, fixedmask, 690 undefmask, fieldmask, flds) 691 patterns.append(pat) 692 allpatterns.append(pat) 693 694 # Validate the masks that we have assembled. 695 if fieldmask & fixedmask: 696 error(lineno, 'fieldmask overlaps fixedmask (0x{0:08x} & 0x{1:08x})' 697 .format(fieldmask, fixedmask)) 698 if fieldmask & undefmask: 699 error(lineno, 'fieldmask overlaps undefmask (0x{0:08x} & 0x{1:08x})' 700 .format(fieldmask, undefmask)) 701 if fixedmask & undefmask: 702 error(lineno, 'fixedmask overlaps undefmask (0x{0:08x} & 0x{1:08x})' 703 .format(fixedmask, undefmask)) 704 if not is_format: 705 allbits = fieldmask | fixedmask | undefmask 706 if allbits != insnmask: 707 error(lineno, 'bits left unspecified (0x{0:08x})' 708 .format(allbits ^ insnmask)) 709# end parse_general 710 711def build_multi_pattern(lineno, pats): 712 """Validate the Patterns going into a MultiPattern.""" 713 global patterns 714 global insnmask 715 716 if len(pats) < 2: 717 error(lineno, 'less than two patterns within braces') 718 719 fixedmask = insnmask 720 undefmask = insnmask 721 722 # Collect fixed/undefmask for all of the children. 723 # Move the defining lineno back to that of the first child. 724 for p in pats: 725 fixedmask &= p.fixedmask 726 undefmask &= p.undefmask 727 if p.lineno < lineno: 728 lineno = p.lineno 729 730 repeat = True 731 while repeat: 732 if fixedmask == 0: 733 error(lineno, 'no overlap in patterns within braces') 734 fixedbits = None 735 for p in pats: 736 thisbits = p.fixedbits & fixedmask 737 if fixedbits is None: 738 fixedbits = thisbits 739 elif fixedbits != thisbits: 740 fixedmask &= ~(fixedbits ^ thisbits) 741 break 742 else: 743 repeat = False 744 745 mp = MultiPattern(lineno, pats, fixedbits, fixedmask, undefmask) 746 patterns.append(mp) 747# end build_multi_pattern 748 749def parse_file(f): 750 """Parse all of the patterns within a file""" 751 752 global patterns 753 754 # Read all of the lines of the file. Concatenate lines 755 # ending in backslash; discard empty lines and comments. 756 toks = [] 757 lineno = 0 758 nesting = 0 759 saved_pats = [] 760 761 for line in f: 762 lineno += 1 763 764 # Expand and strip spaces, to find indent. 765 line = line.rstrip() 766 line = line.expandtabs() 767 len1 = len(line) 768 line = line.lstrip() 769 len2 = len(line) 770 771 # Discard comments 772 end = line.find('#') 773 if end >= 0: 774 line = line[:end] 775 776 t = line.split() 777 if len(toks) != 0: 778 # Next line after continuation 779 toks.extend(t) 780 else: 781 # Allow completely blank lines. 782 if len1 == 0: 783 continue 784 indent = len1 - len2 785 # Empty line due to comment. 786 if len(t) == 0: 787 # Indentation must be correct, even for comment lines. 788 if indent != nesting: 789 error(lineno, 'indentation ', indent, ' != ', nesting) 790 continue 791 start_lineno = lineno 792 toks = t 793 794 # Continuation? 795 if toks[-1] == '\\': 796 toks.pop() 797 continue 798 799 name = toks[0] 800 del toks[0] 801 802 # End nesting? 803 if name == '}': 804 if nesting == 0: 805 error(start_lineno, 'mismatched close brace') 806 if len(toks) != 0: 807 error(start_lineno, 'extra tokens after close brace') 808 nesting -= 2 809 if indent != nesting: 810 error(start_lineno, 'indentation ', indent, ' != ', nesting) 811 pats = patterns 812 patterns = saved_pats.pop() 813 build_multi_pattern(lineno, pats) 814 toks = [] 815 continue 816 817 # Everything else should have current indentation. 818 if indent != nesting: 819 error(start_lineno, 'indentation ', indent, ' != ', nesting) 820 821 # Start nesting? 822 if name == '{': 823 if len(toks) != 0: 824 error(start_lineno, 'extra tokens after open brace') 825 saved_pats.append(patterns) 826 patterns = [] 827 nesting += 2 828 toks = [] 829 continue 830 831 # Determine the type of object needing to be parsed. 832 if name[0] == '%': 833 parse_field(start_lineno, name[1:], toks) 834 elif name[0] == '&': 835 parse_arguments(start_lineno, name[1:], toks) 836 elif name[0] == '@': 837 parse_generic(start_lineno, True, name[1:], toks) 838 else: 839 parse_generic(start_lineno, False, name, toks) 840 toks = [] 841# end parse_file 842 843 844class Tree: 845 """Class representing a node in a decode tree""" 846 847 def __init__(self, fm, tm): 848 self.fixedmask = fm 849 self.thismask = tm 850 self.subs = [] 851 self.base = None 852 853 def str1(self, i): 854 ind = str_indent(i) 855 r = '{0}{1:08x}'.format(ind, self.fixedmask) 856 if self.format: 857 r += ' ' + self.format.name 858 r += ' [\n' 859 for (b, s) in self.subs: 860 r += '{0} {1:08x}:\n'.format(ind, b) 861 r += s.str1(i + 4) + '\n' 862 r += ind + ']' 863 return r 864 865 def __str__(self): 866 return self.str1(0) 867 868 def output_code(self, i, extracted, outerbits, outermask): 869 ind = str_indent(i) 870 871 # If we identified all nodes below have the same format, 872 # extract the fields now. 873 if not extracted and self.base: 874 output(ind, self.base.extract_name(), 875 '(&u.f_', self.base.base.name, ', insn);\n') 876 extracted = True 877 878 # Attempt to aid the compiler in producing compact switch statements. 879 # If the bits in the mask are contiguous, extract them. 880 sh = is_contiguous(self.thismask) 881 if sh > 0: 882 # Propagate SH down into the local functions. 883 def str_switch(b, sh=sh): 884 return '(insn >> {0}) & 0x{1:x}'.format(sh, b >> sh) 885 886 def str_case(b, sh=sh): 887 return '0x{0:x}'.format(b >> sh) 888 else: 889 def str_switch(b): 890 return 'insn & 0x{0:08x}'.format(b) 891 892 def str_case(b): 893 return '0x{0:08x}'.format(b) 894 895 output(ind, 'switch (', str_switch(self.thismask), ') {\n') 896 for b, s in sorted(self.subs): 897 assert (self.thismask & ~s.fixedmask) == 0 898 innermask = outermask | self.thismask 899 innerbits = outerbits | b 900 output(ind, 'case ', str_case(b), ':\n') 901 output(ind, ' /* ', 902 str_match_bits(innerbits, innermask), ' */\n') 903 s.output_code(i + 4, extracted, innerbits, innermask) 904 output(ind, ' return false;\n') 905 output(ind, '}\n') 906# end Tree 907 908 909def build_tree(pats, outerbits, outermask): 910 # Find the intersection of all remaining fixedmask. 911 innermask = ~outermask & insnmask 912 for i in pats: 913 innermask &= i.fixedmask 914 915 if innermask == 0: 916 text = 'overlapping patterns:' 917 for p in pats: 918 text += '\n' + p.file + ':' + str(p.lineno) + ': ' + str(p) 919 error_with_file(pats[0].file, pats[0].lineno, text) 920 921 fullmask = outermask | innermask 922 923 # Sort each element of pats into the bin selected by the mask. 924 bins = {} 925 for i in pats: 926 fb = i.fixedbits & innermask 927 if fb in bins: 928 bins[fb].append(i) 929 else: 930 bins[fb] = [i] 931 932 # We must recurse if any bin has more than one element or if 933 # the single element in the bin has not been fully matched. 934 t = Tree(fullmask, innermask) 935 936 for b, l in bins.items(): 937 s = l[0] 938 if len(l) > 1 or s.fixedmask & ~fullmask != 0: 939 s = build_tree(l, b | outerbits, fullmask) 940 t.subs.append((b, s)) 941 942 return t 943# end build_tree 944 945 946def prop_format(tree): 947 """Propagate Format objects into the decode tree""" 948 949 # Depth first search. 950 for (b, s) in tree.subs: 951 if isinstance(s, Tree): 952 prop_format(s) 953 954 # If all entries in SUBS have the same format, then 955 # propagate that into the tree. 956 f = None 957 for (b, s) in tree.subs: 958 if f is None: 959 f = s.base 960 if f is None: 961 return 962 if f is not s.base: 963 return 964 tree.base = f 965# end prop_format 966 967 968def main(): 969 global arguments 970 global formats 971 global patterns 972 global allpatterns 973 global translate_scope 974 global translate_prefix 975 global output_fd 976 global output_file 977 global input_file 978 global insnwidth 979 global insntype 980 global insnmask 981 global decode_function 982 983 decode_scope = 'static ' 984 985 long_opts = ['decode=', 'translate=', 'output=', 'insnwidth=', 986 'static-decode='] 987 try: 988 (opts, args) = getopt.getopt(sys.argv[1:], 'o:w:', long_opts) 989 except getopt.GetoptError as err: 990 error(0, err) 991 for o, a in opts: 992 if o in ('-o', '--output'): 993 output_file = a 994 elif o == '--decode': 995 decode_function = a 996 decode_scope = '' 997 elif o == '--static-decode': 998 decode_function = a 999 elif o == '--translate': 1000 translate_prefix = a 1001 translate_scope = '' 1002 elif o in ('-w', '--insnwidth'): 1003 insnwidth = int(a) 1004 if insnwidth == 16: 1005 insntype = 'uint16_t' 1006 insnmask = 0xffff 1007 elif insnwidth != 32: 1008 error(0, 'cannot handle insns of width', insnwidth) 1009 else: 1010 assert False, 'unhandled option' 1011 1012 if len(args) < 1: 1013 error(0, 'missing input file') 1014 for filename in args: 1015 input_file = filename 1016 f = open(filename, 'r') 1017 parse_file(f) 1018 f.close() 1019 1020 t = build_tree(patterns, 0, 0) 1021 prop_format(t) 1022 1023 if output_file: 1024 output_fd = open(output_file, 'w') 1025 else: 1026 output_fd = sys.stdout 1027 1028 output_autogen() 1029 for n in sorted(arguments.keys()): 1030 f = arguments[n] 1031 f.output_def() 1032 1033 # A single translate function can be invoked for different patterns. 1034 # Make sure that the argument sets are the same, and declare the 1035 # function only once. 1036 out_pats = {} 1037 for i in allpatterns: 1038 if i.name in out_pats: 1039 p = out_pats[i.name] 1040 if i.base.base != p.base.base: 1041 error(0, i.name, ' has conflicting argument sets') 1042 else: 1043 i.output_decl() 1044 out_pats[i.name] = i 1045 output('\n') 1046 1047 for n in sorted(formats.keys()): 1048 f = formats[n] 1049 f.output_extract() 1050 1051 output(decode_scope, 'bool ', decode_function, 1052 '(DisasContext *ctx, ', insntype, ' insn)\n{\n') 1053 1054 i4 = str_indent(4) 1055 1056 if len(allpatterns) != 0: 1057 output(i4, 'union {\n') 1058 for n in sorted(arguments.keys()): 1059 f = arguments[n] 1060 output(i4, i4, f.struct_name(), ' f_', f.name, ';\n') 1061 output(i4, '} u;\n\n') 1062 t.output_code(4, False, 0, 0) 1063 1064 output(i4, 'return false;\n') 1065 output('}\n') 1066 1067 if output_file: 1068 output_fd.close() 1069# end main 1070 1071 1072if __name__ == '__main__': 1073 main() 1074