1 files changed, 381 insertions, 0 deletions
diff --git a/src/cmd/compile/internal/compare/compare.go b/src/cmd/compile/internal/compare/compare.go
new file mode 100644
index 0000000..e165cd6
--- /dev/null
+++ b/src/cmd/compile/internal/compare/compare.go
@@ -0,0 +1,381 @@
+// Copyright 2022 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 compare contains code for generating comparison
+// routines for structs, strings and interfaces.
+package compare
+
+import (
+	"cmd/compile/internal/base"
+	"cmd/compile/internal/ir"
+	"cmd/compile/internal/typecheck"
+	"cmd/compile/internal/types"
+	"fmt"
+	"math/bits"
+	"sort"
+)
+
+// IsRegularMemory reports whether t can be compared/hashed as regular memory.
+func IsRegularMemory(t *types.Type) bool {
+	a, _ := types.AlgType(t)
+	return a == types.AMEM
+}
+
+// Memrun finds runs of struct fields for which memory-only algs are appropriate.
+// t is the parent struct type, and start is the field index at which to start the run.
+// size is the length in bytes of the memory included in the run.
+// next is the index just after the end of the memory run.
+func Memrun(t *types.Type, start int) (size int64, next int) {
+	next = start
+	for {
+		next++
+		if next == t.NumFields() {
+			break
+		}
+		// Stop run after a padded field.
+		if types.IsPaddedField(t, next-1) {
+			break
+		}
+		// Also, stop before a blank or non-memory field.
+		if f := t.Field(next); f.Sym.IsBlank() || !IsRegularMemory(f.Type) {
+			break
+		}
+		// For issue 46283, don't combine fields if the resulting load would
+		// require a larger alignment than the component fields.
+		if base.Ctxt.Arch.Alignment > 1 {
+			align := t.Alignment()
+			if off := t.Field(start).Offset; off&(align-1) != 0 {
+				// Offset is less aligned than the containing type.
+				// Use offset to determine alignment.
+				align = 1 << uint(bits.TrailingZeros64(uint64(off)))
+			}
+			size := t.Field(next).End() - t.Field(start).Offset
+			if size > align {
+				break
+			}
+		}
+	}
+	return t.Field(next-1).End() - t.Field(start).Offset, next
+}
+
+// EqCanPanic reports whether == on type t could panic (has an interface somewhere).
+// t must be comparable.
+func EqCanPanic(t *types.Type) bool {
+	switch t.Kind() {
+	default:
+		return false
+	case types.TINTER:
+		return true
+	case types.TARRAY:
+		return EqCanPanic(t.Elem())
+	case types.TSTRUCT:
+		for _, f := range t.Fields() {
+			if !f.Sym.IsBlank() && EqCanPanic(f.Type) {
+				return true
+			}
+		}
+		return false
+	}
+}
+
+// EqStructCost returns the cost of an equality comparison of two structs.
+//
+// The cost is determined using an algorithm which takes into consideration
+// the size of the registers in the current architecture and the size of the
+// memory-only fields in the struct.
+func EqStructCost(t *types.Type) int64 {
+	cost := int64(0)
+
+	for i, fields := 0, t.Fields(); i < len(fields); {
+		f := fields[i]
+
+		// Skip blank-named fields.
+		if f.Sym.IsBlank() {
+			i++
+			continue
+		}
+
+		n, _, next := eqStructFieldCost(t, i)
+
+		cost += n
+		i = next
+	}
+
+	return cost
+}
+
+// eqStructFieldCost returns the cost of an equality comparison of two struct fields.
+// t is the parent struct type, and i is the index of the field in the parent struct type.
+// eqStructFieldCost may compute the cost of several adjacent fields at once. It returns
+// the cost, the size of the set of fields it computed the cost for (in bytes), and the
+// index of the first field not part of the set of fields for which the cost
+// has already been calculated.
+func eqStructFieldCost(t *types.Type, i int) (int64, int64, int) {
+	var (
+		cost    = int64(0)
+		regSize = int64(types.RegSize)
+
+		size int64
+		next int
+	)
+
+	if base.Ctxt.Arch.CanMergeLoads {
+		// If we can merge adjacent loads then we can calculate the cost of the
+		// comparison using the size of the memory run and the size of the registers.
+		size, next = Memrun(t, i)
+		cost = size / regSize
+		if size%regSize != 0 {
+			cost++
+		}
+		return cost, size, next
+	}
+
+	// If we cannot merge adjacent loads then we have to use the size of the
+	// field and take into account the type to determine how many loads and compares
+	// are needed.
+	ft := t.Field(i).Type
+	size = ft.Size()
+	next = i + 1
+
+	return calculateCostForType(ft), size, next
+}
+
+func calculateCostForType(t *types.Type) int64 {
+	var cost int64
+	switch t.Kind() {
+	case types.TSTRUCT:
+		return EqStructCost(t)
+	case types.TSLICE:
+		// Slices are not comparable.
+		base.Fatalf("eqStructFieldCost: unexpected slice type")
+	case types.TARRAY:
+		elemCost := calculateCostForType(t.Elem())
+		cost = t.NumElem() * elemCost
+	case types.TSTRING, types.TINTER, types.TCOMPLEX64, types.TCOMPLEX128:
+		cost = 2
+	case types.TINT64, types.TUINT64:
+		cost = 8 / int64(types.RegSize)
+	default:
+		cost = 1
+	}
+	return cost
+}
+
+// EqStruct compares two structs np and nq for equality.
+// It works by building a list of boolean conditions to satisfy.
+// Conditions must be evaluated in the returned order and
+// properly short-circuited by the caller.
+// The first return value is the flattened list of conditions,
+// the second value is a boolean indicating whether any of the
+// comparisons could panic.
+func EqStruct(t *types.Type, np, nq ir.Node) ([]ir.Node, bool) {
+	// The conditions are a list-of-lists. Conditions are reorderable
+	// within each inner list. The outer lists must be evaluated in order.
+	var conds [][]ir.Node
+	conds = append(conds, []ir.Node{})
+	and := func(n ir.Node) {
+		i := len(conds) - 1
+		conds[i] = append(conds[i], n)
+	}
+
+	// Walk the struct using memequal for runs of AMEM
+	// and calling specific equality tests for the others.
+	for i, fields := 0, t.Fields(); i < len(fields); {
+		f := fields[i]
+
+		// Skip blank-named fields.
+		if f.Sym.IsBlank() {
+			i++
+			continue
+		}
+
+		typeCanPanic := EqCanPanic(f.Type)
+
+		// Compare non-memory fields with field equality.
+		if !IsRegularMemory(f.Type) {
+			if typeCanPanic {
+				// Enforce ordering by starting a new set of reorderable conditions.
+				conds = append(conds, []ir.Node{})
+			}
+			switch {
+			case f.Type.IsString():
+				p := typecheck.DotField(base.Pos, typecheck.Expr(np), i)
+				q := typecheck.DotField(base.Pos, typecheck.Expr(nq), i)
+				eqlen, eqmem := EqString(p, q)
+				and(eqlen)
+				and(eqmem)
+			default:
+				and(eqfield(np, nq, i))
+			}
+			if typeCanPanic {
+				// Also enforce ordering after something that can panic.
+				conds = append(conds, []ir.Node{})
+			}
+			i++
+			continue
+		}
+
+		cost, size, next := eqStructFieldCost(t, i)
+		if cost <= 4 {
+			// Cost of 4 or less: use plain field equality.
+			for j := i; j < next; j++ {
+				and(eqfield(np, nq, j))
+			}
+		} else {
+			// Higher cost: use memequal.
+			cc := eqmem(np, nq, i, size)
+			and(cc)
+		}
+		i = next
+	}
+
+	// Sort conditions to put runtime calls last.
+	// Preserve the rest of the ordering.
+	var flatConds []ir.Node
+	for _, c := range conds {
+		isCall := func(n ir.Node) bool {
+			return n.Op() == ir.OCALL || n.Op() == ir.OCALLFUNC
+		}
+		sort.SliceStable(c, func(i, j int) bool {
+			return !isCall(c[i]) && isCall(c[j])
+		})
+		flatConds = append(flatConds, c...)
+	}
+	return flatConds, len(conds) > 1
+}
+
+// EqString returns the nodes
+//
+//	len(s) == len(t)
+//
+// and
+//
+//	memequal(s.ptr, t.ptr, len(s))
+//
+// which can be used to construct string equality comparison.
+// eqlen must be evaluated before eqmem, and shortcircuiting is required.
+func EqString(s, t ir.Node) (eqlen *ir.BinaryExpr, eqmem *ir.CallExpr) {
+	s = typecheck.Conv(s, types.Types[types.TSTRING])
+	t = typecheck.Conv(t, types.Types[types.TSTRING])
+	sptr := ir.NewUnaryExpr(base.Pos, ir.OSPTR, s)
+	tptr := ir.NewUnaryExpr(base.Pos, ir.OSPTR, t)
+	slen := typecheck.Conv(ir.NewUnaryExpr(base.Pos, ir.OLEN, s), types.Types[types.TUINTPTR])
+	tlen := typecheck.Conv(ir.NewUnaryExpr(base.Pos, ir.OLEN, t), types.Types[types.TUINTPTR])
+
+	// Pick the 3rd arg to memequal. Both slen and tlen are fine to use, because we short
+	// circuit the memequal call if they aren't the same. But if one is a constant some
+	// memequal optimizations are easier to apply.
+	probablyConstant := func(n ir.Node) bool {
+		if n.Op() == ir.OCONVNOP {
+			n = n.(*ir.ConvExpr).X
+		}
+		if n.Op() == ir.OLITERAL {
+			return true
+		}
+		if n.Op() != ir.ONAME {
+			return false
+		}
+		name := n.(*ir.Name)
+		if name.Class != ir.PAUTO {
+			return false
+		}
+		if def := name.Defn; def == nil {
+			// n starts out as the empty string
+			return true
+		} else if def.Op() == ir.OAS && (def.(*ir.AssignStmt).Y == nil || def.(*ir.AssignStmt).Y.Op() == ir.OLITERAL) {
+			// n starts out as a constant string
+			return true
+		}
+		return false
+	}
+	cmplen := slen
+	if probablyConstant(t) && !probablyConstant(s) {
+		cmplen = tlen
+	}
+
+	fn := typecheck.LookupRuntime("memequal", types.Types[types.TUINT8], types.Types[types.TUINT8])
+	call := typecheck.Call(base.Pos, fn, []ir.Node{sptr, tptr, ir.Copy(cmplen)}, false).(*ir.CallExpr)
+
+	cmp := ir.NewBinaryExpr(base.Pos, ir.OEQ, slen, tlen)
+	cmp = typecheck.Expr(cmp).(*ir.BinaryExpr)
+	cmp.SetType(types.Types[types.TBOOL])
+	return cmp, call
+}
+
+// EqInterface returns the nodes
+//
+//	s.tab == t.tab (or s.typ == t.typ, as appropriate)
+//
+// and
+//
+//	ifaceeq(s.tab, s.data, t.data) (or efaceeq(s.typ, s.data, t.data), as appropriate)
+//
+// which can be used to construct interface equality comparison.
+// eqtab must be evaluated before eqdata, and shortcircuiting is required.
+func EqInterface(s, t ir.Node) (eqtab *ir.BinaryExpr, eqdata *ir.CallExpr) {
+	if !types.Identical(s.Type(), t.Type()) {
+		base.Fatalf("EqInterface %v %v", s.Type(), t.Type())
+	}
+	// func ifaceeq(tab *uintptr, x, y unsafe.Pointer) (ret bool)
+	// func efaceeq(typ *uintptr, x, y unsafe.Pointer) (ret bool)
+	var fn ir.Node
+	if s.Type().IsEmptyInterface() {
+		fn = typecheck.LookupRuntime("efaceeq")
+	} else {
+		fn = typecheck.LookupRuntime("ifaceeq")
+	}
+
+	stab := ir.NewUnaryExpr(base.Pos, ir.OITAB, s)
+	ttab := ir.NewUnaryExpr(base.Pos, ir.OITAB, t)
+	sdata := ir.NewUnaryExpr(base.Pos, ir.OIDATA, s)
+	tdata := ir.NewUnaryExpr(base.Pos, ir.OIDATA, t)
+	sdata.SetType(types.Types[types.TUNSAFEPTR])
+	tdata.SetType(types.Types[types.TUNSAFEPTR])
+	sdata.SetTypecheck(1)
+	tdata.SetTypecheck(1)
+
+	call := typecheck.Call(base.Pos, fn, []ir.Node{stab, sdata, tdata}, false).(*ir.CallExpr)
+
+	cmp := ir.NewBinaryExpr(base.Pos, ir.OEQ, stab, ttab)
+	cmp = typecheck.Expr(cmp).(*ir.BinaryExpr)
+	cmp.SetType(types.Types[types.TBOOL])
+	return cmp, call
+}
+
+// eqfield returns the node
+//
+//	p.field == q.field
+func eqfield(p, q ir.Node, field int) ir.Node {
+	nx := typecheck.DotField(base.Pos, typecheck.Expr(p), field)
+	ny := typecheck.DotField(base.Pos, typecheck.Expr(q), field)
+	return typecheck.Expr(ir.NewBinaryExpr(base.Pos, ir.OEQ, nx, ny))
+}
+
+// eqmem returns the node
+//
+//	memequal(&p.field, &q.field, size)
+func eqmem(p, q ir.Node, field int, size int64) ir.Node {
+	nx := typecheck.Expr(typecheck.NodAddr(typecheck.DotField(base.Pos, p, field)))
+	ny := typecheck.Expr(typecheck.NodAddr(typecheck.DotField(base.Pos, q, field)))
+
+	fn, needsize := eqmemfunc(size, nx.Type().Elem())
+	call := ir.NewCallExpr(base.Pos, ir.OCALL, fn, nil)
+	call.Args.Append(nx)
+	call.Args.Append(ny)
+	if needsize {
+		call.Args.Append(ir.NewInt(base.Pos, size))
+	}
+
+	return call
+}
+
+func eqmemfunc(size int64, t *types.Type) (fn *ir.Name, needsize bool) {
+	switch size {
+	case 1, 2, 4, 8, 16:
+		buf := fmt.Sprintf("memequal%d", int(size)*8)
+		return typecheck.LookupRuntime(buf, t, t), false
+	}
+
+	return typecheck.LookupRuntime("memequal", t, t), true
+}