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  	f := NewFunc(c.Frontend())
   156  	f.Config = c.config
   157  	// TODO: Either mark some SSA tests as t.Parallel,
   158  	// or set up a shared Cache and Reset it between tests.
   159  	// But not both.
   160  	f.Cache = new(Cache)
   161  	f.pass = &emptyPass
   162  	f.cachedLineStarts = newXposmap(map[int]lineRange{0: {0, 100}, 1: {0, 100}, 2: {0, 100}, 3: {0, 100}, 4: {0, 100}})
   163  
   164  	blocks := make(map[string]*Block)
   165  	values := make(map[string]*Value)
   166  	// Create all the blocks and values.
   167  	for _, bloc := range blocs {
   168  		b := f.NewBlock(bloc.control.kind)
   169  		blocks[bloc.name] = b
   170  		for _, valu := range bloc.valus {
   171  			// args are filled in the second pass.
   172  			values[valu.name] = b.NewValue0IA(src.NoXPos, valu.op, valu.t, valu.auxint, valu.aux)
   173  		}
   174  	}
   175  	// Connect the blocks together and specify control values.
   176  	f.Entry = blocks[entry]
   177  	for _, bloc := range blocs {
   178  		b := blocks[bloc.name]
   179  		c := bloc.control
   180  		// Specify control values.
   181  		if c.control != "" {
   182  			cval, ok := values[c.control]
   183  			if !ok {
   184  				f.Fatalf("control value for block %s missing", bloc.name)
   185  			}
   186  			b.SetControl(cval)
   187  		}
   188  		// Fill in args.
   189  		for _, valu := range bloc.valus {
   190  			v := values[valu.name]
   191  			for _, arg := range valu.args {
   192  				a, ok := values[arg]
   193  				if !ok {
   194  					b.Fatalf("arg %s missing for value %s in block %s",
   195  						arg, valu.name, bloc.name)
   196  				}
   197  				v.AddArg(a)
   198  			}
   199  		}
   200  		// Connect to successors.
   201  		for _, succ := range c.succs {
   202  			b.AddEdgeTo(blocks[succ])
   203  		}
   204  	}
   205  	return fun{f, blocks, values}
   206  }
   207  
   208  // Bloc defines a block for Fun. The bloc name should be unique
   209  // across the containing Fun. entries should consist of calls to valu,
   210  // as well as one call to Goto, If, or Exit to specify the block kind.
   211  func Bloc(name string, entries ...interface{}) bloc {
   212  	b := bloc{}
   213  	b.name = name
   214  	seenCtrl := false
   215  	for _, e := range entries {
   216  		switch v := e.(type) {
   217  		case ctrl:
   218  			// there should be exactly one Ctrl entry.
   219  			if seenCtrl {
   220  				panic(fmt.Sprintf("already seen control for block %s", name))
   221  			}
   222  			b.control = v
   223  			seenCtrl = true
   224  		case valu:
   225  			b.valus = append(b.valus, v)
   226  		}
   227  	}
   228  	if !seenCtrl {
   229  		panic(fmt.Sprintf("block %s doesn't have control", b.name))
   230  	}
   231  	return b
   232  }
   233  
   234  // Valu defines a value in a block.
   235  func Valu(name string, op Op, t *types.Type, auxint int64, aux Aux, args ...string) valu {
   236  	return valu{name, op, t, auxint, aux, args}
   237  }
   238  
   239  // Goto specifies that this is a BlockPlain and names the single successor.
   240  // TODO(matloob): choose a better name.
   241  func Goto(succ string) ctrl {
   242  	return ctrl{BlockPlain, "", []string{succ}}
   243  }
   244  
   245  // If specifies a BlockIf.
   246  func If(cond, sub, alt string) ctrl {
   247  	return ctrl{BlockIf, cond, []string{sub, alt}}
   248  }
   249  
   250  // Exit specifies a BlockExit.
   251  func Exit(arg string) ctrl {
   252  	return ctrl{BlockExit, arg, []string{}}
   253  }
   254  
   255  // Eq specifies a BlockAMD64EQ.
   256  func Eq(cond, sub, alt string) ctrl {
   257  	return ctrl{BlockAMD64EQ, cond, []string{sub, alt}}
   258  }
   259  
   260  // bloc, ctrl, and valu are internal structures used by Bloc, Valu, Goto,
   261  // If, and Exit to help define blocks.
   262  
   263  type bloc struct {
   264  	name    string
   265  	control ctrl
   266  	valus   []valu
   267  }
   268  
   269  type ctrl struct {
   270  	kind    BlockKind
   271  	control string
   272  	succs   []string
   273  }
   274  
   275  type valu struct {
   276  	name   string
   277  	op     Op
   278  	t      *types.Type
   279  	auxint int64
   280  	aux    Aux
   281  	args   []string
   282  }
   283  
   284  func TestArgs(t *testing.T) {
   285  	c := testConfig(t)
   286  	fun := c.Fun("entry",
   287  		Bloc("entry",
   288  			Valu("a", OpConst64, c.config.Types.Int64, 14, nil),
   289  			Valu("b", OpConst64, c.config.Types.Int64, 26, nil),
   290  			Valu("sum", OpAdd64, c.config.Types.Int64, 0, nil, "a", "b"),
   291  			Valu("mem", OpInitMem, types.TypeMem, 0, nil),
   292  			Goto("exit")),
   293  		Bloc("exit",
   294  			Exit("mem")))
   295  	sum := fun.values["sum"]
   296  	for i, name := range []string{"a", "b"} {
   297  		if sum.Args[i] != fun.values[name] {
   298  			t.Errorf("arg %d for sum is incorrect: want %s, got %s",
   299  				i, sum.Args[i], fun.values[name])
   300  		}
   301  	}
   302  }
   303  
   304  func TestEquiv(t *testing.T) {
   305  	cfg := testConfig(t)
   306  	equivalentCases := []struct{ f, g fun }{
   307  		// simple case
   308  		{
   309  			cfg.Fun("entry",
   310  				Bloc("entry",
   311  					Valu("a", OpConst64, cfg.config.Types.Int64, 14, nil),
   312  					Valu("b", OpConst64, cfg.config.Types.Int64, 26, nil),
   313  					Valu("sum", OpAdd64, cfg.config.Types.Int64, 0, nil, "a", "b"),
   314  					Valu("mem", OpInitMem, types.TypeMem, 0, nil),
   315  					Goto("exit")),
   316  				Bloc("exit",
   317  					Exit("mem"))),
   318  			cfg.Fun("entry",
   319  				Bloc("entry",
   320  					Valu("a", OpConst64, cfg.config.Types.Int64, 14, nil),
   321  					Valu("b", OpConst64, cfg.config.Types.Int64, 26, nil),
   322  					Valu("sum", OpAdd64, cfg.config.Types.Int64, 0, nil, "a", "b"),
   323  					Valu("mem", OpInitMem, types.TypeMem, 0, nil),
   324  					Goto("exit")),
   325  				Bloc("exit",
   326  					Exit("mem"))),
   327  		},
   328  		// block order changed
   329  		{
   330  			cfg.Fun("entry",
   331  				Bloc("entry",
   332  					Valu("a", OpConst64, cfg.config.Types.Int64, 14, nil),
   333  					Valu("b", OpConst64, cfg.config.Types.Int64, 26, nil),
   334  					Valu("sum", OpAdd64, cfg.config.Types.Int64, 0, nil, "a", "b"),
   335  					Valu("mem", OpInitMem, types.TypeMem, 0, nil),
   336  					Goto("exit")),
   337  				Bloc("exit",
   338  					Exit("mem"))),
   339  			cfg.Fun("entry",
   340  				Bloc("exit",
   341  					Exit("mem")),
   342  				Bloc("entry",
   343  					Valu("a", OpConst64, cfg.config.Types.Int64, 14, nil),
   344  					Valu("b", OpConst64, cfg.config.Types.Int64, 26, nil),
   345  					Valu("sum", OpAdd64, cfg.config.Types.Int64, 0, nil, "a", "b"),
   346  					Valu("mem", OpInitMem, types.TypeMem, 0, nil),
   347  					Goto("exit"))),
   348  		},
   349  	}
   350  	for _, c := range equivalentCases {
   351  		if !Equiv(c.f.f, c.g.f) {
   352  			t.Error("expected equivalence. Func definitions:")
   353  			t.Error(c.f.f)
   354  			t.Error(c.g.f)
   355  		}
   356  	}
   357  
   358  	differentCases := []struct{ f, g fun }{
   359  		// different shape
   360  		{
   361  			cfg.Fun("entry",
   362  				Bloc("entry",
   363  					Valu("mem", OpInitMem, types.TypeMem, 0, nil),
   364  					Goto("exit")),
   365  				Bloc("exit",
   366  					Exit("mem"))),
   367  			cfg.Fun("entry",
   368  				Bloc("entry",
   369  					Valu("mem", OpInitMem, types.TypeMem, 0, nil),
   370  					Exit("mem"))),
   371  		},
   372  		// value order changed
   373  		{
   374  			cfg.Fun("entry",
   375  				Bloc("entry",
   376  					Valu("mem", OpInitMem, types.TypeMem, 0, nil),
   377  					Valu("b", OpConst64, cfg.config.Types.Int64, 26, nil),
   378  					Valu("a", OpConst64, cfg.config.Types.Int64, 14, nil),
   379  					Exit("mem"))),
   380  			cfg.Fun("entry",
   381  				Bloc("entry",
   382  					Valu("mem", OpInitMem, types.TypeMem, 0, nil),
   383  					Valu("a", OpConst64, cfg.config.Types.Int64, 14, nil),
   384  					Valu("b", OpConst64, cfg.config.Types.Int64, 26, nil),
   385  					Exit("mem"))),
   386  		},
   387  		// value auxint different
   388  		{
   389  			cfg.Fun("entry",
   390  				Bloc("entry",
   391  					Valu("mem", OpInitMem, types.TypeMem, 0, nil),
   392  					Valu("a", OpConst64, cfg.config.Types.Int64, 14, nil),
   393  					Exit("mem"))),
   394  			cfg.Fun("entry",
   395  				Bloc("entry",
   396  					Valu("mem", OpInitMem, types.TypeMem, 0, nil),
   397  					Valu("a", OpConst64, cfg.config.Types.Int64, 26, nil),
   398  					Exit("mem"))),
   399  		},
   400  		// value aux different
   401  		{
   402  			cfg.Fun("entry",
   403  				Bloc("entry",
   404  					Valu("mem", OpInitMem, types.TypeMem, 0, nil),
   405  					Valu("a", OpConstString, cfg.config.Types.String, 0, StringToAux("foo")),
   406  					Exit("mem"))),
   407  			cfg.Fun("entry",
   408  				Bloc("entry",
   409  					Valu("mem", OpInitMem, types.TypeMem, 0, nil),
   410  					Valu("a", OpConstString, cfg.config.Types.String, 0, StringToAux("bar")),
   411  					Exit("mem"))),
   412  		},
   413  		// value args different
   414  		{
   415  			cfg.Fun("entry",
   416  				Bloc("entry",
   417  					Valu("mem", OpInitMem, types.TypeMem, 0, nil),
   418  					Valu("a", OpConst64, cfg.config.Types.Int64, 14, nil),
   419  					Valu("b", OpConst64, cfg.config.Types.Int64, 26, nil),
   420  					Valu("sum", OpAdd64, cfg.config.Types.Int64, 0, nil, "a", "b"),
   421  					Exit("mem"))),
   422  			cfg.Fun("entry",
   423  				Bloc("entry",
   424  					Valu("mem", OpInitMem, types.TypeMem, 0, nil),
   425  					Valu("a", OpConst64, cfg.config.Types.Int64, 0, nil),
   426  					Valu("b", OpConst64, cfg.config.Types.Int64, 14, nil),
   427  					Valu("sum", OpAdd64, cfg.config.Types.Int64, 0, nil, "b", "a"),
   428  					Exit("mem"))),
   429  		},
   430  	}
   431  	for _, c := range differentCases {
   432  		if Equiv(c.f.f, c.g.f) {
   433  			t.Error("expected difference. Func definitions:")
   434  			t.Error(c.f.f)
   435  			t.Error(c.g.f)
   436  		}
   437  	}
   438  }
   439  
   440  // TestConstCache ensures that the cache will not return
   441  // reused free'd values with a non-matching AuxInt
   442  func TestConstCache(t *testing.T) {
   443  	c := testConfig(t)
   444  	f := c.Fun("entry",
   445  		Bloc("entry",
   446  			Valu("mem", OpInitMem, types.TypeMem, 0, nil),
   447  			Exit("mem")))
   448  	v1 := f.f.ConstBool(c.config.Types.Bool, false)
   449  	v2 := f.f.ConstBool(c.config.Types.Bool, true)
   450  	f.f.freeValue(v1)
   451  	f.f.freeValue(v2)
   452  	v3 := f.f.ConstBool(c.config.Types.Bool, false)
   453  	v4 := f.f.ConstBool(c.config.Types.Bool, true)
   454  	if v3.AuxInt != 0 {
   455  		t.Errorf("expected %s to have auxint of 0\n", v3.LongString())
   456  	}
   457  	if v4.AuxInt != 1 {
   458  		t.Errorf("expected %s to have auxint of 1\n", v4.LongString())
   459  	}
   460  
   461  }
   462  
   463  // opcodeMap returns a map from opcode to the number of times that opcode
   464  // appears in the function.
   465  func opcodeMap(f *Func) map[Op]int {
   466  	m := map[Op]int{}
   467  	for _, b := range f.Blocks {
   468  		for _, v := range b.Values {
   469  			m[v.Op]++
   470  		}
   471  	}
   472  	return m
   473  }
   474  
   475  // opcodeCounts checks that the number of opcodes listed in m agree with the
   476  // number of opcodes that appear in the function.
   477  func checkOpcodeCounts(t *testing.T, f *Func, m map[Op]int) {
   478  	n := opcodeMap(f)
   479  	for op, cnt := range m {
   480  		if n[op] != cnt {
   481  			t.Errorf("%s appears %d times, want %d times", op, n[op], cnt)
   482  		}
   483  	}
   484  }
   485
View as plain text