Source file src/cmd/compile/internal/ssa/deadstore_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  	"cmd/internal/src"
    10  	"fmt"
    11  	"sort"
    12  	"testing"
    13  )
    14  
    15  func TestDeadStore(t *testing.T) {
    16  	c := testConfig(t)
    17  	ptrType := c.config.Types.BytePtr
    18  	t.Logf("PTRTYPE %v", ptrType)
    19  	fun := c.Fun("entry",
    20  		Bloc("entry",
    21  			Valu("start", OpInitMem, types.TypeMem, 0, nil),
    22  			Valu("sb", OpSB, c.config.Types.Uintptr, 0, nil),
    23  			Valu("v", OpConstBool, c.config.Types.Bool, 1, nil),
    24  			Valu("addr1", OpAddr, ptrType, 0, nil, "sb"),
    25  			Valu("addr2", OpAddr, ptrType, 0, nil, "sb"),
    26  			Valu("addr3", OpAddr, ptrType, 0, nil, "sb"),
    27  			Valu("zero1", OpZero, types.TypeMem, 1, c.config.Types.Bool, "addr3", "start"),
    28  			Valu("store1", OpStore, types.TypeMem, 0, c.config.Types.Bool, "addr1", "v", "zero1"),
    29  			Valu("store2", OpStore, types.TypeMem, 0, c.config.Types.Bool, "addr2", "v", "store1"),
    30  			Valu("store3", OpStore, types.TypeMem, 0, c.config.Types.Bool, "addr1", "v", "store2"),
    31  			Valu("store4", OpStore, types.TypeMem, 0, c.config.Types.Bool, "addr3", "v", "store3"),
    32  			Goto("exit")),
    33  		Bloc("exit",
    34  			Exit("store3")))
    35  
    36  	CheckFunc(fun.f)
    37  	dse(fun.f)
    38  	CheckFunc(fun.f)
    39  
    40  	v1 := fun.values["store1"]
    41  	if v1.Op != OpCopy {
    42  		t.Errorf("dead store not removed")
    43  	}
    44  
    45  	v2 := fun.values["zero1"]
    46  	if v2.Op != OpCopy {
    47  		t.Errorf("dead store (zero) not removed")
    48  	}
    49  }
    50  
    51  func TestDeadStorePhi(t *testing.T) {
    52  	// make sure we don't get into an infinite loop with phi values.
    53  	c := testConfig(t)
    54  	ptrType := c.config.Types.BytePtr
    55  	fun := c.Fun("entry",
    56  		Bloc("entry",
    57  			Valu("start", OpInitMem, types.TypeMem, 0, nil),
    58  			Valu("sb", OpSB, c.config.Types.Uintptr, 0, nil),
    59  			Valu("v", OpConstBool, c.config.Types.Bool, 1, nil),
    60  			Valu("addr", OpAddr, ptrType, 0, nil, "sb"),
    61  			Goto("loop")),
    62  		Bloc("loop",
    63  			Valu("phi", OpPhi, types.TypeMem, 0, nil, "start", "store"),
    64  			Valu("store", OpStore, types.TypeMem, 0, c.config.Types.Bool, "addr", "v", "phi"),
    65  			If("v", "loop", "exit")),
    66  		Bloc("exit",
    67  			Exit("store")))
    68  
    69  	CheckFunc(fun.f)
    70  	dse(fun.f)
    71  	CheckFunc(fun.f)
    72  }
    73  
    74  func TestDeadStoreTypes(t *testing.T) {
    75  	// Make sure a narrow store can't shadow a wider one. We test an even
    76  	// stronger restriction, that one store can't shadow another unless the
    77  	// types of the address fields are identical (where identicalness is
    78  	// decided by the CSE pass).
    79  	c := testConfig(t)
    80  	t1 := c.config.Types.UInt64.PtrTo()
    81  	t2 := c.config.Types.UInt32.PtrTo()
    82  	fun := c.Fun("entry",
    83  		Bloc("entry",
    84  			Valu("start", OpInitMem, types.TypeMem, 0, nil),
    85  			Valu("sb", OpSB, c.config.Types.Uintptr, 0, nil),
    86  			Valu("v", OpConstBool, c.config.Types.Bool, 1, nil),
    87  			Valu("addr1", OpAddr, t1, 0, nil, "sb"),
    88  			Valu("addr2", OpAddr, t2, 0, nil, "sb"),
    89  			Valu("store1", OpStore, types.TypeMem, 0, c.config.Types.Bool, "addr1", "v", "start"),
    90  			Valu("store2", OpStore, types.TypeMem, 0, c.config.Types.Bool, "addr2", "v", "store1"),
    91  			Goto("exit")),
    92  		Bloc("exit",
    93  			Exit("store2")))
    94  
    95  	CheckFunc(fun.f)
    96  	cse(fun.f)
    97  	dse(fun.f)
    98  	CheckFunc(fun.f)
    99  
   100  	v := fun.values["store1"]
   101  	if v.Op == OpCopy {
   102  		t.Errorf("store %s incorrectly removed", v)
   103  	}
   104  }
   105  
   106  func TestDeadStoreUnsafe(t *testing.T) {
   107  	// Make sure a narrow store can't shadow a wider one. The test above
   108  	// covers the case of two different types, but unsafe pointer casting
   109  	// can get to a point where the size is changed but type unchanged.
   110  	c := testConfig(t)
   111  	ptrType := c.config.Types.UInt64.PtrTo()
   112  	fun := c.Fun("entry",
   113  		Bloc("entry",
   114  			Valu("start", OpInitMem, types.TypeMem, 0, nil),
   115  			Valu("sb", OpSB, c.config.Types.Uintptr, 0, nil),
   116  			Valu("v", OpConstBool, c.config.Types.Bool, 1, nil),
   117  			Valu("addr1", OpAddr, ptrType, 0, nil, "sb"),
   118  			Valu("store1", OpStore, types.TypeMem, 0, c.config.Types.Int64, "addr1", "v", "start"), // store 8 bytes
   119  			Valu("store2", OpStore, types.TypeMem, 0, c.config.Types.Bool, "addr1", "v", "store1"), // store 1 byte
   120  			Goto("exit")),
   121  		Bloc("exit",
   122  			Exit("store2")))
   123  
   124  	CheckFunc(fun.f)
   125  	cse(fun.f)
   126  	dse(fun.f)
   127  	CheckFunc(fun.f)
   128  
   129  	v := fun.values["store1"]
   130  	if v.Op == OpCopy {
   131  		t.Errorf("store %s incorrectly removed", v)
   132  	}
   133  }
   134  
   135  func TestDeadStoreSmallStructInit(t *testing.T) {
   136  	c := testConfig(t)
   137  	ptrType := c.config.Types.BytePtr
   138  	typ := types.NewStruct([]*types.Field{
   139  		types.NewField(src.NoXPos, &types.Sym{Name: "A"}, c.config.Types.Int),
   140  		types.NewField(src.NoXPos, &types.Sym{Name: "B"}, c.config.Types.Int),
   141  	})
   142  	name := c.Temp(typ)
   143  	fun := c.Fun("entry",
   144  		Bloc("entry",
   145  			Valu("start", OpInitMem, types.TypeMem, 0, nil),
   146  			Valu("sp", OpSP, c.config.Types.Uintptr, 0, nil),
   147  			Valu("zero", OpConst64, c.config.Types.Int, 0, nil),
   148  			Valu("v6", OpLocalAddr, ptrType, 0, name, "sp", "start"),
   149  			Valu("v3", OpOffPtr, ptrType, 8, nil, "v6"),
   150  			Valu("v22", OpOffPtr, ptrType, 0, nil, "v6"),
   151  			Valu("zerostore1", OpStore, types.TypeMem, 0, c.config.Types.Int, "v22", "zero", "start"),
   152  			Valu("zerostore2", OpStore, types.TypeMem, 0, c.config.Types.Int, "v3", "zero", "zerostore1"),
   153  			Valu("v8", OpLocalAddr, ptrType, 0, name, "sp", "zerostore2"),
   154  			Valu("v23", OpOffPtr, ptrType, 8, nil, "v8"),
   155  			Valu("v25", OpOffPtr, ptrType, 0, nil, "v8"),
   156  			Valu("zerostore3", OpStore, types.TypeMem, 0, c.config.Types.Int, "v25", "zero", "zerostore2"),
   157  			Valu("zerostore4", OpStore, types.TypeMem, 0, c.config.Types.Int, "v23", "zero", "zerostore3"),
   158  			Goto("exit")),
   159  		Bloc("exit",
   160  			Exit("zerostore4")))
   161  
   162  	fun.f.Name = "smallstructinit"
   163  	CheckFunc(fun.f)
   164  	cse(fun.f)
   165  	dse(fun.f)
   166  	CheckFunc(fun.f)
   167  
   168  	v1 := fun.values["zerostore1"]
   169  	if v1.Op != OpCopy {
   170  		t.Errorf("dead store not removed")
   171  	}
   172  	v2 := fun.values["zerostore2"]
   173  	if v2.Op != OpCopy {
   174  		t.Errorf("dead store not removed")
   175  	}
   176  }
   177  
   178  func TestDeadStoreArrayGap(t *testing.T) {
   179  	c := testConfig(t)
   180  	ptr := c.config.Types.BytePtr
   181  	i64 := c.config.Types.Int64
   182  
   183  	typ := types.NewArray(i64, 5)
   184  	tmp := c.Temp(typ)
   185  
   186  	fun := c.Fun("entry",
   187  		Bloc("entry",
   188  			Valu("start", OpInitMem, types.TypeMem, 0, nil),
   189  			Valu("sp", OpSP, c.config.Types.Uintptr, 0, nil),
   190  
   191  			Valu("base", OpLocalAddr, ptr, 0, tmp, "sp", "start"),
   192  
   193  			Valu("p0", OpOffPtr, ptr, 0, nil, "base"),
   194  			Valu("p1", OpOffPtr, ptr, 8, nil, "base"),
   195  			Valu("p2", OpOffPtr, ptr, 16, nil, "base"),
   196  			Valu("p3", OpOffPtr, ptr, 24, nil, "base"),
   197  			Valu("p4", OpOffPtr, ptr, 32, nil, "base"),
   198  
   199  			Valu("one", OpConst64, i64, 1, nil),
   200  			Valu("seven", OpConst64, i64, 7, nil),
   201  			Valu("zero", OpConst64, i64, 0, nil),
   202  
   203  			Valu("mem0", OpZero, types.TypeMem, 40, typ, "base", "start"),
   204  
   205  			Valu("s0", OpStore, types.TypeMem, 0, i64, "p0", "one", "mem0"),
   206  			Valu("s1", OpStore, types.TypeMem, 0, i64, "p1", "seven", "s0"),
   207  			Valu("s2", OpStore, types.TypeMem, 0, i64, "p3", "one", "s1"),
   208  			Valu("s3", OpStore, types.TypeMem, 0, i64, "p4", "one", "s2"),
   209  			Valu("s4", OpStore, types.TypeMem, 0, i64, "p2", "zero", "s3"),
   210  
   211  			Goto("exit")),
   212  		Bloc("exit",
   213  			Exit("s4")))
   214  
   215  	CheckFunc(fun.f)
   216  	dse(fun.f)
   217  	CheckFunc(fun.f)
   218  
   219  	if op := fun.values["mem0"].Op; op != OpCopy {
   220  		t.Fatalf("dead Zero not removed: got %s, want OpCopy", op)
   221  	}
   222  }
   223  
   224  func TestShadowRanges(t *testing.T) {
   225  	t.Run("simple insert & contains", func(t *testing.T) {
   226  		var sr shadowRanges
   227  		sr.add(10, 20)
   228  
   229  		wantRanges(t, sr.ranges, [][2]uint16{{10, 20}})
   230  		if !sr.contains(12, 18) || !sr.contains(10, 20) {
   231  			t.Fatalf("contains failed after simple add")
   232  		}
   233  		if sr.contains(9, 11) || sr.contains(11, 21) {
   234  			t.Fatalf("contains erroneously true for non-contained range")
   235  		}
   236  	})
   237  
   238  	t.Run("merge overlapping", func(t *testing.T) {
   239  		var sr shadowRanges
   240  		sr.add(10, 20)
   241  		sr.add(15, 25)
   242  
   243  		wantRanges(t, sr.ranges, [][2]uint16{{10, 25}})
   244  		if !sr.contains(13, 24) {
   245  			t.Fatalf("contains should be true after merge")
   246  		}
   247  	})
   248  
   249  	t.Run("merge touching boundary", func(t *testing.T) {
   250  		var sr shadowRanges
   251  		sr.add(100, 150)
   252  		// touches at 150 - should coalesce
   253  		sr.add(150, 180)
   254  
   255  		wantRanges(t, sr.ranges, [][2]uint16{{100, 180}})
   256  	})
   257  
   258  	t.Run("union across several ranges", func(t *testing.T) {
   259  		var sr shadowRanges
   260  		sr.add(10, 20)
   261  		sr.add(30, 40)
   262  		// bridges second, not first
   263  		sr.add(25, 35)
   264  
   265  		wantRanges(t, sr.ranges, [][2]uint16{{10, 20}, {25, 40}})
   266  
   267  		// envelops everything
   268  		sr.add(5, 50)
   269  		wantRanges(t, sr.ranges, [][2]uint16{{5, 50}})
   270  	})
   271  
   272  	t.Run("disjoint intervals stay separate", func(t *testing.T) {
   273  		var sr shadowRanges
   274  		sr.add(10, 20)
   275  		sr.add(22, 30)
   276  
   277  		wantRanges(t, sr.ranges, [][2]uint16{{10, 20}, {22, 30}})
   278  		// spans both
   279  		if sr.contains(15, 25) {
   280  			t.Fatalf("contains across two disjoint ranges should be false")
   281  		}
   282  	})
   283  
   284  	t.Run("large uint16 offsets still work", func(t *testing.T) {
   285  		var sr shadowRanges
   286  		sr.add(40000, 45000)
   287  
   288  		if !sr.contains(42000, 43000) {
   289  			t.Fatalf("contains failed for large uint16 values")
   290  		}
   291  	})
   292  
   293  	t.Run("out-of-bounds inserts ignored", func(t *testing.T) {
   294  		var sr shadowRanges
   295  		sr.add(10, 20)
   296  		sr.add(-5, 5)
   297  		sr.add(70000, 70010)
   298  
   299  		wantRanges(t, sr.ranges, [][2]uint16{{10, 20}})
   300  	})
   301  }
   302  
   303  // canonicalise order for comparisons
   304  func sortRanges(r []shadowRange) {
   305  	sort.Slice(r, func(i, j int) bool { return r[i].lo < r[j].lo })
   306  }
   307  
   308  // compare actual slice with expected pairs
   309  func wantRanges(t *testing.T, got []shadowRange, want [][2]uint16) {
   310  	t.Helper()
   311  	sortRanges(got)
   312  
   313  	if len(got) != len(want) {
   314  		t.Fatalf("len(ranges)=%d, want %d (got=%v)", len(got), len(want), got)
   315  	}
   316  
   317  	for i, w := range want {
   318  		if got[i].lo != w[0] || got[i].hi != w[1] {
   319  			t.Fatalf("range %d = [%d,%d], want [%d,%d] (full=%v)",
   320  				i, got[i].lo, got[i].hi, w[0], w[1], got)
   321  		}
   322  	}
   323  }
   324  
   325  func BenchmarkDeadStore(b *testing.B) {
   326  	cfg := testConfig(b)
   327  	ptr := cfg.config.Types.BytePtr
   328  
   329  	f := cfg.Fun("entry",
   330  		Bloc("entry",
   331  			Valu("start", OpInitMem, types.TypeMem, 0, nil),
   332  			Valu("sb", OpSB, cfg.config.Types.Uintptr, 0, nil),
   333  			Valu("v", OpConstBool, cfg.config.Types.Bool, 1, nil),
   334  			Valu("a1", OpAddr, ptr, 0, nil, "sb"),
   335  			Valu("a2", OpAddr, ptr, 0, nil, "sb"),
   336  			Valu("a3", OpAddr, ptr, 0, nil, "sb"),
   337  			Valu("z1", OpZero, types.TypeMem, 1, cfg.config.Types.Bool, "a3", "start"),
   338  			Valu("s1", OpStore, types.TypeMem, 0, cfg.config.Types.Bool, "a1", "v", "z1"),
   339  			Valu("s2", OpStore, types.TypeMem, 0, cfg.config.Types.Bool, "a2", "v", "s1"),
   340  			Valu("s3", OpStore, types.TypeMem, 0, cfg.config.Types.Bool, "a1", "v", "s2"),
   341  			Valu("s4", OpStore, types.TypeMem, 0, cfg.config.Types.Bool, "a3", "v", "s3"),
   342  			Goto("exit")),
   343  		Bloc("exit",
   344  			Exit("s3")))
   345  
   346  	runBench(b, func() {
   347  		dse(f.f)
   348  	})
   349  }
   350  
   351  func BenchmarkDeadStorePhi(b *testing.B) {
   352  	cfg := testConfig(b)
   353  	ptr := cfg.config.Types.BytePtr
   354  
   355  	f := cfg.Fun("entry",
   356  		Bloc("entry",
   357  			Valu("start", OpInitMem, types.TypeMem, 0, nil),
   358  			Valu("sb", OpSB, cfg.config.Types.Uintptr, 0, nil),
   359  			Valu("v", OpConstBool, cfg.config.Types.Bool, 1, nil),
   360  			Valu("addr", OpAddr, ptr, 0, nil, "sb"),
   361  			Goto("loop")),
   362  		Bloc("loop",
   363  			Valu("phi", OpPhi, types.TypeMem, 0, nil, "start", "store"),
   364  			Valu("store", OpStore, types.TypeMem, 0, cfg.config.Types.Bool, "addr", "v", "phi"),
   365  			If("v", "loop", "exit")),
   366  		Bloc("exit",
   367  			Exit("store")))
   368  
   369  	runBench(b, func() {
   370  		dse(f.f)
   371  	})
   372  }
   373  
   374  func BenchmarkDeadStoreTypes(b *testing.B) {
   375  	cfg := testConfig(b)
   376  
   377  	t1 := cfg.config.Types.UInt64.PtrTo()
   378  	t2 := cfg.config.Types.UInt32.PtrTo()
   379  
   380  	f := cfg.Fun("entry",
   381  		Bloc("entry",
   382  			Valu("start", OpInitMem, types.TypeMem, 0, nil),
   383  			Valu("sb", OpSB, cfg.config.Types.Uintptr, 0, nil),
   384  			Valu("v", OpConstBool, cfg.config.Types.Bool, 1, nil),
   385  			Valu("a1", OpAddr, t1, 0, nil, "sb"),
   386  			Valu("a2", OpAddr, t2, 0, nil, "sb"),
   387  			Valu("s1", OpStore, types.TypeMem, 0, cfg.config.Types.Bool, "a1", "v", "start"),
   388  			Valu("s2", OpStore, types.TypeMem, 0, cfg.config.Types.Bool, "a2", "v", "s1"),
   389  			Goto("exit")),
   390  		Bloc("exit",
   391  			Exit("s2")))
   392  	cse(f.f)
   393  
   394  	runBench(b, func() {
   395  		dse(f.f)
   396  	})
   397  }
   398  
   399  func BenchmarkDeadStoreUnsafe(b *testing.B) {
   400  	cfg := testConfig(b)
   401  	ptr := cfg.config.Types.UInt64.PtrTo()
   402  	f := cfg.Fun("entry",
   403  		Bloc("entry",
   404  			Valu("start", OpInitMem, types.TypeMem, 0, nil),
   405  			Valu("sb", OpSB, cfg.config.Types.Uintptr, 0, nil),
   406  			Valu("v", OpConstBool, cfg.config.Types.Bool, 1, nil),
   407  			Valu("a1", OpAddr, ptr, 0, nil, "sb"),
   408  			Valu("s1", OpStore, types.TypeMem, 0, cfg.config.Types.Int64, "a1", "v", "start"),
   409  			Valu("s2", OpStore, types.TypeMem, 0, cfg.config.Types.Bool, "a1", "v", "s1"),
   410  			Goto("exit")),
   411  		Bloc("exit",
   412  			Exit("s2")))
   413  	cse(f.f)
   414  	runBench(b, func() {
   415  		dse(f.f)
   416  	})
   417  }
   418  
   419  func BenchmarkDeadStoreSmallStructInit(b *testing.B) {
   420  	cfg := testConfig(b)
   421  	ptr := cfg.config.Types.BytePtr
   422  
   423  	typ := types.NewStruct([]*types.Field{
   424  		types.NewField(src.NoXPos, &types.Sym{Name: "A"}, cfg.config.Types.Int),
   425  		types.NewField(src.NoXPos, &types.Sym{Name: "B"}, cfg.config.Types.Int),
   426  	})
   427  	tmp := cfg.Temp(typ)
   428  
   429  	f := cfg.Fun("entry",
   430  		Bloc("entry",
   431  			Valu("start", OpInitMem, types.TypeMem, 0, nil),
   432  			Valu("sp", OpSP, cfg.config.Types.Uintptr, 0, nil),
   433  			Valu("zero", OpConst64, cfg.config.Types.Int, 0, nil),
   434  
   435  			Valu("v6", OpLocalAddr, ptr, 0, tmp, "sp", "start"),
   436  			Valu("v3", OpOffPtr, ptr, 8, nil, "v6"),
   437  			Valu("v22", OpOffPtr, ptr, 0, nil, "v6"),
   438  			Valu("s1", OpStore, types.TypeMem, 0, cfg.config.Types.Int, "v22", "zero", "start"),
   439  			Valu("s2", OpStore, types.TypeMem, 0, cfg.config.Types.Int, "v3", "zero", "s1"),
   440  
   441  			Valu("v8", OpLocalAddr, ptr, 0, tmp, "sp", "s2"),
   442  			Valu("v23", OpOffPtr, ptr, 8, nil, "v8"),
   443  			Valu("v25", OpOffPtr, ptr, 0, nil, "v8"),
   444  			Valu("s3", OpStore, types.TypeMem, 0, cfg.config.Types.Int, "v25", "zero", "s2"),
   445  			Valu("s4", OpStore, types.TypeMem, 0, cfg.config.Types.Int, "v23", "zero", "s3"),
   446  			Goto("exit")),
   447  		Bloc("exit",
   448  			Exit("s4")))
   449  	cse(f.f)
   450  
   451  	runBench(b, func() {
   452  		dse(f.f)
   453  	})
   454  }
   455  
   456  func BenchmarkDeadStoreLargeBlock(b *testing.B) {
   457  	// create a very large block with many shadowed stores
   458  	const (
   459  		addrCount = 128
   460  		// first 7 are dead
   461  		storesPerAddr = 8
   462  	)
   463  	cfg := testConfig(b)
   464  	ptrType := cfg.config.Types.BytePtr
   465  	boolType := cfg.config.Types.Bool
   466  
   467  	items := []interface{}{
   468  		Valu("start", OpInitMem, types.TypeMem, 0, nil),
   469  		Valu("sb", OpSB, cfg.config.Types.Uintptr, 0, nil),
   470  		Valu("v", OpConstBool, boolType, 1, nil),
   471  	}
   472  
   473  	for i := 0; i < addrCount; i++ {
   474  		items = append(items,
   475  			Valu(fmt.Sprintf("addr%d", i), OpAddr, ptrType, 0, nil, "sb"),
   476  		)
   477  	}
   478  
   479  	prev := "start"
   480  	for round := 0; round < storesPerAddr; round++ {
   481  		for i := 0; i < addrCount; i++ {
   482  			store := fmt.Sprintf("s_%03d_%d", i, round)
   483  			addr := fmt.Sprintf("addr%d", i)
   484  			items = append(items,
   485  				Valu(store, OpStore, types.TypeMem, 0, boolType, addr, "v", prev),
   486  			)
   487  			prev = store
   488  		}
   489  	}
   490  
   491  	items = append(items, Goto("exit"))
   492  	entryBlk := Bloc("entry", items...)
   493  	exitBlk := Bloc("exit", Exit(prev))
   494  
   495  	f := cfg.Fun("stress", entryBlk, exitBlk)
   496  
   497  	runBench(b, func() {
   498  		dse(f.f)
   499  	})
   500  }
   501  
   502  func runBench(b *testing.B, build func()) {
   503  	b.ReportAllocs()
   504  	b.ResetTimer()
   505  	for i := 0; i < b.N; i++ {
   506  		build()
   507  	}
   508  }
   509  

View as plain text