1 files changed, 371 insertions, 0 deletions
diff --git a/src/cmd/compile/internal/ssa/block.go b/src/cmd/compile/internal/ssa/block.go
new file mode 100644
index 0000000..519ac21
--- /dev/null
+++ b/src/cmd/compile/internal/ssa/block.go
@@ -0,0 +1,371 @@
+// 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 (
+	"cmd/internal/src"
+	"fmt"
+)
+
+// Block represents a basic block in the control flow graph of a function.
+type Block struct {
+	// A unique identifier for the block. The system will attempt to allocate
+	// these IDs densely, but no guarantees.
+	ID ID
+
+	// Source position for block's control operation
+	Pos src.XPos
+
+	// The kind of block this is.
+	Kind BlockKind
+
+	// Likely direction for branches.
+	// If BranchLikely, Succs[0] is the most likely branch taken.
+	// If BranchUnlikely, Succs[1] is the most likely branch taken.
+	// Ignored if len(Succs) < 2.
+	// Fatal if not BranchUnknown and len(Succs) > 2.
+	Likely BranchPrediction
+
+	// After flagalloc, records whether flags are live at the end of the block.
+	FlagsLiveAtEnd bool
+
+	// Subsequent blocks, if any. The number and order depend on the block kind.
+	Succs []Edge
+
+	// Inverse of successors.
+	// The order is significant to Phi nodes in the block.
+	// TODO: predecessors is a pain to maintain. Can we somehow order phi
+	// arguments by block id and have this field computed explicitly when needed?
+	Preds []Edge
+
+	// A list of values that determine how the block is exited. The number
+	// and type of control values depends on the Kind of the block. For
+	// instance, a BlockIf has a single boolean control value and BlockExit
+	// has a single memory control value.
+	//
+	// The ControlValues() method may be used to get a slice with the non-nil
+	// control values that can be ranged over.
+	//
+	// Controls[1] must be nil if Controls[0] is nil.
+	Controls [2]*Value
+
+	// Auxiliary info for the block. Its value depends on the Kind.
+	Aux    interface{}
+	AuxInt int64
+
+	// The unordered set of Values that define the operation of this block.
+	// After the scheduling pass, this list is ordered.
+	Values []*Value
+
+	// The containing function
+	Func *Func
+
+	// Storage for Succs, Preds and Values.
+	succstorage [2]Edge
+	predstorage [4]Edge
+	valstorage  [9]*Value
+}
+
+// Edge represents a CFG edge.
+// Example edges for b branching to either c or d.
+// (c and d have other predecessors.)
+//   b.Succs = [{c,3}, {d,1}]
+//   c.Preds = [?, ?, ?, {b,0}]
+//   d.Preds = [?, {b,1}, ?]
+// These indexes allow us to edit the CFG in constant time.
+// In addition, it informs phi ops in degenerate cases like:
+// b:
+//    if k then c else c
+// c:
+//    v = Phi(x, y)
+// Then the indexes tell you whether x is chosen from
+// the if or else branch from b.
+//   b.Succs = [{c,0},{c,1}]
+//   c.Preds = [{b,0},{b,1}]
+// means x is chosen if k is true.
+type Edge struct {
+	// block edge goes to (in a Succs list) or from (in a Preds list)
+	b *Block
+	// index of reverse edge.  Invariant:
+	//   e := x.Succs[idx]
+	//   e.b.Preds[e.i] = Edge{x,idx}
+	// and similarly for predecessors.
+	i int
+}
+
+func (e Edge) Block() *Block {
+	return e.b
+}
+func (e Edge) Index() int {
+	return e.i
+}
+func (e Edge) String() string {
+	return fmt.Sprintf("{%v,%d}", e.b, e.i)
+}
+
+//     kind          controls        successors
+//   ------------------------------------------
+//     Exit      [return mem]                []
+//    Plain                []            [next]
+//       If   [boolean Value]      [then, else]
+//    Defer             [mem]  [nopanic, panic]  (control opcode should be OpStaticCall to runtime.deferproc)
+type BlockKind int8
+
+// short form print
+func (b *Block) String() string {
+	return fmt.Sprintf("b%d", b.ID)
+}
+
+// long form print
+func (b *Block) LongString() string {
+	s := b.Kind.String()
+	if b.Aux != nil {
+		s += fmt.Sprintf(" {%s}", b.Aux)
+	}
+	if t := b.AuxIntString(); t != "" {
+		s += fmt.Sprintf(" [%s]", t)
+	}
+	for _, c := range b.ControlValues() {
+		s += fmt.Sprintf(" %s", c)
+	}
+	if len(b.Succs) > 0 {
+		s += " ->"
+		for _, c := range b.Succs {
+			s += " " + c.b.String()
+		}
+	}
+	switch b.Likely {
+	case BranchUnlikely:
+		s += " (unlikely)"
+	case BranchLikely:
+		s += " (likely)"
+	}
+	return s
+}
+
+// NumControls returns the number of non-nil control values the
+// block has.
+func (b *Block) NumControls() int {
+	if b.Controls[0] == nil {
+		return 0
+	}
+	if b.Controls[1] == nil {
+		return 1
+	}
+	return 2
+}
+
+// ControlValues returns a slice containing the non-nil control
+// values of the block. The index of each control value will be
+// the same as it is in the Controls property and can be used
+// in ReplaceControl calls.
+func (b *Block) ControlValues() []*Value {
+	if b.Controls[0] == nil {
+		return b.Controls[:0]
+	}
+	if b.Controls[1] == nil {
+		return b.Controls[:1]
+	}
+	return b.Controls[:2]
+}
+
+// SetControl removes all existing control values and then adds
+// the control value provided. The number of control values after
+// a call to SetControl will always be 1.
+func (b *Block) SetControl(v *Value) {
+	b.ResetControls()
+	b.Controls[0] = v
+	v.Uses++
+}
+
+// ResetControls sets the number of controls for the block to 0.
+func (b *Block) ResetControls() {
+	if b.Controls[0] != nil {
+		b.Controls[0].Uses--
+	}
+	if b.Controls[1] != nil {
+		b.Controls[1].Uses--
+	}
+	b.Controls = [2]*Value{} // reset both controls to nil
+}
+
+// AddControl appends a control value to the existing list of control values.
+func (b *Block) AddControl(v *Value) {
+	i := b.NumControls()
+	b.Controls[i] = v // panics if array is full
+	v.Uses++
+}
+
+// ReplaceControl exchanges the existing control value at the index provided
+// for the new value. The index must refer to a valid control value.
+func (b *Block) ReplaceControl(i int, v *Value) {
+	b.Controls[i].Uses--
+	b.Controls[i] = v
+	v.Uses++
+}
+
+// CopyControls replaces the controls for this block with those from the
+// provided block. The provided block is not modified.
+func (b *Block) CopyControls(from *Block) {
+	if b == from {
+		return
+	}
+	b.ResetControls()
+	for _, c := range from.ControlValues() {
+		b.AddControl(c)
+	}
+}
+
+// Reset sets the block to the provided kind and clears all the blocks control
+// and auxiliary values. Other properties of the block, such as its successors,
+// predecessors and values are left unmodified.
+func (b *Block) Reset(kind BlockKind) {
+	b.Kind = kind
+	b.ResetControls()
+	b.Aux = nil
+	b.AuxInt = 0
+}
+
+// resetWithControl resets b and adds control v.
+// It is equivalent to b.Reset(kind); b.AddControl(v),
+// except that it is one call instead of two and avoids a bounds check.
+// It is intended for use by rewrite rules, where this matters.
+func (b *Block) resetWithControl(kind BlockKind, v *Value) {
+	b.Kind = kind
+	b.ResetControls()
+	b.Aux = nil
+	b.AuxInt = 0
+	b.Controls[0] = v
+	v.Uses++
+}
+
+// resetWithControl2 resets b and adds controls v and w.
+// It is equivalent to b.Reset(kind); b.AddControl(v); b.AddControl(w),
+// except that it is one call instead of three and avoids two bounds checks.
+// It is intended for use by rewrite rules, where this matters.
+func (b *Block) resetWithControl2(kind BlockKind, v, w *Value) {
+	b.Kind = kind
+	b.ResetControls()
+	b.Aux = nil
+	b.AuxInt = 0
+	b.Controls[0] = v
+	b.Controls[1] = w
+	v.Uses++
+	w.Uses++
+}
+
+// truncateValues truncates b.Values at the ith element, zeroing subsequent elements.
+// The values in b.Values after i must already have had their args reset,
+// to maintain correct value uses counts.
+func (b *Block) truncateValues(i int) {
+	tail := b.Values[i:]
+	for j := range tail {
+		tail[j] = nil
+	}
+	b.Values = b.Values[:i]
+}
+
+// AddEdgeTo adds an edge from block b to block c. Used during building of the
+// SSA graph; do not use on an already-completed SSA graph.
+func (b *Block) AddEdgeTo(c *Block) {
+	i := len(b.Succs)
+	j := len(c.Preds)
+	b.Succs = append(b.Succs, Edge{c, j})
+	c.Preds = append(c.Preds, Edge{b, i})
+	b.Func.invalidateCFG()
+}
+
+// removePred removes the ith input edge from b.
+// It is the responsibility of the caller to remove
+// the corresponding successor edge.
+func (b *Block) removePred(i int) {
+	n := len(b.Preds) - 1
+	if i != n {
+		e := b.Preds[n]
+		b.Preds[i] = e
+		// Update the other end of the edge we moved.
+		e.b.Succs[e.i].i = i
+	}
+	b.Preds[n] = Edge{}
+	b.Preds = b.Preds[:n]
+	b.Func.invalidateCFG()
+}
+
+// removeSucc removes the ith output edge from b.
+// It is the responsibility of the caller to remove
+// the corresponding predecessor edge.
+func (b *Block) removeSucc(i int) {
+	n := len(b.Succs) - 1
+	if i != n {
+		e := b.Succs[n]
+		b.Succs[i] = e
+		// Update the other end of the edge we moved.
+		e.b.Preds[e.i].i = i
+	}
+	b.Succs[n] = Edge{}
+	b.Succs = b.Succs[:n]
+	b.Func.invalidateCFG()
+}
+
+func (b *Block) swapSuccessors() {
+	if len(b.Succs) != 2 {
+		b.Fatalf("swapSuccessors with len(Succs)=%d", len(b.Succs))
+	}
+	e0 := b.Succs[0]
+	e1 := b.Succs[1]
+	b.Succs[0] = e1
+	b.Succs[1] = e0
+	e0.b.Preds[e0.i].i = 1
+	e1.b.Preds[e1.i].i = 0
+	b.Likely *= -1
+}
+
+// LackingPos indicates whether b is a block whose position should be inherited
+// from its successors.  This is true if all the values within it have unreliable positions
+// and if it is "plain", meaning that there is no control flow that is also very likely
+// to correspond to a well-understood source position.
+func (b *Block) LackingPos() bool {
+	// Non-plain predecessors are If or Defer, which both (1) have two successors,
+	// which might have different line numbers and (2) correspond to statements
+	// in the source code that have positions, so this case ought not occur anyway.
+	if b.Kind != BlockPlain {
+		return false
+	}
+	if b.Pos != src.NoXPos {
+		return false
+	}
+	for _, v := range b.Values {
+		if v.LackingPos() {
+			continue
+		}
+		return false
+	}
+	return true
+}
+
+func (b *Block) AuxIntString() string {
+	switch b.Kind.AuxIntType() {
+	case "int8":
+		return fmt.Sprintf("%v", int8(b.AuxInt))
+	case "uint8":
+		return fmt.Sprintf("%v", uint8(b.AuxInt))
+	default: // type specified but not implemented - print as int64
+		return fmt.Sprintf("%v", b.AuxInt)
+	case "": // no aux int type
+		return ""
+	}
+}
+
+func (b *Block) Logf(msg string, args ...interface{})   { b.Func.Logf(msg, args...) }
+func (b *Block) Log() bool                              { return b.Func.Log() }
+func (b *Block) Fatalf(msg string, args ...interface{}) { b.Func.Fatalf(msg, args...) }
+
+type BranchPrediction int8
+
+const (
+	BranchUnlikely = BranchPrediction(-1)
+	BranchUnknown  = BranchPrediction(0)
+	BranchLikely   = BranchPrediction(+1)
+)