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// This file contains some utility functions to help define Funcs for testing. 6// As an example, the following func 7// 8// b1: 9// v1 = InitMem <mem> 10// Plain -> b2 11// b2: 12// Exit v1 13// b3: 14// v2 = Const <bool> [true] 15// If v2 -> b3 b2 16// 17// can be defined as 18// 19// fun := Fun("entry", 20// Bloc("entry", 21// Valu("mem", OpInitMem, types.TypeMem, 0, nil), 22// Goto("exit")), 23// Bloc("exit", 24// Exit("mem")), 25// Bloc("deadblock", 26// Valu("deadval", OpConstBool, c.config.Types.Bool, 0, true), 27// If("deadval", "deadblock", "exit"))) 28// 29// and the Blocks or Values used in the Func can be accessed 30// like this: 31// fun.blocks["entry"] or fun.values["deadval"] 32 33package ssa 34 35// TODO(matloob): Choose better names for Fun, Bloc, Goto, etc. 36// TODO(matloob): Write a parser for the Func disassembly. Maybe 37// the parser can be used instead of Fun. 38 39import ( 40 "cmd/compile/internal/types" 41 "cmd/internal/obj" 42 "cmd/internal/src" 43 "fmt" 44 "reflect" 45 "testing" 46) 47 48// Compare two Funcs for equivalence. Their CFGs must be isomorphic, 49// and their values must correspond. 50// Requires that values and predecessors are in the same order, even 51// though Funcs could be equivalent when they are not. 52// TODO(matloob): Allow values and predecessors to be in different 53// orders if the CFG are otherwise equivalent. 54func Equiv(f, g *Func) bool { 55 valcor := make(map[*Value]*Value) 56 var checkVal func(fv, gv *Value) bool 57 checkVal = func(fv, gv *Value) bool { 58 if fv == nil && gv == nil { 59 return true 60 } 61 if valcor[fv] == nil && valcor[gv] == nil { 62 valcor[fv] = gv 63 valcor[gv] = fv 64 // Ignore ids. Ops and Types are compared for equality. 65 // TODO(matloob): Make sure types are canonical and can 66 // be compared for equality. 67 if fv.Op != gv.Op || fv.Type != gv.Type || fv.AuxInt != gv.AuxInt { 68 return false 69 } 70 if !reflect.DeepEqual(fv.Aux, gv.Aux) { 71 // This makes the assumption that aux values can be compared 72 // using DeepEqual. 73 // TODO(matloob): Aux values may be *gc.Sym pointers in the near 74 // future. Make sure they are canonical. 75 return false 76 } 77 if len(fv.Args) != len(gv.Args) { 78 return false 79 } 80 for i := range fv.Args { 81 if !checkVal(fv.Args[i], gv.Args[i]) { 82 return false 83 } 84 } 85 } 86 return valcor[fv] == gv && valcor[gv] == fv 87 } 88 blkcor := make(map[*Block]*Block) 89 var checkBlk func(fb, gb *Block) bool 90 checkBlk = func(fb, gb *Block) bool { 91 if blkcor[fb] == nil && blkcor[gb] == nil { 92 blkcor[fb] = gb 93 blkcor[gb] = fb 94 // ignore ids 95 if fb.Kind != gb.Kind { 96 return false 97 } 98 if len(fb.Values) != len(gb.Values) { 99 return false 100 } 101 for i := range fb.Values { 102 if !checkVal(fb.Values[i], gb.Values[i]) { 103 return false 104 } 105 } 106 if len(fb.Succs) != len(gb.Succs) { 107 return false 108 } 109 for i := range fb.Succs { 110 if !checkBlk(fb.Succs[i].b, gb.Succs[i].b) { 111 return false 112 } 113 } 114 if len(fb.Preds) != len(gb.Preds) { 115 return false 116 } 117 for i := range fb.Preds { 118 if !checkBlk(fb.Preds[i].b, gb.Preds[i].b) { 119 return false 120 } 121 } 122 return true 123 124 } 125 return blkcor[fb] == gb && blkcor[gb] == fb 126 } 127 128 return checkBlk(f.Entry, g.Entry) 129} 130 131// fun is the return type of Fun. It contains the created func 132// itself as well as indexes from block and value names into the 133// corresponding Blocks and Values. 134type fun struct { 135 f *Func 136 blocks map[string]*Block 137 values map[string]*Value 138} 139 140var emptyPass pass = pass{ 141 name: "empty pass", 142} 143 144// AuxCallLSym returns an AuxCall initialized with an LSym that should pass "check" 145// as the Aux of a static call. 146func AuxCallLSym(name string) *AuxCall { 147 return &AuxCall{Fn: &obj.LSym{}} 148} 149 150// Fun takes the name of an entry bloc and a series of Bloc calls, and 151// returns a fun containing the composed Func. entry must be a name 152// supplied to one of the Bloc functions. Each of the bloc names and 153// valu names should be unique across the Fun. 154func (c *Conf) Fun(entry string, blocs ...bloc) fun { 155 // TODO: Either mark some SSA tests as t.Parallel, 156 // or set up a shared Cache and Reset it between tests. 157 // But not both. 158 f := c.config.NewFunc(c.Frontend(), new(Cache)) 159 f.pass = &emptyPass 160 f.cachedLineStarts = newXposmap(map[int]lineRange{0: {0, 100}, 1: {0, 100}, 2: {0, 100}, 3: {0, 100}, 4: {0, 100}}) 161 162 blocks := make(map[string]*Block) 163 values := make(map[string]*Value) 164 // Create all the blocks and values. 165 for _, bloc := range blocs { 166 b := f.NewBlock(bloc.control.kind) 167 blocks[bloc.name] = b 168 for _, valu := range bloc.valus { 169 // args are filled in the second pass. 170 values[valu.name] = b.NewValue0IA(src.NoXPos, valu.op, valu.t, valu.auxint, valu.aux) 171 } 172 } 173 // Connect the blocks together and specify control values. 174 f.Entry = blocks[entry] 175 for _, bloc := range blocs { 176 b := blocks[bloc.name] 177 c := bloc.control 178 // Specify control values. 179 if c.control != "" { 180 cval, ok := values[c.control] 181 if !ok { 182 f.Fatalf("control value for block %s missing", bloc.name) 183 } 184 b.SetControl(cval) 185 } 186 // Fill in args. 187 for _, valu := range bloc.valus { 188 v := values[valu.name] 189 for _, arg := range valu.args { 190 a, ok := values[arg] 191 if !ok { 192 b.Fatalf("arg %s missing for value %s in block %s", 193 arg, valu.name, bloc.name) 194 } 195 v.AddArg(a) 196 } 197 } 198 // Connect to successors. 199 for _, succ := range c.succs { 200 b.AddEdgeTo(blocks[succ]) 201 } 202 } 203 return fun{f, blocks, values} 204} 205 206// Bloc defines a block for Fun. The bloc name should be unique 207// across the containing Fun. entries should consist of calls to valu, 208// as well as one call to Goto, If, or Exit to specify the block kind. 209func Bloc(name string, entries ...interface{}) bloc { 210 b := bloc{} 211 b.name = name 212 seenCtrl := false 213 for _, e := range entries { 214 switch v := e.(type) { 215 case ctrl: 216 // there should be exactly one Ctrl entry. 217 if seenCtrl { 218 panic(fmt.Sprintf("already seen control for block %s", name)) 219 } 220 b.control = v 221 seenCtrl = true 222 case valu: 223 b.valus = append(b.valus, v) 224 } 225 } 226 if !seenCtrl { 227 panic(fmt.Sprintf("block %s doesn't have control", b.name)) 228 } 229 return b 230} 231 232// Valu defines a value in a block. 233func Valu(name string, op Op, t *types.Type, auxint int64, aux Aux, args ...string) valu { 234 return valu{name, op, t, auxint, aux, args} 235} 236 237// Goto specifies that this is a BlockPlain and names the single successor. 238// TODO(matloob): choose a better name. 239func Goto(succ string) ctrl { 240 return ctrl{BlockPlain, "", []string{succ}} 241} 242 243// If specifies a BlockIf. 244func If(cond, sub, alt string) ctrl { 245 return ctrl{BlockIf, cond, []string{sub, alt}} 246} 247 248// Exit specifies a BlockExit. 249func Exit(arg string) ctrl { 250 return ctrl{BlockExit, arg, []string{}} 251} 252 253// Eq specifies a BlockAMD64EQ. 254func Eq(cond, sub, alt string) ctrl { 255 return ctrl{BlockAMD64EQ, cond, []string{sub, alt}} 256} 257 258// bloc, ctrl, and valu are internal structures used by Bloc, Valu, Goto, 259// If, and Exit to help define blocks. 260 261type bloc struct { 262 name string 263 control ctrl 264 valus []valu 265} 266 267type ctrl struct { 268 kind BlockKind 269 control string 270 succs []string 271} 272 273type valu struct { 274 name string 275 op Op 276 t *types.Type 277 auxint int64 278 aux Aux 279 args []string 280} 281 282func TestArgs(t *testing.T) { 283 c := testConfig(t) 284 fun := c.Fun("entry", 285 Bloc("entry", 286 Valu("a", OpConst64, c.config.Types.Int64, 14, nil), 287 Valu("b", OpConst64, c.config.Types.Int64, 26, nil), 288 Valu("sum", OpAdd64, c.config.Types.Int64, 0, nil, "a", "b"), 289 Valu("mem", OpInitMem, types.TypeMem, 0, nil), 290 Goto("exit")), 291 Bloc("exit", 292 Exit("mem"))) 293 sum := fun.values["sum"] 294 for i, name := range []string{"a", "b"} { 295 if sum.Args[i] != fun.values[name] { 296 t.Errorf("arg %d for sum is incorrect: want %s, got %s", 297 i, sum.Args[i], fun.values[name]) 298 } 299 } 300} 301 302func TestEquiv(t *testing.T) { 303 cfg := testConfig(t) 304 equivalentCases := []struct{ f, g fun }{ 305 // simple case 306 { 307 cfg.Fun("entry", 308 Bloc("entry", 309 Valu("a", OpConst64, cfg.config.Types.Int64, 14, nil), 310 Valu("b", OpConst64, cfg.config.Types.Int64, 26, nil), 311 Valu("sum", OpAdd64, cfg.config.Types.Int64, 0, nil, "a", "b"), 312 Valu("mem", OpInitMem, types.TypeMem, 0, nil), 313 Goto("exit")), 314 Bloc("exit", 315 Exit("mem"))), 316 cfg.Fun("entry", 317 Bloc("entry", 318 Valu("a", OpConst64, cfg.config.Types.Int64, 14, nil), 319 Valu("b", OpConst64, cfg.config.Types.Int64, 26, nil), 320 Valu("sum", OpAdd64, cfg.config.Types.Int64, 0, nil, "a", "b"), 321 Valu("mem", OpInitMem, types.TypeMem, 0, nil), 322 Goto("exit")), 323 Bloc("exit", 324 Exit("mem"))), 325 }, 326 // block order changed 327 { 328 cfg.Fun("entry", 329 Bloc("entry", 330 Valu("a", OpConst64, cfg.config.Types.Int64, 14, nil), 331 Valu("b", OpConst64, cfg.config.Types.Int64, 26, nil), 332 Valu("sum", OpAdd64, cfg.config.Types.Int64, 0, nil, "a", "b"), 333 Valu("mem", OpInitMem, types.TypeMem, 0, nil), 334 Goto("exit")), 335 Bloc("exit", 336 Exit("mem"))), 337 cfg.Fun("entry", 338 Bloc("exit", 339 Exit("mem")), 340 Bloc("entry", 341 Valu("a", OpConst64, cfg.config.Types.Int64, 14, nil), 342 Valu("b", OpConst64, cfg.config.Types.Int64, 26, nil), 343 Valu("sum", OpAdd64, cfg.config.Types.Int64, 0, nil, "a", "b"), 344 Valu("mem", OpInitMem, types.TypeMem, 0, nil), 345 Goto("exit"))), 346 }, 347 } 348 for _, c := range equivalentCases { 349 if !Equiv(c.f.f, c.g.f) { 350 t.Error("expected equivalence. Func definitions:") 351 t.Error(c.f.f) 352 t.Error(c.g.f) 353 } 354 } 355 356 differentCases := []struct{ f, g fun }{ 357 // different shape 358 { 359 cfg.Fun("entry", 360 Bloc("entry", 361 Valu("mem", OpInitMem, types.TypeMem, 0, nil), 362 Goto("exit")), 363 Bloc("exit", 364 Exit("mem"))), 365 cfg.Fun("entry", 366 Bloc("entry", 367 Valu("mem", OpInitMem, types.TypeMem, 0, nil), 368 Exit("mem"))), 369 }, 370 // value order changed 371 { 372 cfg.Fun("entry", 373 Bloc("entry", 374 Valu("mem", OpInitMem, types.TypeMem, 0, nil), 375 Valu("b", OpConst64, cfg.config.Types.Int64, 26, nil), 376 Valu("a", OpConst64, cfg.config.Types.Int64, 14, nil), 377 Exit("mem"))), 378 cfg.Fun("entry", 379 Bloc("entry", 380 Valu("mem", OpInitMem, types.TypeMem, 0, nil), 381 Valu("a", OpConst64, cfg.config.Types.Int64, 14, nil), 382 Valu("b", OpConst64, cfg.config.Types.Int64, 26, nil), 383 Exit("mem"))), 384 }, 385 // value auxint different 386 { 387 cfg.Fun("entry", 388 Bloc("entry", 389 Valu("mem", OpInitMem, types.TypeMem, 0, nil), 390 Valu("a", OpConst64, cfg.config.Types.Int64, 14, nil), 391 Exit("mem"))), 392 cfg.Fun("entry", 393 Bloc("entry", 394 Valu("mem", OpInitMem, types.TypeMem, 0, nil), 395 Valu("a", OpConst64, cfg.config.Types.Int64, 26, nil), 396 Exit("mem"))), 397 }, 398 // value aux different 399 { 400 cfg.Fun("entry", 401 Bloc("entry", 402 Valu("mem", OpInitMem, types.TypeMem, 0, nil), 403 Valu("a", OpConstString, cfg.config.Types.String, 0, StringToAux("foo")), 404 Exit("mem"))), 405 cfg.Fun("entry", 406 Bloc("entry", 407 Valu("mem", OpInitMem, types.TypeMem, 0, nil), 408 Valu("a", OpConstString, cfg.config.Types.String, 0, StringToAux("bar")), 409 Exit("mem"))), 410 }, 411 // value args different 412 { 413 cfg.Fun("entry", 414 Bloc("entry", 415 Valu("mem", OpInitMem, types.TypeMem, 0, nil), 416 Valu("a", OpConst64, cfg.config.Types.Int64, 14, nil), 417 Valu("b", OpConst64, cfg.config.Types.Int64, 26, nil), 418 Valu("sum", OpAdd64, cfg.config.Types.Int64, 0, nil, "a", "b"), 419 Exit("mem"))), 420 cfg.Fun("entry", 421 Bloc("entry", 422 Valu("mem", OpInitMem, types.TypeMem, 0, nil), 423 Valu("a", OpConst64, cfg.config.Types.Int64, 0, nil), 424 Valu("b", OpConst64, cfg.config.Types.Int64, 14, nil), 425 Valu("sum", OpAdd64, cfg.config.Types.Int64, 0, nil, "b", "a"), 426 Exit("mem"))), 427 }, 428 } 429 for _, c := range differentCases { 430 if Equiv(c.f.f, c.g.f) { 431 t.Error("expected difference. Func definitions:") 432 t.Error(c.f.f) 433 t.Error(c.g.f) 434 } 435 } 436} 437 438// TestConstCache ensures that the cache will not return 439// reused free'd values with a non-matching AuxInt 440func TestConstCache(t *testing.T) { 441 c := testConfig(t) 442 f := c.Fun("entry", 443 Bloc("entry", 444 Valu("mem", OpInitMem, types.TypeMem, 0, nil), 445 Exit("mem"))) 446 v1 := f.f.ConstBool(c.config.Types.Bool, false) 447 v2 := f.f.ConstBool(c.config.Types.Bool, true) 448 f.f.freeValue(v1) 449 f.f.freeValue(v2) 450 v3 := f.f.ConstBool(c.config.Types.Bool, false) 451 v4 := f.f.ConstBool(c.config.Types.Bool, true) 452 if v3.AuxInt != 0 { 453 t.Errorf("expected %s to have auxint of 0\n", v3.LongString()) 454 } 455 if v4.AuxInt != 1 { 456 t.Errorf("expected %s to have auxint of 1\n", v4.LongString()) 457 } 458 459} 460 461// opcodeMap returns a map from opcode to the number of times that opcode 462// appears in the function. 463func opcodeMap(f *Func) map[Op]int { 464 m := map[Op]int{} 465 for _, b := range f.Blocks { 466 for _, v := range b.Values { 467 m[v.Op]++ 468 } 469 } 470 return m 471} 472 473// opcodeCounts checks that the number of opcodes listed in m agree with the 474// number of opcodes that appear in the function. 475func checkOpcodeCounts(t *testing.T, f *Func, m map[Op]int) { 476 n := opcodeMap(f) 477 for op, cnt := range m { 478 if n[op] != cnt { 479 t.Errorf("%s appears %d times, want %d times", op, n[op], cnt) 480 } 481 } 482} 483