fuse_test.go

     1  // Copyright 2016 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  	"fmt"
     9  	"strconv"
    10  	"testing"
    11  
    12  	"cmd/compile/internal/ssa/block"
    13  	"cmd/compile/internal/ssa/ssaop"
    14  	"cmd/compile/internal/types"
    15  )
    16  
    17  func TestFuseEliminatesOneBranch(t *testing.T) {
    18  	c := testConfig(t)
    19  	ptrType := c.config.Types.BytePtr
    20  	fun := c.Fun("entry",
    21  		Bloc("entry",
    22  			Valu("mem", ssaop.OpInitMem, types.TypeMem, 0, nil),
    23  			Valu("sb", ssaop.OpSB, c.config.Types.Uintptr, 0, nil),
    24  			Goto("checkPtr")),
    25  		Bloc("checkPtr",
    26  			Valu("ptr1", ssaop.OpLoad, ptrType, 0, nil, "sb", "mem"),
    27  			Valu("nilptr", ssaop.OpConstNil, ptrType, 0, nil),
    28  			Valu("bool1", ssaop.OpNeqPtr, c.config.Types.Bool, 0, nil, "ptr1", "nilptr"),
    29  			If("bool1", "then", "exit")),
    30  		Bloc("then",
    31  			Goto("exit")),
    32  		Bloc("exit",
    33  			Exit("mem")))
    34  
    35  	CheckFunc(fun.f)
    36  	fuseLate(fun.f)
    37  
    38  	for _, b := range fun.f.Blocks {
    39  		if b == fun.blocks["then"] && b.Kind != block.BlockInvalid {
    40  			t.Errorf("then was not eliminated, but should have")
    41  		}
    42  	}
    43  }
    44  
    45  func TestFuseEliminatesBothBranches(t *testing.T) {
    46  	c := testConfig(t)
    47  	ptrType := c.config.Types.BytePtr
    48  	fun := c.Fun("entry",
    49  		Bloc("entry",
    50  			Valu("mem", ssaop.OpInitMem, types.TypeMem, 0, nil),
    51  			Valu("sb", ssaop.OpSB, c.config.Types.Uintptr, 0, nil),
    52  			Goto("checkPtr")),
    53  		Bloc("checkPtr",
    54  			Valu("ptr1", ssaop.OpLoad, ptrType, 0, nil, "sb", "mem"),
    55  			Valu("nilptr", ssaop.OpConstNil, ptrType, 0, nil),
    56  			Valu("bool1", ssaop.OpNeqPtr, c.config.Types.Bool, 0, nil, "ptr1", "nilptr"),
    57  			If("bool1", "then", "else")),
    58  		Bloc("then",
    59  			Goto("exit")),
    60  		Bloc("else",
    61  			Goto("exit")),
    62  		Bloc("exit",
    63  			Exit("mem")))
    64  
    65  	CheckFunc(fun.f)
    66  	fuseLate(fun.f)
    67  
    68  	for _, b := range fun.f.Blocks {
    69  		if b == fun.blocks["then"] && b.Kind != block.BlockInvalid {
    70  			t.Errorf("then was not eliminated, but should have")
    71  		}
    72  		if b == fun.blocks["else"] && b.Kind != block.BlockInvalid {
    73  			t.Errorf("else was not eliminated, but should have")
    74  		}
    75  	}
    76  }
    77  
    78  func TestFuseHandlesPhis(t *testing.T) {
    79  	c := testConfig(t)
    80  	ptrType := c.config.Types.BytePtr
    81  	fun := c.Fun("entry",
    82  		Bloc("entry",
    83  			Valu("mem", ssaop.OpInitMem, types.TypeMem, 0, nil),
    84  			Valu("sb", ssaop.OpSB, c.config.Types.Uintptr, 0, nil),
    85  			Goto("checkPtr")),
    86  		Bloc("checkPtr",
    87  			Valu("ptr1", ssaop.OpLoad, ptrType, 0, nil, "sb", "mem"),
    88  			Valu("nilptr", ssaop.OpConstNil, ptrType, 0, nil),
    89  			Valu("bool1", ssaop.OpNeqPtr, c.config.Types.Bool, 0, nil, "ptr1", "nilptr"),
    90  			If("bool1", "then", "else")),
    91  		Bloc("then",
    92  			Goto("exit")),
    93  		Bloc("else",
    94  			Goto("exit")),
    95  		Bloc("exit",
    96  			Valu("phi", ssaop.OpPhi, ptrType, 0, nil, "ptr1", "ptr1"),
    97  			Exit("mem")))
    98  
    99  	CheckFunc(fun.f)
   100  	fuseLate(fun.f)
   101  
   102  	for _, b := range fun.f.Blocks {
   103  		if b == fun.blocks["then"] && b.Kind != block.BlockInvalid {
   104  			t.Errorf("then was not eliminated, but should have")
   105  		}
   106  		if b == fun.blocks["else"] && b.Kind != block.BlockInvalid {
   107  			t.Errorf("else was not eliminated, but should have")
   108  		}
   109  	}
   110  }
   111  
   112  func TestFuseEliminatesEmptyBlocks(t *testing.T) {
   113  	c := testConfig(t)
   114  	// Case 1, plain type empty blocks z0 ~ z3 will be eliminated.
   115  	//     entry
   116  	//       |
   117  	//      z0
   118  	//       |
   119  	//      z1
   120  	//       |
   121  	//      z2
   122  	//       |
   123  	//      z3
   124  	//       |
   125  	//     exit
   126  	fun := c.Fun("entry",
   127  		Bloc("entry",
   128  			Valu("mem", ssaop.OpInitMem, types.TypeMem, 0, nil),
   129  			Valu("sb", ssaop.OpSB, c.config.Types.Uintptr, 0, nil),
   130  			Goto("z0")),
   131  		Bloc("z1",
   132  			Goto("z2")),
   133  		Bloc("z3",
   134  			Goto("exit")),
   135  		Bloc("z2",
   136  			Goto("z3")),
   137  		Bloc("z0",
   138  			Goto("z1")),
   139  		Bloc("exit",
   140  			Exit("mem"),
   141  		))
   142  
   143  	CheckFunc(fun.f)
   144  	fuseLate(fun.f)
   145  
   146  	for k, b := range fun.blocks {
   147  		if k[:1] == "z" && b.Kind != block.BlockInvalid {
   148  			t.Errorf("case1 %s was not eliminated, but should have", k)
   149  		}
   150  	}
   151  
   152  	// Case 2, empty blocks with If branch, z0 and z1 will be eliminated.
   153  	//     entry
   154  	//     /  \
   155  	//    z0  z1
   156  	//     \  /
   157  	//     exit
   158  	fun = c.Fun("entry",
   159  		Bloc("entry",
   160  			Valu("mem", ssaop.OpInitMem, types.TypeMem, 0, nil),
   161  			Valu("c", ssaop.OpArg, c.config.Types.Bool, 0, nil),
   162  			If("c", "z0", "z1")),
   163  		Bloc("z0",
   164  			Goto("exit")),
   165  		Bloc("z1",
   166  			Goto("exit")),
   167  		Bloc("exit",
   168  			Exit("mem"),
   169  		))
   170  
   171  	CheckFunc(fun.f)
   172  	fuseLate(fun.f)
   173  
   174  	for k, b := range fun.blocks {
   175  		if k[:1] == "z" && b.Kind != block.BlockInvalid {
   176  			t.Errorf("case2 %s was not eliminated, but should have", k)
   177  		}
   178  	}
   179  
   180  	// Case 3, empty blocks with multiple predecessors, z0 and z1 will be eliminated.
   181  	//     entry
   182  	//      |  \
   183  	//      |  b0
   184  	//      | /  \
   185  	//      z0   z1
   186  	//       \   /
   187  	//       exit
   188  	fun = c.Fun("entry",
   189  		Bloc("entry",
   190  			Valu("mem", ssaop.OpInitMem, types.TypeMem, 0, nil),
   191  			Valu("c1", ssaop.OpArg, c.config.Types.Bool, 0, nil),
   192  			If("c1", "b0", "z0")),
   193  		Bloc("b0",
   194  			Valu("c2", ssaop.OpArg, c.config.Types.Bool, 0, nil),
   195  			If("c2", "z1", "z0")),
   196  		Bloc("z0",
   197  			Goto("exit")),
   198  		Bloc("z1",
   199  			Goto("exit")),
   200  		Bloc("exit",
   201  			Exit("mem"),
   202  		))
   203  
   204  	CheckFunc(fun.f)
   205  	fuseLate(fun.f)
   206  
   207  	for k, b := range fun.blocks {
   208  		if k[:1] == "z" && b.Kind != block.BlockInvalid {
   209  			t.Errorf("case3 %s was not eliminated, but should have", k)
   210  		}
   211  	}
   212  }
   213  
   214  func TestFuseSideEffects(t *testing.T) {
   215  	c := testConfig(t)
   216  	// Case1, test that we don't fuse branches that have side effects but
   217  	// have no use (e.g. followed by infinite loop).
   218  	// See issue #36005.
   219  	fun := c.Fun("entry",
   220  		Bloc("entry",
   221  			Valu("mem", ssaop.OpInitMem, types.TypeMem, 0, nil),
   222  			Valu("b", ssaop.OpArg, c.config.Types.Bool, 0, nil),
   223  			If("b", "then", "else")),
   224  		Bloc("then",
   225  			Valu("call1", ssaop.OpStaticCall, types.TypeMem, 0, AuxCallLSym("_"), "mem"),
   226  			Goto("empty")),
   227  		Bloc("else",
   228  			Valu("call2", ssaop.OpStaticCall, types.TypeMem, 0, AuxCallLSym("_"), "mem"),
   229  			Goto("empty")),
   230  		Bloc("empty",
   231  			Goto("loop")),
   232  		Bloc("loop",
   233  			Goto("loop")))
   234  
   235  	CheckFunc(fun.f)
   236  	fuseLate(fun.f)
   237  
   238  	for _, b := range fun.f.Blocks {
   239  		if b == fun.blocks["then"] && b.Kind == block.BlockInvalid {
   240  			t.Errorf("then is eliminated, but should not")
   241  		}
   242  		if b == fun.blocks["else"] && b.Kind == block.BlockInvalid {
   243  			t.Errorf("else is eliminated, but should not")
   244  		}
   245  	}
   246  
   247  	// Case2, z0 contains a value that has side effect, z0 shouldn't be eliminated.
   248  	//     entry
   249  	//      | \
   250  	//      |  z0
   251  	//      | /
   252  	//     exit
   253  	fun = c.Fun("entry",
   254  		Bloc("entry",
   255  			Valu("mem", ssaop.OpInitMem, types.TypeMem, 0, nil),
   256  			Valu("c1", ssaop.OpArg, c.config.Types.Bool, 0, nil),
   257  			Valu("p", ssaop.OpArg, c.config.Types.IntPtr, 0, nil),
   258  			If("c1", "z0", "exit")),
   259  		Bloc("z0",
   260  			Valu("nilcheck", ssaop.OpNilCheck, c.config.Types.IntPtr, 0, nil, "p", "mem"),
   261  			Goto("exit")),
   262  		Bloc("exit",
   263  			Exit("mem"),
   264  		))
   265  	CheckFunc(fun.f)
   266  	fuseLate(fun.f)
   267  	z0, ok := fun.blocks["z0"]
   268  	if !ok || z0.Kind == block.BlockInvalid {
   269  		t.Errorf("case2 z0 is eliminated, but should not")
   270  	}
   271  }
   272  
   273  func TestFuseHandlesDifferentiatedPhi(t *testing.T) {
   274  	c := testConfig(t)
   275  	fun := c.Fun("entry",
   276  		Bloc("entry",
   277  			Valu("mem", ssaop.OpInitMem, types.TypeMem, 0, nil),
   278  			Valu("a1", ssaop.OpArg, c.config.Types.UInt64, 0, nil),
   279  			Valu("sb", ssaop.OpSB, c.config.Types.Uintptr, 0, nil),
   280  			Valu("constTrue", ssaop.OpConstBool, c.config.Types.Bool, 1, nil),
   281  			Valu("lower", ssaop.OpConst64, c.config.Types.UInt64, 16, nil),
   282  			Valu("upper", ssaop.OpConst64, c.config.Types.UInt64, 512, nil),
   283  			Goto("checkUpper")),
   284  		Bloc("checkUpper",
   285  			Valu("bool1", ssaop.OpLeq64U, c.config.Types.Bool, 0, nil, "a1", "upper"),
   286  			If("bool1", "checkLower", "exit")),
   287  		Bloc("checkLower",
   288  			Valu("bool2", ssaop.OpLeq64U, c.config.Types.Bool, 0, nil, "lower", "a1"),
   289  			If("bool2", "empty", "exit")),
   290  		Bloc("empty",
   291  			Goto("exit")),
   292  		Bloc("exit",
   293  			Valu("phi", ssaop.OpPhi, c.config.Types.Bool, 0, nil, "bool1", "constTrue", "constTrue"),
   294  			Exit("mem")))
   295  
   296  	CheckFunc(fun.f)
   297  	fuse(fun.f, fuseTypeIntInRange)
   298  	phi := fun.values["phi"]
   299  	cTrue := fun.values["constTrue"]
   300  	if phi.Op == ssaop.OpCopy && phi.Args[0] == cTrue {
   301  		t.Errorf("phi mangled into always true")
   302  	}
   303  }
   304  
   305  func BenchmarkFuse(b *testing.B) {
   306  	for _, n := range [...]int{1, 10, 100, 1000, 10000} {
   307  		b.Run(strconv.Itoa(n), func(b *testing.B) {
   308  			c := testConfig(b)
   309  
   310  			blocks := make([]bloc, 0, 2*n+3)
   311  			blocks = append(blocks,
   312  				Bloc("entry",
   313  					Valu("mem", ssaop.OpInitMem, types.TypeMem, 0, nil),
   314  					Valu("cond", ssaop.OpArg, c.config.Types.Bool, 0, nil),
   315  					Valu("x", ssaop.OpArg, c.config.Types.Int64, 0, nil),
   316  					Goto("exit")))
   317  
   318  			phiArgs := make([]string, 0, 2*n)
   319  			for i := 0; i < n; i++ {
   320  				cname := fmt.Sprintf("c%d", i)
   321  				blocks = append(blocks,
   322  					Bloc(fmt.Sprintf("b%d", i), If("cond", cname, "merge")),
   323  					Bloc(cname, Goto("merge")))
   324  				phiArgs = append(phiArgs, "x", "x")
   325  			}
   326  			blocks = append(blocks,
   327  				Bloc("merge",
   328  					Valu("phi", ssaop.OpPhi, types.TypeMem, 0, nil, phiArgs...),
   329  					Goto("exit")),
   330  				Bloc("exit",
   331  					Exit("mem")))
   332  
   333  			b.ResetTimer()
   334  			for i := 0; i < b.N; i++ {
   335  				fun := c.Fun("entry", blocks...)
   336  				fuseLate(fun.f)
   337  			}
   338  		})
   339  	}
   340  }
   341
View as plain text