src/cmd/compile/internal/ssa/func_test.go - go - Git at Google

 // Copyright 2015 The Go Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style
 // license that can be found in the LICENSE file.

 // This file contains some utility functions to help define Funcs for testing.
 // As an example, the following func
 //
 //   b1:
 //     v1 = InitMem <mem>
 //     Plain -> b2
 //   b2:
 //     Exit v1
 //   b3:
 //     v2 = Const <bool> [true]
 //     If v2 -> b3 b2
 //
 // can be defined as
 //
 //   fun := Fun("entry",
 //       Bloc("entry",
 //           Valu("mem", OpInitMem, TypeMem, 0, nil),
 //           Goto("exit")),
 //       Bloc("exit",
 //           Exit("mem")),
 //       Bloc("deadblock",
 //          Valu("deadval", OpConstBool, TypeBool, 0, true),
 //          If("deadval", "deadblock", "exit")))
 //
 // and the Blocks or Values used in the Func can be accessed
 // like this:
 //   fun.blocks["entry"] or fun.values["deadval"]

 package ssa

 // TODO(matloob): Choose better names for Fun, Bloc, Goto, etc.
 // TODO(matloob): Write a parser for the Func disassembly. Maybe
 //                the parser can be used instead of Fun.

 import (
 	"fmt"
 	"reflect"
 	"testing"
 )

 // Compare two Funcs for equivalence. Their CFGs must be isomorphic,
 // and their values must correspond.
 // Requires that values and predecessors are in the same order, even
 // though Funcs could be equivalent when they are not.
 // TODO(matloob): Allow values and predecessors to be in different
 // orders if the CFG are otherwise equivalent.
 func Equiv(f, g *Func) bool {
 	valcor := make(map[*Value]*Value)
 	var checkVal func(fv, gv *Value) bool
 	checkVal = func(fv, gv *Value) bool {
 		if fv == nil && gv == nil {
 			return true
 		}
 		if valcor[fv] == nil && valcor[gv] == nil {
 			valcor[fv] = gv
 			valcor[gv] = fv
 			// Ignore ids. Ops and Types are compared for equality.
 			// TODO(matloob): Make sure types are canonical and can
 			// be compared for equality.
 			if fv.Op != gv.Op || fv.Type != gv.Type || fv.AuxInt != gv.AuxInt {
 				return false
 			}
 			if !reflect.DeepEqual(fv.Aux, gv.Aux) {
 				// This makes the assumption that aux values can be compared
 				// using DeepEqual.
 				// TODO(matloob): Aux values may be *gc.Sym pointers in the near
 				// future. Make sure they are canonical.
 				return false
 			}
 			if len(fv.Args) != len(gv.Args) {
 				return false
 			}
 			for i := range fv.Args {
 				if !checkVal(fv.Args[i], gv.Args[i]) {
 					return false
 				}
 			}
 		}
 		return valcor[fv] == gv && valcor[gv] == fv
 	}
 	blkcor := make(map[*Block]*Block)
 	var checkBlk func(fb, gb *Block) bool
 	checkBlk = func(fb, gb *Block) bool {
 		if blkcor[fb] == nil && blkcor[gb] == nil {
 			blkcor[fb] = gb
 			blkcor[gb] = fb
 			// ignore ids
 			if fb.Kind != gb.Kind {
 				return false
 			}
 			if len(fb.Values) != len(gb.Values) {
 				return false
 			}
 			for i := range fb.Values {
 				if !checkVal(fb.Values[i], gb.Values[i]) {
 					return false
 				}
 			}
 			if len(fb.Succs) != len(gb.Succs) {
 				return false
 			}
 			for i := range fb.Succs {
 				if !checkBlk(fb.Succs[i].b, gb.Succs[i].b) {
 					return false
 				}
 			}
 			if len(fb.Preds) != len(gb.Preds) {
 				return false
 			}
 			for i := range fb.Preds {
 				if !checkBlk(fb.Preds[i].b, gb.Preds[i].b) {
 					return false
 				}
 			}
 			return true

 		}
 		return blkcor[fb] == gb && blkcor[gb] == fb
 	}

 	return checkBlk(f.Entry, g.Entry)
 }

 // fun is the return type of Fun. It contains the created func
 // itself as well as indexes from block and value names into the
 // corresponding Blocks and Values.
 type fun struct {
 	f      *Func
 	blocks map[string]*Block
 	values map[string]*Value
 }

 var emptyPass pass = pass{
 	name: "empty pass",
 }

 // Fun takes the name of an entry bloc and a series of Bloc calls, and
 // returns a fun containing the composed Func. entry must be a name
 // supplied to one of the Bloc functions. Each of the bloc names and
 // valu names should be unique across the Fun.
 func Fun(c *Config, entry string, blocs ...bloc) fun {
 	f := c.NewFunc()
 	f.pass = &emptyPass

 	blocks := make(map[string]*Block)
 	values := make(map[string]*Value)
 	// Create all the blocks and values.
 	for _, bloc := range blocs {
 		b := f.NewBlock(bloc.control.kind)
 		blocks[bloc.name] = b
 		for _, valu := range bloc.valus {
 			// args are filled in the second pass.
 			values[valu.name] = b.NewValue0IA(0, valu.op, valu.t, valu.auxint, valu.aux)
 		}
 	}
 	// Connect the blocks together and specify control values.
 	f.Entry = blocks[entry]
 	for _, bloc := range blocs {
 		b := blocks[bloc.name]
 		c := bloc.control
 		// Specify control values.
 		if c.control != "" {
 			cval, ok := values[c.control]
 			if !ok {
 				f.Fatalf("control value for block %s missing", bloc.name)
 			}
 			b.SetControl(cval)
 		}
 		// Fill in args.
 		for _, valu := range bloc.valus {
 			v := values[valu.name]
 			for _, arg := range valu.args {
 				a, ok := values[arg]
 				if !ok {
 					b.Fatalf("arg %s missing for value %s in block %s",
 						arg, valu.name, bloc.name)
 				}
 				v.AddArg(a)
 			}
 		}
 		// Connect to successors.
 		for _, succ := range c.succs {
 			b.AddEdgeTo(blocks[succ])
 		}
 	}
 	return fun{f, blocks, values}
 }

 // Bloc defines a block for Fun. The bloc name should be unique
 // across the containing Fun. entries should consist of calls to valu,
 // as well as one call to Goto, If, or Exit to specify the block kind.
 func Bloc(name string, entries ...interface{}) bloc {
 	b := bloc{}
 	b.name = name
 	seenCtrl := false
 	for _, e := range entries {
 		switch v := e.(type) {
 		case ctrl:
 			// there should be exactly one Ctrl entry.
 			if seenCtrl {
 				panic(fmt.Sprintf("already seen control for block %s", name))
 			}
 			b.control = v
 			seenCtrl = true
 		case valu:
 			b.valus = append(b.valus, v)
 		}
 	}
 	if !seenCtrl {
 		panic(fmt.Sprintf("block %s doesn't have control", b.name))
 	}
 	return b
 }

 // Valu defines a value in a block.
 func Valu(name string, op Op, t Type, auxint int64, aux interface{}, args ...string) valu {
 	return valu{name, op, t, auxint, aux, args}
 }

 // Goto specifies that this is a BlockPlain and names the single successor.
 // TODO(matloob): choose a better name.
 func Goto(succ string) ctrl {
 	return ctrl{BlockPlain, "", []string{succ}}
 }

 // If specifies a BlockIf.
 func If(cond, sub, alt string) ctrl {
 	return ctrl{BlockIf, cond, []string{sub, alt}}
 }

 // Exit specifies a BlockExit.
 func Exit(arg string) ctrl {
 	return ctrl{BlockExit, arg, []string{}}
 }

 // Eq specifies a BlockAMD64EQ.
 func Eq(cond, sub, alt string) ctrl {
 	return ctrl{BlockAMD64EQ, cond, []string{sub, alt}}
 }

 // bloc, ctrl, and valu are internal structures used by Bloc, Valu, Goto,
 // If, and Exit to help define blocks.

 type bloc struct {
 	name    string
 	control ctrl
 	valus   []valu
 }

 type ctrl struct {
 	kind    BlockKind
 	control string
 	succs   []string
 }

 type valu struct {
 	name   string
 	op     Op
 	t      Type
 	auxint int64
 	aux    interface{}
 	args   []string
 }

 func TestArgs(t *testing.T) {
 	c := testConfig(t)
 	fun := Fun(c, "entry",
 		Bloc("entry",
 			Valu("a", OpConst64, TypeInt64, 14, nil),
 			Valu("b", OpConst64, TypeInt64, 26, nil),
 			Valu("sum", OpAdd64, TypeInt64, 0, nil, "a", "b"),
 			Valu("mem", OpInitMem, TypeMem, 0, nil),
 			Goto("exit")),
 		Bloc("exit",
 			Exit("mem")))
 	sum := fun.values["sum"]
 	for i, name := range []string{"a", "b"} {
 		if sum.Args[i] != fun.values[name] {
 			t.Errorf("arg %d for sum is incorrect: want %s, got %s",
 				i, sum.Args[i], fun.values[name])
 		}
 	}
 }

 func TestEquiv(t *testing.T) {
 	equivalentCases := []struct{ f, g fun }{
 		// simple case
 		{
 			Fun(testConfig(t), "entry",
 				Bloc("entry",
 					Valu("a", OpConst64, TypeInt64, 14, nil),
 					Valu("b", OpConst64, TypeInt64, 26, nil),
 					Valu("sum", OpAdd64, TypeInt64, 0, nil, "a", "b"),
 					Valu("mem", OpInitMem, TypeMem, 0, nil),
 					Goto("exit")),
 				Bloc("exit",
 					Exit("mem"))),
 			Fun(testConfig(t), "entry",
 				Bloc("entry",
 					Valu("a", OpConst64, TypeInt64, 14, nil),
 					Valu("b", OpConst64, TypeInt64, 26, nil),
 					Valu("sum", OpAdd64, TypeInt64, 0, nil, "a", "b"),
 					Valu("mem", OpInitMem, TypeMem, 0, nil),
 					Goto("exit")),
 				Bloc("exit",
 					Exit("mem"))),
 		},
 		// block order changed
 		{
 			Fun(testConfig(t), "entry",
 				Bloc("entry",
 					Valu("a", OpConst64, TypeInt64, 14, nil),
 					Valu("b", OpConst64, TypeInt64, 26, nil),
 					Valu("sum", OpAdd64, TypeInt64, 0, nil, "a", "b"),
 					Valu("mem", OpInitMem, TypeMem, 0, nil),
 					Goto("exit")),
 				Bloc("exit",
 					Exit("mem"))),
 			Fun(testConfig(t), "entry",
 				Bloc("exit",
 					Exit("mem")),
 				Bloc("entry",
 					Valu("a", OpConst64, TypeInt64, 14, nil),
 					Valu("b", OpConst64, TypeInt64, 26, nil),
 					Valu("sum", OpAdd64, TypeInt64, 0, nil, "a", "b"),
 					Valu("mem", OpInitMem, TypeMem, 0, nil),
 					Goto("exit"))),
 		},
 	}
 	for _, c := range equivalentCases {
 		if !Equiv(c.f.f, c.g.f) {
 			t.Error("expected equivalence. Func definitions:")
 			t.Error(c.f.f)
 			t.Error(c.g.f)
 		}
 	}

 	differentCases := []struct{ f, g fun }{
 		// different shape
 		{
 			Fun(testConfig(t), "entry",
 				Bloc("entry",
 					Valu("mem", OpInitMem, TypeMem, 0, nil),
 					Goto("exit")),
 				Bloc("exit",
 					Exit("mem"))),
 			Fun(testConfig(t), "entry",
 				Bloc("entry",
 					Valu("mem", OpInitMem, TypeMem, 0, nil),
 					Exit("mem"))),
 		},
 		// value order changed
 		{
 			Fun(testConfig(t), "entry",
 				Bloc("entry",
 					Valu("mem", OpInitMem, TypeMem, 0, nil),
 					Valu("b", OpConst64, TypeInt64, 26, nil),
 					Valu("a", OpConst64, TypeInt64, 14, nil),
 					Exit("mem"))),
 			Fun(testConfig(t), "entry",
 				Bloc("entry",
 					Valu("mem", OpInitMem, TypeMem, 0, nil),
 					Valu("a", OpConst64, TypeInt64, 14, nil),
 					Valu("b", OpConst64, TypeInt64, 26, nil),
 					Exit("mem"))),
 		},
 		// value auxint different
 		{
 			Fun(testConfig(t), "entry",
 				Bloc("entry",
 					Valu("mem", OpInitMem, TypeMem, 0, nil),
 					Valu("a", OpConst64, TypeInt64, 14, nil),
 					Exit("mem"))),
 			Fun(testConfig(t), "entry",
 				Bloc("entry",
 					Valu("mem", OpInitMem, TypeMem, 0, nil),
 					Valu("a", OpConst64, TypeInt64, 26, nil),
 					Exit("mem"))),
 		},
 		// value aux different
 		{
 			Fun(testConfig(t), "entry",
 				Bloc("entry",
 					Valu("mem", OpInitMem, TypeMem, 0, nil),
 					Valu("a", OpConst64, TypeInt64, 0, 14),
 					Exit("mem"))),
 			Fun(testConfig(t), "entry",
 				Bloc("entry",
 					Valu("mem", OpInitMem, TypeMem, 0, nil),
 					Valu("a", OpConst64, TypeInt64, 0, 26),
 					Exit("mem"))),
 		},
 		// value args different
 		{
 			Fun(testConfig(t), "entry",
 				Bloc("entry",
 					Valu("mem", OpInitMem, TypeMem, 0, nil),
 					Valu("a", OpConst64, TypeInt64, 14, nil),
 					Valu("b", OpConst64, TypeInt64, 26, nil),
 					Valu("sum", OpAdd64, TypeInt64, 0, nil, "a", "b"),
 					Exit("mem"))),
 			Fun(testConfig(t), "entry",
 				Bloc("entry",
 					Valu("mem", OpInitMem, TypeMem, 0, nil),
 					Valu("a", OpConst64, TypeInt64, 0, nil),
 					Valu("b", OpConst64, TypeInt64, 14, nil),
 					Valu("sum", OpAdd64, TypeInt64, 0, nil, "b", "a"),
 					Exit("mem"))),
 		},
 	}
 	for _, c := range differentCases {
 		if Equiv(c.f.f, c.g.f) {
 			t.Error("expected difference. Func definitions:")
 			t.Error(c.f.f)
 			t.Error(c.g.f)
 		}
 	}
 }

 // TestConstCache ensures that the cache will not return
 // reused free'd values with a non-matching AuxInt
 func TestConstCache(t *testing.T) {
 	f := Fun(testConfig(t), "entry",
 		Bloc("entry",
 			Valu("mem", OpInitMem, TypeMem, 0, nil),
 			Exit("mem")))
 	v1 := f.f.ConstBool(0, TypeBool, false)
 	v2 := f.f.ConstBool(0, TypeBool, true)
 	f.f.freeValue(v1)
 	f.f.freeValue(v2)
 	v3 := f.f.ConstBool(0, TypeBool, false)
 	v4 := f.f.ConstBool(0, TypeBool, true)
 	if v3.AuxInt != 0 {
 		t.Errorf("expected %s to have auxint of 0\n", v3.LongString())
 	}
 	if v4.AuxInt != 1 {
 		t.Errorf("expected %s to have auxint of 1\n", v4.LongString())
 	}

 }

 // opcodeMap returns a map from opcode to the number of times that opcode
 // appears in the function.
 func opcodeMap(f *Func) map[Op]int {
 	m := map[Op]int{}
 	for _, b := range f.Blocks {
 		for _, v := range b.Values {
 			m[v.Op]++
 		}
 	}
 	return m
 }

 // opcodeCounts checks that the number of opcodes listed in m agree with the
 // number of opcodes that appear in the function.
 func checkOpcodeCounts(t *testing.T, f *Func, m map[Op]int) {
 	n := opcodeMap(f)
 	for op, cnt := range m {
 		if n[op] != cnt {
 			t.Errorf("%s appears %d times, want %d times", op, n[op], cnt)
 		}
 	}
 }
	// Copyright 2015 The Go Authors. All rights reserved.
	// Use of this source code is governed by a BSD-style
	// license that can be found in the LICENSE file.

	// This file contains some utility functions to help define Funcs for testing.
	// As an example, the following func
	//
	// b1:
	// v1 = InitMem <mem>
	// Plain -> b2
	// b2:
	// Exit v1
	// b3:
	// v2 = Const <bool> [true]
	// If v2 -> b3 b2
	//
	// can be defined as
	//
	// fun := Fun("entry",
	// Bloc("entry",
	// Valu("mem", OpInitMem, TypeMem, 0, nil),
	// Goto("exit")),
	// Bloc("exit",
	// Exit("mem")),
	// Bloc("deadblock",
	// Valu("deadval", OpConstBool, TypeBool, 0, true),
	// If("deadval", "deadblock", "exit")))
	//
	// and the Blocks or Values used in the Func can be accessed
	// like this:
	// fun.blocks["entry"] or fun.values["deadval"]

	package ssa

	// TODO(matloob): Choose better names for Fun, Bloc, Goto, etc.
	// TODO(matloob): Write a parser for the Func disassembly. Maybe
	// the parser can be used instead of Fun.

	import (
	"fmt"
	"reflect"
	"testing"
	)

	// Compare two Funcs for equivalence. Their CFGs must be isomorphic,
	// and their values must correspond.
	// Requires that values and predecessors are in the same order, even
	// though Funcs could be equivalent when they are not.
	// TODO(matloob): Allow values and predecessors to be in different
	// orders if the CFG are otherwise equivalent.
	func Equiv(f, g *Func) bool {
	valcor := make(map[Value]Value)
	var checkVal func(fv, gv *Value) bool
	checkVal = func(fv, gv *Value) bool {
	if fv == nil && gv == nil {
	return true
	}
	if valcor[fv] == nil && valcor[gv] == nil {
	valcor[fv] = gv
	valcor[gv] = fv
	// Ignore ids. Ops and Types are compared for equality.
	// TODO(matloob): Make sure types are canonical and can
	// be compared for equality.
	if fv.Op != gv.Op \|\| fv.Type != gv.Type \|\| fv.AuxInt != gv.AuxInt {
	return false
	}
	if !reflect.DeepEqual(fv.Aux, gv.Aux) {
	// This makes the assumption that aux values can be compared
	// using DeepEqual.
	// TODO(matloob): Aux values may be *gc.Sym pointers in the near
	// future. Make sure they are canonical.
	return false
	}
	if len(fv.Args) != len(gv.Args) {
	return false
	}
	for i := range fv.Args {
	if !checkVal(fv.Args[i], gv.Args[i]) {
	return false
	}
	}
	}
	return valcor[fv] == gv && valcor[gv] == fv
	}
	blkcor := make(map[Block]Block)
	var checkBlk func(fb, gb *Block) bool
	checkBlk = func(fb, gb *Block) bool {
	if blkcor[fb] == nil && blkcor[gb] == nil {
	blkcor[fb] = gb
	blkcor[gb] = fb
	// ignore ids
	if fb.Kind != gb.Kind {
	return false
	}
	if len(fb.Values) != len(gb.Values) {
	return false
	}
	for i := range fb.Values {
	if !checkVal(fb.Values[i], gb.Values[i]) {
	return false
	}
	}
	if len(fb.Succs) != len(gb.Succs) {
	return false
	}
	for i := range fb.Succs {
	if !checkBlk(fb.Succs[i].b, gb.Succs[i].b) {
	return false
	}
	}
	if len(fb.Preds) != len(gb.Preds) {
	return false
	}
	for i := range fb.Preds {
	if !checkBlk(fb.Preds[i].b, gb.Preds[i].b) {
	return false
	}
	}
	return true

	}
	return blkcor[fb] == gb && blkcor[gb] == fb
	}

	return checkBlk(f.Entry, g.Entry)
	}

	// fun is the return type of Fun. It contains the created func
	// itself as well as indexes from block and value names into the
	// corresponding Blocks and Values.
	type fun struct {
	f *Func
	blocks map[string]*Block
	values map[string]*Value
	}

	var emptyPass pass = pass{
	name: "empty pass",
	}

	// Fun takes the name of an entry bloc and a series of Bloc calls, and
	// returns a fun containing the composed Func. entry must be a name
	// supplied to one of the Bloc functions. Each of the bloc names and
	// valu names should be unique across the Fun.
	func Fun(c *Config, entry string, blocs ...bloc) fun {
	f := c.NewFunc()
	f.pass = &emptyPass

	blocks := make(map[string]*Block)
	values := make(map[string]*Value)
	// Create all the blocks and values.
	for _, bloc := range blocs {
	b := f.NewBlock(bloc.control.kind)
	blocks[bloc.name] = b
	for _, valu := range bloc.valus {
	// args are filled in the second pass.
	values[valu.name] = b.NewValue0IA(0, valu.op, valu.t, valu.auxint, valu.aux)
	}
	}
	// Connect the blocks together and specify control values.
	f.Entry = blocks[entry]
	for _, bloc := range blocs {
	b := blocks[bloc.name]
	c := bloc.control
	// Specify control values.
	if c.control != "" {
	cval, ok := values[c.control]
	if !ok {
	f.Fatalf("control value for block %s missing", bloc.name)
	}
	b.SetControl(cval)
	}
	// Fill in args.
	for _, valu := range bloc.valus {
	v := values[valu.name]
	for _, arg := range valu.args {
	a, ok := values[arg]
	if !ok {
	b.Fatalf("arg %s missing for value %s in block %s",
	arg, valu.name, bloc.name)
	}
	v.AddArg(a)
	}
	}
	// Connect to successors.
	for _, succ := range c.succs {
	b.AddEdgeTo(blocks[succ])
	}
	}
	return fun{f, blocks, values}
	}

	// Bloc defines a block for Fun. The bloc name should be unique
	// across the containing Fun. entries should consist of calls to valu,
	// as well as one call to Goto, If, or Exit to specify the block kind.
	func Bloc(name string, entries ...interface{}) bloc {
	b := bloc{}
	b.name = name
	seenCtrl := false
	for _, e := range entries {
	switch v := e.(type) {
	case ctrl:
	// there should be exactly one Ctrl entry.
	if seenCtrl {
	panic(fmt.Sprintf("already seen control for block %s", name))
	}
	b.control = v
	seenCtrl = true
	case valu:
	b.valus = append(b.valus, v)
	}
	}
	if !seenCtrl {
	panic(fmt.Sprintf("block %s doesn't have control", b.name))
	}
	return b
	}

	// Valu defines a value in a block.
	func Valu(name string, op Op, t Type, auxint int64, aux interface{}, args ...string) valu {
	return valu{name, op, t, auxint, aux, args}
	}

	// Goto specifies that this is a BlockPlain and names the single successor.
	// TODO(matloob): choose a better name.
	func Goto(succ string) ctrl {
	return ctrl{BlockPlain, "", []string{succ}}
	}

	// If specifies a BlockIf.
	func If(cond, sub, alt string) ctrl {
	return ctrl{BlockIf, cond, []string{sub, alt}}
	}

	// Exit specifies a BlockExit.
	func Exit(arg string) ctrl {
	return ctrl{BlockExit, arg, []string{}}
	}

	// Eq specifies a BlockAMD64EQ.
	func Eq(cond, sub, alt string) ctrl {
	return ctrl{BlockAMD64EQ, cond, []string{sub, alt}}
	}

	// bloc, ctrl, and valu are internal structures used by Bloc, Valu, Goto,
	// If, and Exit to help define blocks.

	type bloc struct {
	name string
	control ctrl
	valus []valu
	}

	type ctrl struct {
	kind BlockKind
	control string
	succs []string
	}

	type valu struct {
	name string
	op Op
	t Type
	auxint int64
	aux interface{}
	args []string
	}

	func TestArgs(t *testing.T) {
	c := testConfig(t)
	fun := Fun(c, "entry",
	Bloc("entry",
	Valu("a", OpConst64, TypeInt64, 14, nil),
	Valu("b", OpConst64, TypeInt64, 26, nil),
	Valu("sum", OpAdd64, TypeInt64, 0, nil, "a", "b"),
	Valu("mem", OpInitMem, TypeMem, 0, nil),
	Goto("exit")),
	Bloc("exit",
	Exit("mem")))
	sum := fun.values["sum"]
	for i, name := range []string{"a", "b"} {
	if sum.Args[i] != fun.values[name] {
	t.Errorf("arg %d for sum is incorrect: want %s, got %s",
	i, sum.Args[i], fun.values[name])
	}
	}
	}

	func TestEquiv(t *testing.T) {
	equivalentCases := []struct{ f, g fun }{
	// simple case
	{
	Fun(testConfig(t), "entry",
	Bloc("entry",
	Valu("a", OpConst64, TypeInt64, 14, nil),
	Valu("b", OpConst64, TypeInt64, 26, nil),
	Valu("sum", OpAdd64, TypeInt64, 0, nil, "a", "b"),
	Valu("mem", OpInitMem, TypeMem, 0, nil),
	Goto("exit")),
	Bloc("exit",
	Exit("mem"))),
	Fun(testConfig(t), "entry",
	Bloc("entry",
	Valu("a", OpConst64, TypeInt64, 14, nil),
	Valu("b", OpConst64, TypeInt64, 26, nil),
	Valu("sum", OpAdd64, TypeInt64, 0, nil, "a", "b"),
	Valu("mem", OpInitMem, TypeMem, 0, nil),
	Goto("exit")),
	Bloc("exit",
	Exit("mem"))),
	},
	// block order changed
	{
	Fun(testConfig(t), "entry",
	Bloc("entry",
	Valu("a", OpConst64, TypeInt64, 14, nil),
	Valu("b", OpConst64, TypeInt64, 26, nil),
	Valu("sum", OpAdd64, TypeInt64, 0, nil, "a", "b"),
	Valu("mem", OpInitMem, TypeMem, 0, nil),
	Goto("exit")),
	Bloc("exit",
	Exit("mem"))),
	Fun(testConfig(t), "entry",
	Bloc("exit",
	Exit("mem")),
	Bloc("entry",
	Valu("a", OpConst64, TypeInt64, 14, nil),
	Valu("b", OpConst64, TypeInt64, 26, nil),
	Valu("sum", OpAdd64, TypeInt64, 0, nil, "a", "b"),
	Valu("mem", OpInitMem, TypeMem, 0, nil),
	Goto("exit"))),
	},
	}
	for _, c := range equivalentCases {
	if !Equiv(c.f.f, c.g.f) {
	t.Error("expected equivalence. Func definitions:")
	t.Error(c.f.f)
	t.Error(c.g.f)
	}
	}

	differentCases := []struct{ f, g fun }{
	// different shape
	{
	Fun(testConfig(t), "entry",
	Bloc("entry",
	Valu("mem", OpInitMem, TypeMem, 0, nil),
	Goto("exit")),
	Bloc("exit",
	Exit("mem"))),
	Fun(testConfig(t), "entry",
	Bloc("entry",
	Valu("mem", OpInitMem, TypeMem, 0, nil),
	Exit("mem"))),
	},
	// value order changed
	{
	Fun(testConfig(t), "entry",
	Bloc("entry",
	Valu("mem", OpInitMem, TypeMem, 0, nil),
	Valu("b", OpConst64, TypeInt64, 26, nil),
	Valu("a", OpConst64, TypeInt64, 14, nil),
	Exit("mem"))),
	Fun(testConfig(t), "entry",
	Bloc("entry",
	Valu("mem", OpInitMem, TypeMem, 0, nil),
	Valu("a", OpConst64, TypeInt64, 14, nil),
	Valu("b", OpConst64, TypeInt64, 26, nil),
	Exit("mem"))),
	},
	// value auxint different
	{
	Fun(testConfig(t), "entry",
	Bloc("entry",
	Valu("mem", OpInitMem, TypeMem, 0, nil),
	Valu("a", OpConst64, TypeInt64, 14, nil),
	Exit("mem"))),
	Fun(testConfig(t), "entry",
	Bloc("entry",
	Valu("mem", OpInitMem, TypeMem, 0, nil),
	Valu("a", OpConst64, TypeInt64, 26, nil),
	Exit("mem"))),
	},
	// value aux different
	{
	Fun(testConfig(t), "entry",
	Bloc("entry",
	Valu("mem", OpInitMem, TypeMem, 0, nil),
	Valu("a", OpConst64, TypeInt64, 0, 14),
	Exit("mem"))),
	Fun(testConfig(t), "entry",
	Bloc("entry",
	Valu("mem", OpInitMem, TypeMem, 0, nil),
	Valu("a", OpConst64, TypeInt64, 0, 26),
	Exit("mem"))),
	},
	// value args different
	{
	Fun(testConfig(t), "entry",
	Bloc("entry",
	Valu("mem", OpInitMem, TypeMem, 0, nil),
	Valu("a", OpConst64, TypeInt64, 14, nil),
	Valu("b", OpConst64, TypeInt64, 26, nil),
	Valu("sum", OpAdd64, TypeInt64, 0, nil, "a", "b"),
	Exit("mem"))),
	Fun(testConfig(t), "entry",
	Bloc("entry",
	Valu("mem", OpInitMem, TypeMem, 0, nil),
	Valu("a", OpConst64, TypeInt64, 0, nil),
	Valu("b", OpConst64, TypeInt64, 14, nil),
	Valu("sum", OpAdd64, TypeInt64, 0, nil, "b", "a"),
	Exit("mem"))),
	},
	}
	for _, c := range differentCases {
	if Equiv(c.f.f, c.g.f) {
	t.Error("expected difference. Func definitions:")
	t.Error(c.f.f)
	t.Error(c.g.f)
	}
	}
	}

	// TestConstCache ensures that the cache will not return
	// reused free'd values with a non-matching AuxInt
	func TestConstCache(t *testing.T) {
	f := Fun(testConfig(t), "entry",
	Bloc("entry",
	Valu("mem", OpInitMem, TypeMem, 0, nil),
	Exit("mem")))
	v1 := f.f.ConstBool(0, TypeBool, false)
	v2 := f.f.ConstBool(0, TypeBool, true)
	f.f.freeValue(v1)
	f.f.freeValue(v2)
	v3 := f.f.ConstBool(0, TypeBool, false)
	v4 := f.f.ConstBool(0, TypeBool, true)
	if v3.AuxInt != 0 {
	t.Errorf("expected %s to have auxint of 0\n", v3.LongString())
	}
	if v4.AuxInt != 1 {
	t.Errorf("expected %s to have auxint of 1\n", v4.LongString())
	}

	}

	// opcodeMap returns a map from opcode to the number of times that opcode
	// appears in the function.
	func opcodeMap(f *Func) map[Op]int {
	m := map[Op]int{}
	for _, b := range f.Blocks {
	for _, v := range b.Values {
	m[v.Op]++
	}
	}
	return m
	}

	// opcodeCounts checks that the number of opcodes listed in m agree with the
	// number of opcodes that appear in the function.
	func checkOpcodeCounts(t testing.T, f Func, m map[Op]int) {
	n := opcodeMap(f)
	for op, cnt := range m {
	if n[op] != cnt {
	t.Errorf("%s appears %d times, want %d times", op, n[op], cnt)
	}
	}
	}