1 files changed, 158 insertions, 0 deletions
diff --git a/src/cmd/compile/internal/ssa/fuse.go b/src/cmd/compile/internal/ssa/fuse.go
new file mode 100644
index 0000000000..3f81e452b6
--- /dev/null
+++ b/src/cmd/compile/internal/ssa/fuse.go
@@ -0,0 +1,158 @@
+// 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
+
+// fuse simplifies control flow by joining basic blocks.
+func fuse(f *Func) {
+	for changed := true; changed; {
+		changed = false
+		for _, b := range f.Blocks {
+			changed = fuseBlockIf(b) || changed
+			changed = fuseBlockPlain(b) || changed
+		}
+	}
+}
+
+// fuseBlockIf handles the following cases where s0 and s1 are empty blocks.
+//
+//   b        b        b      b
+//  / \      | \      / |    | |
+// s0  s1    |  s1   s0 |    | |
+//  \ /      | /      \ |    | |
+//   ss      ss        ss     ss
+//
+// If all Phi ops in ss have identical variables for slots corresponding to
+// s0, s1 and b then the branch can be dropped.
+// TODO: If ss doesn't contain any OpPhis, are s0 and s1 dead code anyway.
+func fuseBlockIf(b *Block) bool {
+	if b.Kind != BlockIf {
+		return false
+	}
+
+	var ss0, ss1 *Block
+	s0 := b.Succs[0]
+	if s0.Kind != BlockPlain || len(s0.Preds) != 1 || len(s0.Values) != 0 {
+		s0, ss0 = b, s0
+	} else {
+		ss0 = s0.Succs[0]
+	}
+	s1 := b.Succs[1]
+	if s1.Kind != BlockPlain || len(s1.Preds) != 1 || len(s1.Values) != 0 {
+		s1, ss1 = b, s1
+	} else {
+		ss1 = s1.Succs[0]
+	}
+
+	if ss0 != ss1 {
+		return false
+	}
+	ss := ss0
+
+	// s0 and s1 are equal with b if the corresponding block is missing
+	// (2nd, 3rd and 4th case in the figure).
+	i0, i1 := -1, -1
+	for i, p := range ss.Preds {
+		if p == s0 {
+			i0 = i
+		}
+		if p == s1 {
+			i1 = i
+		}
+	}
+	if i0 == -1 || i1 == -1 {
+		b.Fatalf("invalid predecessors")
+	}
+	for _, v := range ss.Values {
+		if v.Op == OpPhi && v.Args[i0] != v.Args[i1] {
+			return false
+		}
+	}
+
+	// Now we have two of following b->ss, b->s0->ss and b->s1->ss,
+	// with s0 and s1 empty if exist.
+	// We can replace it with b->ss without if all OpPhis in ss
+	// have identical predecessors (verified above).
+	// No critical edge is introduced because b will have one successor.
+	if s0 != b && s1 != b {
+		ss.removePred(s0)
+
+		// Replace edge b->s1->ss with b->ss.
+		// We need to keep a slot for Phis corresponding to b.
+		for i := range b.Succs {
+			if b.Succs[i] == s1 {
+				b.Succs[i] = ss
+			}
+		}
+		for i := range ss.Preds {
+			if ss.Preds[i] == s1 {
+				ss.Preds[i] = b
+			}
+		}
+	} else if s0 != b {
+		ss.removePred(s0)
+	} else if s1 != b {
+		ss.removePred(s1)
+	}
+	b.Kind = BlockPlain
+	b.Control = nil
+	b.Succs = append(b.Succs[:0], ss)
+
+	// Trash the empty blocks s0 & s1.
+	if s0 != b {
+		s0.Kind = BlockInvalid
+		s0.Values = nil
+		s0.Succs = nil
+		s0.Preds = nil
+	}
+	if s1 != b {
+		s1.Kind = BlockInvalid
+		s1.Values = nil
+		s1.Succs = nil
+		s1.Preds = nil
+	}
+	return true
+}
+
+func fuseBlockPlain(b *Block) bool {
+	if b.Kind != BlockPlain {
+		return false
+	}
+
+	c := b.Succs[0]
+	if len(c.Preds) != 1 {
+		return false
+	}
+
+	// move all of b'c values to c.
+	for _, v := range b.Values {
+		v.Block = c
+		c.Values = append(c.Values, v)
+	}
+
+	// replace b->c edge with preds(b) -> c
+	c.predstorage[0] = nil
+	if len(b.Preds) > len(b.predstorage) {
+		c.Preds = b.Preds
+	} else {
+		c.Preds = append(c.predstorage[:0], b.Preds...)
+	}
+	for _, p := range c.Preds {
+		for i, q := range p.Succs {
+			if q == b {
+				p.Succs[i] = c
+			}
+		}
+	}
+	if f := b.Func; f.Entry == b {
+		f.Entry = c
+	}
+
+	// trash b, just in case
+	b.Kind = BlockInvalid
+	b.Values = nil
+	b.Preds = nil
+	b.Succs = nil
+	return true
+}