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 ...interface{}) 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  // bloc, ctrl, and valu are internal structures used by Bloc, Valu, Goto,
   264  // If, and Exit to help define blocks.
   265  
   266  type bloc struct {
   267  	name    string
   268  	control ctrl
   269  	valus   []valu
   270  }
   271  
   272  type ctrl struct {
   273  	kind    BlockKind
   274  	control string
   275  	succs   []string
   276  }
   277  
   278  type valu struct {
   279  	name   string
   280  	op     Op
   281  	t      *types.Type
   282  	auxint int64
   283  	aux    Aux
   284  	args   []string
   285  }
   286  
   287  func TestArgs(t *testing.T) {
   288  	c := testConfig(t)
   289  	fun := c.Fun("entry",
   290  		Bloc("entry",
   291  			Valu("a", OpConst64, c.config.Types.Int64, 14, nil),
   292  			Valu("b", OpConst64, c.config.Types.Int64, 26, nil),
   293  			Valu("sum", OpAdd64, c.config.Types.Int64, 0, nil, "a", "b"),
   294  			Valu("mem", OpInitMem, types.TypeMem, 0, nil),
   295  			Goto("exit")),
   296  		Bloc("exit",
   297  			Exit("mem")))
   298  	sum := fun.values["sum"]
   299  	for i, name := range []string{"a", "b"} {
   300  		if sum.Args[i] != fun.values[name] {
   301  			t.Errorf("arg %d for sum is incorrect: want %s, got %s",
   302  				i, sum.Args[i], fun.values[name])
   303  		}
   304  	}
   305  }
   306  
   307  func TestEquiv(t *testing.T) {
   308  	cfg := testConfig(t)
   309  	equivalentCases := []struct{ f, g fun }{
   310  		// simple case
   311  		{
   312  			cfg.Fun("entry",
   313  				Bloc("entry",
   314  					Valu("a", OpConst64, cfg.config.Types.Int64, 14, nil),
   315  					Valu("b", OpConst64, cfg.config.Types.Int64, 26, nil),
   316  					Valu("sum", OpAdd64, cfg.config.Types.Int64, 0, nil, "a", "b"),
   317  					Valu("mem", OpInitMem, types.TypeMem, 0, nil),
   318  					Goto("exit")),
   319  				Bloc("exit",
   320  					Exit("mem"))),
   321  			cfg.Fun("entry",
   322  				Bloc("entry",
   323  					Valu("a", OpConst64, cfg.config.Types.Int64, 14, nil),
   324  					Valu("b", OpConst64, cfg.config.Types.Int64, 26, nil),
   325  					Valu("sum", OpAdd64, cfg.config.Types.Int64, 0, nil, "a", "b"),
   326  					Valu("mem", OpInitMem, types.TypeMem, 0, nil),
   327  					Goto("exit")),
   328  				Bloc("exit",
   329  					Exit("mem"))),
   330  		},
   331  		// block order changed
   332  		{
   333  			cfg.Fun("entry",
   334  				Bloc("entry",
   335  					Valu("a", OpConst64, cfg.config.Types.Int64, 14, nil),
   336  					Valu("b", OpConst64, cfg.config.Types.Int64, 26, nil),
   337  					Valu("sum", OpAdd64, cfg.config.Types.Int64, 0, nil, "a", "b"),
   338  					Valu("mem", OpInitMem, types.TypeMem, 0, nil),
   339  					Goto("exit")),
   340  				Bloc("exit",
   341  					Exit("mem"))),
   342  			cfg.Fun("entry",
   343  				Bloc("exit",
   344  					Exit("mem")),
   345  				Bloc("entry",
   346  					Valu("a", OpConst64, cfg.config.Types.Int64, 14, nil),
   347  					Valu("b", OpConst64, cfg.config.Types.Int64, 26, nil),
   348  					Valu("sum", OpAdd64, cfg.config.Types.Int64, 0, nil, "a", "b"),
   349  					Valu("mem", OpInitMem, types.TypeMem, 0, nil),
   350  					Goto("exit"))),
   351  		},
   352  	}
   353  	for _, c := range equivalentCases {
   354  		if !Equiv(c.f.f, c.g.f) {
   355  			t.Error("expected equivalence. Func definitions:")
   356  			t.Error(c.f.f)
   357  			t.Error(c.g.f)
   358  		}
   359  	}
   360  
   361  	differentCases := []struct{ f, g fun }{
   362  		// different shape
   363  		{
   364  			cfg.Fun("entry",
   365  				Bloc("entry",
   366  					Valu("mem", OpInitMem, types.TypeMem, 0, nil),
   367  					Goto("exit")),
   368  				Bloc("exit",
   369  					Exit("mem"))),
   370  			cfg.Fun("entry",
   371  				Bloc("entry",
   372  					Valu("mem", OpInitMem, types.TypeMem, 0, nil),
   373  					Exit("mem"))),
   374  		},
   375  		// value order changed
   376  		{
   377  			cfg.Fun("entry",
   378  				Bloc("entry",
   379  					Valu("mem", OpInitMem, types.TypeMem, 0, nil),
   380  					Valu("b", OpConst64, cfg.config.Types.Int64, 26, nil),
   381  					Valu("a", OpConst64, cfg.config.Types.Int64, 14, nil),
   382  					Exit("mem"))),
   383  			cfg.Fun("entry",
   384  				Bloc("entry",
   385  					Valu("mem", OpInitMem, types.TypeMem, 0, nil),
   386  					Valu("a", OpConst64, cfg.config.Types.Int64, 14, nil),
   387  					Valu("b", OpConst64, cfg.config.Types.Int64, 26, nil),
   388  					Exit("mem"))),
   389  		},
   390  		// value auxint different
   391  		{
   392  			cfg.Fun("entry",
   393  				Bloc("entry",
   394  					Valu("mem", OpInitMem, types.TypeMem, 0, nil),
   395  					Valu("a", OpConst64, cfg.config.Types.Int64, 14, nil),
   396  					Exit("mem"))),
   397  			cfg.Fun("entry",
   398  				Bloc("entry",
   399  					Valu("mem", OpInitMem, types.TypeMem, 0, nil),
   400  					Valu("a", OpConst64, cfg.config.Types.Int64, 26, nil),
   401  					Exit("mem"))),
   402  		},
   403  		// value aux different
   404  		{
   405  			cfg.Fun("entry",
   406  				Bloc("entry",
   407  					Valu("mem", OpInitMem, types.TypeMem, 0, nil),
   408  					Valu("a", OpConstString, cfg.config.Types.String, 0, StringToAux("foo")),
   409  					Exit("mem"))),
   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("bar")),
   414  					Exit("mem"))),
   415  		},
   416  		// value args different
   417  		{
   418  			cfg.Fun("entry",
   419  				Bloc("entry",
   420  					Valu("mem", OpInitMem, types.TypeMem, 0, nil),
   421  					Valu("a", OpConst64, cfg.config.Types.Int64, 14, nil),
   422  					Valu("b", OpConst64, cfg.config.Types.Int64, 26, nil),
   423  					Valu("sum", OpAdd64, cfg.config.Types.Int64, 0, nil, "a", "b"),
   424  					Exit("mem"))),
   425  			cfg.Fun("entry",
   426  				Bloc("entry",
   427  					Valu("mem", OpInitMem, types.TypeMem, 0, nil),
   428  					Valu("a", OpConst64, cfg.config.Types.Int64, 0, nil),
   429  					Valu("b", OpConst64, cfg.config.Types.Int64, 14, nil),
   430  					Valu("sum", OpAdd64, cfg.config.Types.Int64, 0, nil, "b", "a"),
   431  					Exit("mem"))),
   432  		},
   433  	}
   434  	for _, c := range differentCases {
   435  		if Equiv(c.f.f, c.g.f) {
   436  			t.Error("expected difference. Func definitions:")
   437  			t.Error(c.f.f)
   438  			t.Error(c.g.f)
   439  		}
   440  	}
   441  }
   442  
   443  // TestConstCache ensures that the cache will not return
   444  // reused free'd values with a non-matching AuxInt
   445  func TestConstCache(t *testing.T) {
   446  	c := testConfig(t)
   447  	f := c.Fun("entry",
   448  		Bloc("entry",
   449  			Valu("mem", OpInitMem, types.TypeMem, 0, nil),
   450  			Exit("mem")))
   451  	v1 := f.f.ConstBool(c.config.Types.Bool, false)
   452  	v2 := f.f.ConstBool(c.config.Types.Bool, true)
   453  	f.f.freeValue(v1)
   454  	f.f.freeValue(v2)
   455  	v3 := f.f.ConstBool(c.config.Types.Bool, false)
   456  	v4 := f.f.ConstBool(c.config.Types.Bool, true)
   457  	if v3.AuxInt != 0 {
   458  		t.Errorf("expected %s to have auxint of 0\n", v3.LongString())
   459  	}
   460  	if v4.AuxInt != 1 {
   461  		t.Errorf("expected %s to have auxint of 1\n", v4.LongString())
   462  	}
   463  
   464  }
   465  
   466  // opcodeMap returns a map from opcode to the number of times that opcode
   467  // appears in the function.
   468  func opcodeMap(f *Func) map[Op]int {
   469  	m := map[Op]int{}
   470  	for _, b := range f.Blocks {
   471  		for _, v := range b.Values {
   472  			m[v.Op]++
   473  		}
   474  	}
   475  	return m
   476  }
   477  
   478  // checkOpcodeCounts checks that the number of opcodes listed in m agree with the
   479  // number of opcodes that appear in the function.
   480  func checkOpcodeCounts(t *testing.T, f *Func, m map[Op]int) {
   481  	n := opcodeMap(f)
   482  	for op, cnt := range m {
   483  		if n[op] != cnt {
   484  			t.Errorf("%s appears %d times, want %d times", op, n[op], cnt)
   485  		}
   486  	}
   487  }
   488
View as plain text