Source file src/cmd/compile/internal/ssacompile/dom_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  package ssacompile
     6  
     7  import (
     8  	"testing"
     9  
    10  	"cmd/compile/internal/ssa"
    11  	"cmd/compile/internal/ssa/ssaop"
    12  	"cmd/compile/internal/types"
    13  )
    14  
    15  func BenchmarkDominatorsLinear(b *testing.B)     { benchmarkDominators(b, 10000, genLinear) }
    16  func BenchmarkDominatorsFwdBack(b *testing.B)    { benchmarkDominators(b, 10000, genFwdBack) }
    17  func BenchmarkDominatorsManyPred(b *testing.B)   { benchmarkDominators(b, 10000, genManyPred) }
    18  func BenchmarkDominatorsMaxPred(b *testing.B)    { benchmarkDominators(b, 10000, genMaxPred) }
    19  func BenchmarkDominatorsMaxPredVal(b *testing.B) { benchmarkDominators(b, 10000, genMaxPredValue) }
    20  
    21  type blockGen func(size int) []bloc
    22  
    23  // genLinear creates an array of blocks that succeed one another
    24  // b_n -> [b_n+1].
    25  func genLinear(size int) []bloc {
    26  	var blocs []bloc
    27  	blocs = append(blocs,
    28  		Bloc("entry",
    29  			Valu("mem", ssaop.OpInitMem, types.TypeMem, 0, nil),
    30  			Goto(blockn(0)),
    31  		),
    32  	)
    33  	for i := 0; i < size; i++ {
    34  		blocs = append(blocs, Bloc(blockn(i),
    35  			Goto(blockn(i+1))))
    36  	}
    37  
    38  	blocs = append(blocs,
    39  		Bloc(blockn(size), Goto("exit")),
    40  		Bloc("exit", Exit("mem")),
    41  	)
    42  
    43  	return blocs
    44  }
    45  
    46  // genFwdBack creates an array of blocks that alternate between
    47  // b_n -> [b_n+1], b_n -> [b_n+1, b_n-1] , b_n -> [b_n+1, b_n+2]
    48  func genFwdBack(size int) []bloc {
    49  	var blocs []bloc
    50  	blocs = append(blocs,
    51  		Bloc("entry",
    52  			Valu("mem", ssaop.OpInitMem, types.TypeMem, 0, nil),
    53  			Valu("p", ssaop.OpConstBool, types.Types[types.TBOOL], 1, nil),
    54  			Goto(blockn(0)),
    55  		),
    56  	)
    57  	for i := 0; i < size; i++ {
    58  		switch i % 2 {
    59  		case 0:
    60  			blocs = append(blocs, Bloc(blockn(i),
    61  				If("p", blockn(i+1), blockn(i+2))))
    62  		case 1:
    63  			blocs = append(blocs, Bloc(blockn(i),
    64  				If("p", blockn(i+1), blockn(i-1))))
    65  		}
    66  	}
    67  
    68  	blocs = append(blocs,
    69  		Bloc(blockn(size), Goto("exit")),
    70  		Bloc("exit", Exit("mem")),
    71  	)
    72  
    73  	return blocs
    74  }
    75  
    76  // genManyPred creates an array of blocks where 1/3rd have a successor of the
    77  // first block, 1/3rd the last block, and the remaining third are plain.
    78  func genManyPred(size int) []bloc {
    79  	var blocs []bloc
    80  	blocs = append(blocs,
    81  		Bloc("entry",
    82  			Valu("mem", ssaop.OpInitMem, types.TypeMem, 0, nil),
    83  			Valu("p", ssaop.OpConstBool, types.Types[types.TBOOL], 1, nil),
    84  			Goto(blockn(0)),
    85  		),
    86  	)
    87  
    88  	// We want predecessor lists to be long, so 2/3rds of the blocks have a
    89  	// successor of the first or last block.
    90  	for i := 0; i < size; i++ {
    91  		switch i % 3 {
    92  		case 0:
    93  			blocs = append(blocs, Bloc(blockn(i),
    94  				Valu("a", ssaop.OpConstBool, types.Types[types.TBOOL], 1, nil),
    95  				Goto(blockn(i+1))))
    96  		case 1:
    97  			blocs = append(blocs, Bloc(blockn(i),
    98  				Valu("a", ssaop.OpConstBool, types.Types[types.TBOOL], 1, nil),
    99  				If("p", blockn(i+1), blockn(0))))
   100  		case 2:
   101  			blocs = append(blocs, Bloc(blockn(i),
   102  				Valu("a", ssaop.OpConstBool, types.Types[types.TBOOL], 1, nil),
   103  				If("p", blockn(i+1), blockn(size))))
   104  		}
   105  	}
   106  
   107  	blocs = append(blocs,
   108  		Bloc(blockn(size), Goto("exit")),
   109  		Bloc("exit", Exit("mem")),
   110  	)
   111  
   112  	return blocs
   113  }
   114  
   115  // genMaxPred maximizes the size of the 'exit' predecessor list.
   116  func genMaxPred(size int) []bloc {
   117  	var blocs []bloc
   118  	blocs = append(blocs,
   119  		Bloc("entry",
   120  			Valu("mem", ssaop.OpInitMem, types.TypeMem, 0, nil),
   121  			Valu("p", ssaop.OpConstBool, types.Types[types.TBOOL], 1, nil),
   122  			Goto(blockn(0)),
   123  		),
   124  	)
   125  
   126  	for i := 0; i < size; i++ {
   127  		blocs = append(blocs, Bloc(blockn(i),
   128  			If("p", blockn(i+1), "exit")))
   129  	}
   130  
   131  	blocs = append(blocs,
   132  		Bloc(blockn(size), Goto("exit")),
   133  		Bloc("exit", Exit("mem")),
   134  	)
   135  
   136  	return blocs
   137  }
   138  
   139  // genMaxPredValue is identical to genMaxPred but contains an
   140  // additional value.
   141  func genMaxPredValue(size int) []bloc {
   142  	var blocs []bloc
   143  	blocs = append(blocs,
   144  		Bloc("entry",
   145  			Valu("mem", ssaop.OpInitMem, types.TypeMem, 0, nil),
   146  			Valu("p", ssaop.OpConstBool, types.Types[types.TBOOL], 1, nil),
   147  			Goto(blockn(0)),
   148  		),
   149  	)
   150  
   151  	for i := 0; i < size; i++ {
   152  		blocs = append(blocs, Bloc(blockn(i),
   153  			Valu("a", ssaop.OpConstBool, types.Types[types.TBOOL], 1, nil),
   154  			If("p", blockn(i+1), "exit")))
   155  	}
   156  
   157  	blocs = append(blocs,
   158  		Bloc(blockn(size), Goto("exit")),
   159  		Bloc("exit", Exit("mem")),
   160  	)
   161  
   162  	return blocs
   163  }
   164  
   165  // sink for benchmark
   166  var domBenchRes []*ssa.Block
   167  
   168  func benchmarkDominators(b *testing.B, size int, bg blockGen) {
   169  	c := testConfig(b)
   170  	fun := c.Fun("entry", bg(size)...)
   171  
   172  	CheckFunc(fun.f)
   173  	b.SetBytes(int64(size))
   174  	b.ResetTimer()
   175  	for i := 0; i < b.N; i++ {
   176  		domBenchRes = ssa.Dominators(fun.f)
   177  	}
   178  }
   179  
   180  type domFunc func(f *ssa.Func) []*ssa.Block
   181  
   182  // verifyDominators verifies that the dominators of fut (function under test)
   183  // as determined by domFn, match the map node->dominator
   184  func verifyDominators(t *testing.T, fut fun, domFn domFunc, doms map[string]string) {
   185  	blockNames := map[*ssa.Block]string{}
   186  	for n, b := range fut.blocks {
   187  		blockNames[b] = n
   188  	}
   189  
   190  	calcDom := domFn(fut.f)
   191  
   192  	for n, d := range doms {
   193  		nblk, ok := fut.blocks[n]
   194  		if !ok {
   195  			t.Errorf("invalid block name %s", n)
   196  		}
   197  		dblk, ok := fut.blocks[d]
   198  		if !ok {
   199  			t.Errorf("invalid block name %s", d)
   200  		}
   201  
   202  		domNode := calcDom[nblk.ID]
   203  		switch {
   204  		case calcDom[nblk.ID] == dblk:
   205  			calcDom[nblk.ID] = nil
   206  			continue
   207  		case calcDom[nblk.ID] != dblk:
   208  			t.Errorf("expected %s as dominator of %s, found %s", d, n, blockNames[domNode])
   209  		default:
   210  			t.Fatal("unexpected dominator condition")
   211  		}
   212  	}
   213  
   214  	for id, d := range calcDom {
   215  		// If nil, we've already verified it
   216  		if d == nil {
   217  			continue
   218  		}
   219  		for _, b := range fut.blocks {
   220  			if int(b.ID) == id {
   221  				t.Errorf("unexpected dominator of %s for %s", blockNames[d], blockNames[b])
   222  			}
   223  		}
   224  	}
   225  
   226  }
   227  
   228  func TestDominatorsSingleBlock(t *testing.T) {
   229  	c := testConfig(t)
   230  	fun := c.Fun("entry",
   231  		Bloc("entry",
   232  			Valu("mem", ssaop.OpInitMem, types.TypeMem, 0, nil),
   233  			Exit("mem")))
   234  
   235  	doms := map[string]string{}
   236  
   237  	CheckFunc(fun.f)
   238  	verifyDominators(t, fun, ssa.Dominators, doms)
   239  	verifyDominators(t, fun, ssa.DominatorsSimple, doms)
   240  
   241  }
   242  
   243  func TestDominatorsSimple(t *testing.T) {
   244  	c := testConfig(t)
   245  	fun := c.Fun("entry",
   246  		Bloc("entry",
   247  			Valu("mem", ssaop.OpInitMem, types.TypeMem, 0, nil),
   248  			Goto("a")),
   249  		Bloc("a",
   250  			Goto("b")),
   251  		Bloc("b",
   252  			Goto("c")),
   253  		Bloc("c",
   254  			Goto("exit")),
   255  		Bloc("exit",
   256  			Exit("mem")))
   257  
   258  	doms := map[string]string{
   259  		"a":    "entry",
   260  		"b":    "a",
   261  		"c":    "b",
   262  		"exit": "c",
   263  	}
   264  
   265  	CheckFunc(fun.f)
   266  	verifyDominators(t, fun, ssa.Dominators, doms)
   267  	verifyDominators(t, fun, ssa.DominatorsSimple, doms)
   268  
   269  }
   270  
   271  func TestDominatorsMultPredFwd(t *testing.T) {
   272  	c := testConfig(t)
   273  	fun := c.Fun("entry",
   274  		Bloc("entry",
   275  			Valu("mem", ssaop.OpInitMem, types.TypeMem, 0, nil),
   276  			Valu("p", ssaop.OpConstBool, types.Types[types.TBOOL], 1, nil),
   277  			If("p", "a", "c")),
   278  		Bloc("a",
   279  			If("p", "b", "c")),
   280  		Bloc("b",
   281  			Goto("c")),
   282  		Bloc("c",
   283  			Goto("exit")),
   284  		Bloc("exit",
   285  			Exit("mem")))
   286  
   287  	doms := map[string]string{
   288  		"a":    "entry",
   289  		"b":    "a",
   290  		"c":    "entry",
   291  		"exit": "c",
   292  	}
   293  
   294  	CheckFunc(fun.f)
   295  	verifyDominators(t, fun, ssa.Dominators, doms)
   296  	verifyDominators(t, fun, ssa.DominatorsSimple, doms)
   297  }
   298  
   299  func TestDominatorsDeadCode(t *testing.T) {
   300  	c := testConfig(t)
   301  	fun := c.Fun("entry",
   302  		Bloc("entry",
   303  			Valu("mem", ssaop.OpInitMem, types.TypeMem, 0, nil),
   304  			Valu("p", ssaop.OpConstBool, types.Types[types.TBOOL], 0, nil),
   305  			If("p", "b3", "b5")),
   306  		Bloc("b2", Exit("mem")),
   307  		Bloc("b3", Goto("b2")),
   308  		Bloc("b4", Goto("b2")),
   309  		Bloc("b5", Goto("b2")))
   310  
   311  	doms := map[string]string{
   312  		"b2": "entry",
   313  		"b3": "entry",
   314  		"b5": "entry",
   315  	}
   316  
   317  	CheckFunc(fun.f)
   318  	verifyDominators(t, fun, ssa.Dominators, doms)
   319  	verifyDominators(t, fun, ssa.DominatorsSimple, doms)
   320  }
   321  
   322  func TestDominatorsMultPredRev(t *testing.T) {
   323  	c := testConfig(t)
   324  	fun := c.Fun("entry",
   325  		Bloc("entry",
   326  			Goto("first")),
   327  		Bloc("first",
   328  			Valu("mem", ssaop.OpInitMem, types.TypeMem, 0, nil),
   329  			Valu("p", ssaop.OpConstBool, types.Types[types.TBOOL], 1, nil),
   330  			Goto("a")),
   331  		Bloc("a",
   332  			If("p", "b", "first")),
   333  		Bloc("b",
   334  			Goto("c")),
   335  		Bloc("c",
   336  			If("p", "exit", "b")),
   337  		Bloc("exit",
   338  			Exit("mem")))
   339  
   340  	doms := map[string]string{
   341  		"first": "entry",
   342  		"a":     "first",
   343  		"b":     "a",
   344  		"c":     "b",
   345  		"exit":  "c",
   346  	}
   347  
   348  	CheckFunc(fun.f)
   349  	verifyDominators(t, fun, ssa.Dominators, doms)
   350  	verifyDominators(t, fun, ssa.DominatorsSimple, doms)
   351  }
   352  
   353  func TestDominatorsMultPred(t *testing.T) {
   354  	c := testConfig(t)
   355  	fun := c.Fun("entry",
   356  		Bloc("entry",
   357  			Valu("mem", ssaop.OpInitMem, types.TypeMem, 0, nil),
   358  			Valu("p", ssaop.OpConstBool, types.Types[types.TBOOL], 1, nil),
   359  			If("p", "a", "c")),
   360  		Bloc("a",
   361  			If("p", "b", "c")),
   362  		Bloc("b",
   363  			Goto("c")),
   364  		Bloc("c",
   365  			If("p", "b", "exit")),
   366  		Bloc("exit",
   367  			Exit("mem")))
   368  
   369  	doms := map[string]string{
   370  		"a":    "entry",
   371  		"b":    "entry",
   372  		"c":    "entry",
   373  		"exit": "c",
   374  	}
   375  
   376  	CheckFunc(fun.f)
   377  	verifyDominators(t, fun, ssa.Dominators, doms)
   378  	verifyDominators(t, fun, ssa.DominatorsSimple, doms)
   379  }
   380  
   381  func TestInfiniteLoop(t *testing.T) {
   382  	c := testConfig(t)
   383  	// note lack of an exit block
   384  	fun := c.Fun("entry",
   385  		Bloc("entry",
   386  			Valu("mem", ssaop.OpInitMem, types.TypeMem, 0, nil),
   387  			Valu("p", ssaop.OpConstBool, types.Types[types.TBOOL], 1, nil),
   388  			Goto("a")),
   389  		Bloc("a",
   390  			Goto("b")),
   391  		Bloc("b",
   392  			Goto("a")))
   393  
   394  	CheckFunc(fun.f)
   395  	doms := map[string]string{"a": "entry",
   396  		"b": "a"}
   397  	verifyDominators(t, fun, ssa.Dominators, doms)
   398  }
   399  
   400  func TestDomTricky(t *testing.T) {
   401  	doms := map[string]string{
   402  		"4":  "1",
   403  		"2":  "4",
   404  		"5":  "4",
   405  		"11": "4",
   406  		"15": "4", // the incorrect answer is "5"
   407  		"10": "15",
   408  		"19": "15",
   409  	}
   410  
   411  	if4 := [2]string{"2", "5"}
   412  	if5 := [2]string{"15", "11"}
   413  	if15 := [2]string{"19", "10"}
   414  
   415  	for i := 0; i < 8; i++ {
   416  		a := 1 & i
   417  		b := 1 & i >> 1
   418  		c := 1 & i >> 2
   419  
   420  		cfg := testConfig(t)
   421  		fun := cfg.Fun("1",
   422  			Bloc("1",
   423  				Valu("mem", ssaop.OpInitMem, types.TypeMem, 0, nil),
   424  				Valu("p", ssaop.OpConstBool, types.Types[types.TBOOL], 1, nil),
   425  				Goto("4")),
   426  			Bloc("2",
   427  				Goto("11")),
   428  			Bloc("4",
   429  				If("p", if4[a], if4[1-a])), // 2, 5
   430  			Bloc("5",
   431  				If("p", if5[b], if5[1-b])), //15, 11
   432  			Bloc("10",
   433  				Exit("mem")),
   434  			Bloc("11",
   435  				Goto("15")),
   436  			Bloc("15",
   437  				If("p", if15[c], if15[1-c])), //19, 10
   438  			Bloc("19",
   439  				Goto("10")))
   440  		CheckFunc(fun.f)
   441  		verifyDominators(t, fun, ssa.Dominators, doms)
   442  		verifyDominators(t, fun, ssa.DominatorsSimple, doms)
   443  	}
   444  }
   445  
   446  // generateDominatorMap uses dominatorsSimple to obtain a
   447  // reference dominator tree for testing faster algorithms.
   448  func generateDominatorMap(fut fun) map[string]string {
   449  	blockNames := map[*ssa.Block]string{}
   450  	for n, b := range fut.blocks {
   451  		blockNames[b] = n
   452  	}
   453  	referenceDom := ssa.DominatorsSimple(fut.f)
   454  	doms := make(map[string]string)
   455  	for _, b := range fut.f.Blocks {
   456  		if d := referenceDom[b.ID]; d != nil {
   457  			doms[blockNames[b]] = blockNames[d]
   458  		}
   459  	}
   460  	return doms
   461  }
   462  
   463  func TestDominatorsPostTrickyA(t *testing.T) {
   464  	testDominatorsPostTricky(t, "b8", "b11", "b10", "b8", "b14", "b15")
   465  }
   466  
   467  func TestDominatorsPostTrickyB(t *testing.T) {
   468  	testDominatorsPostTricky(t, "b11", "b8", "b10", "b8", "b14", "b15")
   469  }
   470  
   471  func TestDominatorsPostTrickyC(t *testing.T) {
   472  	testDominatorsPostTricky(t, "b8", "b11", "b8", "b10", "b14", "b15")
   473  }
   474  
   475  func TestDominatorsPostTrickyD(t *testing.T) {
   476  	testDominatorsPostTricky(t, "b11", "b8", "b8", "b10", "b14", "b15")
   477  }
   478  
   479  func TestDominatorsPostTrickyE(t *testing.T) {
   480  	testDominatorsPostTricky(t, "b8", "b11", "b10", "b8", "b15", "b14")
   481  }
   482  
   483  func TestDominatorsPostTrickyF(t *testing.T) {
   484  	testDominatorsPostTricky(t, "b11", "b8", "b10", "b8", "b15", "b14")
   485  }
   486  
   487  func TestDominatorsPostTrickyG(t *testing.T) {
   488  	testDominatorsPostTricky(t, "b8", "b11", "b8", "b10", "b15", "b14")
   489  }
   490  
   491  func TestDominatorsPostTrickyH(t *testing.T) {
   492  	testDominatorsPostTricky(t, "b11", "b8", "b8", "b10", "b15", "b14")
   493  }
   494  
   495  func testDominatorsPostTricky(t *testing.T, b7then, b7else, b12then, b12else, b13then, b13else string) {
   496  	c := testConfig(t)
   497  	fun := c.Fun("b1",
   498  		Bloc("b1",
   499  			Valu("mem", ssaop.OpInitMem, types.TypeMem, 0, nil),
   500  			Valu("p", ssaop.OpConstBool, types.Types[types.TBOOL], 1, nil),
   501  			If("p", "b3", "b2")),
   502  		Bloc("b3",
   503  			If("p", "b5", "b6")),
   504  		Bloc("b5",
   505  			Goto("b7")),
   506  		Bloc("b7",
   507  			If("p", b7then, b7else)),
   508  		Bloc("b8",
   509  			Goto("b13")),
   510  		Bloc("b13",
   511  			If("p", b13then, b13else)),
   512  		Bloc("b14",
   513  			Goto("b10")),
   514  		Bloc("b15",
   515  			Goto("b16")),
   516  		Bloc("b16",
   517  			Goto("b9")),
   518  		Bloc("b9",
   519  			Goto("b7")),
   520  		Bloc("b11",
   521  			Goto("b12")),
   522  		Bloc("b12",
   523  			If("p", b12then, b12else)),
   524  		Bloc("b10",
   525  			Goto("b6")),
   526  		Bloc("b6",
   527  			Goto("b17")),
   528  		Bloc("b17",
   529  			Goto("b18")),
   530  		Bloc("b18",
   531  			If("p", "b22", "b19")),
   532  		Bloc("b22",
   533  			Goto("b23")),
   534  		Bloc("b23",
   535  			If("p", "b21", "b19")),
   536  		Bloc("b19",
   537  			If("p", "b24", "b25")),
   538  		Bloc("b24",
   539  			Goto("b26")),
   540  		Bloc("b26",
   541  			Goto("b25")),
   542  		Bloc("b25",
   543  			If("p", "b27", "b29")),
   544  		Bloc("b27",
   545  			Goto("b30")),
   546  		Bloc("b30",
   547  			Goto("b28")),
   548  		Bloc("b29",
   549  			Goto("b31")),
   550  		Bloc("b31",
   551  			Goto("b28")),
   552  		Bloc("b28",
   553  			If("p", "b32", "b33")),
   554  		Bloc("b32",
   555  			Goto("b21")),
   556  		Bloc("b21",
   557  			Goto("b47")),
   558  		Bloc("b47",
   559  			If("p", "b45", "b46")),
   560  		Bloc("b45",
   561  			Goto("b48")),
   562  		Bloc("b48",
   563  			Goto("b49")),
   564  		Bloc("b49",
   565  			If("p", "b50", "b51")),
   566  		Bloc("b50",
   567  			Goto("b52")),
   568  		Bloc("b52",
   569  			Goto("b53")),
   570  		Bloc("b53",
   571  			Goto("b51")),
   572  		Bloc("b51",
   573  			Goto("b54")),
   574  		Bloc("b54",
   575  			Goto("b46")),
   576  		Bloc("b46",
   577  			Exit("mem")),
   578  		Bloc("b33",
   579  			Goto("b34")),
   580  		Bloc("b34",
   581  			Goto("b37")),
   582  		Bloc("b37",
   583  			If("p", "b35", "b36")),
   584  		Bloc("b35",
   585  			Goto("b38")),
   586  		Bloc("b38",
   587  			Goto("b39")),
   588  		Bloc("b39",
   589  			If("p", "b40", "b41")),
   590  		Bloc("b40",
   591  			Goto("b42")),
   592  		Bloc("b42",
   593  			Goto("b43")),
   594  		Bloc("b43",
   595  			Goto("b41")),
   596  		Bloc("b41",
   597  			Goto("b44")),
   598  		Bloc("b44",
   599  			Goto("b36")),
   600  		Bloc("b36",
   601  			Goto("b20")),
   602  		Bloc("b20",
   603  			Goto("b18")),
   604  		Bloc("b2",
   605  			Goto("b4")),
   606  		Bloc("b4",
   607  			Exit("mem")))
   608  	CheckFunc(fun.f)
   609  	doms := generateDominatorMap(fun)
   610  	verifyDominators(t, fun, ssa.Dominators, doms)
   611  }
   612  

View as plain text