Source file src/cmd/compile/internal/ssa/nilcheck_test.go

     1  package ssa
     2  
     3  import (
     4  	"cmd/compile/internal/types"
     5  	"strconv"
     6  	"testing"
     7  )
     8  
     9  func BenchmarkNilCheckDeep1(b *testing.B)     { benchmarkNilCheckDeep(b, 1) }
    10  func BenchmarkNilCheckDeep10(b *testing.B)    { benchmarkNilCheckDeep(b, 10) }
    11  func BenchmarkNilCheckDeep100(b *testing.B)   { benchmarkNilCheckDeep(b, 100) }
    12  func BenchmarkNilCheckDeep1000(b *testing.B)  { benchmarkNilCheckDeep(b, 1000) }
    13  func BenchmarkNilCheckDeep10000(b *testing.B) { benchmarkNilCheckDeep(b, 10000) }
    14  
    15  // benchmarkNilCheckDeep is a stress test of nilcheckelim.
    16  // It uses the worst possible input: A linear string of
    17  // nil checks, none of which can be eliminated.
    18  // Run with multiple depths to observe big-O behavior.
    19  func benchmarkNilCheckDeep(b *testing.B, depth int) {
    20  	c := testConfig(b)
    21  	ptrType := c.config.Types.BytePtr
    22  
    23  	var blocs []bloc
    24  	blocs = append(blocs,
    25  		Bloc("entry",
    26  			Valu("mem", OpInitMem, types.TypeMem, 0, nil),
    27  			Valu("sb", OpSB, c.config.Types.Uintptr, 0, nil),
    28  			Goto(blockn(0)),
    29  		),
    30  	)
    31  	for i := 0; i < depth; i++ {
    32  		blocs = append(blocs,
    33  			Bloc(blockn(i),
    34  				Valu(ptrn(i), OpAddr, ptrType, 0, nil, "sb"),
    35  				Valu(booln(i), OpIsNonNil, c.config.Types.Bool, 0, nil, ptrn(i)),
    36  				If(booln(i), blockn(i+1), "exit"),
    37  			),
    38  		)
    39  	}
    40  	blocs = append(blocs,
    41  		Bloc(blockn(depth), Goto("exit")),
    42  		Bloc("exit", Exit("mem")),
    43  	)
    44  
    45  	fun := c.Fun("entry", blocs...)
    46  
    47  	CheckFunc(fun.f)
    48  	b.SetBytes(int64(depth)) // helps for eyeballing linearity
    49  	b.ResetTimer()
    50  	b.ReportAllocs()
    51  
    52  	for i := 0; i < b.N; i++ {
    53  		nilcheckelim(fun.f)
    54  	}
    55  }
    56  
    57  func blockn(n int) string { return "b" + strconv.Itoa(n) }
    58  func ptrn(n int) string   { return "p" + strconv.Itoa(n) }
    59  func booln(n int) string  { return "c" + strconv.Itoa(n) }
    60  
    61  func isNilCheck(b *Block) bool {
    62  	return b.Kind == BlockIf && b.Controls[0].Op == OpIsNonNil
    63  }
    64  
    65  // TestNilcheckSimple verifies that a second repeated nilcheck is removed.
    66  func TestNilcheckSimple(t *testing.T) {
    67  	c := testConfig(t)
    68  	ptrType := c.config.Types.BytePtr
    69  	fun := c.Fun("entry",
    70  		Bloc("entry",
    71  			Valu("mem", OpInitMem, types.TypeMem, 0, nil),
    72  			Valu("sb", OpSB, c.config.Types.Uintptr, 0, nil),
    73  			Goto("checkPtr")),
    74  		Bloc("checkPtr",
    75  			Valu("ptr1", OpLoad, ptrType, 0, nil, "sb", "mem"),
    76  			Valu("bool1", OpIsNonNil, c.config.Types.Bool, 0, nil, "ptr1"),
    77  			If("bool1", "secondCheck", "exit")),
    78  		Bloc("secondCheck",
    79  			Valu("bool2", OpIsNonNil, c.config.Types.Bool, 0, nil, "ptr1"),
    80  			If("bool2", "extra", "exit")),
    81  		Bloc("extra",
    82  			Goto("exit")),
    83  		Bloc("exit",
    84  			Exit("mem")))
    85  
    86  	CheckFunc(fun.f)
    87  	nilcheckelim(fun.f)
    88  
    89  	// clean up the removed nil check
    90  	fuse(fun.f, fuseTypePlain)
    91  	deadcode(fun.f)
    92  
    93  	CheckFunc(fun.f)
    94  	for _, b := range fun.f.Blocks {
    95  		if b == fun.blocks["secondCheck"] && isNilCheck(b) {
    96  			t.Errorf("secondCheck was not eliminated")
    97  		}
    98  	}
    99  }
   100  
   101  // TestNilcheckDomOrder ensures that the nil check elimination isn't dependent
   102  // on the order of the dominees.
   103  func TestNilcheckDomOrder(t *testing.T) {
   104  	c := testConfig(t)
   105  	ptrType := c.config.Types.BytePtr
   106  	fun := c.Fun("entry",
   107  		Bloc("entry",
   108  			Valu("mem", OpInitMem, types.TypeMem, 0, nil),
   109  			Valu("sb", OpSB, c.config.Types.Uintptr, 0, nil),
   110  			Goto("checkPtr")),
   111  		Bloc("checkPtr",
   112  			Valu("ptr1", OpLoad, ptrType, 0, nil, "sb", "mem"),
   113  			Valu("bool1", OpIsNonNil, c.config.Types.Bool, 0, nil, "ptr1"),
   114  			If("bool1", "secondCheck", "exit")),
   115  		Bloc("exit",
   116  			Exit("mem")),
   117  		Bloc("secondCheck",
   118  			Valu("bool2", OpIsNonNil, c.config.Types.Bool, 0, nil, "ptr1"),
   119  			If("bool2", "extra", "exit")),
   120  		Bloc("extra",
   121  			Goto("exit")))
   122  
   123  	CheckFunc(fun.f)
   124  	nilcheckelim(fun.f)
   125  
   126  	// clean up the removed nil check
   127  	fuse(fun.f, fuseTypePlain)
   128  	deadcode(fun.f)
   129  
   130  	CheckFunc(fun.f)
   131  	for _, b := range fun.f.Blocks {
   132  		if b == fun.blocks["secondCheck"] && isNilCheck(b) {
   133  			t.Errorf("secondCheck was not eliminated")
   134  		}
   135  	}
   136  }
   137  
   138  // TestNilcheckAddr verifies that nilchecks of OpAddr constructed values are removed.
   139  func TestNilcheckAddr(t *testing.T) {
   140  	c := testConfig(t)
   141  	ptrType := c.config.Types.BytePtr
   142  	fun := c.Fun("entry",
   143  		Bloc("entry",
   144  			Valu("mem", OpInitMem, types.TypeMem, 0, nil),
   145  			Valu("sb", OpSB, c.config.Types.Uintptr, 0, nil),
   146  			Goto("checkPtr")),
   147  		Bloc("checkPtr",
   148  			Valu("ptr1", OpAddr, ptrType, 0, nil, "sb"),
   149  			Valu("bool1", OpIsNonNil, c.config.Types.Bool, 0, nil, "ptr1"),
   150  			If("bool1", "extra", "exit")),
   151  		Bloc("extra",
   152  			Goto("exit")),
   153  		Bloc("exit",
   154  			Exit("mem")))
   155  
   156  	CheckFunc(fun.f)
   157  	nilcheckelim(fun.f)
   158  
   159  	// clean up the removed nil check
   160  	fuse(fun.f, fuseTypePlain)
   161  	deadcode(fun.f)
   162  
   163  	CheckFunc(fun.f)
   164  	for _, b := range fun.f.Blocks {
   165  		if b == fun.blocks["checkPtr"] && isNilCheck(b) {
   166  			t.Errorf("checkPtr was not eliminated")
   167  		}
   168  	}
   169  }
   170  
   171  // TestNilcheckAddPtr verifies that nilchecks of OpAddPtr constructed values are removed.
   172  func TestNilcheckAddPtr(t *testing.T) {
   173  	c := testConfig(t)
   174  	ptrType := c.config.Types.BytePtr
   175  	fun := c.Fun("entry",
   176  		Bloc("entry",
   177  			Valu("mem", OpInitMem, types.TypeMem, 0, nil),
   178  			Valu("sb", OpSB, c.config.Types.Uintptr, 0, nil),
   179  			Goto("checkPtr")),
   180  		Bloc("checkPtr",
   181  			Valu("off", OpConst64, c.config.Types.Int64, 20, nil),
   182  			Valu("ptr1", OpAddPtr, ptrType, 0, nil, "sb", "off"),
   183  			Valu("bool1", OpIsNonNil, c.config.Types.Bool, 0, nil, "ptr1"),
   184  			If("bool1", "extra", "exit")),
   185  		Bloc("extra",
   186  			Goto("exit")),
   187  		Bloc("exit",
   188  			Exit("mem")))
   189  
   190  	CheckFunc(fun.f)
   191  	nilcheckelim(fun.f)
   192  
   193  	// clean up the removed nil check
   194  	fuse(fun.f, fuseTypePlain)
   195  	deadcode(fun.f)
   196  
   197  	CheckFunc(fun.f)
   198  	for _, b := range fun.f.Blocks {
   199  		if b == fun.blocks["checkPtr"] && isNilCheck(b) {
   200  			t.Errorf("checkPtr was not eliminated")
   201  		}
   202  	}
   203  }
   204  
   205  // TestNilcheckPhi tests that nil checks of phis, for which all values are known to be
   206  // non-nil are removed.
   207  func TestNilcheckPhi(t *testing.T) {
   208  	c := testConfig(t)
   209  	ptrType := c.config.Types.BytePtr
   210  	fun := c.Fun("entry",
   211  		Bloc("entry",
   212  			Valu("mem", OpInitMem, types.TypeMem, 0, nil),
   213  			Valu("sb", OpSB, c.config.Types.Uintptr, 0, nil),
   214  			Valu("sp", OpSP, c.config.Types.Uintptr, 0, nil),
   215  			Valu("baddr", OpLocalAddr, c.config.Types.Bool, 0, StringToAux("b"), "sp", "mem"),
   216  			Valu("bool1", OpLoad, c.config.Types.Bool, 0, nil, "baddr", "mem"),
   217  			If("bool1", "b1", "b2")),
   218  		Bloc("b1",
   219  			Valu("ptr1", OpAddr, ptrType, 0, nil, "sb"),
   220  			Goto("checkPtr")),
   221  		Bloc("b2",
   222  			Valu("ptr2", OpAddr, ptrType, 0, nil, "sb"),
   223  			Goto("checkPtr")),
   224  		// both ptr1 and ptr2 are guaranteed non-nil here
   225  		Bloc("checkPtr",
   226  			Valu("phi", OpPhi, ptrType, 0, nil, "ptr1", "ptr2"),
   227  			Valu("bool2", OpIsNonNil, c.config.Types.Bool, 0, nil, "phi"),
   228  			If("bool2", "extra", "exit")),
   229  		Bloc("extra",
   230  			Goto("exit")),
   231  		Bloc("exit",
   232  			Exit("mem")))
   233  
   234  	CheckFunc(fun.f)
   235  	nilcheckelim(fun.f)
   236  
   237  	// clean up the removed nil check
   238  	fuse(fun.f, fuseTypePlain)
   239  	deadcode(fun.f)
   240  
   241  	CheckFunc(fun.f)
   242  	for _, b := range fun.f.Blocks {
   243  		if b == fun.blocks["checkPtr"] && isNilCheck(b) {
   244  			t.Errorf("checkPtr was not eliminated")
   245  		}
   246  	}
   247  }
   248  
   249  // TestNilcheckKeepRemove verifies that duplicate checks of the same pointer
   250  // are removed, but checks of different pointers are not.
   251  func TestNilcheckKeepRemove(t *testing.T) {
   252  	c := testConfig(t)
   253  	ptrType := c.config.Types.BytePtr
   254  	fun := c.Fun("entry",
   255  		Bloc("entry",
   256  			Valu("mem", OpInitMem, types.TypeMem, 0, nil),
   257  			Valu("sb", OpSB, c.config.Types.Uintptr, 0, nil),
   258  			Goto("checkPtr")),
   259  		Bloc("checkPtr",
   260  			Valu("ptr1", OpLoad, ptrType, 0, nil, "sb", "mem"),
   261  			Valu("bool1", OpIsNonNil, c.config.Types.Bool, 0, nil, "ptr1"),
   262  			If("bool1", "differentCheck", "exit")),
   263  		Bloc("differentCheck",
   264  			Valu("ptr2", OpLoad, ptrType, 0, nil, "sb", "mem"),
   265  			Valu("bool2", OpIsNonNil, c.config.Types.Bool, 0, nil, "ptr2"),
   266  			If("bool2", "secondCheck", "exit")),
   267  		Bloc("secondCheck",
   268  			Valu("bool3", OpIsNonNil, c.config.Types.Bool, 0, nil, "ptr1"),
   269  			If("bool3", "extra", "exit")),
   270  		Bloc("extra",
   271  			Goto("exit")),
   272  		Bloc("exit",
   273  			Exit("mem")))
   274  
   275  	CheckFunc(fun.f)
   276  	nilcheckelim(fun.f)
   277  
   278  	// clean up the removed nil check
   279  	fuse(fun.f, fuseTypePlain)
   280  	deadcode(fun.f)
   281  
   282  	CheckFunc(fun.f)
   283  	foundDifferentCheck := false
   284  	for _, b := range fun.f.Blocks {
   285  		if b == fun.blocks["secondCheck"] && isNilCheck(b) {
   286  			t.Errorf("secondCheck was not eliminated")
   287  		}
   288  		if b == fun.blocks["differentCheck"] && isNilCheck(b) {
   289  			foundDifferentCheck = true
   290  		}
   291  	}
   292  	if !foundDifferentCheck {
   293  		t.Errorf("removed differentCheck, but shouldn't have")
   294  	}
   295  }
   296  
   297  // TestNilcheckInFalseBranch tests that nil checks in the false branch of a nilcheck
   298  // block are *not* removed.
   299  func TestNilcheckInFalseBranch(t *testing.T) {
   300  	c := testConfig(t)
   301  	ptrType := c.config.Types.BytePtr
   302  	fun := c.Fun("entry",
   303  		Bloc("entry",
   304  			Valu("mem", OpInitMem, types.TypeMem, 0, nil),
   305  			Valu("sb", OpSB, c.config.Types.Uintptr, 0, nil),
   306  			Goto("checkPtr")),
   307  		Bloc("checkPtr",
   308  			Valu("ptr1", OpLoad, ptrType, 0, nil, "sb", "mem"),
   309  			Valu("bool1", OpIsNonNil, c.config.Types.Bool, 0, nil, "ptr1"),
   310  			If("bool1", "extra", "secondCheck")),
   311  		Bloc("secondCheck",
   312  			Valu("bool2", OpIsNonNil, c.config.Types.Bool, 0, nil, "ptr1"),
   313  			If("bool2", "extra", "thirdCheck")),
   314  		Bloc("thirdCheck",
   315  			Valu("bool3", OpIsNonNil, c.config.Types.Bool, 0, nil, "ptr1"),
   316  			If("bool3", "extra", "exit")),
   317  		Bloc("extra",
   318  			Goto("exit")),
   319  		Bloc("exit",
   320  			Exit("mem")))
   321  
   322  	CheckFunc(fun.f)
   323  	nilcheckelim(fun.f)
   324  
   325  	// clean up the removed nil check
   326  	fuse(fun.f, fuseTypePlain)
   327  	deadcode(fun.f)
   328  
   329  	CheckFunc(fun.f)
   330  	foundSecondCheck := false
   331  	foundThirdCheck := false
   332  	for _, b := range fun.f.Blocks {
   333  		if b == fun.blocks["secondCheck"] && isNilCheck(b) {
   334  			foundSecondCheck = true
   335  		}
   336  		if b == fun.blocks["thirdCheck"] && isNilCheck(b) {
   337  			foundThirdCheck = true
   338  		}
   339  	}
   340  	if !foundSecondCheck {
   341  		t.Errorf("removed secondCheck, but shouldn't have [false branch]")
   342  	}
   343  	if !foundThirdCheck {
   344  		t.Errorf("removed thirdCheck, but shouldn't have [false branch]")
   345  	}
   346  }
   347  
   348  // TestNilcheckUser verifies that a user nil check that dominates a generated nil check
   349  // wil remove the generated nil check.
   350  func TestNilcheckUser(t *testing.T) {
   351  	c := testConfig(t)
   352  	ptrType := c.config.Types.BytePtr
   353  	fun := c.Fun("entry",
   354  		Bloc("entry",
   355  			Valu("mem", OpInitMem, types.TypeMem, 0, nil),
   356  			Valu("sb", OpSB, c.config.Types.Uintptr, 0, nil),
   357  			Goto("checkPtr")),
   358  		Bloc("checkPtr",
   359  			Valu("ptr1", OpLoad, ptrType, 0, nil, "sb", "mem"),
   360  			Valu("nilptr", OpConstNil, ptrType, 0, nil),
   361  			Valu("bool1", OpNeqPtr, c.config.Types.Bool, 0, nil, "ptr1", "nilptr"),
   362  			If("bool1", "secondCheck", "exit")),
   363  		Bloc("secondCheck",
   364  			Valu("bool2", OpIsNonNil, c.config.Types.Bool, 0, nil, "ptr1"),
   365  			If("bool2", "extra", "exit")),
   366  		Bloc("extra",
   367  			Goto("exit")),
   368  		Bloc("exit",
   369  			Exit("mem")))
   370  
   371  	CheckFunc(fun.f)
   372  	// we need the opt here to rewrite the user nilcheck
   373  	opt(fun.f)
   374  	nilcheckelim(fun.f)
   375  
   376  	// clean up the removed nil check
   377  	fuse(fun.f, fuseTypePlain)
   378  	deadcode(fun.f)
   379  
   380  	CheckFunc(fun.f)
   381  	for _, b := range fun.f.Blocks {
   382  		if b == fun.blocks["secondCheck"] && isNilCheck(b) {
   383  			t.Errorf("secondCheck was not eliminated")
   384  		}
   385  	}
   386  }
   387  
   388  // TestNilcheckBug reproduces a bug in nilcheckelim found by compiling math/big
   389  func TestNilcheckBug(t *testing.T) {
   390  	c := testConfig(t)
   391  	ptrType := c.config.Types.BytePtr
   392  	fun := c.Fun("entry",
   393  		Bloc("entry",
   394  			Valu("mem", OpInitMem, types.TypeMem, 0, nil),
   395  			Valu("sb", OpSB, c.config.Types.Uintptr, 0, nil),
   396  			Goto("checkPtr")),
   397  		Bloc("checkPtr",
   398  			Valu("ptr1", OpLoad, ptrType, 0, nil, "sb", "mem"),
   399  			Valu("nilptr", OpConstNil, ptrType, 0, nil),
   400  			Valu("bool1", OpNeqPtr, c.config.Types.Bool, 0, nil, "ptr1", "nilptr"),
   401  			If("bool1", "secondCheck", "couldBeNil")),
   402  		Bloc("couldBeNil",
   403  			Goto("secondCheck")),
   404  		Bloc("secondCheck",
   405  			Valu("bool2", OpIsNonNil, c.config.Types.Bool, 0, nil, "ptr1"),
   406  			If("bool2", "extra", "exit")),
   407  		Bloc("extra",
   408  			// prevent fuse from eliminating this block
   409  			Valu("store", OpStore, types.TypeMem, 0, ptrType, "ptr1", "nilptr", "mem"),
   410  			Goto("exit")),
   411  		Bloc("exit",
   412  			Valu("phi", OpPhi, types.TypeMem, 0, nil, "mem", "store"),
   413  			Exit("phi")))
   414  
   415  	CheckFunc(fun.f)
   416  	// we need the opt here to rewrite the user nilcheck
   417  	opt(fun.f)
   418  	nilcheckelim(fun.f)
   419  
   420  	// clean up the removed nil check
   421  	fuse(fun.f, fuseTypePlain)
   422  	deadcode(fun.f)
   423  
   424  	CheckFunc(fun.f)
   425  	foundSecondCheck := false
   426  	for _, b := range fun.f.Blocks {
   427  		if b == fun.blocks["secondCheck"] && isNilCheck(b) {
   428  			foundSecondCheck = true
   429  		}
   430  	}
   431  	if !foundSecondCheck {
   432  		t.Errorf("secondCheck was eliminated, but shouldn't have")
   433  	}
   434  }
   435  

View as plain text