func_test.go

     1  // Copyright 2015 The Go Authors. All rights reserved.
     2  // Use of this source code is governed by a BSD-style
     3  // license that can be found in the LICENSE file.
     4  
     5  // This file contains some utility functions to help define Funcs for testing.
     6  // As an example, the following func
     7  //
     8  //   b1:
     9  //     v1 = InitMem <mem>
    10  //     Plain -> b2
    11  //   b2:
    12  //     Exit v1
    13  //   b3:
    14  //     v2 = Const <bool> [true]
    15  //     If v2 -> b3 b2
    16  //
    17  // can be defined as
    18  //
    19  //   fun := Fun("entry",
    20  //       Bloc("entry",
    21  //           Valu("mem", OpInitMem, types.TypeMem, 0, nil),
    22  //           Goto("exit")),
    23  //       Bloc("exit",
    24  //           Exit("mem")),
    25  //       Bloc("deadblock",
    26  //          Valu("deadval", OpConstBool, c.config.Types.Bool, 0, true),
    27  //          If("deadval", "deadblock", "exit")))
    28  //
    29  // and the Blocks or Values used in the Func can be accessed
    30  // like this:
    31  //   fun.blocks["entry"] or fun.values["deadval"]
    32  
    33  package ssacompile
    34  
    35  import (
    36  	"fmt"
    37  	"reflect"
    38  	"testing"
    39  
    40  	"cmd/compile/internal/ssa"
    41  	"cmd/compile/internal/ssa/block"
    42  	"cmd/compile/internal/ssa/ssaop"
    43  	"cmd/compile/internal/types"
    44  	"cmd/internal/obj"
    45  	"cmd/internal/src"
    46  )
    47  
    48  // TODO(matloob): Choose better names for Fun, Bloc, Goto, etc.
    49  // TODO(matloob): Write a parser for the Func disassembly. Maybe
    50  // the parser can be used instead of Fun.
    51  
    52  // Compare two Funcs for equivalence. Their CFGs must be isomorphic,
    53  // and their values must correspond.
    54  // Requires that values and predecessors are in the same order, even
    55  // though Funcs could be equivalent when they are not.
    56  // TODO(matloob): Allow values and predecessors to be in different
    57  // orders if the CFG are otherwise equivalent.
    58  func Equiv(f, g *ssa.Func) bool {
    59  	valcor := make(map[*ssa.Value]*ssa.Value)
    60  	var checkVal func(fv, gv *ssa.Value) bool
    61  	checkVal = func(fv, gv *ssa.Value) bool {
    62  		if fv == nil && gv == nil {
    63  			return true
    64  		}
    65  		if valcor[fv] == nil && valcor[gv] == nil {
    66  			valcor[fv] = gv
    67  			valcor[gv] = fv
    68  			// Ignore ids. Ops and Types are compared for equality.
    69  			// TODO(matloob): Make sure types are canonical and can
    70  			// be compared for equality.
    71  			if fv.Op != gv.Op || fv.Type != gv.Type || fv.AuxInt != gv.AuxInt {
    72  				return false
    73  			}
    74  			if !reflect.DeepEqual(fv.Aux, gv.Aux) {
    75  				// This makes the assumption that aux values can be compared
    76  				// using DeepEqual.
    77  				// TODO(matloob): Aux values may be *gc.Sym pointers in the near
    78  				// future. Make sure they are canonical.
    79  				return false
    80  			}
    81  			if len(fv.Args) != len(gv.Args) {
    82  				return false
    83  			}
    84  			for i := range fv.Args {
    85  				if !checkVal(fv.Args[i], gv.Args[i]) {
    86  					return false
    87  				}
    88  			}
    89  		}
    90  		return valcor[fv] == gv && valcor[gv] == fv
    91  	}
    92  	blkcor := make(map[*ssa.Block]*ssa.Block)
    93  	var checkBlk func(fb, gb *ssa.Block) bool
    94  	checkBlk = func(fb, gb *ssa.Block) bool {
    95  		if blkcor[fb] == nil && blkcor[gb] == nil {
    96  			blkcor[fb] = gb
    97  			blkcor[gb] = fb
    98  			// ignore ids
    99  			if fb.Kind != gb.Kind {
   100  				return false
   101  			}
   102  			if len(fb.Values) != len(gb.Values) {
   103  				return false
   104  			}
   105  			for i := range fb.Values {
   106  				if !checkVal(fb.Values[i], gb.Values[i]) {
   107  					return false
   108  				}
   109  			}
   110  			if len(fb.Succs) != len(gb.Succs) {
   111  				return false
   112  			}
   113  			for i := range fb.Succs {
   114  				if !checkBlk(fb.Succs[i].B, gb.Succs[i].B) {
   115  					return false
   116  				}
   117  			}
   118  			if len(fb.Preds) != len(gb.Preds) {
   119  				return false
   120  			}
   121  			for i := range fb.Preds {
   122  				if !checkBlk(fb.Preds[i].B, gb.Preds[i].B) {
   123  					return false
   124  				}
   125  			}
   126  			return true
   127  
   128  		}
   129  		return blkcor[fb] == gb && blkcor[gb] == fb
   130  	}
   131  
   132  	return checkBlk(f.Entry, g.Entry)
   133  }
   134  
   135  // fun is the return type of Fun. It contains the created func
   136  // itself as well as indexes from block and value names into the
   137  // corresponding Blocks and Values.
   138  type fun struct {
   139  	f      *ssa.Func
   140  	blocks map[string]*ssa.Block
   141  	values map[string]*ssa.Value
   142  }
   143  
   144  var emptyPass ssa.Pass = ssa.Pass{
   145  	Name: "empty pass",
   146  }
   147  
   148  // AuxCallLSym returns an AuxCall initialized with an LSym that should pass "check"
   149  // as the Aux of a static call.
   150  func AuxCallLSym(name string) *ssa.AuxCall {
   151  	return &ssa.AuxCall{Fn: &obj.LSym{}}
   152  }
   153  
   154  // Fun takes the name of an entry bloc and a series of Bloc calls, and
   155  // returns a fun containing the composed Func. entry must be a name
   156  // supplied to one of the Bloc functions. Each of the bloc names and
   157  // valu names should be unique across the Fun.
   158  func (c *Conf) Fun(entry string, blocs ...bloc) fun {
   159  	// TODO: Either mark some SSA tests as t.Parallel,
   160  	// or set up a shared Cache and Reset it between tests.
   161  	// But not both.
   162  	f := c.config.NewFunc(c.Frontend(), new(ssa.Cache))
   163  	f.Pass = &emptyPass
   164  	f.CachedLineStarts = ssa.NewXPosMap(map[int]ssa.LineRange{0: {First: 0, Last: 100}, 1: {First: 0, Last: 100}, 2: {First: 0, Last: 100}, 3: {First: 0, Last: 100}, 4: {First: 0, Last: 100}})
   165  
   166  	blocks := make(map[string]*ssa.Block)
   167  	values := make(map[string]*ssa.Value)
   168  	// Create all the blocks and values.
   169  	for _, bloc := range blocs {
   170  		b := f.NewBlock(bloc.control.kind)
   171  		blocks[bloc.name] = b
   172  		for _, valu := range bloc.valus {
   173  			// args are filled in the second pass.
   174  			values[valu.name] = b.NewValue0IA(src.NoXPos, valu.op, valu.t, valu.auxint, valu.aux)
   175  		}
   176  	}
   177  	// Connect the blocks together and specify control values.
   178  	f.Entry = blocks[entry]
   179  	for _, bloc := range blocs {
   180  		b := blocks[bloc.name]
   181  		c := bloc.control
   182  		// Specify control values.
   183  		if c.control != "" {
   184  			cval, ok := values[c.control]
   185  			if !ok {
   186  				f.Fatalf("control value for block %s missing", bloc.name)
   187  			}
   188  			b.SetControl(cval)
   189  		}
   190  		// Fill in args.
   191  		for _, valu := range bloc.valus {
   192  			v := values[valu.name]
   193  			for _, arg := range valu.args {
   194  				a, ok := values[arg]
   195  				if !ok {
   196  					b.Fatalf("arg %s missing for value %s in block %s",
   197  						arg, valu.name, bloc.name)
   198  				}
   199  				v.AddArg(a)
   200  			}
   201  		}
   202  		// Connect to successors.
   203  		for _, succ := range c.succs {
   204  			b.AddEdgeTo(blocks[succ])
   205  		}
   206  	}
   207  	return fun{f, blocks, values}
   208  }
   209  
   210  // Bloc defines a block for Fun. The bloc name should be unique
   211  // across the containing Fun. entries should consist of calls to valu,
   212  // as well as one call to Goto, If, or Exit to specify the block kind.
   213  func Bloc(name string, entries ...any) bloc {
   214  	b := bloc{}
   215  	b.name = name
   216  	seenCtrl := false
   217  	for _, e := range entries {
   218  		switch v := e.(type) {
   219  		case ctrl:
   220  			// there should be exactly one Ctrl entry.
   221  			if seenCtrl {
   222  				panic(fmt.Sprintf("already seen control for block %s", name))
   223  			}
   224  			b.control = v
   225  			seenCtrl = true
   226  		case valu:
   227  			b.valus = append(b.valus, v)
   228  		}
   229  	}
   230  	if !seenCtrl {
   231  		panic(fmt.Sprintf("block %s doesn't have control", b.name))
   232  	}
   233  	return b
   234  }
   235  
   236  // Valu defines a value in a block.
   237  func Valu(name string, op ssaop.Op, t *types.Type, auxint int64, aux ssa.Aux, args ...string) valu {
   238  	return valu{name, op, t, auxint, aux, args}
   239  }
   240  
   241  // Goto specifies that this is a BlockPlain and names the single successor.
   242  // TODO(matloob): choose a better name.
   243  func Goto(succ string) ctrl {
   244  	return ctrl{block.BlockPlain, "", []string{succ}}
   245  }
   246  
   247  // If specifies a BlockIf.
   248  func If(cond, sub, alt string) ctrl {
   249  	return ctrl{block.BlockIf, cond, []string{sub, alt}}
   250  }
   251  
   252  // Exit specifies a BlockExit.
   253  func Exit(arg string) ctrl {
   254  	return ctrl{block.BlockExit, arg, []string{}}
   255  }
   256  
   257  // Ret specifies a BlockRet.
   258  func Ret(arg string) ctrl {
   259  	return ctrl{block.BlockRet, arg, []string{}}
   260  }
   261  
   262  // Eq specifies a BlockAMD64EQ.
   263  func Eq(cond, sub, alt string) ctrl {
   264  	return ctrl{block.BlockAMD64EQ, cond, []string{sub, alt}}
   265  }
   266  
   267  // Lt specifies a BlockAMD64LT.
   268  func Lt(cond, yes, no string) ctrl {
   269  	return ctrl{block.BlockAMD64LT, cond, []string{yes, no}}
   270  }
   271  
   272  // bloc, ctrl, and valu are internal structures used by Bloc, Valu, Goto,
   273  // If, and Exit to help define blocks.
   274  
   275  type bloc struct {
   276  	name    string
   277  	control ctrl
   278  	valus   []valu
   279  }
   280  
   281  type ctrl struct {
   282  	kind    block.BlockKind
   283  	control string
   284  	succs   []string
   285  }
   286  
   287  type valu struct {
   288  	name   string
   289  	op     ssaop.Op
   290  	t      *types.Type
   291  	auxint int64
   292  	aux    ssa.Aux
   293  	args   []string
   294  }
   295  
   296  func TestArgs(t *testing.T) {
   297  	c := testConfig(t)
   298  	fun := c.Fun("entry",
   299  		Bloc("entry",
   300  			Valu("a", ssaop.OpConst64, c.config.Types.Int64, 14, nil),
   301  			Valu("b", ssaop.OpConst64, c.config.Types.Int64, 26, nil),
   302  			Valu("sum", ssaop.OpAdd64, c.config.Types.Int64, 0, nil, "a", "b"),
   303  			Valu("mem", ssaop.OpInitMem, types.TypeMem, 0, nil),
   304  			Goto("exit")),
   305  		Bloc("exit",
   306  			Exit("mem")))
   307  	sum := fun.values["sum"]
   308  	for i, name := range []string{"a", "b"} {
   309  		if sum.Args[i] != fun.values[name] {
   310  			t.Errorf("arg %d for sum is incorrect: want %s, got %s",
   311  				i, sum.Args[i], fun.values[name])
   312  		}
   313  	}
   314  }
   315  
   316  func TestEquiv(t *testing.T) {
   317  	cfg := testConfig(t)
   318  	equivalentCases := []struct{ f, g fun }{
   319  		// simple case
   320  		{
   321  			cfg.Fun("entry",
   322  				Bloc("entry",
   323  					Valu("a", ssaop.OpConst64, cfg.config.Types.Int64, 14, nil),
   324  					Valu("b", ssaop.OpConst64, cfg.config.Types.Int64, 26, nil),
   325  					Valu("sum", ssaop.OpAdd64, cfg.config.Types.Int64, 0, nil, "a", "b"),
   326  					Valu("mem", ssaop.OpInitMem, types.TypeMem, 0, nil),
   327  					Goto("exit")),
   328  				Bloc("exit",
   329  					Exit("mem"))),
   330  			cfg.Fun("entry",
   331  				Bloc("entry",
   332  					Valu("a", ssaop.OpConst64, cfg.config.Types.Int64, 14, nil),
   333  					Valu("b", ssaop.OpConst64, cfg.config.Types.Int64, 26, nil),
   334  					Valu("sum", ssaop.OpAdd64, cfg.config.Types.Int64, 0, nil, "a", "b"),
   335  					Valu("mem", ssaop.OpInitMem, types.TypeMem, 0, nil),
   336  					Goto("exit")),
   337  				Bloc("exit",
   338  					Exit("mem"))),
   339  		},
   340  		// block order changed
   341  		{
   342  			cfg.Fun("entry",
   343  				Bloc("entry",
   344  					Valu("a", ssaop.OpConst64, cfg.config.Types.Int64, 14, nil),
   345  					Valu("b", ssaop.OpConst64, cfg.config.Types.Int64, 26, nil),
   346  					Valu("sum", ssaop.OpAdd64, cfg.config.Types.Int64, 0, nil, "a", "b"),
   347  					Valu("mem", ssaop.OpInitMem, types.TypeMem, 0, nil),
   348  					Goto("exit")),
   349  				Bloc("exit",
   350  					Exit("mem"))),
   351  			cfg.Fun("entry",
   352  				Bloc("exit",
   353  					Exit("mem")),
   354  				Bloc("entry",
   355  					Valu("a", ssaop.OpConst64, cfg.config.Types.Int64, 14, nil),
   356  					Valu("b", ssaop.OpConst64, cfg.config.Types.Int64, 26, nil),
   357  					Valu("sum", ssaop.OpAdd64, cfg.config.Types.Int64, 0, nil, "a", "b"),
   358  					Valu("mem", ssaop.OpInitMem, types.TypeMem, 0, nil),
   359  					Goto("exit"))),
   360  		},
   361  	}
   362  	for _, c := range equivalentCases {
   363  		if !Equiv(c.f.f, c.g.f) {
   364  			t.Error("expected equivalence. Func definitions:")
   365  			t.Error(c.f.f)
   366  			t.Error(c.g.f)
   367  		}
   368  	}
   369  
   370  	differentCases := []struct{ f, g fun }{
   371  		// different shape
   372  		{
   373  			cfg.Fun("entry",
   374  				Bloc("entry",
   375  					Valu("mem", ssaop.OpInitMem, types.TypeMem, 0, nil),
   376  					Goto("exit")),
   377  				Bloc("exit",
   378  					Exit("mem"))),
   379  			cfg.Fun("entry",
   380  				Bloc("entry",
   381  					Valu("mem", ssaop.OpInitMem, types.TypeMem, 0, nil),
   382  					Exit("mem"))),
   383  		},
   384  		// value order changed
   385  		{
   386  			cfg.Fun("entry",
   387  				Bloc("entry",
   388  					Valu("mem", ssaop.OpInitMem, types.TypeMem, 0, nil),
   389  					Valu("b", ssaop.OpConst64, cfg.config.Types.Int64, 26, nil),
   390  					Valu("a", ssaop.OpConst64, cfg.config.Types.Int64, 14, nil),
   391  					Exit("mem"))),
   392  			cfg.Fun("entry",
   393  				Bloc("entry",
   394  					Valu("mem", ssaop.OpInitMem, types.TypeMem, 0, nil),
   395  					Valu("a", ssaop.OpConst64, cfg.config.Types.Int64, 14, nil),
   396  					Valu("b", ssaop.OpConst64, cfg.config.Types.Int64, 26, nil),
   397  					Exit("mem"))),
   398  		},
   399  		// value auxint different
   400  		{
   401  			cfg.Fun("entry",
   402  				Bloc("entry",
   403  					Valu("mem", ssaop.OpInitMem, types.TypeMem, 0, nil),
   404  					Valu("a", ssaop.OpConst64, cfg.config.Types.Int64, 14, nil),
   405  					Exit("mem"))),
   406  			cfg.Fun("entry",
   407  				Bloc("entry",
   408  					Valu("mem", ssaop.OpInitMem, types.TypeMem, 0, nil),
   409  					Valu("a", ssaop.OpConst64, cfg.config.Types.Int64, 26, nil),
   410  					Exit("mem"))),
   411  		},
   412  		// value aux different
   413  		{
   414  			cfg.Fun("entry",
   415  				Bloc("entry",
   416  					Valu("mem", ssaop.OpInitMem, types.TypeMem, 0, nil),
   417  					Valu("a", ssaop.OpConstString, cfg.config.Types.String, 0, ssa.StringToAux("foo")),
   418  					Exit("mem"))),
   419  			cfg.Fun("entry",
   420  				Bloc("entry",
   421  					Valu("mem", ssaop.OpInitMem, types.TypeMem, 0, nil),
   422  					Valu("a", ssaop.OpConstString, cfg.config.Types.String, 0, ssa.StringToAux("bar")),
   423  					Exit("mem"))),
   424  		},
   425  		// value args different
   426  		{
   427  			cfg.Fun("entry",
   428  				Bloc("entry",
   429  					Valu("mem", ssaop.OpInitMem, types.TypeMem, 0, nil),
   430  					Valu("a", ssaop.OpConst64, cfg.config.Types.Int64, 14, nil),
   431  					Valu("b", ssaop.OpConst64, cfg.config.Types.Int64, 26, nil),
   432  					Valu("sum", ssaop.OpAdd64, cfg.config.Types.Int64, 0, nil, "a", "b"),
   433  					Exit("mem"))),
   434  			cfg.Fun("entry",
   435  				Bloc("entry",
   436  					Valu("mem", ssaop.OpInitMem, types.TypeMem, 0, nil),
   437  					Valu("a", ssaop.OpConst64, cfg.config.Types.Int64, 0, nil),
   438  					Valu("b", ssaop.OpConst64, cfg.config.Types.Int64, 14, nil),
   439  					Valu("sum", ssaop.OpAdd64, cfg.config.Types.Int64, 0, nil, "b", "a"),
   440  					Exit("mem"))),
   441  		},
   442  	}
   443  	for _, c := range differentCases {
   444  		if Equiv(c.f.f, c.g.f) {
   445  			t.Error("expected difference. Func definitions:")
   446  			t.Error(c.f.f)
   447  			t.Error(c.g.f)
   448  		}
   449  	}
   450  }
   451  
   452  // TestConstCache ensures that the cache will not return
   453  // reused free'd values with a non-matching AuxInt
   454  func TestConstCache(t *testing.T) {
   455  	c := testConfig(t)
   456  	f := c.Fun("entry",
   457  		Bloc("entry",
   458  			Valu("mem", ssaop.OpInitMem, types.TypeMem, 0, nil),
   459  			Exit("mem")))
   460  	v1 := f.f.ConstBool(c.config.Types.Bool, false)
   461  	v2 := f.f.ConstBool(c.config.Types.Bool, true)
   462  	f.f.FreeValue(v1)
   463  	f.f.FreeValue(v2)
   464  	v3 := f.f.ConstBool(c.config.Types.Bool, false)
   465  	v4 := f.f.ConstBool(c.config.Types.Bool, true)
   466  	if v3.AuxInt != 0 {
   467  		t.Errorf("expected %s to have auxint of 0\n", v3.LongString())
   468  	}
   469  	if v4.AuxInt != 1 {
   470  		t.Errorf("expected %s to have auxint of 1\n", v4.LongString())
   471  	}
   472  
   473  }
   474  
   475  // opcodeMap returns a map from opcode to the number of times that opcode
   476  // appears in the function.
   477  func opcodeMap(f *ssa.Func) map[ssaop.Op]int {
   478  	m := map[ssaop.Op]int{}
   479  	for _, b := range f.Blocks {
   480  		for _, v := range b.Values {
   481  			m[v.Op]++
   482  		}
   483  	}
   484  	return m
   485  }
   486  
   487  // checkOpcodeCounts checks that the number of opcodes listed in m agree with the
   488  // number of opcodes that appear in the function.
   489  func checkOpcodeCounts(t *testing.T, f *ssa.Func, m map[ssaop.Op]int) {
   490  	n := opcodeMap(f)
   491  	for op, cnt := range m {
   492  		if n[op] != cnt {
   493  			t.Errorf("%s appears %d times, want %d times", op, n[op], cnt)
   494  		}
   495  	}
   496  }
   497
View as plain text