diff options
author | Keith Randall <khr@golang.org> | 2015-05-28 13:49:20 -0700 |
---|---|---|
committer | Keith Randall <khr@golang.org> | 2015-05-28 13:51:18 -0700 |
commit | 067e8dfd82163ddcbde248dbe5a1187a417e5d36 (patch) | |
tree | 7bfb46b901d03498c7739c92bec21d81d3a2c485 /src/cmd/compile/internal/ssa/deadcode.go | |
parent | 247786c1745abc0c7185f7c15ca256edf68ed6d6 (diff) | |
parent | ccc037699e2966b7c79ba84c67471cef5e67a3b8 (diff) | |
download | go-067e8dfd82163ddcbde248dbe5a1187a417e5d36.tar.gz go-067e8dfd82163ddcbde248dbe5a1187a417e5d36.zip |
[dev.ssa] Merge remote-tracking branch 'origin/master' into mergebranch
Semi-regular merge of tip to dev.ssa.
Complicated a bit by the move of cmd/internal/* to cmd/compile/internal/*.
Change-Id: I1c66d3c29bb95cce4a53c5a3476373aa5245303d
Diffstat (limited to 'src/cmd/compile/internal/ssa/deadcode.go')
-rw-r--r-- | src/cmd/compile/internal/ssa/deadcode.go | 157 |
1 files changed, 157 insertions, 0 deletions
diff --git a/src/cmd/compile/internal/ssa/deadcode.go b/src/cmd/compile/internal/ssa/deadcode.go new file mode 100644 index 0000000000..a805861489 --- /dev/null +++ b/src/cmd/compile/internal/ssa/deadcode.go @@ -0,0 +1,157 @@ +// 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 + } + } +} |