* [PATCH 0/8] decodetree: Add non-overlapping groups @ 2020-05-18 16:40 Richard Henderson 2020-05-18 16:40 ` [PATCH 1/8] decodetree: Remove python 3.4 check Richard Henderson ` (7 more replies) 0 siblings, 8 replies; 22+ messages in thread From: Richard Henderson @ 2020-05-18 16:40 UTC (permalink / raw) To: qemu-devel; +Cc: peter.maydell This is a feature that Peter requested for completing the neon decodetree conversion. I ought to write some more test cases for this, but the change to t32.decode proves it is minimally functional. I'm undecided if I should add errors for useless nesting of these within other non- overlapping groups. While useless, it's likely still functional. r~ Richard Henderson (8): decodetree: Remove python 3.4 check decodetree: Tidy error_with_file decodetree: Rename MultiPattern to IncMultiPattern decodetree: Split out MultiPattern from IncMultiPattern decodetree: Allow group covering the entire insn space decodetree: Move semantic propagation into classes decodetree: Implement non-overlapping groups target/arm: Use a non-overlapping group for misc control target/arm/t32.decode | 4 +- ...decode => succ_pattern_group_nest2.decode} | 2 +- scripts/decodetree.py | 539 ++++++++++-------- 3 files changed, 307 insertions(+), 238 deletions(-) rename tests/decode/{err_pattern_group_nest1.decode => succ_pattern_group_nest2.decode} (85%) -- 2.20.1 ^ permalink raw reply [flat|nested] 22+ messages in thread
* [PATCH 1/8] decodetree: Remove python 3.4 check 2020-05-18 16:40 [PATCH 0/8] decodetree: Add non-overlapping groups Richard Henderson @ 2020-05-18 16:40 ` Richard Henderson 2020-05-18 16:46 ` Philippe Mathieu-Daudé 2020-05-29 9:35 ` Philippe Mathieu-Daudé 2020-05-18 16:40 ` [PATCH 2/8] decodetree: Tidy error_with_file Richard Henderson ` (6 subsequent siblings) 7 siblings, 2 replies; 22+ messages in thread From: Richard Henderson @ 2020-05-18 16:40 UTC (permalink / raw) To: qemu-devel; +Cc: peter.maydell We are now guaranteed python 3.5 or later. Signed-off-by: Richard Henderson <richard.henderson@linaro.org> --- scripts/decodetree.py | 25 +++++++++---------------- 1 file changed, 9 insertions(+), 16 deletions(-) diff --git a/scripts/decodetree.py b/scripts/decodetree.py index 46ab917807..f9d204aa36 100755 --- a/scripts/decodetree.py +++ b/scripts/decodetree.py @@ -75,13 +75,6 @@ def output(*args): output_fd.write(a) -if sys.version_info >= (3, 4): - re_fullmatch = re.fullmatch -else: - def re_fullmatch(pat, str): - return re.match('^' + pat + '$', str) - - def output_autogen(): output('/* This file is autogenerated by scripts/decodetree.py. */\n\n') @@ -428,18 +421,18 @@ def parse_field(lineno, name, toks): width = 0 func = None for t in toks: - if re_fullmatch('!function=' + re_ident, t): + if re.fullmatch('!function=' + re_ident, t): if func: error(lineno, 'duplicate function') func = t.split('=') func = func[1] continue - if re_fullmatch('[0-9]+:s[0-9]+', t): + if re.fullmatch('[0-9]+:s[0-9]+', t): # Signed field extract subtoks = t.split(':s') sign = True - elif re_fullmatch('[0-9]+:[0-9]+', t): + elif re.fullmatch('[0-9]+:[0-9]+', t): # Unsigned field extract subtoks = t.split(':') sign = False @@ -488,11 +481,11 @@ def parse_arguments(lineno, name, toks): flds = [] extern = False for t in toks: - if re_fullmatch('!extern', t): + if re.fullmatch('!extern', t): extern = True anyextern = True continue - if not re_fullmatch(re_ident, t): + if not re.fullmatch(re_ident, t): error(lineno, 'invalid argument set token "{0}"'.format(t)) if t in flds: error(lineno, 'duplicate argument "{0}"'.format(t)) @@ -621,13 +614,13 @@ def parse_generic(lineno, is_format, name, toks): continue # 'Foo=%Bar' imports a field with a different name. - if re_fullmatch(re_ident + '=%' + re_ident, t): + if re.fullmatch(re_ident + '=%' + re_ident, t): (fname, iname) = t.split('=%') flds = add_field_byname(lineno, flds, fname, iname) continue # 'Foo=number' sets an argument field to a constant value - if re_fullmatch(re_ident + '=[+-]?[0-9]+', t): + if re.fullmatch(re_ident + '=[+-]?[0-9]+', t): (fname, value) = t.split('=') value = int(value) flds = add_field(lineno, flds, fname, ConstField(value)) @@ -635,7 +628,7 @@ def parse_generic(lineno, is_format, name, toks): # Pattern of 0s, 1s, dots and dashes indicate required zeros, # required ones, or dont-cares. - if re_fullmatch('[01.-]+', t): + if re.fullmatch('[01.-]+', t): shift = len(t) fms = t.replace('0', '1') fms = fms.replace('.', '0') @@ -652,7 +645,7 @@ def parse_generic(lineno, is_format, name, toks): fixedmask = (fixedmask << shift) | fms undefmask = (undefmask << shift) | ubm # Otherwise, fieldname:fieldwidth - elif re_fullmatch(re_ident + ':s?[0-9]+', t): + elif re.fullmatch(re_ident + ':s?[0-9]+', t): (fname, flen) = t.split(':') sign = False if flen[0] == 's': -- 2.20.1 ^ permalink raw reply related [flat|nested] 22+ messages in thread
* Re: [PATCH 1/8] decodetree: Remove python 3.4 check 2020-05-18 16:40 ` [PATCH 1/8] decodetree: Remove python 3.4 check Richard Henderson @ 2020-05-18 16:46 ` Philippe Mathieu-Daudé 2020-05-29 9:35 ` Philippe Mathieu-Daudé 1 sibling, 0 replies; 22+ messages in thread From: Philippe Mathieu-Daudé @ 2020-05-18 16:46 UTC (permalink / raw) To: Richard Henderson, qemu-devel; +Cc: peter.maydell On 5/18/20 6:40 PM, Richard Henderson wrote: > We are now guaranteed python 3.5 or later. > > Signed-off-by: Richard Henderson <richard.henderson@linaro.org> > --- > scripts/decodetree.py | 25 +++++++++---------------- > 1 file changed, 9 insertions(+), 16 deletions(-) > > diff --git a/scripts/decodetree.py b/scripts/decodetree.py > index 46ab917807..f9d204aa36 100755 > --- a/scripts/decodetree.py > +++ b/scripts/decodetree.py > @@ -75,13 +75,6 @@ def output(*args): > output_fd.write(a) > > > -if sys.version_info >= (3, 4): > - re_fullmatch = re.fullmatch > -else: > - def re_fullmatch(pat, str): > - return re.match('^' + pat + '$', str) > - > - > def output_autogen(): > output('/* This file is autogenerated by scripts/decodetree.py. */\n\n') > > @@ -428,18 +421,18 @@ def parse_field(lineno, name, toks): > width = 0 > func = None > for t in toks: > - if re_fullmatch('!function=' + re_ident, t): > + if re.fullmatch('!function=' + re_ident, t): > if func: > error(lineno, 'duplicate function') > func = t.split('=') > func = func[1] > continue > > - if re_fullmatch('[0-9]+:s[0-9]+', t): > + if re.fullmatch('[0-9]+:s[0-9]+', t): > # Signed field extract > subtoks = t.split(':s') > sign = True > - elif re_fullmatch('[0-9]+:[0-9]+', t): > + elif re.fullmatch('[0-9]+:[0-9]+', t): > # Unsigned field extract > subtoks = t.split(':') > sign = False > @@ -488,11 +481,11 @@ def parse_arguments(lineno, name, toks): > flds = [] > extern = False > for t in toks: > - if re_fullmatch('!extern', t): > + if re.fullmatch('!extern', t): > extern = True > anyextern = True > continue > - if not re_fullmatch(re_ident, t): > + if not re.fullmatch(re_ident, t): > error(lineno, 'invalid argument set token "{0}"'.format(t)) > if t in flds: > error(lineno, 'duplicate argument "{0}"'.format(t)) > @@ -621,13 +614,13 @@ def parse_generic(lineno, is_format, name, toks): > continue > > # 'Foo=%Bar' imports a field with a different name. > - if re_fullmatch(re_ident + '=%' + re_ident, t): > + if re.fullmatch(re_ident + '=%' + re_ident, t): > (fname, iname) = t.split('=%') > flds = add_field_byname(lineno, flds, fname, iname) > continue > > # 'Foo=number' sets an argument field to a constant value > - if re_fullmatch(re_ident + '=[+-]?[0-9]+', t): > + if re.fullmatch(re_ident + '=[+-]?[0-9]+', t): > (fname, value) = t.split('=') > value = int(value) > flds = add_field(lineno, flds, fname, ConstField(value)) > @@ -635,7 +628,7 @@ def parse_generic(lineno, is_format, name, toks): > > # Pattern of 0s, 1s, dots and dashes indicate required zeros, > # required ones, or dont-cares. > - if re_fullmatch('[01.-]+', t): > + if re.fullmatch('[01.-]+', t): > shift = len(t) > fms = t.replace('0', '1') > fms = fms.replace('.', '0') > @@ -652,7 +645,7 @@ def parse_generic(lineno, is_format, name, toks): > fixedmask = (fixedmask << shift) | fms > undefmask = (undefmask << shift) | ubm > # Otherwise, fieldname:fieldwidth > - elif re_fullmatch(re_ident + ':s?[0-9]+', t): > + elif re.fullmatch(re_ident + ':s?[0-9]+', t): > (fname, flen) = t.split(':') > sign = False > if flen[0] == 's': > Reviewed-by: Philippe Mathieu-Daudé <philmd@redhat.com> ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: [PATCH 1/8] decodetree: Remove python 3.4 check 2020-05-18 16:40 ` [PATCH 1/8] decodetree: Remove python 3.4 check Richard Henderson 2020-05-18 16:46 ` Philippe Mathieu-Daudé @ 2020-05-29 9:35 ` Philippe Mathieu-Daudé 1 sibling, 0 replies; 22+ messages in thread From: Philippe Mathieu-Daudé @ 2020-05-29 9:35 UTC (permalink / raw) To: Richard Henderson, qemu-devel; +Cc: peter.maydell On 5/18/20 6:40 PM, Richard Henderson wrote: > We are now guaranteed python 3.5 or later. FYI this has been addressed by John Snow: https://www.mail-archive.com/qemu-block@nongnu.org/msg66830.html > > Signed-off-by: Richard Henderson <richard.henderson@linaro.org> > --- > scripts/decodetree.py | 25 +++++++++---------------- > 1 file changed, 9 insertions(+), 16 deletions(-) > > diff --git a/scripts/decodetree.py b/scripts/decodetree.py > index 46ab917807..f9d204aa36 100755 > --- a/scripts/decodetree.py > +++ b/scripts/decodetree.py > @@ -75,13 +75,6 @@ def output(*args): > output_fd.write(a) > > > -if sys.version_info >= (3, 4): > - re_fullmatch = re.fullmatch > -else: > - def re_fullmatch(pat, str): > - return re.match('^' + pat + '$', str) > - > - > def output_autogen(): > output('/* This file is autogenerated by scripts/decodetree.py. */\n\n') > > @@ -428,18 +421,18 @@ def parse_field(lineno, name, toks): > width = 0 > func = None > for t in toks: > - if re_fullmatch('!function=' + re_ident, t): > + if re.fullmatch('!function=' + re_ident, t): > if func: > error(lineno, 'duplicate function') > func = t.split('=') > func = func[1] > continue > > - if re_fullmatch('[0-9]+:s[0-9]+', t): > + if re.fullmatch('[0-9]+:s[0-9]+', t): > # Signed field extract > subtoks = t.split(':s') > sign = True > - elif re_fullmatch('[0-9]+:[0-9]+', t): > + elif re.fullmatch('[0-9]+:[0-9]+', t): > # Unsigned field extract > subtoks = t.split(':') > sign = False > @@ -488,11 +481,11 @@ def parse_arguments(lineno, name, toks): > flds = [] > extern = False > for t in toks: > - if re_fullmatch('!extern', t): > + if re.fullmatch('!extern', t): > extern = True > anyextern = True > continue > - if not re_fullmatch(re_ident, t): > + if not re.fullmatch(re_ident, t): > error(lineno, 'invalid argument set token "{0}"'.format(t)) > if t in flds: > error(lineno, 'duplicate argument "{0}"'.format(t)) > @@ -621,13 +614,13 @@ def parse_generic(lineno, is_format, name, toks): > continue > > # 'Foo=%Bar' imports a field with a different name. > - if re_fullmatch(re_ident + '=%' + re_ident, t): > + if re.fullmatch(re_ident + '=%' + re_ident, t): > (fname, iname) = t.split('=%') > flds = add_field_byname(lineno, flds, fname, iname) > continue > > # 'Foo=number' sets an argument field to a constant value > - if re_fullmatch(re_ident + '=[+-]?[0-9]+', t): > + if re.fullmatch(re_ident + '=[+-]?[0-9]+', t): > (fname, value) = t.split('=') > value = int(value) > flds = add_field(lineno, flds, fname, ConstField(value)) > @@ -635,7 +628,7 @@ def parse_generic(lineno, is_format, name, toks): > > # Pattern of 0s, 1s, dots and dashes indicate required zeros, > # required ones, or dont-cares. > - if re_fullmatch('[01.-]+', t): > + if re.fullmatch('[01.-]+', t): > shift = len(t) > fms = t.replace('0', '1') > fms = fms.replace('.', '0') > @@ -652,7 +645,7 @@ def parse_generic(lineno, is_format, name, toks): > fixedmask = (fixedmask << shift) | fms > undefmask = (undefmask << shift) | ubm > # Otherwise, fieldname:fieldwidth > - elif re_fullmatch(re_ident + ':s?[0-9]+', t): > + elif re.fullmatch(re_ident + ':s?[0-9]+', t): > (fname, flen) = t.split(':') > sign = False > if flen[0] == 's': > ^ permalink raw reply [flat|nested] 22+ messages in thread
* [PATCH 2/8] decodetree: Tidy error_with_file 2020-05-18 16:40 [PATCH 0/8] decodetree: Add non-overlapping groups Richard Henderson 2020-05-18 16:40 ` [PATCH 1/8] decodetree: Remove python 3.4 check Richard Henderson @ 2020-05-18 16:40 ` Richard Henderson 2020-06-02 14:24 ` Peter Maydell 2020-05-18 16:40 ` [PATCH 3/8] decodetree: Rename MultiPattern to IncMultiPattern Richard Henderson ` (5 subsequent siblings) 7 siblings, 1 reply; 22+ messages in thread From: Richard Henderson @ 2020-05-18 16:40 UTC (permalink / raw) To: qemu-devel; +Cc: peter.maydell Use proper varargs to print the arguments. Signed-off-by: Richard Henderson <richard.henderson@linaro.org> --- scripts/decodetree.py | 24 ++++++++++++++---------- 1 file changed, 14 insertions(+), 10 deletions(-) diff --git a/scripts/decodetree.py b/scripts/decodetree.py index f9d204aa36..b559db3086 100755 --- a/scripts/decodetree.py +++ b/scripts/decodetree.py @@ -51,23 +51,27 @@ def error_with_file(file, lineno, *args): global output_file global output_fd + prefix = '' + if file: + prefix += '{0}:'.format(file) if lineno: - r = '{0}:{1}: error:'.format(file, lineno) - elif input_file: - r = '{0}: error:'.format(file) - else: - r = 'error:' - for a in args: - r += ' ' + str(a) - r += '\n' - sys.stderr.write(r) + prefix += '{0}:'.format(lineno) + if prefix: + prefix += ' ' + print(prefix, end='error: ', file=sys.stderr) + print(*args, file=sys.stderr) + if output_file and output_fd: output_fd.close() os.remove(output_file) exit(1) +# end error_with_file + def error(lineno, *args): - error_with_file(input_file, lineno, args) + error_with_file(input_file, lineno, *args) +# end error + def output(*args): global output_fd -- 2.20.1 ^ permalink raw reply related [flat|nested] 22+ messages in thread
* Re: [PATCH 2/8] decodetree: Tidy error_with_file 2020-05-18 16:40 ` [PATCH 2/8] decodetree: Tidy error_with_file Richard Henderson @ 2020-06-02 14:24 ` Peter Maydell 0 siblings, 0 replies; 22+ messages in thread From: Peter Maydell @ 2020-06-02 14:24 UTC (permalink / raw) To: Richard Henderson; +Cc: QEMU Developers On Mon, 18 May 2020 at 17:40, Richard Henderson <richard.henderson@linaro.org> wrote: > > Use proper varargs to print the arguments. > > Signed-off-by: Richard Henderson <richard.henderson@linaro.org> > --- > scripts/decodetree.py | 24 ++++++++++++++---------- > 1 file changed, 14 insertions(+), 10 deletions(-) Reviewed-by: Peter Maydell <peter.maydell@linaro.org> thanks -- PMM ^ permalink raw reply [flat|nested] 22+ messages in thread
* [PATCH 3/8] decodetree: Rename MultiPattern to IncMultiPattern 2020-05-18 16:40 [PATCH 0/8] decodetree: Add non-overlapping groups Richard Henderson 2020-05-18 16:40 ` [PATCH 1/8] decodetree: Remove python 3.4 check Richard Henderson 2020-05-18 16:40 ` [PATCH 2/8] decodetree: Tidy error_with_file Richard Henderson @ 2020-05-18 16:40 ` Richard Henderson 2020-05-18 16:47 ` Philippe Mathieu-Daudé 2020-05-18 16:40 ` [PATCH 4/8] decodetree: Split out MultiPattern from IncMultiPattern Richard Henderson ` (4 subsequent siblings) 7 siblings, 1 reply; 22+ messages in thread From: Richard Henderson @ 2020-05-18 16:40 UTC (permalink / raw) To: qemu-devel; +Cc: peter.maydell Name the current node for "inclusive" multi-pattern, in preparation for adding a node for "exclusive" multi-pattern. Signed-off-by: Richard Henderson <richard.henderson@linaro.org> --- scripts/decodetree.py | 14 +++++++------- 1 file changed, 7 insertions(+), 7 deletions(-) diff --git a/scripts/decodetree.py b/scripts/decodetree.py index b559db3086..7af6b3056d 100755 --- a/scripts/decodetree.py +++ b/scripts/decodetree.py @@ -371,7 +371,7 @@ class Pattern(General): # end Pattern -class MultiPattern(General): +class IncMultiPattern(General): """Class representing an overlapping set of instruction patterns""" def __init__(self, lineno, pats, fixb, fixm, udfm, w): @@ -410,7 +410,7 @@ class MultiPattern(General): output(ind, '}\n') else: p.output_code(i, extracted, p.fixedbits, p.fixedmask) -#end MultiPattern +#end IncMultiPattern def parse_field(lineno, name, toks): @@ -751,8 +751,8 @@ def parse_generic(lineno, is_format, name, toks): .format(allbits ^ insnmask)) # end parse_general -def build_multi_pattern(lineno, pats): - """Validate the Patterns going into a MultiPattern.""" +def build_incmulti_pattern(lineno, pats): + """Validate the Patterns going into a IncMultiPattern.""" global patterns global insnmask @@ -792,9 +792,9 @@ def build_multi_pattern(lineno, pats): else: repeat = False - mp = MultiPattern(lineno, pats, fixedbits, fixedmask, undefmask, width) + mp = IncMultiPattern(lineno, pats, fixedbits, fixedmask, undefmask, width) patterns.append(mp) -# end build_multi_pattern +# end build_incmulti_pattern def parse_file(f): """Parse all of the patterns within a file""" @@ -860,7 +860,7 @@ def parse_file(f): error(start_lineno, 'indentation ', indent, ' != ', nesting) pats = patterns patterns = saved_pats.pop() - build_multi_pattern(lineno, pats) + build_incmulti_pattern(lineno, pats) toks = [] continue -- 2.20.1 ^ permalink raw reply related [flat|nested] 22+ messages in thread
* Re: [PATCH 3/8] decodetree: Rename MultiPattern to IncMultiPattern 2020-05-18 16:40 ` [PATCH 3/8] decodetree: Rename MultiPattern to IncMultiPattern Richard Henderson @ 2020-05-18 16:47 ` Philippe Mathieu-Daudé 0 siblings, 0 replies; 22+ messages in thread From: Philippe Mathieu-Daudé @ 2020-05-18 16:47 UTC (permalink / raw) To: Richard Henderson, qemu-devel; +Cc: peter.maydell On 5/18/20 6:40 PM, Richard Henderson wrote: > Name the current node for "inclusive" multi-pattern, in > preparation for adding a node for "exclusive" multi-pattern. > > Signed-off-by: Richard Henderson <richard.henderson@linaro.org> > --- > scripts/decodetree.py | 14 +++++++------- > 1 file changed, 7 insertions(+), 7 deletions(-) > > diff --git a/scripts/decodetree.py b/scripts/decodetree.py > index b559db3086..7af6b3056d 100755 > --- a/scripts/decodetree.py > +++ b/scripts/decodetree.py > @@ -371,7 +371,7 @@ class Pattern(General): > # end Pattern > > > -class MultiPattern(General): > +class IncMultiPattern(General): > """Class representing an overlapping set of instruction patterns""" > > def __init__(self, lineno, pats, fixb, fixm, udfm, w): > @@ -410,7 +410,7 @@ class MultiPattern(General): > output(ind, '}\n') > else: > p.output_code(i, extracted, p.fixedbits, p.fixedmask) > -#end MultiPattern > +#end IncMultiPattern > > > def parse_field(lineno, name, toks): > @@ -751,8 +751,8 @@ def parse_generic(lineno, is_format, name, toks): > .format(allbits ^ insnmask)) > # end parse_general > > -def build_multi_pattern(lineno, pats): > - """Validate the Patterns going into a MultiPattern.""" > +def build_incmulti_pattern(lineno, pats): > + """Validate the Patterns going into a IncMultiPattern.""" > global patterns > global insnmask > > @@ -792,9 +792,9 @@ def build_multi_pattern(lineno, pats): > else: > repeat = False > > - mp = MultiPattern(lineno, pats, fixedbits, fixedmask, undefmask, width) > + mp = IncMultiPattern(lineno, pats, fixedbits, fixedmask, undefmask, width) > patterns.append(mp) > -# end build_multi_pattern > +# end build_incmulti_pattern > > def parse_file(f): > """Parse all of the patterns within a file""" > @@ -860,7 +860,7 @@ def parse_file(f): > error(start_lineno, 'indentation ', indent, ' != ', nesting) > pats = patterns > patterns = saved_pats.pop() > - build_multi_pattern(lineno, pats) > + build_incmulti_pattern(lineno, pats) > toks = [] > continue > > Reviewed-by: Philippe Mathieu-Daudé <f4bug@amsat.org> ^ permalink raw reply [flat|nested] 22+ messages in thread
* [PATCH 4/8] decodetree: Split out MultiPattern from IncMultiPattern 2020-05-18 16:40 [PATCH 0/8] decodetree: Add non-overlapping groups Richard Henderson ` (2 preceding siblings ...) 2020-05-18 16:40 ` [PATCH 3/8] decodetree: Rename MultiPattern to IncMultiPattern Richard Henderson @ 2020-05-18 16:40 ` Richard Henderson 2020-05-18 16:47 ` Philippe Mathieu-Daudé 2020-05-18 16:40 ` [PATCH 5/8] decodetree: Allow group covering the entire insn space Richard Henderson ` (3 subsequent siblings) 7 siblings, 1 reply; 22+ messages in thread From: Richard Henderson @ 2020-05-18 16:40 UTC (permalink / raw) To: qemu-devel; +Cc: peter.maydell Signed-off-by: Richard Henderson <richard.henderson@linaro.org> --- scripts/decodetree.py | 37 ++++++++++++++++++++++++++----------- 1 file changed, 26 insertions(+), 11 deletions(-) diff --git a/scripts/decodetree.py b/scripts/decodetree.py index 7af6b3056d..ea313bcdea 100755 --- a/scripts/decodetree.py +++ b/scripts/decodetree.py @@ -371,7 +371,32 @@ class Pattern(General): # end Pattern -class IncMultiPattern(General): +class MultiPattern(General): + """Class representing a set of instruction patterns""" + + def __init__(self, lineno, pats): + self.file = input_file + self.lineno = lineno + self.pats = pats + self.base = None + self.fixedbits = 0 + self.fixedmask = 0 + self.undefmask = 0 + self.width = None + + def __str__(self): + r = 'group' + if self.fixedbits is not None: + r += ' ' + str_match_bits(self.fixedbits, self.fixedmask) + return r + + def output_decl(self): + for p in self.pats: + p.output_decl() +# end MultiPattern + + +class IncMultiPattern(MultiPattern): """Class representing an overlapping set of instruction patterns""" def __init__(self, lineno, pats, fixb, fixm, udfm, w): @@ -384,16 +409,6 @@ class IncMultiPattern(General): self.undefmask = udfm self.width = w - def __str__(self): - r = "{" - for p in self.pats: - r = r + ' ' + str(p) - return r + "}" - - def output_decl(self): - for p in self.pats: - p.output_decl() - def output_code(self, i, extracted, outerbits, outermask): global translate_prefix ind = str_indent(i) -- 2.20.1 ^ permalink raw reply related [flat|nested] 22+ messages in thread
* Re: [PATCH 4/8] decodetree: Split out MultiPattern from IncMultiPattern 2020-05-18 16:40 ` [PATCH 4/8] decodetree: Split out MultiPattern from IncMultiPattern Richard Henderson @ 2020-05-18 16:47 ` Philippe Mathieu-Daudé 0 siblings, 0 replies; 22+ messages in thread From: Philippe Mathieu-Daudé @ 2020-05-18 16:47 UTC (permalink / raw) To: Richard Henderson, qemu-devel; +Cc: peter.maydell On 5/18/20 6:40 PM, Richard Henderson wrote: > Signed-off-by: Richard Henderson <richard.henderson@linaro.org> > --- > scripts/decodetree.py | 37 ++++++++++++++++++++++++++----------- > 1 file changed, 26 insertions(+), 11 deletions(-) > > diff --git a/scripts/decodetree.py b/scripts/decodetree.py > index 7af6b3056d..ea313bcdea 100755 > --- a/scripts/decodetree.py > +++ b/scripts/decodetree.py > @@ -371,7 +371,32 @@ class Pattern(General): > # end Pattern > > > -class IncMultiPattern(General): > +class MultiPattern(General): > + """Class representing a set of instruction patterns""" > + > + def __init__(self, lineno, pats): > + self.file = input_file > + self.lineno = lineno > + self.pats = pats > + self.base = None > + self.fixedbits = 0 > + self.fixedmask = 0 > + self.undefmask = 0 > + self.width = None > + > + def __str__(self): > + r = 'group' > + if self.fixedbits is not None: > + r += ' ' + str_match_bits(self.fixedbits, self.fixedmask) > + return r > + > + def output_decl(self): > + for p in self.pats: > + p.output_decl() > +# end MultiPattern > + > + > +class IncMultiPattern(MultiPattern): > """Class representing an overlapping set of instruction patterns""" > > def __init__(self, lineno, pats, fixb, fixm, udfm, w): > @@ -384,16 +409,6 @@ class IncMultiPattern(General): > self.undefmask = udfm > self.width = w > > - def __str__(self): > - r = "{" > - for p in self.pats: > - r = r + ' ' + str(p) > - return r + "}" > - > - def output_decl(self): > - for p in self.pats: > - p.output_decl() > - > def output_code(self, i, extracted, outerbits, outermask): > global translate_prefix > ind = str_indent(i) > Reviewed-by: Philippe Mathieu-Daudé <philmd@redhat.com> ^ permalink raw reply [flat|nested] 22+ messages in thread
* [PATCH 5/8] decodetree: Allow group covering the entire insn space 2020-05-18 16:40 [PATCH 0/8] decodetree: Add non-overlapping groups Richard Henderson ` (3 preceding siblings ...) 2020-05-18 16:40 ` [PATCH 4/8] decodetree: Split out MultiPattern from IncMultiPattern Richard Henderson @ 2020-05-18 16:40 ` Richard Henderson 2020-06-02 14:35 ` Peter Maydell 2020-06-02 19:11 ` Peter Maydell 2020-05-18 16:40 ` [PATCH 6/8] decodetree: Move semantic propagation into classes Richard Henderson ` (2 subsequent siblings) 7 siblings, 2 replies; 22+ messages in thread From: Richard Henderson @ 2020-05-18 16:40 UTC (permalink / raw) To: qemu-devel; +Cc: peter.maydell This is an edge case for sure, but the logic that disallowed this case was faulty. Further, a few fixes scattered about can allow this to work. Signed-off-by: Richard Henderson <richard.henderson@linaro.org> --- ...est1.decode => succ_pattern_group_nest2.decode} | 2 +- scripts/decodetree.py | 14 +++++++++++--- 2 files changed, 12 insertions(+), 4 deletions(-) rename tests/decode/{err_pattern_group_nest1.decode => succ_pattern_group_nest2.decode} (85%) diff --git a/tests/decode/err_pattern_group_nest1.decode b/tests/decode/succ_pattern_group_nest2.decode similarity index 85% rename from tests/decode/err_pattern_group_nest1.decode rename to tests/decode/succ_pattern_group_nest2.decode index 92e971c3c5..8d5ab4b2d3 100644 --- a/tests/decode/err_pattern_group_nest1.decode +++ b/tests/decode/succ_pattern_group_nest2.decode @@ -6,7 +6,7 @@ %sub3 16:8 %sub4 24:8 -# Groups with no overlap are supposed to fail +# Group with complete overlap of the two patterns { top 00000000 00000000 00000000 00000000 sub4 ........ ........ ........ ........ %sub1 %sub2 %sub3 %sub4 diff --git a/scripts/decodetree.py b/scripts/decodetree.py index ea313bcdea..3307c74c30 100755 --- a/scripts/decodetree.py +++ b/scripts/decodetree.py @@ -124,6 +124,7 @@ def is_pow2(x): def ctz(x): """Return the number of times 2 factors into X.""" + assert x != 0 r = 0 while ((x >> r) & 1) == 0: r += 1 @@ -131,6 +132,8 @@ def ctz(x): def is_contiguous(bits): + if bits == 0: + return -1 shift = ctz(bits) if is_pow2((bits >> shift) + 1): return shift @@ -793,9 +796,8 @@ def build_incmulti_pattern(lineno, pats): error(lineno, 'width mismatch in patterns within braces') repeat = True - while repeat: - if fixedmask == 0: - error(lineno, 'no overlap in patterns within braces') + fixedbits = 0 + while repeat and fixedmask != 0: fixedbits = None for p in pats: thisbits = p.fixedbits & fixedmask @@ -978,6 +980,12 @@ def build_tree(pats, outerbits, outermask): innermask &= i.fixedmask if innermask == 0: + # Edge condition: One pattern covers the entire insnmask + if len(pats) == 1: + t = Tree(outermask, innermask) + t.subs.append((0, pats[0])) + return t + text = 'overlapping patterns:' for p in pats: text += '\n' + p.file + ':' + str(p.lineno) + ': ' + str(p) -- 2.20.1 ^ permalink raw reply related [flat|nested] 22+ messages in thread
* Re: [PATCH 5/8] decodetree: Allow group covering the entire insn space 2020-05-18 16:40 ` [PATCH 5/8] decodetree: Allow group covering the entire insn space Richard Henderson @ 2020-06-02 14:35 ` Peter Maydell 2020-06-02 15:15 ` Richard Henderson 2020-06-02 19:11 ` Peter Maydell 1 sibling, 1 reply; 22+ messages in thread From: Peter Maydell @ 2020-06-02 14:35 UTC (permalink / raw) To: Richard Henderson; +Cc: QEMU Developers On Mon, 18 May 2020 at 17:41, Richard Henderson <richard.henderson@linaro.org> wrote: > > This is an edge case for sure, but the logic that disallowed > this case was faulty. Further, a few fixes scattered about > can allow this to work. > > Signed-off-by: Richard Henderson <richard.henderson@linaro.org> > --- > ...est1.decode => succ_pattern_group_nest2.decode} | 2 +- > scripts/decodetree.py | 14 +++++++++++--- > 2 files changed, 12 insertions(+), 4 deletions(-) > rename tests/decode/{err_pattern_group_nest1.decode => succ_pattern_group_nest2.decode} (85%) > @@ -978,6 +980,12 @@ def build_tree(pats, outerbits, outermask): > innermask &= i.fixedmask > > if innermask == 0: > + # Edge condition: One pattern covers the entire insnmask > + if len(pats) == 1: > + t = Tree(outermask, innermask) > + t.subs.append((0, pats[0])) > + return t > + > text = 'overlapping patterns:' > for p in pats: > text += '\n' + p.file + ':' + str(p.lineno) + ': ' + str(p) I don't really understand this code, but does the similar looking build_size_tree() also need a change to handle a length-one pats ? thanks -- PMM ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: [PATCH 5/8] decodetree: Allow group covering the entire insn space 2020-06-02 14:35 ` Peter Maydell @ 2020-06-02 15:15 ` Richard Henderson 0 siblings, 0 replies; 22+ messages in thread From: Richard Henderson @ 2020-06-02 15:15 UTC (permalink / raw) To: Peter Maydell; +Cc: QEMU Developers On 6/2/20 7:35 AM, Peter Maydell wrote: > On Mon, 18 May 2020 at 17:41, Richard Henderson > <richard.henderson@linaro.org> wrote: >> >> This is an edge case for sure, but the logic that disallowed >> this case was faulty. Further, a few fixes scattered about >> can allow this to work. >> >> Signed-off-by: Richard Henderson <richard.henderson@linaro.org> >> --- >> ...est1.decode => succ_pattern_group_nest2.decode} | 2 +- >> scripts/decodetree.py | 14 +++++++++++--- >> 2 files changed, 12 insertions(+), 4 deletions(-) >> rename tests/decode/{err_pattern_group_nest1.decode => succ_pattern_group_nest2.decode} (85%) > >> @@ -978,6 +980,12 @@ def build_tree(pats, outerbits, outermask): >> innermask &= i.fixedmask >> >> if innermask == 0: >> + # Edge condition: One pattern covers the entire insnmask >> + if len(pats) == 1: >> + t = Tree(outermask, innermask) >> + t.subs.append((0, pats[0])) >> + return t >> + >> text = 'overlapping patterns:' >> for p in pats: >> text += '\n' + p.file + ':' + str(p.lineno) + ': ' + str(p) > > I don't really understand this code, but does the similar > looking build_size_tree() also need a change to handle a > length-one pats ? I don't think so, because in that case we'd exit earlier with if onewidth: return SizeLeaf(innermask, minwidth) r~ ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: [PATCH 5/8] decodetree: Allow group covering the entire insn space 2020-05-18 16:40 ` [PATCH 5/8] decodetree: Allow group covering the entire insn space Richard Henderson 2020-06-02 14:35 ` Peter Maydell @ 2020-06-02 19:11 ` Peter Maydell 1 sibling, 0 replies; 22+ messages in thread From: Peter Maydell @ 2020-06-02 19:11 UTC (permalink / raw) To: Richard Henderson; +Cc: QEMU Developers On Mon, 18 May 2020 at 17:41, Richard Henderson <richard.henderson@linaro.org> wrote: > > This is an edge case for sure, but the logic that disallowed > this case was faulty. Further, a few fixes scattered about > can allow this to work. > > Signed-off-by: Richard Henderson <richard.henderson@linaro.org> > -- Reviewed-by: Peter Maydell <peter.maydell@linaro.org> thanks -- PMM ^ permalink raw reply [flat|nested] 22+ messages in thread
* [PATCH 6/8] decodetree: Move semantic propagation into classes 2020-05-18 16:40 [PATCH 0/8] decodetree: Add non-overlapping groups Richard Henderson ` (4 preceding siblings ...) 2020-05-18 16:40 ` [PATCH 5/8] decodetree: Allow group covering the entire insn space Richard Henderson @ 2020-05-18 16:40 ` Richard Henderson 2020-06-02 19:12 ` Peter Maydell 2020-05-18 16:40 ` [PATCH 7/8] decodetree: Implement non-overlapping groups Richard Henderson 2020-05-18 16:40 ` [PATCH 8/8] target/arm: Use a non-overlapping group for misc control Richard Henderson 7 siblings, 1 reply; 22+ messages in thread From: Richard Henderson @ 2020-05-18 16:40 UTC (permalink / raw) To: qemu-devel; +Cc: peter.maydell Create ExcMultiPattern to hold an set of non-overlapping patterns. The body of build_tree, prop_format become member functions on this class. Add minimal member functions to Pattern and MultiPattern to allow recusion through the tree. Move the bulk of build_incmulti_pattern to prop_masks and prop_width in MultiPattern, since we will need this for both kinds of containers. Only perform prop_width for variablewidth. Remove global patterns variable, and pass down container object into parse_file from main. No functional change in all of this. Signed-off-by: Richard Henderson <richard.henderson@linaro.org> --- scripts/decodetree.py | 464 +++++++++++++++++++++++------------------- 1 file changed, 253 insertions(+), 211 deletions(-) diff --git a/scripts/decodetree.py b/scripts/decodetree.py index 3307c74c30..0ba01e049c 100755 --- a/scripts/decodetree.py +++ b/scripts/decodetree.py @@ -31,7 +31,6 @@ variablewidth = False fields = {} arguments = {} formats = {} -patterns = [] allpatterns = [] anyextern = False @@ -371,16 +370,27 @@ class Pattern(General): output(ind, 'u.f_', arg, '.', n, ' = ', f.str_extract(), ';\n') output(ind, 'if (', translate_prefix, '_', self.name, '(ctx, &u.f_', arg, ')) return true;\n') + + # Normal patterns do not have children. + def build_tree(self): + return + def prop_masks(self): + return + def prop_format(self): + return + def prop_width(self): + return + # end Pattern class MultiPattern(General): """Class representing a set of instruction patterns""" - def __init__(self, lineno, pats): + def __init__(self, lineno): self.file = input_file self.lineno = lineno - self.pats = pats + self.pats = [] self.base = None self.fixedbits = 0 self.fixedmask = 0 @@ -396,22 +406,63 @@ class MultiPattern(General): def output_decl(self): for p in self.pats: p.output_decl() + + def prop_masks(self): + global insnmask + + fixedmask = insnmask + undefmask = insnmask + + # Collect fixedmask/undefmask for all of the children. + for p in self.pats: + p.prop_masks() + fixedmask &= p.fixedmask + undefmask &= p.undefmask + + # Widen fixedmask until all fixedbits match + repeat = True + fixedbits = 0 + while repeat and fixedmask != 0: + fixedbits = None + for p in self.pats: + thisbits = p.fixedbits & fixedmask + if fixedbits is None: + fixedbits = thisbits + elif fixedbits != thisbits: + fixedmask &= ~(fixedbits ^ thisbits) + break + else: + repeat = False + + self.fixedbits = fixedbits + self.fixedmask = fixedmask + self.undefmask = undefmask + + def build_tree(self): + for p in self.pats: + p.build_tree() + + def prop_format(self): + for p in self.pats: + p.build_tree() + + def prop_width(self): + width = None + for p in self.pats: + p.prop_width() + if width is None: + width = p.width + elif width != p.width: + error_with_file(self.file, self.lineno, + 'width mismatch in patterns within braces') + self.width = width + # end MultiPattern class IncMultiPattern(MultiPattern): """Class representing an overlapping set of instruction patterns""" - def __init__(self, lineno, pats, fixb, fixm, udfm, w): - self.file = input_file - self.lineno = lineno - self.pats = pats - self.base = None - self.fixedbits = fixb - self.fixedmask = fixm - self.undefmask = udfm - self.width = w - def output_code(self, i, extracted, outerbits, outermask): global translate_prefix ind = str_indent(i) @@ -431,6 +482,153 @@ class IncMultiPattern(MultiPattern): #end IncMultiPattern +class Tree: + """Class representing a node in a decode tree""" + + def __init__(self, fm, tm): + self.fixedmask = fm + self.thismask = tm + self.subs = [] + self.base = None + + def str1(self, i): + ind = str_indent(i) + r = '{0}{1:08x}'.format(ind, self.fixedmask) + if self.format: + r += ' ' + self.format.name + r += ' [\n' + for (b, s) in self.subs: + r += '{0} {1:08x}:\n'.format(ind, b) + r += s.str1(i + 4) + '\n' + r += ind + ']' + return r + + def __str__(self): + return self.str1(0) + + def output_code(self, i, extracted, outerbits, outermask): + ind = str_indent(i) + + # If we identified all nodes below have the same format, + # extract the fields now. + if not extracted and self.base: + output(ind, self.base.extract_name(), + '(ctx, &u.f_', self.base.base.name, ', insn);\n') + extracted = True + + # Attempt to aid the compiler in producing compact switch statements. + # If the bits in the mask are contiguous, extract them. + sh = is_contiguous(self.thismask) + if sh > 0: + # Propagate SH down into the local functions. + def str_switch(b, sh=sh): + return '(insn >> {0}) & 0x{1:x}'.format(sh, b >> sh) + + def str_case(b, sh=sh): + return '0x{0:x}'.format(b >> sh) + else: + def str_switch(b): + return 'insn & 0x{0:08x}'.format(b) + + def str_case(b): + return '0x{0:08x}'.format(b) + + output(ind, 'switch (', str_switch(self.thismask), ') {\n') + for b, s in sorted(self.subs): + assert (self.thismask & ~s.fixedmask) == 0 + innermask = outermask | self.thismask + innerbits = outerbits | b + output(ind, 'case ', str_case(b), ':\n') + output(ind, ' /* ', + str_match_bits(innerbits, innermask), ' */\n') + s.output_code(i + 4, extracted, innerbits, innermask) + output(ind, ' return false;\n') + output(ind, '}\n') +# end Tree + + +class ExcMultiPattern(MultiPattern): + """Class representing a non-overlapping set of instruction patterns""" + + def output_code(self, i, extracted, outerbits, outermask): + # Defer everything to our decomposed Tree node + self.tree.output_code(i, extracted, outerbits, outermask) + + @staticmethod + def __build_tree(pats, outerbits, outermask): + # Find the intersection of all remaining fixedmask. + innermask = ~outermask & insnmask + for i in pats: + innermask &= i.fixedmask + + if innermask == 0: + # Edge condition: One pattern covers the entire insnmask + if len(pats) == 1: + t = Tree(outermask, innermask) + t.subs.append((0, pats[0])) + return t + + text = 'overlapping patterns:' + for p in pats: + text += '\n' + p.file + ':' + str(p.lineno) + ': ' + str(p) + error_with_file(pats[0].file, pats[0].lineno, text) + + fullmask = outermask | innermask + + # Sort each element of pats into the bin selected by the mask. + bins = {} + for i in pats: + fb = i.fixedbits & innermask + if fb in bins: + bins[fb].append(i) + else: + bins[fb] = [i] + + # We must recurse if any bin has more than one element or if + # the single element in the bin has not been fully matched. + t = Tree(fullmask, innermask) + + for b, l in bins.items(): + s = l[0] + if len(l) > 1 or s.fixedmask & ~fullmask != 0: + s = ExcMultiPattern.__build_tree(l, b | outerbits, fullmask) + t.subs.append((b, s)) + + return t + + def build_tree(self): + super().prop_format() + self.tree = self.__build_tree(self.pats, self.fixedbits, + self.fixedmask) + + @staticmethod + def __prop_format(tree): + """Propagate Format objects into the decode tree""" + + # Depth first search. + for (b, s) in tree.subs: + if isinstance(s, Tree): + ExcMultiPattern.__prop_format(s) + + # If all entries in SUBS have the same format, then + # propagate that into the tree. + f = None + for (b, s) in tree.subs: + if f is None: + f = s.base + if f is None: + return + if f is not s.base: + return + tree.base = f + + def prop_format(self): + super().prop_format() + self.__prop_format(self.tree) + +# end ExcMultiPattern + + def parse_field(lineno, name, toks): """Parse one instruction field from TOKS at LINENO""" global fields @@ -587,18 +785,19 @@ def infer_format(arg, fieldmask, flds, width): # end infer_format -def parse_generic(lineno, is_format, name, toks): +def parse_generic(lineno, parent_pat, name, toks): """Parse one instruction format from TOKS at LINENO""" global fields global arguments global formats - global patterns global allpatterns global re_ident global insnwidth global insnmask global variablewidth + is_format = parent_pat is None + fixedmask = 0 fixedbits = 0 undefmask = 0 @@ -749,7 +948,7 @@ def parse_generic(lineno, is_format, name, toks): error(lineno, 'field {0} not initialized'.format(f)) pat = Pattern(name, lineno, fmt, fixedbits, fixedmask, undefmask, fieldmask, flds, width) - patterns.append(pat) + parent_pat.pats.append(pat) allpatterns.append(pat) # Validate the masks that we have assembled. @@ -769,61 +968,16 @@ def parse_generic(lineno, is_format, name, toks): .format(allbits ^ insnmask)) # end parse_general -def build_incmulti_pattern(lineno, pats): - """Validate the Patterns going into a IncMultiPattern.""" - global patterns - global insnmask - if len(pats) < 2: - error(lineno, 'less than two patterns within braces') - - fixedmask = insnmask - undefmask = insnmask - - # Collect fixed/undefmask for all of the children. - # Move the defining lineno back to that of the first child. - for p in pats: - fixedmask &= p.fixedmask - undefmask &= p.undefmask - if p.lineno < lineno: - lineno = p.lineno - - width = None - for p in pats: - if width is None: - width = p.width - elif width != p.width: - error(lineno, 'width mismatch in patterns within braces') - - repeat = True - fixedbits = 0 - while repeat and fixedmask != 0: - fixedbits = None - for p in pats: - thisbits = p.fixedbits & fixedmask - if fixedbits is None: - fixedbits = thisbits - elif fixedbits != thisbits: - fixedmask &= ~(fixedbits ^ thisbits) - break - else: - repeat = False - - mp = IncMultiPattern(lineno, pats, fixedbits, fixedmask, undefmask, width) - patterns.append(mp) -# end build_incmulti_pattern - -def parse_file(f): +def parse_file(f, parent_pat): """Parse all of the patterns within a file""" - global patterns - # Read all of the lines of the file. Concatenate lines # ending in backslash; discard empty lines and comments. toks = [] lineno = 0 nesting = 0 - saved_pats = [] + nesting_pats = [] for line in f: lineno += 1 @@ -868,16 +1022,20 @@ def parse_file(f): # End nesting? if name == '}': - if nesting == 0: - error(start_lineno, 'mismatched close brace') if len(toks) != 0: error(start_lineno, 'extra tokens after close brace') + if len(parent_pat.pats) < 2: + error(lineno, 'less than two patterns within braces') + + try: + parent_pat = nesting_pats.pop() + except: + error(lineno, 'mismatched close brace') + nesting -= 2 if indent != nesting: - error(start_lineno, 'indentation ', indent, ' != ', nesting) - pats = patterns - patterns = saved_pats.pop() - build_incmulti_pattern(lineno, pats) + error(lineno, 'indentation ', indent, ' != ', nesting) + toks = [] continue @@ -889,8 +1047,12 @@ def parse_file(f): if name == '{': if len(toks) != 0: error(start_lineno, 'extra tokens after open brace') - saved_pats.append(patterns) - patterns = [] + + nested_pat = IncMultiPattern(start_lineno) + parent_pat.pats.append(nested_pat) + nesting_pats.append(parent_pat) + parent_pat = nested_pat + nesting += 2 toks = [] continue @@ -901,121 +1063,13 @@ def parse_file(f): elif name[0] == '&': parse_arguments(start_lineno, name[1:], toks) elif name[0] == '@': - parse_generic(start_lineno, True, name[1:], toks) + parse_generic(start_lineno, None, name[1:], toks) else: - parse_generic(start_lineno, False, name, toks) + parse_generic(start_lineno, parent_pat, name, toks) toks = [] # end parse_file -class Tree: - """Class representing a node in a decode tree""" - - def __init__(self, fm, tm): - self.fixedmask = fm - self.thismask = tm - self.subs = [] - self.base = None - - def str1(self, i): - ind = str_indent(i) - r = '{0}{1:08x}'.format(ind, self.fixedmask) - if self.format: - r += ' ' + self.format.name - r += ' [\n' - for (b, s) in self.subs: - r += '{0} {1:08x}:\n'.format(ind, b) - r += s.str1(i + 4) + '\n' - r += ind + ']' - return r - - def __str__(self): - return self.str1(0) - - def output_code(self, i, extracted, outerbits, outermask): - ind = str_indent(i) - - # If we identified all nodes below have the same format, - # extract the fields now. - if not extracted and self.base: - output(ind, self.base.extract_name(), - '(ctx, &u.f_', self.base.base.name, ', insn);\n') - extracted = True - - # Attempt to aid the compiler in producing compact switch statements. - # If the bits in the mask are contiguous, extract them. - sh = is_contiguous(self.thismask) - if sh > 0: - # Propagate SH down into the local functions. - def str_switch(b, sh=sh): - return '(insn >> {0}) & 0x{1:x}'.format(sh, b >> sh) - - def str_case(b, sh=sh): - return '0x{0:x}'.format(b >> sh) - else: - def str_switch(b): - return 'insn & 0x{0:08x}'.format(b) - - def str_case(b): - return '0x{0:08x}'.format(b) - - output(ind, 'switch (', str_switch(self.thismask), ') {\n') - for b, s in sorted(self.subs): - assert (self.thismask & ~s.fixedmask) == 0 - innermask = outermask | self.thismask - innerbits = outerbits | b - output(ind, 'case ', str_case(b), ':\n') - output(ind, ' /* ', - str_match_bits(innerbits, innermask), ' */\n') - s.output_code(i + 4, extracted, innerbits, innermask) - output(ind, ' return false;\n') - output(ind, '}\n') -# end Tree - - -def build_tree(pats, outerbits, outermask): - # Find the intersection of all remaining fixedmask. - innermask = ~outermask & insnmask - for i in pats: - innermask &= i.fixedmask - - if innermask == 0: - # Edge condition: One pattern covers the entire insnmask - if len(pats) == 1: - t = Tree(outermask, innermask) - t.subs.append((0, pats[0])) - return t - - text = 'overlapping patterns:' - for p in pats: - text += '\n' + p.file + ':' + str(p.lineno) + ': ' + str(p) - error_with_file(pats[0].file, pats[0].lineno, text) - - fullmask = outermask | innermask - - # Sort each element of pats into the bin selected by the mask. - bins = {} - for i in pats: - fb = i.fixedbits & innermask - if fb in bins: - bins[fb].append(i) - else: - bins[fb] = [i] - - # We must recurse if any bin has more than one element or if - # the single element in the bin has not been fully matched. - t = Tree(fullmask, innermask) - - for b, l in bins.items(): - s = l[0] - if len(l) > 1 or s.fixedmask & ~fullmask != 0: - s = build_tree(l, b | outerbits, fullmask) - t.subs.append((b, s)) - - return t -# end build_tree - - class SizeTree: """Class representing a node in a size decode tree""" @@ -1157,28 +1211,6 @@ def build_size_tree(pats, width, outerbits, outermask): # end build_size_tree -def prop_format(tree): - """Propagate Format objects into the decode tree""" - - # Depth first search. - for (b, s) in tree.subs: - if isinstance(s, Tree): - prop_format(s) - - # If all entries in SUBS have the same format, then - # propagate that into the tree. - f = None - for (b, s) in tree.subs: - if f is None: - f = s.base - if f is None: - return - if f is not s.base: - return - tree.base = f -# end prop_format - - def prop_size(tree): """Propagate minimum widths up the decode size tree""" @@ -1199,7 +1231,6 @@ def prop_size(tree): def main(): global arguments global formats - global patterns global allpatterns global translate_scope global translate_prefix @@ -1246,18 +1277,29 @@ def main(): if len(args) < 1: error(0, 'missing input file') + + toppat = ExcMultiPattern(0) + for filename in args: input_file = filename f = open(filename, 'r') - parse_file(f) + parse_file(f, toppat) f.close() - if variablewidth: - stree = build_size_tree(patterns, 8, 0, 0) - prop_size(stree) + # We do not want to compute masks for toppat, because those masks + # are used as a starting point for build_tree. For toppat, we must + # insist that decode begins from naught. + for i in toppat.pats: + i.prop_masks() - dtree = build_tree(patterns, 0, 0) - prop_format(dtree) + toppat.build_tree() + toppat.prop_format() + + if variablewidth: + for i in toppat.pats: + i.prop_width() + stree = build_size_tree(toppat.pats, 8, 0, 0) + prop_size(stree) if output_file: output_fd = open(output_file, 'w') @@ -1316,7 +1358,7 @@ def main(): f = arguments[n] output(i4, i4, f.struct_name(), ' f_', f.name, ';\n') output(i4, '} u;\n\n') - dtree.output_code(4, False, 0, 0) + toppat.output_code(4, False, 0, 0) output(i4, 'return false;\n') output('}\n') -- 2.20.1 ^ permalink raw reply related [flat|nested] 22+ messages in thread
* Re: [PATCH 6/8] decodetree: Move semantic propagation into classes 2020-05-18 16:40 ` [PATCH 6/8] decodetree: Move semantic propagation into classes Richard Henderson @ 2020-06-02 19:12 ` Peter Maydell 0 siblings, 0 replies; 22+ messages in thread From: Peter Maydell @ 2020-06-02 19:12 UTC (permalink / raw) To: Richard Henderson; +Cc: QEMU Developers On Mon, 18 May 2020 at 17:41, Richard Henderson <richard.henderson@linaro.org> wrote: > > Create ExcMultiPattern to hold an set of non-overlapping patterns. > The body of build_tree, prop_format become member functions on this > class. Add minimal member functions to Pattern and MultiPattern > to allow recusion through the tree. > > Move the bulk of build_incmulti_pattern to prop_masks and prop_width > in MultiPattern, since we will need this for both kinds of containers. > Only perform prop_width for variablewidth. > > Remove global patterns variable, and pass down container object into > parse_file from main. > > No functional change in all of this. > > Signed-off-by: Richard Henderson <richard.henderson@linaro.org> > --- > scripts/decodetree.py | 464 +++++++++++++++++++++++------------------- > 1 file changed, 253 insertions(+), 211 deletions(-) > I feel like this would have been easier to review if it had been multiple patches (there's a lot of stuff that's just code-motion in here together with actual changes) but I've waded through it now, so Reviewed-by: Peter Maydell <peter.maydell@linaro.org> thanks -- PMM ^ permalink raw reply [flat|nested] 22+ messages in thread
* [PATCH 7/8] decodetree: Implement non-overlapping groups 2020-05-18 16:40 [PATCH 0/8] decodetree: Add non-overlapping groups Richard Henderson ` (5 preceding siblings ...) 2020-05-18 16:40 ` [PATCH 6/8] decodetree: Move semantic propagation into classes Richard Henderson @ 2020-05-18 16:40 ` Richard Henderson 2020-05-18 16:53 ` Philippe Mathieu-Daudé 2020-06-02 19:13 ` Peter Maydell 2020-05-18 16:40 ` [PATCH 8/8] target/arm: Use a non-overlapping group for misc control Richard Henderson 7 siblings, 2 replies; 22+ messages in thread From: Richard Henderson @ 2020-05-18 16:40 UTC (permalink / raw) To: qemu-devel; +Cc: peter.maydell Intended to be nested within overlapping groups. Suggested-by: Peter Maydell <peter.maydell@linaro.org> Signed-off-by: Richard Henderson <richard.henderson@linaro.org> --- scripts/decodetree.py | 21 ++++++++++++++------- 1 file changed, 14 insertions(+), 7 deletions(-) diff --git a/scripts/decodetree.py b/scripts/decodetree.py index 0ba01e049c..a9739f671d 100755 --- a/scripts/decodetree.py +++ b/scripts/decodetree.py @@ -1021,21 +1021,22 @@ def parse_file(f, parent_pat): del toks[0] # End nesting? - if name == '}': + if name == '}' or name == ']': if len(toks) != 0: error(start_lineno, 'extra tokens after close brace') if len(parent_pat.pats) < 2: error(lineno, 'less than two patterns within braces') + # Make sure { } and [ ] nest properly. + if (name == '}') != isinstance(parent_pat, IncMultiPattern): + error(lineno, 'mismatched close brace') + try: parent_pat = nesting_pats.pop() except: - error(lineno, 'mismatched close brace') + error(lineno, 'extra close brace') nesting -= 2 - if indent != nesting: - error(lineno, 'indentation ', indent, ' != ', nesting) - toks = [] continue @@ -1044,11 +1045,14 @@ def parse_file(f, parent_pat): error(start_lineno, 'indentation ', indent, ' != ', nesting) # Start nesting? - if name == '{': + if name == '{' or name == '[': if len(toks) != 0: error(start_lineno, 'extra tokens after open brace') - nested_pat = IncMultiPattern(start_lineno) + if name == '{': + nested_pat = IncMultiPattern(start_lineno) + else: + nested_pat = ExcMultiPattern(start_lineno) parent_pat.pats.append(nested_pat) nesting_pats.append(parent_pat) parent_pat = nested_pat @@ -1067,6 +1071,9 @@ def parse_file(f, parent_pat): else: parse_generic(start_lineno, parent_pat, name, toks) toks = [] + + if nesting != 0: + error(lineno, 'missing close brace') # end parse_file -- 2.20.1 ^ permalink raw reply related [flat|nested] 22+ messages in thread
* Re: [PATCH 7/8] decodetree: Implement non-overlapping groups 2020-05-18 16:40 ` [PATCH 7/8] decodetree: Implement non-overlapping groups Richard Henderson @ 2020-05-18 16:53 ` Philippe Mathieu-Daudé 2020-06-02 19:13 ` Peter Maydell 1 sibling, 0 replies; 22+ messages in thread From: Philippe Mathieu-Daudé @ 2020-05-18 16:53 UTC (permalink / raw) To: Richard Henderson, qemu-devel; +Cc: peter.maydell On 5/18/20 6:40 PM, Richard Henderson wrote: > Intended to be nested within overlapping groups. > > Suggested-by: Peter Maydell <peter.maydell@linaro.org> > Signed-off-by: Richard Henderson <richard.henderson@linaro.org> > --- > scripts/decodetree.py | 21 ++++++++++++++------- > 1 file changed, 14 insertions(+), 7 deletions(-) > > diff --git a/scripts/decodetree.py b/scripts/decodetree.py > index 0ba01e049c..a9739f671d 100755 > --- a/scripts/decodetree.py > +++ b/scripts/decodetree.py > @@ -1021,21 +1021,22 @@ def parse_file(f, parent_pat): > del toks[0] > > # End nesting? > - if name == '}': > + if name == '}' or name == ']': > if len(toks) != 0: > error(start_lineno, 'extra tokens after close brace') > if len(parent_pat.pats) < 2: > error(lineno, 'less than two patterns within braces') > > + # Make sure { } and [ ] nest properly. > + if (name == '}') != isinstance(parent_pat, IncMultiPattern): > + error(lineno, 'mismatched close brace') > + > try: > parent_pat = nesting_pats.pop() > except: > - error(lineno, 'mismatched close brace') > + error(lineno, 'extra close brace') > > nesting -= 2 > - if indent != nesting: > - error(lineno, 'indentation ', indent, ' != ', nesting) > - > toks = [] > continue > > @@ -1044,11 +1045,14 @@ def parse_file(f, parent_pat): > error(start_lineno, 'indentation ', indent, ' != ', nesting) > > # Start nesting? > - if name == '{': > + if name == '{' or name == '[': > if len(toks) != 0: > error(start_lineno, 'extra tokens after open brace') > > - nested_pat = IncMultiPattern(start_lineno) > + if name == '{': > + nested_pat = IncMultiPattern(start_lineno) > + else: > + nested_pat = ExcMultiPattern(start_lineno) > parent_pat.pats.append(nested_pat) > nesting_pats.append(parent_pat) > parent_pat = nested_pat > @@ -1067,6 +1071,9 @@ def parse_file(f, parent_pat): > else: > parse_generic(start_lineno, parent_pat, name, toks) > toks = [] > + > + if nesting != 0: > + error(lineno, 'missing close brace') > # end parse_file > > > Reviewed-by: Philippe Mathieu-Daudé <f4bug@amsat.org> ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: [PATCH 7/8] decodetree: Implement non-overlapping groups 2020-05-18 16:40 ` [PATCH 7/8] decodetree: Implement non-overlapping groups Richard Henderson 2020-05-18 16:53 ` Philippe Mathieu-Daudé @ 2020-06-02 19:13 ` Peter Maydell 2020-06-02 19:19 ` Richard Henderson 1 sibling, 1 reply; 22+ messages in thread From: Peter Maydell @ 2020-06-02 19:13 UTC (permalink / raw) To: Richard Henderson; +Cc: QEMU Developers On Mon, 18 May 2020 at 17:41, Richard Henderson <richard.henderson@linaro.org> wrote: > > Intended to be nested within overlapping groups. > > Suggested-by: Peter Maydell <peter.maydell@linaro.org> > Signed-off-by: Richard Henderson <richard.henderson@linaro.org> > --- > scripts/decodetree.py | 21 ++++++++++++++------- > 1 file changed, 14 insertions(+), 7 deletions(-) > > diff --git a/scripts/decodetree.py b/scripts/decodetree.py > index 0ba01e049c..a9739f671d 100755 > --- a/scripts/decodetree.py > +++ b/scripts/decodetree.py > @@ -1021,21 +1021,22 @@ def parse_file(f, parent_pat): > del toks[0] > > # End nesting? > - if name == '}': > + if name == '}' or name == ']': > if len(toks) != 0: > error(start_lineno, 'extra tokens after close brace') > if len(parent_pat.pats) < 2: > error(lineno, 'less than two patterns within braces') > > + # Make sure { } and [ ] nest properly. > + if (name == '}') != isinstance(parent_pat, IncMultiPattern): > + error(lineno, 'mismatched close brace') > + > try: > parent_pat = nesting_pats.pop() > except: > - error(lineno, 'mismatched close brace') > + error(lineno, 'extra close brace') > > nesting -= 2 > - if indent != nesting: > - error(lineno, 'indentation ', indent, ' != ', nesting) > - Why do we lose this error check ? > toks = [] > continue thanks -- PMM ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: [PATCH 7/8] decodetree: Implement non-overlapping groups 2020-06-02 19:13 ` Peter Maydell @ 2020-06-02 19:19 ` Richard Henderson 0 siblings, 0 replies; 22+ messages in thread From: Richard Henderson @ 2020-06-02 19:19 UTC (permalink / raw) To: Peter Maydell; +Cc: QEMU Developers On 6/2/20 12:13 PM, Peter Maydell wrote: > On Mon, 18 May 2020 at 17:41, Richard Henderson > <richard.henderson@linaro.org> wrote: >> >> Intended to be nested within overlapping groups. >> >> Suggested-by: Peter Maydell <peter.maydell@linaro.org> >> Signed-off-by: Richard Henderson <richard.henderson@linaro.org> >> --- >> scripts/decodetree.py | 21 ++++++++++++++------- >> 1 file changed, 14 insertions(+), 7 deletions(-) >> >> diff --git a/scripts/decodetree.py b/scripts/decodetree.py >> index 0ba01e049c..a9739f671d 100755 >> --- a/scripts/decodetree.py >> +++ b/scripts/decodetree.py >> @@ -1021,21 +1021,22 @@ def parse_file(f, parent_pat): >> del toks[0] >> >> # End nesting? >> - if name == '}': >> + if name == '}' or name == ']': >> if len(toks) != 0: >> error(start_lineno, 'extra tokens after close brace') >> if len(parent_pat.pats) < 2: >> error(lineno, 'less than two patterns within braces') >> >> + # Make sure { } and [ ] nest properly. >> + if (name == '}') != isinstance(parent_pat, IncMultiPattern): >> + error(lineno, 'mismatched close brace') >> + >> try: >> parent_pat = nesting_pats.pop() >> except: >> - error(lineno, 'mismatched close brace') >> + error(lineno, 'extra close brace') >> >> nesting -= 2 >> - if indent != nesting: >> - error(lineno, 'indentation ', indent, ' != ', nesting) >> - > > Why do we lose this error check ? Hmm, wasn't supposed to. Will fix. r~ ^ permalink raw reply [flat|nested] 22+ messages in thread
* [PATCH 8/8] target/arm: Use a non-overlapping group for misc control 2020-05-18 16:40 [PATCH 0/8] decodetree: Add non-overlapping groups Richard Henderson ` (6 preceding siblings ...) 2020-05-18 16:40 ` [PATCH 7/8] decodetree: Implement non-overlapping groups Richard Henderson @ 2020-05-18 16:40 ` Richard Henderson 2020-05-18 16:56 ` Philippe Mathieu-Daudé 7 siblings, 1 reply; 22+ messages in thread From: Richard Henderson @ 2020-05-18 16:40 UTC (permalink / raw) To: qemu-devel; +Cc: peter.maydell This sub-group in the t32 deocode are mutually exclusive. Signed-off-by: Richard Henderson <richard.henderson@linaro.org> --- target/arm/t32.decode | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) diff --git a/target/arm/t32.decode b/target/arm/t32.decode index c63082fc9c..c21a988f97 100644 --- a/target/arm/t32.decode +++ b/target/arm/t32.decode @@ -312,13 +312,13 @@ CLZ 1111 1010 1011 ---- 1111 .... 1000 .... @rdm &cps # Miscellaneous control - { + [ CLREX 1111 0011 1011 1111 1000 1111 0010 1111 DSB 1111 0011 1011 1111 1000 1111 0100 ---- DMB 1111 0011 1011 1111 1000 1111 0101 ---- ISB 1111 0011 1011 1111 1000 1111 0110 ---- SB 1111 0011 1011 1111 1000 1111 0111 0000 - } + ] # Note that the v7m insn overlaps both the normal and banked insn. { -- 2.20.1 ^ permalink raw reply related [flat|nested] 22+ messages in thread
* Re: [PATCH 8/8] target/arm: Use a non-overlapping group for misc control 2020-05-18 16:40 ` [PATCH 8/8] target/arm: Use a non-overlapping group for misc control Richard Henderson @ 2020-05-18 16:56 ` Philippe Mathieu-Daudé 0 siblings, 0 replies; 22+ messages in thread From: Philippe Mathieu-Daudé @ 2020-05-18 16:56 UTC (permalink / raw) To: Richard Henderson, qemu-devel; +Cc: peter.maydell On 5/18/20 6:40 PM, Richard Henderson wrote: > This sub-group in the t32 deocode are mutually exclusive. "The miscellaneous control instructions are mutually exclusive within the t32 decode sub-group."? Reviewed-by: Philippe Mathieu-Daudé <f4bug@amsat.org> > > Signed-off-by: Richard Henderson <richard.henderson@linaro.org> > --- > target/arm/t32.decode | 4 ++-- > 1 file changed, 2 insertions(+), 2 deletions(-) > > diff --git a/target/arm/t32.decode b/target/arm/t32.decode > index c63082fc9c..c21a988f97 100644 > --- a/target/arm/t32.decode > +++ b/target/arm/t32.decode > @@ -312,13 +312,13 @@ CLZ 1111 1010 1011 ---- 1111 .... 1000 .... @rdm > &cps > > # Miscellaneous control > - { > + [ > CLREX 1111 0011 1011 1111 1000 1111 0010 1111 > DSB 1111 0011 1011 1111 1000 1111 0100 ---- > DMB 1111 0011 1011 1111 1000 1111 0101 ---- > ISB 1111 0011 1011 1111 1000 1111 0110 ---- > SB 1111 0011 1011 1111 1000 1111 0111 0000 > - } > + ] > > # Note that the v7m insn overlaps both the normal and banked insn. > { > ^ permalink raw reply [flat|nested] 22+ messages in thread
end of thread, other threads:[~2020-06-02 19:20 UTC | newest] Thread overview: 22+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2020-05-18 16:40 [PATCH 0/8] decodetree: Add non-overlapping groups Richard Henderson 2020-05-18 16:40 ` [PATCH 1/8] decodetree: Remove python 3.4 check Richard Henderson 2020-05-18 16:46 ` Philippe Mathieu-Daudé 2020-05-29 9:35 ` Philippe Mathieu-Daudé 2020-05-18 16:40 ` [PATCH 2/8] decodetree: Tidy error_with_file Richard Henderson 2020-06-02 14:24 ` Peter Maydell 2020-05-18 16:40 ` [PATCH 3/8] decodetree: Rename MultiPattern to IncMultiPattern Richard Henderson 2020-05-18 16:47 ` Philippe Mathieu-Daudé 2020-05-18 16:40 ` [PATCH 4/8] decodetree: Split out MultiPattern from IncMultiPattern Richard Henderson 2020-05-18 16:47 ` Philippe Mathieu-Daudé 2020-05-18 16:40 ` [PATCH 5/8] decodetree: Allow group covering the entire insn space Richard Henderson 2020-06-02 14:35 ` Peter Maydell 2020-06-02 15:15 ` Richard Henderson 2020-06-02 19:11 ` Peter Maydell 2020-05-18 16:40 ` [PATCH 6/8] decodetree: Move semantic propagation into classes Richard Henderson 2020-06-02 19:12 ` Peter Maydell 2020-05-18 16:40 ` [PATCH 7/8] decodetree: Implement non-overlapping groups Richard Henderson 2020-05-18 16:53 ` Philippe Mathieu-Daudé 2020-06-02 19:13 ` Peter Maydell 2020-06-02 19:19 ` Richard Henderson 2020-05-18 16:40 ` [PATCH 8/8] target/arm: Use a non-overlapping group for misc control Richard Henderson 2020-05-18 16:56 ` Philippe Mathieu-Daudé
This is an external index of several public inboxes, see mirroring instructions on how to clone and mirror all data and code used by this external index.