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