Adding upstream version 1.16.10.upstream/1.16.10upstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 484 insertions, 0 deletions

diff --git a/src/cmd/compile/internal/ssa/func_test.go b/src/cmd/compile/internal/ssa/func_test.go
new file mode 100644
index 0000000..568c643
--- /dev/null
+++ b/src/cmd/compile/internal/ssa/func_test.go
@@ -0,0 +1,484 @@
+// Copyright 2015 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.
+
+// This file contains some utility functions to help define Funcs for testing.
+// As an example, the following func
+//
+//   b1:
+//     v1 = InitMem <mem>
+//     Plain -> b2
+//   b2:
+//     Exit v1
+//   b3:
+//     v2 = Const <bool> [true]
+//     If v2 -> b3 b2
+//
+// can be defined as
+//
+//   fun := Fun("entry",
+//       Bloc("entry",
+//           Valu("mem", OpInitMem, types.TypeMem, 0, nil),
+//           Goto("exit")),
+//       Bloc("exit",
+//           Exit("mem")),
+//       Bloc("deadblock",
+//          Valu("deadval", OpConstBool, c.config.Types.Bool, 0, true),
+//          If("deadval", "deadblock", "exit")))
+//
+// and the Blocks or Values used in the Func can be accessed
+// like this:
+//   fun.blocks["entry"] or fun.values["deadval"]
+
+package ssa
+
+// TODO(matloob): Choose better names for Fun, Bloc, Goto, etc.
+// TODO(matloob): Write a parser for the Func disassembly. Maybe
+//                the parser can be used instead of Fun.
+
+import (
+	"cmd/compile/internal/types"
+	"cmd/internal/obj"
+	"cmd/internal/src"
+	"fmt"
+	"reflect"
+	"testing"
+)
+
+// Compare two Funcs for equivalence. Their CFGs must be isomorphic,
+// and their values must correspond.
+// Requires that values and predecessors are in the same order, even
+// though Funcs could be equivalent when they are not.
+// TODO(matloob): Allow values and predecessors to be in different
+// orders if the CFG are otherwise equivalent.
+func Equiv(f, g *Func) bool {
+	valcor := make(map[*Value]*Value)
+	var checkVal func(fv, gv *Value) bool
+	checkVal = func(fv, gv *Value) bool {
+		if fv == nil && gv == nil {
+			return true
+		}
+		if valcor[fv] == nil && valcor[gv] == nil {
+			valcor[fv] = gv
+			valcor[gv] = fv
+			// Ignore ids. Ops and Types are compared for equality.
+			// TODO(matloob): Make sure types are canonical and can
+			// be compared for equality.
+			if fv.Op != gv.Op || fv.Type != gv.Type || fv.AuxInt != gv.AuxInt {
+				return false
+			}
+			if !reflect.DeepEqual(fv.Aux, gv.Aux) {
+				// This makes the assumption that aux values can be compared
+				// using DeepEqual.
+				// TODO(matloob): Aux values may be *gc.Sym pointers in the near
+				// future. Make sure they are canonical.
+				return false
+			}
+			if len(fv.Args) != len(gv.Args) {
+				return false
+			}
+			for i := range fv.Args {
+				if !checkVal(fv.Args[i], gv.Args[i]) {
+					return false
+				}
+			}
+		}
+		return valcor[fv] == gv && valcor[gv] == fv
+	}
+	blkcor := make(map[*Block]*Block)
+	var checkBlk func(fb, gb *Block) bool
+	checkBlk = func(fb, gb *Block) bool {
+		if blkcor[fb] == nil && blkcor[gb] == nil {
+			blkcor[fb] = gb
+			blkcor[gb] = fb
+			// ignore ids
+			if fb.Kind != gb.Kind {
+				return false
+			}
+			if len(fb.Values) != len(gb.Values) {
+				return false
+			}
+			for i := range fb.Values {
+				if !checkVal(fb.Values[i], gb.Values[i]) {
+					return false
+				}
+			}
+			if len(fb.Succs) != len(gb.Succs) {
+				return false
+			}
+			for i := range fb.Succs {
+				if !checkBlk(fb.Succs[i].b, gb.Succs[i].b) {
+					return false
+				}
+			}
+			if len(fb.Preds) != len(gb.Preds) {
+				return false
+			}
+			for i := range fb.Preds {
+				if !checkBlk(fb.Preds[i].b, gb.Preds[i].b) {
+					return false
+				}
+			}
+			return true
+
+		}
+		return blkcor[fb] == gb && blkcor[gb] == fb
+	}
+
+	return checkBlk(f.Entry, g.Entry)
+}
+
+// fun is the return type of Fun. It contains the created func
+// itself as well as indexes from block and value names into the
+// corresponding Blocks and Values.
+type fun struct {
+	f      *Func
+	blocks map[string]*Block
+	values map[string]*Value
+}
+
+var emptyPass pass = pass{
+	name: "empty pass",
+}
+
+// AuxCallLSym returns an AuxCall initialized with an LSym that should pass "check"
+// as the Aux of a static call.
+func AuxCallLSym(name string) *AuxCall {
+	return &AuxCall{Fn: &obj.LSym{}}
+}
+
+// Fun takes the name of an entry bloc and a series of Bloc calls, and
+// returns a fun containing the composed Func. entry must be a name
+// supplied to one of the Bloc functions. Each of the bloc names and
+// valu names should be unique across the Fun.
+func (c *Conf) Fun(entry string, blocs ...bloc) fun {
+	f := NewFunc(c.Frontend())
+	f.Config = c.config
+	// TODO: Either mark some SSA tests as t.Parallel,
+	// or set up a shared Cache and Reset it between tests.
+	// But not both.
+	f.Cache = new(Cache)
+	f.pass = &emptyPass
+	f.cachedLineStarts = newXposmap(map[int]lineRange{0: {0, 100}, 1: {0, 100}, 2: {0, 100}, 3: {0, 100}, 4: {0, 100}})
+
+	blocks := make(map[string]*Block)
+	values := make(map[string]*Value)
+	// Create all the blocks and values.
+	for _, bloc := range blocs {
+		b := f.NewBlock(bloc.control.kind)
+		blocks[bloc.name] = b
+		for _, valu := range bloc.valus {
+			// args are filled in the second pass.
+			values[valu.name] = b.NewValue0IA(src.NoXPos, valu.op, valu.t, valu.auxint, valu.aux)
+		}
+	}
+	// Connect the blocks together and specify control values.
+	f.Entry = blocks[entry]
+	for _, bloc := range blocs {
+		b := blocks[bloc.name]
+		c := bloc.control
+		// Specify control values.
+		if c.control != "" {
+			cval, ok := values[c.control]
+			if !ok {
+				f.Fatalf("control value for block %s missing", bloc.name)
+			}
+			b.SetControl(cval)
+		}
+		// Fill in args.
+		for _, valu := range bloc.valus {
+			v := values[valu.name]
+			for _, arg := range valu.args {
+				a, ok := values[arg]
+				if !ok {
+					b.Fatalf("arg %s missing for value %s in block %s",
+						arg, valu.name, bloc.name)
+				}
+				v.AddArg(a)
+			}
+		}
+		// Connect to successors.
+		for _, succ := range c.succs {
+			b.AddEdgeTo(blocks[succ])
+		}
+	}
+	return fun{f, blocks, values}
+}
+
+// Bloc defines a block for Fun. The bloc name should be unique
+// across the containing Fun. entries should consist of calls to valu,
+// as well as one call to Goto, If, or Exit to specify the block kind.
+func Bloc(name string, entries ...interface{}) bloc {
+	b := bloc{}
+	b.name = name
+	seenCtrl := false
+	for _, e := range entries {
+		switch v := e.(type) {
+		case ctrl:
+			// there should be exactly one Ctrl entry.
+			if seenCtrl {
+				panic(fmt.Sprintf("already seen control for block %s", name))
+			}
+			b.control = v
+			seenCtrl = true
+		case valu:
+			b.valus = append(b.valus, v)
+		}
+	}
+	if !seenCtrl {
+		panic(fmt.Sprintf("block %s doesn't have control", b.name))
+	}
+	return b
+}
+
+// Valu defines a value in a block.
+func Valu(name string, op Op, t *types.Type, auxint int64, aux interface{}, args ...string) valu {
+	return valu{name, op, t, auxint, aux, args}
+}
+
+// Goto specifies that this is a BlockPlain and names the single successor.
+// TODO(matloob): choose a better name.
+func Goto(succ string) ctrl {
+	return ctrl{BlockPlain, "", []string{succ}}
+}
+
+// If specifies a BlockIf.
+func If(cond, sub, alt string) ctrl {
+	return ctrl{BlockIf, cond, []string{sub, alt}}
+}
+
+// Exit specifies a BlockExit.
+func Exit(arg string) ctrl {
+	return ctrl{BlockExit, arg, []string{}}
+}
+
+// Eq specifies a BlockAMD64EQ.
+func Eq(cond, sub, alt string) ctrl {
+	return ctrl{BlockAMD64EQ, cond, []string{sub, alt}}
+}
+
+// bloc, ctrl, and valu are internal structures used by Bloc, Valu, Goto,
+// If, and Exit to help define blocks.
+
+type bloc struct {
+	name    string
+	control ctrl
+	valus   []valu
+}
+
+type ctrl struct {
+	kind    BlockKind
+	control string
+	succs   []string
+}
+
+type valu struct {
+	name   string
+	op     Op
+	t      *types.Type
+	auxint int64
+	aux    interface{}
+	args   []string
+}
+
+func TestArgs(t *testing.T) {
+	c := testConfig(t)
+	fun := c.Fun("entry",
+		Bloc("entry",
+			Valu("a", OpConst64, c.config.Types.Int64, 14, nil),
+			Valu("b", OpConst64, c.config.Types.Int64, 26, nil),
+			Valu("sum", OpAdd64, c.config.Types.Int64, 0, nil, "a", "b"),
+			Valu("mem", OpInitMem, types.TypeMem, 0, nil),
+			Goto("exit")),
+		Bloc("exit",
+			Exit("mem")))
+	sum := fun.values["sum"]
+	for i, name := range []string{"a", "b"} {
+		if sum.Args[i] != fun.values[name] {
+			t.Errorf("arg %d for sum is incorrect: want %s, got %s",
+				i, sum.Args[i], fun.values[name])
+		}
+	}
+}
+
+func TestEquiv(t *testing.T) {
+	cfg := testConfig(t)
+	equivalentCases := []struct{ f, g fun }{
+		// simple case
+		{
+			cfg.Fun("entry",
+				Bloc("entry",
+					Valu("a", OpConst64, cfg.config.Types.Int64, 14, nil),
+					Valu("b", OpConst64, cfg.config.Types.Int64, 26, nil),
+					Valu("sum", OpAdd64, cfg.config.Types.Int64, 0, nil, "a", "b"),
+					Valu("mem", OpInitMem, types.TypeMem, 0, nil),
+					Goto("exit")),
+				Bloc("exit",
+					Exit("mem"))),
+			cfg.Fun("entry",
+				Bloc("entry",
+					Valu("a", OpConst64, cfg.config.Types.Int64, 14, nil),
+					Valu("b", OpConst64, cfg.config.Types.Int64, 26, nil),
+					Valu("sum", OpAdd64, cfg.config.Types.Int64, 0, nil, "a", "b"),
+					Valu("mem", OpInitMem, types.TypeMem, 0, nil),
+					Goto("exit")),
+				Bloc("exit",
+					Exit("mem"))),
+		},
+		// block order changed
+		{
+			cfg.Fun("entry",
+				Bloc("entry",
+					Valu("a", OpConst64, cfg.config.Types.Int64, 14, nil),
+					Valu("b", OpConst64, cfg.config.Types.Int64, 26, nil),
+					Valu("sum", OpAdd64, cfg.config.Types.Int64, 0, nil, "a", "b"),
+					Valu("mem", OpInitMem, types.TypeMem, 0, nil),
+					Goto("exit")),
+				Bloc("exit",
+					Exit("mem"))),
+			cfg.Fun("entry",
+				Bloc("exit",
+					Exit("mem")),
+				Bloc("entry",
+					Valu("a", OpConst64, cfg.config.Types.Int64, 14, nil),
+					Valu("b", OpConst64, cfg.config.Types.Int64, 26, nil),
+					Valu("sum", OpAdd64, cfg.config.Types.Int64, 0, nil, "a", "b"),
+					Valu("mem", OpInitMem, types.TypeMem, 0, nil),
+					Goto("exit"))),
+		},
+	}
+	for _, c := range equivalentCases {
+		if !Equiv(c.f.f, c.g.f) {
+			t.Error("expected equivalence. Func definitions:")
+			t.Error(c.f.f)
+			t.Error(c.g.f)
+		}
+	}
+
+	differentCases := []struct{ f, g fun }{
+		// different shape
+		{
+			cfg.Fun("entry",
+				Bloc("entry",
+					Valu("mem", OpInitMem, types.TypeMem, 0, nil),
+					Goto("exit")),
+				Bloc("exit",
+					Exit("mem"))),
+			cfg.Fun("entry",
+				Bloc("entry",
+					Valu("mem", OpInitMem, types.TypeMem, 0, nil),
+					Exit("mem"))),
+		},
+		// value order changed
+		{
+			cfg.Fun("entry",
+				Bloc("entry",
+					Valu("mem", OpInitMem, types.TypeMem, 0, nil),
+					Valu("b", OpConst64, cfg.config.Types.Int64, 26, nil),
+					Valu("a", OpConst64, cfg.config.Types.Int64, 14, nil),
+					Exit("mem"))),
+			cfg.Fun("entry",
+				Bloc("entry",
+					Valu("mem", OpInitMem, types.TypeMem, 0, nil),
+					Valu("a", OpConst64, cfg.config.Types.Int64, 14, nil),
+					Valu("b", OpConst64, cfg.config.Types.Int64, 26, nil),
+					Exit("mem"))),
+		},
+		// value auxint different
+		{
+			cfg.Fun("entry",
+				Bloc("entry",
+					Valu("mem", OpInitMem, types.TypeMem, 0, nil),
+					Valu("a", OpConst64, cfg.config.Types.Int64, 14, nil),
+					Exit("mem"))),
+			cfg.Fun("entry",
+				Bloc("entry",
+					Valu("mem", OpInitMem, types.TypeMem, 0, nil),
+					Valu("a", OpConst64, cfg.config.Types.Int64, 26, nil),
+					Exit("mem"))),
+		},
+		// value aux different
+		{
+			cfg.Fun("entry",
+				Bloc("entry",
+					Valu("mem", OpInitMem, types.TypeMem, 0, nil),
+					Valu("a", OpConst64, cfg.config.Types.Int64, 0, 14),
+					Exit("mem"))),
+			cfg.Fun("entry",
+				Bloc("entry",
+					Valu("mem", OpInitMem, types.TypeMem, 0, nil),
+					Valu("a", OpConst64, cfg.config.Types.Int64, 0, 26),
+					Exit("mem"))),
+		},
+		// value args different
+		{
+			cfg.Fun("entry",
+				Bloc("entry",
+					Valu("mem", OpInitMem, types.TypeMem, 0, nil),
+					Valu("a", OpConst64, cfg.config.Types.Int64, 14, nil),
+					Valu("b", OpConst64, cfg.config.Types.Int64, 26, nil),
+					Valu("sum", OpAdd64, cfg.config.Types.Int64, 0, nil, "a", "b"),
+					Exit("mem"))),
+			cfg.Fun("entry",
+				Bloc("entry",
+					Valu("mem", OpInitMem, types.TypeMem, 0, nil),
+					Valu("a", OpConst64, cfg.config.Types.Int64, 0, nil),
+					Valu("b", OpConst64, cfg.config.Types.Int64, 14, nil),
+					Valu("sum", OpAdd64, cfg.config.Types.Int64, 0, nil, "b", "a"),
+					Exit("mem"))),
+		},
+	}
+	for _, c := range differentCases {
+		if Equiv(c.f.f, c.g.f) {
+			t.Error("expected difference. Func definitions:")
+			t.Error(c.f.f)
+			t.Error(c.g.f)
+		}
+	}
+}
+
+// TestConstCache ensures that the cache will not return
+// reused free'd values with a non-matching AuxInt
+func TestConstCache(t *testing.T) {
+	c := testConfig(t)
+	f := c.Fun("entry",
+		Bloc("entry",
+			Valu("mem", OpInitMem, types.TypeMem, 0, nil),
+			Exit("mem")))
+	v1 := f.f.ConstBool(c.config.Types.Bool, false)
+	v2 := f.f.ConstBool(c.config.Types.Bool, true)
+	f.f.freeValue(v1)
+	f.f.freeValue(v2)
+	v3 := f.f.ConstBool(c.config.Types.Bool, false)
+	v4 := f.f.ConstBool(c.config.Types.Bool, true)
+	if v3.AuxInt != 0 {
+		t.Errorf("expected %s to have auxint of 0\n", v3.LongString())
+	}
+	if v4.AuxInt != 1 {
+		t.Errorf("expected %s to have auxint of 1\n", v4.LongString())
+	}
+
+}
+
+// opcodeMap returns a map from opcode to the number of times that opcode
+// appears in the function.
+func opcodeMap(f *Func) map[Op]int {
+	m := map[Op]int{}
+	for _, b := range f.Blocks {
+		for _, v := range b.Values {
+			m[v.Op]++
+		}
+	}
+	return m
+}
+
+// opcodeCounts checks that the number of opcodes listed in m agree with the
+// number of opcodes that appear in the function.
+func checkOpcodeCounts(t *testing.T, f *Func, m map[Op]int) {
+	n := opcodeMap(f)
+	for op, cnt := range m {
+		if n[op] != cnt {
+			t.Errorf("%s appears %d times, want %d times", op, n[op], cnt)
+		}
+	}
+}