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.Control != 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: Compute which values are live across blocks. 54 live := make([]bool, f.NumValues()) 55 for _, b := range f.Blocks { 56 for _, v := range b.Values { 57 for _, a := range v.Args { 58 if a.Block != v.Block { 59 live[a.ID] = true 60 } 61 } 62 } 63 if b.Control != nil && b.Control.Block != b { 64 live[b.Control.ID] = true 65 } 66 } 67 68 // Step 3: Redirect control flow around known branches. 69 // p: 70 // ... goto b ... 71 // b: <- p ... 72 // v = phi(true, ...) 73 // if v goto t else u 74 // We can redirect p to go directly to t instead of b. 75 // (If v is not live after b). 76 for _, b := range f.Blocks { 77 if b.Kind != BlockIf { 78 continue 79 } 80 if len(b.Values) != 1 { 81 continue 82 } 83 v := b.Values[0] 84 if v.Op != OpPhi { 85 continue 86 } 87 if b.Control != v { 88 continue 89 } 90 if live[v.ID] { 91 continue 92 } 93 for i := 0; i < len(v.Args); i++ { 94 a := v.Args[i] 95 if a.Op != OpConstBool { 96 continue 97 } 98 99 // The predecessor we come in from. 100 e1 := b.Preds[i] 101 p := e1.b 102 pi := e1.i 103 104 // The successor we always go to when coming in 105 // from that predecessor. 106 e2 := b.Succs[1-a.AuxInt] 107 t := e2.b 108 ti := e2.i 109 110 // Remove b's incoming edge from p. 111 b.removePred(i) 112 n := len(b.Preds) 113 v.Args[i].Uses-- 114 v.Args[i] = v.Args[n] 115 v.Args[n] = nil 116 v.Args = v.Args[:n] 117 118 // Redirect p's outgoing edge to t. 119 p.Succs[pi] = Edge{t, len(t.Preds)} 120 121 // Fix up t to have one more predecessor. 122 t.Preds = append(t.Preds, Edge{p, pi}) 123 for _, w := range t.Values { 124 if w.Op != OpPhi { 125 continue 126 } 127 w.AddArg(w.Args[ti]) 128 } 129 130 if len(b.Preds) == 1 { 131 v.Op = OpCopy 132 // No longer a phi, stop optimizing here. 133 break 134 } 135 i-- 136 } 137 } 138 } 139
View as plain text