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 5package ssa 6 7import ( 8 "cmd/compile/internal/types" 9 "testing" 10) 11 12func BenchmarkDominatorsLinear(b *testing.B) { benchmarkDominators(b, 10000, genLinear) } 13func BenchmarkDominatorsFwdBack(b *testing.B) { benchmarkDominators(b, 10000, genFwdBack) } 14func BenchmarkDominatorsManyPred(b *testing.B) { benchmarkDominators(b, 10000, genManyPred) } 15func BenchmarkDominatorsMaxPred(b *testing.B) { benchmarkDominators(b, 10000, genMaxPred) } 16func BenchmarkDominatorsMaxPredVal(b *testing.B) { benchmarkDominators(b, 10000, genMaxPredValue) } 17 18type blockGen func(size int) []bloc 19 20// genLinear creates an array of blocks that succeed one another 21// b_n -> [b_n+1]. 22func genLinear(size int) []bloc { 23 var blocs []bloc 24 blocs = append(blocs, 25 Bloc("entry", 26 Valu("mem", OpInitMem, types.TypeMem, 0, nil), 27 Goto(blockn(0)), 28 ), 29 ) 30 for i := 0; i < size; i++ { 31 blocs = append(blocs, Bloc(blockn(i), 32 Goto(blockn(i+1)))) 33 } 34 35 blocs = append(blocs, 36 Bloc(blockn(size), Goto("exit")), 37 Bloc("exit", Exit("mem")), 38 ) 39 40 return blocs 41} 42 43// genFwdBack creates an array of blocks that alternate between 44// b_n -> [b_n+1], b_n -> [b_n+1, b_n-1] , b_n -> [b_n+1, b_n+2] 45func genFwdBack(size int) []bloc { 46 var blocs []bloc 47 blocs = append(blocs, 48 Bloc("entry", 49 Valu("mem", OpInitMem, types.TypeMem, 0, nil), 50 Valu("p", OpConstBool, types.Types[types.TBOOL], 1, nil), 51 Goto(blockn(0)), 52 ), 53 ) 54 for i := 0; i < size; i++ { 55 switch i % 2 { 56 case 0: 57 blocs = append(blocs, Bloc(blockn(i), 58 If("p", blockn(i+1), blockn(i+2)))) 59 case 1: 60 blocs = append(blocs, Bloc(blockn(i), 61 If("p", blockn(i+1), blockn(i-1)))) 62 } 63 } 64 65 blocs = append(blocs, 66 Bloc(blockn(size), Goto("exit")), 67 Bloc("exit", Exit("mem")), 68 ) 69 70 return blocs 71} 72 73// genManyPred creates an array of blocks where 1/3rd have a successor of the 74// first block, 1/3rd the last block, and the remaining third are plain. 75func genManyPred(size int) []bloc { 76 var blocs []bloc 77 blocs = append(blocs, 78 Bloc("entry", 79 Valu("mem", OpInitMem, types.TypeMem, 0, nil), 80 Valu("p", OpConstBool, types.Types[types.TBOOL], 1, nil), 81 Goto(blockn(0)), 82 ), 83 ) 84 85 // We want predecessor lists to be long, so 2/3rds of the blocks have a 86 // successor of the first or last block. 87 for i := 0; i < size; i++ { 88 switch i % 3 { 89 case 0: 90 blocs = append(blocs, Bloc(blockn(i), 91 Valu("a", OpConstBool, types.Types[types.TBOOL], 1, nil), 92 Goto(blockn(i+1)))) 93 case 1: 94 blocs = append(blocs, Bloc(blockn(i), 95 Valu("a", OpConstBool, types.Types[types.TBOOL], 1, nil), 96 If("p", blockn(i+1), blockn(0)))) 97 case 2: 98 blocs = append(blocs, Bloc(blockn(i), 99 Valu("a", OpConstBool, types.Types[types.TBOOL], 1, nil), 100 If("p", blockn(i+1), blockn(size)))) 101 } 102 } 103 104 blocs = append(blocs, 105 Bloc(blockn(size), Goto("exit")), 106 Bloc("exit", Exit("mem")), 107 ) 108 109 return blocs 110} 111 112// genMaxPred maximizes the size of the 'exit' predecessor list. 113func genMaxPred(size int) []bloc { 114 var blocs []bloc 115 blocs = append(blocs, 116 Bloc("entry", 117 Valu("mem", OpInitMem, types.TypeMem, 0, nil), 118 Valu("p", OpConstBool, types.Types[types.TBOOL], 1, nil), 119 Goto(blockn(0)), 120 ), 121 ) 122 123 for i := 0; i < size; i++ { 124 blocs = append(blocs, Bloc(blockn(i), 125 If("p", blockn(i+1), "exit"))) 126 } 127 128 blocs = append(blocs, 129 Bloc(blockn(size), Goto("exit")), 130 Bloc("exit", Exit("mem")), 131 ) 132 133 return blocs 134} 135 136// genMaxPredValue is identical to genMaxPred but contains an 137// additional value. 138func genMaxPredValue(size int) []bloc { 139 var blocs []bloc 140 blocs = append(blocs, 141 Bloc("entry", 142 Valu("mem", OpInitMem, types.TypeMem, 0, nil), 143 Valu("p", OpConstBool, types.Types[types.TBOOL], 1, nil), 144 Goto(blockn(0)), 145 ), 146 ) 147 148 for i := 0; i < size; i++ { 149 blocs = append(blocs, Bloc(blockn(i), 150 Valu("a", OpConstBool, types.Types[types.TBOOL], 1, nil), 151 If("p", blockn(i+1), "exit"))) 152 } 153 154 blocs = append(blocs, 155 Bloc(blockn(size), Goto("exit")), 156 Bloc("exit", Exit("mem")), 157 ) 158 159 return blocs 160} 161 162// sink for benchmark 163var domBenchRes []*Block 164 165func benchmarkDominators(b *testing.B, size int, bg blockGen) { 166 c := testConfig(b) 167 fun := c.Fun("entry", bg(size)...) 168 169 CheckFunc(fun.f) 170 b.SetBytes(int64(size)) 171 b.ResetTimer() 172 for i := 0; i < b.N; i++ { 173 domBenchRes = dominators(fun.f) 174 } 175} 176 177type domFunc func(f *Func) []*Block 178 179// verifyDominators verifies that the dominators of fut (function under test) 180// as determined by domFn, match the map node->dominator 181func verifyDominators(t *testing.T, fut fun, domFn domFunc, doms map[string]string) { 182 blockNames := map[*Block]string{} 183 for n, b := range fut.blocks { 184 blockNames[b] = n 185 } 186 187 calcDom := domFn(fut.f) 188 189 for n, d := range doms { 190 nblk, ok := fut.blocks[n] 191 if !ok { 192 t.Errorf("invalid block name %s", n) 193 } 194 dblk, ok := fut.blocks[d] 195 if !ok { 196 t.Errorf("invalid block name %s", d) 197 } 198 199 domNode := calcDom[nblk.ID] 200 switch { 201 case calcDom[nblk.ID] == dblk: 202 calcDom[nblk.ID] = nil 203 continue 204 case calcDom[nblk.ID] != dblk: 205 t.Errorf("expected %s as dominator of %s, found %s", d, n, blockNames[domNode]) 206 default: 207 t.Fatal("unexpected dominator condition") 208 } 209 } 210 211 for id, d := range calcDom { 212 // If nil, we've already verified it 213 if d == nil { 214 continue 215 } 216 for _, b := range fut.blocks { 217 if int(b.ID) == id { 218 t.Errorf("unexpected dominator of %s for %s", blockNames[d], blockNames[b]) 219 } 220 } 221 } 222 223} 224 225func TestDominatorsSingleBlock(t *testing.T) { 226 c := testConfig(t) 227 fun := c.Fun("entry", 228 Bloc("entry", 229 Valu("mem", OpInitMem, types.TypeMem, 0, nil), 230 Exit("mem"))) 231 232 doms := map[string]string{} 233 234 CheckFunc(fun.f) 235 verifyDominators(t, fun, dominators, doms) 236 verifyDominators(t, fun, dominatorsSimple, doms) 237 238} 239 240func TestDominatorsSimple(t *testing.T) { 241 c := testConfig(t) 242 fun := c.Fun("entry", 243 Bloc("entry", 244 Valu("mem", OpInitMem, types.TypeMem, 0, nil), 245 Goto("a")), 246 Bloc("a", 247 Goto("b")), 248 Bloc("b", 249 Goto("c")), 250 Bloc("c", 251 Goto("exit")), 252 Bloc("exit", 253 Exit("mem"))) 254 255 doms := map[string]string{ 256 "a": "entry", 257 "b": "a", 258 "c": "b", 259 "exit": "c", 260 } 261 262 CheckFunc(fun.f) 263 verifyDominators(t, fun, dominators, doms) 264 verifyDominators(t, fun, dominatorsSimple, doms) 265 266} 267 268func TestDominatorsMultPredFwd(t *testing.T) { 269 c := testConfig(t) 270 fun := c.Fun("entry", 271 Bloc("entry", 272 Valu("mem", OpInitMem, types.TypeMem, 0, nil), 273 Valu("p", OpConstBool, types.Types[types.TBOOL], 1, nil), 274 If("p", "a", "c")), 275 Bloc("a", 276 If("p", "b", "c")), 277 Bloc("b", 278 Goto("c")), 279 Bloc("c", 280 Goto("exit")), 281 Bloc("exit", 282 Exit("mem"))) 283 284 doms := map[string]string{ 285 "a": "entry", 286 "b": "a", 287 "c": "entry", 288 "exit": "c", 289 } 290 291 CheckFunc(fun.f) 292 verifyDominators(t, fun, dominators, doms) 293 verifyDominators(t, fun, dominatorsSimple, doms) 294} 295 296func TestDominatorsDeadCode(t *testing.T) { 297 c := testConfig(t) 298 fun := c.Fun("entry", 299 Bloc("entry", 300 Valu("mem", OpInitMem, types.TypeMem, 0, nil), 301 Valu("p", OpConstBool, types.Types[types.TBOOL], 0, nil), 302 If("p", "b3", "b5")), 303 Bloc("b2", Exit("mem")), 304 Bloc("b3", Goto("b2")), 305 Bloc("b4", Goto("b2")), 306 Bloc("b5", Goto("b2"))) 307 308 doms := map[string]string{ 309 "b2": "entry", 310 "b3": "entry", 311 "b5": "entry", 312 } 313 314 CheckFunc(fun.f) 315 verifyDominators(t, fun, dominators, doms) 316 verifyDominators(t, fun, dominatorsSimple, doms) 317} 318 319func TestDominatorsMultPredRev(t *testing.T) { 320 c := testConfig(t) 321 fun := c.Fun("entry", 322 Bloc("entry", 323 Goto("first")), 324 Bloc("first", 325 Valu("mem", OpInitMem, types.TypeMem, 0, nil), 326 Valu("p", OpConstBool, types.Types[types.TBOOL], 1, nil), 327 Goto("a")), 328 Bloc("a", 329 If("p", "b", "first")), 330 Bloc("b", 331 Goto("c")), 332 Bloc("c", 333 If("p", "exit", "b")), 334 Bloc("exit", 335 Exit("mem"))) 336 337 doms := map[string]string{ 338 "first": "entry", 339 "a": "first", 340 "b": "a", 341 "c": "b", 342 "exit": "c", 343 } 344 345 CheckFunc(fun.f) 346 verifyDominators(t, fun, dominators, doms) 347 verifyDominators(t, fun, dominatorsSimple, doms) 348} 349 350func TestDominatorsMultPred(t *testing.T) { 351 c := testConfig(t) 352 fun := c.Fun("entry", 353 Bloc("entry", 354 Valu("mem", OpInitMem, types.TypeMem, 0, nil), 355 Valu("p", OpConstBool, types.Types[types.TBOOL], 1, nil), 356 If("p", "a", "c")), 357 Bloc("a", 358 If("p", "b", "c")), 359 Bloc("b", 360 Goto("c")), 361 Bloc("c", 362 If("p", "b", "exit")), 363 Bloc("exit", 364 Exit("mem"))) 365 366 doms := map[string]string{ 367 "a": "entry", 368 "b": "entry", 369 "c": "entry", 370 "exit": "c", 371 } 372 373 CheckFunc(fun.f) 374 verifyDominators(t, fun, dominators, doms) 375 verifyDominators(t, fun, dominatorsSimple, doms) 376} 377 378func TestInfiniteLoop(t *testing.T) { 379 c := testConfig(t) 380 // note lack of an exit block 381 fun := c.Fun("entry", 382 Bloc("entry", 383 Valu("mem", OpInitMem, types.TypeMem, 0, nil), 384 Valu("p", OpConstBool, types.Types[types.TBOOL], 1, nil), 385 Goto("a")), 386 Bloc("a", 387 Goto("b")), 388 Bloc("b", 389 Goto("a"))) 390 391 CheckFunc(fun.f) 392 doms := map[string]string{"a": "entry", 393 "b": "a"} 394 verifyDominators(t, fun, dominators, doms) 395} 396 397func TestDomTricky(t *testing.T) { 398 doms := map[string]string{ 399 "4": "1", 400 "2": "4", 401 "5": "4", 402 "11": "4", 403 "15": "4", // the incorrect answer is "5" 404 "10": "15", 405 "19": "15", 406 } 407 408 if4 := [2]string{"2", "5"} 409 if5 := [2]string{"15", "11"} 410 if15 := [2]string{"19", "10"} 411 412 for i := 0; i < 8; i++ { 413 a := 1 & i 414 b := 1 & i >> 1 415 c := 1 & i >> 2 416 417 cfg := testConfig(t) 418 fun := cfg.Fun("1", 419 Bloc("1", 420 Valu("mem", OpInitMem, types.TypeMem, 0, nil), 421 Valu("p", OpConstBool, types.Types[types.TBOOL], 1, nil), 422 Goto("4")), 423 Bloc("2", 424 Goto("11")), 425 Bloc("4", 426 If("p", if4[a], if4[1-a])), // 2, 5 427 Bloc("5", 428 If("p", if5[b], if5[1-b])), //15, 11 429 Bloc("10", 430 Exit("mem")), 431 Bloc("11", 432 Goto("15")), 433 Bloc("15", 434 If("p", if15[c], if15[1-c])), //19, 10 435 Bloc("19", 436 Goto("10"))) 437 CheckFunc(fun.f) 438 verifyDominators(t, fun, dominators, doms) 439 verifyDominators(t, fun, dominatorsSimple, doms) 440 } 441} 442 443// generateDominatorMap uses dominatorsSimple to obtain a 444// reference dominator tree for testing faster algorithms. 445func generateDominatorMap(fut fun) map[string]string { 446 blockNames := map[*Block]string{} 447 for n, b := range fut.blocks { 448 blockNames[b] = n 449 } 450 referenceDom := dominatorsSimple(fut.f) 451 doms := make(map[string]string) 452 for _, b := range fut.f.Blocks { 453 if d := referenceDom[b.ID]; d != nil { 454 doms[blockNames[b]] = blockNames[d] 455 } 456 } 457 return doms 458} 459 460func TestDominatorsPostTrickyA(t *testing.T) { 461 testDominatorsPostTricky(t, "b8", "b11", "b10", "b8", "b14", "b15") 462} 463 464func TestDominatorsPostTrickyB(t *testing.T) { 465 testDominatorsPostTricky(t, "b11", "b8", "b10", "b8", "b14", "b15") 466} 467 468func TestDominatorsPostTrickyC(t *testing.T) { 469 testDominatorsPostTricky(t, "b8", "b11", "b8", "b10", "b14", "b15") 470} 471 472func TestDominatorsPostTrickyD(t *testing.T) { 473 testDominatorsPostTricky(t, "b11", "b8", "b8", "b10", "b14", "b15") 474} 475 476func TestDominatorsPostTrickyE(t *testing.T) { 477 testDominatorsPostTricky(t, "b8", "b11", "b10", "b8", "b15", "b14") 478} 479 480func TestDominatorsPostTrickyF(t *testing.T) { 481 testDominatorsPostTricky(t, "b11", "b8", "b10", "b8", "b15", "b14") 482} 483 484func TestDominatorsPostTrickyG(t *testing.T) { 485 testDominatorsPostTricky(t, "b8", "b11", "b8", "b10", "b15", "b14") 486} 487 488func TestDominatorsPostTrickyH(t *testing.T) { 489 testDominatorsPostTricky(t, "b11", "b8", "b8", "b10", "b15", "b14") 490} 491 492func testDominatorsPostTricky(t *testing.T, b7then, b7else, b12then, b12else, b13then, b13else string) { 493 c := testConfig(t) 494 fun := c.Fun("b1", 495 Bloc("b1", 496 Valu("mem", OpInitMem, types.TypeMem, 0, nil), 497 Valu("p", OpConstBool, types.Types[types.TBOOL], 1, nil), 498 If("p", "b3", "b2")), 499 Bloc("b3", 500 If("p", "b5", "b6")), 501 Bloc("b5", 502 Goto("b7")), 503 Bloc("b7", 504 If("p", b7then, b7else)), 505 Bloc("b8", 506 Goto("b13")), 507 Bloc("b13", 508 If("p", b13then, b13else)), 509 Bloc("b14", 510 Goto("b10")), 511 Bloc("b15", 512 Goto("b16")), 513 Bloc("b16", 514 Goto("b9")), 515 Bloc("b9", 516 Goto("b7")), 517 Bloc("b11", 518 Goto("b12")), 519 Bloc("b12", 520 If("p", b12then, b12else)), 521 Bloc("b10", 522 Goto("b6")), 523 Bloc("b6", 524 Goto("b17")), 525 Bloc("b17", 526 Goto("b18")), 527 Bloc("b18", 528 If("p", "b22", "b19")), 529 Bloc("b22", 530 Goto("b23")), 531 Bloc("b23", 532 If("p", "b21", "b19")), 533 Bloc("b19", 534 If("p", "b24", "b25")), 535 Bloc("b24", 536 Goto("b26")), 537 Bloc("b26", 538 Goto("b25")), 539 Bloc("b25", 540 If("p", "b27", "b29")), 541 Bloc("b27", 542 Goto("b30")), 543 Bloc("b30", 544 Goto("b28")), 545 Bloc("b29", 546 Goto("b31")), 547 Bloc("b31", 548 Goto("b28")), 549 Bloc("b28", 550 If("p", "b32", "b33")), 551 Bloc("b32", 552 Goto("b21")), 553 Bloc("b21", 554 Goto("b47")), 555 Bloc("b47", 556 If("p", "b45", "b46")), 557 Bloc("b45", 558 Goto("b48")), 559 Bloc("b48", 560 Goto("b49")), 561 Bloc("b49", 562 If("p", "b50", "b51")), 563 Bloc("b50", 564 Goto("b52")), 565 Bloc("b52", 566 Goto("b53")), 567 Bloc("b53", 568 Goto("b51")), 569 Bloc("b51", 570 Goto("b54")), 571 Bloc("b54", 572 Goto("b46")), 573 Bloc("b46", 574 Exit("mem")), 575 Bloc("b33", 576 Goto("b34")), 577 Bloc("b34", 578 Goto("b37")), 579 Bloc("b37", 580 If("p", "b35", "b36")), 581 Bloc("b35", 582 Goto("b38")), 583 Bloc("b38", 584 Goto("b39")), 585 Bloc("b39", 586 If("p", "b40", "b41")), 587 Bloc("b40", 588 Goto("b42")), 589 Bloc("b42", 590 Goto("b43")), 591 Bloc("b43", 592 Goto("b41")), 593 Bloc("b41", 594 Goto("b44")), 595 Bloc("b44", 596 Goto("b36")), 597 Bloc("b36", 598 Goto("b20")), 599 Bloc("b20", 600 Goto("b18")), 601 Bloc("b2", 602 Goto("b4")), 603 Bloc("b4", 604 Exit("mem"))) 605 CheckFunc(fun.f) 606 doms := generateDominatorMap(fun) 607 verifyDominators(t, fun, dominators, doms) 608} 609