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