cmd/internal/ssa: utility functions to make Funcs
Adds a more convenient way to define Funcs for testing.
For instance,
b1:
v1 = Arg <mem> [.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", OpArg, TypeMem, ".mem"),
Goto("exit")),
Bloc("exit",
Exit("mem")),
Bloc("deadblock",
Valu("deadval", OpConst, TypeBool, true),
If("deadval", "deadblock", "exit")))
Also add an Equiv function to test two Funcs for equivalence.
Change-Id: If1633865aeefb8e765e772b6dad19250d93a413a
Reviewed-on: https://go-review.googlesource.com/9992
Reviewed-by: Keith Randall <khr@golang.org>
diff --git a/src/cmd/internal/ssa/deadcode_test.go b/src/cmd/internal/ssa/deadcode_test.go
index 1b7c81c..ced46e5 100644
--- a/src/cmd/internal/ssa/deadcode_test.go
+++ b/src/cmd/internal/ssa/deadcode_test.go
@@ -2,44 +2,35 @@
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.
-// TODO: these tests are pretty verbose. Is there a way to simplify
-// building a small Func for testing?
-
-package ssa_test
+package ssa
import (
- . "cmd/internal/ssa"
"testing"
)
func TestDeadLoop(t *testing.T) {
- f := new(Func)
- entry := f.NewBlock(BlockPlain)
- exit := f.NewBlock(BlockExit)
- f.Entry = entry
- addEdge(entry, exit)
- mem := entry.NewValue(OpArg, TypeMem, ".mem")
- exit.Control = mem
+ fun := Fun("entry",
+ Bloc("entry",
+ Valu("mem", OpArg, TypeMem, ".mem"),
+ Goto("exit")),
+ Bloc("exit",
+ Exit("mem")),
+ // dead loop
+ Bloc("deadblock",
+ // dead value in dead block
+ Valu("deadval", OpConst, TypeBool, true),
+ If("deadval", "deadblock", "exit")))
- // dead loop
- deadblock := f.NewBlock(BlockIf)
- addEdge(deadblock, deadblock)
- addEdge(deadblock, exit)
+ CheckFunc(fun.f)
+ Deadcode(fun.f)
+ CheckFunc(fun.f)
- // dead value in dead block
- deadval := deadblock.NewValue(OpConst, TypeBool, true)
- deadblock.Control = deadval
-
- CheckFunc(f)
- Deadcode(f)
- CheckFunc(f)
-
- for _, b := range f.Blocks {
- if b == deadblock {
+ for _, b := range fun.f.Blocks {
+ if b == fun.blocks["deadblock"] {
t.Errorf("dead block not removed")
}
for _, v := range b.Values {
- if v == deadval {
+ if v == fun.values["deadval"] {
t.Errorf("control value of dead block not removed")
}
}
@@ -47,23 +38,21 @@
}
func TestDeadValue(t *testing.T) {
- f := new(Func)
- entry := f.NewBlock(BlockPlain)
- exit := f.NewBlock(BlockExit)
- f.Entry = entry
- addEdge(entry, exit)
- mem := entry.NewValue(OpArg, TypeMem, ".mem")
- exit.Control = mem
+ fun := Fun("entry",
+ Bloc("entry",
+ Valu("mem", OpArg, TypeMem, ".mem"),
+ Valu("deadval", OpConst, TypeInt64, int64(37)),
+ Goto("exit")),
+ Bloc("exit",
+ Exit("mem")))
- deadval := entry.NewValue(OpConst, TypeInt64, int64(37))
+ CheckFunc(fun.f)
+ Deadcode(fun.f)
+ CheckFunc(fun.f)
- CheckFunc(f)
- Deadcode(f)
- CheckFunc(f)
-
- for _, b := range f.Blocks {
+ for _, b := range fun.f.Blocks {
for _, v := range b.Values {
- if v == deadval {
+ if v == fun.values["deadval"] {
t.Errorf("dead value not removed")
}
}
@@ -71,42 +60,34 @@
}
func TestNeverTaken(t *testing.T) {
- f := new(Func)
- entry := f.NewBlock(BlockIf)
- exit := f.NewBlock(BlockExit)
- then := f.NewBlock(BlockPlain)
- else_ := f.NewBlock(BlockPlain)
- f.Entry = entry
- addEdge(entry, then)
- addEdge(entry, else_)
- addEdge(then, exit)
- addEdge(else_, exit)
- mem := entry.NewValue(OpArg, TypeMem, ".mem")
- exit.Control = mem
+ fun := Fun("entry",
+ Bloc("entry",
+ Valu("cond", OpConst, TypeBool, false),
+ Valu("mem", OpArg, TypeMem, ".mem"),
+ If("cond", "then", "else")),
+ Bloc("then",
+ Goto("exit")),
+ Bloc("else",
+ Goto("exit")),
+ Bloc("exit",
+ Exit("mem")))
- cond := entry.NewValue(OpConst, TypeBool, false)
- entry.Control = cond
+ CheckFunc(fun.f)
+ Deadcode(fun.f)
+ CheckFunc(fun.f)
- CheckFunc(f)
- Deadcode(f)
- CheckFunc(f)
-
- if entry.Kind != BlockPlain {
+ if fun.blocks["entry"].Kind != BlockPlain {
t.Errorf("if(false) not simplified")
}
- for _, b := range f.Blocks {
- if b == then {
+ for _, b := range fun.f.Blocks {
+ if b == fun.blocks["then"] {
t.Errorf("then block still present")
}
for _, v := range b.Values {
- if v == cond {
+ if v == fun.values["cond"] {
t.Errorf("constant condition still present")
}
}
}
-}
-func addEdge(b, c *Block) {
- b.Succs = append(b.Succs, c)
- c.Preds = append(c.Preds, b)
}
diff --git a/src/cmd/internal/ssa/func_test.go b/src/cmd/internal/ssa/func_test.go
new file mode 100644
index 0000000..e7619ca
--- /dev/null
+++ b/src/cmd/internal/ssa/func_test.go
@@ -0,0 +1,401 @@
+// This file contains some utility functions to help define Funcs for testing.
+// As an example, the following func
+//
+// b1:
+// v1 = Arg <mem> [.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", OpArg, TypeMem, ".mem"),
+// Goto("exit")),
+// Bloc("exit",
+// Exit("mem")),
+// Bloc("deadblock",
+// Valu("deadval", OpConst, TypeBool, 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 (
+ "log"
+ "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 {
+ 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], gb.Succs[i]) {
+ return false
+ }
+ }
+ if len(fb.Preds) != len(gb.Preds) {
+ return false
+ }
+ for i := range fb.Preds {
+ if !checkBlk(fb.Preds[i], gb.Preds[i]) {
+ 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
+}
+
+// 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(entry string, blocs ...bloc) fun {
+ f := new(Func)
+ 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.NewValue(valu.op, valu.t, 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 {
+ log.Panicf("control value for block %s missing", bloc.name)
+ }
+ b.Control = cval
+ }
+ // Fill in args.
+ for _, valu := range bloc.valus {
+ v := values[valu.name]
+ for _, arg := range valu.args {
+ a, ok := values[arg]
+ if !ok {
+ log.Panicf("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 {
+ addEdge(b, 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 {
+ log.Panicf("already seen control for block %s", name)
+ }
+ b.control = v
+ seenCtrl = true
+ case valu:
+ b.valus = append(b.valus, v)
+ }
+ }
+ if !seenCtrl {
+ log.Panicf("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, aux interface{}, args ...string) valu {
+ return valu{name, op, t, 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{}}
+}
+
+// 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
+ aux interface{}
+ args []string
+}
+
+func addEdge(b, c *Block) {
+ b.Succs = append(b.Succs, c)
+ c.Preds = append(c.Preds, b)
+}
+
+func TestArgs(t *testing.T) {
+ fun := Fun("entry",
+ Bloc("entry",
+ Valu("a", OpConst, TypeInt64, 14),
+ Valu("b", OpConst, TypeInt64, 26),
+ Valu("sum", OpAdd, TypeInt64, nil, "a", "b"),
+ Valu("mem", OpArg, TypeMem, ".mem"),
+ 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("entry",
+ Bloc("entry",
+ Valu("a", OpConst, TypeInt64, 14),
+ Valu("b", OpConst, TypeInt64, 26),
+ Valu("sum", OpAdd, TypeInt64, nil, "a", "b"),
+ Valu("mem", OpArg, TypeMem, ".mem"),
+ Goto("exit")),
+ Bloc("exit",
+ Exit("mem"))),
+ Fun("entry",
+ Bloc("entry",
+ Valu("a", OpConst, TypeInt64, 14),
+ Valu("b", OpConst, TypeInt64, 26),
+ Valu("sum", OpAdd, TypeInt64, nil, "a", "b"),
+ Valu("mem", OpArg, TypeMem, ".mem"),
+ Goto("exit")),
+ Bloc("exit",
+ Exit("mem"))),
+ },
+ // block order changed
+ {
+ Fun("entry",
+ Bloc("entry",
+ Valu("a", OpConst, TypeInt64, 14),
+ Valu("b", OpConst, TypeInt64, 26),
+ Valu("sum", OpAdd, TypeInt64, nil, "a", "b"),
+ Valu("mem", OpArg, TypeMem, ".mem"),
+ Goto("exit")),
+ Bloc("exit",
+ Exit("mem"))),
+ Fun("entry",
+ Bloc("exit",
+ Exit("mem")),
+ Bloc("entry",
+ Valu("a", OpConst, TypeInt64, 14),
+ Valu("b", OpConst, TypeInt64, 26),
+ Valu("sum", OpAdd, TypeInt64, nil, "a", "b"),
+ Valu("mem", OpArg, TypeMem, ".mem"),
+ Goto("exit"))),
+ },
+ }
+ for _, c := range equivalentCases {
+ if !Equiv(c.f.f, c.g.f) {
+ t.Errorf("expected equivalence. Func definitions:")
+ // TODO(matloob): Rewrite PrintFunc to output to a string or writer,
+ // so the functions can be written to the error log.
+ PrintFunc(c.f.f)
+ PrintFunc(c.g.f)
+ }
+ }
+
+ differentCases := []struct{ f, g fun }{
+ // different shape
+ {
+ Fun("entry",
+ Bloc("entry",
+ Valu("mem", OpArg, TypeMem, ".mem"),
+ Goto("exit")),
+ Bloc("exit",
+ Exit("mem"))),
+ Fun("entry",
+ Bloc("entry",
+ Valu("mem", OpArg, TypeMem, ".mem"),
+ Exit("mem"))),
+ },
+ // value order changed
+ {
+ Fun("entry",
+ Bloc("entry",
+ Valu("mem", OpArg, TypeMem, ".mem"),
+ Valu("b", OpConst, TypeInt64, 26),
+ Valu("a", OpConst, TypeInt64, 14),
+ Exit("mem"))),
+ Fun("entry",
+ Bloc("entry",
+ Valu("mem", OpArg, TypeMem, ".mem"),
+ Valu("a", OpConst, TypeInt64, 14),
+ Valu("b", OpConst, TypeInt64, 26),
+ Exit("mem"))),
+ },
+ // value aux different
+ {
+ Fun("entry",
+ Bloc("entry",
+ Valu("mem", OpArg, TypeMem, ".mem"),
+ Valu("a", OpConst, TypeInt64, 14),
+ Exit("mem"))),
+ Fun("entry",
+ Bloc("entry",
+ Valu("mem", OpArg, TypeMem, ".mem"),
+ Valu("a", OpConst, TypeInt64, 26),
+ Exit("mem"))),
+ },
+ // value args different
+ {
+ Fun("entry",
+ Bloc("entry",
+ Valu("mem", OpArg, TypeMem, ".mem"),
+ Valu("a", OpConst, TypeInt64, 14),
+ Valu("b", OpConst, TypeInt64, 26),
+ Valu("sum", OpAdd, TypeInt64, nil, "a", "b"),
+ Exit("mem"))),
+ Fun("entry",
+ Bloc("entry",
+ Valu("mem", OpArg, TypeMem, ".mem"),
+ Valu("a", OpConst, TypeInt64, 0),
+ Valu("b", OpConst, TypeInt64, 14),
+ Valu("sum", OpAdd, TypeInt64, nil, "b", "a"),
+ Exit("mem"))),
+ },
+ }
+ for _, c := range differentCases {
+ if Equiv(c.f.f, c.g.f) {
+ t.Errorf("expected difference. Func definitions:")
+ // TODO(matloob): Rewrite PrintFunc to output to a string or writer,
+ // so the functions can be written to the error log.
+ PrintFunc(c.f.f)
+ PrintFunc(c.g.f)
+ }
+ }
+}
