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