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