[dev.ssa] cmd/internal/ssa: SSA backend compiler skeleton
First pass adding code for SSA backend. It is standalone for now.
I've included just a few passes to make the review size manageable -
I have more passes coming.
cmd/internal/ssa is the library containing the ssa compiler proper.
cmd/internal/ssa/ssac is a driver that loads an sexpr-based IR,
converts it to SSA form, and calls the above library. It is essentially
throwaway code - it will disappear once the Go compiler calls
cmd/internal/ssa itself. The .goir files in ssac/ are dumps of fibonacci
programs I made from a hacked-up compiler. They are just for testing.
Change-Id: I5ee89356ec12c87cd916681097cd3c2cd591040c
Reviewed-on: https://go-review.googlesource.com/6681
Reviewed-by: Alan Donovan <adonovan@google.com>
diff --git a/src/cmd/internal/ssa/block.go b/src/cmd/internal/ssa/block.go
new file mode 100644
index 0000000..ff1cb1b
--- /dev/null
+++ b/src/cmd/internal/ssa/block.go
@@ -0,0 +1,92 @@
+// 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 (
+ "fmt"
+ "strings"
+)
+
+// 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
+
+ // The kind of block this is.
+ Kind BlockKind
+
+ // Subsequent blocks, if any. The number and order depend on the block kind.
+ // All blocks must be distinct (to make phi values in successors unambiguous).
+ Succs []*Block
+
+ // Inverse of successors.
+ // The order is significant to Phi nodes in the block.
+ Preds []*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?
+
+ // A value that determines how the block is exited. Its value depends on the kind
+ // of the block. For instance, a BlockIf has a boolean control value and BlockExit
+ // has a memory control value.
+ Control *Value
+
+ // The unordered set of Values contained in this block.
+ // The list must include the control value, if any. (TODO: need this last condition?)
+ Values []*Value
+
+ // The containing function
+ Func *Func
+}
+
+// kind control successors
+// ------------------------------------------
+// Exit return mem []
+// Plain nil [next]
+// If a boolean Value [then, else]
+// Call mem [nopanic, panic] (control opcode should be OpCall or OpStaticCall)
+type BlockKind int8
+
+const (
+ BlockExit BlockKind = iota // no successors. There should only be 1 of these.
+ BlockPlain // a single successor
+ BlockIf // 2 successors, if control goto Succs[0] else goto Succs[1]
+ BlockCall // 2 successors, normal return and panic
+ BlockUnknown
+
+ // 386/amd64 variants of BlockIf that take the flags register as an arg
+ BlockEQ
+ BlockNE
+ BlockLT
+ BlockLE
+ BlockGT
+ BlockGE
+ BlockULT
+ BlockULE
+ BlockUGT
+ BlockUGE
+)
+
+//go:generate stringer -type=BlockKind
+
+// short form print
+func (b *Block) String() string {
+ return fmt.Sprintf("b%d", b.ID)
+}
+
+// long form print
+func (b *Block) LongString() string {
+ s := strings.TrimPrefix(b.Kind.String(), "Block")
+ if b.Control != nil {
+ s += fmt.Sprintf(" %s", b.Control)
+ }
+ if len(b.Succs) > 0 {
+ s += " ->"
+ for _, c := range b.Succs {
+ s += " " + c.String()
+ }
+ }
+ return s
+}
diff --git a/src/cmd/internal/ssa/blockkind_string.go b/src/cmd/internal/ssa/blockkind_string.go
new file mode 100644
index 0000000..6204f19
--- /dev/null
+++ b/src/cmd/internal/ssa/blockkind_string.go
@@ -0,0 +1,16 @@
+// generated by stringer -type=BlockKind; DO NOT EDIT
+
+package ssa
+
+import "fmt"
+
+const _BlockKind_name = "BlockExitBlockPlainBlockIfBlockCallBlockUnknownBlockEQBlockNEBlockLTBlockLEBlockGTBlockGEBlockULTBlockULEBlockUGTBlockUGE"
+
+var _BlockKind_index = [...]uint8{0, 9, 19, 26, 35, 47, 54, 61, 68, 75, 82, 89, 97, 105, 113, 121}
+
+func (i BlockKind) String() string {
+ if i < 0 || i+1 >= BlockKind(len(_BlockKind_index)) {
+ return fmt.Sprintf("BlockKind(%d)", i)
+ }
+ return _BlockKind_name[_BlockKind_index[i]:_BlockKind_index[i+1]]
+}
diff --git a/src/cmd/internal/ssa/check.go b/src/cmd/internal/ssa/check.go
new file mode 100644
index 0000000..b501cdb
--- /dev/null
+++ b/src/cmd/internal/ssa/check.go
@@ -0,0 +1,125 @@
+// 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"
+
+// checkFunc checks invariants of f.
+func checkFunc(f *Func) {
+ blockMark := make([]bool, f.NumBlocks())
+ valueMark := make([]bool, f.NumValues())
+
+ for _, b := range f.Blocks {
+ if blockMark[b.ID] {
+ log.Panicf("block %s appears twice in %s!", b, f.Name)
+ }
+ blockMark[b.ID] = true
+ if b.Func != f {
+ log.Panicf("%s.Func=%s, want %s", b, b.Func.Name, f.Name)
+ }
+
+ for i, c := range b.Succs {
+ for j, d := range b.Succs {
+ if i != j && c == d {
+ log.Panicf("%s.Succs has duplicate block %s", b, c)
+ }
+ }
+ }
+ // Note: duplicate successors are hard in the following case:
+ // if(...) goto x else goto x
+ // x: v = phi(a, b)
+ // If the conditional is true, does v get the value of a or b?
+ // We could solve this other ways, but the easiest is just to
+ // require (by possibly adding empty control-flow blocks) that
+ // all successors are distinct. They will need to be distinct
+ // anyway for register allocation (duplicate successors implies
+ // the existence of critical edges).
+
+ for _, p := range b.Preds {
+ var found bool
+ for _, c := range p.Succs {
+ if c == b {
+ found = true
+ break
+ }
+ }
+ if !found {
+ log.Panicf("block %s is not a succ of its pred block %s", b, p)
+ }
+ }
+
+ switch b.Kind {
+ case BlockExit:
+ if len(b.Succs) != 0 {
+ log.Panicf("exit block %s has successors", b)
+ }
+ if b.Control == nil {
+ log.Panicf("exit block %s has no control value", b)
+ }
+ if b.Control.Type != TypeMem {
+ log.Panicf("exit block %s has non-memory control value %s", b, b.Control.LongString())
+ }
+ case BlockPlain:
+ if len(b.Succs) != 1 {
+ log.Panicf("plain block %s len(Succs)==%d, want 1", b, len(b.Succs))
+ }
+ if b.Control != nil {
+ log.Panicf("plain block %s has non-nil control %s", b, b.Control.LongString())
+ }
+ case BlockIf:
+ if len(b.Succs) != 2 {
+ log.Panicf("if block %s len(Succs)==%d, want 2", b, len(b.Succs))
+ }
+ if b.Control == nil {
+ log.Panicf("if block %s has no control value", b)
+ }
+ if b.Control.Type != TypeBool {
+ log.Panicf("if block %s has non-bool control value %s", b, b.Control.LongString())
+ }
+ case BlockCall:
+ if len(b.Succs) != 2 {
+ log.Panicf("call block %s len(Succs)==%d, want 2", b, len(b.Succs))
+ }
+ if b.Control == nil {
+ log.Panicf("call block %s has no control value", b)
+ }
+ if b.Control.Type != TypeMem {
+ log.Panicf("call block %s has non-memory control value %s", b, b.Control.LongString())
+ }
+ if b.Succs[1].Kind != BlockExit {
+ log.Panicf("exception edge from call block %s does not go to exit but %s", b, b.Succs[1])
+ }
+ }
+
+ for _, v := range b.Values {
+ if valueMark[v.ID] {
+ log.Panicf("value %s appears twice!", v.LongString())
+ }
+ valueMark[v.ID] = true
+
+ if v.Block != b {
+ log.Panicf("%s.block != %s", v, b)
+ }
+ if v.Op == OpPhi && len(v.Args) != len(b.Preds) {
+ log.Panicf("phi length %s does not match pred length %d for block %s", v.LongString(), len(b.Preds), b)
+ }
+
+ // TODO: check idom
+ // TODO: check for cycles in values
+ // TODO: check type
+ }
+ }
+
+ for _, id := range f.bid.free {
+ if blockMark[id] {
+ log.Panicf("used block b%d in free list", id)
+ }
+ }
+ for _, id := range f.vid.free {
+ if valueMark[id] {
+ log.Panicf("used value v%d in free list", id)
+ }
+ }
+}
diff --git a/src/cmd/internal/ssa/compile.go b/src/cmd/internal/ssa/compile.go
new file mode 100644
index 0000000..5e21bdf6
--- /dev/null
+++ b/src/cmd/internal/ssa/compile.go
@@ -0,0 +1,65 @@
+// 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 "fmt"
+
+// Compile is the main entry point for this package.
+// Compile modifies f so that on return:
+// · all Values in f map to 0 or 1 assembly instructions of the target architecture
+// · the order of f.Blocks is the order to emit the Blocks
+// · the order of b.Values is the order to emit the Values in each Block
+// · f has a non-nil regAlloc field
+func Compile(f *Func) {
+ // TODO: debugging - set flags to control verbosity of compiler,
+ // which phases to dump IR before/after, etc.
+ fmt.Printf("compiling %s\n", f.Name)
+
+ // hook to print function & phase if panic happens
+ phaseName := "init"
+ defer func() {
+ if phaseName != "" {
+ fmt.Printf("panic during %s while compiling %s\n", phaseName, f.Name)
+ }
+ }()
+
+ // Run all the passes
+ printFunc(f)
+ checkFunc(f)
+ for _, p := range passes {
+ phaseName = p.name
+ fmt.Printf(" pass %s begin\n", p.name)
+ p.fn(f)
+ fmt.Printf(" pass %s end\n", p.name)
+ printFunc(f)
+ checkFunc(f)
+ }
+
+ // Squash error printing defer
+ phaseName = ""
+}
+
+type pass struct {
+ name string
+ fn func(*Func)
+}
+
+// list of passes for the compiler
+var passes = [...]pass{
+ {"phielim", phielim},
+ {"copyelim", copyelim},
+ //{"opt", opt},
+ // cse
+ {"deadcode", deadcode},
+ //{"fuse", fuse},
+ //{"lower", lower},
+ // cse
+ //{"critical", critical}, // remove critical edges
+ //{"layout", layout}, // schedule blocks
+ //{"schedule", schedule}, // schedule values
+ // regalloc
+ // stack slot alloc (+size stack frame)
+ //{"cgen", cgen},
+}
diff --git a/src/cmd/internal/ssa/copyelim.go b/src/cmd/internal/ssa/copyelim.go
new file mode 100644
index 0000000..10c2dcc
--- /dev/null
+++ b/src/cmd/internal/ssa/copyelim.go
@@ -0,0 +1,29 @@
+// 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
+
+// copyelim removes all copies from f.
+func copyelim(f *Func) {
+ for _, b := range f.Blocks {
+ for _, v := range b.Values {
+ for i, w := range v.Args {
+ x := w
+ for x.Op == OpCopy {
+ x = x.Args[0]
+ }
+ if x != w {
+ v.Args[i] = x
+ }
+ }
+ }
+ v := b.Control
+ if v != nil {
+ for v.Op == OpCopy {
+ v = v.Args[0]
+ }
+ b.Control = v
+ }
+ }
+}
diff --git a/src/cmd/internal/ssa/deadcode.go b/src/cmd/internal/ssa/deadcode.go
new file mode 100644
index 0000000..1647ea9
--- /dev/null
+++ b/src/cmd/internal/ssa/deadcode.go
@@ -0,0 +1,153 @@
+// 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 == OpConstBool {
+ 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)
+ }
+ }
+ for j := i; j < len(b.Values); j++ {
+ b.Values[j] = nil // aid GC
+ }
+ 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
+ for j := i; j < len(f.Blocks); j++ {
+ f.Blocks[j] = nil
+ }
+ f.Blocks = f.Blocks[:i]
+
+ // TODO: renumber Blocks and Values densely?
+}
+
+// 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
+ }
+ }
+}
diff --git a/src/cmd/internal/ssa/deadcode_test.go b/src/cmd/internal/ssa/deadcode_test.go
new file mode 100644
index 0000000..94fc359
--- /dev/null
+++ b/src/cmd/internal/ssa/deadcode_test.go
@@ -0,0 +1,112 @@
+// 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.
+
+// TODO: these tests are pretty verbose. Is there a way to simplify
+// building a small Func for testing?
+
+package ssa_test
+
+import (
+ . "cmd/internal/ssa"
+ "testing"
+)
+
+func TestDeadLoop(t *testing.T) {
+ f := new(Func)
+ entry := f.NewBlock(BlockPlain)
+ exit := f.NewBlock(BlockExit)
+ f.Entry = entry
+ addEdge(entry, exit)
+ mem := entry.NewValue(OpArg, TypeMem, ".mem")
+ exit.Control = mem
+
+ // dead loop
+ deadblock := f.NewBlock(BlockIf)
+ addEdge(deadblock, deadblock)
+ addEdge(deadblock, exit)
+
+ // dead value in dead block
+ deadval := deadblock.NewValue(OpConstBool, TypeBool, true)
+ deadblock.Control = deadval
+
+ CheckFunc(f)
+ Deadcode(f)
+ CheckFunc(f)
+
+ for _, b := range f.Blocks {
+ if b == deadblock {
+ t.Errorf("dead block not removed")
+ }
+ for _, v := range b.Values {
+ if v == deadval {
+ t.Errorf("control value of dead block not removed")
+ }
+ }
+ }
+}
+
+func TestDeadValue(t *testing.T) {
+ f := new(Func)
+ entry := f.NewBlock(BlockPlain)
+ exit := f.NewBlock(BlockExit)
+ f.Entry = entry
+ addEdge(entry, exit)
+ mem := entry.NewValue(OpArg, TypeMem, ".mem")
+ exit.Control = mem
+
+ deadval := entry.NewValue(OpConstInt, TypeInt, 37)
+
+ CheckFunc(f)
+ Deadcode(f)
+ CheckFunc(f)
+
+ for _, b := range f.Blocks {
+ for _, v := range b.Values {
+ if v == deadval {
+ t.Errorf("dead value not removed")
+ }
+ }
+ }
+}
+
+func TestNeverTaken(t *testing.T) {
+ f := new(Func)
+ entry := f.NewBlock(BlockIf)
+ exit := f.NewBlock(BlockExit)
+ then := f.NewBlock(BlockPlain)
+ else_ := f.NewBlock(BlockPlain)
+ f.Entry = entry
+ addEdge(entry, then)
+ addEdge(entry, else_)
+ addEdge(then, exit)
+ addEdge(else_, exit)
+ mem := entry.NewValue(OpArg, TypeMem, ".mem")
+ exit.Control = mem
+
+ cond := entry.NewValue(OpConstBool, TypeBool, false)
+ entry.Control = cond
+
+ CheckFunc(f)
+ Deadcode(f)
+ CheckFunc(f)
+
+ if entry.Kind != BlockPlain {
+ t.Errorf("if(false) not simplified")
+ }
+ for _, b := range f.Blocks {
+ if b == then {
+ t.Errorf("then block still present")
+ }
+ for _, v := range b.Values {
+ if v == cond {
+ t.Errorf("constant condition still present")
+ }
+ }
+ }
+}
+
+func addEdge(b, c *Block) {
+ b.Succs = append(b.Succs, c)
+ c.Preds = append(c.Preds, b)
+}
diff --git a/src/cmd/internal/ssa/export_test.go b/src/cmd/internal/ssa/export_test.go
new file mode 100644
index 0000000..ab4ab82
--- /dev/null
+++ b/src/cmd/internal/ssa/export_test.go
@@ -0,0 +1,9 @@
+// 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
+
+var CheckFunc = checkFunc
+var PrintFunc = printFunc
+var Deadcode = deadcode
diff --git a/src/cmd/internal/ssa/func.go b/src/cmd/internal/ssa/func.go
new file mode 100644
index 0000000..6868e3d
--- /dev/null
+++ b/src/cmd/internal/ssa/func.go
@@ -0,0 +1,61 @@
+// 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
+
+// A Func represents a Go func declaration (or function literal) and
+// its body. This package compiles each Func independently.
+type Func struct {
+ Name string // e.g. bytes·Compare
+ Type Type // type signature of the function.
+ Blocks []*Block // unordered set of all basic blocks (note: not indexable by ID)
+ Entry *Block // the entry basic block
+ bid idAlloc // block ID allocator
+ vid idAlloc // value ID allocator
+
+ // when register allocation is done, maps value ids to locations
+ RegAlloc []Location
+}
+
+// NumBlocks returns an integer larger than the id of any Block in the Func.
+func (f *Func) NumBlocks() int {
+ return f.bid.num()
+}
+
+// NumValues returns an integer larger than the id of any Value in the Func.
+func (f *Func) NumValues() int {
+ return f.vid.num()
+}
+
+// NewBlock returns a new block of the given kind and appends it to f.Blocks.
+func (f *Func) NewBlock(kind BlockKind) *Block {
+ b := &Block{
+ ID: f.bid.get(),
+ Kind: kind,
+ Func: f,
+ }
+ f.Blocks = append(f.Blocks, b)
+ return b
+}
+
+// NewValue returns a new value in the block with no arguments.
+func (b *Block) NewValue(op Op, t Type, aux interface{}) *Value {
+ v := &Value{
+ ID: b.Func.vid.get(),
+ Op: op,
+ Type: t,
+ Aux: aux,
+ Block: b,
+ }
+ v.Args = v.argstorage[:0]
+ b.Values = append(b.Values, v)
+ return v
+}
+
+// ConstInt returns an int constant representing its argument.
+func (f *Func) ConstInt(c int64) *Value {
+ // TODO: cache?
+ // TODO: different types?
+ return f.Entry.NewValue(OpConstInt, TypeInt, c)
+}
diff --git a/src/cmd/internal/ssa/id.go b/src/cmd/internal/ssa/id.go
new file mode 100644
index 0000000..43f23c8
--- /dev/null
+++ b/src/cmd/internal/ssa/id.go
@@ -0,0 +1,41 @@
+// 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
+
+type ID int32
+
+// idAlloc provides an allocator for unique integers.
+type idAlloc struct {
+ last ID
+ free []ID
+}
+
+// get allocates an ID and returns it.
+func (a *idAlloc) get() ID {
+ if n := len(a.free); n > 0 {
+ x := a.free[n-1]
+ a.free = a.free[:n-1]
+ return x
+ }
+ x := a.last
+ x++
+ if x == 1<<31-1 {
+ panic("too many ids for this function")
+ }
+ a.last = x
+ return x
+}
+
+// put deallocates an ID.
+func (a *idAlloc) put(x ID) {
+ a.free = append(a.free, x)
+ // TODO: IR check should make sure that the IR contains
+ // no IDs that are in the free list.
+}
+
+// num returns the maximum ID ever returned + 1.
+func (a *idAlloc) num() int {
+ return int(a.last + 1)
+}
diff --git a/src/cmd/internal/ssa/location.go b/src/cmd/internal/ssa/location.go
new file mode 100644
index 0000000..94c1b42
--- /dev/null
+++ b/src/cmd/internal/ssa/location.go
@@ -0,0 +1,42 @@
+// 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 (
+ "fmt"
+)
+
+// A place that an ssa variable can reside.
+type Location interface {
+ Name() string // name to use in assembly templates: %rax, 16(%rsp), ...
+}
+
+// A Register is a machine register, like %rax.
+type Register struct {
+ name string
+}
+
+func (r *Register) Name() string {
+ return r.name
+}
+
+// A LocalSlot is a location in the stack frame.
+type LocalSlot struct {
+ idx int64 // offset in locals area (distance down from FP == caller's SP)
+}
+
+func (s *LocalSlot) Name() string {
+ return fmt.Sprintf("loc%d", s.idx)
+}
+
+// An ArgSlot is a location in the parents' stack frame where it passed us an argument.
+type ArgSlot struct {
+ idx int64 // offset in argument area
+}
+
+// A CalleeSlot is a location in the stack frame where we pass an argument to a callee.
+type CalleeSlot struct {
+ idx int64 // offset in callee area
+}
diff --git a/src/cmd/internal/ssa/op.go b/src/cmd/internal/ssa/op.go
new file mode 100644
index 0000000..a4364b1
--- /dev/null
+++ b/src/cmd/internal/ssa/op.go
@@ -0,0 +1,345 @@
+// 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
+
+// An Op encodes the specific operation that a Value performs.
+// Opcodes' semantics can be modified by the type and aux fields of the Value.
+// For instance, OpAdd can be 32 or 64 bit, signed or unsigned, float or complex, depending on Value.Type.
+// Semantics of each op are described below.
+// Ops come in two flavors, architecture-independent and architecture-dependent.
+type Op int32
+
+// All the opcodes
+const (
+ OpUnknown Op = iota
+
+ // machine-independent opcodes
+
+ OpNop // should never be used, appears only briefly during construction, Has type Void.
+ OpThunk // used during ssa construction. Like OpCopy, but the arg has not been specified yet.
+
+ // 2-input arithmetic
+ OpAdd
+ OpSub
+ OpMul
+
+ // 2-input comparisons
+ OpLess
+
+ // constants
+ OpConstNil
+ OpConstBool // aux is type bool
+ OpConstString // aux is type string
+ OpConstInt // aux is type int64
+ OpConstFloat // aux is type float64
+ OpConstComplex // aux is type complex128
+
+ OpArg // address of a function parameter/result
+ OpGlobal // address of a global variable
+ OpFunc // entry address of a function
+ OpCopy // output = input
+ OpPhi // select an input based on which predecessor we came from
+
+ OpSliceMake // args are ptr/len/cap
+ OpSlicePtr
+ OpSliceLen
+ OpSliceCap
+
+ OpStringMake // args are ptr/len
+ OpStringPtr
+ OpStringLen
+
+ OpSlice
+ OpIndex
+ OpIndexAddr
+
+ OpLoad // args are ptr, memory
+ OpStore // args are ptr, memory, returns memory
+
+ OpCheckNil // arg[0] != nil
+ OpCheckBound // 0 <= arg[0] < arg[1]
+
+ // function calls. Arguments to the call have already been written to the stack.
+ // Return values appear on the stack.
+ OpCall // args are function ptr, memory
+ OpStaticCall // aux is function, arg is memory
+
+ OpConvert
+ OpConvNop
+
+ // These ops return a pointer to a location on the stack. Aux contains an int64
+ // indicating an offset from the base pointer.
+ OpFPAddr // offset from FP (+ == args from caller, - == locals)
+ OpSPAddr // offset from SP
+
+ // load/store from constant offsets from SP/FP
+ // The distinction between FP/SP needs to be maintained until after
+ // register allocation because we don't know the size of the frame yet.
+ OpLoadFP
+ OpLoadSP
+ OpStoreFP
+ OpStoreSP
+
+ // spill&restore ops for the register allocator. These are
+ // semantically identical to OpCopy - they do not take/return
+ // stores like regular memory ops do. We can get away with that because
+ // we know there is no aliasing to spill slots on the stack.
+ OpStoreReg8
+ OpLoadReg8
+
+ // machine-dependent opcodes go here
+
+ // x86
+ OpADDQ
+ OpSUBQ
+ OpADDCQ // 1 input arg, add aux which is an int64 constant
+ OpSUBCQ // 1 input arg. output = input - aux.(int64)
+ OpNEGQ
+ OpCMPQ
+ OpCMPCQ // 1 input arg. Compares input with aux.(int64)
+ OpADDL
+ OpInvertFlags // inverts interpretation of the flags register (< to >=, etc.)
+ OpSETL // generate bool = "flags encode less than"
+ OpSETGE
+
+ OpLEAQ // x+y
+ OpLEAQ2 // x+2*y
+ OpLEAQ4 // x+4*y
+ OpLEAQ8 // x+8*y
+
+ OpLoadFP8
+ OpLoadSP8
+ OpStoreFP8
+ OpStoreSP8
+
+ OpMax // sentinel
+)
+
+//go:generate stringer -type=Op
+
+type OpInfo struct {
+ flags int32
+
+ // assembly template
+ // %In: location of input n
+ // %On: location of output n
+ // %A: print aux with fmt.Print
+ asm string
+
+ // computes type for values with this opcode
+ typer func(v *Value)
+
+ // returns a reg constraint for the instruction. [0] gives a reg constraint
+ // for each input, [1] gives a reg constraint for each output. (Values have
+ // exactly one output for now)
+ reg [2][]regMask
+}
+
+type regMask uint64
+
+var regs386 = [...]string{
+ "AX",
+ "BX",
+ "CX",
+ "DX",
+ "SI",
+ "DI",
+ "SP",
+ "BP",
+ "X0",
+
+ // pseudo registers
+ "FLAGS",
+ "OVERWRITE0", // the same register as the first input
+}
+
+// TODO: match up these with regs386 above
+var gp regMask = 0xff
+var cx regMask = 0x4
+var flags regMask = 1 << 9
+var overwrite0 regMask = 1 << 10
+
+const (
+ // possible properties of opcodes
+ OpFlagCommutative int32 = 1 << iota
+
+ // architecture constants
+ Arch386
+ ArchAmd64
+ ArchArm
+)
+
+func firstArgTyper(v *Value) {
+ v.Type = v.Args[0].Type
+}
+func boolTyper(v *Value) {
+ v.Type = TypeBool
+}
+func stringTyper(v *Value) {
+ v.Type = TypeString
+}
+func flagsTyper(v *Value) {
+ v.Type = TypeFlags
+}
+func uint8Typer(v *Value) {
+ v.Type = TypeUint8
+}
+func uint64Typer(v *Value) {
+ v.Type = TypeUint64
+}
+func auxTyper(v *Value) {
+ v.Type = v.Aux.(Type)
+}
+
+// general purpose registers, 2 input, 1 output
+var gp21 = [2][]regMask{{gp, gp}, {gp}}
+var gp21_overwrite = [2][]regMask{{gp, gp}, {overwrite0}}
+
+// general purpose registers, 1 input, 1 output
+var gp11 = [2][]regMask{{gp}, {gp}}
+var gp11_overwrite = [2][]regMask{{gp}, {overwrite0}}
+
+// shift operations
+var shift = [2][]regMask{{gp, cx}, {overwrite0}}
+
+var gp2_flags = [2][]regMask{{gp, gp}, {flags}}
+var gp1_flags = [2][]regMask{{gp}, {flags}}
+var gpload = [2][]regMask{{gp, 0}, {gp}}
+var gpstore = [2][]regMask{{gp, gp, 0}, {0}}
+
+// Opcodes that represent the input Go program
+var genericTable = [...]OpInfo{
+ // the unknown op is used only during building and should not appear in a
+ // fully formed ssa representation.
+
+ OpAdd: {flags: OpFlagCommutative, typer: firstArgTyper},
+ OpSub: {typer: firstArgTyper},
+ OpMul: {flags: OpFlagCommutative, typer: firstArgTyper},
+ OpLess: {typer: boolTyper},
+
+ OpConstBool: {typer: boolTyper}, // aux is a bool
+ OpConstString: {typer: stringTyper}, // aux is a string
+ OpConstInt: {}, // aux is an int64
+ OpConstFloat: {}, // aux is a float64
+ OpConstComplex: {},
+ OpArg: {}, // aux is the name of the input variable TODO:?
+ OpGlobal: {}, // address of a global variable
+ OpFunc: {},
+ OpCopy: {},
+ OpPhi: {},
+
+ OpConvNop: {}, // aux is the type to convert to
+
+ /*
+ // build and take apart slices
+ {name: "slicemake"}, // (ptr,len,cap) -> slice
+ {name: "sliceptr"}, // pointer part of slice
+ {name: "slicelen"}, // length part of slice
+ {name: "slicecap"}, // capacity part of slice
+
+ // build and take apart strings
+ {name: "stringmake"}, // (ptr,len) -> string
+ {name: "stringptr"}, // pointer part of string
+ {name: "stringlen"}, // length part of string
+
+ // operations on arrays/slices/strings
+ {name: "slice"}, // (s, i, j) -> s[i:j]
+ {name: "index"}, // (mem, ptr, idx) -> val
+ {name: "indexaddr"}, // (ptr, idx) -> ptr
+
+ // loads & stores
+ {name: "load"}, // (mem, check, ptr) -> val
+ {name: "store"}, // (mem, check, ptr, val) -> mem
+
+ // checks
+ {name: "checknil"}, // (mem, ptr) -> check
+ {name: "checkbound"}, // (mem, idx, len) -> check
+
+ // functions
+ {name: "call"},
+
+ // builtins
+ {name: "len"},
+ {name: "convert"},
+
+ // tuples
+ {name: "tuple"}, // build a tuple out of its arguments
+ {name: "extract"}, // aux is an int64. Extract that index out of a tuple
+ {name: "extractsuffix"}, // aux is an int64. Slice a tuple with [aux:]
+
+ */
+}
+
+// Opcodes that appear in an output amd64 program
+var amd64Table = [...]OpInfo{
+ OpADDQ: {flags: OpFlagCommutative, asm: "ADDQ\t%I0,%I1,%O0", reg: gp21, typer: firstArgTyper}, // TODO: overwrite
+ OpADDCQ: {asm: "ADDQ\t$%A,%I0,%O0", reg: gp11_overwrite, typer: firstArgTyper}, // aux = int64 constant to add
+ OpSUBQ: {asm: "SUBQ\t%I0,%I1,%O0", reg: gp21, typer: firstArgTyper},
+ OpSUBCQ: {asm: "SUBQ\t$%A,%I0,%O0", reg: gp11_overwrite, typer: firstArgTyper},
+
+ OpCMPQ: {asm: "CMPQ\t%I0,%I1", reg: gp2_flags, typer: flagsTyper}, // compute arg[0]-arg[1] and produce flags
+ OpCMPCQ: {asm: "CMPQ\t$%A,%I0", reg: gp1_flags},
+
+ OpLEAQ: {flags: OpFlagCommutative, asm: "LEAQ\t%A(%I0)(%I1*1),%O0", reg: gp21}, // aux = int64 constant to add
+ OpLEAQ2: {asm: "LEAQ\t%A(%I0)(%I1*2),%O0"},
+ OpLEAQ4: {asm: "LEAQ\t%A(%I0)(%I1*4),%O0"},
+ OpLEAQ8: {asm: "LEAQ\t%A(%I0)(%I1*8),%O0"},
+
+ //OpLoad8: {asm: "MOVQ\t%A(%I0),%O0", reg: gpload},
+ //OpStore8: {asm: "MOVQ\t%I1,%A(%I0)", reg: gpstore},
+
+ OpStaticCall: {asm: "CALL\t%A(SB)"},
+
+ OpCopy: {asm: "MOVQ\t%I0,%O0", reg: gp11},
+
+ // convert from flags back to boolean
+ OpSETL: {typer: boolTyper},
+
+ // ops for load/store to stack
+ OpLoadFP8: {asm: "MOVQ\t%A(FP),%O0"},
+ OpLoadSP8: {asm: "MOVQ\t%A(SP),%O0"},
+ OpStoreFP8: {asm: "MOVQ\t%I0,%A(FP)"},
+ OpStoreSP8: {asm: "MOVQ\t%I0,%A(SP)"},
+
+ // ops for spilling of registers
+ // unlike regular loads & stores, these take no memory argument.
+ // They are just like OpCopy but we use them during register allocation.
+ // TODO: different widths, float
+ OpLoadReg8: {asm: "MOVQ\t%I0,%O0", reg: gp11},
+ OpStoreReg8: {asm: "MOVQ\t%I0,%O0", reg: gp11},
+}
+
+// A Table is a list of opcodes with a common set of flags.
+type Table struct {
+ t []OpInfo
+ flags int32
+}
+
+var tables = []Table{
+ {genericTable[:], 0},
+ {amd64Table[:], ArchAmd64}, // TODO: pick this dynamically
+}
+
+// table of opcodes, indexed by opcode ID
+var opcodeTable [OpMax]OpInfo
+
+// map from opcode names to opcode IDs
+var nameToOp map[string]Op
+
+func init() {
+ // build full opcode table
+ // Note that the arch-specific table overwrites the generic table
+ for _, t := range tables {
+ for op, entry := range t.t {
+ entry.flags |= t.flags
+ opcodeTable[op] = entry
+ }
+ }
+ // build name to opcode mapping
+ nameToOp = make(map[string]Op)
+ for op := range opcodeTable {
+ nameToOp[Op(op).String()] = Op(op)
+ }
+}
diff --git a/src/cmd/internal/ssa/op_string.go b/src/cmd/internal/ssa/op_string.go
new file mode 100644
index 0000000..40051eb
--- /dev/null
+++ b/src/cmd/internal/ssa/op_string.go
@@ -0,0 +1,16 @@
+// generated by stringer -type=Op; DO NOT EDIT
+
+package ssa
+
+import "fmt"
+
+const _Op_name = "OpUnknownOpNopOpThunkOpAddOpSubOpMulOpLessOpConstNilOpConstBoolOpConstStringOpConstIntOpConstFloatOpConstComplexOpArgOpGlobalOpFuncOpCopyOpPhiOpSliceMakeOpSlicePtrOpSliceLenOpSliceCapOpStringMakeOpStringPtrOpStringLenOpSliceOpIndexOpIndexAddrOpLoadOpStoreOpCheckNilOpCheckBoundOpCallOpStaticCallOpConvertOpConvNopOpFPAddrOpSPAddrOpLoadFPOpLoadSPOpStoreFPOpStoreSPOpStoreReg8OpLoadReg8OpADDQOpSUBQOpADDCQOpSUBCQOpNEGQOpCMPQOpCMPCQOpADDLOpInvertFlagsOpSETLOpSETGEOpLEAQOpLEAQ2OpLEAQ4OpLEAQ8OpLoadFP8OpLoadSP8OpStoreFP8OpStoreSP8OpMax"
+
+var _Op_index = [...]uint16{0, 9, 14, 21, 26, 31, 36, 42, 52, 63, 76, 86, 98, 112, 117, 125, 131, 137, 142, 153, 163, 173, 183, 195, 206, 217, 224, 231, 242, 248, 255, 265, 277, 283, 295, 304, 313, 321, 329, 337, 345, 354, 363, 374, 384, 390, 396, 403, 410, 416, 422, 429, 435, 448, 454, 461, 467, 474, 481, 488, 497, 506, 516, 526, 531}
+
+func (i Op) String() string {
+ if i < 0 || i+1 >= Op(len(_Op_index)) {
+ return fmt.Sprintf("Op(%d)", i)
+ }
+ return _Op_name[_Op_index[i]:_Op_index[i+1]]
+}
diff --git a/src/cmd/internal/ssa/phielim.go b/src/cmd/internal/ssa/phielim.go
new file mode 100644
index 0000000..19c0d07
--- /dev/null
+++ b/src/cmd/internal/ssa/phielim.go
@@ -0,0 +1,44 @@
+// 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
+
+// phielim eliminates redundant phi values from f.
+// A phi is redundant if its arguments are all equal. For
+// purposes of counting, ignore the phi itself. Both of
+// these phis are redundant:
+// v = phi(x,x,x)
+// v = phi(x,v,x,v)
+func phielim(f *Func) {
+ args := newSparseSet(f.NumValues())
+ for _, b := range f.Blocks {
+ for _, v := range b.Values {
+ if v.Op != OpPhi {
+ continue
+ }
+ args.clear()
+ for _, x := range v.Args {
+ for x.Op == OpCopy {
+ x = x.Args[0]
+ }
+ args.add(x.ID)
+ }
+ switch {
+ case args.size() == 1:
+ v.Op = OpCopy
+ v.SetArgs1(v.Args[0])
+ case args.size() == 2 && args.contains(v.ID):
+ var w *Value
+ for _, x := range v.Args {
+ if x.ID != v.ID {
+ w = x
+ break
+ }
+ }
+ v.Op = OpCopy
+ v.SetArgs1(w)
+ }
+ }
+ }
+}
diff --git a/src/cmd/internal/ssa/print.go b/src/cmd/internal/ssa/print.go
new file mode 100644
index 0000000..eeea30d
--- /dev/null
+++ b/src/cmd/internal/ssa/print.go
@@ -0,0 +1,63 @@
+// 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 "fmt"
+
+func printFunc(f *Func) {
+ fmt.Print(f.Name)
+ fmt.Print(" ")
+ fmt.Println(f.Type)
+ printed := make([]bool, f.NumValues())
+ for _, b := range f.Blocks {
+ fmt.Printf(" b%d:\n", b.ID)
+ n := 0
+
+ // print phis first since all value cycles contain a phi
+ for _, v := range b.Values {
+ if v.Op != OpPhi {
+ continue
+ }
+ fmt.Print(" ")
+ fmt.Println(v.LongString())
+ printed[v.ID] = true
+ n++
+ }
+
+ // print rest of values in dependency order
+ for n < len(b.Values) {
+ m := n
+ outer:
+ for _, v := range b.Values {
+ if printed[v.ID] {
+ continue
+ }
+ for _, w := range v.Args {
+ if w.Block == b && !printed[w.ID] {
+ continue outer
+ }
+ }
+ fmt.Print(" ")
+ fmt.Println(v.LongString())
+ printed[v.ID] = true
+ n++
+ }
+ if m == n {
+ fmt.Println("dependency cycle!")
+ for _, v := range b.Values {
+ if printed[v.ID] {
+ continue
+ }
+ fmt.Print(" ")
+ fmt.Println(v.LongString())
+ printed[v.ID] = true
+ n++
+ }
+ }
+ }
+
+ fmt.Println(" " + b.LongString())
+ }
+}
diff --git a/src/cmd/internal/ssa/sparseset.go b/src/cmd/internal/ssa/sparseset.go
new file mode 100644
index 0000000..e1f9a9a
--- /dev/null
+++ b/src/cmd/internal/ssa/sparseset.go
@@ -0,0 +1,60 @@
+// 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
+
+// from http://research.swtch.com/sparse
+// in turn, from Briggs and Torczon
+
+type sparseSet struct {
+ dense []ID
+ sparse []int
+}
+
+// newSparseSet returns a sparseSet that can represent
+// integers between 0 and n-1
+func newSparseSet(n int) *sparseSet {
+ return &sparseSet{nil, make([]int, n)}
+}
+
+func (s *sparseSet) size() int {
+ return len(s.dense)
+}
+
+func (s *sparseSet) contains(x ID) bool {
+ i := s.sparse[x]
+ return i < len(s.dense) && s.dense[i] == x
+}
+
+func (s *sparseSet) add(x ID) {
+ i := len(s.dense)
+ s.dense = append(s.dense, x)
+ s.sparse[x] = i
+}
+
+func (s *sparseSet) remove(x ID) {
+ i := s.sparse[x]
+ if i < len(s.dense) && s.dense[i] == x {
+ y := s.dense[len(s.dense)-1]
+ s.dense[i] = y
+ s.sparse[y] = i
+ s.dense = s.dense[:len(s.dense)-1]
+ }
+}
+
+// pop removes an arbitrary element from the set.
+// The set must be nonempty.
+func (s *sparseSet) pop() ID {
+ x := s.dense[len(s.dense)-1]
+ s.dense = s.dense[:len(s.dense)-1]
+ return x
+}
+
+func (s *sparseSet) clear() {
+ s.dense = s.dense[:0]
+}
+
+func (s *sparseSet) contents() []ID {
+ return s.dense
+}
diff --git a/src/cmd/internal/ssa/ssac/.gitignore b/src/cmd/internal/ssa/ssac/.gitignore
new file mode 100644
index 0000000..ab17b9d
--- /dev/null
+++ b/src/cmd/internal/ssa/ssac/.gitignore
@@ -0,0 +1 @@
+ssac
diff --git a/src/cmd/internal/ssa/ssac/fib.goir b/src/cmd/internal/ssa/ssac/fib.goir
new file mode 100644
index 0000000..b572cda
--- /dev/null
+++ b/src/cmd/internal/ssa/ssac/fib.goir
@@ -0,0 +1,46 @@
+ (TYPE T127bd68 int)
+ (TYPE T127bd68 int)
+ (TYPE T127bd68 int)
+ (TYPE T127bd68 int)
+ (TYPE T7faedc523360 (FUNC (int) (int)))
+ (TYPE T127bd68 int)
+ (TYPE T127bd68 int)
+ (TYPE T7faedc523360 (FUNC (int) (int)))
+ (TYPE T127bd68 int)
+ (TYPE T127bd68 int)
+ (TYPE T127bd68 int)
+ (TYPE T127bd68 int)
+ (TYPE T127bd68 int)
+ (TYPE T127bd68 int)
+ (DCL n T127bd68)
+ (DCL ~r1 T127bd68)
+ (DCL n T127bd68)
+ (DCL autotmp_0000 T127bd68)
+ (DCL fib T7faedc523360)
+ (DCL n T127bd68)
+ (DCL autotmp_0001 T127bd68)
+ (DCL fib T7faedc523360)
+ (DCL n T127bd68)
+ (DCL ~r1 T127bd68)
+ (DCL autotmp_0000 T127bd68)
+ (DCL autotmp_0001 T127bd68)
+ (DCL autotmp_0001 T127bd68)
+ (DCL autotmp_0000 T127bd68)
+ (IF (LT n (CINT 2)) .then0 .else0)
+ (LABEL .then0)
+ (AS ~r1 n)
+ (AS (SP T127bd68 8) ~r1)
+ (RETURN)
+ (GOTO .end0)
+ (LABEL .else0)
+ (GOTO .end0)
+ (LABEL .end0)
+ (AS (SP T127bd68 0) (SUB n (CINT 1)))
+ (CALL fib)
+ (AS autotmp_0000 (LOAD (SP T127bd68 8)))
+ (AS (SP T127bd68 0) (SUB n (CINT 2)))
+ (CALL fib)
+ (AS autotmp_0001 (LOAD (SP T127bd68 8)))
+ (AS ~r1 (ADD autotmp_0000 autotmp_0001))
+ (AS (SP T127bd68 8) ~r1)
+ (RETURN)
diff --git a/src/cmd/internal/ssa/ssac/fibiter.goir b/src/cmd/internal/ssa/ssac/fibiter.goir
new file mode 100644
index 0000000..43c7a3d
--- /dev/null
+++ b/src/cmd/internal/ssa/ssac/fibiter.goir
@@ -0,0 +1,62 @@
+ (NAME runtime·fibiter)
+ (TYPE Tf5dd68 int)
+ (TYPE Tf5dd68 int)
+ (TYPE Tf5dd68 int)
+ (TYPE Tf5dd68 int)
+ (TYPE Tf5dd68 int)
+ (TYPE Tf5dd68 int)
+ (TYPE Tf5dd68 int)
+ (TYPE Tf5dd68 int)
+ (TYPE Tf5dd68 int)
+ (TYPE Tf5dd68 int)
+ (TYPE Tf5dd68 int)
+ (TYPE Tf5dd68 int)
+ (TYPE Tf5dd68 int)
+ (TYPE Tf5dd68 int)
+ (TYPE Tf5dd68 int)
+ (TYPE Tf5dd68 int)
+ (TYPE Tf5dd68 int)
+ (TYPE Tf5dd68 int)
+ (TYPE Tf5dd68 int)
+ (TYPE Tf5dd68 int)
+ (TYPE Tf5dd68 int)
+ (TYPE Tf5dd68 int)
+ (DCL a Tf5dd68)
+ (DCL a Tf5dd68)
+ (DCL b Tf5dd68)
+ (DCL b Tf5dd68)
+ (DCL i Tf5dd68)
+ (DCL i Tf5dd68)
+ (DCL i Tf5dd68)
+ (DCL n Tf5dd68)
+ (DCL autotmp_0002 Tf5dd68)
+ (DCL i Tf5dd68)
+ (DCL i Tf5dd68)
+ (DCL autotmp_0002 Tf5dd68)
+ (DCL autotmp_0002 Tf5dd68)
+ (DCL autotmp_0003 Tf5dd68)
+ (DCL a Tf5dd68)
+ (DCL b Tf5dd68)
+ (DCL a Tf5dd68)
+ (DCL b Tf5dd68)
+ (DCL b Tf5dd68)
+ (DCL autotmp_0003 Tf5dd68)
+ (DCL ~r1 Tf5dd68)
+ (DCL a Tf5dd68)
+ (AS n (LOAD (SP Tf5dd68 0)))
+ (AS a (CINT 0))
+ (AS b (CINT 1))
+ (AS i (CINT 0))
+ (GOTO .top0)
+ (LABEL .top0)
+ (IF (LT i n) .body0 .end0)
+ (LABEL .body0)
+ (AS autotmp_0003 (ADD a b))
+ (AS a b)
+ (AS b autotmp_0003)
+ (AS autotmp_0002 i)
+ (AS i (ADD autotmp_0002 (CINT 1)))
+ (GOTO .top0)
+ (LABEL .end0)
+ (AS (SP Tf5dd68 8) a)
+ (RETURN)
diff --git a/src/cmd/internal/ssa/ssac/main.go b/src/cmd/internal/ssa/ssac/main.go
new file mode 100644
index 0000000..4975b50
--- /dev/null
+++ b/src/cmd/internal/ssa/ssac/main.go
@@ -0,0 +1,436 @@
+// 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 main
+
+// Stub package for testing ssa compiler backend. Will eventually
+// be deleted when ssa is called directly from the main compiler.
+
+import (
+ "bufio"
+ "flag"
+ "fmt"
+ "io"
+ "os"
+ "strconv"
+ "strings"
+
+ "cmd/internal/ssa/types"
+
+ "cmd/internal/ssa"
+)
+
+// testing harness which runs the compiler using an IR read from a file
+func main() {
+ flag.Parse()
+ file := flag.Arg(0)
+ r, err := os.Open(file)
+ if err != nil {
+ panic(err)
+ }
+ f := buildFunc(readFunc(r))
+ ssa.Compile(f)
+ // TODO: output f
+}
+
+// readFunc reads the intermediate representation generated by the
+// compiler frontend and returns it as a list of sexpressions.
+func readFunc(r io.Reader) []sexpr {
+ var lines []sexpr
+ s := bufio.NewScanner(r)
+ for s.Scan() {
+ line := s.Text()
+ e := parseSexpr(strings.Trim(line, " "))
+
+ if !e.compound {
+ panic("bad stmt: " + line)
+ }
+ if e.parts[0].compound {
+ panic("bad op: " + line)
+ }
+ lines = append(lines, e)
+ }
+ return lines
+}
+
+// buildFunc converts from the 6g IR dump format to the internal
+// form. Builds SSA and all that.
+func buildFunc(lines []sexpr) *ssa.Func {
+ f := new(ssa.Func)
+
+ // We construct SSA using an algorithm similar to
+ // Brau, Buchwald, Hack, Leißa, Mallon, and Zwinkau
+ // http://pp.info.uni-karlsruhe.de/uploads/publikationen/braun13cc.pdf
+
+ // allocate starting block
+ f.Entry = f.NewBlock(ssa.BlockPlain)
+ // TODO: all args. Make a struct containing args/returnvals, declare
+ // an FP which contains a pointer to that struct.
+
+ var exit *ssa.Block // all returns (if any) branch to here TODO: defers & panics?
+
+ // add a block for each label
+ // Also a few other preprocessing steps, all in one pass.
+ labels := map[string]*ssa.Block{}
+ types := map[string]ssa.Type{}
+ callFallthrough := map[int]*ssa.Block{}
+ for i, e := range lines {
+ switch e.parts[0].name {
+ case "LABEL":
+ labels[e.parts[1].name] = f.NewBlock(ssa.BlockPlain)
+ case "NAME":
+ f.Name = e.parts[1].name
+ case "RETURN":
+ if exit == nil {
+ exit = f.NewBlock(ssa.BlockExit)
+ }
+ case "TYPE":
+ types[e.parts[1].name] = parseSexprType(e.parts[2])
+ case "CALL":
+ // allocate a new block for fallthrough
+ callFallthrough[i] = f.NewBlock(ssa.BlockPlain)
+ if exit == nil {
+ exit = f.NewBlock(ssa.BlockExit)
+ }
+ }
+ }
+
+ // map from block id to sexprs in that block
+ blocklines := make([][]sexpr, f.NumBlocks())
+
+ // Add sexprs to the correct block. Add edges between blocks.
+ b := f.Entry
+ var i int
+ for j, e := range lines {
+ if b == nil && e.parts[0].name != "LABEL" {
+ // dead code (e.g. return in "if" branch makes the "goto end" statement dead)
+ continue
+ }
+ switch e.parts[0].name {
+ case "IF":
+ if b.Kind != ssa.BlockPlain {
+ panic("bad b state")
+ }
+ b.Kind = ssa.BlockIf
+ edge(b, labels[e.parts[2].name])
+ edge(b, labels[e.parts[3].name])
+ blocklines[b.ID] = lines[i : j+1]
+ b = nil
+ case "GOTO":
+ edge(b, labels[e.parts[1].name])
+ blocklines[b.ID] = lines[i:j]
+ b = nil
+ case "LABEL":
+ b = labels[e.parts[1].name]
+ i = j + 1
+ case "RETURN":
+ if b.Kind != ssa.BlockPlain {
+ panic("bad b state")
+ }
+ edge(b, exit)
+ blocklines[b.ID] = lines[i:j]
+ b = nil
+ case "CALL":
+ if b.Kind != ssa.BlockPlain {
+ panic("bad b state")
+ }
+ b.Kind = ssa.BlockCall
+ c := callFallthrough[j]
+ edge(b, c)
+ edge(b, exit)
+ blocklines[b.ID] = lines[i : j+1]
+ b = c
+ i = j + 1
+ }
+ // note that we don't keep goto/label/return sexprs
+ }
+ if b != nil {
+ panic("control flow falls off end of function")
+ }
+
+ // Read types for each variable
+ // Number the variables densely
+ varids := map[string]int{} // map from variable name to id
+ var varnames []string // map from id to variable name
+ var vartypes []ssa.Type // map from variable id to type
+ for _, e := range lines {
+ if e.parts[0].name != "DCL" {
+ continue
+ }
+ name := e.parts[1].name
+ if _, ok := varids[name]; ok {
+ continue
+ }
+ id := len(varids)
+ if id == 1<<31-1 {
+ panic("too many variables")
+ }
+ fmt.Printf("var %d = %s\n", id, name)
+ varids[name] = id
+ varnames = append(varnames, name)
+ vartypes = append(vartypes, types[e.parts[2].name])
+ }
+ memID := len(varids)
+ fmt.Printf("var %d = .mem\n", memID)
+ varids[".mem"] = memID // TODO: need .mem here?
+ varnames = append(varnames, ".mem")
+ vartypes = append(vartypes, ssa.TypeMem)
+
+ // map from variable ID to current Value of that variable
+ curBlock := NewSparseMap(len(varids))
+
+ var state ssaFuncState
+ state.types = types
+ state.varids = varids
+ state.varnames = varnames
+ state.vartypes = vartypes
+ state.curBlock = curBlock
+ state.done = make([]bool, f.NumBlocks())
+ state.defs = map[blockvar]*ssa.Value{}
+ state.memID = memID
+
+ // Convert each block to ssa
+ // TODO: order blocks for maximum happiness - we want to process
+ // all the predecessors of a block before processing the block itself,
+ // if at all possible.
+ for _, b := range f.Blocks {
+ fmt.Printf("processing block %d\n", b.ID)
+ curBlock.Clear()
+ for _, e := range blocklines[b.ID] {
+ switch e.parts[0].name {
+ case "AS":
+ if e.parts[1].compound {
+ // store expression
+ lhs := genExpr(&state, b, e.parts[1])
+ rhs := genExpr(&state, b, e.parts[2])
+ mem := genVar(&state, b, memID)
+ v := b.NewValue(ssa.OpStore, ssa.TypeMem, nil)
+ v.AddArg(lhs)
+ v.AddArg(rhs)
+ v.AddArg(mem)
+ curBlock.Put(memID, v)
+ } else {
+ // variable assignment
+ v := genExpr(&state, b, e.parts[2])
+ curBlock.Put(varids[e.parts[1].name], v)
+ }
+ case "DCL":
+ // nothing to do
+ case "IF":
+ b.Control = genExpr(&state, b, e.parts[1])
+ case "CALL":
+ // only direct call for now - indirect call takes addr value as well
+ v := b.NewValue(ssa.OpStaticCall, ssa.TypeMem, e.parts[1].name)
+ v.AddArg(genVar(&state, b, memID))
+ curBlock.Put(memID, v)
+ b.Control = v
+ }
+ }
+ // link up thunks to their actual values
+ for _, v := range b.Values {
+ if v.Op != ssa.OpThunk {
+ continue
+ }
+ varid := v.Aux.(int)
+ w := genVar(&state, b, varid)
+ v.Op = ssa.OpCopy
+ v.Aux = nil
+ v.AddArg(w)
+ }
+
+ // record final values at the end of the block
+ for _, e := range curBlock.Contents() {
+ state.defs[blockvar{b.ID, e.Key}] = e.Val
+ // TODO: somehow avoid storing dead values to this map.
+ }
+ curBlock.Clear()
+ state.done[b.ID] = true
+ }
+
+ // the final store value is returned
+ if exit != nil {
+ exit.Control = genVar(&state, exit, memID)
+ }
+
+ return f
+}
+
+func edge(a, b *ssa.Block) {
+ a.Succs = append(a.Succs, b)
+ b.Preds = append(b.Preds, a)
+}
+
+func genVar(state *ssaFuncState, b *ssa.Block, id int) *ssa.Value {
+ // look up variable
+ v := state.curBlock.Get(id)
+ if v != nil {
+ // variable was defined previously in this block
+ // (or we memoized the result)
+ return v
+ }
+
+ // Variable comes in from outside of basic block.
+ v = lookupVarIncoming(state, b, id)
+
+ // memoize result so future callers will not look it up again
+ state.curBlock.Put(id, v)
+ return v
+}
+
+func genExpr(state *ssaFuncState, b *ssa.Block, e sexpr) *ssa.Value {
+ if !e.compound {
+ return genVar(state, b, state.varids[e.name])
+ }
+ switch e.parts[0].name {
+ case "ADD":
+ x := genExpr(state, b, e.parts[1])
+ y := genExpr(state, b, e.parts[2])
+ v := b.NewValue(ssa.OpAdd, x.Type, nil)
+ v.AddArg(x)
+ v.AddArg(y)
+ return v
+ case "SUB":
+ x := genExpr(state, b, e.parts[1])
+ y := genExpr(state, b, e.parts[2])
+ v := b.NewValue(ssa.OpSub, x.Type, nil)
+ v.AddArg(x)
+ v.AddArg(y)
+ return v
+ case "CINT":
+ c, err := strconv.ParseInt(e.parts[1].name, 10, 64)
+ if err != nil {
+ panic("bad cint value")
+ }
+ return b.Func.ConstInt(c)
+ case "LT":
+ x := genExpr(state, b, e.parts[1])
+ y := genExpr(state, b, e.parts[2])
+ v := b.NewValue(ssa.OpLess, ssa.TypeBool, nil)
+ v.AddArg(x)
+ v.AddArg(y)
+ return v
+ case "FP":
+ typ := state.types[e.parts[1].name]
+ offset, err := strconv.ParseInt(e.parts[2].name, 10, 64)
+ if err != nil {
+ panic(err)
+ }
+ v := b.NewValue(ssa.OpFPAddr, types.NewPointer(typ), offset)
+ return v
+ case "SP":
+ typ := state.types[e.parts[1].name]
+ offset, err := strconv.ParseInt(e.parts[2].name, 10, 64)
+ if err != nil {
+ panic(err)
+ }
+ v := b.NewValue(ssa.OpSPAddr, types.NewPointer(typ), offset)
+ return v
+ case "LOAD":
+ p := genExpr(state, b, e.parts[1])
+ v := b.NewValue(ssa.OpLoad, p.Type.(*types.Pointer).Elem(), nil)
+ v.AddArg(p)
+ v.AddArg(genVar(state, b, state.memID))
+ return v
+ default:
+ fmt.Println(e.parts[0].name)
+ panic("unknown op")
+ }
+}
+
+// map key combining block id and variable id
+type blockvar struct {
+ bid ssa.ID
+ varid int
+}
+
+type ssaFuncState struct {
+ types map[string]ssa.Type
+ varnames []string
+ varids map[string]int
+ vartypes []ssa.Type
+ curBlock *SparseMap // value of each variable in block we're working on
+ defs map[blockvar]*ssa.Value // values for variables at the end of blocks
+ done []bool
+ memID int
+}
+
+// Find the value of the variable with the given id leaving block b.
+func lookupVarOutgoing(state *ssaFuncState, b *ssa.Block, id int) *ssa.Value {
+ fmt.Printf("lookupOutgoing var=%d block=%d\n", id, b.ID)
+ v := state.defs[blockvar{b.ID, id}]
+ if v != nil {
+ return v
+ }
+ if state.done[b.ID] {
+ // The variable was not defined in this block, and we haven't
+ // memoized the answer yet. Look it up recursively. This might
+ // cause infinite recursion, so add a copy first.
+ v = b.NewValue(ssa.OpCopy, state.vartypes[id], nil)
+ state.defs[blockvar{b.ID, id}] = v
+ v.AddArg(lookupVarIncoming(state, b, id))
+ return v
+ }
+ // We don't know about defined variables in this block (yet).
+ // Make a thunk for this variable.
+ fmt.Printf("making thunk for var=%d in block=%d\n", id, b.ID)
+ v = b.NewValue(ssa.OpThunk, state.vartypes[id], id)
+
+ // memoize result
+ state.defs[blockvar{b.ID, id}] = v
+ return v
+}
+
+// Find the Value of the variable coming into block b.
+func lookupVarIncoming(state *ssaFuncState, b *ssa.Block, id int) *ssa.Value {
+ fmt.Printf("lookupIncoming var=%d block=%d\n", id, b.ID)
+ var v *ssa.Value
+ switch len(b.Preds) {
+ case 0:
+ // TODO: handle function args some other way (assignments in starting block?)
+ // TODO: error if variable isn't a function arg (including mem input)
+ v = b.NewValue(ssa.OpArg, state.vartypes[id], state.varnames[id])
+ case 1:
+ v = lookupVarOutgoing(state, b.Preds[0], id)
+ default:
+ v = b.NewValue(ssa.OpCopy, state.vartypes[id], nil)
+
+ args := make([]*ssa.Value, len(b.Preds))
+ for i, p := range b.Preds {
+ args[i] = lookupVarOutgoing(state, p, id)
+ }
+
+ // if <=1 value that isn't this variable's thunk, don't make phi
+ v.Op = ssa.OpPhi
+ v.AddArgs(args...) // note: order corresponding to b.Pred
+ }
+ return v
+}
+
+func parseSexprType(e sexpr) ssa.Type {
+ if !e.compound {
+ switch e.name {
+ case "int":
+ return ssa.TypeInt
+ default:
+ fmt.Println(e.name)
+ panic("unknown type")
+ }
+ }
+ if e.parts[0].name == "FUNC" {
+ // TODO: receiver? Already folded into args? Variadic?
+ var args, rets []*types.Var
+ for _, s := range e.parts[1].parts {
+ t := parseSexprType(s)
+ args = append(args, types.NewParam(0, nil, "noname", t))
+ }
+ for _, s := range e.parts[2].parts {
+ t := parseSexprType(s)
+ rets = append(rets, types.NewParam(0, nil, "noname", t))
+ }
+ sig := types.NewSignature(nil, nil, types.NewTuple(args...), types.NewTuple(rets...), false)
+ return ssa.Type(sig)
+ }
+ // TODO: array/struct/...
+ panic("compound type")
+}
diff --git a/src/cmd/internal/ssa/ssac/sexpr.go b/src/cmd/internal/ssa/ssac/sexpr.go
new file mode 100644
index 0000000..77e8923
--- /dev/null
+++ b/src/cmd/internal/ssa/ssac/sexpr.go
@@ -0,0 +1,82 @@
+// 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 main
+
+import "strings"
+
+// an sexpr is an s-expression. It is either a token or a
+// parenthesized list of s-expressions.
+//
+// Used just for initial development. Should we keep it for testing, or
+// ditch it once we've plugged into the main compiler output?
+
+type sexpr struct {
+ compound bool
+ name string // !compound
+ parts []sexpr // compound
+}
+
+func (s *sexpr) String() string {
+ if !s.compound {
+ return s.name
+ }
+ x := "("
+ for i, p := range s.parts {
+ if i != 0 {
+ x += " "
+ }
+ x += p.String()
+ }
+ return x + ")"
+}
+
+func parseSexpr(s string) sexpr {
+ var e string
+ e, s = grabOne(s)
+ if len(e) > 0 && e[0] == '(' {
+ e = e[1 : len(e)-1]
+ var parts []sexpr
+ for e != "" {
+ var p string
+ p, e = grabOne(e)
+ parts = append(parts, parseSexpr(p))
+ }
+ return sexpr{true, "", parts}
+ }
+ return sexpr{false, e, nil}
+}
+
+// grabOne peels off first token or parenthesized string from s.
+// returns first thing and the remainder of s.
+func grabOne(s string) (string, string) {
+ for len(s) > 0 && s[0] == ' ' {
+ s = s[1:]
+ }
+ if len(s) == 0 || s[0] != '(' {
+ i := strings.Index(s, " ")
+ if i < 0 {
+ return s, ""
+ }
+ return s[:i], s[i:]
+ }
+ d := 0
+ i := 0
+ for {
+ if len(s) == i {
+ panic("unterminated s-expression: " + s)
+ }
+ if s[i] == '(' {
+ d++
+ }
+ if s[i] == ')' {
+ d--
+ if d == 0 {
+ i++
+ return s[:i], s[i:]
+ }
+ }
+ i++
+ }
+}
diff --git a/src/cmd/internal/ssa/ssac/sparsemap.go b/src/cmd/internal/ssa/ssac/sparsemap.go
new file mode 100644
index 0000000..b7a0fb0
--- /dev/null
+++ b/src/cmd/internal/ssa/ssac/sparsemap.go
@@ -0,0 +1,69 @@
+// 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 main
+
+// Maintains a map[int]*ssa.Value, but cheaper.
+
+// from http://research.swtch.com/sparse
+// in turn, from Briggs and Torczon
+
+import (
+ "cmd/internal/ssa"
+)
+
+type SparseMap struct {
+ dense []SparseMapEntry
+ sparse []int
+}
+type SparseMapEntry struct {
+ Key int
+ Val *ssa.Value
+}
+
+// NewSparseMap returns a SparseMap that can have
+// integers between 0 and n-1 as keys.
+func NewSparseMap(n int) *SparseMap {
+ return &SparseMap{nil, make([]int, n)}
+}
+
+func (s *SparseMap) Get(x int) *ssa.Value {
+ i := s.sparse[x]
+ if i < len(s.dense) && s.dense[i].Key == x {
+ return s.dense[i].Val
+ }
+ return nil
+}
+
+func (s *SparseMap) Put(x int, v *ssa.Value) {
+ i := s.sparse[x]
+ if i < len(s.dense) && s.dense[i].Key == x {
+ s.dense[i].Val = v
+ return
+ }
+ i = len(s.dense)
+ s.dense = append(s.dense, SparseMapEntry{x, v})
+ s.sparse[x] = i
+}
+
+func (s *SparseMap) Remove(x int) {
+ i := s.sparse[x]
+ if i < len(s.dense) && s.dense[i].Key == x {
+ y := s.dense[len(s.dense)-1]
+ s.dense[i] = y
+ s.sparse[y.Key] = i
+ s.dense = s.dense[:len(s.dense)-1]
+ }
+}
+
+func (s *SparseMap) Clear() {
+ s.dense = s.dense[:0]
+}
+
+// Contents returns a slice of key/value pairs.
+// Caller must not modify any returned entries.
+// The return value is invalid after the SparseMap is modified in any way.
+func (s *SparseMap) Contents() []SparseMapEntry {
+ return s.dense
+}
diff --git a/src/cmd/internal/ssa/type.go b/src/cmd/internal/ssa/type.go
new file mode 100644
index 0000000..3389622
--- /dev/null
+++ b/src/cmd/internal/ssa/type.go
@@ -0,0 +1,84 @@
+// 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/ssa/types" // TODO: use golang.org/x/tools/go/types instead
+)
+
+// We just inherit types from go/types
+type Type types.Type
+
+var (
+ // shortcuts for commonly used basic types
+ TypeInt = types.Typ[types.Int]
+ TypeUint = types.Typ[types.Uint]
+ TypeInt8 = types.Typ[types.Int8]
+ TypeInt16 = types.Typ[types.Int16]
+ TypeInt32 = types.Typ[types.Int32]
+ TypeInt64 = types.Typ[types.Int64]
+ TypeUint8 = types.Typ[types.Uint8]
+ TypeUint16 = types.Typ[types.Uint16]
+ TypeUint32 = types.Typ[types.Uint32]
+ TypeUint64 = types.Typ[types.Uint64]
+ TypeUintptr = types.Typ[types.Uintptr]
+ TypeBool = types.Typ[types.Bool]
+ TypeString = types.Typ[types.String]
+
+ TypeInvalid = types.Typ[types.Invalid]
+
+ // Additional compiler-only types go here.
+ TypeMem = &Memory{}
+ TypeFlags = &Flags{}
+)
+
+// typeIdentical returns whether it two arguments are the same type.
+func typeIdentical(t, u Type) bool {
+ if t == TypeMem {
+ return u == TypeMem
+ }
+ if t == TypeFlags {
+ return u == TypeFlags
+ }
+ return types.Identical(t, u)
+}
+
+// A type representing all of memory
+type Memory struct {
+}
+
+func (t *Memory) Underlying() types.Type { panic("Underlying of Memory") }
+func (t *Memory) String() string { return "mem" }
+
+// A type representing the unknown type
+type Unknown struct {
+}
+
+func (t *Unknown) Underlying() types.Type { panic("Underlying of Unknown") }
+func (t *Unknown) String() string { return "unk" }
+
+// A type representing the void type. Used during building, should always
+// be eliminated by the first deadcode pass.
+type Void struct {
+}
+
+func (t *Void) Underlying() types.Type { panic("Underlying of Void") }
+func (t *Void) String() string { return "void" }
+
+// A type representing the results of a nil check or bounds check.
+// TODO: or type check?
+// TODO: just use bool?
+type Check struct {
+}
+
+func (t *Check) Underlying() types.Type { panic("Underlying of Check") }
+func (t *Check) String() string { return "check" }
+
+// x86 flags type
+type Flags struct {
+}
+
+func (t *Flags) Underlying() types.Type { panic("Underlying of Flags") }
+func (t *Flags) String() string { return "flags" }
diff --git a/src/cmd/internal/ssa/types/object.go b/src/cmd/internal/ssa/types/object.go
new file mode 100644
index 0000000..cd0be16
--- /dev/null
+++ b/src/cmd/internal/ssa/types/object.go
@@ -0,0 +1,39 @@
+// 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.
+
+// This package is a drop-in replacement for go/types
+// for use until go/types is included in the main repo.
+
+package types
+
+// An Object describes a named language entity such as a package,
+// constant, type, variable, function (incl. methods), or label.
+// All objects implement the Object interface.
+//
+type Object interface {
+ Name() string // package local object name
+ Type() Type // object type
+}
+
+// An object implements the common parts of an Object.
+type object struct {
+ name string
+ typ Type
+}
+
+func (obj *object) Name() string { return obj.name }
+func (obj *object) Type() Type { return obj.typ }
+
+// A Variable represents a declared variable (including function parameters and results, and struct fields).
+type Var struct {
+ object
+ anonymous bool // if set, the variable is an anonymous struct field, and name is the type name
+ visited bool // for initialization cycle detection
+ isField bool // var is struct field
+ used bool // set if the variable was used
+}
+
+func NewParam(pos int, pkg *int, name string, typ Type) *Var {
+ return &Var{object: object{name, typ}, used: true} // parameters are always 'used'
+}
diff --git a/src/cmd/internal/ssa/types/type.go b/src/cmd/internal/ssa/types/type.go
new file mode 100644
index 0000000..e01de5c
--- /dev/null
+++ b/src/cmd/internal/ssa/types/type.go
@@ -0,0 +1,229 @@
+// 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.
+
+// This package is a drop-in replacement for go/types
+// for use until go/types is included in the main repo.
+
+package types
+
+// A Type represents a type of Go.
+// All types implement the Type interface.
+type Type interface {
+ // Underlying returns the underlying type of a type.
+ Underlying() Type
+
+ // String returns a string representation of a type.
+ String() string
+}
+
+// BasicKind describes the kind of basic type.
+type BasicKind int
+
+const (
+ Invalid BasicKind = iota // type is invalid
+
+ // predeclared types
+ Bool
+ Int
+ Int8
+ Int16
+ Int32
+ Int64
+ Uint
+ Uint8
+ Uint16
+ Uint32
+ Uint64
+ Uintptr
+ Float32
+ Float64
+ Complex64
+ Complex128
+ String
+ UnsafePointer
+
+ // types for untyped values
+ UntypedBool
+ UntypedInt
+ UntypedRune
+ UntypedFloat
+ UntypedComplex
+ UntypedString
+ UntypedNil
+
+ // aliases
+ Byte = Uint8
+ Rune = Int32
+)
+
+// BasicInfo is a set of flags describing properties of a basic type.
+type BasicInfo int
+
+// Properties of basic types.
+const (
+ IsBoolean BasicInfo = 1 << iota
+ IsInteger
+ IsUnsigned
+ IsFloat
+ IsComplex
+ IsString
+ IsUntyped
+
+ IsOrdered = IsInteger | IsFloat | IsString
+ IsNumeric = IsInteger | IsFloat | IsComplex
+ IsConstType = IsBoolean | IsNumeric | IsString
+)
+
+// A Basic represents a basic type.
+type Basic struct {
+ kind BasicKind
+ info BasicInfo
+ name string
+}
+
+// Kind returns the kind of basic type b.
+func (b *Basic) Kind() BasicKind { return b.kind }
+
+// Info returns information about properties of basic type b.
+func (b *Basic) Info() BasicInfo { return b.info }
+
+// Name returns the name of basic type b.
+func (b *Basic) Name() string { return b.name }
+
+// A Pointer represents a pointer type.
+type Pointer struct {
+ base Type // element type
+}
+
+// NewPointer returns a new pointer type for the given element (base) type.
+func NewPointer(elem Type) *Pointer { return &Pointer{base: elem} }
+
+// Elem returns the element type for the given pointer p.
+func (p *Pointer) Elem() Type { return p.base }
+
+// A Slice represents a slice type.
+type Slice struct {
+ elem Type
+}
+
+// NewSlice returns a new slice type for the given element type.
+func NewSlice(elem Type) *Slice { return &Slice{elem} }
+
+// Elem returns the element type of slice s.
+func (s *Slice) Elem() Type { return s.elem }
+
+// Implementations for Type methods.
+func (t *Basic) Underlying() Type { return t }
+func (t *Slice) Underlying() Type { return t }
+func (t *Pointer) Underlying() Type { return t }
+func (t *Signature) Underlying() Type { return t }
+
+func (b *Basic) String() string { return b.name }
+func (t *Slice) String() string { return "[]" + t.elem.String() }
+func (t *Pointer) String() string { return "*" + t.base.String() }
+func (t *Signature) String() string { return "sig" /* TODO */ }
+
+var Typ = [...]*Basic{
+ Invalid: {Invalid, 0, "invalid type"},
+
+ Bool: {Bool, IsBoolean, "bool"},
+ Int: {Int, IsInteger, "int"},
+ Int8: {Int8, IsInteger, "int8"},
+ Int16: {Int16, IsInteger, "int16"},
+ Int32: {Int32, IsInteger, "int32"},
+ Int64: {Int64, IsInteger, "int64"},
+ Uint: {Uint, IsInteger | IsUnsigned, "uint"},
+ Uint8: {Uint8, IsInteger | IsUnsigned, "uint8"},
+ Uint16: {Uint16, IsInteger | IsUnsigned, "uint16"},
+ Uint32: {Uint32, IsInteger | IsUnsigned, "uint32"},
+ Uint64: {Uint64, IsInteger | IsUnsigned, "uint64"},
+ Uintptr: {Uintptr, IsInteger | IsUnsigned, "uintptr"},
+ Float32: {Float32, IsFloat, "float32"},
+ Float64: {Float64, IsFloat, "float64"},
+ Complex64: {Complex64, IsComplex, "complex64"},
+ Complex128: {Complex128, IsComplex, "complex128"},
+ String: {String, IsString, "string"},
+ UnsafePointer: {UnsafePointer, 0, "Pointer"},
+
+ UntypedBool: {UntypedBool, IsBoolean | IsUntyped, "untyped bool"},
+ UntypedInt: {UntypedInt, IsInteger | IsUntyped, "untyped int"},
+ UntypedRune: {UntypedRune, IsInteger | IsUntyped, "untyped rune"},
+ UntypedFloat: {UntypedFloat, IsFloat | IsUntyped, "untyped float"},
+ UntypedComplex: {UntypedComplex, IsComplex | IsUntyped, "untyped complex"},
+ UntypedString: {UntypedString, IsString | IsUntyped, "untyped string"},
+ UntypedNil: {UntypedNil, IsUntyped, "untyped nil"},
+}
+
+// Identical reports whether x and y are identical.
+func Identical(x, y Type) bool {
+ if x == y {
+ return true
+ }
+
+ switch x := x.(type) {
+ case *Basic:
+ // Basic types are singletons except for the rune and byte
+ // aliases, thus we cannot solely rely on the x == y check
+ // above.
+ if y, ok := y.(*Basic); ok {
+ return x.kind == y.kind
+ }
+ default:
+ panic("can't handle yet")
+ }
+ return false
+}
+
+// A Tuple represents an ordered list of variables; a nil *Tuple is a valid (empty) tuple.
+// Tuples are used as components of signatures and to represent the type of multiple
+// assignments; they are not first class types of Go.
+type Tuple struct {
+ vars []*Var
+}
+
+// NewTuple returns a new tuple for the given variables.
+func NewTuple(x ...*Var) *Tuple {
+ if len(x) > 0 {
+ return &Tuple{x}
+ }
+ return nil
+}
+
+// Len returns the number variables of tuple t.
+func (t *Tuple) Len() int {
+ if t != nil {
+ return len(t.vars)
+ }
+ return 0
+}
+
+// At returns the i'th variable of tuple t.
+func (t *Tuple) At(i int) *Var { return t.vars[i] }
+
+// A Signature represents a (non-builtin) function or method type.
+type Signature struct {
+ recv *Var // nil if not a method
+ params *Tuple // (incoming) parameters from left to right; or nil
+ results *Tuple // (outgoing) results from left to right; or nil
+ variadic bool // true if the last parameter's type is of the form ...T (or string, for append built-in only)
+}
+
+// NewSignature returns a new function type for the given receiver, parameters,
+// and results, either of which may be nil. If variadic is set, the function
+// is variadic, it must have at least one parameter, and the last parameter
+// must be of unnamed slice type.
+func NewSignature(scope *int, recv *Var, params, results *Tuple, variadic bool) *Signature {
+ // TODO(gri) Should we rely on the correct (non-nil) incoming scope
+ // or should this function allocate and populate a scope?
+ if variadic {
+ n := params.Len()
+ if n == 0 {
+ panic("types.NewSignature: variadic function must have at least one parameter")
+ }
+ if _, ok := params.At(n - 1).typ.(*Slice); !ok {
+ panic("types.NewSignature: variadic parameter must be of unnamed slice type")
+ }
+ }
+ return &Signature{recv, params, results, variadic}
+}
diff --git a/src/cmd/internal/ssa/value.go b/src/cmd/internal/ssa/value.go
new file mode 100644
index 0000000..740525a
--- /dev/null
+++ b/src/cmd/internal/ssa/value.go
@@ -0,0 +1,117 @@
+// 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 (
+ "fmt"
+ "strings"
+)
+
+// A Value represents a value in the SSA representation of the program.
+// The ID and Type fields must not be modified. The remainder may be modified
+// if they preserve the value of the Value (e.g. changing a (mul 2 x) to an (add x x)).
+type Value struct {
+ // A unique identifier for the value. For performance we allocate these IDs
+ // densely starting at 0. There is no guarantee that there won't be occasional holes, though.
+ ID ID
+
+ // The operation that computes this value. See op.go.
+ Op Op
+
+ // The type of this value. Normally this will be a Go type, but there
+ // are a few other pseudo-types, see type.go.
+ Type Type
+
+ // Auxiliary info for this value. The type of this information depends on the opcode (& type).
+ Aux interface{}
+
+ // Arguments of this value
+ Args []*Value
+
+ // Containing basic block
+ Block *Block
+
+ // Storage for the first two args
+ argstorage [2]*Value
+}
+
+// Examples:
+// Opcode aux args
+// OpAdd nil 2
+// OpConstStr string 0
+// OpConstInt int64 0
+// OpAddcq int64 1 amd64 op: v = arg[0] + constant
+
+// short form print. Just v#.
+func (v *Value) String() string {
+ return fmt.Sprintf("v%d", v.ID)
+}
+
+// long form print. v# = opcode <type> [aux] args [: reg]
+func (v *Value) LongString() string {
+ s := fmt.Sprintf("v%d = %s", v.ID, strings.TrimPrefix(v.Op.String(), "Op"))
+ s += " <" + v.Type.String() + ">"
+ if v.Aux != nil {
+ s += fmt.Sprintf(" [%v]", v.Aux)
+ }
+ for _, a := range v.Args {
+ s += fmt.Sprintf(" %v", a)
+ }
+ r := v.Block.Func.RegAlloc
+ if r != nil && r[v.ID] != nil {
+ s += " : " + r[v.ID].Name()
+ }
+ return s
+}
+
+func (v *Value) AddArg(w *Value) {
+ v.Args = append(v.Args, w)
+}
+func (v *Value) AddArgs(a ...*Value) {
+ v.Args = append(v.Args, a...)
+}
+func (v *Value) SetArg(i int, w *Value) {
+ v.Args[i] = w
+}
+func (v *Value) RemoveArg(i int) {
+ copy(v.Args[i:], v.Args[i+1:])
+ v.Args = v.Args[:len(v.Args)-1]
+}
+func (v *Value) SetArgs1(a *Value) {
+ v.resetArgs()
+ v.AddArg(a)
+}
+func (v *Value) SetArgs2(a *Value, b *Value) {
+ v.resetArgs()
+ v.AddArg(a)
+ v.AddArg(b)
+}
+
+func (v *Value) resetArgs() {
+ v.argstorage[0] = nil
+ v.argstorage[1] = nil
+ v.Args = v.argstorage[:0]
+}
+
+// CopyFrom converts v to be the same value as w. v and w must
+// have the same type.
+func (v *Value) CopyFrom(w *Value) {
+ if !typeIdentical(v.Type, w.Type) {
+ panic("copyFrom with unequal types")
+ }
+ v.Op = w.Op
+ v.Aux = w.Aux
+ v.resetArgs()
+ v.AddArgs(w.Args...)
+}
+
+// SetType sets the type of v. v must not have had its type
+// set yet (it must be TypeInvalid).
+func (v *Value) SetType() {
+ if v.Type != TypeInvalid {
+ panic("setting type when it is already set")
+ }
+ opcodeTable[v.Op].typer(v)
+}
