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