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

View as plain text