branchelim_test.go

     1  // Copyright 2017 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  	"testing"
     9  
    10  	"cmd/compile/internal/ssa/block"
    11  	"cmd/compile/internal/ssa/ssaop"
    12  	"cmd/compile/internal/types"
    13  )
    14  
    15  // Test that a trivial 'if' is eliminated
    16  func TestBranchElimIf(t *testing.T) {
    17  	var testData = []struct {
    18  		arch    string
    19  		intType string
    20  		ok      bool
    21  	}{
    22  		{"arm64", "int32", true},
    23  		{"amd64", "int32", true},
    24  		{"amd64", "int8", false},
    25  	}
    26  
    27  	for _, data := range testData {
    28  		t.Run(data.arch+"/"+data.intType, func(t *testing.T) {
    29  			c := testConfigArch(t, data.arch)
    30  			boolType := c.config.Types.Bool
    31  			var intType *types.Type
    32  			switch data.intType {
    33  			case "int32":
    34  				intType = c.config.Types.Int32
    35  			case "int8":
    36  				intType = c.config.Types.Int8
    37  			default:
    38  				t.Fatal("invalid integer type:", data.intType)
    39  			}
    40  			fun := c.Fun("entry",
    41  				Bloc("entry",
    42  					Valu("start", ssaop.OpInitMem, types.TypeMem, 0, nil),
    43  					Valu("sb", ssaop.OpSB, c.config.Types.Uintptr, 0, nil),
    44  					Valu("const1", ssaop.OpConst32, intType, 1, nil),
    45  					Valu("const2", ssaop.OpConst32, intType, 2, nil),
    46  					Valu("addr", ssaop.OpAddr, boolType.PtrTo(), 0, nil, "sb"),
    47  					Valu("cond", ssaop.OpLoad, boolType, 0, nil, "addr", "start"),
    48  					If("cond", "b2", "b3")),
    49  				Bloc("b2",
    50  					Goto("b3")),
    51  				Bloc("b3",
    52  					Valu("phi", ssaop.OpPhi, intType, 0, nil, "const1", "const2"),
    53  					Valu("retstore", ssaop.OpStore, types.TypeMem, 0, nil, "phi", "sb", "start"),
    54  					Exit("retstore")))
    55  
    56  			CheckFunc(fun.f)
    57  			branchelim(fun.f)
    58  			CheckFunc(fun.f)
    59  			Deadcode(fun.f)
    60  			CheckFunc(fun.f)
    61  
    62  			if data.ok {
    63  
    64  				if len(fun.f.Blocks) != 1 {
    65  					t.Fatalf("expected 1 block after branchelim and deadcode; found %d", len(fun.f.Blocks))
    66  				}
    67  				if fun.values["phi"].Op != ssaop.OpCondSelect {
    68  					t.Fatalf("expected phi op to be CondSelect; found op %s", fun.values["phi"].Op)
    69  				}
    70  				if fun.values["phi"].Args[2] != fun.values["cond"] {
    71  					t.Errorf("expected CondSelect condition to be %s; found %s", fun.values["cond"], fun.values["phi"].Args[2])
    72  				}
    73  				if fun.blocks["entry"].Kind != block.BlockExit {
    74  					t.Errorf("expected entry to be BlockExit; found kind %s", fun.blocks["entry"].Kind.String())
    75  				}
    76  			} else {
    77  				if len(fun.f.Blocks) != 3 {
    78  					t.Fatalf("expected 3 block after branchelim and deadcode; found %d", len(fun.f.Blocks))
    79  				}
    80  			}
    81  		})
    82  	}
    83  }
    84  
    85  // Test that a trivial if/else is eliminated
    86  func TestBranchElimIfElse(t *testing.T) {
    87  	for _, arch := range []string{"arm64", "amd64"} {
    88  		t.Run(arch, func(t *testing.T) {
    89  			c := testConfigArch(t, arch)
    90  			boolType := c.config.Types.Bool
    91  			intType := c.config.Types.Int32
    92  			fun := c.Fun("entry",
    93  				Bloc("entry",
    94  					Valu("start", ssaop.OpInitMem, types.TypeMem, 0, nil),
    95  					Valu("sb", ssaop.OpSB, c.config.Types.Uintptr, 0, nil),
    96  					Valu("const1", ssaop.OpConst32, intType, 1, nil),
    97  					Valu("const2", ssaop.OpConst32, intType, 2, nil),
    98  					Valu("addr", ssaop.OpAddr, boolType.PtrTo(), 0, nil, "sb"),
    99  					Valu("cond", ssaop.OpLoad, boolType, 0, nil, "addr", "start"),
   100  					If("cond", "b2", "b3")),
   101  				Bloc("b2",
   102  					Goto("b4")),
   103  				Bloc("b3",
   104  					Goto("b4")),
   105  				Bloc("b4",
   106  					Valu("phi", ssaop.OpPhi, intType, 0, nil, "const1", "const2"),
   107  					Valu("retstore", ssaop.OpStore, types.TypeMem, 0, nil, "phi", "sb", "start"),
   108  					Exit("retstore")))
   109  
   110  			CheckFunc(fun.f)
   111  			branchelim(fun.f)
   112  			CheckFunc(fun.f)
   113  			Deadcode(fun.f)
   114  			CheckFunc(fun.f)
   115  
   116  			if len(fun.f.Blocks) != 1 {
   117  				t.Fatalf("expected 1 block after branchelim; found %d", len(fun.f.Blocks))
   118  			}
   119  			if fun.values["phi"].Op != ssaop.OpCondSelect {
   120  				t.Fatalf("expected phi op to be CondSelect; found op %s", fun.values["phi"].Op)
   121  			}
   122  			if fun.values["phi"].Args[2] != fun.values["cond"] {
   123  				t.Errorf("expected CondSelect condition to be %s; found %s", fun.values["cond"], fun.values["phi"].Args[2])
   124  			}
   125  			if fun.blocks["entry"].Kind != block.BlockExit {
   126  				t.Errorf("expected entry to be BlockExit; found kind %s", fun.blocks["entry"].Kind.String())
   127  			}
   128  		})
   129  	}
   130  }
   131  
   132  // Test that an if/else CFG that loops back
   133  // into itself does *not* get eliminated.
   134  func TestNoBranchElimLoop(t *testing.T) {
   135  	for _, arch := range []string{"arm64", "amd64"} {
   136  		t.Run(arch, func(t *testing.T) {
   137  			c := testConfigArch(t, arch)
   138  			boolType := c.config.Types.Bool
   139  			intType := c.config.Types.Int32
   140  
   141  			// The control flow here is totally bogus,
   142  			// but a dead cycle seems like the only plausible
   143  			// way to arrive at a diamond CFG that is also a loop.
   144  			fun := c.Fun("entry",
   145  				Bloc("entry",
   146  					Valu("start", ssaop.OpInitMem, types.TypeMem, 0, nil),
   147  					Valu("sb", ssaop.OpSB, c.config.Types.Uintptr, 0, nil),
   148  					Valu("const2", ssaop.OpConst32, intType, 2, nil),
   149  					Valu("const3", ssaop.OpConst32, intType, 3, nil),
   150  					Goto("b5")),
   151  				Bloc("b2",
   152  					Valu("addr", ssaop.OpAddr, boolType.PtrTo(), 0, nil, "sb"),
   153  					Valu("cond", ssaop.OpLoad, boolType, 0, nil, "addr", "start"),
   154  					Valu("phi", ssaop.OpPhi, intType, 0, nil, "const2", "const3"),
   155  					If("cond", "b3", "b4")),
   156  				Bloc("b3",
   157  					Goto("b2")),
   158  				Bloc("b4",
   159  					Goto("b2")),
   160  				Bloc("b5",
   161  					Exit("start")))
   162  
   163  			CheckFunc(fun.f)
   164  			branchelim(fun.f)
   165  			CheckFunc(fun.f)
   166  
   167  			if len(fun.f.Blocks) != 5 {
   168  				t.Errorf("expected 5 block after branchelim; found %d", len(fun.f.Blocks))
   169  			}
   170  			if fun.values["phi"].Op != ssaop.OpPhi {
   171  				t.Errorf("expected phi op to be CondSelect; found op %s", fun.values["phi"].Op)
   172  			}
   173  		})
   174  	}
   175  }
   176
View as plain text