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 // findlive returns the reachable blocks and live values in f. 8 func findlive(f *Func) (reachable []bool, live []bool) { 9 reachable = reachableBlocks(f) 10 live = liveValues(f, reachable) 11 return 12 } 13 14 // reachableBlocks returns the reachable blocks in f. 15 func reachableBlocks(f *Func) []bool { 16 reachable := make([]bool, f.NumBlocks()) 17 reachable[f.Entry.ID] = true 18 p := []*Block{f.Entry} // stack-like worklist 19 for len(p) > 0 { 20 // Pop a reachable block 21 b := p[len(p)-1] 22 p = p[:len(p)-1] 23 // Mark successors as reachable 24 s := b.Succs 25 if b.Kind == BlockFirst { 26 s = s[:1] 27 } 28 for _, e := range s { 29 c := e.b 30 if !reachable[c.ID] { 31 reachable[c.ID] = true 32 p = append(p, c) // push 33 } 34 } 35 } 36 return reachable 37 } 38 39 // liveValues returns the live values in f. 40 // reachable is a map from block ID to whether the block is reachable. 41 func liveValues(f *Func, reachable []bool) []bool { 42 live := make([]bool, f.NumValues()) 43 44 // After regalloc, consider all values to be live. 45 // See the comment at the top of regalloc.go and in deadcode for details. 46 if f.RegAlloc != nil { 47 for i := range live { 48 live[i] = true 49 } 50 return live 51 } 52 53 // Find all live values 54 var q []*Value // stack-like worklist of unscanned values 55 56 // Starting set: all control values of reachable blocks are live. 57 // Calls are live (because callee can observe the memory state). 58 for _, b := range f.Blocks { 59 if !reachable[b.ID] { 60 continue 61 } 62 if v := b.Control; v != nil && !live[v.ID] { 63 live[v.ID] = true 64 q = append(q, v) 65 } 66 for _, v := range b.Values { 67 if opcodeTable[v.Op].call && !live[v.ID] { 68 live[v.ID] = true 69 q = append(q, v) 70 } 71 if v.Type.IsVoid() && !live[v.ID] { 72 // The only Void ops are nil checks. We must keep these. 73 live[v.ID] = true 74 q = append(q, v) 75 } 76 } 77 } 78 79 // Compute transitive closure of live values. 80 for len(q) > 0 { 81 // pop a reachable value 82 v := q[len(q)-1] 83 q = q[:len(q)-1] 84 for i, x := range v.Args { 85 if v.Op == OpPhi && !reachable[v.Block.Preds[i].b.ID] { 86 continue 87 } 88 if !live[x.ID] { 89 live[x.ID] = true 90 q = append(q, x) // push 91 } 92 } 93 } 94 95 return live 96 } 97 98 // deadcode removes dead code from f. 99 func deadcode(f *Func) { 100 // deadcode after regalloc is forbidden for now. Regalloc 101 // doesn't quite generate legal SSA which will lead to some 102 // required moves being eliminated. See the comment at the 103 // top of regalloc.go for details. 104 if f.RegAlloc != nil { 105 f.Fatalf("deadcode after regalloc") 106 } 107 108 // Find reachable blocks. 109 reachable := reachableBlocks(f) 110 111 // Get rid of edges from dead to live code. 112 for _, b := range f.Blocks { 113 if reachable[b.ID] { 114 continue 115 } 116 for i := 0; i < len(b.Succs); { 117 e := b.Succs[i] 118 if reachable[e.b.ID] { 119 b.removeEdge(i) 120 } else { 121 i++ 122 } 123 } 124 } 125 126 // Get rid of dead edges from live code. 127 for _, b := range f.Blocks { 128 if !reachable[b.ID] { 129 continue 130 } 131 if b.Kind != BlockFirst { 132 continue 133 } 134 b.removeEdge(1) 135 b.Kind = BlockPlain 136 b.Likely = BranchUnknown 137 } 138 139 // Splice out any copies introduced during dead block removal. 140 copyelim(f) 141 142 // Find live values. 143 live := liveValues(f, reachable) 144 145 // Remove dead & duplicate entries from namedValues map. 146 s := f.newSparseSet(f.NumValues()) 147 defer f.retSparseSet(s) 148 i := 0 149 for _, name := range f.Names { 150 j := 0 151 s.clear() 152 values := f.NamedValues[name] 153 for _, v := range values { 154 if live[v.ID] && !s.contains(v.ID) { 155 values[j] = v 156 j++ 157 s.add(v.ID) 158 } 159 } 160 if j == 0 { 161 delete(f.NamedValues, name) 162 } else { 163 f.Names[i] = name 164 i++ 165 for k := len(values) - 1; k >= j; k-- { 166 values[k] = nil 167 } 168 f.NamedValues[name] = values[:j] 169 } 170 } 171 for k := len(f.Names) - 1; k >= i; k-- { 172 f.Names[k] = LocalSlot{} 173 } 174 f.Names = f.Names[:i] 175 176 // Unlink values. 177 for _, b := range f.Blocks { 178 if !reachable[b.ID] { 179 b.SetControl(nil) 180 } 181 for _, v := range b.Values { 182 if !live[v.ID] { 183 v.resetArgs() 184 } 185 } 186 } 187 188 // Remove dead values from blocks' value list. Return dead 189 // values to the allocator. 190 for _, b := range f.Blocks { 191 i := 0 192 for _, v := range b.Values { 193 if live[v.ID] { 194 b.Values[i] = v 195 i++ 196 } else { 197 f.freeValue(v) 198 } 199 } 200 // aid GC 201 tail := b.Values[i:] 202 for j := range tail { 203 tail[j] = nil 204 } 205 b.Values = b.Values[:i] 206 } 207 208 // Remove unreachable blocks. Return dead blocks to allocator. 209 i = 0 210 for _, b := range f.Blocks { 211 if reachable[b.ID] { 212 f.Blocks[i] = b 213 i++ 214 } else { 215 if len(b.Values) > 0 { 216 b.Fatalf("live values in unreachable block %v: %v", b, b.Values) 217 } 218 f.freeBlock(b) 219 } 220 } 221 // zero remainder to help GC 222 tail := f.Blocks[i:] 223 for j := range tail { 224 tail[j] = nil 225 } 226 f.Blocks = f.Blocks[:i] 227 } 228 229 // removeEdge removes the i'th outgoing edge from b (and 230 // the corresponding incoming edge from b.Succs[i].b). 231 func (b *Block) removeEdge(i int) { 232 e := b.Succs[i] 233 c := e.b 234 j := e.i 235 236 // Adjust b.Succs 237 b.removeSucc(i) 238 239 // Adjust c.Preds 240 c.removePred(j) 241 242 // Remove phi args from c's phis. 243 n := len(c.Preds) 244 for _, v := range c.Values { 245 if v.Op != OpPhi { 246 continue 247 } 248 v.Args[j].Uses-- 249 v.Args[j] = v.Args[n] 250 v.Args[n] = nil 251 v.Args = v.Args[:n] 252 phielimValue(v) 253 // Note: this is trickier than it looks. Replacing 254 // a Phi with a Copy can in general cause problems because 255 // Phi and Copy don't have exactly the same semantics. 256 // Phi arguments always come from a predecessor block, 257 // whereas copies don't. This matters in loops like: 258 // 1: x = (Phi y) 259 // y = (Add x 1) 260 // goto 1 261 // If we replace Phi->Copy, we get 262 // 1: x = (Copy y) 263 // y = (Add x 1) 264 // goto 1 265 // (Phi y) refers to the *previous* value of y, whereas 266 // (Copy y) refers to the *current* value of y. 267 // The modified code has a cycle and the scheduler 268 // will barf on it. 269 // 270 // Fortunately, this situation can only happen for dead 271 // code loops. We know the code we're working with is 272 // not dead, so we're ok. 273 // Proof: If we have a potential bad cycle, we have a 274 // situation like this: 275 // x = (Phi z) 276 // y = (op1 x ...) 277 // z = (op2 y ...) 278 // Where opX are not Phi ops. But such a situation 279 // implies a cycle in the dominator graph. In the 280 // example, x.Block dominates y.Block, y.Block dominates 281 // z.Block, and z.Block dominates x.Block (treating 282 // "dominates" as reflexive). Cycles in the dominator 283 // graph can only happen in an unreachable cycle. 284 } 285 } 286