| // Copyright 2015 The Go Authors. All rights reserved. |
| // Use of this source code is governed by a BSD-style |
| // license that can be found in the LICENSE file. |
| |
| package ssa |
| |
| import "log" |
| |
| // deadcode removes dead code from f. |
| func deadcode(f *Func) { |
| |
| // Find all reachable basic blocks. |
| reachable := make([]bool, f.NumBlocks()) |
| reachable[f.Entry.ID] = true |
| p := []*Block{f.Entry} // stack-like worklist |
| for len(p) > 0 { |
| // pop a reachable block |
| b := p[len(p)-1] |
| p = p[:len(p)-1] |
| |
| // constant-fold conditionals |
| // TODO: rewrite rules instead? |
| if b.Kind == BlockIf && b.Control.Op == OpConst { |
| cond := b.Control.Aux.(bool) |
| var c *Block |
| if cond { |
| // then branch is always taken |
| c = b.Succs[1] |
| } else { |
| // else branch is always taken |
| c = b.Succs[0] |
| b.Succs[0] = b.Succs[1] |
| } |
| b.Succs[1] = nil // aid GC |
| b.Succs = b.Succs[:1] |
| removePredecessor(b, c) |
| b.Kind = BlockPlain |
| b.Control = nil |
| } |
| |
| for _, c := range b.Succs { |
| if !reachable[c.ID] { |
| reachable[c.ID] = true |
| p = append(p, c) // push |
| } |
| } |
| } |
| |
| // Find all live values |
| live := make([]bool, f.NumValues()) // flag to set for each live value |
| var q []*Value // stack-like worklist of unscanned values |
| |
| // Starting set: all control values of reachable blocks are live. |
| for _, b := range f.Blocks { |
| if !reachable[b.ID] { |
| continue |
| } |
| if v := b.Control; v != nil && !live[v.ID] { |
| live[v.ID] = true |
| q = append(q, v) |
| } |
| } |
| |
| // Compute transitive closure of live values. |
| for len(q) > 0 { |
| // pop a reachable value |
| v := q[len(q)-1] |
| q = q[:len(q)-1] |
| for _, x := range v.Args { |
| if !live[x.ID] { |
| live[x.ID] = true |
| q = append(q, x) // push |
| } |
| } |
| } |
| |
| // Remove dead values from blocks' value list. Return dead |
| // value ids to the allocator. |
| for _, b := range f.Blocks { |
| i := 0 |
| for _, v := range b.Values { |
| if live[v.ID] { |
| b.Values[i] = v |
| i++ |
| } else { |
| f.vid.put(v.ID) |
| } |
| } |
| // aid GC |
| tail := b.Values[i:] |
| for j := range tail { |
| tail[j] = nil |
| } |
| b.Values = b.Values[:i] |
| } |
| |
| // Remove unreachable blocks. Return dead block ids to allocator. |
| i := 0 |
| for _, b := range f.Blocks { |
| if reachable[b.ID] { |
| f.Blocks[i] = b |
| i++ |
| } else { |
| if len(b.Values) > 0 { |
| panic("live value in unreachable block") |
| } |
| f.bid.put(b.ID) |
| } |
| } |
| // zero remainder to help GC |
| tail := f.Blocks[i:] |
| for j := range tail { |
| tail[j] = nil |
| } |
| f.Blocks = f.Blocks[:i] |
| |
| // TODO: renumber Blocks and Values densely? |
| // TODO: save dead Values and Blocks for reuse? Or should we just let GC handle it? |
| } |
| |
| // There was an edge b->c. It has been removed from b's successors. |
| // Fix up c to handle that fact. |
| func removePredecessor(b, c *Block) { |
| n := len(c.Preds) - 1 |
| if n == 0 { |
| // c is now dead - don't bother working on it |
| if c.Preds[0] != b { |
| log.Panicf("%s.Preds[0]==%s, want %s", c, c.Preds[0], b) |
| } |
| return |
| } |
| |
| // find index of b in c's predecessor list |
| var i int |
| for j, p := range c.Preds { |
| if p == b { |
| i = j |
| break |
| } |
| } |
| |
| c.Preds[i] = c.Preds[n] |
| c.Preds[n] = nil // aid GC |
| c.Preds = c.Preds[:n] |
| // rewrite phi ops to match the new predecessor list |
| for _, v := range c.Values { |
| if v.Op != OpPhi { |
| continue |
| } |
| v.Args[i] = v.Args[n] |
| v.Args[n] = nil // aid GC |
| v.Args = v.Args[:n] |
| if n == 1 { |
| v.Op = OpCopy |
| } |
| } |
| } |