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