fuse_test.go

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