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