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