1 // Copyright 2015 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 // combine copyelim and phielim into a single pass. 8 // copyelim removes all uses of OpCopy values from f. 9 // A subsequent deadcode pass is needed to actually remove the copies. 10 func copyelim(f *Func) { 11 phielim(f) 12 13 // loop of copyelimValue(v) process has been done in phielim() pass. 14 // Update block control values. 15 for _, b := range f.Blocks { 16 for i, v := range b.ControlValues() { 17 if v.Op == OpCopy { 18 b.ReplaceControl(i, v.Args[0]) 19 } 20 } 21 } 22 23 // Update named values. 24 for _, name := range f.Names { 25 values := f.NamedValues[*name] 26 for i, v := range values { 27 if v.Op == OpCopy { 28 values[i] = v.Args[0] 29 } 30 } 31 } 32 } 33 34 // copySource returns the (non-copy) op which is the 35 // ultimate source of v. v must be a copy op. 36 func copySource(v *Value) *Value { 37 w := v.Args[0] 38 39 // This loop is just: 40 // for w.Op == OpCopy { 41 // w = w.Args[0] 42 // } 43 // but we take some extra care to make sure we 44 // don't get stuck in an infinite loop. 45 // Infinite copy loops may happen in unreachable code. 46 // (TODO: or can they? Needs a test.) 47 slow := w 48 var advance bool 49 for w.Op == OpCopy { 50 w = w.Args[0] 51 if w == slow { 52 w.reset(OpUnknown) 53 break 54 } 55 if advance { 56 slow = slow.Args[0] 57 } 58 advance = !advance 59 } 60 61 // The answer is w. Update all the copies we saw 62 // to point directly to w. Doing this update makes 63 // sure that we don't end up doing O(n^2) work 64 // for a chain of n copies. 65 for v != w { 66 x := v.Args[0] 67 v.SetArg(0, w) 68 v = x 69 } 70 return w 71 } 72 73 // copyelimValue ensures that no args of v are copies. 74 func copyelimValue(v *Value) { 75 for i, a := range v.Args { 76 if a.Op == OpCopy { 77 v.SetArg(i, copySource(a)) 78 } 79 } 80 } 81 82 // phielim eliminates redundant phi values from f. 83 // A phi is redundant if its arguments are all equal. For 84 // purposes of counting, ignore the phi itself. Both of 85 // these phis are redundant: 86 // 87 // v = phi(x,x,x) 88 // v = phi(x,v,x,v) 89 // 90 // We repeat this process to also catch situations like: 91 // 92 // v = phi(x, phi(x, x), phi(x, v)) 93 // 94 // TODO: Can we also simplify cases like: 95 // 96 // v = phi(v, w, x) 97 // w = phi(v, w, x) 98 // 99 // and would that be useful? 100 func phielim(f *Func) { 101 for { 102 change := false 103 for _, b := range f.Blocks { 104 for _, v := range b.Values { 105 // This is an early place in SSA where all values are examined. 106 // Rewrite all 0-sized Go values to remove accessors, dereferences, loads, etc. 107 if t := v.Type; (t.IsStruct() || t.IsArray()) && t.Size() == 0 { 108 if t.IsStruct() { 109 v.reset(OpStructMake0) 110 } else { 111 v.reset(OpArrayMake0) 112 } 113 } 114 // Modify all values so no arg (including args 115 // of OpCopy) is a copy. 116 copyelimValue(v) 117 change = phielimValue(v) || change 118 } 119 } 120 if !change { 121 break 122 } 123 } 124 } 125 126 // phielimValue tries to convert the phi v to a copy. 127 func phielimValue(v *Value) bool { 128 if v.Op != OpPhi { 129 return false 130 } 131 132 // If there are two distinct args of v which 133 // are not v itself, then the phi must remain. 134 // Otherwise, we can replace it with a copy. 135 var w *Value 136 for _, x := range v.Args { 137 if x == v { 138 continue 139 } 140 if x == w { 141 continue 142 } 143 if w != nil { 144 return false 145 } 146 w = x 147 } 148 149 if w == nil { 150 // v references only itself. It must be in 151 // a dead code loop. Don't bother modifying it. 152 return false 153 } 154 v.Op = OpCopy 155 v.SetArgs1(w) 156 f := v.Block.Func 157 if f.pass.debug > 0 { 158 f.Warnl(v.Pos, "eliminated phi") 159 } 160 return true 161 } 162