[PATCH 0/8] decodetree: Add non-overlapping groups

[PATCH 0/8] decodetree: Add non-overlapping groups

[Richard Henderson]

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

[PATCH 1/8] decodetree: Remove python 3.4 check

[Richard Henderson]

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

[PATCH 2/8] decodetree: Tidy error_with_file

[Richard Henderson]

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

[PATCH 3/8] decodetree: Rename MultiPattern to IncMultiPattern

[Richard Henderson]

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

[PATCH 4/8] decodetree: Split out MultiPattern from IncMultiPattern

[Richard Henderson]

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

[PATCH 5/8] decodetree: Allow group covering the entire insn space

[Richard Henderson]

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

[PATCH 6/8] decodetree: Move semantic propagation into classes

[Richard Henderson]

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

[PATCH 7/8] decodetree: Implement non-overlapping groups

[Richard Henderson]

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

[PATCH 8/8] target/arm: Use a non-overlapping group for misc control

[Richard Henderson]

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

Re: [PATCH 1/8] decodetree: Remove python 3.4 check

[Philippe Mathieu-Daudé]

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>

Re: [PATCH 4/8] decodetree: Split out MultiPattern from IncMultiPattern

[Philippe Mathieu-Daudé]

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>

Re: [PATCH 3/8] decodetree: Rename MultiPattern to IncMultiPattern

[Philippe Mathieu-Daudé]

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>

Re: [PATCH 7/8] decodetree: Implement non-overlapping groups

[Philippe Mathieu-Daudé]

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>

Re: [PATCH 8/8] target/arm: Use a non-overlapping group for misc control

[Philippe Mathieu-Daudé]

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.
>       {
> 

Re: [PATCH 1/8] decodetree: Remove python 3.4 check

[Philippe Mathieu-Daudé]

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':
> 

Re: [PATCH 2/8] decodetree: Tidy error_with_file

[Peter Maydell]

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

Re: [PATCH 5/8] decodetree: Allow group covering the entire insn space

[Peter Maydell]

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

Re: [PATCH 5/8] decodetree: Allow group covering the entire insn space

[Richard Henderson]

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~

Re: [PATCH 5/8] decodetree: Allow group covering the entire insn space

[Peter Maydell]

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

Re: [PATCH 6/8] decodetree: Move semantic propagation into classes

[Peter Maydell]

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

Re: [PATCH 7/8] decodetree: Implement non-overlapping groups

[Peter Maydell]

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

Re: [PATCH 7/8] decodetree: Implement non-overlapping groups

[Richard Henderson]

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~