1 files changed, 102 insertions, 0 deletions
diff --git a/src/cmd/compile/internal/ssa/layout.go b/src/cmd/compile/internal/ssa/layout.go
new file mode 100644
index 0000000000..8dd4b65979
--- /dev/null
+++ b/src/cmd/compile/internal/ssa/layout.go
@@ -0,0 +1,102 @@
+// 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
+
+// layout orders basic blocks in f with the goal of minimizing control flow instructions.
+// After this phase returns, the order of f.Blocks matters and is the order
+// in which those blocks will appear in the assembly output.
+func layout(f *Func) {
+	order := make([]*Block, 0, f.NumBlocks())
+	scheduled := make([]bool, f.NumBlocks())
+	idToBlock := make([]*Block, f.NumBlocks())
+	indegree := make([]int, f.NumBlocks())
+	posdegree := f.newSparseSet(f.NumBlocks()) // blocks with positive remaining degree
+	defer f.retSparseSet(posdegree)
+	zerodegree := f.newSparseSet(f.NumBlocks()) // blocks with zero remaining degree
+	defer f.retSparseSet(zerodegree)
+
+	// Initialize indegree of each block
+	for _, b := range f.Blocks {
+		idToBlock[b.ID] = b
+		indegree[b.ID] = len(b.Preds)
+		if len(b.Preds) == 0 {
+			zerodegree.add(b.ID)
+		} else {
+			posdegree.add(b.ID)
+		}
+	}
+
+	bid := f.Entry.ID
+blockloop:
+	for {
+		// add block to schedule
+		b := idToBlock[bid]
+		order = append(order, b)
+		scheduled[bid] = true
+		if len(order) == len(f.Blocks) {
+			break
+		}
+
+		for _, c := range b.Succs {
+			indegree[c.ID]--
+			if indegree[c.ID] == 0 {
+				posdegree.remove(c.ID)
+				zerodegree.add(c.ID)
+			}
+		}
+
+		// Pick the next block to schedule
+		// Pick among the successor blocks that have not been scheduled yet.
+
+		// Use likely direction if we have it.
+		var likely *Block
+		switch b.Likely {
+		case BranchLikely:
+			likely = b.Succs[0]
+		case BranchUnlikely:
+			likely = b.Succs[1]
+		}
+		if likely != nil && !scheduled[likely.ID] {
+			bid = likely.ID
+			continue
+		}
+
+		// Use degree for now.
+		bid = 0
+		mindegree := f.NumBlocks()
+		for _, c := range order[len(order)-1].Succs {
+			if scheduled[c.ID] {
+				continue
+			}
+			if indegree[c.ID] < mindegree {
+				mindegree = indegree[c.ID]
+				bid = c.ID
+			}
+		}
+		if bid != 0 {
+			continue
+		}
+		// TODO: improve this part
+		// No successor of the previously scheduled block works.
+		// Pick a zero-degree block if we can.
+		for zerodegree.size() > 0 {
+			cid := zerodegree.pop()
+			if !scheduled[cid] {
+				bid = cid
+				continue blockloop
+			}
+		}
+		// Still nothing, pick any block.
+		for {
+			cid := posdegree.pop()
+			if !scheduled[cid] {
+				bid = cid
+				continue blockloop
+			}
+		}
+		b.Fatalf("no block available for layout")
+	}
+	f.Blocks = order
+}