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