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