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 if len(b.Values) != nval+nOtherPhi { 139 return false 140 } 141 if nOtherPhi > 0 { 142 // Check for any phi which is the argument of another phi. 143 // These cases are tricky, as substitutions done by replaceUses 144 // are no longer trivial to do in any ordering. See issue 45175. 145 m := make(map[*Value]bool, 1+nOtherPhi) 146 for _, v := range b.Values { 147 if v.Op == OpPhi { 148 m[v] = true 149 } 150 } 151 for v := range m { 152 for _, a := range v.Args { 153 if a != v && m[a] { 154 return false 155 } 156 } 157 } 158 } 159 160 // Locate index of first const phi arg. 161 cidx := -1 162 for i, a := range ctl.Args { 163 if a.Op == OpConstBool { 164 cidx = i 165 break 166 } 167 } 168 if cidx == -1 { 169 return false 170 } 171 172 // p is the predecessor corresponding to cidx. 173 pe := b.Preds[cidx] 174 p := pe.b 175 pi := pe.i 176 177 // t is the "taken" branch: the successor we always go to when coming in from p. 178 ti := 1 ^ ctl.Args[cidx].AuxInt ^ swap 179 te := b.Succs[ti] 180 t := te.b 181 if p == b || t == b { 182 // This is an infinite loop; we can't remove it. See issue 33903. 183 return false 184 } 185 186 var fixPhi func(*Value, int) 187 if nOtherPhi > 0 { 188 fixPhi = shortcircuitPhiPlan(b, ctl, cidx, ti) 189 if fixPhi == nil { 190 return false 191 } 192 } 193 194 // We're committed. Update CFG and Phis. 195 // If you modify this section, update shortcircuitPhiPlan corresponding. 196 197 // Remove b's incoming edge from p. 198 b.removePred(cidx) 199 b.removePhiArg(ctl, cidx) 200 201 // Redirect p's outgoing edge to t. 202 p.Succs[pi] = Edge{t, len(t.Preds)} 203 204 // Fix up t to have one more predecessor. 205 t.Preds = append(t.Preds, Edge{p, pi}) 206 for _, v := range t.Values { 207 if v.Op != OpPhi { 208 continue 209 } 210 v.AddArg(v.Args[te.i]) 211 } 212 213 if nOtherPhi != 0 { 214 // Adjust all other phis as necessary. 215 // Use a plain for loop instead of range because fixPhi may move phis, 216 // thus modifying b.Values. 217 for i := 0; i < len(b.Values); i++ { 218 phi := b.Values[i] 219 if phi.Uses == 0 || phi == ctl || phi.Op != OpPhi { 220 continue 221 } 222 fixPhi(phi, i) 223 if phi.Block == b { 224 continue 225 } 226 // phi got moved to a different block with v.moveTo. 227 // Adjust phi values in this new block that refer 228 // to phi to refer to the corresponding phi arg instead. 229 // phi used to be evaluated prior to this block, 230 // and now it is evaluated in this block. 231 for _, v := range phi.Block.Values { 232 if v.Op != OpPhi || v == phi { 233 continue 234 } 235 for j, a := range v.Args { 236 if a == phi { 237 v.SetArg(j, phi.Args[j]) 238 } 239 } 240 } 241 if phi.Uses != 0 { 242 phielimValue(phi) 243 } else { 244 phi.reset(OpInvalid) 245 } 246 i-- // v.moveTo put a new value at index i; reprocess 247 } 248 249 // We may have left behind some phi values with no uses 250 // but the wrong number of arguments. Eliminate those. 251 for _, v := range b.Values { 252 if v.Uses == 0 { 253 v.reset(OpInvalid) 254 } 255 } 256 } 257 258 if len(b.Preds) == 0 { 259 // Block is now dead. 260 b.Kind = BlockInvalid 261 } 262 263 phielimValue(ctl) 264 return true 265 } 266 267 // shortcircuitPhiPlan returns a function to handle non-ctl phi values in b, 268 // where b is as described in shortcircuitBlock. 269 // The returned function accepts a value v 270 // and the index i of v in v.Block: v.Block.Values[i] == v. 271 // If the returned function moves v to a different block, it will use v.moveTo. 272 // cidx is the index in ctl of the ConstBool arg. 273 // ti is the index in b.Succs of the always taken branch when arriving from p. 274 // If shortcircuitPhiPlan returns nil, there is no plan available, 275 // and the CFG modifications must not proceed. 276 // The returned function assumes that shortcircuitBlock has completed its CFG modifications. 277 func shortcircuitPhiPlan(b *Block, ctl *Value, cidx int, ti int64) func(*Value, int) { 278 // t is the "taken" branch: the successor we always go to when coming in from p. 279 t := b.Succs[ti].b 280 // u is the "untaken" branch: the successor we never go to when coming in from p. 281 u := b.Succs[1^ti].b 282 283 // In the following CFG matching, ensure that b's preds are entirely distinct from b's succs. 284 // This is probably a stronger condition than required, but this happens extremely rarely, 285 // and it makes it easier to avoid getting deceived by pretty ASCII charts. See #44465. 286 if p0, p1 := b.Preds[0].b, b.Preds[1].b; p0 == t || p1 == t || p0 == u || p1 == u { 287 return nil 288 } 289 290 // Look for some common CFG structures 291 // in which the outbound paths from b merge, 292 // with no other preds joining them. 293 // In these cases, we can reconstruct what the value 294 // of any phi in b must be in the successor blocks. 295 296 if len(t.Preds) == 1 && len(t.Succs) == 1 && 297 len(u.Preds) == 1 && len(u.Succs) == 1 && 298 t.Succs[0].b == u.Succs[0].b && len(t.Succs[0].b.Preds) == 2 { 299 // p q 300 // \ / 301 // b 302 // / \ 303 // t u 304 // \ / 305 // m 306 // 307 // After the CFG modifications, this will look like 308 // 309 // p q 310 // | / 311 // | b 312 // |/ \ 313 // t u 314 // \ / 315 // m 316 // 317 // NB: t.Preds is (b, p), not (p, b). 318 m := t.Succs[0].b 319 return func(v *Value, i int) { 320 // Replace any uses of v in t and u with the value v must have, 321 // given that we have arrived at that block. 322 // Then move v to m and adjust its value accordingly; 323 // this handles all other uses of v. 324 argP, argQ := v.Args[cidx], v.Args[1^cidx] 325 u.replaceUses(v, argQ) 326 phi := t.Func.newValue(OpPhi, v.Type, t, v.Pos) 327 phi.AddArg2(argQ, argP) 328 t.replaceUses(v, phi) 329 if v.Uses == 0 { 330 return 331 } 332 v.moveTo(m, i) 333 // The phi in m belongs to whichever pred idx corresponds to t. 334 if m.Preds[0].b == t { 335 v.SetArgs2(phi, argQ) 336 } else { 337 v.SetArgs2(argQ, phi) 338 } 339 } 340 } 341 342 if len(t.Preds) == 2 && len(u.Preds) == 1 && len(u.Succs) == 1 && u.Succs[0].b == t { 343 // p q 344 // \ / 345 // b 346 // |\ 347 // | u 348 // |/ 349 // t 350 // 351 // After the CFG modifications, this will look like 352 // 353 // q 354 // / 355 // b 356 // |\ 357 // p | u 358 // \|/ 359 // t 360 // 361 // NB: t.Preds is (b or u, b or u, p). 362 return func(v *Value, i int) { 363 // Replace any uses of v in u. Then move v to t. 364 argP, argQ := v.Args[cidx], v.Args[1^cidx] 365 u.replaceUses(v, argQ) 366 v.moveTo(t, i) 367 v.SetArgs3(argQ, argQ, argP) 368 } 369 } 370 371 if len(u.Preds) == 2 && len(t.Preds) == 1 && len(t.Succs) == 1 && t.Succs[0].b == u { 372 // p q 373 // \ / 374 // b 375 // /| 376 // t | 377 // \| 378 // u 379 // 380 // After the CFG modifications, this will look like 381 // 382 // p q 383 // | / 384 // | b 385 // |/| 386 // t | 387 // \| 388 // u 389 // 390 // NB: t.Preds is (b, p), not (p, b). 391 return func(v *Value, i int) { 392 // Replace any uses of v in t. Then move v to u. 393 argP, argQ := v.Args[cidx], v.Args[1^cidx] 394 phi := t.Func.newValue(OpPhi, v.Type, t, v.Pos) 395 phi.AddArg2(argQ, argP) 396 t.replaceUses(v, phi) 397 if v.Uses == 0 { 398 return 399 } 400 v.moveTo(u, i) 401 v.SetArgs2(argQ, phi) 402 } 403 } 404 405 // Look for some common CFG structures 406 // in which one outbound path from b exits, 407 // with no other preds joining. 408 // In these cases, we can reconstruct what the value 409 // of any phi in b must be in the path leading to exit, 410 // and move the phi to the non-exit path. 411 412 if len(t.Preds) == 1 && len(u.Preds) == 1 && len(t.Succs) == 0 { 413 // p q 414 // \ / 415 // b 416 // / \ 417 // t u 418 // 419 // where t is an Exit/Ret block. 420 // 421 // After the CFG modifications, this will look like 422 // 423 // p q 424 // | / 425 // | b 426 // |/ \ 427 // t u 428 // 429 // NB: t.Preds is (b, p), not (p, b). 430 return func(v *Value, i int) { 431 // Replace any uses of v in t and x. Then move v to u. 432 argP, argQ := v.Args[cidx], v.Args[1^cidx] 433 // If there are no uses of v in t or x, this phi will be unused. 434 // That's OK; it's not worth the cost to prevent that. 435 phi := t.Func.newValue(OpPhi, v.Type, t, v.Pos) 436 phi.AddArg2(argQ, argP) 437 t.replaceUses(v, phi) 438 if v.Uses == 0 { 439 return 440 } 441 v.moveTo(u, i) 442 v.SetArgs1(argQ) 443 } 444 } 445 446 if len(u.Preds) == 1 && len(t.Preds) == 1 && len(u.Succs) == 0 { 447 // p q 448 // \ / 449 // b 450 // / \ 451 // t u 452 // 453 // where u is an Exit/Ret block. 454 // 455 // After the CFG modifications, this will look like 456 // 457 // p q 458 // | / 459 // | b 460 // |/ \ 461 // t u 462 // 463 // NB: t.Preds is (b, p), not (p, b). 464 return func(v *Value, i int) { 465 // Replace any uses of v in u (and x). Then move v to t. 466 argP, argQ := v.Args[cidx], v.Args[1^cidx] 467 u.replaceUses(v, argQ) 468 v.moveTo(t, i) 469 v.SetArgs2(argQ, argP) 470 } 471 } 472 473 // TODO: handle more cases; shortcircuit optimizations turn out to be reasonably high impact 474 return nil 475 } 476 477 // replaceUses replaces all uses of old in b with new. 478 func (b *Block) replaceUses(old, new *Value) { 479 for _, v := range b.Values { 480 for i, a := range v.Args { 481 if a == old { 482 v.SetArg(i, new) 483 } 484 } 485 } 486 for i, v := range b.ControlValues() { 487 if v == old { 488 b.ReplaceControl(i, new) 489 } 490 } 491 } 492 493 // moveTo moves v to dst, adjusting the appropriate Block.Values slices. 494 // The caller is responsible for ensuring that this is safe. 495 // i is the index of v in v.Block.Values. 496 func (v *Value) moveTo(dst *Block, i int) { 497 if dst.Func.scheduled { 498 v.Fatalf("moveTo after scheduling") 499 } 500 src := v.Block 501 if src.Values[i] != v { 502 v.Fatalf("moveTo bad index %d", v, i) 503 } 504 if src == dst { 505 return 506 } 507 v.Block = dst 508 dst.Values = append(dst.Values, v) 509 last := len(src.Values) - 1 510 src.Values[i] = src.Values[last] 511 src.Values[last] = nil 512 src.Values = src.Values[:last] 513 } 514