[go/dev.simd] [dev.simd] simd/archsimd/_gen/specgen/specexpr: constraint solver for SIMD spec
7 views
Skip to first unread message
Austin Clements (Gerrit)
Jul 9, 2026, 2:41:07 PMJul 9
to David Chase, Junyang Shao, goph...@pubsubhelper.golang.org, Cherry Mui, Austin Clements, golang-co...@googlegroups.com
Attention needed from David Chase and Junyang Shao
Austin Clements has uploaded the change for review![]( "Open in Gerrit")
Austin Clements would like David Chase and Junyang Shao to review this change.
Commit message
[dev.simd] simd/archsimd/_gen/specgen/specexpr: constraint solver for SIMD spec
The SIMD spec package uses Go generics to express a lot of the
constraints on vector shapes and other types in the API, but that
can't express everything we need.
This package implements a simple expression language and constraint
solver for writing additional constraints on API types. It's only
meant to be used by the specgen package, which will provide a much
higher-level API to processing the SIMD spec.
Change-Id: I3e8a9e5381f6f507c1e1cf22c69dc1338c63c044
Change diff
diff --git a/src/simd/archsimd/_gen/specgen/specexpr/expr.go b/src/simd/archsimd/_gen/specgen/specexpr/expr.go
new file mode 100644
index 0000000..e70a3b8
--- /dev/null
+++ b/src/simd/archsimd/_gen/specgen/specexpr/expr.go
@@ -0,0 +1,337 @@
+// Copyright 2026 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package specexpr
+
+import (
+ "cmp"
+ "fmt"
+ "iter"
+ "reflect"
+ "strings"
+ "sync"
+)
+
+type Expr interface {
+ String() string
+ Eval(b *Bindings) (any, error)
+ preorder(yield func(Expr) bool) bool
+}
+
+func exprVars(e Expr) iter.Seq[Variable] {
+ return func(yield func(Variable) bool) {
+ e.preorder(func(e Expr) bool {
+ if v, ok := e.(Variable); ok {
+ return yield(v)
+ }
+ return true
+ })
+ }
+}
+
+type Literal struct {
+ Val any
+}
+
+func (e *Literal) String() string {
+ return fmt.Sprint(e.Val)
+}
+func (e *Literal) Eval(b *Bindings) (any, error) {
+ return e.Val, nil
+}
+func (e *Literal) preorder(yield func(Expr) bool) bool {
+ return yield(e)
+}
+
+type Variable string
+
+func (e Variable) String() string {
+ return string(e)
+}
+func (e Variable) Eval(b *Bindings) (any, error) {
+ val := b.Get(e)
+ if val == nil {
+ panic(fmt.Errorf("variable %s not solved", e))
+ }
+ return val, nil
+}
+func (e Variable) preorder(yield func(Expr) bool) bool {
+ return yield(e)
+}
+
+type Func struct {
+ Name string
+ Func func([]any) (any, error)
+}
+
+func MakeFunc1[T any](name string, fn func(T) (any, error)) func(e Expr) *Apply {
+ f := &Func{
+ Name: name,
+ Func: func(a []any) (any, error) {
+ if len(a) != 1 {
+ panic(fmt.Sprintf("got %d arguments, want %d", len(a), 1))
+ }
+ v, ok := a[0].(T)
+ if !ok {
+ panic(fmt.Sprintf("argument is %T, want %T", a[0], *new(T)))
+ }
+ return fn(v)
+ },
+ }
+ return func(e Expr) *Apply {
+ return f.Apply(e)
+ }
+}
+func MakeFunc2[T, U any](name string, fn func(T, U) (any, error)) func(e1, e2 Expr) *Apply {
+ f := &Func{
+ Name: name,
+ Func: func(a []any) (any, error) {
+ if len(a) != 2 {
+ panic(fmt.Sprintf("got %d arguments, want %d", len(a), 2))
+ }
+ v1, ok := a[0].(T)
+ if !ok {
+ panic(fmt.Sprintf("argument is %T, want %T", a[0], *new(T)))
+ }
+ v2, ok := a[1].(U)
+ if !ok {
+ panic(fmt.Sprintf("argument is %T, want %T", a[1], *new(U)))
+ }
+ return fn(v1, v2)
+ },
+ }
+ return func(e1, e2 Expr) *Apply {
+ return f.Apply(e1, e2)
+ }
+}
+
+func MakeFunc(name string, fn func([]any) (any, error)) *Func {
+ return &Func{name, fn}
+}
+
+type fieldGetterKey struct {
+ rt reflect.Type
+ fieldName string
+}
+
+var fieldGetters sync.Map
+
+// MakeField returns a Func that projects field fieldName from a value of type
+// T. The returned functions are memoized, so only one *Func is created per type
+// and field and this is efficient to call repeatedly.
+func MakeField[T any](fieldName string) *Func {
+ rt := reflect.TypeFor[T]()
+ key := fieldGetterKey{rt, fieldName}
+ get, ok := fieldGetters.Load(key)
+ if !ok {
+ f, ok := rt.FieldByName(fieldName)
+ if !ok {
+ panic(fmt.Sprintf("no such field %s in type %s", fieldName, rt))
+ }
+ getF := MakeFunc(rt.Name()+"."+fieldName, func(a []any) (any, error) {
+ if len(a) != 1 {
+ panic("expected exactly 1 argument")
+ }
+ var rv reflect.Value
+ if _, ok := a[0].(T); ok {
+ rv = reflect.ValueOf(a[0])
+ } else if _, ok := a[0].(*T); ok {
+ rv = reflect.ValueOf(a[0]).Elem()
+ } else {
+ panic(fmt.Sprintf("argument is %T, want %s", a[0], rt))
+ }
+ return rv.FieldByIndex(f.Index).Interface(), nil
+ })
+ get, _ = fieldGetters.LoadOrStore(key, getF)
+ }
+ return get.(*Func)
+}
+
+func (f *Func) Apply(args ...Expr) *Apply {
+ return &Apply{f, args}
+}
+
+type Apply struct {
+ Func *Func
+ Args []Expr
+}
+
+func (e *Apply) String() string {
+ var buf strings.Builder
+ buf.WriteString(e.Func.Name)
+ buf.WriteByte('(')
+ for i, x := range e.Args {
+ if i > 0 {
+ buf.WriteString(", ")
+ }
+ buf.WriteString(x.String())
+ }
+ buf.WriteByte(')')
+ return buf.String()
+}
+func (e *Apply) Eval(b *Bindings) (any, error) {
+ vals := make([]any, 0, 16)
+ for _, arg := range e.Args {
+ val, err := arg.Eval(b)
+ if err != nil {
+ return nil, err
+ }
+ vals = append(vals, val)
+ }
+ return e.Func.Func(vals)
+}
+func (e *Apply) preorder(yield func(Expr) bool) bool {
+ if !yield(e) {
+ return false
+ }
+ for _, a := range e.Args {
+ if !a.preorder(yield) {
+ return false
+ }
+ }
+ return true
+}
+
+type BinExpr struct {
+ Op BinOp
+ X, Y Expr
+}
+
+func (e *BinExpr) String() string {
+ op := "???"
+ if int(e.Op) < len(opStrings) && opStrings[e.Op] != "" {
+ op = opStrings[e.Op]
+ }
+ return e.X.String() + op + e.Y.String()
+}
+func (e *BinExpr) preorder(yield func(Expr) bool) bool {
+ return yield(e) && e.X.preorder(yield) && e.Y.preorder(yield)
+}
+
+type BinOp byte
+
+const (
+ _ BinOp = iota
+ OpTimes // int = int * int or Width = int * Width (or Width * int)
+ OpDiv // int = int / int (must be exact) or Width = Width / int
+
+ // Comparison operators
+ OpEqual // bool = expr = expr
+ OpNotEqual // bool = expr != expr
+ OpGreaterThan // bool = expr > expr
+ OpLessThan // bool = expr < expr
+ OpGreaterOrEqual // bool = expr >= expr
+ OpLessOrEqual // bool = expr <= expr
+)
+
+var opStrings = [...]string{
+ OpTimes: "*",
+ OpDiv: "/",
+
+ OpEqual: "=",
+ OpNotEqual: "!=",
+ OpGreaterThan: ">",
+ OpLessThan: "<",
+ OpGreaterOrEqual: ">=",
+ OpLessOrEqual: "<=",
+}
+
+func (e *BinExpr) Eval(b *Bindings) (any, error) {
+ xVal, err := e.X.Eval(b)
+ if err != nil {
+ return nil, err
+ }
+ yVal, err := e.Y.Eval(b)
+ if err != nil {
+ return nil, err
+ }
+
+ xi, xIsInt := xVal.(int)
+ yi, yIsInt := yVal.(int)
+ xw, xIsWidth := xVal.(Width)
+ yw, yIsWidth := yVal.(Width)
+
+ switch e.Op {
+ case OpTimes:
+ switch {
+ case xIsInt && yIsInt:
+ return xi * yi, nil
+ case xIsInt && yIsWidth:
+ return yw.Mul(xi), nil
+ case xIsWidth && yIsInt:
+ return xw.Mul(yi), nil
+ default:
+ panic(fmt.Errorf("invalid types for multiplication: %T and %T", xVal, yVal))
+ }
+
+ case OpDiv:
+ switch {
+ case xIsInt && yIsInt:
+ if yi == 0 {
+ return nil, fmt.Errorf("division by zero")
+ }
+ if xi%yi != 0 {
+ return nil, fmt.Errorf("inexact division %d/%d", xi, yi)
+ }
+ return xi / yi, nil
+ case xIsWidth && yIsInt:
+ return xw.DivInt(yi)
+ default:
+ panic(fmt.Errorf("invalid types for division: %T and %T", xVal, yVal))
+ }
+
+ case OpEqual, OpNotEqual, OpGreaterThan, OpLessThan, OpGreaterOrEqual, OpLessOrEqual:
+ return e.evalComparison(xVal, yVal)
+ }
+
+ panic("bad binop")
+}
+
+func (e *BinExpr) evalComparison(xVal, yVal any) (any, error) {
+ xi, xIsInt := xVal.(int)
+ yi, yIsInt := yVal.(int)
+ xw, xIsWidth := xVal.(Width)
+ yw, yIsWidth := yVal.(Width)
+
+ var res int
+ switch {
+ case xIsInt && yIsInt:
+ res = cmp.Compare(xi, yi)
+ case xIsWidth && yIsWidth:
+ var ok bool
+ res, ok = xw.Compare(yw)
+ if !ok {
+ // Incomparable
+ return e.Op == OpNotEqual, nil
+ }
+ default:
+ switch e.Op {
+ case OpEqual, OpNotEqual:
+ if reflect.TypeOf(xVal) != reflect.TypeOf(yVal) {
+ panic(fmt.Errorf("incompatible types for comparison: %T and %T", xVal, yVal))
+ }
+ if e.Op == OpEqual {
+ return xVal == yVal, nil
+ } else {
+ return xVal != yVal, nil
+ }
+ }
+ panic(fmt.Errorf("incompatible types for comparison: %T and %T", xVal, yVal))
+ }
+ switch e.Op {
+ case OpEqual:
+ return res == 0, nil
+ case OpNotEqual:
+ return res != 0, nil
+ case OpGreaterThan:
+ return res > 0, nil
+ case OpLessThan:
+ return res < 0, nil
+ case OpGreaterOrEqual:
+ return res >= 0, nil
+ case OpLessOrEqual:
+ return res <= 0, nil
+ }
+ panic(fmt.Errorf("unsupported comparison operator"))
+}
diff --git a/src/simd/archsimd/_gen/specgen/specexpr/parse.go b/src/simd/archsimd/_gen/specgen/specexpr/parse.go
new file mode 100644
index 0000000..84bab9e
--- /dev/null
+++ b/src/simd/archsimd/_gen/specgen/specexpr/parse.go
@@ -0,0 +1,278 @@
+// Copyright 2026 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package specexpr
+
+import (
+ "fmt"
+ "strconv"
+ "strings"
+)
+
+// ParseExpr parses an expression.
+func ParseExpr(x string) (Expr, error) {
+ var e Expr
+ var err error
+
+ func() {
+ defer func() {
+ v := recover()
+ if v2, ok := v.(*parseError); ok {
+ err = v2
+ return
+ } else if v != nil {
+ panic(v)
+ }
+ }()
+ p := &parser{s: x}
+ p.skipSpace()
+ e = p.parseExpr()
+ if p.pos < len(p.s) {
+ p.fail("unexpected trailing characters")
+ }
+ }()
+ return e, err
+}
+
+type parser struct {
+ s string
+ pos int
+}
+
+type parseError struct {
+ msg string
+ args []any
+ pos int
+}
+
+func (e *parseError) Error() string {
+ return fmt.Sprintf("%s at %d", fmt.Sprintf(e.msg, e.args...), 1+e.pos)
+}
+
+func (p *parser) fail(msg string, args ...any) {
+ panic(&parseError{msg: msg, args: args, pos: p.pos})
+}
+
+func (p *parser) skipSpace() {
+ for p.pos < len(p.s) && (p.s[p.pos] == ' ' || p.s[p.pos] == '\t' || p.s[p.pos] == '\r' || p.s[p.pos] == '\n') {
+ p.pos++
+ }
+}
+
+func (p *parser) peek() byte {
+ if p.pos >= len(p.s) {
+ return 0
+ }
+ return p.s[p.pos]
+}
+
+// consume consumes one or more characters matching pred. It does NOT consume
+// whitespace.
+func (p *parser) consume(pred func(c byte) bool) (string, bool) {
+ if p.pos >= len(p.s) || !pred(p.s[p.pos]) {
+ return "", false
+ }
+ start := p.pos
+ p.pos++
+ for p.pos < len(p.s) && pred(p.s[p.pos]) {
+ p.pos++
+ }
+ return p.s[start:p.pos], true
+}
+
+func isDigit(c byte) bool {
+ return c >= '0' && c <= '9'
+}
+
+func isAlpha(c byte) bool {
+ return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z')
+}
+
+// try either consumes s followed zero or more whitespace and returns true, or
+// does nothing and returns false.
+func (p *parser) try(s string) bool {
+ if !strings.HasPrefix(p.s[p.pos:], s) {
+ return false
+ }
+ p.pos += len(s)
+ p.skipSpace()
+ return true
+}
+
+func (p *parser) peekShape() bool {
+ // Peek base type
+ if p.peek() == '{' {
+ return true
+ }
+ start := p.pos
+ if _, ok := p.consume(isAlpha); !ok {
+ return false
+ }
+ // Peek N
+ ok := p.pos < len(p.s) && (isDigit(p.s[p.pos]) || p.s[p.pos] == '{')
+ p.pos = start
+ return ok
+}
+
+func (p *parser) parseExpr() Expr {
+ return p.parseComparison()
+}
+
+func (p *parser) parseComparison() Expr {
+ x := p.parseMulDiv()
+ var op BinOp
+ switch {
+ case p.try("="):
+ op = OpEqual
+ case p.try("!="):
+ op = OpNotEqual
+ case p.try(">="):
+ op = OpGreaterOrEqual
+ case p.try(">"):
+ op = OpGreaterThan
+ case p.try("<="):
+ op = OpLessOrEqual
+ case p.try("<"):
+ op = OpLessThan
+ default:
+ return x
+ }
+
+ y := p.parseMulDiv()
+ return &BinExpr{op, x, y}
+}
+
+func (p *parser) parseMulDiv() Expr {
+ x := p.parsePrimary()
+loop:
+ for {
+ var op BinOp
+ switch {
+ case p.try("*"):
+ op = OpTimes
+ case p.try("/"):
+ op = OpDiv
+ default:
+ break loop
+ }
+ y := p.parsePrimary()
+ x = &BinExpr{op, x, y}
+ }
+ return x
+}
+
+func (p *parser) parsePrimary() Expr {
+ if p.try("(") {
+ e := p.parseExpr()
+ if !p.try(")") {
+ p.fail("expected ')'")
+ }
+ return e
+ }
+
+ // Shape
+ if p.peekShape() {
+ return p.parseSymShape()
+ }
+
+ // Number literal
+ b := p.peek()
+ if isDigit(b) {
+ val := p.parseNumber()
+ return &Literal{val}
+ }
+
+ // Variable
+ if isAlpha(b) {
+ name, _ := p.consume(isAlpha)
+ p.skipSpace()
+ return Variable(name)
+ }
+
+ if b == 0 {
+ p.fail("unexpected end")
+ }
+ p.fail("unexpected character '%c'", b)
+ panic("not reachable")
+}
+
+func (p *parser) parseNumber() int {
+ nStr, ok := p.consume(isDigit)
+ if !ok {
+ p.fail("expected number")
+ }
+ num, err := strconv.Atoi(nStr)
+ if err != nil {
+ p.fail("%s", err)
+ }
+ p.skipSpace()
+ return num
+}
+
+// - BaseNxL: A fixed vector with L lanes. E.g., Int32x4
+// - BaseNs: A scalable vector. E.g., Float32s
+// - BaseNwW: A fixed vector of width W. E.g., Int32w128 (same as Int32x4)
+// - MaskNxL, MaskNs, or MaskNwW: Similar, but describes a mask.
+// - baseN: A scalar. E.g., uint8
+func (p *parser) parseSymShape() *Apply {
+ var b, n Expr
+
+ trySymPart := func() Expr {
+ if !p.try("{") {
+ return nil
+ }
+
+ x := p.parseExpr()
+ if !p.try("}") {
+ p.fail("expected '}' in symbolic shape")
+ }
+ return x
+ }
+
+ // Base
+ if b = trySymPart(); b == nil {
+ base, ok := p.consume(isAlpha)
+ if !ok {
+ p.fail("expected shape base name")
+ }
+ b = &Literal{strings.ToLower(base)}
+ }
+
+ // Element size
+ if n = trySymPart(); n == nil {
+ n = &Literal{p.parseNumber()}
+ }
+
+ elem := MakeBasic(b, n)
+
+ // Width
+ var x *Apply
+ // Don't use p.try here because that will skip whitespace.
+ switch p.peek() {
+ case 's':
+ p.pos++
+ x = MakeVector(elem, &Literal{UnitWidth()})
+ case 'x':
+ p.pos++
+ l := trySymPart()
+ if l == nil {
+ // TODO: Disallow width-rounding in this case?
+ l = &Literal{Val: FixedWidth(p.parseNumber())}
+ }
+ x = makeVectorL(elem, l)
+ case 'w':
+ p.pos++
+ w := trySymPart()
+ if w == nil {
+ w = &Literal{Val: FixedWidth(p.parseNumber())}
+ }
+ x = MakeVector(elem, w)
+ default:
+ // Scalar
+ x = elem
+ }
+
+ p.skipSpace()
+ return x
+}
diff --git a/src/simd/archsimd/_gen/specgen/specexpr/parse_test.go b/src/simd/archsimd/_gen/specgen/specexpr/parse_test.go
new file mode 100644
index 0000000..4712d45
--- /dev/null
+++ b/src/simd/archsimd/_gen/specgen/specexpr/parse_test.go
@@ -0,0 +1,142 @@
+// Copyright 2026 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package specexpr
+
+import (
+ "reflect"
+ "strings"
+ "testing"
+)
+
+func TestParseExpr(t *testing.T) {
+ tests := []struct {
+ expr string
+ want Expr
+ }{
+ {
+ expr: "10",
+ want: &Literal{10},
+ },
+ {
+ expr: "v",
+ want: Variable("v"),
+ },
+ {
+ expr: "v * 2",
+ want: &BinExpr{OpTimes, Variable("v"), &Literal{2}},
+ },
+ {
+ expr: "v / 2",
+ want: &BinExpr{OpDiv, Variable("v"), &Literal{2}},
+ },
+ {
+ expr: "x = y * 2",
+ want: &BinExpr{OpEqual, Variable("x"), &BinExpr{OpTimes, Variable("y"), &Literal{2}}},
+ },
+ {
+ expr: "a > b",
+ want: &BinExpr{OpGreaterThan, Variable("a"), Variable("b")},
+ },
+ {
+ expr: "a >= b",
+ want: &BinExpr{OpGreaterOrEqual, Variable("a"), Variable("b")},
+ },
+ {
+ expr: "a < b",
+ want: &BinExpr{OpLessThan, Variable("a"), Variable("b")},
+ },
+ {
+ expr: "a <= b",
+ want: &BinExpr{OpLessOrEqual, Variable("a"), Variable("b")},
+ },
+ {
+ expr: "(v * 2) / 3",
+ want: &BinExpr{OpDiv, &BinExpr{OpTimes, Variable("v"), &Literal{2}}, &Literal{3}},
+ },
+ {
+ expr: "Int32x4",
+ want: makeVectorL(MakeBasic(&Literal{"int"}, &Literal{32}), &Literal{FixedWidth(4)}),
+ },
+ {
+ expr: "Float64s",
+ want: MakeVector(MakeBasic(&Literal{"float"}, &Literal{64}), &Literal{UnitWidth()}),
+ },
+ {
+ expr: "{B}{N}x{L}",
+ want: makeVectorL(MakeBasic(Variable("B"), Variable("N")), Variable("L")),
+ },
+ {
+ expr: "{B}{N}w{W}",
+ want: MakeVector(MakeBasic(Variable("B"), Variable("N")), Variable("W")),
+ },
+ {
+ expr: "{xB}{xN*2}x{xL/2}",
+ want: makeVectorL(
+ MakeBasic(Variable("xB"), &BinExpr{OpTimes, Variable("xN"), &Literal{2}}),
+ &BinExpr{OpDiv, Variable("xL"), &Literal{2}},
+ ),
+ },
+ }
+
+ for _, tc := range tests {
+ t.Run(tc.expr, func(t *testing.T) {
+ got, err := ParseExpr(tc.expr)
+ if err != nil {
+ t.Fatalf("ParseExpr(%q) failed: %v", tc.expr, err)
+ }
+ if !reflect.DeepEqual(got, tc.want) {
+ t.Errorf("ParseExpr(%q) = %+v; want %+v", tc.expr, got, tc.want)
+ }
+ })
+ }
+}
+
+func TestParseExprErrors(t *testing.T) {
+ tests := []struct {
+ expr string
+ wantErr string
+ }{
+ {
+ expr: "",
+ wantErr: "unexpected end",
+ },
+ {
+ expr: "12 34",
+ wantErr: "unexpected trailing characters",
+ },
+ {
+ expr: "(12",
+ wantErr: "expected ')'",
+ },
+ {
+ expr: "Int32x",
+ wantErr: "expected number",
+ },
+ {
+ expr: "Int32w",
+ wantErr: "expected number",
+ },
+ {
+ expr: "{B",
+ wantErr: "expected '}' in symbolic shape",
+ },
+ {
+ expr: "Int32x{}",
+ wantErr: "unexpected character '}'",
+ },
+ }
+
+ for _, tc := range tests {
+ t.Run(tc.expr, func(t *testing.T) {
+ _, err := ParseExpr(tc.expr)
+ if err == nil {
+ t.Fatalf("ParseExpr(%q) succeeded; want error containing %q", tc.expr, tc.wantErr)
+ }
+ if gotErr := err.Error(); !strings.Contains(gotErr, tc.wantErr) {
+ t.Errorf("ParseExpr(%q) returned error %q; want error containing %q", tc.expr, gotErr, tc.wantErr)
+ }
+ })
+ }
+}
diff --git a/src/simd/archsimd/_gen/specgen/specexpr/shape.go b/src/simd/archsimd/_gen/specgen/specexpr/shape.go
new file mode 100644
index 0000000..f58f18c1
--- /dev/null
+++ b/src/simd/archsimd/_gen/specgen/specexpr/shape.go
@@ -0,0 +1,266 @@
+// Copyright 2026 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package specexpr
+
+import (
+ "fmt"
+ "strings"
+)
+
+// MinWidth is the minimum vector width, in bits.
+const MinWidth = FixedWidth(128)
+
+type Type interface {
+ isType()
+ String() string
+}
+
+type Basic struct {
+ Base string // "int", "uint", "float", "mask", etc
+ Bits int // 0 if unsized
+}
+
+var MakeBasic = MakeFunc2("Basic", func(base string, bits int) (any, error) {
+ return Basic{Base: base, Bits: bits}, nil
+})
+
+func (t Basic) isType() {}
+func (t Basic) String() string {
+ if t.Bits == 0 {
+ return t.Base
+ }
+ return fmt.Sprintf("%s%d", t.Base, t.Bits)
+}
+
+type Vector struct {
+ Elem Basic // Must have Bits != 0
+ Width Width // Bit width
+}
+
+var MakeVector = MakeFunc2("VectorW", func(elem Basic, w Width) (any, error) {
+ if !w.ValidWidth() {
+ return nil, fmt.Errorf("invalid width %s", w)
+ }
+ return Vector{Elem: elem, Width: w}, nil
+})
+
+var makeVectorL = MakeFunc2("VectorL", func(elem Basic, l Width) (any, error) {
+ w := l.Mul(elem.Bits)
+ if w2, ok := w.(FixedWidth); ok {
+ // Perform width rounding
+ w = max(MinWidth, w2)
+ }
+ if !w.ValidWidth() {
+ return nil, fmt.Errorf("invalid width %s", w)
+ }
+ return Vector{Elem: elem, Width: w}, nil
+})
+
+func (t Vector) isType() {}
+func (t Vector) String() string {
+ var buf strings.Builder
+ if t.Elem.Base == "" {
+ buf.WriteString("<bad Elem>")
+ } else {
+ buf.WriteString(strings.ToTitle(t.Elem.Base[:1]))
+ buf.WriteString(t.Elem.Base[1:])
+ fmt.Fprintf(&buf, "%d", t.Elem.Bits)
+ }
+ if t.Scalable() {
+ buf.WriteString("s")
+ } else {
+ l, err := t.Width.DivInt(t.Elem.Bits)
+ if err == nil {
+ fmt.Fprintf(&buf, "x%d", l)
+ } else {
+ // Bad width, but we can print it anyway
+ fmt.Fprintf(&buf, "w%s", t.Width)
+ }
+ }
+ return buf.String()
+}
+func (t Vector) Scalable() bool {
+ sw, ok := t.Width.(ScalableWidth)
+ return ok && sw.ValidWidth()
+}
+
+type Pointer struct {
+ Elem Type
+}
+
+var MakePointer = MakeFunc1("Pointer", func(elem Type) (any, error) {
+ return &Pointer{elem}, nil
+})
+
+func (t Pointer) isType() {}
+func (t Pointer) String() string {
+ return "*" + t.Elem.String()
+}
+
+type Array struct {
+ Elem Type
+ Len int
+}
+
+var MakeArray = MakeFunc2("Array", func(elem Type, len int) (any, error) {
+ return &Array{elem, len}, nil
+})
+
+func (t Array) isType() {}
+func (t Array) String() string {
+ return fmt.Sprintf("[%d]%s", t.Len, t.Elem)
+}
+
+type Slice struct {
+ Elem Type
+}
+
+var MakeSlice = MakeFunc1("Slice", func(elem Type) (any, error) {
+ return &Slice{elem}, nil
+})
+
+func (t Slice) isType() {}
+func (t Slice) String() string {
+ return "[]" + t.Elem.String()
+}
+
+// // A Shape describes the Shape of a vector, mask, or scalar type.
+// type Shape struct {
+// // Base is the base element kind. One of "float", "int", "uint", or "mask".
+// Base string
+
+// // N is the element bit width, or 0 for an unsized basic type (in which case
+// // L must be 1)
+// N int
+
+// // L is the lane count, or 1 if this is a scalar, or -1 if this is a scalable
+// // vector.
+// L int
+// }
+
+// func MustParseShape(str string) Shape {
+// s, err := ParseShape(str)
+// if err != nil {
+// panic(err)
+// }
+// return s
+// }
+
+// var shapeRe = regexp.MustCompile(`^([A-Za-z][a-z]*)([0-9]+)?(?:(s)|x([0-9]+)|w([0-9])+)?$`)
+
+// // ParseShape parses a shape. This must be in one of the following forms:
+// //
+// // - BaseNxL: A fixed vector with L lanes. E.g., Int32x4
+// // - BaseNs: A scalable vector. E.g., Float32s
+// // - BaseNwW: A fixed vector of width W. E.g., Int32w128 (same as Int32x4)
+// // - MaskNxL, MaskNs, or MaskNwW: Similar, but describes a mask.
+// // - baseN: A scalar. E.g., uint8
+// // - base: An unsized scalar. E.g., int
+// func ParseShape(str string) (Shape, error) {
+// m := shapeRe.FindStringSubmatch(str)
+// if m == nil {
+// return Shape{}, fmt.Errorf("malformed shape %q", str)
+// }
+// var err error
+// s := Shape{Base: strings.ToLower(m[1])}
+// if m[2] == "" {
+// // Unsized scalar
+// if m[3] == "" && m[4] == "" && m[5] == "" {
+// s.L = 1
+// return s, nil
+// }
+// return Shape{}, fmt.Errorf("malformed shape %q: missing element width", str)
+// }
+// if s.N, err = strconv.Atoi(m[2]); err != nil {
+// return Shape{}, fmt.Errorf("malformed shape %q: %s", str, err)
+// }
+// if m[3] != "" {
+// // Scalable
+// s.L = -1
+// } else if m[4] != "" {
+// // Lane spec
+// if s.L, err = strconv.Atoi(m[4]); err != nil {
+// return Shape{}, fmt.Errorf("malformed shape %q: %s", str, err)
+// }
+// } else if m[5] != "" {
+// // Width spec
+// var w int
+// if w, err = strconv.Atoi(m[5]); err != nil {
+// return Shape{}, fmt.Errorf("malformed shape %q: %s", str, err)
+// }
+// if w%s.N != 0 {
+// return Shape{}, fmt.Errorf("width not a multiple of element size in %q", str)
+// }
+// s.L = w / s.N
+// } else {
+// // Scalar
+// s.L = 1
+// }
+// return s, nil
+// }
+
+// func (s Shape) Scalable() bool {
+// return s.L == -1
+// }
+
+// func (s Shape) Bind(name VarName, b interface{ Bind(VarName, any) }) {
+// b.Bind(name, s)
+// b.Bind(name+"B", s.Base)
+// if s.N == 0 {
+// return
+// }
+// b.Bind(name+"N", s.N)
+// elem := s
+// elem.L = 1
+// b.Bind(name+"E", elem)
+// if s.L == 1 {
+// return
+// }
+// if s.Scalable() {
+// b.Bind(name+"L", mkWidth(1, s.N))
+// b.Bind(name+"W", mkWidth(1, 1))
+// } else {
+// b.Bind(name+"L", s.L)
+// b.Bind(name+"W", s.N*s.L)
+// }
+// }
+
+// func (s Shape) String() string {
+// if s == (Shape{}) {
+// return "Shape{}"
+// }
+// if s.Base != "" {
+// if s.L == 1 {
+// // Scalar
+// if s.N == 0 {
+// // Unsized basic type
+// return s.Base
+// }
+// return fmt.Sprintf("%s%d", s.Base, s.N)
+// } else if s.L > 1 || s.Scalable() {
+// // Vector
+// var buf strings.Builder
+// buf.WriteString(strings.ToTitle(s.Base[:1]))
+// buf.WriteString(s.Base[1:])
+// fmt.Fprintf(&buf, "%d", s.N)
+// if s.Scalable() {
+// buf.WriteString("s")
+// } else {
+// fmt.Fprintf(&buf, "x%d", s.L)
+// }
+// return buf.String()
+// }
+// }
+// return fmt.Sprintf("Shape{%v,%v,%v}", s.Base, s.N, s.L)
+// }
+
+// func (s Shape) Valid(a *Arch) bool {
+// // Check for a shape compatible with s.
+// w := s.L * s.N
+// if w > a.MaxWidth || (s.Scalable() && !a.Scalable) {
+// return false
+// }
+// return slices.Contains(a.Shapes, s)
+// }
diff --git a/src/simd/archsimd/_gen/specgen/specexpr/solver.go b/src/simd/archsimd/_gen/specgen/specexpr/solver.go
new file mode 100644
index 0000000..e299571
--- /dev/null
+++ b/src/simd/archsimd/_gen/specgen/specexpr/solver.go
@@ -0,0 +1,516 @@
+// Copyright 2026 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+// Package specexpr manipulates symbolic constraints on vector shapes.
+//
+// # Shapes
+//
+// A vector shape consists of a base type B (e.g., int, float), element width N
+// (8, 16, 32, or 64), and a vector width W (128, 256, 512, or scalable). It
+// also has a lane count L, which is the vector width / element width. These are
+// written like "Int32x4" or "Int32w128" or, for a scalable vector, "Int32s"
+// Masks are represented as vectors with a base type of "mask", e.g.,
+// "Mask32x4".
+//
+// Scalar shapes consist only of a base type and an element width, e.g.,
+// "uint32".
+//
+// # Expressions
+//
+// Constrains are written as boolean expressions over shapes and a few basic
+// types.
+//
+// The primary expressions are:
+//
+// - Variable ([a-zA-Z]+), such as x or xL
+//
+// - Integers ([0-9]+)
+//
+// - Shapes, written in the form given above, but where each component can be
+// written as a bracketed expression, such as "Int32x{z/2}".
+//
+// These can be combined with operators * or /, or comparison operators =, >, <,
+// >=, <=. Arithmetic operators bind more tightly than comparison operators.
+//
+// # Example
+//
+// Consider a DotProductPairs function that takes two vectors x and y that have
+// the same shape and produces a vector z that has the same base type as x and
+// y, but has half as many elements, each of double the width. This can be
+// expressed as:
+//
+// y=x
+// z={xB}{xN*2}x{xL/2}
+//
+// # Width rounding
+//
+// The minimum vector width is 128 bits. Sometimes, operations would naturally
+// produce a width smaller than this, so hardware simply pads the vector out to
+// 128 bits. Shapes implement this behavior. For example, consider a "convert to
+// float32 operation" with constraints
+//
+// z=Float32x{xL}
+//
+// If x is Float64x2, then z would naturally be Float32x2, but since this is
+// only 64 bits, the shape is "rounded" up to Float32x4.
+//
+// # Limitations
+//
+// The solver is intentionally simple. See [Solver] for a description of its
+// limitations. If you run up against its limitations, you're probably being too
+// clever.
+package specexpr
+
+import (
+ "cmp"
+ "container/heap"
+ "fmt"
+ "io"
+ "iter"
+ "log"
+ "maps"
+ "slices"
+ "strings"
+)
+
+// A Solver solves a set of constraints.
+//
+// This is a simple monotonic solver. It looks for a single order in which it
+// can resolve all constraints, assertions of the form "var=expr" are treated as
+// candidates for resolving the value of "var", and anything else is treated as
+// a boolean check. Variables that appear only on the right hand side of
+// assignments are "independent" and it will enumerate all possible assignments
+// of these variables. It never tries to invert any formulas and refuses to
+// solve a system with cycles. This is intentional to keep this solver fast: if
+// your formulas are cyclic, you're doing something too complicated.
+type Solver struct {
+ vars map[Variable][]any
+ asserts []Expr
+ tracer *tracer
+}
+
+// SetTrace enables emitting a solver trace to w.
+func (s *Solver) SetTrace(w io.Writer) {
+ if w == nil {
+ s.tracer = nil
+ } else {
+ s.tracer = &tracer{w: w}
+ }
+}
+
+// Declare declares a variable and its domain.
+func (s *Solver) Declare(v Variable, domain []any) {
+ if s.vars == nil {
+ s.vars = make(map[Variable][]any)
+ }
+ if _, ok := s.vars[v]; ok {
+ panic(v + " redeclared")
+ }
+ s.vars[v] = domain
+}
+
+// Assign is a convenience for asserting that v=val.
+func (s *Solver) Assign(v Variable, val Expr) Variable {
+ s.Assert(&BinExpr{Op: OpEqual, X: v, Y: val})
+ return v
+}
+
+// Assert asserts a boolean condition must be true.
+func (s *Solver) Assert(cond Expr) {
+ s.asserts = append(s.asserts, cond)
+}
+
+func (s *Solver) Fprint(w io.Writer) {
+ for _, v := range slices.Sorted(maps.Keys(s.vars)) {
+ fmt.Fprintf(w, "%s in %v\n", v, s.vars[v])
+ }
+ for _, expr := range s.asserts {
+ fmt.Fprintf(w, "%s\n", expr)
+ }
+}
+
+// Bindings is a set of variable values.
+type Bindings struct {
+ varNames map[Variable]int // Shared between all solutions
+ vals []any
+}
+
+// Get returns the value of v if resolved, or nil.
+func (b *Bindings) Get(v Variable) any {
+ vid, ok := b.varNames[v]
+ if !ok || vid >= len(b.vals) {
+ return nil
+ }
+ return b.vals[vid]
+}
+
+// All yields all variable bindings.
+func (b *Bindings) All() iter.Seq2[Variable, any] {
+ return func(yield func(Variable, any) bool) {
+ for _, varName := range slices.Sorted(maps.Keys(b.varNames)) {
+ vid := b.varNames[varName]
+ if vid < len(b.vals) && !yield(varName, b.vals[vid]) {
+ return
+ }
+ }
+ }
+}
+
+func (b *Bindings) String() string {
+ var buf strings.Builder
+ buf.WriteByte('{')
+ for v, val := range b.All() {
+ if buf.Len() > 1 {
+ buf.WriteByte(' ')
+ }
+ fmt.Fprintf(&buf, "%s=%v", v, val)
+ }
+ buf.WriteByte('}')
+ return buf.String()
+}
+
+// Solve yields all satisfying assignments of the variables in s.
+func (s *Solver) Solve() iter.Seq2[*Bindings, error] {
+ steps, err := s.topoSort()
+ if err != nil {
+ return func(yield func(*Bindings, error) bool) {
+ yield(nil, err)
+ }
+ }
+
+ // Assign variable indexes
+ varIDs := make(map[Variable]int)
+ for _, step := range steps {
+ if step.kind == solverStepCheck {
+ continue
+ }
+ if _, ok := varIDs[step.bind]; ok {
+ panic(fmt.Sprintf("variable %s resolved multiple times by solver sequence", step.bind))
+ }
+ varIDs[step.bind] = len(varIDs)
+ }
+
+ // If there are no solutions, then we report any evaluation errors. As soon
+ // as we yield anything, we set this to nil to indicate that.
+ errors := make(map[string]bool)
+ addErr := func(err error) {
+ if errors != nil {
+ errors[err.Error()] = true
+ }
+ }
+
+ // Walk solver steps
+ b := Bindings{
+ varNames: varIDs,
+ vals: make([]any, 0, len(varIDs)),
+ }
+ pop := func() {
+ b.vals = b.vals[:len(b.vals)-1]
+ }
+ var visit func(steps []*solverStep, yield func(*Bindings, error) bool) bool
+ visit = func(steps []*solverStep, yield func(*Bindings, error) bool) bool {
+ if len(steps) == 0 {
+ errors = nil // Discard any errors
+ // Snapshot Bindings.
+ s.tracer.sat()
+ return yield(&Bindings{varNames: b.varNames, vals: slices.Clone(b.vals)}, nil)
+ }
+ step := steps[0]
+ steps = steps[1:]
+ switch step.kind {
+ case solverStepAssign:
+ val, err := step.expr.(*BinExpr).Y.Eval(&b)
+ if err == nil {
+ if domain, ok := s.vars[step.bind]; ok && !slices.Contains(domain, val) {
+ err = fmt.Errorf("cannot assign %s=%v: not in domain", step.bind, val)
+ }
+ }
+ s.tracer.assign(step.expr, step.bind, val, err)
+ if err != nil {
+ addErr(err)
+ return true
+ }
+ b.vals = append(b.vals, val)
+ defer pop()
+ return visit(steps, yield)
+
+ case solverStepCheck:
+ val, err := step.expr.Eval(&b)
+ s.tracer.check(step.expr, val, err)
+ if err != nil {
+ addErr(err)
+ return true
+ }
+ vBool, ok := val.(bool)
+ if !ok {
+ panic(fmt.Errorf("%s has type %T, expected bool", step.expr, val))
+ }
+ if vBool {
+ return visit(steps, yield)
+ }
+ return true
+
+ case solverStepIndep:
+ i := len(b.vals)
+ b.vals = append(b.vals, nil)
+ defer pop()
+ for _, val := range s.vars[step.bind] {
+ b.vals[i] = val
+ s.tracer.enter(step.bind, val)
+ if !visit(steps, yield) {
+ return false
+ }
+ s.tracer.exit()
+ }
+ return true
+ }
+ panic("bad step kind")
+ }
+ return func(yield func(*Bindings, error) bool) {
+ if visit(steps, yield) {
+ if len(errors) > 0 {
+ err := fmt.Errorf("%s", strings.Join(slices.Sorted(maps.Keys(errors)), "\n"))
+ yield(nil, err)
+ }
+ }
+ }
+}
+
+type solverStep struct {
+ kind solverStepKind
+ id int
+ expr Expr
+ bind Variable // Variable to bind for solverStepAssign or solverStepIndep
+ hid int // heap index
+}
+
+type solverStepKind int
+
+const (
+ solverStepCheck solverStepKind = iota
+ solverStepAssign
+ solverStepIndep
+)
+
+func (s *solverStep) Compare(t *solverStep) int {
+ // Put assertions before independent variables because they may cut off paths
+ // before we have to enumerate values.
+ if s.kind != t.kind {
+ return cmp.Compare(s.kind, t.kind)
+ }
+ switch s.kind {
+ case solverStepCheck, solverStepAssign:
+ return cmp.Compare(s.id, t.id)
+ case solverStepIndep:
+ return cmp.Compare(s.bind, t.bind)
+ }
+ panic("bad solverStep kind")
+}
+
+type solverHeap []*solverStep
+
+func (sh solverHeap) Len() int { return len(sh) }
+
+func (sh solverHeap) Less(i, j int) bool {
+ return sh[i].Compare(sh[j]) < 0
+}
+
+func (sh solverHeap) Swap(i, j int) {
+ sh[i], sh[j] = sh[j], sh[i]
+ sh[i].hid, sh[j].hid = i, j
+}
+
+func (sh *solverHeap) Push(x any) {
+ item := x.(*solverStep)
+ item.hid = len(*sh)
+ *sh = append(*sh, item)
+}
+
+func (sh *solverHeap) Pop() any {
+ old := *sh
+ n := len(old)
+ item := old[n-1]
+ old[n-1] = nil
+ item.hid = -1
+ *sh = old[0 : n-1]
+ return item
+}
+
+func (s *Solver) topoSort() (order []*solverStep, err error) {
+ // This is a topo-sort with a few tricks: an assertion can be evaluated once
+ // all of its input variables are available, BUT a variable value can be
+ // resolved by potentially more than one assertion. Since we have a mix of
+ // "AND" and "OR" dependencies, we use a wavefront-style topo sort where we
+ // track the number of unresolved input variables to each assertion and
+ // whenever we resolve one of these inputs for the first time, we decrement
+ // that count. Once it reaches zero, that assertion is let out of the gate.
+ //
+ // Also, we bias toward steps that are more likely to cut off a path and less
+ // likely to cause more fan-out.
+
+ var queue solverHeap
+ defs := make(map[Variable][]*solverStep)
+ uses := make(map[Variable]map[*solverStep]bool)
+ remaining := make(map[*solverStep]int)
+
+ isVarAssign := func(e Expr) (Variable, Expr, bool) {
+ switch e := e.(type) {
+ case *BinExpr:
+ if e.Op == OpEqual {
+ switch x := e.X.(type) {
+ case Variable:
+ return x, e.Y, true
+ }
+ }
+ }
+ return "", nil, false
+ }
+
+ for i, assert := range s.asserts {
+ var rhs Expr
+ // Wrap the assertion in a step, assigning an ID.
+ var step *solverStep
+ if def, val, ok := isVarAssign(assert); ok {
+ if def == val {
+ // x=x assertion. It's always true and will muck up the sorting,
+ // so throw it out.
+ continue
+ }
+ // Variable assignment
+ step = &solverStep{kind: solverStepAssign, id: i, expr: assert, hid: -1, bind: def}
+ // Record variable definition.
+ defs[def] = append(defs[def], step)
+ rhs = val
+ } else {
+ // Boolean check
+ step = &solverStep{kind: solverStepCheck, id: i, expr: assert, hid: -1}
+ rhs = assert
+ }
+
+ // Record variables this step depends on.
+ deps := 0
+ for use := range exprVars(rhs) {
+ if uses[use] == nil {
+ uses[use] = make(map[*solverStep]bool)
+ }
+ if !uses[use][step] {
+ uses[use][step] = true
+ deps++
+ }
+ }
+ if deps == 0 {
+ // Already solvable, enqueue it.
+ step.hid = len(queue)
+ queue = append(queue, step)
+ } else {
+ remaining[step] = deps
+ }
+ }
+
+ // Find the independent variables and also seed the frontier with them.
+ for v := range uses {
+ if defs[v] == nil {
+ if _, ok := s.vars[v]; !ok {
+ return nil, fmt.Errorf("no domain for independent variable %q", v)
+ }
+ queue = append(queue, &solverStep{kind: solverStepIndep, bind: v, hid: -1})
+ }
+ }
+ // Any variables that are declared but not referenced are also independent.
+ for v := range s.vars {
+ if uses[v] == nil && defs[v] == nil {
+ queue = append(queue, &solverStep{kind: solverStepIndep, bind: v, hid: -1})
+ }
+ }
+
+ // Drive the frontier
+ heap.Init(&queue)
+ for len(queue) > 0 {
+ step := queue[0]
+ heap.Pop(&queue)
+ step.hid = -1
+
+ order = append(order, step)
+
+ if step.kind == solverStepCheck {
+ continue
+ }
+
+ // This step resolved variable v.
+ v := step.bind
+
+ // Demote any other assignments of this variable to checks.
+ for _, def := range defs[v] {
+ if def != step {
+ def.kind = solverStepCheck
+ // Adjust heap
+ if def.hid != -1 {
+ heap.Fix(&queue, def.hid)
+ }
+ }
+ }
+ delete(defs, v)
+
+ // Check steps that depend on v.
+ for use := range uses[v] {
+ remaining[use]--
+ if remaining[use] == 0 {
+ // All variables used by this step are now resolved. Add it to the
+ // queue.
+ heap.Push(&queue, use)
+ delete(remaining, use)
+ }
+ }
+ }
+
+ if len(remaining) > 0 {
+ return nil, reportCycle(defs, remaining)
+ }
+ return order, nil
+}
+
+func reportCycle(defs map[Variable][]*solverStep, remaining map[*solverStep]int) error {
+ // There was a cycle. There could be more than one cycle, but report one.
+ // Start with the "minimum" remaining step for stability.
+ var step *solverStep
+ for rem := range remaining {
+ if rem.kind == solverStepAssign && (step == nil || rem.Compare(step) < 0) {
+ step = rem
+ }
+ }
+ // Walk forward through the graph, filtered to unresolved nodes.
+ var cycle []Expr
+ have := make(map[*solverStep]int)
+ var visit func(step *solverStep) error
+ visit = func(step *solverStep) error {
+ if step.kind != solverStepAssign || remaining[step] == 0 {
+ return nil
+ }
+ if i, ok := have[step]; ok {
+ // Found the cycle
+ return fmt.Errorf("cyclic requirements: %v", cycle[i:])
+ }
+ have[step] = len(cycle)
+ cycle = append(cycle, step.expr)
+ for v := range exprVars(step.expr.(*BinExpr).Y) {
+ for _, def := range defs[v] {
+ if err := visit(def); err != nil {
+ return err
+ }
+ }
+ }
+ delete(have, step)
+ cycle = cycle[:len(cycle)-1]
+ return nil
+ }
+ err := visit(step)
+ if err == nil {
+ log.Printf("remaining:")
+ for rem, count := range remaining {
+ log.Printf(" %v (%d)", rem, count)
+ }
+ log.Fatal("unresolved assertions, but failed to find a cycle")
+ }
+ return err
+}
diff --git a/src/simd/archsimd/_gen/specgen/specexpr/solver_test.go b/src/simd/archsimd/_gen/specgen/specexpr/solver_test.go
new file mode 100644
index 0000000..140cffb
--- /dev/null
+++ b/src/simd/archsimd/_gen/specgen/specexpr/solver_test.go
@@ -0,0 +1,410 @@
+// Copyright 2026 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package specexpr
+
+import (
+ "fmt"
+ "maps"
+ "slices"
+ "strings"
+ "testing"
+)
+
+func TestSolver(t *testing.T) {
+ t.Run("constant assignment", func(t *testing.T) {
+ s := &Solver{}
+ v1 := Variable("v1")
+ s.Assign(v1, &Literal{10})
+
+ sol := uniqueSolution(t, s)
+ bCheck(t, sol, map[Variable]any{v1: 10})
+ })
+
+ t.Run("simple dependency", func(t *testing.T) {
+ testBinaryOp(t, 10, &BinExpr{
+ Op: OpTimes,
+ X: Variable("v1"),
+ Y: &Literal{2},
+ }, 20)
+ })
+
+ t.Run("division", func(t *testing.T) {
+ testBinaryOp(t, 16, &BinExpr{
+ Op: OpDiv,
+ X: Variable("v1"),
+ Y: &Literal{4},
+ }, 4)
+ })
+
+ t.Run("cycle detection", func(t *testing.T) {
+ s := &Solver{}
+ v1 := Variable("v1")
+ v2 := Variable("v2")
+ s.Assign(v1, Variable(v2))
+ s.Assign(v2, Variable(v1))
+
+ err := solverError(t, s)
+ if !strings.Contains(err.Error(), "cyclic requirements") {
+ t.Fatalf("expected cycle error, got %v", err)
+ }
+ })
+
+ t.Run("multiple assignment conflicting values", func(t *testing.T) {
+ s := &Solver{}
+ v1 := Variable("v1")
+ s.Assign(v1, &Literal{10})
+ s.Assign(v1, &Literal{20})
+
+ err := solverError(t, s)
+ if !strings.Contains(err.Error(), "no solutions") {
+ t.Fatalf("expected no solutions error, got %v", err)
+ }
+ })
+
+ t.Run("multiple assignment same value", func(t *testing.T) {
+ s := &Solver{}
+ v1 := Variable("v1")
+ s.Assign(v1, &Literal{10})
+ s.Assign(v1, &Literal{10})
+
+ sol := uniqueSolution(t, s)
+ bCheck(t, sol, map[Variable]any{v1: 10})
+ })
+
+ t.Run("swidth times int", func(t *testing.T) {
+ s := &Solver{}
+ v1 := Variable("v1")
+ v2 := Variable("v2")
+ s.Assign(v1, &Literal{mkWidth(1, 2)})
+ s.Assign(v2, &BinExpr{
+ Op: OpTimes,
+ X: v1,
+ Y: &Literal{4},
+ })
+
+ sol := uniqueSolution(t, s)
+ bCheck(t, sol, map[Variable]any{
+ v1: mkWidth(1, 2),
+ v2: mkWidth(2, 1),
+ })
+ })
+
+ t.Run("int times swidth", func(t *testing.T) {
+ s := &Solver{}
+ v1 := Variable("v1")
+ v2 := Variable("v2")
+ s.Assign(v1, &Literal{mkWidth(1, 2)})
+ s.Assign(v2, &BinExpr{
+ Op: OpTimes,
+ X: &Literal{4},
+ Y: v1,
+ })
+
+ sol := uniqueSolution(t, s)
+ bCheck(t, sol, map[Variable]any{
+ v1: mkWidth(1, 2),
+ v2: mkWidth(2, 1),
+ })
+ })
+
+ t.Run("swidth div int", func(t *testing.T) {
+ s := &Solver{}
+ v1 := Variable("v1")
+ v2 := Variable("v2")
+ s.Assign(v1, &Literal{mkWidth(1, 2)})
+ s.Assign(v2, &BinExpr{
+ Op: OpDiv,
+ X: v1,
+ Y: &Literal{2},
+ })
+
+ sol := uniqueSolution(t, s)
+ bCheck(t, sol, map[Variable]any{
+ v1: mkWidth(1, 2),
+ v2: mkWidth(1, 4),
+ })
+ })
+}
+
+func testBinaryOp(t *testing.T, v1Val int, v2Expr Expr, expectedV2Val any) {
+ t.Helper()
+ s := &Solver{}
+ v1 := Variable("v1")
+ v2 := Variable("v2")
+ s.Assign(v1, &Literal{v1Val})
+ s.Assign(v2, v2Expr)
+
+ sol := uniqueSolution(t, s)
+ bCheck(t, sol, map[Variable]any{v1: v1Val, v2: expectedV2Val})
+}
+
+func TestComparisons(t *testing.T) {
+ t.Run("greater than", func(t *testing.T) {
+ s := &Solver{}
+ v1 := Variable("v1")
+ v2 := Variable("v2")
+ s.Assign(v1, &Literal{20})
+ s.Assign(v2, &Literal{10})
+
+ // Add comparison v1 > v2 and assert it must be true
+ s.Assert(&BinExpr{Op: OpGreaterThan, X: v1, Y: v2})
+
+ uniqueSolution(t, s)
+ })
+
+ t.Run("less than", func(t *testing.T) {
+ s := &Solver{}
+ v1 := Variable("v1")
+ v2 := Variable("v2")
+ s.Assign(v1, &Literal{10})
+ s.Assign(v2, &Literal{20})
+
+ s.Assert(&BinExpr{Op: OpLessThan, X: v1, Y: v2})
+
+ uniqueSolution(t, s)
+ })
+}
+
+func TestSolveShape(t *testing.T) {
+ t.Run("scalar Int32", func(t *testing.T) {
+ s := &Solver{}
+ x := mustParseExpr(t, "Int32")
+ s.Assign("x", x)
+
+ sol := uniqueSolution(t, s)
+ bCheck(t, sol, map[Variable]any{
+ "x": Basic{"int", 32},
+ })
+ })
+
+ t.Run("vector Int32x4", func(t *testing.T) {
+ s := &Solver{}
+ s.Assign("x", mustParseExpr(t, "Int32x4"))
+
+ sol := uniqueSolution(t, s)
+ bCheck(t, sol, map[Variable]any{
+ "x": Vector{Basic{"int", 32}, FixedWidth(128)},
+ })
+ })
+
+ t.Run("scalar symbolic {xB}{xN}", func(t *testing.T) {
+ s := &Solver{}
+ s.Assign("x", mustParseExpr(t, "{xB}{xN}"))
+ s.Assign("xB", &Literal{"int"})
+ s.Assign("xN", &Literal{32})
+
+ sol := uniqueSolution(t, s)
+ bCheck(t, sol, map[Variable]any{
+ "x": Basic{"int", 32},
+ "xB": "int",
+ "xN": 32,
+ })
+ })
+
+ vectorElem := MakeField[Vector]("Elem")
+ basicBase := MakeField[Basic]("Base")
+ basicBits := MakeField[Basic]("Bits")
+ vectorWidth := MakeField[Vector]("Width")
+ assignVector := func(s *Solver, v Variable, e Expr) {
+ x := s.Assign(v, e)
+ s.Assign(v+"B", basicBase.Apply(vectorElem.Apply(x)))
+ xN := s.Assign(v+"N", basicBits.Apply(vectorElem.Apply(x)))
+ xW := s.Assign(v+"W", vectorWidth.Apply(x))
+ s.Assign(v+"L", &BinExpr{Op: OpDiv, X: xW, Y: xN})
+ }
+
+ t.Run("derived scalable vector with lane count", func(t *testing.T) {
+ s := &Solver{}
+ assignVector(s, "x", mustParseExpr(t, "Int32s"))
+ s.Assign("y", mustParseExpr(t, "{xB}{xN*2}x{xL/2}"))
+
+ sol := uniqueSolution(t, s)
+ bCheck(t, sol, map[Variable]any{
+ "y": Vector{Basic{"int", 64}, mkWidth(1, 1)},
+ "xW": mkWidth(1, 1),
+ "xL": mkWidth(1, 32),
+ })
+ })
+
+ t.Run("derived scalable vector with width", func(t *testing.T) {
+ s := &Solver{}
+ assignVector(s, "x", mustParseExpr(t, "Int32s"))
+ s.Assign("y", mustParseExpr(t, "{xB}{xN*2}w{xW}"))
+
+ sol := uniqueSolution(t, s)
+ bCheck(t, sol, map[Variable]any{
+ "y": Vector{Basic{"int", 64}, mkWidth(1, 1)},
+ "xW": mkWidth(1, 1),
+ })
+ })
+
+ t.Run("width rounding", func(t *testing.T) {
+ s := &Solver{}
+ assignVector(s, "x", mustParseExpr(t, "Int64x2"))
+ s.Assign("y", mustParseExpr(t, "{xB}{xN/2}x{xL}"))
+
+ sol := uniqueSolution(t, s)
+ bCheck(t, sol, map[Variable]any{
+ "y": Vector{Basic{"int", 32}, FixedWidth(128)},
+ })
+ })
+
+ t.Run("domain limits", func(t *testing.T) {
+ s := &Solver{}
+ s.Declare("x", []any{1, 2})
+ s.Declare("y", []any{1, 2})
+ s.Assign("y", mustParseExpr(t, "x*2"))
+
+ sol := uniqueSolution(t, s)
+ bCheck(t, sol, map[Variable]any{
+ "x": 1, "y": 2,
+ })
+ })
+
+ t.Run("non-scalable width", func(t *testing.T) {
+ s := &Solver{}
+ assignVector(s, "x", mustParseExpr(t, "Int32s"))
+ s.Assign("y", mustParseExpr(t, "Int16x{xL}"))
+
+ err := solverError(t, s)
+ if !strings.Contains(err.Error(), "invalid width") {
+ t.Fatalf("expected invalid width error, got: %v", err)
+ }
+ })
+}
+
+func TestEnumerator(t *testing.T) {
+ t.Run("simple enumeration", func(t *testing.T) {
+ s := &Solver{}
+ v1 := Variable("v1")
+ v2 := Variable("v2")
+
+ s.Declare(v1, []any{1, 2, 3, 4})
+
+ // Assert v2 = v1 * 2
+ s.Assign(v2, &BinExpr{Op: OpTimes, X: v1, Y: &Literal{2}})
+
+ sols := allSolutions(s)
+
+ if len(sols) != 4 {
+ t.Errorf("expected 4 solutions, got %d", len(sols))
+ }
+
+ // Verify that each solution maps v2 to v1*2
+ for _, sol := range sols {
+ m := bmap(sol)
+ v1Val := m[v1].(int)
+ v2Val := m[v2].(int)
+ if v2Val != v1Val*2 {
+ t.Errorf("solution %v violates v2 = v1*2", m)
+ }
+ }
+ })
+
+ t.Run("comparison constraints enumeration", func(t *testing.T) {
+ s := &Solver{}
+ v1 := Variable("v1")
+ v2 := Variable("v2")
+
+ s.Declare(v1, []any{1, 2, 3, 4, 5})
+
+ // v2 = v1 * 2
+ s.Assign(v2, &BinExpr{Op: OpTimes, X: v1, Y: &Literal{2}})
+
+ // v1 > 2
+ s.Assert(&BinExpr{Op: OpGreaterThan, X: v1, Y: &Literal{2}})
+
+ // v2 < 10
+ s.Assert(&BinExpr{Op: OpLessThan, X: v2, Y: &Literal{10}})
+
+ sols := allSolutions(s)
+
+ // Solutions should be v1=3, v1=4. So 2 solutions
+ if len(sols) != 2 {
+ t.Errorf("expected 2 solutions, got %d", len(sols))
+ }
+ })
+}
+
+func mustParseExpr(t *testing.T, x string) Expr {
+ t.Helper()
+ e, err := ParseExpr(x)
+ if err != nil {
+ t.Fatal(err)
+ }
+ return e
+}
+
+func allSolutions(s *Solver) []*Bindings {
+ var sols []*Bindings
+ for b, err := range s.Solve() {
+ if err != nil {
+ panic(err) // tests expect valid execution when enumerating
+ }
+ sols = append(sols, b)
+ }
+ return sols
+}
+
+func uniqueSolution(t *testing.T, s *Solver) *Bindings {
+ t.Helper()
+ var sols []*Bindings
+ for b, err := range s.Solve() {
+ if err != nil {
+ t.Fatalf("solve failed: %v", err)
+ }
+ sols = append(sols, b)
+ if len(sols) >= 20 {
+ // Stop before we go too deep
+ t.Fatalf("expected exactly one solution, got >= 20")
+ }
+ }
+ if len(sols) != 1 {
+ t.Errorf("expected exactly one solution, got %d", len(sols))
+ for _, sol := range sols {
+ t.Errorf(" %s", sol)
+ }
+ t.FailNow()
+ }
+ return sols[0]
+}
+
+func solverError(t *testing.T, s *Solver) error {
+ t.Helper()
+ for soln, err := range s.Solve() {
+ if err != nil {
+ return err
+ }
+ t.Fatalf("expected solver error, but got solution:\n%s", soln)
+ }
+ return fmt.Errorf("no solutions")
+}
+
+// bmap converts a Bindings to a map.
+func bmap(b *Bindings) map[Variable]any {
+ return maps.Collect(b.All())
+}
+
+// bCheck fails t if got[v] != want[v] for any keys in want.
+func bCheck(t *testing.T, got *Bindings, want map[Variable]any) {
+ t.Helper()
+ var keys []Variable
+ for k := range want {
+ keys = append(keys, k)
+ }
+ slices.Sort(keys)
+
+ var mismatches []string
+ for _, k := range keys {
+ wantVal := want[k]
+ gotVal := got.Get(k)
+ if gotVal != wantVal {
+ mismatches = append(mismatches, fmt.Sprintf(" %s: got %v (%T), want %v (%T)", k, gotVal, gotVal, wantVal, wantVal))
+ }
+ }
+ if len(mismatches) > 0 {
+ t.Fatalf("solution mismatch:\n%s", strings.Join(mismatches, "\n"))
+ }
+}
diff --git a/src/simd/archsimd/_gen/specgen/specexpr/tracer.go b/src/simd/archsimd/_gen/specgen/specexpr/tracer.go
new file mode 100644
index 0000000..19ce3e3
--- /dev/null
+++ b/src/simd/archsimd/_gen/specgen/specexpr/tracer.go
@@ -0,0 +1,64 @@
+// Copyright 2026 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package specexpr
+
+import (
+ "fmt"
+ "io"
+)
+
+type tracer struct {
+ w io.Writer
+ level int
+}
+
+func (t *tracer) assign(expr Expr, v Variable, val any, err error) {
+ if t == nil {
+ return
+ }
+ fmt.Fprintf(t.w, "%*s├ %s => ", t.level, "", expr)
+ if err == nil {
+ fmt.Fprintf(t.w, "%s=%v\n", v, val)
+ } else {
+ fmt.Fprintf(t.w, "%s\n", err)
+ }
+}
+
+func (t *tracer) check(expr Expr, val any, err error) {
+ if t == nil {
+ return
+ }
+ if val == false || err != nil {
+ fmt.Fprintf(t.w, "%*s✘ %s", t.level, "", expr)
+ if err != nil {
+ fmt.Fprintf(t.w, " => %s", err)
+ }
+ fmt.Fprint(t.w, "\n")
+ } else {
+ fmt.Fprintf(t.w, "%*s│ %s\n", t.level, "", expr)
+ }
+}
+
+func (t *tracer) enter(v Variable, val any) {
+ if t == nil {
+ return
+ }
+ fmt.Fprintf(t.w, "%*s↳ %s=%v\n", t.level, "", v, val)
+ t.level += 4
+}
+
+func (t *tracer) exit() {
+ if t == nil {
+ return
+ }
+ t.level -= 4
+}
+
+func (t *tracer) sat() {
+ if t == nil {
+ return
+ }
+ fmt.Fprintf(t.w, "%*s✔ SAT\n", t.level, "")
+}
diff --git a/src/simd/archsimd/_gen/specgen/specexpr/width.go b/src/simd/archsimd/_gen/specgen/specexpr/width.go
new file mode 100644
index 0000000..054b0a0
--- /dev/null
+++ b/src/simd/archsimd/_gen/specgen/specexpr/width.go
@@ -0,0 +1,124 @@
+// Copyright 2026 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package specexpr
+
+import (
+ "cmp"
+ "fmt"
+ "strings"
+)
+
+// Width represents a vector width or lane count.
+type Width interface {
+ // ValidWidth returns true for supported fixed widths (128, 256, 512) and
+ // the scalable width.
+ ValidWidth() bool
+
+ Mul(x int) Width
+ DivInt(x int) (Width, error)
+ Compare(o Width) (int, bool)
+
+ String() string
+}
+
+// FixedWidth is a fixed width, in terms of bits.
+type FixedWidth int
+
+func (w FixedWidth) ValidWidth() bool {
+ switch w {
+ case 128, 256, 512:
+ return true
+ }
+ return false
+}
+func (w FixedWidth) Mul(x int) Width { return w * FixedWidth(x) }
+func (w FixedWidth) DivInt(x int) (Width, error) {
+ if x == 0 {
+ return nil, fmt.Errorf("division by zero")
+ }
+ if w%FixedWidth(x) != 0 {
+ return nil, fmt.Errorf("inexact division %d/%d", w, x)
+ }
+ return w / FixedWidth(x), nil
+}
+func (w FixedWidth) Compare(o Width) (int, bool) {
+ if o, ok := o.(FixedWidth); ok {
+ return cmp.Compare(w, o), true
+ }
+ return 0, false
+}
+func (w FixedWidth) String() string {
+ return fmt.Sprint(int(w))
+}
+
+// UnitWidth returns the ScalableWidth VW.
+func UnitWidth() ScalableWidth {
+ return ScalableWidth{1, 1}
+}
+
+// An ScalableWidth represents a symbolic width relative to a fixed but unknown
+// scalable vector width VW. This is represented as a rational factor
+// VW*num/denom
+type ScalableWidth struct {
+ num, denom int
+}
+
+func gcd(a, b int) int {
+ for b != 0 {
+ a, b = b, a%b
+ }
+ if a < 0 {
+ return -a
+ }
+ return a
+}
+
+func mkWidth(num, denom int) ScalableWidth {
+ if denom == 0 {
+ panic("denominator cannot be zero")
+ }
+ g := gcd(num, denom)
+ num /= g
+ denom /= g
+ if denom < 0 {
+ num = -num
+ denom = -denom
+ }
+ return ScalableWidth{num, denom}
+}
+
+func (w ScalableWidth) ValidWidth() bool {
+ return w == ScalableWidth{1, 1}
+}
+
+func (w ScalableWidth) Mul(x int) Width {
+ return mkWidth(w.num*x, w.denom)
+}
+
+func (w ScalableWidth) DivInt(x int) (Width, error) {
+ if x == 0 {
+ return nil, fmt.Errorf("division by zero")
+ }
+ return mkWidth(w.num, w.denom*x), nil
+}
+
+func (w ScalableWidth) Compare(o Width) (int, bool) {
+ if o, ok := o.(ScalableWidth); ok {
+ return cmp.Compare(w.num*o.denom, o.num*w.denom), true
+ }
+ return 0, false
+}
+
+func (w ScalableWidth) String() string {
+ var buf strings.Builder
+ buf.WriteString("VW")
+ if w.num > 1 {
+ fmt.Fprintf(&buf, "*%d", w.num)
+ }
+ if w.denom > 1 {
+ fmt.Fprintf(&buf, "/%d", w.denom)
+ }
+ return buf.String()
+}
diff --git a/src/simd/archsimd/_gen/specgen/specexpr/width_test.go b/src/simd/archsimd/_gen/specgen/specexpr/width_test.go
new file mode 100644
index 0000000..4085086
--- /dev/null
+++ b/src/simd/archsimd/_gen/specgen/specexpr/width_test.go
@@ -0,0 +1,28 @@
+// Copyright 2026 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package specexpr
+
+import "testing"
+
+func TestMkWidth(t *testing.T) {
+ tests := []struct {
+ num, denom int
+ want ScalableWidth
+ }{
+ {4, 8, ScalableWidth{1, 2}},
+ {3, 9, ScalableWidth{1, 3}},
+ {12, 18, ScalableWidth{2, 3}},
+ {0, 5, ScalableWidth{0, 1}},
+ {-4, 8, ScalableWidth{-1, 2}},
+ {4, -8, ScalableWidth{-1, 2}},
+ {-4, -8, ScalableWidth{1, 2}},
+ }
+ for _, tc := range tests {
+ got := mkWidth(tc.num, tc.denom)
+ if got != tc.want {
+ t.Errorf("mkWidth(%d, %d) = %v; want %v", tc.num, tc.denom, got, tc.want)
+ }
+ }
+}
Change information
Files:
- A src/simd/archsimd/_gen/specgen/specexpr/expr.go
- A src/simd/archsimd/_gen/specgen/specexpr/parse.go
- A src/simd/archsimd/_gen/specgen/specexpr/parse_test.go
- A src/simd/archsimd/_gen/specgen/specexpr/shape.go
- A src/simd/archsimd/_gen/specgen/specexpr/solver.go
- A src/simd/archsimd/_gen/specgen/specexpr/solver_test.go
- A src/simd/archsimd/_gen/specgen/specexpr/tracer.go
- A src/simd/archsimd/_gen/specgen/specexpr/width.go
- A src/simd/archsimd/_gen/specgen/specexpr/width_test.go
Change size: XL
Delta: 9 files changed, 2165 insertions(+), 0 deletions(-)
Related details
Attention is currently required from:
- David Chase
- Junyang Shao
Submit Requirements:
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Austin Clements (Gerrit)
Jul 10, 2026, 1:36:02 PMJul 10
to Austin Clements, goph...@pubsubhelper.golang.org, golang...@luci-project-accounts.iam.gserviceaccount.com, David Chase, Junyang Shao, Cherry Mui, golang-co...@googlegroups.com
Attention needed from David Chase and Junyang Shao
Austin Clements added 1 comment![]( "Open in Gerrit")
Patchset-level comments
File-level comment, Patchset 2 (Latest):
Austin Clements . resolved
Hold off on this one. I found an issue with the handling of ints vs FixedWidths that runs kind of deep.
Related details
Attention is currently required from:
- David Chase
- Junyang Shao
Submit Requirements:
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Austin Clements (Gerrit)
Jul 10, 2026, 2:38:29 PMJul 10
to Austin Clements, goph...@pubsubhelper.golang.org, golang...@luci-project-accounts.iam.gserviceaccount.com, David Chase, Junyang Shao, Cherry Mui, golang-co...@googlegroups.com
Attention needed from David Chase and Junyang Shao
Austin Clements added 1 comment![]( "Open in Gerrit")
Patchset-level comments
Austin Clements . resolved
Hold off on this one. I found an issue with the handling of ints vs FixedWidths that runs kind of deep.
Austin Clements
Fixed.
Related details
Attention is currently required from:
- David Chase
- Junyang Shao
Submit Requirements:
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Austin Clements (Gerrit)
Jul 12, 2026, 9:30:16 PMJul 12
to Austin Clements, goph...@pubsubhelper.golang.org, golang-co...@googlegroups.com
Attention needed from David Chase and Junyang Shao
Austin Clements uploaded new patchset![]( "Open in Gerrit")
Austin Clements uploaded patch set #5 to this change.
Following approvals got outdated and were removed:
- TryBots-Pass: LUCI-TryBot-Result+1 by golang...@luci-project-accounts.iam.gserviceaccount.com
Related details
Attention is currently required from:
- David Chase
- Junyang Shao
Submit Requirements:
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Junyang Shao (Gerrit)
Jul 13, 2026, 1:24:37 PMJul 13
to Austin Clements, goph...@pubsubhelper.golang.org, golang...@luci-project-accounts.iam.gserviceaccount.com, David Chase, Cherry Mui, golang-co...@googlegroups.com
Attention needed from Austin Clements and David Chase
Junyang Shao added 3 comments![]( "Open in Gerrit")
File src/simd/archsimd/_gen/specgen/specexpr/expr.go
Line 88, Patchset 6 (Latest):
panic(fmt.Sprintf("%s: argument is %T, want %T", a[0], name, *new(T)))Junyang Shao . unresolved
Should it be `...name, a[0]...`?
File src/simd/archsimd/_gen/specgen/specexpr/num.go
Line 63, Patchset 6 (Latest):
return mkWidth(int(w)*x.denom, x.num), nilJunyang Shao . unresolved
IIUC, `Div` computes `w/x`.
For scalable `x = VW*num/denom`, it's computed as `w/(VW*num/denom) = (w*denom/num)/VW`
However this value is `(w*denom/num)*VW`. Is this wrong, or I miss anything?
File src/simd/archsimd/_gen/specgen/specexpr/solver.go
Line 21, Patchset 6 (Latest):
// Constrains are written as boolean expressions over shapes and a few basicJunyang Shao . unresolved
Constraints?
Related details
Attention is currently required from:
- Austin Clements
- David Chase
Submit Requirements:
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Junyang Shao (Gerrit)
Jul 14, 2026, 5:08:07 PMJul 14
to Austin Clements, goph...@pubsubhelper.golang.org, golang...@luci-project-accounts.iam.gserviceaccount.com, David Chase, Cherry Mui, golang-co...@googlegroups.com
Attention needed from Austin Clements and David Chase
Junyang Shao added 6 comments![]( "Open in Gerrit")
File src/simd/archsimd/_gen/specgen/specexpr/num_test.go
Line 18, Patchset 6 (Latest):
{-4, 8, ScalableWidth{-1, 2}},
{4, -8, ScalableWidth{-1, 2}},
{-4, -8, ScalableWidth{1, 2}},Junyang Shao . unresolved
I am wondering what does a negative scalable vector width mean?
File src/simd/archsimd/_gen/specgen/specexpr/parse.go
Line 191, Patchset 6 (Latest):
Junyang Shao . unresolved
Should we leave a TODO for arrays, slices and pointers?
File src/simd/archsimd/_gen/specgen/specexpr/shape.go
Line 95, Patchset 6 (Latest):
var MakePointer = MakeFunc1("Pointer", func(elem Type) (any, error) {Junyang Shao . unresolved
`MakePointer`
`MakeArray`
`MakeSlice`.
It looks like they are never used or tested, are they in a future CL?
File src/simd/archsimd/_gen/specgen/specexpr/solver.go
Line 34, Patchset 6 (Latest):
// >=, <=. Arithmetic operators bind more tightly than comparison operators.Junyang Shao . unresolved
Should we just say arithmetic operators has higher precedence than comparison operators?
Line 82, Patchset 6 (Latest):
// a boolean check. Variables that appear only on the right hand side of
// assignments are "independent" and it will enumerate all possible assignments
// of these variables. It never tries to invert any formulas and refuses toJunyang Shao . unresolved
I was confused by the 2 "assignments" in this sentence until I read:
```
// Assign is a convenience for asserting that v=val.
func (s *Solver) Assign(v Variable, val Expr) Variable
```
Should we just say this to make the reading more natural:
```
// ... Variables that appear only on the right hand side of
// an "var=expr" assertion are "independent" and it will enumerate all possible values of these Variables...
```
?
File src/simd/archsimd/_gen/specgen/specexpr/solver_test.go
Line 118, Patchset 6 (Latest):
t.Run("swidth div int", func(t *testing.T) {
s := newSolver(t)
v1 := Variable("v1")
v2 := Variable("v2")
s.Assign(v1, mkWidth(1, 2))
s.Assign(v2, &BinExpr{
Op: OpDiv,
X: v1,
Y: Int(2),
})
sol := uniqueSolution(t, s)
bCheck(t, sol, map[Variable]any{
v1: mkWidth(1, 2),
v2: mkWidth(1, 4),
})
})Junyang Shao . unresolved
Inferred from the test, looks like we shouldn't have int div swidth. Should we remove that case from `func (w Int) Div(x Num) (Num, error)` and panic if we see it?
Junyang Shao (Gerrit)
Jul 14, 2026, 8:43:30 PMJul 14
to Austin Clements, goph...@pubsubhelper.golang.org, golang...@luci-project-accounts.iam.gserviceaccount.com, David Chase, Cherry Mui, golang-co...@googlegroups.com
Attention needed from Austin Clements and David Chase
Junyang Shao added 5 comments![]( "Open in Gerrit")
File src/simd/archsimd/_gen/specgen/specexpr/solver.go
Line 298, Patchset 6 (Latest):
solverStepCheck solverStepKind = iota
solverStepAssign
solverStepIndepJunyang Shao . unresolved
Can we document these?
Line 348, Patchset 6 (Latest):
// This is a topo-sort with a few tricks: an assertion can be evaluated once
// all of its input variables are available, BUT a variable value can be
// resolved by potentially more than one assertion. Since we have a mix of
// "AND" and "OR" dependencies, we use a wavefront-style topo sort where we
// track the number of unresolved input variables to each assertion and
// whenever we resolve one of these inputs for the first time, we decrement
// that count. Once it reaches zero, that assertion is let out of the gate.
//
// Also, we bias toward steps that are more likely to cut off a path and less
// likely to cause more fan-out.Junyang Shao . unresolved
I was initially confused by what are "AND" and "OR" dependencies.
After reading more, I think "AND" dependency means:
```
x=Basic{xB, xN}
```
`x` is resolved when we know both `xB` and `xN`, and it is done by driving the frontiers.
"OR" dependency means:
```
x=Basic{xB, xN}
...
x=y
...
```
We need only one of the assignment to be resolved to know the definition of `x`, and the other assignment can be demoted to a check and resolved.
Should we make that explicit here?
Line 435, Patchset 6 (Latest):
heap.Init(&queue)Junyang Shao . unresolved
Should we mention in the comment that `queue` is the frontier of all variables with 0 dependencies at the current state?
Line 439, Patchset 6 (Latest):
step.hid = -1Junyang Shao . unresolved
It looks like `func (sh *solverHeap) Pop() any` already sets the element's `hid` to -1?
File src/simd/archsimd/_gen/specgen/specexpr/solver_test.go
Line 179, Patchset 6 (Latest):
x := mustParseExpr(t, "Int32")
s.Assign("x", x)Junyang Shao . unresolved
`s.Assign("x", mustParseExpr(t, "Int32"))`?
David Chase (Gerrit)
Jul 20, 2026, 1:49:07 PMJul 20
to Austin Clements, goph...@pubsubhelper.golang.org, golang...@luci-project-accounts.iam.gserviceaccount.com, Junyang Shao, Cherry Mui, golang-co...@googlegroups.com
Attention needed from Austin Clements
David Chase added 1 comment![]( "Open in Gerrit")
File src/simd/archsimd/_gen/specgen/specexpr/solver.go
Line 34, Patchset 6 (Latest):
// >=, <=. Arithmetic operators bind more tightly than comparison operators.Junyang Shao . unresolved
David ChaseShould we just say arithmetic operators has higher precedence than comparison operators?
I think bind-more-tightly might be less ambiguous. ("group more tightly", perhaps).
Related details
Attention is currently required from:
- Austin Clements
Submit Requirements:
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
David Chase (Gerrit)
Jul 20, 2026, 4:37:49 PMJul 20
to Austin Clements, goph...@pubsubhelper.golang.org, golang...@luci-project-accounts.iam.gserviceaccount.com, Junyang Shao, Cherry Mui, golang-co...@googlegroups.com
Attention needed from Austin Clements
David Chase added 5 comments![]( "Open in Gerrit")
File src/simd/archsimd/_gen/specgen/specexpr/expr.go
Line 21, Patchset 6 (Latest):
func exprVars(e Expr) iter.Seq[Variable] {David Chase . unresolved
Internal, and a tool, so a doc comment is perhaps doubly optional, but
// exprVars iterates the Variables in an Expr, `for v := range exprVars(e)`
File src/simd/archsimd/_gen/specgen/specexpr/parse.go
Line 13, Patchset 6 (Latest):
// ParseExpr parses an expression.David Chase . unresolved
my snap reaction is "what expressions?"
I went and looked at doc.go, I'm going to guess this is require expressions, e.g. "z={xB}{xN*2}x{xL/2}".
(But is it the whole thing, or just the RHS of the equality?)
Line 227, Patchset 6 (Latest):
p.fail("expected '}' in symbolic shape")David Chase . unresolved
I know you have tests that depend on this, but it seems like 'after "{<expr>"' is a more concrete description of what was observed.
Line 236, Patchset 6 (Latest):
p.fail("expected shape base name")David Chase . unresolved
again, error message could be more concrete, e.g. "expected shape base name, which should match the regexp [a-zA-Z]+"
File src/simd/archsimd/_gen/specgen/specexpr/solver.go
Line 55, Patchset 6 (Latest):
// If x is Float64x2, then z would naturally be Float32x2, but since this is
// only 64 bits, the shape is "rounded" up to Float32x4.
//David Chase . unresolved
I assume these have to be different operations, but I think there are (some) operations on 512-bit vectors that produce 256-bit vectors, versus similar operations on scalable (SVE, RVV) simd that do some different version of halvening, like low-half followed by zeroes, or even elements set, odd elements zero.
And look what I found, joy:
SVE:
FCVTNT
Floating-point down convert and narrow (top, predicated)
Convert active floating-point elements from the source vector to the next lower precision, and place the results in the odd-numbered half-width elements of the destination vector, leaving the even-numbered elements unchanged. Inactive elements in the destination vector register remain unmodified.
FCVTX
Floating-point down convert, rounding to odd (predicated)
Convert active double-precision floating-point elements from the source vector to single-precision, rounding to Odd, and place the results in the even-numbered 32-bit elements of the destination vector, while setting the odd-numbered elements to zero. Inactive elements in the destination vector register remain unmodified.
NEON:
FCVTN, FCVTN2
Floating-point Convert to lower precision Narrow (vector). This instruction reads each vector element in the SIMD&FP source register, converts each result to half the precision of the source element, writes the final result to a vector, and writes the vector to the lower or upper half of the destination SIMD&FP register. The destination vector elements are half as long as the source vector elements. The rounding mode is determined by the FPCR. The FCVTN instruction writes the vector to the lower half of the destination register and clears the upper half, while the FCVTN2 instruction writes the vector to the upper half of the destination register without affecting the other bits of the register.
Related details
Attention is currently required from:
- Austin Clements
Submit Requirements:
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Austin Clements (Gerrit)
Aug 6, 2026, 2:58:59 PM (yesterday) Aug 6
to Austin Clements, goph...@pubsubhelper.golang.org, golang...@luci-project-accounts.iam.gserviceaccount.com, David Chase, Junyang Shao, Cherry Mui, golang-co...@googlegroups.com
Attention needed from David Chase and Junyang Shao
Austin Clements added 19 comments![]( "Open in Gerrit")
File src/simd/archsimd/_gen/specgen/specexpr/expr.go
Internal, and a tool, so a doc comment is perhaps doubly optional, but
// exprVars iterates the Variables in an Expr, `for v := range exprVars(e)`
Austin Clements
Done
Line 88, Patchset 6:
panic(fmt.Sprintf("%s: argument is %T, want %T", a[0], name, *new(T)))Junyang Shao . resolved
Should it be `...name, a[0]...`?
Austin Clements
Done
File src/simd/archsimd/_gen/specgen/specexpr/num.go
IIUC, `Div` computes `w/x`.
For scalable `x = VW*num/denom`, it's computed as `w/(VW*num/denom) = (w*denom/num)/VW`
However this value is `(w*denom/num)*VW`. Is this wrong, or I miss anything?
Austin Clements
Oh no! You're totally right. We can't implement this case, so I've replaced this with an error.
File src/simd/archsimd/_gen/specgen/specexpr/num_test.go
Line 18, Patchset 6:
{-4, 8, ScalableWidth{-1, 2}},
{4, -8, ScalableWidth{-1, 2}},
{-4, -8, ScalableWidth{1, 2}},Junyang Shao . resolved
I am wondering what does a negative scalable vector width mean?
Austin Clements
Added a comment explaining that these should never happen, and we're just testing the GCD algorithm.
File src/simd/archsimd/_gen/specgen/specexpr/parse.go
my snap reaction is "what expressions?"
I went and looked at doc.go, I'm going to guess this is require expressions, e.g. "z={xB}{xN*2}x{xL/2}".
(But is it the whole thing, or just the RHS of the equality?)
Austin Clements
It's the whole thing. Changed to "constraint expression".
Should we leave a TODO for arrays, slices and pointers?
Austin Clements
I think we actually don't need constraint syntax for those because they can be expressed directly in Go's type system.
I know you have tests that depend on this, but it seems like 'after "{<expr>"' is a more concrete description of what was observed.
Austin Clements
Done
again, error message could be more concrete, e.g. "expected shape base name, which should match the regexp [a-zA-Z]+"
Austin Clements
Done
File src/simd/archsimd/_gen/specgen/specexpr/shape.go
Line 95, Patchset 6:
var MakePointer = MakeFunc1("Pointer", func(elem Type) (any, error) {Junyang Shao . resolved
`MakePointer`
`MakeArray`
`MakeSlice`.It looks like they are never used or tested, are they in a future CL?
Austin Clements
Yeah, they're used in a later CL. Here we're just making sure everything has constructor functions.
File src/simd/archsimd/_gen/specgen/specexpr/solver.go
Line 21, Patchset 6:
// Constrains are written as boolean expressions over shapes and a few basicJunyang Shao . resolved
Austin ClementsConstraints?
Done
Line 34, Patchset 6:
// >=, <=. Arithmetic operators bind more tightly than comparison operators.Junyang Shao . resolved
David ChaseShould we just say arithmetic operators has higher precedence than comparison operators?
I think bind-more-tightly might be less ambiguous. ("group more tightly", perhaps).
Austin Clements
I can never remember which way higher and lower precedence goes despite working on compilers for years!
Line 55, Patchset 6:
// If x is Float64x2, then z would naturally be Float32x2, but since this is
// only 64 bits, the shape is "rounded" up to Float32x4.
//David Chase . unresolved
I assume these have to be different operations, but I think there are (some) operations on 512-bit vectors that produce 256-bit vectors, versus similar operations on scalable (SVE, RVV) simd that do some different version of halvening, like low-half followed by zeroes, or even elements set, odd elements zero.
And look what I found, joy:
SVE:
FCVTNT
Floating-point down convert and narrow (top, predicated)
Convert active floating-point elements from the source vector to the next lower precision, and place the results in the odd-numbered half-width elements of the destination vector, leaving the even-numbered elements unchanged. Inactive elements in the destination vector register remain unmodified.FCVTX
Floating-point down convert, rounding to odd (predicated)
Convert active double-precision floating-point elements from the source vector to single-precision, rounding to Odd, and place the results in the even-numbered 32-bit elements of the destination vector, while setting the odd-numbered elements to zero. Inactive elements in the destination vector register remain unmodified.NEON:
FCVTN, FCVTN2
Floating-point Convert to lower precision Narrow (vector). This instruction reads each vector element in the SIMD&FP source register, converts each result to half the precision of the source element, writes the final result to a vector, and writes the vector to the lower or upper half of the destination SIMD&FP register. The destination vector elements are half as long as the source vector elements. The rounding mode is determined by the FPCR. The FCVTN instruction writes the vector to the lower half of the destination register and clears the upper half, while the FCVTN2 instruction writes the vector to the upper half of the destination register without affecting the other bits of the register.
Austin Clements
I agree that is a thing, though I'm not sure what your larger point is. This seems like an API question, and I think "one name means one thing" implies that the 512->256 version and the N->(N/2 but padded to N) need different names. Or possibly 512->256 shouldn't even exist.
Line 82, Patchset 6:
// a boolean check. Variables that appear only on the right hand side of
// assignments are "independent" and it will enumerate all possible assignments
// of these variables. It never tries to invert any formulas and refuses toJunyang Shao . resolved
I was confused by the 2 "assignments" in this sentence until I read:
```
// Assign is a convenience for asserting that v=val.
func (s *Solver) Assign(v Variable, val Expr) Variable
```
Should we just say this to make the reading more natural:
```
// ... Variables that appear only on the right hand side of
// an "var=expr" assertion are "independent" and it will enumerate all possible values of these Variables...
```
?
Austin Clements
Done
Line 298, Patchset 6:
solverStepCheck solverStepKind = iota
solverStepAssign
solverStepIndepJunyang Shao . resolved
Austin ClementsCan we document these?
Done
Line 348, Patchset 6:
// This is a topo-sort with a few tricks: an assertion can be evaluated once
// all of its input variables are available, BUT a variable value can be
// resolved by potentially more than one assertion. Since we have a mix of
// "AND" and "OR" dependencies, we use a wavefront-style topo sort where we
// track the number of unresolved input variables to each assertion and
// whenever we resolve one of these inputs for the first time, we decrement
// that count. Once it reaches zero, that assertion is let out of the gate.
//
// Also, we bias toward steps that are more likely to cut off a path and less
// likely to cause more fan-out.Junyang Shao . resolved
I was initially confused by what are "AND" and "OR" dependencies.
After reading more, I think "AND" dependency means:
```
x=Basic{xB, xN}
```
`x` is resolved when we know both `xB` and `xN`, and it is done by driving the frontiers."OR" dependency means:
```
x=Basic{xB, xN}
...
x=y
...
```
We need only one of the assignment to be resolved to know the definition of `x`, and the other assignment can be demoted to a check and resolved.Should we make that explicit here?
Austin Clements
Good point. Expanded the docs.
Should we mention in the comment that `queue` is the frontier of all variables with 0 dependencies at the current state?
Austin Clements
Done
It looks like `func (sh *solverHeap) Pop() any` already sets the element's `hid` to -1?
Austin Clements
Done
File src/simd/archsimd/_gen/specgen/specexpr/solver_test.go
Line 118, Patchset 6:
t.Run("swidth div int", func(t *testing.T) {
s := newSolver(t)
v1 := Variable("v1")
v2 := Variable("v2")
s.Assign(v1, mkWidth(1, 2))
s.Assign(v2, &BinExpr{
Op: OpDiv,
X: v1,
Y: Int(2),
})
sol := uniqueSolution(t, s)
bCheck(t, sol, map[Variable]any{
v1: mkWidth(1, 2),
v2: mkWidth(1, 4),
})
})Junyang Shao . resolved
Inferred from the test, looks like we shouldn't have int div swidth. Should we remove that case from `func (w Int) Div(x Num) (Num, error)` and panic if we see it?
Austin Clements
Done.
`s.Assign("x", mustParseExpr(t, "Int32"))`?
Attention is currently required from:
- David Chase
- Junyang Shao
Submit Requirements:
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Austin Clements (Gerrit)
Aug 6, 2026, 2:59:00 PM (yesterday) Aug 6
to Austin Clements, goph...@pubsubhelper.golang.org, golang-co...@googlegroups.com
Attention needed from David Chase and Junyang Shao
Austin Clements uploaded new patchset![]( "Open in Gerrit")
Austin Clements uploaded patch set #7 to this change.
Following approvals got outdated and were removed:
- TryBots-Pass: LUCI-TryBot-Result+1 by golang...@luci-project-accounts.iam.gserviceaccount.com
Related details
Attention is currently required from:
- David Chase
- Junyang Shao
Submit Requirements:
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Austin Clements (Gerrit)
5:16 PM (5 hours ago) 5:16 PM
to David Chase, Junyang Shao, goph...@pubsubhelper.golang.org, Cherry Mui, Austin Clements, golang-co...@googlegroups.com
Attention needed from David Chase and Junyang Shao
Austin Clements has uploaded the change for review![]( "Open in Gerrit")
Austin Clements would like David Chase and Junyang Shao to review this change.
Commit message
simd/archsimd/_gen/specgen/specexpr: constraint solver for SIMD spec
The SIMD spec package uses Go generics to express a lot of the
constraints on vector shapes and other types in the API, but that
can't express everything we need.
This package implements a simple expression language and constraint
solver for writing additional constraints on API types. It's only
meant to be used by the specgen package, which will provide a much
higher-level API to processing the SIMD spec.
Change-Id: I3e8a9e5381f6f507c1e1cf22c69dc1338c63c044
Change diff
diff --git a/src/simd/archsimd/_gen/specgen/specexpr/expr.go b/src/simd/archsimd/_gen/specgen/specexpr/expr.go
new file mode 100644
index 0000000..f3e89b9
--- /dev/null
+++ b/src/simd/archsimd/_gen/specgen/specexpr/expr.go
@@ -0,0 +1,326 @@
+// Copyright 2026 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package specexpr
+
+import (
+ "fmt"
+ "iter"
+ "reflect"
+ "strings"
+ "sync"
+)
+
+type Expr interface {
+ String() string
+ eval(b *Bindings) (any, error)
+ preorder(yield func(Expr) bool) bool
+}
+
+// exprVars yields all Variable nodes in an Expr.
+func exprVars(e Expr) iter.Seq[Variable] {
+ return func(yield func(Variable) bool) {
+ e.preorder(func(e Expr) bool {
+ if v, ok := e.(Variable); ok {
+ return yield(v)
+ }
+ return true
+ })
+ }
+}
+
+// Literal is an [Expr] that evaluates to a literal value.
+//
+// For [Int] and [SymbolicWidth], you probably just want to use those types
+// directly. They're literal values, so you could wrap them in a Literal, but
+// they are valid expressions on their own.
+type Literal struct {
+ Val any
+}
+
+func (e *Literal) String() string {
+ return fmt.Sprint(e.Val)
+}
+func (e *Literal) eval(b *Bindings) (any, error) {
+ if i, ok := e.Val.(int); ok {
+ // The evaluator works with Nums, not ints directly.
+ return Int(i), nil
+ }
+ return e.Val, nil
+}
+func (e *Literal) preorder(yield func(Expr) bool) bool {
+ return yield(e)
+}
+
+// Variable is an [Expr] that evaluates to the value of the named variable.
+type Variable string
+
+func (e Variable) String() string {
+ return string(e)
+}
+func (e Variable) eval(b *Bindings) (any, error) {
+ val := b.Get(e)
+ if val == nil {
+ panic(fmt.Errorf("variable %s not solved", e))
+ }
+ return val, nil
+}
+func (e Variable) preorder(yield func(Expr) bool) bool {
+ return yield(e)
+}
+
+// Func is a function that can be used in an expression. Use the [Func.Apply]
+// method to create an [Expr].
+type Func struct {
+ Name string
+ Func func([]any) (any, error)
+}
+
+func MakeFunc1[T any](name string, fn func(T) (any, error)) func(e Expr) *Apply {
+ f := &Func{
+ Name: name,
+ Func: func(a []any) (any, error) {
+ if len(a) != 1 {
+ panic(fmt.Sprintf("%s: got %d arguments, want %d", name, len(a), 1))
+ }
+ v, ok := a[0].(T)
+ if !ok {
+ panic(fmt.Sprintf("%s: argument is %T, want %T", name, a[0], *new(T)))
+ }
+ return fn(v)
+ },
+ }
+ return func(e Expr) *Apply {
+ return f.Apply(e)
+ }
+}
+func MakeFunc2[T, U any](name string, fn func(T, U) (any, error)) func(e1, e2 Expr) *Apply {
+ f := &Func{
+ Name: name,
+ Func: func(a []any) (any, error) {
+ if len(a) != 2 {
+ panic(fmt.Sprintf("%s: got %d arguments, want %d", name, len(a), 2))
+ }
+ v1, ok := a[0].(T)
+ if !ok {
+ panic(fmt.Sprintf("%s: argument is %T, want %T", name, a[0], *new(T)))
+ }
+ v2, ok := a[1].(U)
+ if !ok {
+ panic(fmt.Sprintf("%s: argument is %T, want %T", name, a[1], *new(U)))+// Apply is an [Expr] that applies a [Func] to a sequence of arguments.
+type Apply struct {
+ Func *Func
+ Args []Expr
+}
+
+func (e *Apply) String() string {
+ var buf strings.Builder
+ buf.WriteString(e.Func.Name)
+ buf.WriteByte('(')
+ for i, x := range e.Args {
+ if i > 0 {
+ buf.WriteString(", ")
+ }
+ buf.WriteString(x.String())
+ }
+ buf.WriteByte(')')
+ return buf.String()
+}
+func (e *Apply) eval(b *Bindings) (any, error) {
+ vals := make([]any, 0, 16)
+ for _, arg := range e.Args {
+ val, err := arg.eval(b)
+ if err != nil {
+ return nil, err
+ }
+ vals = append(vals, val)
+ }
+ return e.Func.Func(vals)
+}
+func (e *Apply) preorder(yield func(Expr) bool) bool {
+ if !yield(e) {
+ return false
+ }
+ for _, a := range e.Args {
+ if !a.preorder(yield) {
+ return false
+ }
+ }
+ return true
+}
+
+// BinExpr is a binary [Expr].+func (e *BinExpr) eval(b *Bindings) (any, error) {
+ xVal, err := e.X.eval(b)
+ if err != nil {
+ return nil, err
+ }
+ yVal, err := e.Y.eval(b)
+ if err != nil {
+ return nil, err
+ }
+
+ xn, okX := xVal.(Num)
+ yn, okY := yVal.(Num)
+
+ switch e.Op {
+ case OpEqual, OpNotEqual:
+ if okX && okY {
+ // Fall through to numeric operations
+ break
+ }
+ // Otherwise, general equality
+ if reflect.TypeOf(xVal) != reflect.TypeOf(yVal) {
+ panic(fmt.Errorf("incompatible types for comparison: %T and %T", xVal, yVal))
+ }
+ if e.Op == OpEqual {
+ return xVal == yVal, nil
+ } else {
+ return xVal != yVal, nil
+ }
+ }
+
+ if !okX {
+ panic(fmt.Errorf("invalid type for %v: %v (%T)", e.Op, xVal, xVal))
+ }
+ if !okY {
+ panic(fmt.Errorf("invalid type for %v: %v (%T)", e.Op, yVal, yVal))
+ }
+
+ switch e.Op {
+ case OpTimes:
+ return xn.Mul(yn)
+
+ case OpDiv:
+ return xn.Div(yn)
+
+ case OpEqual, OpNotEqual, OpGreaterThan, OpLessThan, OpGreaterOrEqual, OpLessOrEqual:
+ return e.evalComparison(xn, yn)
+ }
+
+ panic("bad binop")
+}
+
+func (e *BinExpr) evalComparison(x, y Num) (any, error) {
+ res, ok := x.Compare(y)
+ if !ok {
+ // Incomparable
+ return e.Op == OpNotEqual, nil
+ }
+ switch e.Op {
+ case OpEqual:
+ return res == 0, nil
+ case OpNotEqual:
+ return res != 0, nil
+ case OpGreaterThan:
+ return res > 0, nil
+ case OpLessThan:
+ return res < 0, nil
+ case OpGreaterOrEqual:
+ return res >= 0, nil
+ case OpLessOrEqual:
+ return res <= 0, nil
+ }
+ panic("bad comparison operator")
+}
diff --git a/src/simd/archsimd/_gen/specgen/specexpr/num.go b/src/simd/archsimd/_gen/specgen/specexpr/num.go
new file mode 100644
index 0000000..3686fdb
--- /dev/null
+++ b/src/simd/archsimd/_gen/specgen/specexpr/num.go
@@ -0,0 +1,177 @@
+// Copyright 2026 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package specexpr
+
+import (
+ "cmp"
+ "fmt"
+ "strings"
+)
+
+// Num represents a number in the solver. This is abstracted because we work
+// with both concrete numbers and *symbolic widths* and need to be able to mix
+// them. A Num is also an [Expr].
+type Num interface {
+ Expr
+
+ // ValidWidth returns true if this is a valid width: either a fixed width
+ // (128, 256, 512) or the scalable width VW.
+ ValidWidth() bool
+
+ Mul(x Num) (Num, error)
+ Div(x Num) (Num, error)
+ Compare(o Num) (int, bool)
+
+ String() string
+}
+
+// Int is an integer that satisfies [Num].
+type Int int
+
+func (w Int) ValidWidth() bool {
+ switch w {
+ case 128, 256, 512:
+ return true
+ }
+ return false
+}
+func (w Int) Mul(x Num) (Num, error) {
+ switch x := x.(type) {
+ case Int:
+ return w * x, nil
+ case ScalableWidth:
+ return mkWidth(int(w)*x.num, x.denom), nil
+ }
+ panic("unknown Num")
+}
+func (w Int) Div(x Num) (Num, error) {
+ switch x := x.(type) {
+ case Int:
+ if x == 0 {
+ return nil, fmt.Errorf("division by zero")
+ }
+ if w%x != 0 {
+ return nil, fmt.Errorf("inexact division %d/%d", w, x)
+ }
+ return w / x, nil
+ case ScalableWidth:
+ // ScalableWidth is implicitly multiplied by VW. We have no way to
+ // express the inverse of VW.
+ return nil, fmt.Errorf("cannot divide Int by ScalableWidth")
+ }
+ panic("unknown Num")
+}
+func (w Int) Compare(o Num) (int, bool) {
+ if o, ok := o.(Int); ok {
+ return cmp.Compare(w, o), true
+ }
+ return 0, false
+}
+func (w Int) String() string {
+ return fmt.Sprint(int(w))
+}
+func (w Int) eval(b *Bindings) (any, error) {
+ return w, nil
+}
+func (w Int) preorder(yield func(Expr) bool) bool {
+ return true
+}
+
+// An ScalableWidth represents a symbolic width relative to a fixed but unknown
+// scalable vector width VW. This is represented as a rational factor
+// VW*num/denom
+type ScalableWidth struct {
+ num, denom int
+}
+
+// VW returns the base ScalableWidth representing a full-width scalable vector.
+func VW() ScalableWidth {
+ return ScalableWidth{1, 1}
+}
+
+func (w ScalableWidth) Mul(x Num) (Num, error) {
+ switch x := x.(type) {
+ case Int:
+ return mkWidth(w.num*int(x), w.denom), nil
+ case ScalableWidth:
+ return nil, fmt.Errorf("cannot multiply two scalable widths")
+ }
+ panic("unknown Num")
+}
+
+func (w ScalableWidth) Div(x Num) (Num, error) {
+ switch x := x.(type) {
+ case Int:
+ if x == 0 {
+ return nil, fmt.Errorf("division by zero")
+ }
+ return mkWidth(w.num, w.denom*int(x)), nil
+ case ScalableWidth:
+ a, b := w.num*x.denom, w.denom*x.num
+ if b == 0 {
+ return nil, fmt.Errorf("division by zero")
+ }
+ if a%b != 0 {
+ return nil, fmt.Errorf("inexact division %d/%d", w, x)
+ }
+ return Int(a / b), nil
+ }
+ panic("unknown Num")
+}
+
+func (w ScalableWidth) Compare(o Num) (int, bool) {
+ if o, ok := o.(ScalableWidth); ok {
+ return cmp.Compare(w.num*o.denom, o.num*w.denom), true
+ }
+ return 0, false
+}
+
+func (w ScalableWidth) String() string {
+ var buf strings.Builder
+ buf.WriteString("VW")
+ if w.num > 1 {
+ fmt.Fprintf(&buf, "*%d", w.num)
+ }
+ if w.denom > 1 {
+ fmt.Fprintf(&buf, "/%d", w.denom)
+ }
+ return buf.String()
+}
+
+func (w ScalableWidth) eval(b *Bindings) (any, error) {
+ return w, nil
+}
+
+func (w ScalableWidth) preorder(yield func(Expr) bool) bool {
+ return true
+}
diff --git a/src/simd/archsimd/_gen/specgen/specexpr/num_test.go b/src/simd/archsimd/_gen/specgen/specexpr/num_test.go
new file mode 100644
index 0000000..f28a8df
--- /dev/null
+++ b/src/simd/archsimd/_gen/specgen/specexpr/num_test.go
@@ -0,0 +1,29 @@
+// Copyright 2026 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package specexpr
+
+import "testing"
+
+func TestMkWidth(t *testing.T) {
+ tests := []struct {
+ num, denom int
+ want ScalableWidth
+ }{
+ {4, 8, ScalableWidth{1, 2}},
+ {3, 9, ScalableWidth{1, 3}},
+ {12, 18, ScalableWidth{2, 3}},
+ {0, 5, ScalableWidth{0, 1}},
+ // We should never have a negative scalable width, but test GCD on them just in case.
+ {-4, 8, ScalableWidth{-1, 2}},
+ {4, -8, ScalableWidth{-1, 2}},
+ {-4, -8, ScalableWidth{1, 2}},
+ }
+ for _, tc := range tests {
+ got := mkWidth(tc.num, tc.denom)
+ if got != tc.want {
+ t.Errorf("mkWidth(%d, %d) = %v; want %v", tc.num, tc.denom, got, tc.want)
+ }
+ }
+}
diff --git a/src/simd/archsimd/_gen/specgen/specexpr/parse.go b/src/simd/archsimd/_gen/specgen/specexpr/parse.go
new file mode 100644
index 0000000..b741b40
--- /dev/null
+++ b/src/simd/archsimd/_gen/specgen/specexpr/parse.go
@@ -0,0 +1,282 @@
+// Copyright 2026 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package specexpr
+
+import (
+ "fmt"
+ "strconv"
+ "strings"
+)
+
+// ParseExpr parses a constraint expression.+func (p *parser) failAt(pos int, msg string, args ...any) {
+ panic(&parseError{msg: msg, args: args, pos: pos})
+ return p.parseNumber()
+ }
+
+ // Variable
+ if isAlpha(b) {
+ name, _ := p.consume(isAlpha)
+ p.skipSpace()
+ return Variable(name)
+ }
+
+ if b == 0 {
+ p.fail("unexpected end")
+ }
+ p.fail("unexpected character '%c'", b)
+ panic("not reachable")
+}
+
+func (p *parser) parseNumber() Int {
+ nStr, ok := p.consume(isDigit)
+ if !ok {
+ p.fail("expected number")
+ }
+ num, err := strconv.Atoi(nStr)
+ if err != nil {
+ p.fail("%s", err)
+ }
+ p.skipSpace()
+ return Int(num)
+}
+
+// - BaseNxL: A fixed vector with L lanes. E.g., Int32x4
+// - BaseNs: A scalable vector. E.g., Float32s
+// - BaseNwW: A fixed vector of width W. E.g., Int32w128 (same as Int32x4)
+// - MaskNxL, MaskNs, or MaskNwW: Similar, but describes a mask.
+// - baseN: A scalar. E.g., uint8
+func (p *parser) parseSymShape() *Apply {
+ var b, n Expr
+
+ trySymPart := func() Expr {
+ openPos := p.pos
+ if !p.try("{") {
+ return nil
+ }
+
+ x := p.parseExpr()
+ if !p.try("}") {
+ p.failAt(openPos, "'{' missing close '}' in symbolic shape")
+ }
+ return x
+ }
+
+ // Base
+ if b = trySymPart(); b == nil {
+ base, ok := p.consume(isAlpha)
+ if !ok {
+ p.fail("expected shape base name matching [a-zA-Z]+")
+ }
+ b = &Literal{strings.ToLower(base)}
+ }
+
+ // Element size
+ if n = trySymPart(); n == nil {
+ n = p.parseNumber()
+ }
+
+ elem := MakeBasic(b, n)
+
+ // Width
+ var x *Apply
+ // Don't use p.try here because that will skip whitespace.
+ switch p.peek() {
+ case 's':
+ p.pos++
+ x = MakeVector(elem, VW())
+ case 'x':
+ p.pos++
+ l := trySymPart()
+ if l == nil {
+ // TODO: Disallow width-rounding in this case?
+ l = p.parseNumber()
+ }
+ x = makeVectorL(elem, l)
+ case 'w':
+ p.pos++
+ w := trySymPart()
+ if w == nil {
+ w = p.parseNumber()
+ }
+ x = MakeVector(elem, w)
+ default:
+ // Scalar
+ x = elem
+ }
+
+ p.skipSpace()
+ return x
+}
diff --git a/src/simd/archsimd/_gen/specgen/specexpr/parse_test.go b/src/simd/archsimd/_gen/specgen/specexpr/parse_test.go
new file mode 100644
index 0000000..1810df1
--- /dev/null
+++ b/src/simd/archsimd/_gen/specgen/specexpr/parse_test.go
@@ -0,0 +1,142 @@
+// Copyright 2026 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package specexpr
+
+import (
+ "reflect"
+ "strings"
+ "testing"
+)
+
+func TestParseExpr(t *testing.T) {
+ tests := []struct {
+ expr string
+ want Expr
+ }{
+ {
+ expr: "10",
+ want: Int(10),
+ },
+ {
+ expr: "v",
+ want: Variable("v"),
+ },
+ {
+ expr: "v * 2",
+ want: &BinExpr{OpTimes, Variable("v"), Int(2)},
+ },
+ {
+ expr: "v / 2",
+ want: &BinExpr{OpDiv, Variable("v"), Int(2)},
+ },
+ {
+ expr: "x = y * 2",
+ want: &BinExpr{OpEqual, Variable("x"), &BinExpr{OpTimes, Variable("y"), Int(2)}},
+ },
+ {
+ expr: "a > b",
+ want: &BinExpr{OpGreaterThan, Variable("a"), Variable("b")},
+ },
+ {
+ expr: "a >= b",
+ want: &BinExpr{OpGreaterOrEqual, Variable("a"), Variable("b")},
+ },
+ {
+ expr: "a < b",
+ want: &BinExpr{OpLessThan, Variable("a"), Variable("b")},
+ },
+ {
+ expr: "a <= b",
+ want: &BinExpr{OpLessOrEqual, Variable("a"), Variable("b")},
+ },
+ {
+ expr: "(v * 2) / 3",
+ want: &BinExpr{OpDiv, &BinExpr{OpTimes, Variable("v"), Int(2)}, Int(3)},
+ },
+ {
+ expr: "Int32x4",
+ want: makeVectorL(MakeBasic(&Literal{"int"}, Int(32)), Int(4)),
+ },
+ {
+ expr: "Float64s",
+ want: MakeVector(MakeBasic(&Literal{"float"}, Int(64)), VW()),
+ },
+ {
+ expr: "{B}{N}x{L}",
+ want: makeVectorL(MakeBasic(Variable("B"), Variable("N")), Variable("L")),
+ },
+ {
+ expr: "{B}{N}w{W}",
+ want: MakeVector(MakeBasic(Variable("B"), Variable("N")), Variable("W")),
+ },
+ {
+ expr: "{xB}{xN*2}x{xL/2}",
+ want: makeVectorL(
+ MakeBasic(Variable("xB"), &BinExpr{OpTimes, Variable("xN"), Int(2)}),
+ &BinExpr{OpDiv, Variable("xL"), Int(2)},
+ wantErr: "'{' missing close '}' in symbolic shape at 1",
+ },
+ {
+ expr: "Int32x{}",
+ wantErr: "unexpected character '}'",
+ },
+ }
+
+ for _, tc := range tests {
+ t.Run(tc.expr, func(t *testing.T) {
+ _, err := ParseExpr(tc.expr)
+ if err == nil {
+ t.Fatalf("ParseExpr(%q) succeeded; want error containing %q", tc.expr, tc.wantErr)
+ }
+ if gotErr := err.Error(); !strings.Contains(gotErr, tc.wantErr) {
+ t.Errorf("ParseExpr(%q) returned error %q; want error containing %q", tc.expr, gotErr, tc.wantErr)
+ }
+ })
+ }
+}
diff --git a/src/simd/archsimd/_gen/specgen/specexpr/shape.go b/src/simd/archsimd/_gen/specgen/specexpr/shape.go
new file mode 100644
index 0000000..ba563df
--- /dev/null
+++ b/src/simd/archsimd/_gen/specgen/specexpr/shape.go
@@ -0,0 +1,129 @@
+// Copyright 2026 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package specexpr
+
+import (
+ "fmt"
+ "strings"
+)
+
+// MinWidth is the minimum vector width, in bits.
+const MinWidth = Int(128)
+
+type Type interface {
+ isType()
+ String() string
+}
+
+type Basic struct {
+ Base string // "int", "uint", "float", "Mask", etc
+ Bits Int // 0 if unsized, otherwise >= 8
+}
+
+var MakeBasic = MakeFunc2("Basic", func(base string, bits Int) (any, error) {
+ // Perform width rounding.
+ bits = max(8, bits)
+ return Basic{Base: base, Bits: bits}, nil
+})
+
+func (t Basic) isType() {}
+func (t Basic) String() string {
+ if t.Bits == 0 {
+ return t.Base
+ }
+ return fmt.Sprintf("%s%d", t.Base, t.Bits)
+}
+
+type Vector struct {
+ Elem Basic // Must have Bits != 0
+ Width Num // Bit width
+}
+
+var MakeVector = MakeFunc2("VectorW", func(elem Basic, w Num) (any, error) {
+ if !w.ValidWidth() {
+ return nil, fmt.Errorf("invalid width %s", w)
+ }
+ return Vector{Elem: elem, Width: w}, nil
+})
+
+var makeVectorL = MakeFunc2("VectorL", func(elem Basic, l Num) (any, error) {
+ w, _ := l.Mul(elem.Bits)
+ if w2, ok := w.(Int); ok {
+ // Perform width rounding
+ w = max(MinWidth, w2)
+ }
+ if !w.ValidWidth() {
+ return nil, fmt.Errorf("invalid width %s", w)
+ }
+ return Vector{Elem: elem, Width: w}, nil
+})
+
+func (t Vector) isType() {}
+func (t Vector) String() string {
+ var buf strings.Builder
+ if t.Elem.Base == "" {
+ buf.WriteString("<bad Elem>")
+ } else {
+ buf.WriteString(strings.ToTitle(t.Elem.Base[:1]))
+ buf.WriteString(t.Elem.Base[1:])
+ fmt.Fprintf(&buf, "%d", t.Elem.Bits)
+ }
+ if t.Scalable() {
+ buf.WriteString("s")
+ } else {
+ l, err := t.Width.Div(t.Elem.Bits)
+ if err == nil {
+ fmt.Fprintf(&buf, "x%d", l)
+ } else {
+ // Bad width, but we can print it anyway
+ fmt.Fprintf(&buf, "w%s", t.Width)
+ }
+ }
+ return buf.String()
+}
+func (t Vector) Scalable() bool {
+ sw, ok := t.Width.(ScalableWidth)
+ return ok && sw.ValidWidth()
+}
+
+type Pointer struct {
+ Elem Type
+}
+
+var MakePointer = MakeFunc1("Pointer", func(elem Type) (any, error) {
+ return Pointer{elem}, nil
+})
+
+func (t Pointer) isType() {}
+func (t Pointer) String() string {
+ return "*" + t.Elem.String()
+}
+
+type Array struct {
+ Elem Type
+ Len Int
+}
+
+var MakeArray = MakeFunc2("Array", func(elem Type, len Int) (any, error) {
+ return Array{elem, len}, nil
+})
+
+func (t Array) isType() {}
+func (t Array) String() string {
+ return fmt.Sprintf("[%d]%s", t.Len, t.Elem)
+}
+
+type Slice struct {
+ Elem Type
+}
+
+var MakeSlice = MakeFunc1("Slice", func(elem Type) (any, error) {
+ return Slice{elem}, nil
+})
+
+func (t Slice) isType() {}
+func (t Slice) String() string {
+ return "[]" + t.Elem.String()
+}
diff --git a/src/simd/archsimd/_gen/specgen/specexpr/solver.go b/src/simd/archsimd/_gen/specgen/specexpr/solver.go
new file mode 100644
index 0000000..e5eb0ed
--- /dev/null
+++ b/src/simd/archsimd/_gen/specgen/specexpr/solver.go
@@ -0,0 +1,543 @@
+// Copyright 2026 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+// Package specexpr manipulates symbolic constraints on vector shapes.
+//
+// # Shapes
+//
+// A vector shape consists of a base type B (e.g., int, float), element width N
+// (8, 16, 32, or 64), and a vector width W (128, 256, 512, or scalable). It
+// also has a lane count L, which is the vector width / element width. These are
+// written like "Int32x4" or "Int32w128" or, for a scalable vector, "Int32s"
+// Masks are represented as vectors with a base type of "Mask", e.g.,
+// "Mask32x4".
+//
+// Scalar shapes consist only of a base type and an element width, e.g.,
+// "uint32".
+//
+// # Expressions
+//
+// Constraints are written as boolean expressions over shapes and a few basic+// a boolean check. Variables that appear only on the right hand side of
+// assignments are "independent" and it will enumerate all possible values of
+// these variables. It never tries to invert any formulas and refuses to solve a
+// system with cycles. This is intentional to keep this solver fast: if your
+// formulas are cyclic, you're doing something too complicated.
+type Solver struct {
+ vars map[Variable][]any
+ asserts []Expr
+ tracer *tracer
+}
+
+// SetTrace enables emitting a solver trace to w.
+func (s *Solver) SetTrace(w io.Writer) {
+ if w == nil {
+ s.tracer = nil
+ } else {
+ s.tracer = &tracer{w: w}
+ }
+}
+
+// Declare declares a variable and its domain.
+//
+// Any "int" values in domain will be converted to [Int].
+func (s *Solver) Declare(v Variable, domain []any) {
+ if s.vars == nil {
+ s.vars = make(map[Variable][]any)
+ }
+ if _, ok := s.vars[v]; ok {
+ panic(v + " redeclared")
+ }
+ for i, d := range domain {
+ if d, ok := d.(int); ok {
+ domain[i] = Int(d)
+ }
+ val, err := step.expr.(*BinExpr).Y.eval(&b)
+ if err == nil {
+ if domain, ok := s.vars[step.bind]; ok && !slices.Contains(domain, val) {
+ err = fmt.Errorf("cannot assign %s=%v: not in domain", step.bind, val)
+ }
+ }
+ s.tracer.assign(step.expr, step.bind, val, err)
+ if err != nil {
+ addErr(err)
+ return true
+ }
+ b.vals = append(b.vals, val)
+ defer pop()
+ return visit(steps, yield)
+
+ case solverStepCheck:
+ val, err := step.expr.eval(&b)+ // solverStepIndep is a solverStep that simultaneously binds
+ // [solverStep.bind] to every possible value in bind's domain.
+ solverStepIndep solverStepKind = iota
+ // solverStepAssign is a solverStep where expr is an [OpEqual] [BinExpr]
+ // where the LHS is a Variable. It evaluates the RHS and assigns it to the
+ // variable. Variable must not have been bound by an earlier step (any
+ // subsequent OpEqual expressions for this variable should instead be a
+ // solverStepCheck).
+ solverStepAssign
+ // solverStepCheck is a solverStep that checks that expr is true and
+ // otherwise terminates the current solver branch.
+ solverStepCheck
+ // This is a topo-sort with a few tricks: an assertion can be evaluated once
+ // all of its input variables are available, BUT a variable value can be
+ // resolved by potentially more than one assertion. Hence, we have a mix of
+ // "AND" and "OR" dependencies. For example, if we have:
+ //
+ // x=Basic{xB, xN}
+ // x=y
+ //
+ // Then x depends on "Basic{xB, xN}" OR "y" because we can assign x's value
+ // as soon as we resolve either of these. But resolving the first of these
+ // two expressions depends on xB AND xN.
+ //
+ // To handle this mix of "AND" and "OR" dependencies, we use a
+ // wavefront-style topo sort where we track the number of unresolved input
+ // variables to each assertion and whenever we resolve one of these inputs
+ // for the first time, we decrement that count. Once it reaches zero, that
+ // assertion is let out of the gate.
+ //
+ // The second trick is that in the set of possible next steps, we bias
+ // toward taking steps that are more likely to cut off a path and less
+ // Drive the frontier. queue is the frontier of variables whose dependencies
+ // are all resolved, maintained in a heuristic order.
+ heap.Init(&queue)
+ for len(queue) > 0 {
+ step := queue[0]
+ heap.Pop(&queue)
+
index 0000000..03cd85a
--- /dev/null
+++ b/src/simd/archsimd/_gen/specgen/specexpr/solver_test.go
@@ -0,0 +1,415 @@
+// Copyright 2026 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package specexpr
+
+import (
+ "fmt"
+ "maps"
+ "slices"
+ "strings"
+ "testing"
+)
+
+func newSolver(t *testing.T) *Solver {
+ var s Solver
+ s.SetTrace(t.Output())
+ return &s
+}
+
+func TestSolver(t *testing.T) {
+ t.Run("constant assignment", func(t *testing.T) {
+ s := newSolver(t)
+ v1 := Variable("v1")
+ s.Assign(v1, Int(10))
+
+ sol := uniqueSolution(t, s)
+ bCheck(t, sol, map[Variable]any{v1: Int(10)})
+ })
+
+ t.Run("simple dependency", func(t *testing.T) {
+ testBinaryOp(t, 10, &BinExpr{
+ Op: OpTimes,
+ X: Variable("v1"),
+ Y: Int(2),
+ }, Int(20))
+ })
+
+ t.Run("division", func(t *testing.T) {
+ testBinaryOp(t, 16, &BinExpr{
+ Op: OpDiv,
+ X: Variable("v1"),
+ Y: Int(4),
+ }, Int(4))
+ })
+
+ t.Run("cycle detection", func(t *testing.T) {
+ s := newSolver(t)
+ v1 := Variable("v1")
+ v2 := Variable("v2")
+ s.Assign(v1, Variable(v2))
+ s.Assign(v2, Variable(v1))
+
+ err := solverError(t, s)
+ if !strings.Contains(err.Error(), "cyclic requirements") {
+ t.Fatalf("expected cycle error, got %v", err)
+ }
+ })
+
+ t.Run("multiple assignment conflicting values", func(t *testing.T) {
+ s := newSolver(t)
+ v1 := Variable("v1")
+ s.Assign(v1, Int(10))
+ s.Assign(v1, Int(20))
+
+ err := solverError(t, s)
+ if !strings.Contains(err.Error(), "no solutions") {
+ t.Fatalf("expected no solutions error, got %v", err)
+ }
+ })
+
+ t.Run("multiple assignment same value", func(t *testing.T) {
+ s := newSolver(t)
+ v1 := Variable("v1")
+ s.Assign(v1, Int(10))
+ s.Assign(v1, Int(10))
+
+ sol := uniqueSolution(t, s)
+ bCheck(t, sol, map[Variable]any{v1: Int(10)})
+ })
+
+ t.Run("swidth times int", func(t *testing.T) {
+ s := newSolver(t)
+ v1 := Variable("v1")
+ v2 := Variable("v2")
+ s.Assign(v1, mkWidth(1, 2))
+ s.Assign(v2, &BinExpr{
+ Op: OpTimes,
+ X: v1,
+ Y: Int(4),
+ })
+
+ sol := uniqueSolution(t, s)
+ bCheck(t, sol, map[Variable]any{
+ v1: mkWidth(1, 2),
+ v2: mkWidth(2, 1),
+ })
+ })
+
+ t.Run("int times swidth", func(t *testing.T) {
+ s := newSolver(t)
+ v1 := Variable("v1")
+ v2 := Variable("v2")
+ s.Assign(v1, mkWidth(1, 2))
+ s.Assign(v2, &BinExpr{
+ Op: OpTimes,
+ X: Int(4),
+ Y: v1,
+ })
+
+ sol := uniqueSolution(t, s)
+ bCheck(t, sol, map[Variable]any{
+ v1: mkWidth(1, 2),
+ v2: mkWidth(2, 1),
+ })
+ })
+
+ t.Run("swidth div int", func(t *testing.T) {
+ s := newSolver(t)
+ v1 := Variable("v1")
+ v2 := Variable("v2")
+ s.Assign(v1, mkWidth(1, 2))
+ s.Assign(v2, &BinExpr{
+ Op: OpDiv,
+ X: v1,
+ Y: Int(2),
+ })
+
+ sol := uniqueSolution(t, s)
+ bCheck(t, sol, map[Variable]any{
+ v1: mkWidth(1, 2),
+ v2: mkWidth(1, 4),
+ })
+ })
+}
+
+func testBinaryOp(t *testing.T, v1Val Int, v2Expr Expr, expectedV2Val any) {
+ t.Helper()
+ s := newSolver(t)
+ v1 := Variable("v1")
+ v2 := Variable("v2")
+ s.Assign(v1, v1Val)
+ s.Assign(v2, v2Expr)
+
+ sol := uniqueSolution(t, s)
+ bCheck(t, sol, map[Variable]any{v1: v1Val, v2: expectedV2Val})
+}
+
+func TestComparisons(t *testing.T) {
+ t.Run("greater than", func(t *testing.T) {
+ s := newSolver(t)
+ v1 := Variable("v1")
+ v2 := Variable("v2")
+ s.Assign(v1, Int(20))
+ s.Assign(v2, Int(10))
+
+ // Add comparison v1 > v2 and assert it must be true
+ s.Assert(&BinExpr{Op: OpGreaterThan, X: v1, Y: v2})
+
+ uniqueSolution(t, s)
+ })
+
+ t.Run("less than", func(t *testing.T) {
+ s := newSolver(t)
+ v1 := Variable("v1")
+ v2 := Variable("v2")
+ s.Assign(v1, Int(10))
+ s.Assign(v2, Int(20))
+
+ s.Assert(&BinExpr{Op: OpLessThan, X: v1, Y: v2})
+
+ uniqueSolution(t, s)
+ })
+}
+
+func TestSolveShape(t *testing.T) {
+ t.Run("scalar Int32", func(t *testing.T) {
+ s := newSolver(t)
+ s.Assign("x", mustParseExpr(t, "Int32"))
+
+ sol := uniqueSolution(t, s)
+ bCheck(t, sol, map[Variable]any{
+ "x": Basic{"int", 32},
+ })
+ })
+
+ t.Run("vector Int32x4", func(t *testing.T) {
+ s := newSolver(t)
+ s.Assign("x", mustParseExpr(t, "Int32x4"))
+
+ sol := uniqueSolution(t, s)
+ bCheck(t, sol, map[Variable]any{
+ "x": Vector{Basic{"int", 32}, Int(128)},
+ })
+ })
+
+ t.Run("scalar symbolic {xB}{xN}", func(t *testing.T) {
+ s := newSolver(t)
+ s.Assign("x", mustParseExpr(t, "{xB}{xN}"))
+ s.Assign("xB", &Literal{"int"})
+ s.Assign("xN", Int(32))
+
+ sol := uniqueSolution(t, s)
+ bCheck(t, sol, map[Variable]any{
+ "x": Basic{"int", 32},
+ "xB": "int",
+ "xN": Int(32),
+ })
+ })
+
+ vectorElem := MakeField[Vector]("Elem")
+ basicBase := MakeField[Basic]("Base")
+ basicBits := MakeField[Basic]("Bits")
+ vectorWidth := MakeField[Vector]("Width")
+ assignVector := func(s *Solver, v Variable, e Expr) {
+ x := s.Assign(v, e)
+ s.Assign(v+"B", basicBase.Apply(vectorElem.Apply(x)))
+ xN := s.Assign(v+"N", basicBits.Apply(vectorElem.Apply(x)))
+ xW := s.Assign(v+"W", vectorWidth.Apply(x))
+ s.Assign(v+"L", &BinExpr{Op: OpDiv, X: xW, Y: xN})
+ }
+
+ t.Run("derived scalable vector with lane count", func(t *testing.T) {
+ s := newSolver(t)
+ assignVector(s, "x", mustParseExpr(t, "Int32s"))
+ s.Assign("y", mustParseExpr(t, "{xB}{xN*2}x{xL/2}"))
+
+ sol := uniqueSolution(t, s)
+ bCheck(t, sol, map[Variable]any{
+ "y": Vector{Basic{"int", 64}, mkWidth(1, 1)},
+ "xW": mkWidth(1, 1),
+ "xL": mkWidth(1, 32),
+ })
+ })
+
+ t.Run("derived scalable vector with width", func(t *testing.T) {
+ s := newSolver(t)
+ assignVector(s, "x", mustParseExpr(t, "Int32s"))
+ s.Assign("y", mustParseExpr(t, "{xB}{xN*2}w{xW}"))
+
+ sol := uniqueSolution(t, s)
+ bCheck(t, sol, map[Variable]any{
+ "y": Vector{Basic{"int", 64}, mkWidth(1, 1)},
+ "xW": mkWidth(1, 1),
+ })
+ })
+
+ t.Run("width rounding", func(t *testing.T) {
+ s := newSolver(t)
+ assignVector(s, "x", mustParseExpr(t, "Int64x2"))
+ s.Assign("y", mustParseExpr(t, "{xB}{xN/2}x{xL}"))
+
+ sol := uniqueSolution(t, s)
+ bCheck(t, sol, map[Variable]any{
+ "y": Vector{Basic{"int", 32}, Int(128)},
+ })
+ })
+
+ t.Run("domain limits", func(t *testing.T) {
+ s := newSolver(t)
+ s.Declare("x", []any{1, 2})
+ s.Declare("y", []any{1, 2})
+ s.Assign("y", mustParseExpr(t, "x*2"))
+
+ sol := uniqueSolution(t, s)
+ bCheck(t, sol, map[Variable]any{
+ "x": Int(1), "y": Int(2),
+ })
+ })
+
+ t.Run("non-scalable width", func(t *testing.T) {
+ s := newSolver(t)
+ assignVector(s, "x", mustParseExpr(t, "Int32s"))
+ s.Assign("y", mustParseExpr(t, "Int16x{xL}"))
+
+ err := solverError(t, s)
+ if !strings.Contains(err.Error(), "invalid width") {
+ t.Fatalf("expected invalid width error, got: %v", err)
+ }
+ })
+}
+
+func TestEnumerator(t *testing.T) {
+ t.Run("simple enumeration", func(t *testing.T) {
+ s := newSolver(t)
+ v1 := Variable("v1")
+ v2 := Variable("v2")
+
+ s.Declare(v1, []any{1, 2, 3, 4})
+
+ // Assert v2 = v1 * 2
+ s.Assign(v2, &BinExpr{Op: OpTimes, X: v1, Y: Int(2)})
+
+ sols := allSolutions(s)
+
+ if len(sols) != 4 {
+ t.Errorf("expected 4 solutions, got %d", len(sols))
+ }
+
+ // Verify that each solution maps v2 to v1*2
+ for _, sol := range sols {
+ m := bmap(sol)
+ v1Val := m[v1].(Int)
+ v2Val := m[v2].(Int)
+ if v2Val != v1Val*2 {
+ t.Errorf("solution %v violates v2 = v1*2", m)
+ }
+ }
+ })
+
+ t.Run("comparison constraints enumeration", func(t *testing.T) {
+ s := newSolver(t)
+ v1 := Variable("v1")
+ v2 := Variable("v2")
+
+ s.Declare(v1, []any{1, 2, 3, 4, 5})
+
+ // v2 = v1 * 2
+ s.Assign(v2, &BinExpr{Op: OpTimes, X: v1, Y: Int(2)})
+
+ // v1 > 2
+ s.Assert(&BinExpr{Op: OpGreaterThan, X: v1, Y: Int(2)})
+
+ // v2 < 10
+ s.Assert(&BinExpr{Op: OpLessThan, X: v2, Y: Int(10)})Change information
Files:
- A src/simd/archsimd/_gen/specgen/specexpr/expr.go
- A src/simd/archsimd/_gen/specgen/specexpr/num.go
- A src/simd/archsimd/_gen/specgen/specexpr/num_test.go
- A src/simd/archsimd/_gen/specgen/specexpr/parse.go
- A src/simd/archsimd/_gen/specgen/specexpr/parse_test.go
- A src/simd/archsimd/_gen/specgen/specexpr/shape.go
- A src/simd/archsimd/_gen/specgen/specexpr/solver.go
- A src/simd/archsimd/_gen/specgen/specexpr/solver_test.go
- A src/simd/archsimd/_gen/specgen/specexpr/tracer.go
Change size: XL
Delta: 9 files changed, 2107 insertions(+), 0 deletions(-)
Related details
Attention is currently required from:
- David Chase
- Junyang Shao
Submit Requirements:
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Reply all
Reply to author
Forward
0 new messages