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