From 73df946d56c74384511a194dd01dbe099584fd1a Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Sun, 28 Apr 2024 15:14:23 +0200 Subject: Adding upstream version 1.16.10. Signed-off-by: Daniel Baumann --- src/cmd/compile/internal/ssa/func_test.go | 484 ++++++++++++++++++++++++++++++ 1 file changed, 484 insertions(+) create mode 100644 src/cmd/compile/internal/ssa/func_test.go (limited to 'src/cmd/compile/internal/ssa/func_test.go') 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 +// Plain -> b2 +// b2: +// Exit v1 +// b3: +// v2 = Const [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) + } + } +} -- cgit v1.2.3