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