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