dom_test.go

Documentation: cmd/compile/internal/ssa

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