// 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.
package ssa
import (
"cmd/compile/internal/types"
"testing"
)
func BenchmarkDominatorsLinear(b *testing.B) { benchmarkDominators(b, 10000, genLinear) }
func BenchmarkDominatorsFwdBack(b *testing.B) { benchmarkDominators(b, 10000, genFwdBack) }
func BenchmarkDominatorsManyPred(b *testing.B) { benchmarkDominators(b, 10000, genManyPred) }
func BenchmarkDominatorsMaxPred(b *testing.B) { benchmarkDominators(b, 10000, genMaxPred) }
func BenchmarkDominatorsMaxPredVal(b *testing.B) { benchmarkDominators(b, 10000, genMaxPredValue) }
type blockGen func(size int) []bloc
// genLinear creates an array of blocks that succeed one another
// b_n -> [b_n+1].
func genLinear(size int) []bloc {
var blocs []bloc
blocs = append(blocs,
Bloc("entry",
Valu("mem", OpInitMem, types.TypeMem, 0, nil),
Goto(blockn(0)),
),
)
for i := 0; i < size; i++ {
blocs = append(blocs, Bloc(blockn(i),
Goto(blockn(i+1))))
}
blocs = append(blocs,
Bloc(blockn(size), Goto("exit")),
Bloc("exit", Exit("mem")),
)
return blocs
}
// genLinear creates an array of blocks that alternate between
// b_n -> [b_n+1], b_n -> [b_n+1, b_n-1] , b_n -> [b_n+1, b_n+2]
func genFwdBack(size int) []bloc {
var blocs []bloc
blocs = append(blocs,
Bloc("entry",
Valu("mem", OpInitMem, types.TypeMem, 0, nil),
Valu("p", OpConstBool, types.Types[types.TBOOL], 1, nil),
Goto(blockn(0)),
),
)
for i := 0; i < size; i++ {
switch i % 2 {
case 0:
blocs = append(blocs, Bloc(blockn(i),
If("p", blockn(i+1), blockn(i+2))))
case 1:
blocs = append(blocs, Bloc(blockn(i),
If("p", blockn(i+1), blockn(i-1))))
}
}
blocs = append(blocs,
Bloc(blockn(size), Goto("exit")),
Bloc("exit", Exit("mem")),
)
return blocs
}
// genManyPred creates an array of blocks where 1/3rd have a successor of the
// first block, 1/3rd the last block, and the remaining third are plain.
func genManyPred(size int) []bloc {
var blocs []bloc
blocs = append(blocs,
Bloc("entry",
Valu("mem", OpInitMem, types.TypeMem, 0, nil),
Valu("p", OpConstBool, types.Types[types.TBOOL], 1, nil),
Goto(blockn(0)),
),
)
// We want predecessor lists to be long, so 2/3rds of the blocks have a
// successor of the first or last block.
for i := 0; i < size; i++ {
switch i % 3 {
case 0:
blocs = append(blocs, Bloc(blockn(i),
Valu("a", OpConstBool, types.Types[types.TBOOL], 1, nil),
Goto(blockn(i+1))))
case 1:
blocs = append(blocs, Bloc(blockn(i),
Valu("a", OpConstBool, types.Types[types.TBOOL], 1, nil),
If("p", blockn(i+1), blockn(0))))
case 2:
blocs = append(blocs, Bloc(blockn(i),
Valu("a", OpConstBool, types.Types[types.TBOOL], 1, nil),
If("p", blockn(i+1), blockn(size))))
}
}
blocs = append(blocs,
Bloc(blockn(size), Goto("exit")),
Bloc("exit", Exit("mem")),
)
return blocs
}
// genMaxPred maximizes the size of the 'exit' predecessor list.
func genMaxPred(size int) []bloc {
var blocs []bloc
blocs = append(blocs,
Bloc("entry",
Valu("mem", OpInitMem, types.TypeMem, 0, nil),
Valu("p", OpConstBool, types.Types[types.TBOOL], 1, nil),
Goto(blockn(0)),
),
)
for i := 0; i < size; i++ {
blocs = append(blocs, Bloc(blockn(i),
If("p", blockn(i+1), "exit")))
}
blocs = append(blocs,
Bloc(blockn(size), Goto("exit")),
Bloc("exit", Exit("mem")),
)
return blocs
}
// genMaxPredValue is identical to genMaxPred but contains an
// additional value.
func genMaxPredValue(size int) []bloc {
var blocs []bloc
blocs = append(blocs,
Bloc("entry",
Valu("mem", OpInitMem, types.TypeMem, 0, nil),
Valu("p", OpConstBool, types.Types[types.TBOOL], 1, nil),
Goto(blockn(0)),
),
)
for i := 0; i < size; i++ {
blocs = append(blocs, Bloc(blockn(i),
Valu("a", OpConstBool, types.Types[types.TBOOL], 1, nil),
If("p", blockn(i+1), "exit")))
}
blocs = append(blocs,
Bloc(blockn(size), Goto("exit")),
Bloc("exit", Exit("mem")),
)
return blocs
}
// sink for benchmark
var domBenchRes []*Block
func benchmarkDominators(b *testing.B, size int, bg blockGen) {
c := testConfig(b)
fun := c.Fun("entry", bg(size)...)
CheckFunc(fun.f)
b.SetBytes(int64(size))
b.ResetTimer()
for i := 0; i < b.N; i++ {
domBenchRes = dominators(fun.f)
}
}
type domFunc func(f *Func) []*Block
// verifyDominators verifies that the dominators of fut (function under test)
// as determined by domFn, match the map node->dominator
func verifyDominators(t *testing.T, fut fun, domFn domFunc, doms map[string]string) {
blockNames := map[*Block]string{}
for n, b := range fut.blocks {
blockNames[b] = n
}
calcDom := domFn(fut.f)
for n, d := range doms {
nblk, ok := fut.blocks[n]
if !ok {
t.Errorf("invalid block name %s", n)
}
dblk, ok := fut.blocks[d]
if !ok {
t.Errorf("invalid block name %s", d)
}
domNode := calcDom[nblk.ID]
switch {
case calcDom[nblk.ID] == dblk:
calcDom[nblk.ID] = nil
continue
case calcDom[nblk.ID] != dblk:
t.Errorf("expected %s as dominator of %s, found %s", d, n, blockNames[domNode])
default:
t.Fatal("unexpected dominator condition")
}
}
for id, d := range calcDom {
// If nil, we've already verified it
if d == nil {
continue
}
for _, b := range fut.blocks {
if int(b.ID) == id {
t.Errorf("unexpected dominator of %s for %s", blockNames[d], blockNames[b])
}
}
}
}
func TestDominatorsSingleBlock(t *testing.T) {
c := testConfig(t)
fun := c.Fun("entry",
Bloc("entry",
Valu("mem", OpInitMem, types.TypeMem, 0, nil),
Exit("mem")))
doms := map[string]string{}
CheckFunc(fun.f)
verifyDominators(t, fun, dominators, doms)
verifyDominators(t, fun, dominatorsSimple, doms)
}
func TestDominatorsSimple(t *testing.T) {
c := testConfig(t)
fun := c.Fun("entry",
Bloc("entry",
Valu("mem", OpInitMem, types.TypeMem, 0, nil),
Goto("a")),
Bloc("a",
Goto("b")),
Bloc("b",
Goto("c")),
Bloc("c",
Goto("exit")),
Bloc("exit",
Exit("mem")))
doms := map[string]string{
"a": "entry",
"b": "a",
"c": "b",
"exit": "c",
}
CheckFunc(fun.f)
verifyDominators(t, fun, dominators, doms)
verifyDominators(t, fun, dominatorsSimple, doms)
}
func TestDominatorsMultPredFwd(t *testing.T) {
c := testConfig(t)
fun := c.Fun("entry",
Bloc("entry",
Valu("mem", OpInitMem, types.TypeMem, 0, nil),
Valu("p", OpConstBool, types.Types[types.TBOOL], 1, nil),
If("p", "a", "c")),
Bloc("a",
If("p", "b", "c")),
Bloc("b",
Goto("c")),
Bloc("c",
Goto("exit")),
Bloc("exit",
Exit("mem")))
doms := map[string]string{
"a": "entry",
"b": "a",
"c": "entry",
"exit": "c",
}
CheckFunc(fun.f)
verifyDominators(t, fun, dominators, doms)
verifyDominators(t, fun, dominatorsSimple, doms)
}
func TestDominatorsDeadCode(t *testing.T) {
c := testConfig(t)
fun := c.Fun("entry",
Bloc("entry",
Valu("mem", OpInitMem, types.TypeMem, 0, nil),
Valu("p", OpConstBool, types.Types[types.TBOOL], 0, nil),
If("p", "b3", "b5")),
Bloc("b2", Exit("mem")),
Bloc("b3", Goto("b2")),
Bloc("b4", Goto("b2")),
Bloc("b5", Goto("b2")))
doms := map[string]string{
"b2": "entry",
"b3": "entry",
"b5": "entry",
}
CheckFunc(fun.f)
verifyDominators(t, fun, dominators, doms)
verifyDominators(t, fun, dominatorsSimple, doms)
}
func TestDominatorsMultPredRev(t *testing.T) {
c := testConfig(t)
fun := c.Fun("entry",
Bloc("entry",
Goto("first")),
Bloc("first",
Valu("mem", OpInitMem, types.TypeMem, 0, nil),
Valu("p", OpConstBool, types.Types[types.TBOOL], 1, nil),
Goto("a")),
Bloc("a",
If("p", "b", "first")),
Bloc("b",
Goto("c")),
Bloc("c",
If("p", "exit", "b")),
Bloc("exit",
Exit("mem")))
doms := map[string]string{
"first": "entry",
"a": "first",
"b": "a",
"c": "b",
"exit": "c",
}
CheckFunc(fun.f)
verifyDominators(t, fun, dominators, doms)
verifyDominators(t, fun, dominatorsSimple, doms)
}
func TestDominatorsMultPred(t *testing.T) {
c := testConfig(t)
fun := c.Fun("entry",
Bloc("entry",
Valu("mem", OpInitMem, types.TypeMem, 0, nil),
Valu("p", OpConstBool, types.Types[types.TBOOL], 1, nil),
If("p", "a", "c")),
Bloc("a",
If("p", "b", "c")),
Bloc("b",
Goto("c")),
Bloc("c",
If("p", "b", "exit")),
Bloc("exit",
Exit("mem")))
doms := map[string]string{
"a": "entry",
"b": "entry",
"c": "entry",
"exit": "c",
}
CheckFunc(fun.f)
verifyDominators(t, fun, dominators, doms)
verifyDominators(t, fun, dominatorsSimple, doms)
}
func TestInfiniteLoop(t *testing.T) {
c := testConfig(t)
// note lack of an exit block
fun := c.Fun("entry",
Bloc("entry",
Valu("mem", OpInitMem, types.TypeMem, 0, nil),
Valu("p", OpConstBool, types.Types[types.TBOOL], 1, nil),
Goto("a")),
Bloc("a",
Goto("b")),
Bloc("b",
Goto("a")))
CheckFunc(fun.f)
doms := map[string]string{"a": "entry",
"b": "a"}
verifyDominators(t, fun, dominators, doms)
}
func TestDomTricky(t *testing.T) {
doms := map[string]string{
"4": "1",
"2": "4",
"5": "4",
"11": "4",
"15": "4", // the incorrect answer is "5"
"10": "15",
"19": "15",
}
if4 := [2]string{"2", "5"}
if5 := [2]string{"15", "11"}
if15 := [2]string{"19", "10"}
for i := 0; i < 8; i++ {
a := 1 & i
b := 1 & i >> 1
c := 1 & i >> 2
cfg := testConfig(t)
fun := cfg.Fun("1",
Bloc("1",
Valu("mem", OpInitMem, types.TypeMem, 0, nil),
Valu("p", OpConstBool, types.Types[types.TBOOL], 1, nil),
Goto("4")),
Bloc("2",
Goto("11")),
Bloc("4",
If("p", if4[a], if4[1-a])), // 2, 5
Bloc("5",
If("p", if5[b], if5[1-b])), //15, 11
Bloc("10",
Exit("mem")),
Bloc("11",
Goto("15")),
Bloc("15",
If("p", if15[c], if15[1-c])), //19, 10
Bloc("19",
Goto("10")))
CheckFunc(fun.f)
verifyDominators(t, fun, dominators, doms)
verifyDominators(t, fun, dominatorsSimple, doms)
}
}
// generateDominatorMap uses dominatorsSimple to obtain a
// reference dominator tree for testing faster algorithms.
func generateDominatorMap(fut fun) map[string]string {
blockNames := map[*Block]string{}
for n, b := range fut.blocks {
blockNames[b] = n
}
referenceDom := dominatorsSimple(fut.f)
doms := make(map[string]string)
for _, b := range fut.f.Blocks {
if d := referenceDom[b.ID]; d != nil {
doms[blockNames[b]] = blockNames[d]
}
}
return doms
}
func TestDominatorsPostTrickyA(t *testing.T) {
testDominatorsPostTricky(t, "b8", "b11", "b10", "b8", "b14", "b15")
}
func TestDominatorsPostTrickyB(t *testing.T) {
testDominatorsPostTricky(t, "b11", "b8", "b10", "b8", "b14", "b15")
}
func TestDominatorsPostTrickyC(t *testing.T) {
testDominatorsPostTricky(t, "b8", "b11", "b8", "b10", "b14", "b15")
}
func TestDominatorsPostTrickyD(t *testing.T) {
testDominatorsPostTricky(t, "b11", "b8", "b8", "b10", "b14", "b15")
}
func TestDominatorsPostTrickyE(t *testing.T) {
testDominatorsPostTricky(t, "b8", "b11", "b10", "b8", "b15", "b14")
}
func TestDominatorsPostTrickyF(t *testing.T) {
testDominatorsPostTricky(t, "b11", "b8", "b10", "b8", "b15", "b14")
}
func TestDominatorsPostTrickyG(t *testing.T) {
testDominatorsPostTricky(t, "b8", "b11", "b8", "b10", "b15", "b14")
}
func TestDominatorsPostTrickyH(t *testing.T) {
testDominatorsPostTricky(t, "b11", "b8", "b8", "b10", "b15", "b14")
}
func testDominatorsPostTricky(t *testing.T, b7then, b7else, b12then, b12else, b13then, b13else string) {
c := testConfig(t)
fun := c.Fun("b1",
Bloc("b1",
Valu("mem", OpInitMem, types.TypeMem, 0, nil),
Valu("p", OpConstBool, types.Types[types.TBOOL], 1, nil),
If("p", "b3", "b2")),
Bloc("b3",
If("p", "b5", "b6")),
Bloc("b5",
Goto("b7")),
Bloc("b7",
If("p", b7then, b7else)),
Bloc("b8",
Goto("b13")),
Bloc("b13",
If("p", b13then, b13else)),
Bloc("b14",
Goto("b10")),
Bloc("b15",
Goto("b16")),
Bloc("b16",
Goto("b9")),
Bloc("b9",
Goto("b7")),
Bloc("b11",
Goto("b12")),
Bloc("b12",
If("p", b12then, b12else)),
Bloc("b10",
Goto("b6")),
Bloc("b6",
Goto("b17")),
Bloc("b17",
Goto("b18")),
Bloc("b18",
If("p", "b22", "b19")),
Bloc("b22",
Goto("b23")),
Bloc("b23",
If("p", "b21", "b19")),
Bloc("b19",
If("p", "b24", "b25")),
Bloc("b24",
Goto("b26")),
Bloc("b26",
Goto("b25")),
Bloc("b25",
If("p", "b27", "b29")),
Bloc("b27",
Goto("b30")),
Bloc("b30",
Goto("b28")),
Bloc("b29",
Goto("b31")),
Bloc("b31",
Goto("b28")),
Bloc("b28",
If("p", "b32", "b33")),
Bloc("b32",
Goto("b21")),
Bloc("b21",
Goto("b47")),
Bloc("b47",
If("p", "b45", "b46")),
Bloc("b45",
Goto("b48")),
Bloc("b48",
Goto("b49")),
Bloc("b49",
If("p", "b50", "b51")),
Bloc("b50",
Goto("b52")),
Bloc("b52",
Goto("b53")),
Bloc("b53",
Goto("b51")),
Bloc("b51",
Goto("b54")),
Bloc("b54",
Goto("b46")),
Bloc("b46",
Exit("mem")),
Bloc("b33",
Goto("b34")),
Bloc("b34",
Goto("b37")),
Bloc("b37",
If("p", "b35", "b36")),
Bloc("b35",
Goto("b38")),
Bloc("b38",
Goto("b39")),
Bloc("b39",
If("p", "b40", "b41")),
Bloc("b40",
Goto("b42")),
Bloc("b42",
Goto("b43")),
Bloc("b43",
Goto("b41")),
Bloc("b41",
Goto("b44")),
Bloc("b44",
Goto("b36")),
Bloc("b36",
Goto("b20")),
Bloc("b20",
Goto("b18")),
Bloc("b2",
Goto("b4")),
Bloc("b4",
Exit("mem")))
CheckFunc(fun.f)
doms := generateDominatorMap(fun)
verifyDominators(t, fun, dominators, doms)
}