Source file src/cmd/compile/internal/ssa/shortcircuit.go
1 // Copyright 2016 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 // shortcircuit finds situations where branch directions 8 // are always correlated and rewrites the CFG to take 9 // advantage of that fact. 10 // This optimization is useful for compiling && and || expressions. 11 func shortcircuit(f *Func) { 12 // Step 1: Replace a phi arg with a constant if that arg 13 // is the control value of a preceding If block. 14 // b1: 15 // If a goto b2 else b3 16 // b2: <- b1 ... 17 // x = phi(a, ...) 18 // 19 // We can replace the "a" in the phi with the constant true. 20 var ct, cf *Value 21 for _, b := range f.Blocks { 22 for _, v := range b.Values { 23 if v.Op != OpPhi { 24 continue 25 } 26 if !v.Type.IsBoolean() { 27 continue 28 } 29 for i, a := range v.Args { 30 e := b.Preds[i] 31 p := e.b 32 if p.Kind != BlockIf { 33 continue 34 } 35 if p.Controls[0] != a { 36 continue 37 } 38 if e.i == 0 { 39 if ct == nil { 40 ct = f.ConstBool(f.Config.Types.Bool, true) 41 } 42 v.SetArg(i, ct) 43 } else { 44 if cf == nil { 45 cf = f.ConstBool(f.Config.Types.Bool, false) 46 } 47 v.SetArg(i, cf) 48 } 49 } 50 } 51 } 52 53 // Step 2: Redirect control flow around known branches. 54 // p: 55 // ... goto b ... 56 // b: <- p ... 57 // v = phi(true, ...) 58 // if v goto t else u 59 // We can redirect p to go directly to t instead of b. 60 // (If v is not live after b). 61 fuse(f, fuseTypePlain|fuseTypeShortCircuit) 62 } 63 64 // shortcircuitBlock checks for a CFG in which an If block 65 // has as its control value a Phi that has a ConstBool arg. 66 // In some such cases, we can rewrite the CFG into a flatter form. 67 // 68 // (1) Look for a CFG of the form 69 // 70 // p other pred(s) 71 // \ / 72 // b 73 // / \ 74 // t other succ 75 // 76 // in which b is an If block containing a single phi value with a single use (b's Control), 77 // which has a ConstBool arg. 78 // p is the predecessor corresponding to the argument slot in which the ConstBool is found. 79 // t is the successor corresponding to the value of the ConstBool arg. 80 // 81 // Rewrite this into 82 // 83 // p other pred(s) 84 // | / 85 // | b 86 // |/ \ 87 // t u 88 // 89 // and remove the appropriate phi arg(s). 90 // 91 // (2) Look for a CFG of the form 92 // 93 // p q 94 // \ / 95 // b 96 // / \ 97 // t u 98 // 99 // in which b is as described in (1). 100 // However, b may also contain other phi values. 101 // The CFG will be modified as described in (1). 102 // However, in order to handle those other phi values, 103 // for each other phi value w, we must be able to eliminate w from b. 104 // We can do that though a combination of moving w to a different block 105 // and rewriting uses of w to use a different value instead. 106 // See shortcircuitPhiPlan for details. 107 func shortcircuitBlock(b *Block) bool { 108 if b.Kind != BlockIf { 109 return false 110 } 111 // Look for control values of the form Copy(Not(Copy(Phi(const, ...)))). 112 // Those must be the only values in the b, and they each must be used only by b. 113 // Track the negations so that we can swap successors as needed later. 114 ctl := b.Controls[0] 115 nval := 1 // the control value 116 var swap int64 117 for ctl.Uses == 1 && ctl.Block == b && (ctl.Op == OpCopy || ctl.Op == OpNot) { 118 if ctl.Op == OpNot { 119 swap = 1 ^ swap 120 } 121 ctl = ctl.Args[0] 122 nval++ // wrapper around control value 123 } 124 if ctl.Op != OpPhi || ctl.Block != b || ctl.Uses != 1 { 125 return false 126 } 127 nOtherPhi := 0 128 for _, w := range b.Values { 129 if w.Op == OpPhi && w != ctl { 130 nOtherPhi++ 131 } 132 } 133 if nOtherPhi > 0 && len(b.Preds) != 2 { 134 // We rely on b having exactly two preds in shortcircuitPhiPlan 135 // to reason about the values of phis. 136 return false 137 } 138 // We only process blocks with only phi values except for control 139 // value and its wrappers. 140 if len(b.Values) != nval+nOtherPhi { 141 return false 142 } 143 if nOtherPhi > 0 { 144 // Check for any phi which is the argument of another phi. 145 // These cases are tricky, as substitutions done by replaceUses 146 // are no longer trivial to do in any ordering. See issue 45175. 147 m := make(map[*Value]bool, 1+nOtherPhi) 148 for _, v := range b.Values { 149 if v.Op == OpPhi { 150 m[v] = true 151 } 152 } 153 for v := range m { 154 for _, a := range v.Args { 155 if a != v && m[a] { 156 return false 157 } 158 } 159 } 160 } 161 162 // Locate index of first const phi arg. 163 cidx := -1 164 for i, a := range ctl.Args { 165 if a.Op == OpConstBool { 166 cidx = i 167 break 168 } 169 } 170 if cidx == -1 { 171 return false 172 } 173 174 // p is the predecessor corresponding to cidx. 175 pe := b.Preds[cidx] 176 p := pe.b 177 pi := pe.i 178 179 // t is the "taken" branch: the successor we always go to when coming in from p. 180 ti := 1 ^ ctl.Args[cidx].AuxInt ^ swap 181 te := b.Succs[ti] 182 t := te.b 183 if p == b || t == b { 184 // This is an infinite loop; we can't remove it. See issue 33903. 185 return false 186 } 187 188 var fixPhi func(*Value, int) 189 if nOtherPhi > 0 { 190 fixPhi = shortcircuitPhiPlan(b, ctl, cidx, ti) 191 if fixPhi == nil { 192 return false 193 } 194 } 195 196 // We're committed. Update CFG and Phis. 197 // If you modify this section, update shortcircuitPhiPlan corresponding. 198 199 // Remove b's incoming edge from p. 200 b.removePred(cidx) 201 b.removePhiArg(ctl, cidx) 202 203 // Redirect p's outgoing edge to t. 204 p.Succs[pi] = Edge{t, len(t.Preds)} 205 206 // Fix up t to have one more predecessor. 207 t.Preds = append(t.Preds, Edge{p, pi}) 208 for _, v := range t.Values { 209 if v.Op != OpPhi { 210 continue 211 } 212 v.AddArg(v.Args[te.i]) 213 } 214 215 if nOtherPhi != 0 { 216 // Adjust all other phis as necessary. 217 // Use a plain for loop instead of range because fixPhi may move phis, 218 // thus modifying b.Values. 219 for i := 0; i < len(b.Values); i++ { 220 phi := b.Values[i] 221 if phi.Uses == 0 || phi == ctl || phi.Op != OpPhi { 222 continue 223 } 224 fixPhi(phi, i) 225 if phi.Block == b { 226 continue 227 } 228 // phi got moved to a different block with v.moveTo. 229 // Adjust phi values in this new block that refer 230 // to phi to refer to the corresponding phi arg instead. 231 // phi used to be evaluated prior to this block, 232 // and now it is evaluated in this block. 233 for _, v := range phi.Block.Values { 234 if v.Op != OpPhi || v == phi { 235 continue 236 } 237 for j, a := range v.Args { 238 if a == phi { 239 v.SetArg(j, phi.Args[j]) 240 } 241 } 242 } 243 if phi.Uses != 0 { 244 phielimValue(phi) 245 } else { 246 phi.reset(OpInvalid) 247 } 248 i-- // v.moveTo put a new value at index i; reprocess 249 } 250 251 // We may have left behind some phi values with no uses 252 // but the wrong number of arguments. Eliminate those. 253 for _, v := range b.Values { 254 if v.Uses == 0 { 255 v.reset(OpInvalid) 256 } 257 } 258 } 259 260 if len(b.Preds) == 0 { 261 // Block is now dead. 262 b.Kind = BlockInvalid 263 } 264 265 phielimValue(ctl) 266 return true 267 } 268 269 // shortcircuitPhiPlan returns a function to handle non-ctl phi values in b, 270 // where b is as described in shortcircuitBlock. 271 // The returned function accepts a value v 272 // and the index i of v in v.Block: v.Block.Values[i] == v. 273 // If the returned function moves v to a different block, it will use v.moveTo. 274 // cidx is the index in ctl of the ConstBool arg. 275 // ti is the index in b.Succs of the always taken branch when arriving from p. 276 // If shortcircuitPhiPlan returns nil, there is no plan available, 277 // and the CFG modifications must not proceed. 278 // The returned function assumes that shortcircuitBlock has completed its CFG modifications. 279 func shortcircuitPhiPlan(b *Block, ctl *Value, cidx int, ti int64) func(*Value, int) { 280 // t is the "taken" branch: the successor we always go to when coming in from p. 281 t := b.Succs[ti].b 282 // u is the "untaken" branch: the successor we never go to when coming in from p. 283 u := b.Succs[1^ti].b 284 285 // In the following CFG matching, ensure that b's preds are entirely distinct from b's succs. 286 // This is probably a stronger condition than required, but this happens extremely rarely, 287 // and it makes it easier to avoid getting deceived by pretty ASCII charts. See #44465. 288 if p0, p1 := b.Preds[0].b, b.Preds[1].b; p0 == t || p1 == t || p0 == u || p1 == u { 289 return nil 290 } 291 292 // Look for some common CFG structures 293 // in which the outbound paths from b merge, 294 // with no other preds joining them. 295 // In these cases, we can reconstruct what the value 296 // of any phi in b must be in the successor blocks. 297 298 if len(t.Preds) == 1 && len(t.Succs) == 1 && len(u.Preds) == 1 && 299 len(t.Succs[0].b.Preds) == 2 { 300 m := t.Succs[0].b 301 if visited := u.flowsTo(m, 5); visited != nil { 302 // p q 303 // \ / 304 // b 305 // / \ 306 // t U (sub graph that satisfy condition in flowsTo) 307 // \ / 308 // m 309 // 310 // After the CFG modifications, this will look like 311 // 312 // p q 313 // | / 314 // | b 315 // |/ \ 316 // t U 317 // \ / 318 // m 319 // 320 // NB: t.Preds is (b, p), not (p, b). 321 return func(v *Value, i int) { 322 // Replace any uses of v in t and u with the value v must have, 323 // given that we have arrived at that block. 324 // Then move v to m and adjust its value accordingly; 325 // this handles all other uses of v. 326 argP, argQ := v.Args[cidx], v.Args[1^cidx] 327 phi := t.Func.newValue(OpPhi, v.Type, t, v.Pos) 328 phi.AddArg2(argQ, argP) 329 t.replaceUses(v, phi) 330 for bb := range visited { 331 bb.replaceUses(v, argQ) 332 } 333 if v.Uses == 0 { 334 return 335 } 336 v.moveTo(m, i) 337 // The phi in m belongs to whichever pred idx corresponds to t. 338 if m.Preds[0].b == t { 339 v.SetArgs2(phi, argQ) 340 } else { 341 v.SetArgs2(argQ, phi) 342 } 343 } 344 } 345 } 346 347 if len(t.Preds) == 2 && len(u.Preds) == 1 { 348 if visited := u.flowsTo(t, 5); visited != nil { 349 // p q 350 // \ / 351 // b 352 // |\ 353 // | U ((sub graph that satisfy condition in flowsTo)) 354 // |/ 355 // t 356 // 357 // After the CFG modifications, this will look like 358 // 359 // q 360 // / 361 // b 362 // |\ 363 // p | U 364 // \|/ 365 // t 366 // 367 // NB: t.Preds is (b or U, b or U, p). 368 return func(v *Value, i int) { 369 // Replace any uses of v in U. Then move v to t. 370 argP, argQ := v.Args[cidx], v.Args[1^cidx] 371 for bb := range visited { 372 bb.replaceUses(v, argQ) 373 } 374 v.moveTo(t, i) 375 v.SetArgs3(argQ, argQ, argP) 376 } 377 } 378 } 379 380 if len(u.Preds) == 2 && len(t.Preds) == 1 && len(t.Succs) == 1 && t.Succs[0].b == u { 381 // p q 382 // \ / 383 // b 384 // /| 385 // t | 386 // \| 387 // u 388 // 389 // After the CFG modifications, this will look like 390 // 391 // p q 392 // | / 393 // | b 394 // |/| 395 // t | 396 // \| 397 // u 398 // 399 // NB: t.Preds is (b, p), not (p, b). 400 return func(v *Value, i int) { 401 // Replace any uses of v in t. Then move v to u. 402 argP, argQ := v.Args[cidx], v.Args[1^cidx] 403 phi := t.Func.newValue(OpPhi, v.Type, t, v.Pos) 404 phi.AddArg2(argQ, argP) 405 t.replaceUses(v, phi) 406 if v.Uses == 0 { 407 return 408 } 409 v.moveTo(u, i) 410 v.SetArgs2(argQ, phi) 411 } 412 } 413 414 // Look for some common CFG structures 415 // in which one outbound path from b exits, 416 // with no other preds joining. 417 // In these cases, we can reconstruct what the value 418 // of any phi in b must be in the path leading to exit, 419 // and move the phi to the non-exit path. 420 421 if len(t.Preds) == 1 && len(u.Preds) == 1 && len(t.Succs) == 0 { 422 // p q 423 // \ / 424 // b 425 // / \ 426 // t u 427 // 428 // where t is an Exit/Ret block. 429 // 430 // After the CFG modifications, this will look like 431 // 432 // p q 433 // | / 434 // | b 435 // |/ \ 436 // t u 437 // 438 // NB: t.Preds is (b, p), not (p, b). 439 return func(v *Value, i int) { 440 // Replace any uses of v in t and x. Then move v to u. 441 argP, argQ := v.Args[cidx], v.Args[1^cidx] 442 // If there are no uses of v in t or x, this phi will be unused. 443 // That's OK; it's not worth the cost to prevent that. 444 phi := t.Func.newValue(OpPhi, v.Type, t, v.Pos) 445 phi.AddArg2(argQ, argP) 446 t.replaceUses(v, phi) 447 if v.Uses == 0 { 448 return 449 } 450 v.moveTo(u, i) 451 v.SetArgs1(argQ) 452 } 453 } 454 455 if len(u.Preds) == 1 && len(t.Preds) == 1 && len(u.Succs) == 0 { 456 // p q 457 // \ / 458 // b 459 // / \ 460 // t u 461 // 462 // where u is an Exit/Ret block. 463 // 464 // After the CFG modifications, this will look like 465 // 466 // p q 467 // | / 468 // | b 469 // |/ \ 470 // t u 471 // 472 // NB: t.Preds is (b, p), not (p, b). 473 return func(v *Value, i int) { 474 // Replace any uses of v in u (and x). Then move v to t. 475 argP, argQ := v.Args[cidx], v.Args[1^cidx] 476 u.replaceUses(v, argQ) 477 v.moveTo(t, i) 478 v.SetArgs2(argQ, argP) 479 } 480 } 481 482 // TODO: handle more cases; shortcircuit optimizations turn out to be reasonably high impact 483 return nil 484 } 485 486 // replaceUses replaces all uses of old in b with new. 487 func (b *Block) replaceUses(old, new *Value) { 488 for _, v := range b.Values { 489 for i, a := range v.Args { 490 if a == old { 491 v.SetArg(i, new) 492 } 493 } 494 } 495 for i, v := range b.ControlValues() { 496 if v == old { 497 b.ReplaceControl(i, new) 498 } 499 } 500 } 501 502 // moveTo moves v to dst, adjusting the appropriate Block.Values slices. 503 // The caller is responsible for ensuring that this is safe. 504 // i is the index of v in v.Block.Values. 505 func (v *Value) moveTo(dst *Block, i int) { 506 if dst.Func.scheduled { 507 v.Fatalf("moveTo after scheduling") 508 } 509 src := v.Block 510 if src.Values[i] != v { 511 v.Fatalf("moveTo bad index %d", v, i) 512 } 513 if src == dst { 514 return 515 } 516 v.Block = dst 517 dst.Values = append(dst.Values, v) 518 last := len(src.Values) - 1 519 src.Values[i] = src.Values[last] 520 src.Values[last] = nil 521 src.Values = src.Values[:last] 522 } 523 524 // flowsTo checks that the subgraph starting from v and ends at t is a DAG, with 525 // the following constraints: 526 // 527 // (1) v can reach t. 528 // (2) v's connected component removing the paths containing t is a DAG. 529 // (3) The blocks in the subgraph G defined in (2) has all their preds also in G, 530 // except v. 531 // (4) The subgraph defined in (2) has a size smaller than cap. 532 // 533 // We know that the subgraph G defined in constraint (2)(3) has the property that v 534 // dominates all the blocks in G: 535 // If there exist a block x in G that is not dominated by v, then there exist a 536 // path P from entry to x that does not contain v. Denote x's predecessor in P 537 // as x', then x' must also be in G given constraint (3), same to its pred x'' 538 // in P. Given constraint (2), by going back in P we will in the end reach v, 539 // which conflicts with the definition of P. 540 // 541 // Constraint (2)'s DAG requirement could be further relaxed to contain "internal" 542 // loops that doesn't change the dominance relation of v. But that is more subtle 543 // and requires another constraint on the source block v, and a more complex proof. 544 // Furthermore optimizing the branch guarding a loop might bring less gains as the 545 // loop itself might be the bottleneck. 546 func (v *Block) flowsTo(t *Block, cap int) map[*Block]struct{} { 547 seen := map[*Block]struct{}{} 548 var boundedDFS func(b *Block) 549 hasPathToT := false 550 fullyExplored := true 551 isDAG := true 552 visited := map[*Block]struct{}{} 553 boundedDFS = func(b *Block) { 554 if _, ok := seen[b]; ok { 555 return 556 } 557 if _, ok := visited[b]; ok { 558 isDAG = false 559 return 560 } 561 if b == t { 562 // do not put t into seen, this way 563 // if v can reach t's connected component without going through t, 564 // it will fail the pred check after boundedDFSUntil. 565 hasPathToT = true 566 return 567 } 568 if len(seen) > cap { 569 fullyExplored = false 570 return 571 } 572 seen[b] = struct{}{} 573 visited[b] = struct{}{} 574 for _, se := range b.Succs { 575 boundedDFS(se.b) 576 if !(isDAG && fullyExplored) { 577 return 578 } 579 } 580 delete(visited, b) 581 } 582 boundedDFS(v) 583 if hasPathToT && fullyExplored && isDAG { 584 for b := range seen { 585 if b != v { 586 for _, se := range b.Preds { 587 if _, ok := seen[se.b]; !ok { 588 return nil 589 } 590 } 591 } 592 } 593 return seen 594 } 595 return nil 596 } 597