schedule_test.go

     1  // Copyright 2015 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"
    11  	"cmd/compile/internal/ssa/ssaop"
    12  	"cmd/compile/internal/types"
    13  )
    14  
    15  func TestSchedule(t *testing.T) {
    16  	c := testConfig(t)
    17  	cases := []fun{
    18  		c.Fun("entry",
    19  			Bloc("entry",
    20  				Valu("mem0", ssaop.OpInitMem, types.TypeMem, 0, nil),
    21  				Valu("ptr", ssaop.OpConst64, c.config.Types.Int64, 0xABCD, nil),
    22  				Valu("v", ssaop.OpConst64, c.config.Types.Int64, 12, nil),
    23  				Valu("mem1", ssaop.OpStore, types.TypeMem, 0, c.config.Types.Int64, "ptr", "v", "mem0"),
    24  				Valu("mem2", ssaop.OpStore, types.TypeMem, 0, c.config.Types.Int64, "ptr", "v", "mem1"),
    25  				Valu("mem3", ssaop.OpStore, types.TypeMem, 0, c.config.Types.Int64, "ptr", "sum", "mem2"),
    26  				Valu("l1", ssaop.OpLoad, c.config.Types.Int64, 0, nil, "ptr", "mem1"),
    27  				Valu("l2", ssaop.OpLoad, c.config.Types.Int64, 0, nil, "ptr", "mem2"),
    28  				Valu("sum", ssaop.OpAdd64, c.config.Types.Int64, 0, nil, "l1", "l2"),
    29  				Goto("exit")),
    30  			Bloc("exit",
    31  				Exit("mem3"))),
    32  	}
    33  	for _, c := range cases {
    34  		schedule(c.f)
    35  		if !isSingleLiveMem(c.f) {
    36  			t.Error("single-live-mem restriction not enforced by schedule for func:")
    37  			ssa.PrintFunc(c.f)
    38  		}
    39  	}
    40  }
    41  
    42  func isSingleLiveMem(f *ssa.Func) bool {
    43  	for _, b := range f.Blocks {
    44  		var liveMem *ssa.Value
    45  		for _, v := range b.Values {
    46  			for _, w := range v.Args {
    47  				if w.Type.IsMemory() {
    48  					if liveMem == nil {
    49  						liveMem = w
    50  						continue
    51  					}
    52  					if w != liveMem {
    53  						return false
    54  					}
    55  				}
    56  			}
    57  			if v.Type.IsMemory() {
    58  				liveMem = v
    59  			}
    60  		}
    61  	}
    62  	return true
    63  }
    64  
    65  func TestStoreOrder(t *testing.T) {
    66  	// In the function below, v2 depends on v3 and v4, v4 depends on v3, and v3 depends on store v5.
    67  	// storeOrder did not handle this case correctly.
    68  	c := testConfig(t)
    69  	fun := c.Fun("entry",
    70  		Bloc("entry",
    71  			Valu("mem0", ssaop.OpInitMem, types.TypeMem, 0, nil),
    72  			Valu("a", ssaop.OpAdd64, c.config.Types.Int64, 0, nil, "b", "c"),                        // v2
    73  			Valu("b", ssaop.OpLoad, c.config.Types.Int64, 0, nil, "ptr", "mem1"),                    // v3
    74  			Valu("c", ssaop.OpNeg64, c.config.Types.Int64, 0, nil, "b"),                             // v4
    75  			Valu("mem1", ssaop.OpStore, types.TypeMem, 0, c.config.Types.Int64, "ptr", "v", "mem0"), // v5
    76  			Valu("mem2", ssaop.OpStore, types.TypeMem, 0, c.config.Types.Int64, "ptr", "a", "mem1"),
    77  			Valu("ptr", ssaop.OpConst64, c.config.Types.Int64, 0xABCD, nil),
    78  			Valu("v", ssaop.OpConst64, c.config.Types.Int64, 12, nil),
    79  			Goto("exit")),
    80  		Bloc("exit",
    81  			Exit("mem2")))
    82  
    83  	CheckFunc(fun.f)
    84  	order := storeOrder(fun.f.Blocks[0].Values, fun.f.NewSparseSet(fun.f.NumValues()), make([]int32, fun.f.NumValues()))
    85  
    86  	// check that v2, v3, v4 is sorted after v5
    87  	var ai, bi, ci, si int
    88  	for i, v := range order {
    89  		switch v.ID {
    90  		case 2:
    91  			ai = i
    92  		case 3:
    93  			bi = i
    94  		case 4:
    95  			ci = i
    96  		case 5:
    97  			si = i
    98  		}
    99  	}
   100  	if ai < si || bi < si || ci < si {
   101  		t.Logf("Func: %s", fun.f)
   102  		t.Errorf("store order is wrong: got %v, want v2 v3 v4 after v5", order)
   103  	}
   104  }
   105  
   106  func TestCarryChainOrder(t *testing.T) {
   107  	// In the function below, there are two carry chains that have no dependencies on each other,
   108  	// one is A1 -> A1carry -> A1Carryvalue, the other is A2 -> A2carry -> A2Carryvalue. If they
   109  	// are not scheduled properly, the carry will be clobbered, causing the carry to be regenerated.
   110  	c := testConfigARM64(t)
   111  	fun := c.Fun("entry",
   112  		Bloc("entry",
   113  			Valu("mem0", ssaop.OpInitMem, types.TypeMem, 0, nil),
   114  			Valu("x", ssaop.OpARM64MOVDconst, c.config.Types.UInt64, 5, nil),
   115  			Valu("y", ssaop.OpARM64MOVDconst, c.config.Types.UInt64, 6, nil),
   116  			Valu("z", ssaop.OpARM64MOVDconst, c.config.Types.UInt64, 7, nil),
   117  			Valu("A1", ssaop.OpARM64ADDSflags, types.NewTuple(c.config.Types.UInt64, types.TypeFlags), 0, nil, "x", "z"), // x+z, set flags
   118  			Valu("A1carry", ssaop.OpSelect1, types.TypeFlags, 0, nil, "A1"),
   119  			Valu("A2", ssaop.OpARM64ADDSflags, types.NewTuple(c.config.Types.UInt64, types.TypeFlags), 0, nil, "y", "z"), // y+z, set flags
   120  			Valu("A2carry", ssaop.OpSelect1, types.TypeFlags, 0, nil, "A2"),
   121  			Valu("A1value", ssaop.OpSelect0, c.config.Types.UInt64, 0, nil, "A1"),
   122  			Valu("A1Carryvalue", ssaop.OpARM64ADCzerocarry, c.config.Types.UInt64, 0, nil, "A1carry"), // 0+0+A1carry
   123  			Valu("A2value", ssaop.OpSelect0, c.config.Types.UInt64, 0, nil, "A2"),
   124  			Valu("A2Carryvalue", ssaop.OpARM64ADCzerocarry, c.config.Types.UInt64, 0, nil, "A2carry"), // 0+0+A2carry
   125  			Valu("ValueSum", ssaop.OpARM64ADD, c.config.Types.UInt64, 0, nil, "A1value", "A2value"),
   126  			Valu("CarrySum", ssaop.OpARM64ADD, c.config.Types.UInt64, 0, nil, "A1Carryvalue", "A2Carryvalue"),
   127  			Valu("Sum", ssaop.OpARM64AND, c.config.Types.UInt64, 0, nil, "ValueSum", "CarrySum"),
   128  			Goto("exit")),
   129  		Bloc("exit",
   130  			Exit("mem0")),
   131  	)
   132  
   133  	CheckFunc(fun.f)
   134  	schedule(fun.f)
   135  
   136  	// The expected order is A1 < A1carry < A1Carryvalue < A2 < A2carry < A2Carryvalue.
   137  	// There is no dependency between the two carry chains, so it doesn't matter which
   138  	// comes first and which comes after, but the unsorted position of A1 is before A2,
   139  	// so A1Carryvalue < A2.
   140  	var ai, bi, ci, di, ei, fi int
   141  	for i, v := range fun.f.Blocks[0].Values {
   142  		switch {
   143  		case fun.values["A1"] == v:
   144  			ai = i
   145  		case fun.values["A1carry"] == v:
   146  			bi = i
   147  		case fun.values["A1Carryvalue"] == v:
   148  			ci = i
   149  		case fun.values["A2"] == v:
   150  			di = i
   151  		case fun.values["A2carry"] == v:
   152  			ei = i
   153  		case fun.values["A2Carryvalue"] == v:
   154  			fi = i
   155  		}
   156  	}
   157  	if !(ai < bi && bi < ci && ci < di && di < ei && ei < fi) {
   158  		t.Logf("Func: %s", fun.f)
   159  		t.Errorf("carry chain order is wrong: got %v, want V%d after V%d after V%d after V%d after V%d after V%d,",
   160  			fun.f.Blocks[0], fun.values["A1"].ID, fun.values["A1carry"].ID, fun.values["A1Carryvalue"].ID,
   161  			fun.values["A2"].ID, fun.values["A2carry"].ID, fun.values["A2Carryvalue"].ID)
   162  	}
   163  }
   164
View as plain text