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