[PATCH 0/6] decodetree: support named fields

[PATCH 0/6] decodetree: support named fields

[Peter Maydell]

This patchset adds support to the decodetree generator
for "named fields", where one field can refer to some
other already extracted field, as well as to portions
of the instruction word. The specific case where I want
this is for some load/store insns in the A64 decoder:

# Load/store with an unsigned 12 bit immediate, which is scaled by the
# element size. The function gets the sz:imm and returns the scaled immediate.
# For vectors, opc bit 1 (insn bit 23) is effectively bit 2 of the size.
%uimm_scaled    10:12 sz:3 !function=uimm_scaled
@ldst_uimm      .. ... . .. .. ............ rn:5 rt:5 &ldst_imm unpriv=0 p=0 w=0 imm=%uimm_scaled
STR_i           sz:2 111 0 01 00 ............ ..... ..... @ldst_uimm sign=0 ext=0
LDR_i           00 111 0 01 01 ............ ..... ..... @ldst_uimm sign=0 ext=1 sz=0
LDR_i           01 111 0 01 01 ............ ..... ..... @ldst_uimm sign=0 ext=1 sz=1
LDR_i           10 111 0 01 01 ............ ..... ..... @ldst_uimm sign=0 ext=1 sz=2
LDR_i           11 111 0 01 01 ............ ..... ..... @ldst_uimm sign=0 ext=1 sz=3
LDR_i           00 111 0 01 10 ............ ..... ..... @ldst_uimm sign=1 ext=0 sz=0
LDR_i           01 111 0 01 10 ............ ..... ..... @ldst_uimm sign=1 ext=0 sz=1
LDR_i           10 111 0 01 10 ............ ..... ..... @ldst_uimm sign=1 ext=0 sz=2
LDR_i           00 111 0 01 11 ............ ..... ..... @ldst_uimm sign=1 ext=1 sz=0
LDR_i           01 111 0 01 11 ............ ..... ..... @ldst_uimm sign=1 ext=1 sz=1

Here we need to manually decode the sz field in bits 31:30 because
of the complexity of the sign/ext and the parts of the encode space
that are UNDEF (or are prefetch). And we want to use a !function
to do the "scale the immediate offset by the size of the datatype"
so we can use the same LDR_i and STR_i trans_ functions that we
already have for the unscaled-immediate loads and stores.

But at the moment you can't re-decode bits in a %field that are fixed
in the instruction pattern, and you can't refer to the
already-decoded sz value directly. This patchset implements the
syntax used above where the %field can refer to another field,
e.g. 'sz:2'.

Patch 1 fixes a trivial bug in the check.sh script that meant
that failures weren't reported up to meson.

thanks
-- PMM

Peter Maydell (6):
  tests/decodetree/check.sh: Exit failure for all failures
  docs: Document decodetree named field syntax
  scripts/decodetree: Pass lvalue-formatter function to str_extract()
  scripts/decodetree: Implement a topological sort
  scripts/decodetree: Implement named field support
  tests/decode: Add tests for various named-field cases

 docs/devel/decodetree.rst            |  33 +++-
 tests/decode/err_field1.decode       |   2 +-
 tests/decode/err_field10.decode      |   7 +
 tests/decode/err_field7.decode       |   7 +
 tests/decode/err_field8.decode       |   8 +
 tests/decode/err_field9.decode       |  14 ++
 tests/decode/succ_named_field.decode |  19 +++
 scripts/decodetree.py                | 239 +++++++++++++++++++++++++--
 tests/decode/check.sh                |   1 +
 9 files changed, 310 insertions(+), 20 deletions(-)
 create mode 100644 tests/decode/err_field10.decode
 create mode 100644 tests/decode/err_field7.decode
 create mode 100644 tests/decode/err_field8.decode
 create mode 100644 tests/decode/err_field9.decode
 create mode 100644 tests/decode/succ_named_field.decode

-- 
2.34.1

[PATCH 1/6] tests/decodetree/check.sh: Exit failure for all failures

[Peter Maydell]

The check.sh script doesn't set its exit status to 1 for failures in
the succ_* (should-pass) tests, only for the err_* (should-error)
tests.  This means that even on a test failure meson will report that
the test suite passed.  Set the exit status for all failures.

Signed-off-by: Peter Maydell <peter.maydell@linaro.org>
---
In an ideal world we'd tell meson how to run each test, so that
we got per-test pass/fail/log information, I suppose.
---
 tests/decode/check.sh | 1 +
 1 file changed, 1 insertion(+)

diff --git a/tests/decode/check.sh b/tests/decode/check.sh
index 95445a01155..4b5a47fbbf2 100755
--- a/tests/decode/check.sh
+++ b/tests/decode/check.sh
@@ -18,6 +18,7 @@ done
 for i in succ_*.decode; do
     if ! $PYTHON $DECODETREE $i > /dev/null 2> /dev/null; then
         echo FAIL:$i 1>&2
+        E=1
     fi
 done
 
-- 
2.34.1

Re: [PATCH 1/6] tests/decodetree/check.sh: Exit failure for all failures

[Richard Henderson]

On 5/23/23 05:04, Peter Maydell wrote:
> The check.sh script doesn't set its exit status to 1 for failures in
> the succ_* (should-pass) tests, only for the err_* (should-error)
> tests.  This means that even on a test failure meson will report that
> the test suite passed.  Set the exit status for all failures.
> 
> Signed-off-by: Peter Maydell <peter.maydell@linaro.org>
> ---
> In an ideal world we'd tell meson how to run each test, so that
> we got per-test pass/fail/log information, I suppose.

Reviewed-by: Richard Henderson <richard.henderson@linaro.org>

But I've also just sent a conversion to meson.


r~

[PATCH 2/6] docs: Document decodetree named field syntax

[Peter Maydell]

Document the named field syntax that we want to implement for the
decodetree script.  This allows a field to be defined in terms of
some other field that the instruction pattern has already set, for
example:

   %sz_imm 10:3 sz:3 !function=expand_sz_imm

to allow a function to be passed both an immediate field from the
instruction and also a sz value which might have been specified by
the instruction pattern directly (sz=1, etc) rather than being a
simple field within the instruction.

Note that the restriction on not having the format referring to the
pattern and the pattern referring to the format simultaneously is a
restriction of the decoder generator rather than inherently being a
silly thing to do.

Signed-off-by: Peter Maydell <peter.maydell@linaro.org>
---
 docs/devel/decodetree.rst | 33 ++++++++++++++++++++++++++++-----
 1 file changed, 28 insertions(+), 5 deletions(-)

diff --git a/docs/devel/decodetree.rst b/docs/devel/decodetree.rst
index 49ea50c2a7f..e3392aa7057 100644
--- a/docs/devel/decodetree.rst
+++ b/docs/devel/decodetree.rst
@@ -23,22 +23,42 @@ Fields
 
 Syntax::
 
-  field_def     := '%' identifier ( unnamed_field )* ( !function=identifier )?
+  field_def     := '%' identifier ( field )* ( !function=identifier )?
+  field         := unnamed_field | named_field
   unnamed_field := number ':' ( 's' ) number
+  named_field   := identifier ':' ( 's' ) number
 
 For *unnamed_field*, the first number is the least-significant bit position
 of the field and the second number is the length of the field.  If the 's' is
-present, the field is considered signed.  If multiple ``unnamed_fields`` are
-present, they are concatenated.  In this way one can define disjoint fields.
+present, the field is considered signed.
+
+A *named_field* refers to some other field in the instruction pattern
+or format. Regardless of the length of the other field where it is
+defined, it will be inserted into this field with the specified
+signedness and bit width.
+
+Field definitions that involve loops (i.e. where a field is defined
+directly or indirectly in terms of itself) are errors.
+
+A format can include fields that refer to named fields that are
+defined in the instruction pattern(s) that use the format.
+Conversely, an instruction pattern can include fields that refer to
+named fields that are defined in the format it uses. However you
+cannot currently do both at once (i.e. pattern P uses format F; F has
+a field A that refers to a named field B that is defined in P, and P
+has a field C that refers to a named field D that is defined in F).
+
+If multiple ``fields`` are present, they are concatenated.
+In this way one can define disjoint fields.
 
 If ``!function`` is specified, the concatenated result is passed through the
 named function, taking and returning an integral value.
 
-One may use ``!function`` with zero ``unnamed_fields``.  This case is called
+One may use ``!function`` with zero ``fields``.  This case is called
 a *parameter*, and the named function is only passed the ``DisasContext``
 and returns an integral value extracted from there.
 
-A field with no ``unnamed_fields`` and no ``!function`` is in error.
+A field with no ``fields`` and no ``!function`` is in error.
 
 Field examples:
 
@@ -56,6 +76,9 @@ Field examples:
 | %shimm8 5:s8 13:1         | expand_shimm8(sextract(i, 5, 8) << 1 |      |
 |   !function=expand_shimm8 |               extract(i, 13, 1))            |
 +---------------------------+---------------------------------------------+
+| %sz_imm 10:2 sz:3         | expand_sz_imm(extract(i, 10, 2) << 3 |      |
+|   !function=expand_sz_imm |               extract(a->sz, 0, 3))         |
++---------------------------+---------------------------------------------+
 
 Argument Sets
 =============
-- 
2.34.1

Re: [PATCH 2/6] docs: Document decodetree named field syntax

[Richard Henderson]

On 5/23/23 05:04, Peter Maydell wrote:
> Document the named field syntax that we want to implement for the
> decodetree script.  This allows a field to be defined in terms of
> some other field that the instruction pattern has already set, for
> example:
> 
>     %sz_imm 10:3 sz:3 !function=expand_sz_imm
> 
> to allow a function to be passed both an immediate field from the
> instruction and also a sz value which might have been specified by
> the instruction pattern directly (sz=1, etc) rather than being a
> simple field within the instruction.
> 
> Note that the restriction on not having the format referring to the
> pattern and the pattern referring to the format simultaneously is a
> restriction of the decoder generator rather than inherently being a
> silly thing to do.
> 
> Signed-off-by: Peter Maydell<peter.maydell@linaro.org>
> ---
>   docs/devel/decodetree.rst | 33 ++++++++++++++++++++++++++++-----
>   1 file changed, 28 insertions(+), 5 deletions(-)

Reviewed-by: Richard Henderson <richard.henderson@linaro.org>

r~

[PATCH 3/6] scripts/decodetree: Pass lvalue-formatter function to str_extract()

[Peter Maydell]

To support referring to other named fields in field definitions, we
need to pass the str_extract() method a function which tells it how
to emit the code for a previously initialized named field.  (In
Pattern::output_code() the other field will be "u.f_foo.field", and
in Format::output_extract() it is "a->field".)

Refactor the two callsites that currently do "output code to
initialize each field", and have them pass a lambda that defines how
to format the lvalue in each case.  This is then used both in
emitting the LHS of the assignment and also passed down to
str_extract() as a new argument (unused at the moment, but will be
used in the following patch).

Signed-off-by: Peter Maydell <peter.maydell@linaro.org>
---
 scripts/decodetree.py | 26 +++++++++++++++-----------
 1 file changed, 15 insertions(+), 11 deletions(-)

diff --git a/scripts/decodetree.py b/scripts/decodetree.py
index a03dc6b5e3e..33f4252b4ee 100644
--- a/scripts/decodetree.py
+++ b/scripts/decodetree.py
@@ -205,7 +205,7 @@ def __str__(self):
             s = ''
         return str(self.pos) + ':' + s + str(self.len)
 
-    def str_extract(self):
+    def str_extract(self, lvalue_formatter):
         global bitop_width
         s = 's' if self.sign else ''
         return f'{s}extract{bitop_width}(insn, {self.pos}, {self.len})'
@@ -228,12 +228,12 @@ def __init__(self, subs, mask):
     def __str__(self):
         return str(self.subs)
 
-    def str_extract(self):
+    def str_extract(self, lvalue_formatter):
         global bitop_width
         ret = '0'
         pos = 0
         for f in reversed(self.subs):
-            ext = f.str_extract()
+            ext = f.str_extract(lvalue_formatter)
             if pos == 0:
                 ret = ext
             else:
@@ -264,7 +264,7 @@ def __init__(self, value):
     def __str__(self):
         return str(self.value)
 
-    def str_extract(self):
+    def str_extract(self, lvalue_formatter):
         return str(self.value)
 
     def __cmp__(self, other):
@@ -283,8 +283,9 @@ def __init__(self, func, base):
     def __str__(self):
         return self.func + '(' + str(self.base) + ')'
 
-    def str_extract(self):
-        return self.func + '(ctx, ' + self.base.str_extract() + ')'
+    def str_extract(self, lvalue_formatter):
+        return (self.func + '(ctx, '
+                + self.base.str_extract(lvalue_formatter) + ')')
 
     def __eq__(self, other):
         return self.func == other.func and self.base == other.base
@@ -304,7 +305,7 @@ def __init__(self, func):
     def __str__(self):
         return self.func
 
-    def str_extract(self):
+    def str_extract(self, lvalue_formatter):
         return self.func + '(ctx)'
 
     def __eq__(self, other):
@@ -357,6 +358,11 @@ def __str__(self):
 
     def str1(self, i):
         return str_indent(i) + self.__str__()
+
+    def output_fields(self, indent, lvalue_formatter):
+        for n, f in self.fields.items():
+            output(indent, lvalue_formatter(n), ' = ',
+                   f.str_extract(lvalue_formatter), ';\n')
 # end General
 
 
@@ -370,8 +376,7 @@ def extract_name(self):
     def output_extract(self):
         output('static void ', self.extract_name(), '(DisasContext *ctx, ',
                self.base.struct_name(), ' *a, ', insntype, ' insn)\n{\n')
-        for n, f in self.fields.items():
-            output('    a->', n, ' = ', f.str_extract(), ';\n')
+        self.output_fields(str_indent(4), lambda n: 'a->' + n)
         output('}\n\n')
 # end Format
 
@@ -395,8 +400,7 @@ def output_code(self, i, extracted, outerbits, outermask):
         if not extracted:
             output(ind, self.base.extract_name(),
                    '(ctx, &u.f_', arg, ', insn);\n')
-        for n, f in self.fields.items():
-            output(ind, 'u.f_', arg, '.', n, ' = ', f.str_extract(), ';\n')
+        self.output_fields(ind, lambda n: 'u.f_' + arg + '.' + n)
         output(ind, 'if (', translate_prefix, '_', self.name,
                '(ctx, &u.f_', arg, ')) return true;\n')
 
-- 
2.34.1

Re: [PATCH 3/6] scripts/decodetree: Pass lvalue-formatter function to str_extract()

[Richard Henderson]

On 5/23/23 05:04, Peter Maydell wrote:
> To support referring to other named fields in field definitions, we
> need to pass the str_extract() method a function which tells it how
> to emit the code for a previously initialized named field.  (In
> Pattern::output_code() the other field will be "u.f_foo.field", and
> in Format::output_extract() it is "a->field".)
> 
> Refactor the two callsites that currently do "output code to
> initialize each field", and have them pass a lambda that defines how
> to format the lvalue in each case.  This is then used both in
> emitting the LHS of the assignment and also passed down to
> str_extract() as a new argument (unused at the moment, but will be
> used in the following patch).
> 
> Signed-off-by: Peter Maydell<peter.maydell@linaro.org>
> ---
>   scripts/decodetree.py | 26 +++++++++++++++-----------
>   1 file changed, 15 insertions(+), 11 deletions(-)

Reviewed-by: Richard Henderson <richard.henderson@linaro.org>

r~

[PATCH 4/6] scripts/decodetree: Implement a topological sort

[Peter Maydell]

To support named fields, we will need to be able to do a topological
sort (so that we ensure that we output the assignment to field A
before the assignment to field B if field B refers to field A by
name). The good news is that there is a tsort in the python standard
library; the bad news is that it was only added in Python 3.9.

To bridge the gap between our current minimum supported Python
version and 3.9, provide a local implementation that has the
same API as the stdlib version for the parts we care about.
In future when QEMU's minimum Python version requirement reaches
3.9 we can delete this code and replace it with an 'import' line.

The core of this implementation is based on
https://code.activestate.com/recipes/578272-topological-sort/
which is MIT-licensed.

Signed-off-by: Peter Maydell <peter.maydell@linaro.org>
---
 scripts/decodetree.py | 74 +++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 74 insertions(+)

diff --git a/scripts/decodetree.py b/scripts/decodetree.py
index 33f4252b4ee..e1fd995eaab 100644
--- a/scripts/decodetree.py
+++ b/scripts/decodetree.py
@@ -53,6 +53,80 @@
 re_fmt_ident = '@[a-zA-Z0-9_]*'
 re_pat_ident = '[a-zA-Z0-9_]*'
 
+# Local implementation of a topological sort. We use the same API that
+# the Python graphlib does, so that when QEMU moves forward to a
+# baseline of Python 3.9 or newer this code can all be dropped and
+# replaced with:
+#    from graphlib import TopologicalSorter, CycleError
+#
+# https://docs.python.org/3.9/library/graphlib.html#graphlib.TopologicalSorter
+#
+# We only implement the parts of TopologicalSorter we care about:
+#  ts = TopologicalSorter(graph=None)
+#    create the sorter. graph is a dictionary whose keys are
+#    nodes and whose values are lists of the predecessors of that node.
+#    (That is, if graph contains "A" -> ["B", "C"] then we must output
+#    B and C before A.)
+#  ts.static_order()
+#    returns a list of all the nodes in sorted order, or raises CycleError
+#  CycleError
+#    exception raised if there are cycles in the graph. The second
+#    element in the args attribute is a list of nodes which form a
+#    cycle; the first and last element are the same, eg [a, b, c, a]
+#    (Our implementation doesn't give the order correctly.)
+#
+# For our purposes we can assume that the data set is always small
+# (typically 10 nodes or less, actual links in the graph very rare),
+# so we don't need to worry about efficiency of implementation.
+#
+# The core of this implementation is from
+# https://code.activestate.com/recipes/578272-topological-sort/
+# (but updated to Python 3), and is under the MIT license.
+
+class CycleError(ValueError):
+    """Subclass of ValueError raised if cycles exist in the graph"""
+    pass
+
+class TopologicalSorter:
+    """Topologically sort a graph"""
+    def __init__(self, graph=None):
+        self.graph = graph
+
+    def static_order(self):
+        # We do the sort right here, unlike the stdlib version
+        from functools import reduce
+        data = {}
+        r = []
+
+        if not self.graph:
+            return []
+
+        # This code wants the values in the dict to be specifically sets
+        for k, v in self.graph.items():
+            data[k] = set(v)
+
+        # Find all items that don't depend on anything.
+        extra_items_in_deps = (reduce(set.union, data.values())
+                               - set(data.keys()))
+        # Add empty dependencies where needed
+        data.update({item:{} for item in extra_items_in_deps})
+        while True:
+            ordered = set(item for item, dep in data.items() if not dep)
+            if not ordered:
+                break
+            r.extend(ordered)
+            data = {item: (dep - ordered)
+                    for item, dep in data.items()
+                        if item not in ordered}
+        if data:
+            # This doesn't give as nice results as the stdlib, which
+            # gives you the cycle by listing the nodes in order. Here
+            # we only know the nodes in the cycle but not their order.
+            raise CycleError(f'nodes are in a cycle', list(data.keys()))
+
+        return r
+# end TopologicalSorter
+
 def error_with_file(file, lineno, *args):
     """Print an error message from file:line and args and exit."""
     global output_file
-- 
2.34.1

Re: [PATCH 4/6] scripts/decodetree: Implement a topological sort

[Richard Henderson]

On 5/23/23 05:04, Peter Maydell wrote:
> To support named fields, we will need to be able to do a topological
> sort (so that we ensure that we output the assignment to field A
> before the assignment to field B if field B refers to field A by
> name). The good news is that there is a tsort in the python standard
> library; the bad news is that it was only added in Python 3.9.
> 
> To bridge the gap between our current minimum supported Python
> version and 3.9, provide a local implementation that has the
> same API as the stdlib version for the parts we care about.
> In future when QEMU's minimum Python version requirement reaches
> 3.9 we can delete this code and replace it with an 'import' line.
> 
> The core of this implementation is based on
> https://code.activestate.com/recipes/578272-topological-sort/
> which is MIT-licensed.
> 
> Signed-off-by: Peter Maydell<peter.maydell@linaro.org>
> ---
>   scripts/decodetree.py | 74 +++++++++++++++++++++++++++++++++++++++++++
>   1 file changed, 74 insertions(+)

My python fu is not quite up to the constructor (?) forms used here, but

Acked-by: Richard Henderson <richard.henderson@linaro.org>


r~

[PATCH 5/6] scripts/decodetree: Implement named field support

[Peter Maydell]

Implement support for named fields, i.e.  where one field is defined
in terms of another, rather than directly in terms of bits extracted
from the instruction.

The new method referenced_fields() on all the Field classes returns a
list of fields that this field references.  This just passes through,
except for the new NamedField class.

We can then use referenced_fields() to:
 * construct a list of 'dangling references' for a format or
   pattern, which is the fields that the format/pattern uses but
   doesn't define itself
 * do a topological sort, so that we output "field = value"
   assignments in an order that means that we assign a field before
   we reference it in a subsequent assignment
 * check when we output the code for a pattern whether we need to
   fill in the format fields before or after the pattern fields, and
   do other error checking

Signed-off-by: Peter Maydell <peter.maydell@linaro.org>
---
 scripts/decodetree.py | 145 ++++++++++++++++++++++++++++++++++++++++--
 1 file changed, 139 insertions(+), 6 deletions(-)

diff --git a/scripts/decodetree.py b/scripts/decodetree.py
index e1fd995eaab..70629b37646 100644
--- a/scripts/decodetree.py
+++ b/scripts/decodetree.py
@@ -284,6 +284,9 @@ def str_extract(self, lvalue_formatter):
         s = 's' if self.sign else ''
         return f'{s}extract{bitop_width}(insn, {self.pos}, {self.len})'
 
+    def referenced_fields(self):
+        return []
+
     def __eq__(self, other):
         return self.sign == other.sign and self.mask == other.mask
 
@@ -315,6 +318,12 @@ def str_extract(self, lvalue_formatter):
             pos += f.len
         return ret
 
+    def referenced_fields(self):
+        l = []
+        for f in self.subs:
+            l.extend(f.referenced_fields())
+        return l
+
     def __ne__(self, other):
         if len(self.subs) != len(other.subs):
             return True
@@ -341,6 +350,9 @@ def __str__(self):
     def str_extract(self, lvalue_formatter):
         return str(self.value)
 
+    def referenced_fields(self):
+        return []
+
     def __cmp__(self, other):
         return self.value - other.value
 # end ConstField
@@ -361,6 +373,9 @@ def str_extract(self, lvalue_formatter):
         return (self.func + '(ctx, '
                 + self.base.str_extract(lvalue_formatter) + ')')
 
+    def referenced_fields(self):
+        return self.base.referenced_fields()
+
     def __eq__(self, other):
         return self.func == other.func and self.base == other.base
 
@@ -382,6 +397,9 @@ def __str__(self):
     def str_extract(self, lvalue_formatter):
         return self.func + '(ctx)'
 
+    def referenced_fields(self):
+        return []
+
     def __eq__(self, other):
         return self.func == other.func
 
@@ -389,6 +407,32 @@ def __ne__(self, other):
         return not self.__eq__(other)
 # end ParameterField
 
+class NamedField:
+    """Class representing a field already named in the pattern"""
+    def __init__(self, name, sign, len):
+        self.mask = 0
+        self.sign = sign
+        self.len = len
+        self.name = name
+
+    def __str__(self):
+        return self.name
+
+    def str_extract(self, lvalue_formatter):
+        global bitop_width
+        s = 's' if self.sign else ''
+        lvalue = lvalue_formatter(self.name)
+        return f'{s}extract{bitop_width}({lvalue}, 0, {self.len})'
+
+    def referenced_fields(self):
+        return [self.name]
+
+    def __eq__(self, other):
+        return self.name == other.name
+
+    def __ne__(self, other):
+        return not self.__eq__(other)
+# end NamedField
 
 class Arguments:
     """Class representing the extracted fields of a format"""
@@ -412,7 +456,6 @@ def output_def(self):
             output('} ', self.struct_name(), ';\n\n')
 # end Arguments
 
-
 class General:
     """Common code between instruction formats and instruction patterns"""
     def __init__(self, name, lineno, base, fixb, fixm, udfm, fldm, flds, w):
@@ -426,6 +469,7 @@ def __init__(self, name, lineno, base, fixb, fixm, udfm, fldm, flds, w):
         self.fieldmask = fldm
         self.fields = flds
         self.width = w
+        self.dangling = None
 
     def __str__(self):
         return self.name + ' ' + str_match_bits(self.fixedbits, self.fixedmask)
@@ -433,10 +477,51 @@ def __str__(self):
     def str1(self, i):
         return str_indent(i) + self.__str__()
 
+    def dangling_references(self):
+        # Return a list of all named references which aren't satisfied
+        # directly by this format/pattern. This will be either:
+        #  * a format referring to a field which is specified by the
+        #    pattern(s) using it
+        #  * a pattern referring to a field which is specified by the
+        #    format it uses
+        #  * a user error (referring to a field that doesn't exist at all)
+        if self.dangling is None:
+            # Compute this once and cache the answer
+            dangling = []
+            for n, f in self.fields.items():
+                for r in f.referenced_fields():
+                    if r not in self.fields:
+                        dangling.append(r)
+            self.dangling = dangling
+        return self.dangling
+
     def output_fields(self, indent, lvalue_formatter):
+        # We use a topological sort to ensure that any use of NamedField
+        # comes after the initialization of the field it is referencing.
+        graph = {}
         for n, f in self.fields.items():
-            output(indent, lvalue_formatter(n), ' = ',
-                   f.str_extract(lvalue_formatter), ';\n')
+            refs = f.referenced_fields()
+            graph[n] = refs
+
+        try:
+            ts = TopologicalSorter(graph)
+            for n in ts.static_order():
+                # We only want to emit assignments for the keys
+                # in our fields list, not for anything that ends up
+                # in the tsort graph only because it was referenced as
+                # a NamedField.
+                try:
+                    f = self.fields[n]
+                    output(indent, lvalue_formatter(n), ' = ',
+                           f.str_extract(lvalue_formatter), ';\n')
+                except KeyError:
+                    pass
+        except CycleError as e:
+            # The second element of args is a list of nodes which form
+            # a cycle (there might be others too, but only one is reported).
+            # Pretty-print it to tell the user.
+            cycle = ' => '.join(e.args[1])
+            error(self.lineno, 'field definitions form a cycle: ' + cycle)
 # end General
 
 
@@ -471,10 +556,36 @@ def output_code(self, i, extracted, outerbits, outermask):
         ind = str_indent(i)
         arg = self.base.base.name
         output(ind, '/* ', self.file, ':', str(self.lineno), ' */\n')
+        # We might have named references in the format that refer to fields
+        # in the pattern, or named references in the pattern that refer
+        # to fields in the format. This affects whether we extract the fields
+        # for the format before or after the ones for the pattern.
+        # For simplicity we don't allow cross references in both directions.
+        # This is also where we catch the syntax error of referring to
+        # a nonexistent field.
+        fmt_refs = self.base.dangling_references()
+        for r in fmt_refs:
+            if r not in self.fields:
+                error(self.lineno, f'format refers to undefined field {r}')
+        pat_refs = self.dangling_references()
+        for r in pat_refs:
+            if r not in self.base.fields:
+                error(self.lineno, f'pattern refers to undefined field {r}')
+        if pat_refs and fmt_refs:
+            error(self.lineno, ('pattern that uses fields defined in format '
+                                'cannot use format that uses fields defined '
+                                'in pattern'))
+        if fmt_refs:
+            # pattern fields first
+            self.output_fields(ind, lambda n: 'u.f_' + arg + '.' + n)
+            assert not extracted, "dangling fmt refs but it was already extracted"
         if not extracted:
             output(ind, self.base.extract_name(),
                    '(ctx, &u.f_', arg, ', insn);\n')
-        self.output_fields(ind, lambda n: 'u.f_' + arg + '.' + n)
+        if not fmt_refs:
+            # pattern fields last
+            self.output_fields(ind, lambda n: 'u.f_' + arg + '.' + n)
+
         output(ind, 'if (', translate_prefix, '_', self.name,
                '(ctx, &u.f_', arg, ')) return true;\n')
 
@@ -614,8 +725,10 @@ 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:
+        # extract the fields now. But don't do it if the format relies
+        # on named fields from the insn pattern, as those won't have
+        # been initialised at this point.
+        if not extracted and self.base and not self.base.dangling_references():
             output(ind, self.base.extract_name(),
                    '(ctx, &u.f_', self.base.base.name, ', insn);\n')
             extracted = True
@@ -737,6 +850,7 @@ def parse_field(lineno, name, toks):
     """Parse one instruction field from TOKS at LINENO"""
     global fields
     global insnwidth
+    global re_C_ident
 
     # A "simple" field will have only one entry;
     # a "multifield" will have several.
@@ -751,6 +865,25 @@ def parse_field(lineno, name, toks):
             func = func[1]
             continue
 
+        if re.fullmatch(re_C_ident + ':s[0-9]+', t):
+            # Signed named field
+            subtoks = t.split(':')
+            n = subtoks[0]
+            le = int(subtoks[1])
+            f = NamedField(n, True, le)
+            subs.append(f)
+            width += le
+            continue
+        if re.fullmatch(re_C_ident + ':[0-9]+', t):
+            # Unsigned named field
+            subtoks = t.split(':')
+            n = subtoks[0]
+            le = int(subtoks[1])
+            f = NamedField(n, False, le)
+            subs.append(f)
+            width += le
+            continue
+
         if re.fullmatch('[0-9]+:s[0-9]+', t):
             # Signed field extract
             subtoks = t.split(':s')
-- 
2.34.1

Re: [PATCH 5/6] scripts/decodetree: Implement named field support

[Richard Henderson]

On 5/23/23 05:04, Peter Maydell wrote:
> Implement support for named fields, i.e.  where one field is defined
> in terms of another, rather than directly in terms of bits extracted
> from the instruction.
> 
> The new method referenced_fields() on all the Field classes returns a
> list of fields that this field references.  This just passes through,
> except for the new NamedField class.
> 
> We can then use referenced_fields() to:
>   * construct a list of 'dangling references' for a format or
>     pattern, which is the fields that the format/pattern uses but
>     doesn't define itself
>   * do a topological sort, so that we output "field = value"
>     assignments in an order that means that we assign a field before
>     we reference it in a subsequent assignment
>   * check when we output the code for a pattern whether we need to
>     fill in the format fields before or after the pattern fields, and
>     do other error checking
> 
> Signed-off-by: Peter Maydell<peter.maydell@linaro.org>
> ---
>   scripts/decodetree.py | 145 ++++++++++++++++++++++++++++++++++++++++--
>   1 file changed, 139 insertions(+), 6 deletions(-)

Reviewed-by: Richard Henderson <richard.henderson@linaro.org>

r~

[PATCH 6/6] tests/decode: Add tests for various named-field cases

[Peter Maydell]

Add some tests for various cases of named-field use, both ones that
should work and ones that should be diagnosed as errors.

Signed-off-by: Peter Maydell <peter.maydell@linaro.org>
---
 tests/decode/err_field1.decode       |  2 +-
 tests/decode/err_field10.decode      |  7 +++++++
 tests/decode/err_field7.decode       |  7 +++++++
 tests/decode/err_field8.decode       |  8 ++++++++
 tests/decode/err_field9.decode       | 14 ++++++++++++++
 tests/decode/succ_named_field.decode | 19 +++++++++++++++++++
 6 files changed, 56 insertions(+), 1 deletion(-)
 create mode 100644 tests/decode/err_field10.decode
 create mode 100644 tests/decode/err_field7.decode
 create mode 100644 tests/decode/err_field8.decode
 create mode 100644 tests/decode/err_field9.decode
 create mode 100644 tests/decode/succ_named_field.decode

diff --git a/tests/decode/err_field1.decode b/tests/decode/err_field1.decode
index e07a5a73e0e..85c3f326d07 100644
--- a/tests/decode/err_field1.decode
+++ b/tests/decode/err_field1.decode
@@ -2,4 +2,4 @@
 # See the COPYING.LIB file in the top-level directory.
 
 # Diagnose invalid field syntax
-%field	asdf
+%field	1asdf
diff --git a/tests/decode/err_field10.decode b/tests/decode/err_field10.decode
new file mode 100644
index 00000000000..3e672b7459e
--- /dev/null
+++ b/tests/decode/err_field10.decode
@@ -0,0 +1,7 @@
+# This work is licensed under the terms of the GNU LGPL, version 2 or later.
+# See the COPYING.LIB file in the top-level directory.
+
+# Diagnose formats which refer to undefined fields
+%field1        field2:3
+@fmt ........ ........ ........ ........ %field1
+insn 00000000 00000000 00000000 00000000 @fmt
diff --git a/tests/decode/err_field7.decode b/tests/decode/err_field7.decode
new file mode 100644
index 00000000000..51fad7cceaf
--- /dev/null
+++ b/tests/decode/err_field7.decode
@@ -0,0 +1,7 @@
+# This work is licensed under the terms of the GNU LGPL, version 2 or later.
+# See the COPYING.LIB file in the top-level directory.
+
+# Diagnose fields whose definitions form a loop
+%field1        field2:3
+%field2        field1:4
+insn 00000000 00000000 00000000 00000000 %field1 %field2
diff --git a/tests/decode/err_field8.decode b/tests/decode/err_field8.decode
new file mode 100644
index 00000000000..cc47c08a459
--- /dev/null
+++ b/tests/decode/err_field8.decode
@@ -0,0 +1,8 @@
+# This work is licensed under the terms of the GNU LGPL, version 2 or later.
+# See the COPYING.LIB file in the top-level directory.
+
+# Diagnose patterns which refer to undefined fields
+&f1 f1 a
+%field1        field2:3
+@fmt ........ ........ ........ .... a:4 &f1
+insn 00000000 00000000 00000000 0000 .... @fmt f1=%field1
diff --git a/tests/decode/err_field9.decode b/tests/decode/err_field9.decode
new file mode 100644
index 00000000000..e7361d521ba
--- /dev/null
+++ b/tests/decode/err_field9.decode
@@ -0,0 +1,14 @@
+# This work is licensed under the terms of the GNU LGPL, version 2 or later.
+# See the COPYING.LIB file in the top-level directory.
+
+# Diagnose fields where the format refers to a field defined in the
+# pattern and the pattern refers to a field defined in the format.
+# This is theoretically not impossible to implement, but is not
+# supported by the script at this time.
+&abcd a b c d
+%refa        a:3
+%refc        c:4
+# Format defines 'c' and sets 'b' to an indirect ref to 'a'
+@fmt ........ ........ ........ c:8 &abcd b=%refa
+# Pattern defines 'a' and sets 'd' to an indirect ref to 'c'
+insn 00000000 00000000 00000000 ........ @fmt d=%refc a=6
diff --git a/tests/decode/succ_named_field.decode b/tests/decode/succ_named_field.decode
new file mode 100644
index 00000000000..e64b3f93568
--- /dev/null
+++ b/tests/decode/succ_named_field.decode
@@ -0,0 +1,19 @@
+# This work is licensed under the terms of the GNU LGPL, version 2 or later.
+# See the COPYING.LIB file in the top-level directory.
+
+# field using a named_field
+%imm_sz	8:8 sz:3
+insn 00000000 00000000 ........ 00000000 imm_sz=%imm_sz sz=1
+
+# Ditto, via a format. Here a field in the format
+# references a named field defined in the insn pattern:
+&imm_a imm alpha
+%foo 0:16 alpha:4
+@foo 00000001 ........ ........ ........ &imm_a imm=%foo
+i1   ........ 00000000 ........ ........ @foo alpha=1
+i2   ........ 00000001 ........ ........ @foo alpha=2
+
+# Here the named field is defined in the format and referenced
+# from the insn pattern:
+@bar 00000010 ........ ........ ........ &imm_a alpha=4
+i3   ........ 00000000 ........ ........ @bar imm=%foo
-- 
2.34.1

Re: [PATCH 6/6] tests/decode: Add tests for various named-field cases

[Richard Henderson]

On 5/23/23 05:04, Peter Maydell wrote:
> Add some tests for various cases of named-field use, both ones that
> should work and ones that should be diagnosed as errors.
> 
> Signed-off-by: Peter Maydell<peter.maydell@linaro.org>
> ---
>   tests/decode/err_field1.decode       |  2 +-
>   tests/decode/err_field10.decode      |  7 +++++++
>   tests/decode/err_field7.decode       |  7 +++++++
>   tests/decode/err_field8.decode       |  8 ++++++++
>   tests/decode/err_field9.decode       | 14 ++++++++++++++
>   tests/decode/succ_named_field.decode | 19 +++++++++++++++++++
>   6 files changed, 56 insertions(+), 1 deletion(-)
>   create mode 100644 tests/decode/err_field10.decode
>   create mode 100644 tests/decode/err_field7.decode
>   create mode 100644 tests/decode/err_field8.decode
>   create mode 100644 tests/decode/err_field9.decode
>   create mode 100644 tests/decode/succ_named_field.decode

Reviewed-by: Richard Henderson <richard.henderson@linaro.org>

r~

Re: [PATCH 6/6] tests/decode: Add tests for various named-field cases

[Peter Maydell]

On Tue, 23 May 2023 at 13:04, Peter Maydell <peter.maydell@linaro.org> wrote:
>
> Add some tests for various cases of named-field use, both ones that
> should work and ones that should be diagnosed as errors.
>
> Signed-off-by: Peter Maydell <peter.maydell@linaro.org>
> ---
>  tests/decode/err_field1.decode       |  2 +-
>  tests/decode/err_field10.decode      |  7 +++++++
>  tests/decode/err_field7.decode       |  7 +++++++
>  tests/decode/err_field8.decode       |  8 ++++++++
>  tests/decode/err_field9.decode       | 14 ++++++++++++++
>  tests/decode/succ_named_field.decode | 19 +++++++++++++++++++
>  6 files changed, 56 insertions(+), 1 deletion(-)
>  create mode 100644 tests/decode/err_field10.decode
>  create mode 100644 tests/decode/err_field7.decode
>  create mode 100644 tests/decode/err_field8.decode
>  create mode 100644 tests/decode/err_field9.decode
>  create mode 100644 tests/decode/succ_named_field.decode
>
> diff --git a/tests/decode/err_field1.decode b/tests/decode/err_field1.decode
> index e07a5a73e0e..85c3f326d07 100644
> --- a/tests/decode/err_field1.decode
> +++ b/tests/decode/err_field1.decode
> @@ -2,4 +2,4 @@
>  # See the COPYING.LIB file in the top-level directory.
>
>  # Diagnose invalid field syntax
> -%field asdf
> +%field 1asdf

I just realized that this specific change needs to go before patch 5:
it's updating an existing test because "asdf" used to be invalid
syntax and now is not. Otherwise bisection will break.

-- PMM

Re: [PATCH 6/6] tests/decode: Add tests for various named-field cases

[Richard Henderson]

On 5/24/23 03:26, Peter Maydell wrote:
> On Tue, 23 May 2023 at 13:04, Peter Maydell <peter.maydell@linaro.org> wrote:
>>
>> Add some tests for various cases of named-field use, both ones that
>> should work and ones that should be diagnosed as errors.
>>
>> Signed-off-by: Peter Maydell <peter.maydell@linaro.org>
>> ---
>>   tests/decode/err_field1.decode       |  2 +-
>>   tests/decode/err_field10.decode      |  7 +++++++
>>   tests/decode/err_field7.decode       |  7 +++++++
>>   tests/decode/err_field8.decode       |  8 ++++++++
>>   tests/decode/err_field9.decode       | 14 ++++++++++++++
>>   tests/decode/succ_named_field.decode | 19 +++++++++++++++++++
>>   6 files changed, 56 insertions(+), 1 deletion(-)
>>   create mode 100644 tests/decode/err_field10.decode
>>   create mode 100644 tests/decode/err_field7.decode
>>   create mode 100644 tests/decode/err_field8.decode
>>   create mode 100644 tests/decode/err_field9.decode
>>   create mode 100644 tests/decode/succ_named_field.decode
>>
>> diff --git a/tests/decode/err_field1.decode b/tests/decode/err_field1.decode
>> index e07a5a73e0e..85c3f326d07 100644
>> --- a/tests/decode/err_field1.decode
>> +++ b/tests/decode/err_field1.decode
>> @@ -2,4 +2,4 @@
>>   # See the COPYING.LIB file in the top-level directory.
>>
>>   # Diagnose invalid field syntax
>> -%field asdf
>> +%field 1asdf
> 
> I just realized that this specific change needs to go before patch 5:
> it's updating an existing test because "asdf" used to be invalid
> syntax and now is not. Otherwise bisection will break.

Really?  The test still fails here at patch 5:

/home/rth/qemu/bld/../src/tests/decode/err_field1.decode:5: error: invalid field token "asdf"


r~

Re: [PATCH 6/6] tests/decode: Add tests for various named-field cases

[Peter Maydell]

On Fri, 26 May 2023 at 18:07, Richard Henderson
<richard.henderson@linaro.org> wrote:
>
> On 5/24/23 03:26, Peter Maydell wrote:
> > On Tue, 23 May 2023 at 13:04, Peter Maydell <peter.maydell@linaro.org> wrote:
> >>
> >> Add some tests for various cases of named-field use, both ones that
> >> should work and ones that should be diagnosed as errors.
> >>
> >> Signed-off-by: Peter Maydell <peter.maydell@linaro.org>
> >> ---
> >>   tests/decode/err_field1.decode       |  2 +-
> >>   tests/decode/err_field10.decode      |  7 +++++++
> >>   tests/decode/err_field7.decode       |  7 +++++++
> >>   tests/decode/err_field8.decode       |  8 ++++++++
> >>   tests/decode/err_field9.decode       | 14 ++++++++++++++
> >>   tests/decode/succ_named_field.decode | 19 +++++++++++++++++++
> >>   6 files changed, 56 insertions(+), 1 deletion(-)
> >>   create mode 100644 tests/decode/err_field10.decode
> >>   create mode 100644 tests/decode/err_field7.decode
> >>   create mode 100644 tests/decode/err_field8.decode
> >>   create mode 100644 tests/decode/err_field9.decode
> >>   create mode 100644 tests/decode/succ_named_field.decode
> >>
> >> diff --git a/tests/decode/err_field1.decode b/tests/decode/err_field1.decode
> >> index e07a5a73e0e..85c3f326d07 100644
> >> --- a/tests/decode/err_field1.decode
> >> +++ b/tests/decode/err_field1.decode
> >> @@ -2,4 +2,4 @@
> >>   # See the COPYING.LIB file in the top-level directory.
> >>
> >>   # Diagnose invalid field syntax
> >> -%field asdf
> >> +%field 1asdf
> >
> > I just realized that this specific change needs to go before patch 5:
> > it's updating an existing test because "asdf" used to be invalid
> > syntax and now is not. Otherwise bisection will break.
>
> Really?  The test still fails here at patch 5:
>
> /home/rth/qemu/bld/../src/tests/decode/err_field1.decode:5: error: invalid field token "asdf"

Oh, right, because there's no trailing size specification
so it doesn't get recognized as a named field.

thanks
-- PMM