[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

39 files changed, 5010 insertions, 0 deletions

diff --git a/src/cmd/compile/internal/ssa/TODO b/src/cmd/compile/internal/ssa/TODO
new file mode 100644
index 0000000000..afb723ae4c
--- /dev/null
+++ b/src/cmd/compile/internal/ssa/TODO
@@ -0,0 +1,47 @@
+This is a list of things that need to be worked on.  It is by no means complete.
+
+Allocation
+- Allocation of decls in stackalloc.  Decls survive if they are
+  addrtaken or are too large for registerization.
+
+Scheduling
+ - Make sure loads are scheduled correctly with respect to stores.
+   Same for flag type values.  We can't have more than one value of
+   mem or flag types live at once.
+ - Reduce register pressure.  Schedule instructions which kill
+   variables first.
+
+Values
+ - Add a line number field.  Figure out how to populate it and
+   maintain it during rewrites.
+ - Store *Type instead of Type?  Keep an array of used Types in Func
+   and reference by id?  Unify with the type ../gc so we just use a
+   pointer instead of an interface?
+ - Recycle dead values instead of using GC to do that.
+ - A lot of Aux fields are just int64.  Add a separate AuxInt field?
+   If not that, then cache the interfaces that wrap int64s.
+ - OpStore uses 3 args.  Increase the size of argstorage to 3?
+
+Opcodes
+ - Rename ops to prevent cross-arch conflicts.  MOVQ -> MOVQamd64 (or
+   MOVQ6?).  Other option: build opcode table in Config instead of globally.
+ - Remove asm string from opinfo, no longer needed.
+ - It's annoying to list the opcode both in the opcode list and an
+   opInfo map entry.  Specify it one place and use go:generate to
+   produce both?
+
+Regalloc
+ - Make less arch-dependent
+ - Don't spill everything at every basic block boundary.
+ - Allow args and return values to be ssa-able.
+ - Handle 2-address instructions.
+
+Rewrites
+ - Strength reduction (both arch-indep and arch-dependent?)
+ - Code sequence for shifts >= wordsize
+ - Start another architecture (arm?)
+
+Common-Subexpression Elimination
+ - Make better decision about which value in an equivalence class we should
+   choose to replace other values in that class.
+ - Can we move control values out of their basic block?
diff --git a/src/cmd/compile/internal/ssa/block.go b/src/cmd/compile/internal/ssa/block.go
new file mode 100644
index 0000000000..dcf3676bc2
--- /dev/null
+++ b/src/cmd/compile/internal/ssa/block.go
@@ -0,0 +1,94 @@
+// 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 successors 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 that define the operation of this block.
+	// The list must include the control value, if any. (TODO: need this last condition?)
+	// After the scheduling pass, this list is ordered.
+	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
+	// TODO(khr): BlockPanic for the built-in panic call, has 1 edge to the exit block
+	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/compile/internal/ssa/blockkind_string.go b/src/cmd/compile/internal/ssa/blockkind_string.go
new file mode 100644
index 0000000000..6204f1948f
--- /dev/null
+++ b/src/cmd/compile/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/compile/internal/ssa/cgen.go b/src/cmd/compile/internal/ssa/cgen.go
new file mode 100644
index 0000000000..51c72aacd9
--- /dev/null
+++ b/src/cmd/compile/internal/ssa/cgen.go
@@ -0,0 +1,135 @@
+// 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 (
+	"bytes"
+	"fmt"
+	"os"
+)
+
+// cgen selects machine instructions for the function.
+// This pass generates assembly output for now, but should
+// TODO(khr): generate binary output (via liblink?) instead of text.
+func cgen(f *Func) {
+	fmt.Printf("TEXT %s(SB),0,$0\n", f.Name) // TODO: frame size / arg size
+
+	// TODO: prolog, allocate stack frame
+
+	for idx, b := range f.Blocks {
+		fmt.Printf("%d:\n", b.ID)
+		for _, v := range b.Values {
+			var buf bytes.Buffer
+			asm := opcodeTable[v.Op].asm
+			buf.WriteString("        ")
+			for i := 0; i < len(asm); i++ {
+				switch asm[i] {
+				default:
+					buf.WriteByte(asm[i])
+				case '\t':
+					buf.WriteByte(' ')
+					for buf.Len()%8 != 0 {
+						buf.WriteByte(' ')
+					}
+				case '%':
+					i++
+					switch asm[i] {
+					case '%':
+						buf.WriteByte('%')
+					case 'I':
+						i++
+						n := asm[i] - '0'
+						if f.RegAlloc[v.Args[n].ID] != nil {
+							buf.WriteString(f.RegAlloc[v.Args[n].ID].Name())
+						} else {
+							fmt.Fprintf(&buf, "v%d", v.Args[n].ID)
+						}
+					case 'O':
+						i++
+						n := asm[i] - '0'
+						if n != 0 {
+							panic("can only handle 1 output for now")
+						}
+						if f.RegAlloc[v.ID] != nil {
+							buf.WriteString(f.RegAlloc[v.ID].Name())
+						} else {
+							fmt.Fprintf(&buf, "v%d", v.ID)
+						}
+					case 'A':
+						fmt.Fprint(&buf, v.Aux)
+					}
+				}
+			}
+			for buf.Len() < 40 {
+				buf.WriteByte(' ')
+			}
+			buf.WriteString("; ")
+			buf.WriteString(v.LongString())
+			buf.WriteByte('\n')
+			os.Stdout.Write(buf.Bytes())
+		}
+		// find next block in layout sequence
+		var next *Block
+		if idx < len(f.Blocks)-1 {
+			next = f.Blocks[idx+1]
+		}
+		// emit end of block code
+		// TODO: this is machine specific
+		switch b.Kind {
+		case BlockPlain:
+			if b.Succs[0] != next {
+				fmt.Printf("\tJMP\t%d\n", b.Succs[0].ID)
+			}
+		case BlockExit:
+			// TODO: run defers (if any)
+			// TODO: deallocate frame
+			fmt.Println("\tRET")
+		case BlockCall:
+			// nothing to emit - call instruction already happened
+		case BlockEQ:
+			if b.Succs[0] == next {
+				fmt.Printf("\tJNE\t%d\n", b.Succs[1].ID)
+			} else if b.Succs[1] == next {
+				fmt.Printf("\tJEQ\t%d\n", b.Succs[0].ID)
+			} else {
+				fmt.Printf("\tJEQ\t%d\n", b.Succs[0].ID)
+				fmt.Printf("\tJMP\t%d\n", b.Succs[1].ID)
+			}
+		case BlockNE:
+			if b.Succs[0] == next {
+				fmt.Printf("\tJEQ\t%d\n", b.Succs[1].ID)
+			} else if b.Succs[1] == next {
+				fmt.Printf("\tJNE\t%d\n", b.Succs[0].ID)
+			} else {
+				fmt.Printf("\tJNE\t%d\n", b.Succs[0].ID)
+				fmt.Printf("\tJMP\t%d\n", b.Succs[1].ID)
+			}
+		case BlockLT:
+			if b.Succs[0] == next {
+				fmt.Printf("\tJGE\t%d\n", b.Succs[1].ID)
+			} else if b.Succs[1] == next {
+				fmt.Printf("\tJLT\t%d\n", b.Succs[0].ID)
+			} else {
+				fmt.Printf("\tJLT\t%d\n", b.Succs[0].ID)
+				fmt.Printf("\tJMP\t%d\n", b.Succs[1].ID)
+			}
+		case BlockULT:
+			if b.Succs[0] == next {
+				fmt.Printf("\tJAE\t%d\n", b.Succs[1].ID)
+			} else if b.Succs[1] == next {
+				fmt.Printf("\tJB\t%d\n", b.Succs[0].ID)
+			} else {
+				fmt.Printf("\tJB\t%d\n", b.Succs[0].ID)
+				fmt.Printf("\tJMP\t%d\n", b.Succs[1].ID)
+			}
+		default:
+			fmt.Printf("\t%s ->", b.Kind.String())
+			for _, s := range b.Succs {
+				fmt.Printf(" %d", s.ID)
+			}
+			fmt.Printf("\n")
+		}
+	}
+}
diff --git a/src/cmd/compile/internal/ssa/check.go b/src/cmd/compile/internal/ssa/check.go
new file mode 100644
index 0000000000..667313ad9f
--- /dev/null
+++ b/src/cmd/compile/internal/ssa/check.go
@@ -0,0 +1,124 @@
+// 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.IsMemory() {
+				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.IsBoolean() {
+				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.IsMemory() {
+				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 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/compile/internal/ssa/compile.go b/src/cmd/compile/internal/ssa/compile.go
new file mode 100644
index 0000000000..c1f7956791
--- /dev/null
+++ b/src/cmd/compile/internal/ssa/compile.go
@@ -0,0 +1,115 @@
+// 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"
+	"log"
+)
+
+// 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},
+	{"generic cse", cse},
+	{"generic deadcode", deadcode},
+	{"fuse", fuse},
+	{"lower", lower},
+	{"lowered cse", cse},
+	{"lowered deadcode", deadcode},
+	{"critical", critical}, // remove critical edges
+	{"layout", layout},     // schedule blocks
+	{"schedule", schedule}, // schedule values
+	{"regalloc", regalloc},
+	{"stackalloc", stackalloc},
+	{"cgen", cgen},
+}
+
+// Double-check phase ordering constraints.
+// This code is intended to document the ordering requirements
+// between different phases.  It does not override the passes
+// list above.
+type constraint struct {
+	a, b string // a must come before b
+}
+
+var passOrder = [...]constraint{
+	// don't layout blocks until critical edges have been removed
+	{"critical", "layout"},
+	// regalloc requires the removal of all critical edges
+	{"critical", "regalloc"},
+	// regalloc requires all the values in a block to be scheduled
+	{"schedule", "regalloc"},
+	// stack allocation requires register allocation
+	{"regalloc", "stackalloc"},
+	// code generation requires stack allocation
+	{"stackalloc", "cgen"},
+}
+
+func init() {
+	for _, c := range passOrder {
+		a, b := c.a, c.b
+		i := -1
+		j := -1
+		for k, p := range passes {
+			if p.name == a {
+				i = k
+			}
+			if p.name == b {
+				j = k
+			}
+		}
+		if i < 0 {
+			log.Panicf("pass %s not found", a)
+		}
+		if j < 0 {
+			log.Panicf("pass %s not found", b)
+		}
+		if i >= j {
+			log.Panicf("passes %s and %s out of order", a, b)
+		}
+	}
+}
diff --git a/src/cmd/compile/internal/ssa/config.go b/src/cmd/compile/internal/ssa/config.go
new file mode 100644
index 0000000000..9f1d2a8593
--- /dev/null
+++ b/src/cmd/compile/internal/ssa/config.go
@@ -0,0 +1,48 @@
+// 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"
+
+type Config struct {
+	arch    string            // "amd64", etc.
+	ptrSize int64             // 4 or 8
+	Uintptr Type              // pointer arithmetic type
+	lower   func(*Value) bool // lowering function
+
+	// TODO: more stuff.  Compiler flags of interest, ...
+}
+
+// NewConfig returns a new configuration object for the given architecture.
+func NewConfig(arch string) *Config {
+	c := &Config{arch: arch}
+	switch arch {
+	case "amd64":
+		c.ptrSize = 8
+		c.lower = lowerAmd64
+	case "386":
+		c.ptrSize = 4
+		c.lower = lowerAmd64 // TODO(khr): full 32-bit support
+	default:
+		log.Fatalf("arch %s not implemented", arch)
+	}
+
+	// cache the intptr type in the config
+	c.Uintptr = TypeUInt32
+	if c.ptrSize == 8 {
+		c.Uintptr = TypeUInt64
+	}
+
+	return c
+}
+
+// NewFunc returns a new, empty function object
+func (c *Config) NewFunc() *Func {
+	// TODO(khr): should this function take name, type, etc. as arguments?
+	return &Func{Config: c}
+}
+
+// TODO(khr): do we really need a separate Config, or can we just
+// store all its fields inside a Func?
diff --git a/src/cmd/compile/internal/ssa/copyelim.go b/src/cmd/compile/internal/ssa/copyelim.go
new file mode 100644
index 0000000000..10c2dcc440
--- /dev/null
+++ b/src/cmd/compile/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/compile/internal/ssa/critical.go b/src/cmd/compile/internal/ssa/critical.go
new file mode 100644
index 0000000000..503681ffd3
--- /dev/null
+++ b/src/cmd/compile/internal/ssa/critical.go
@@ -0,0 +1,51 @@
+// 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
+
+// critical splits critical edges (those that go from a block with
+// more than one outedge to a block with more than one inedge).
+// Regalloc wants a critical-edge-free CFG so it can implement phi values.
+func critical(f *Func) {
+	for _, b := range f.Blocks {
+		if len(b.Preds) <= 1 {
+			continue
+		}
+
+		// decide if we need to split edges coming into b.
+		hasphi := false
+		for _, v := range b.Values {
+			if v.Op == OpPhi && v.Type != TypeMem {
+				hasphi = true
+				break
+			}
+		}
+		if !hasphi {
+			// no splitting needed
+			continue
+		}
+
+		// split input edges coming from multi-output blocks.
+		for i, c := range b.Preds {
+			if c.Kind == BlockPlain {
+				continue // only single output block
+			}
+
+			// allocate a new block to place on the edge
+			d := f.NewBlock(BlockPlain)
+
+			// splice it in
+			d.Preds = append(d.Preds, c)
+			d.Succs = append(d.Succs, b)
+			b.Preds[i] = d
+			// replace b with d in c's successor list.
+			for j, b2 := range c.Succs {
+				if b2 == b {
+					c.Succs[j] = d
+					break
+				}
+			}
+		}
+	}
+}
diff --git a/src/cmd/compile/internal/ssa/cse.go b/src/cmd/compile/internal/ssa/cse.go
new file mode 100644
index 0000000000..aba24aeabc
--- /dev/null
+++ b/src/cmd/compile/internal/ssa/cse.go
@@ -0,0 +1,163 @@
+// 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 "sort"
+
+// cse does common-subexpression elimination on the Function.
+// Values are just relinked, nothing is deleted.  A subsequent deadcode
+// pass is required to actually remove duplicate expressions.
+func cse(f *Func) {
+	// Two values are equivalent if they satisfy the following definition:
+	// equivalent(v, w):
+	//   v.op == w.op
+	//   v.type == w.type
+	//   v.aux == w.aux
+	//   len(v.args) == len(w.args)
+	//   equivalent(v.args[i], w.args[i]) for i in 0..len(v.args)-1
+
+	// The algorithm searches for a partition of f's values into
+	// equivalence classes using the above definition.
+	// It starts with a coarse partition and iteratively refines it
+	// until it reaches a fixed point.
+
+	// Make initial partition based on opcode/type/aux/nargs
+	// TODO(khr): types are not canonical, so we may split unnecessarily.  Fix that.
+	type key struct {
+		op    Op
+		typ   Type
+		aux   interface{}
+		nargs int
+	}
+	m := map[key]eqclass{}
+	for _, b := range f.Blocks {
+		for _, v := range b.Values {
+			k := key{v.Op, v.Type, v.Aux, len(v.Args)}
+			m[k] = append(m[k], v)
+		}
+	}
+
+	// A partition is a set of disjoint eqclasses.
+	var partition []eqclass
+	for _, v := range m {
+		partition = append(partition, v)
+	}
+
+	// map from value id back to eqclass id
+	valueEqClass := make([]int, f.NumValues())
+	for i, e := range partition {
+		for _, v := range e {
+			valueEqClass[v.ID] = i
+		}
+	}
+
+	// Find an equivalence class where some members of the class have
+	// non-equivalent arguments.  Split the equivalence class appropriately.
+	// Repeat until we can't find any more splits.
+	for {
+		changed := false
+
+		for i, e := range partition {
+			v := e[0]
+			// all values in this equiv class that are not equivalent to v get moved
+			// into another equiv class q.
+			var q eqclass
+		eqloop:
+			for j := 1; j < len(e); {
+				w := e[j]
+				for i := 0; i < len(v.Args); i++ {
+					if valueEqClass[v.Args[i].ID] != valueEqClass[w.Args[i].ID] {
+						// w is not equivalent to v.
+						// remove w from e
+						e, e[j] = e[:len(e)-1], e[len(e)-1]
+						// add w to q
+						q = append(q, w)
+						valueEqClass[w.ID] = len(partition)
+						changed = true
+						continue eqloop
+					}
+				}
+				// v and w are equivalent.  Keep w in e.
+				j++
+			}
+			partition[i] = e
+			if q != nil {
+				partition = append(partition, q)
+			}
+		}
+
+		if !changed {
+			break
+		}
+	}
+
+	// Compute dominator tree
+	idom := dominators(f)
+
+	// Compute substitutions we would like to do.  We substitute v for w
+	// if v and w are in the same equivalence class and v dominates w.
+	rewrite := make([]*Value, f.NumValues())
+	for _, e := range partition {
+		sort.Sort(e) // ensure deterministic ordering
+		for len(e) > 1 {
+			// Find a maximal dominant element in e
+			v := e[0]
+			for _, w := range e[1:] {
+				if dom(w.Block, v.Block, idom) {
+					v = w
+				}
+			}
+
+			// Replace all elements of e which v dominates
+			for i := 0; i < len(e); {
+				w := e[i]
+				if w == v {
+					e, e[i] = e[:len(e)-1], e[len(e)-1]
+				} else if dom(v.Block, w.Block, idom) {
+					rewrite[w.ID] = v
+					e, e[i] = e[:len(e)-1], e[len(e)-1]
+				} else {
+					i++
+				}
+			}
+			// TODO(khr): if value is a control value, do we need to keep it block-local?
+		}
+	}
+
+	// Apply substitutions
+	for _, b := range f.Blocks {
+		for _, v := range b.Values {
+			for i, w := range v.Args {
+				if x := rewrite[w.ID]; x != nil {
+					v.SetArg(i, x)
+				}
+			}
+		}
+	}
+}
+
+// returns true if b dominates c.
+// TODO(khr): faster
+func dom(b, c *Block, idom []*Block) bool {
+	// Walk up from c in the dominator tree looking for b.
+	for c != nil {
+		if c == b {
+			return true
+		}
+		c = idom[c.ID]
+	}
+	// Reached the entry block, never saw b.
+	return false
+}
+
+// An eqclass approximates an equivalence class.  During the
+// algorithm it may represent the union of several of the
+// final equivalence classes.
+type eqclass []*Value
+
+// Sort an equivalence class by value ID.
+func (e eqclass) Len() int           { return len(e) }
+func (e eqclass) Swap(i, j int)      { e[i], e[j] = e[j], e[i] }
+func (e eqclass) Less(i, j int) bool { return e[i].ID < e[j].ID }
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
+		}
+	}
+}
diff --git a/src/cmd/compile/internal/ssa/deadcode_test.go b/src/cmd/compile/internal/ssa/deadcode_test.go
new file mode 100644
index 0000000000..ced46e524b
--- /dev/null
+++ b/src/cmd/compile/internal/ssa/deadcode_test.go
@@ -0,0 +1,93 @@
+// 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 (
+	"testing"
+)
+
+func TestDeadLoop(t *testing.T) {
+	fun := Fun("entry",
+		Bloc("entry",
+			Valu("mem", OpArg, TypeMem, ".mem"),
+			Goto("exit")),
+		Bloc("exit",
+			Exit("mem")),
+		// dead loop
+		Bloc("deadblock",
+			// dead value in dead block
+			Valu("deadval", OpConst, TypeBool, true),
+			If("deadval", "deadblock", "exit")))
+
+	CheckFunc(fun.f)
+	Deadcode(fun.f)
+	CheckFunc(fun.f)
+
+	for _, b := range fun.f.Blocks {
+		if b == fun.blocks["deadblock"] {
+			t.Errorf("dead block not removed")
+		}
+		for _, v := range b.Values {
+			if v == fun.values["deadval"] {
+				t.Errorf("control value of dead block not removed")
+			}
+		}
+	}
+}
+
+func TestDeadValue(t *testing.T) {
+	fun := Fun("entry",
+		Bloc("entry",
+			Valu("mem", OpArg, TypeMem, ".mem"),
+			Valu("deadval", OpConst, TypeInt64, int64(37)),
+			Goto("exit")),
+		Bloc("exit",
+			Exit("mem")))
+
+	CheckFunc(fun.f)
+	Deadcode(fun.f)
+	CheckFunc(fun.f)
+
+	for _, b := range fun.f.Blocks {
+		for _, v := range b.Values {
+			if v == fun.values["deadval"] {
+				t.Errorf("dead value not removed")
+			}
+		}
+	}
+}
+
+func TestNeverTaken(t *testing.T) {
+	fun := Fun("entry",
+		Bloc("entry",
+			Valu("cond", OpConst, TypeBool, false),
+			Valu("mem", OpArg, TypeMem, ".mem"),
+			If("cond", "then", "else")),
+		Bloc("then",
+			Goto("exit")),
+		Bloc("else",
+			Goto("exit")),
+		Bloc("exit",
+			Exit("mem")))
+
+	CheckFunc(fun.f)
+	Deadcode(fun.f)
+	CheckFunc(fun.f)
+
+	if fun.blocks["entry"].Kind != BlockPlain {
+		t.Errorf("if(false) not simplified")
+	}
+	for _, b := range fun.f.Blocks {
+		if b == fun.blocks["then"] {
+			t.Errorf("then block still present")
+		}
+		for _, v := range b.Values {
+			if v == fun.values["cond"] {
+				t.Errorf("constant condition still present")
+			}
+		}
+	}
+
+}
diff --git a/src/cmd/compile/internal/ssa/dom.go b/src/cmd/compile/internal/ssa/dom.go
new file mode 100644
index 0000000000..aaf3ab3da1
--- /dev/null
+++ b/src/cmd/compile/internal/ssa/dom.go
@@ -0,0 +1,121 @@
+// 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
+
+// This file contains code to compute the dominator tree
+// of a control-flow graph.
+
+import "log"
+
+// postorder computes a postorder traversal ordering for the
+// basic blocks in f.  Unreachable blocks will not appear.
+func postorder(f *Func) []*Block {
+	mark := make([]byte, f.NumBlocks())
+	// mark values
+	const (
+		notFound    = 0 // block has not been discovered yet
+		notExplored = 1 // discovered and in queue, outedges not processed yet
+		explored    = 2 // discovered and in queue, outedges processed
+		done        = 3 // all done, in output ordering
+	)
+
+	// result ordering
+	var order []*Block
+
+	// stack of blocks
+	var s []*Block
+	s = append(s, f.Entry)
+	mark[f.Entry.ID] = notExplored
+	for len(s) > 0 {
+		b := s[len(s)-1]
+		switch mark[b.ID] {
+		case explored:
+			// Children have all been visited.  Pop & output block.
+			s = s[:len(s)-1]
+			mark[b.ID] = done
+			order = append(order, b)
+		case notExplored:
+			// Children have not been visited yet.  Mark as explored
+			// and queue any children we haven't seen yet.
+			mark[b.ID] = explored
+			for _, c := range b.Succs {
+				if mark[c.ID] == notFound {
+					mark[c.ID] = notExplored
+					s = append(s, c)
+				}
+			}
+		default:
+			log.Fatalf("bad stack state %v %d", b, mark[b.ID])
+		}
+	}
+	return order
+}
+
+// dominators computes the dominator tree for f.  It returns a slice
+// which maps block ID to the immediate dominator of that block.
+// Unreachable blocks map to nil.  The entry block maps to nil.
+func dominators(f *Func) []*Block {
+	// A simple algorithm for now
+	// Cooper, Harvey, Kennedy
+	idom := make([]*Block, f.NumBlocks())
+
+	// Compute postorder walk
+	post := postorder(f)
+
+	// Make map from block id to order index (for intersect call)
+	postnum := make([]int, f.NumBlocks())
+	for i, b := range post {
+		postnum[b.ID] = i
+	}
+
+	// Make the entry block a self-loop
+	idom[f.Entry.ID] = f.Entry
+	if postnum[f.Entry.ID] != len(post)-1 {
+		log.Fatalf("entry block %v not last in postorder", f.Entry)
+	}
+
+	// Compute relaxation of idom entries
+	for {
+		changed := false
+
+		for i := len(post) - 2; i >= 0; i-- {
+			b := post[i]
+			var d *Block
+			for _, p := range b.Preds {
+				if idom[p.ID] == nil {
+					continue
+				}
+				if d == nil {
+					d = p
+					continue
+				}
+				d = intersect(d, p, postnum, idom)
+			}
+			if d != idom[b.ID] {
+				idom[b.ID] = d
+				changed = true
+			}
+		}
+		if !changed {
+			break
+		}
+	}
+	// Set idom of entry block to nil instead of itself.
+	idom[f.Entry.ID] = nil
+	return idom
+}
+
+// intersect finds the closest dominator of both b and c.
+// It requires a postorder numbering of all the blocks.
+func intersect(b, c *Block, postnum []int, idom []*Block) *Block {
+	for b != c {
+		if postnum[b.ID] < postnum[c.ID] {
+			b = idom[b.ID]
+		} else {
+			c = idom[c.ID]
+		}
+	}
+	return b
+}
diff --git a/src/cmd/compile/internal/ssa/export_test.go b/src/cmd/compile/internal/ssa/export_test.go
new file mode 100644
index 0000000000..ab4ab82345
--- /dev/null
+++ b/src/cmd/compile/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/compile/internal/ssa/func.go b/src/cmd/compile/internal/ssa/func.go
new file mode 100644
index 0000000000..3e41ef3bc1
--- /dev/null
+++ b/src/cmd/compile/internal/ssa/func.go
@@ -0,0 +1,108 @@
+// 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 {
+	Config *Config  // architecture information
+	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
+	// when stackalloc is done, the size of the stack frame
+	FrameSize int64
+}
+
+// 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
+}
+
+// NewValue1 returns a new value in the block with one argument.
+func (b *Block) NewValue1(op Op, t Type, aux interface{}, arg *Value) *Value {
+	v := &Value{
+		ID:    b.Func.vid.get(),
+		Op:    op,
+		Type:  t,
+		Aux:   aux,
+		Block: b,
+	}
+	v.Args = v.argstorage[:1]
+	v.Args[0] = arg
+	b.Values = append(b.Values, v)
+	return v
+}
+
+// NewValue2 returns a new value in the block with two arguments.
+func (b *Block) NewValue2(op Op, t Type, aux interface{}, arg0, arg1 *Value) *Value {
+	v := &Value{
+		ID:    b.Func.vid.get(),
+		Op:    op,
+		Type:  t,
+		Aux:   aux,
+		Block: b,
+	}
+	v.Args = v.argstorage[:2]
+	v.Args[0] = arg0
+	v.Args[1] = arg1
+	b.Values = append(b.Values, v)
+	return v
+}
+
+// NewValue3 returns a new value in the block with three arguments.
+func (b *Block) NewValue3(op Op, t Type, aux interface{}, arg0, arg1, arg2 *Value) *Value {
+	v := &Value{
+		ID:    b.Func.vid.get(),
+		Op:    op,
+		Type:  t,
+		Aux:   aux,
+		Block: b,
+	}
+	v.Args = []*Value{arg0, arg1, arg2}
+	b.Values = append(b.Values, v)
+	return v
+}
+
+// ConstInt returns an int constant representing its argument.
+func (f *Func) ConstInt(t Type, c int64) *Value {
+	// TODO: cache?
+	return f.Entry.NewValue(OpConst, t, c)
+}
diff --git a/src/cmd/compile/internal/ssa/func_test.go b/src/cmd/compile/internal/ssa/func_test.go
new file mode 100644
index 0000000000..e7619ca4f8
--- /dev/null
+++ b/src/cmd/compile/internal/ssa/func_test.go
@@ -0,0 +1,401 @@
+// This file contains some utility functions to help define Funcs for testing.
+// As an example, the following func
+//
+//   b1:
+//     v1 = Arg <mem> [.mem]
+//     Plain -> b2
+//   b2:
+//     Exit v1
+//   b3:
+//     v2 = Const <bool> [true]
+//     If v2 -> b3 b2
+//
+// can be defined as
+//
+//   fun := Fun("entry",
+//       Bloc("entry",
+//           Valu("mem", OpArg, TypeMem, ".mem"),
+//           Goto("exit")),
+//       Bloc("exit",
+//           Exit("mem")),
+//       Bloc("deadblock",
+//          Valu("deadval", OpConst, TypeBool, true),
+//          If("deadval", "deadblock", "exit")))
+//
+// and the Blocks or Values used in the Func can be accessed
+// like this:
+//   fun.blocks["entry"] or fun.values["deadval"]
+
+package ssa
+
+// TODO(matloob): Choose better names for Fun, Bloc, Goto, etc.
+// TODO(matloob): Write a parser for the Func disassembly. Maybe
+//                the parser can be used instead of Fun.
+
+import (
+	"log"
+	"reflect"
+	"testing"
+)
+
+// Compare two Funcs for equivalence. Their CFGs must be isomorphic,
+// and their values must correspond.
+// Requires that values and predecessors are in the same order, even
+// though Funcs could be equivalent when they are not.
+// TODO(matloob): Allow values and predecessors to be in different
+// orders if the CFG are otherwise equivalent.
+func Equiv(f, g *Func) bool {
+	valcor := make(map[*Value]*Value)
+	var checkVal func(fv, gv *Value) bool
+	checkVal = func(fv, gv *Value) bool {
+		if fv == nil && gv == nil {
+			return true
+		}
+		if valcor[fv] == nil && valcor[gv] == nil {
+			valcor[fv] = gv
+			valcor[gv] = fv
+			// Ignore ids. Ops and Types are compared for equality.
+			// TODO(matloob): Make sure types are canonical and can
+			// be compared for equality.
+			if fv.Op != gv.Op || fv.Type != gv.Type {
+				return false
+			}
+			if !reflect.DeepEqual(fv.Aux, gv.Aux) {
+				// This makes the assumption that aux values can be compared
+				// using DeepEqual.
+				// TODO(matloob): Aux values may be *gc.Sym pointers in the near
+				// future. Make sure they are canonical.
+				return false
+			}
+			if len(fv.Args) != len(gv.Args) {
+				return false
+			}
+			for i := range fv.Args {
+				if !checkVal(fv.Args[i], gv.Args[i]) {
+					return false
+				}
+			}
+		}
+		return valcor[fv] == gv && valcor[gv] == fv
+	}
+	blkcor := make(map[*Block]*Block)
+	var checkBlk func(fb, gb *Block) bool
+	checkBlk = func(fb, gb *Block) bool {
+		if blkcor[fb] == nil && blkcor[gb] == nil {
+			blkcor[fb] = gb
+			blkcor[gb] = fb
+			// ignore ids
+			if fb.Kind != gb.Kind {
+				return false
+			}
+			if len(fb.Values) != len(gb.Values) {
+				return false
+			}
+			for i := range fb.Values {
+				if !checkVal(fb.Values[i], gb.Values[i]) {
+					return false
+				}
+			}
+			if len(fb.Succs) != len(gb.Succs) {
+				return false
+			}
+			for i := range fb.Succs {
+				if !checkBlk(fb.Succs[i], gb.Succs[i]) {
+					return false
+				}
+			}
+			if len(fb.Preds) != len(gb.Preds) {
+				return false
+			}
+			for i := range fb.Preds {
+				if !checkBlk(fb.Preds[i], gb.Preds[i]) {
+					return false
+				}
+			}
+			return true
+
+		}
+		return blkcor[fb] == gb && blkcor[gb] == fb
+	}
+
+	return checkBlk(f.Entry, g.Entry)
+}
+
+// fun is the return type of Fun. It contains the created func
+// itself as well as indexes from block and value names into the
+// corresponding Blocks and Values.
+type fun struct {
+	f      *Func
+	blocks map[string]*Block
+	values map[string]*Value
+}
+
+// Fun takes the name of an entry bloc and a series of Bloc calls, and
+// returns a fun containing the composed Func. entry must be a name
+// supplied to one of the Bloc functions. Each of the bloc names and
+// valu names should be unique across the Fun.
+func Fun(entry string, blocs ...bloc) fun {
+	f := new(Func)
+	blocks := make(map[string]*Block)
+	values := make(map[string]*Value)
+	// Create all the blocks and values.
+	for _, bloc := range blocs {
+		b := f.NewBlock(bloc.control.kind)
+		blocks[bloc.name] = b
+		for _, valu := range bloc.valus {
+			// args are filled in the second pass.
+			values[valu.name] = b.NewValue(valu.op, valu.t, valu.aux)
+		}
+	}
+	// Connect the blocks together and specify control values.
+	f.Entry = blocks[entry]
+	for _, bloc := range blocs {
+		b := blocks[bloc.name]
+		c := bloc.control
+		// Specify control values.
+		if c.control != "" {
+			cval, ok := values[c.control]
+			if !ok {
+				log.Panicf("control value for block %s missing", bloc.name)
+			}
+			b.Control = cval
+		}
+		// Fill in args.
+		for _, valu := range bloc.valus {
+			v := values[valu.name]
+			for _, arg := range valu.args {
+				a, ok := values[arg]
+				if !ok {
+					log.Panicf("arg %s missing for value %s in block %s",
+						arg, valu.name, bloc.name)
+				}
+				v.AddArg(a)
+			}
+		}
+		// Connect to successors.
+		for _, succ := range c.succs {
+			addEdge(b, blocks[succ])
+		}
+	}
+	return fun{f, blocks, values}
+}
+
+// Bloc defines a block for Fun. The bloc name should be unique
+// across the containing Fun. entries should consist of calls to valu,
+// as well as one call to Goto, If, or Exit to specify the block kind.
+func Bloc(name string, entries ...interface{}) bloc {
+	b := bloc{}
+	b.name = name
+	seenCtrl := false
+	for _, e := range entries {
+		switch v := e.(type) {
+		case ctrl:
+			// there should be exactly one Ctrl entry.
+			if seenCtrl {
+				log.Panicf("already seen control for block %s", name)
+			}
+			b.control = v
+			seenCtrl = true
+		case valu:
+			b.valus = append(b.valus, v)
+		}
+	}
+	if !seenCtrl {
+		log.Panicf("block %s doesn't have control", b.name)
+	}
+	return b
+}
+
+// Valu defines a value in a block.
+func Valu(name string, op Op, t Type, aux interface{}, args ...string) valu {
+	return valu{name, op, t, aux, args}
+}
+
+// Goto specifies that this is a BlockPlain and names the single successor.
+// TODO(matloob): choose a better name.
+func Goto(succ string) ctrl {
+	return ctrl{BlockPlain, "", []string{succ}}
+}
+
+// If specifies a BlockIf.
+func If(cond, sub, alt string) ctrl {
+	return ctrl{BlockIf, cond, []string{sub, alt}}
+}
+
+// Exit specifies a BlockExit.
+func Exit(arg string) ctrl {
+	return ctrl{BlockExit, arg, []string{}}
+}
+
+// bloc, ctrl, and valu are internal structures used by Bloc, Valu, Goto,
+// If, and Exit to help define blocks.
+
+type bloc struct {
+	name    string
+	control ctrl
+	valus   []valu
+}
+
+type ctrl struct {
+	kind    BlockKind
+	control string
+	succs   []string
+}
+
+type valu struct {
+	name string
+	op   Op
+	t    Type
+	aux  interface{}
+	args []string
+}
+
+func addEdge(b, c *Block) {
+	b.Succs = append(b.Succs, c)
+	c.Preds = append(c.Preds, b)
+}
+
+func TestArgs(t *testing.T) {
+	fun := Fun("entry",
+		Bloc("entry",
+			Valu("a", OpConst, TypeInt64, 14),
+			Valu("b", OpConst, TypeInt64, 26),
+			Valu("sum", OpAdd, TypeInt64, nil, "a", "b"),
+			Valu("mem", OpArg, TypeMem, ".mem"),
+			Goto("exit")),
+		Bloc("exit",
+			Exit("mem")))
+	sum := fun.values["sum"]
+	for i, name := range []string{"a", "b"} {
+		if sum.Args[i] != fun.values[name] {
+			t.Errorf("arg %d for sum is incorrect: want %s, got %s",
+				i, sum.Args[i], fun.values[name])
+		}
+	}
+}
+
+func TestEquiv(t *testing.T) {
+	equivalentCases := []struct{ f, g fun }{
+		// simple case
+		{
+			Fun("entry",
+				Bloc("entry",
+					Valu("a", OpConst, TypeInt64, 14),
+					Valu("b", OpConst, TypeInt64, 26),
+					Valu("sum", OpAdd, TypeInt64, nil, "a", "b"),
+					Valu("mem", OpArg, TypeMem, ".mem"),
+					Goto("exit")),
+				Bloc("exit",
+					Exit("mem"))),
+			Fun("entry",
+				Bloc("entry",
+					Valu("a", OpConst, TypeInt64, 14),
+					Valu("b", OpConst, TypeInt64, 26),
+					Valu("sum", OpAdd, TypeInt64, nil, "a", "b"),
+					Valu("mem", OpArg, TypeMem, ".mem"),
+					Goto("exit")),
+				Bloc("exit",
+					Exit("mem"))),
+		},
+		// block order changed
+		{
+			Fun("entry",
+				Bloc("entry",
+					Valu("a", OpConst, TypeInt64, 14),
+					Valu("b", OpConst, TypeInt64, 26),
+					Valu("sum", OpAdd, TypeInt64, nil, "a", "b"),
+					Valu("mem", OpArg, TypeMem, ".mem"),
+					Goto("exit")),
+				Bloc("exit",
+					Exit("mem"))),
+			Fun("entry",
+				Bloc("exit",
+					Exit("mem")),
+				Bloc("entry",
+					Valu("a", OpConst, TypeInt64, 14),
+					Valu("b", OpConst, TypeInt64, 26),
+					Valu("sum", OpAdd, TypeInt64, nil, "a", "b"),
+					Valu("mem", OpArg, TypeMem, ".mem"),
+					Goto("exit"))),
+		},
+	}
+	for _, c := range equivalentCases {
+		if !Equiv(c.f.f, c.g.f) {
+			t.Errorf("expected equivalence. Func definitions:")
+			// TODO(matloob): Rewrite PrintFunc to output to a string or writer,
+			// so the functions can be written to the error log.
+			PrintFunc(c.f.f)
+			PrintFunc(c.g.f)
+		}
+	}
+
+	differentCases := []struct{ f, g fun }{
+		// different shape
+		{
+			Fun("entry",
+				Bloc("entry",
+					Valu("mem", OpArg, TypeMem, ".mem"),
+					Goto("exit")),
+				Bloc("exit",
+					Exit("mem"))),
+			Fun("entry",
+				Bloc("entry",
+					Valu("mem", OpArg, TypeMem, ".mem"),
+					Exit("mem"))),
+		},
+		// value order changed
+		{
+			Fun("entry",
+				Bloc("entry",
+					Valu("mem", OpArg, TypeMem, ".mem"),
+					Valu("b", OpConst, TypeInt64, 26),
+					Valu("a", OpConst, TypeInt64, 14),
+					Exit("mem"))),
+			Fun("entry",
+				Bloc("entry",
+					Valu("mem", OpArg, TypeMem, ".mem"),
+					Valu("a", OpConst, TypeInt64, 14),
+					Valu("b", OpConst, TypeInt64, 26),
+					Exit("mem"))),
+		},
+		// value aux different
+		{
+			Fun("entry",
+				Bloc("entry",
+					Valu("mem", OpArg, TypeMem, ".mem"),
+					Valu("a", OpConst, TypeInt64, 14),
+					Exit("mem"))),
+			Fun("entry",
+				Bloc("entry",
+					Valu("mem", OpArg, TypeMem, ".mem"),
+					Valu("a", OpConst, TypeInt64, 26),
+					Exit("mem"))),
+		},
+		// value args different
+		{
+			Fun("entry",
+				Bloc("entry",
+					Valu("mem", OpArg, TypeMem, ".mem"),
+					Valu("a", OpConst, TypeInt64, 14),
+					Valu("b", OpConst, TypeInt64, 26),
+					Valu("sum", OpAdd, TypeInt64, nil, "a", "b"),
+					Exit("mem"))),
+			Fun("entry",
+				Bloc("entry",
+					Valu("mem", OpArg, TypeMem, ".mem"),
+					Valu("a", OpConst, TypeInt64, 0),
+					Valu("b", OpConst, TypeInt64, 14),
+					Valu("sum", OpAdd, TypeInt64, nil, "b", "a"),
+					Exit("mem"))),
+		},
+	}
+	for _, c := range differentCases {
+		if Equiv(c.f.f, c.g.f) {
+			t.Errorf("expected difference. Func definitions:")
+			// TODO(matloob): Rewrite PrintFunc to output to a string or writer,
+			// so the functions can be written to the error log.
+			PrintFunc(c.f.f)
+			PrintFunc(c.g.f)
+		}
+	}
+}
diff --git a/src/cmd/compile/internal/ssa/fuse.go b/src/cmd/compile/internal/ssa/fuse.go
new file mode 100644
index 0000000000..af3e8a8e14
--- /dev/null
+++ b/src/cmd/compile/internal/ssa/fuse.go
@@ -0,0 +1,43 @@
+// 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 _, b := range f.Blocks {
+		if b.Kind != BlockPlain {
+			continue
+		}
+		c := b.Succs[0]
+		if len(c.Preds) != 1 {
+			continue
+		}
+
+		// move all of b's 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.Preds = b.Preds
+		for _, p := range c.Preds {
+			for i, q := range p.Succs {
+				if q == b {
+					p.Succs[i] = c
+				}
+			}
+		}
+		if f.Entry == b {
+			f.Entry = c
+		}
+
+		// trash b, just in case
+		b.Kind = BlockUnknown
+		b.Values = nil
+		b.Preds = nil
+		b.Succs = nil
+	}
+}
diff --git a/src/cmd/compile/internal/ssa/generic.go b/src/cmd/compile/internal/ssa/generic.go
new file mode 100644
index 0000000000..91f9c17d11
--- /dev/null
+++ b/src/cmd/compile/internal/ssa/generic.go
@@ -0,0 +1,236 @@
+// autogenerated from rulegen/generic.rules: do not edit!
+// generated with: go run rulegen/rulegen.go rulegen/generic.rules genericRules generic.go
+package ssa
+
+func genericRules(v *Value) bool {
+	switch v.Op {
+	case OpAdd:
+		// match: (Add <t> (Const [c]) (Const [d]))
+		// cond: is64BitInt(t)
+		// result: (Const [{c.(int64)+d.(int64)}])
+		{
+			t := v.Type
+			if v.Args[0].Op != OpConst {
+				goto end8d047ed0ae9537b840adc79ea82c6e05
+			}
+			c := v.Args[0].Aux
+			if v.Args[1].Op != OpConst {
+				goto end8d047ed0ae9537b840adc79ea82c6e05
+			}
+			d := v.Args[1].Aux
+			if !(is64BitInt(t)) {
+				goto end8d047ed0ae9537b840adc79ea82c6e05
+			}
+			v.Op = OpConst
+			v.Aux = nil
+			v.resetArgs()
+			v.Aux = c.(int64) + d.(int64)
+			return true
+		}
+		goto end8d047ed0ae9537b840adc79ea82c6e05
+	end8d047ed0ae9537b840adc79ea82c6e05:
+		;
+	case OpArrayIndex:
+		// match: (ArrayIndex (Load ptr mem) idx)
+		// cond:
+		// result: (Load (PtrIndex <ptr.Type.Elem().Elem().PtrTo()> ptr idx) mem)
+		{
+			if v.Args[0].Op != OpLoad {
+				goto end3809f4c52270a76313e4ea26e6f0b753
+			}
+			ptr := v.Args[0].Args[0]
+			mem := v.Args[0].Args[1]
+			idx := v.Args[1]
+			v.Op = OpLoad
+			v.Aux = nil
+			v.resetArgs()
+			v0 := v.Block.NewValue(OpPtrIndex, TypeInvalid, nil)
+			v0.Type = ptr.Type.Elem().Elem().PtrTo()
+			v0.AddArg(ptr)
+			v0.AddArg(idx)
+			v.AddArg(v0)
+			v.AddArg(mem)
+			return true
+		}
+		goto end3809f4c52270a76313e4ea26e6f0b753
+	end3809f4c52270a76313e4ea26e6f0b753:
+		;
+	case OpIsInBounds:
+		// match: (IsInBounds (Const [c]) (Const [d]))
+		// cond:
+		// result: (Const [inBounds(c.(int64),d.(int64))])
+		{
+			if v.Args[0].Op != OpConst {
+				goto enddbd1a394d9b71ee64335361b8384865c
+			}
+			c := v.Args[0].Aux
+			if v.Args[1].Op != OpConst {
+				goto enddbd1a394d9b71ee64335361b8384865c
+			}
+			d := v.Args[1].Aux
+			v.Op = OpConst
+			v.Aux = nil
+			v.resetArgs()
+			v.Aux = inBounds(c.(int64), d.(int64))
+			return true
+		}
+		goto enddbd1a394d9b71ee64335361b8384865c
+	enddbd1a394d9b71ee64335361b8384865c:
+		;
+	case OpMul:
+		// match: (Mul <t> (Const [c]) (Const [d]))
+		// cond: is64BitInt(t)
+		// result: (Const [{c.(int64)*d.(int64)}])
+		{
+			t := v.Type
+			if v.Args[0].Op != OpConst {
+				goto end776610f88cf04f438242d76ed2b14f1c
+			}
+			c := v.Args[0].Aux
+			if v.Args[1].Op != OpConst {
+				goto end776610f88cf04f438242d76ed2b14f1c
+			}
+			d := v.Args[1].Aux
+			if !(is64BitInt(t)) {
+				goto end776610f88cf04f438242d76ed2b14f1c
+			}
+			v.Op = OpConst
+			v.Aux = nil
+			v.resetArgs()
+			v.Aux = c.(int64) * d.(int64)
+			return true
+		}
+		goto end776610f88cf04f438242d76ed2b14f1c
+	end776610f88cf04f438242d76ed2b14f1c:
+		;
+	case OpPtrIndex:
+		// match: (PtrIndex <t> ptr idx)
+		// cond:
+		// result: (Add ptr (Mul <v.Block.Func.Config.Uintptr> idx (Const <v.Block.Func.Config.Uintptr> [t.Elem().Size()])))
+		{
+			t := v.Type
+			ptr := v.Args[0]
+			idx := v.Args[1]
+			v.Op = OpAdd
+			v.Aux = nil
+			v.resetArgs()
+			v.AddArg(ptr)
+			v0 := v.Block.NewValue(OpMul, TypeInvalid, nil)
+			v0.Type = v.Block.Func.Config.Uintptr
+			v0.AddArg(idx)
+			v1 := v.Block.NewValue(OpConst, TypeInvalid, nil)
+			v1.Type = v.Block.Func.Config.Uintptr
+			v1.Aux = t.Elem().Size()
+			v0.AddArg(v1)
+			v.AddArg(v0)
+			return true
+		}
+		goto end383c68c41e72d22ef00c4b7b0fddcbb8
+	end383c68c41e72d22ef00c4b7b0fddcbb8:
+		;
+	case OpSliceCap:
+		// match: (SliceCap (Load ptr mem))
+		// cond:
+		// result: (Load (Add <ptr.Type> ptr (Const <v.Block.Func.Config.Uintptr> [int64(v.Block.Func.Config.ptrSize*2)])) mem)
+		{
+			if v.Args[0].Op != OpLoad {
+				goto endbf1d4db93c4664ed43be3f73afb4dfa3
+			}
+			ptr := v.Args[0].Args[0]
+			mem := v.Args[0].Args[1]
+			v.Op = OpLoad
+			v.Aux = nil
+			v.resetArgs()
+			v0 := v.Block.NewValue(OpAdd, TypeInvalid, nil)
+			v0.Type = ptr.Type
+			v0.AddArg(ptr)
+			v1 := v.Block.NewValue(OpConst, TypeInvalid, nil)
+			v1.Type = v.Block.Func.Config.Uintptr
+			v1.Aux = int64(v.Block.Func.Config.ptrSize * 2)
+			v0.AddArg(v1)
+			v.AddArg(v0)
+			v.AddArg(mem)
+			return true
+		}
+		goto endbf1d4db93c4664ed43be3f73afb4dfa3
+	endbf1d4db93c4664ed43be3f73afb4dfa3:
+		;
+	case OpSliceLen:
+		// match: (SliceLen (Load ptr mem))
+		// cond:
+		// result: (Load (Add <ptr.Type> ptr (Const <v.Block.Func.Config.Uintptr> [int64(v.Block.Func.Config.ptrSize)])) mem)
+		{
+			if v.Args[0].Op != OpLoad {
+				goto end9190b1ecbda4c5dd6d3e05d2495fb297
+			}
+			ptr := v.Args[0].Args[0]
+			mem := v.Args[0].Args[1]
+			v.Op = OpLoad
+			v.Aux = nil
+			v.resetArgs()
+			v0 := v.Block.NewValue(OpAdd, TypeInvalid, nil)
+			v0.Type = ptr.Type
+			v0.AddArg(ptr)
+			v1 := v.Block.NewValue(OpConst, TypeInvalid, nil)
+			v1.Type = v.Block.Func.Config.Uintptr
+			v1.Aux = int64(v.Block.Func.Config.ptrSize)
+			v0.AddArg(v1)
+			v.AddArg(v0)
+			v.AddArg(mem)
+			return true
+		}
+		goto end9190b1ecbda4c5dd6d3e05d2495fb297
+	end9190b1ecbda4c5dd6d3e05d2495fb297:
+		;
+	case OpSlicePtr:
+		// match: (SlicePtr (Load ptr mem))
+		// cond:
+		// result: (Load ptr mem)
+		{
+			if v.Args[0].Op != OpLoad {
+				goto end459613b83f95b65729d45c2ed663a153
+			}
+			ptr := v.Args[0].Args[0]
+			mem := v.Args[0].Args[1]
+			v.Op = OpLoad
+			v.Aux = nil
+			v.resetArgs()
+			v.AddArg(ptr)
+			v.AddArg(mem)
+			return true
+		}
+		goto end459613b83f95b65729d45c2ed663a153
+	end459613b83f95b65729d45c2ed663a153:
+		;
+	case OpStore:
+		// match: (Store dst (Load <t> src mem) mem)
+		// cond: t.Size() > 8
+		// result: (Move [t.Size()] dst src mem)
+		{
+			dst := v.Args[0]
+			if v.Args[1].Op != OpLoad {
+				goto end324ffb6d2771808da4267f62c854e9c8
+			}
+			t := v.Args[1].Type
+			src := v.Args[1].Args[0]
+			mem := v.Args[1].Args[1]
+			if v.Args[2] != v.Args[1].Args[1] {
+				goto end324ffb6d2771808da4267f62c854e9c8
+			}
+			if !(t.Size() > 8) {
+				goto end324ffb6d2771808da4267f62c854e9c8
+			}
+			v.Op = OpMove
+			v.Aux = nil
+			v.resetArgs()
+			v.Aux = t.Size()
+			v.AddArg(dst)
+			v.AddArg(src)
+			v.AddArg(mem)
+			return true
+		}
+		goto end324ffb6d2771808da4267f62c854e9c8
+	end324ffb6d2771808da4267f62c854e9c8:
+	}
+	return false
+}
diff --git a/src/cmd/compile/internal/ssa/id.go b/src/cmd/compile/internal/ssa/id.go
new file mode 100644
index 0000000000..3f53e1a434
--- /dev/null
+++ b/src/cmd/compile/internal/ssa/id.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.
+
+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)
+}
+
+// num returns the maximum ID ever returned + 1.
+func (a *idAlloc) num() int {
+	return int(a.last + 1)
+}
diff --git a/src/cmd/compile/internal/ssa/layout.go b/src/cmd/compile/internal/ssa/layout.go
new file mode 100644
index 0000000000..7123397c4c
--- /dev/null
+++ b/src/cmd/compile/internal/ssa/layout.go
@@ -0,0 +1,88 @@
+// 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"
+
+// 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 := newSparseSet(f.NumBlocks())  // blocks with positive remaining degree
+	zerodegree := newSparseSet(f.NumBlocks()) // blocks with zero remaining degree
+
+	// 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.
+		// Just use degree for now.  TODO(khr): use likely direction hints.
+		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
+			}
+		}
+		log.Panicf("no block available for layout")
+	}
+	f.Blocks = order
+}
diff --git a/src/cmd/compile/internal/ssa/location.go b/src/cmd/compile/internal/ssa/location.go
new file mode 100644
index 0000000000..1b6f6d66c1
--- /dev/null
+++ b/src/cmd/compile/internal/ssa/location.go
@@ -0,0 +1,34 @@
+// 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.
+// They are numbered densely from 0 (for each architecture).
+type Register struct {
+	Num  int32
+	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 up from SP)
+}
+
+func (s *LocalSlot) Name() string {
+	return fmt.Sprintf("%d(SP)", s.Idx)
+}
diff --git a/src/cmd/compile/internal/ssa/lower.go b/src/cmd/compile/internal/ssa/lower.go
new file mode 100644
index 0000000000..44f0b83fa8
--- /dev/null
+++ b/src/cmd/compile/internal/ssa/lower.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.
+
+package ssa
+
+import "log"
+
+//go:generate go run rulegen/rulegen.go rulegen/lower_amd64.rules lowerAmd64 lowerAmd64.go
+
+// convert to machine-dependent ops
+func lower(f *Func) {
+	// repeat rewrites until we find no more rewrites
+	applyRewrite(f, f.Config.lower)
+
+	// Check for unlowered opcodes, fail if we find one.
+	for _, b := range f.Blocks {
+		for _, v := range b.Values {
+			if v.Op < OpGenericEnd && v.Op != OpFP && v.Op != OpSP && v.Op != OpArg && v.Op != OpCopy && v.Op != OpPhi {
+				log.Panicf("%s not lowered", v.LongString())
+			}
+		}
+	}
+
+	// additional pass for 386/amd64, link condition codes directly to blocks
+	// TODO: do generically somehow?  Special "block" rewrite rules?
+	for _, b := range f.Blocks {
+		for {
+			switch b.Kind {
+			case BlockIf:
+				switch b.Control.Op {
+				case OpSETL:
+					b.Kind = BlockLT
+					b.Control = b.Control.Args[0]
+					continue
+				case OpSETNE:
+					b.Kind = BlockNE
+					b.Control = b.Control.Args[0]
+					continue
+				case OpSETB:
+					b.Kind = BlockULT
+					b.Control = b.Control.Args[0]
+					continue
+				case OpMOVBload:
+					b.Kind = BlockNE
+					b.Control = b.NewValue2(OpTESTB, TypeFlags, nil, b.Control, b.Control)
+					continue
+					// TODO: others
+				}
+			case BlockLT:
+				if b.Control.Op == OpInvertFlags {
+					b.Kind = BlockGT
+					b.Control = b.Control.Args[0]
+					continue
+				}
+			case BlockGT:
+				if b.Control.Op == OpInvertFlags {
+					b.Kind = BlockLT
+					b.Control = b.Control.Args[0]
+					continue
+				}
+			case BlockLE:
+				if b.Control.Op == OpInvertFlags {
+					b.Kind = BlockGE
+					b.Control = b.Control.Args[0]
+					continue
+				}
+			case BlockGE:
+				if b.Control.Op == OpInvertFlags {
+					b.Kind = BlockLE
+					b.Control = b.Control.Args[0]
+					continue
+				}
+			case BlockULT:
+				if b.Control.Op == OpInvertFlags {
+					b.Kind = BlockUGT
+					b.Control = b.Control.Args[0]
+					continue
+				}
+			case BlockUGT:
+				if b.Control.Op == OpInvertFlags {
+					b.Kind = BlockULT
+					b.Control = b.Control.Args[0]
+					continue
+				}
+			case BlockULE:
+				if b.Control.Op == OpInvertFlags {
+					b.Kind = BlockUGE
+					b.Control = b.Control.Args[0]
+					continue
+				}
+			case BlockUGE:
+				if b.Control.Op == OpInvertFlags {
+					b.Kind = BlockULE
+					b.Control = b.Control.Args[0]
+					continue
+				}
+			case BlockEQ:
+				if b.Control.Op == OpInvertFlags {
+					b.Control = b.Control.Args[0]
+					continue
+				}
+			case BlockNE:
+				if b.Control.Op == OpInvertFlags {
+					b.Control = b.Control.Args[0]
+					continue
+				}
+			}
+			break
+		}
+	}
+}
diff --git a/src/cmd/compile/internal/ssa/lowerAmd64.go b/src/cmd/compile/internal/ssa/lowerAmd64.go
new file mode 100644
index 0000000000..51cef97b30
--- /dev/null
+++ b/src/cmd/compile/internal/ssa/lowerAmd64.go
@@ -0,0 +1,773 @@
+// autogenerated from rulegen/lower_amd64.rules: do not edit!
+// generated with: go run rulegen/rulegen.go rulegen/lower_amd64.rules lowerAmd64 lowerAmd64.go
+package ssa
+
+func lowerAmd64(v *Value) bool {
+	switch v.Op {
+	case OpADDQ:
+		// match: (ADDQ x (MOVQconst [c]))
+		// cond:
+		// result: (ADDQconst [c] x)
+		{
+			x := v.Args[0]
+			if v.Args[1].Op != OpMOVQconst {
+				goto endacffd55e74ee0ff59ad58a18ddfc9973
+			}
+			c := v.Args[1].Aux
+			v.Op = OpADDQconst
+			v.Aux = nil
+			v.resetArgs()
+			v.Aux = c
+			v.AddArg(x)
+			return true
+		}
+		goto endacffd55e74ee0ff59ad58a18ddfc9973
+	endacffd55e74ee0ff59ad58a18ddfc9973:
+		;
+		// match: (ADDQ (MOVQconst [c]) x)
+		// cond:
+		// result: (ADDQconst [c] x)
+		{
+			if v.Args[0].Op != OpMOVQconst {
+				goto end7166f476d744ab7a51125959d3d3c7e2
+			}
+			c := v.Args[0].Aux
+			x := v.Args[1]
+			v.Op = OpADDQconst
+			v.Aux = nil
+			v.resetArgs()
+			v.Aux = c
+			v.AddArg(x)
+			return true
+		}
+		goto end7166f476d744ab7a51125959d3d3c7e2
+	end7166f476d744ab7a51125959d3d3c7e2:
+		;
+		// match: (ADDQ x (SHLQconst [shift] y))
+		// cond: shift.(int64) == 3
+		// result: (LEAQ8 [int64(0)] x y)
+		{
+			x := v.Args[0]
+			if v.Args[1].Op != OpSHLQconst {
+				goto endaf4f724e1e17f2b116d336c07da0165d
+			}
+			shift := v.Args[1].Aux
+			y := v.Args[1].Args[0]
+			if !(shift.(int64) == 3) {
+				goto endaf4f724e1e17f2b116d336c07da0165d
+			}
+			v.Op = OpLEAQ8
+			v.Aux = nil
+			v.resetArgs()
+			v.Aux = int64(0)
+			v.AddArg(x)
+			v.AddArg(y)
+			return true
+		}
+		goto endaf4f724e1e17f2b116d336c07da0165d
+	endaf4f724e1e17f2b116d336c07da0165d:
+		;
+	case OpADDQconst:
+		// match: (ADDQconst [c] (LEAQ8 [d] x y))
+		// cond:
+		// result: (LEAQ8 [addOff(c, d)] x y)
+		{
+			c := v.Aux
+			if v.Args[0].Op != OpLEAQ8 {
+				goto ende2cc681c9abf9913288803fb1b39e639
+			}
+			d := v.Args[0].Aux
+			x := v.Args[0].Args[0]
+			y := v.Args[0].Args[1]
+			v.Op = OpLEAQ8
+			v.Aux = nil
+			v.resetArgs()
+			v.Aux = addOff(c, d)
+			v.AddArg(x)
+			v.AddArg(y)
+			return true
+		}
+		goto ende2cc681c9abf9913288803fb1b39e639
+	ende2cc681c9abf9913288803fb1b39e639:
+		;
+		// match: (ADDQconst [off] x)
+		// cond: off.(int64) == 0
+		// result: (Copy x)
+		{
+			off := v.Aux
+			x := v.Args[0]
+			if !(off.(int64) == 0) {
+				goto endfa1c7cc5ac4716697e891376787f86ce
+			}
+			v.Op = OpCopy
+			v.Aux = nil
+			v.resetArgs()
+			v.AddArg(x)
+			return true
+		}
+		goto endfa1c7cc5ac4716697e891376787f86ce
+	endfa1c7cc5ac4716697e891376787f86ce:
+		;
+	case OpAdd:
+		// match: (Add <t> x y)
+		// cond: (is64BitInt(t) || isPtr(t))
+		// result: (ADDQ x y)
+		{
+			t := v.Type
+			x := v.Args[0]
+			y := v.Args[1]
+			if !(is64BitInt(t) || isPtr(t)) {
+				goto endf031c523d7dd08e4b8e7010a94cd94c9
+			}
+			v.Op = OpADDQ
+			v.Aux = nil
+			v.resetArgs()
+			v.AddArg(x)
+			v.AddArg(y)
+			return true
+		}
+		goto endf031c523d7dd08e4b8e7010a94cd94c9
+	endf031c523d7dd08e4b8e7010a94cd94c9:
+		;
+		// match: (Add <t> x y)
+		// cond: is32BitInt(t)
+		// result: (ADDL x y)
+		{
+			t := v.Type
+			x := v.Args[0]
+			y := v.Args[1]
+			if !(is32BitInt(t)) {
+				goto end35a02a1587264e40cf1055856ff8445a
+			}
+			v.Op = OpADDL
+			v.Aux = nil
+			v.resetArgs()
+			v.AddArg(x)
+			v.AddArg(y)
+			return true
+		}
+		goto end35a02a1587264e40cf1055856ff8445a
+	end35a02a1587264e40cf1055856ff8445a:
+		;
+	case OpCMPQ:
+		// match: (CMPQ x (MOVQconst [c]))
+		// cond:
+		// result: (CMPQconst x [c])
+		{
+			x := v.Args[0]
+			if v.Args[1].Op != OpMOVQconst {
+				goto end32ef1328af280ac18fa8045a3502dae9
+			}
+			c := v.Args[1].Aux
+			v.Op = OpCMPQconst
+			v.Aux = nil
+			v.resetArgs()
+			v.AddArg(x)
+			v.Aux = c
+			return true
+		}
+		goto end32ef1328af280ac18fa8045a3502dae9
+	end32ef1328af280ac18fa8045a3502dae9:
+		;
+		// match: (CMPQ (MOVQconst [c]) x)
+		// cond:
+		// result: (InvertFlags (CMPQconst <TypeFlags> x [c]))
+		{
+			if v.Args[0].Op != OpMOVQconst {
+				goto endf8ca12fe79290bc82b11cfa463bc9413
+			}
+			c := v.Args[0].Aux
+			x := v.Args[1]
+			v.Op = OpInvertFlags
+			v.Aux = nil
+			v.resetArgs()
+			v0 := v.Block.NewValue(OpCMPQconst, TypeInvalid, nil)
+			v0.Type = TypeFlags
+			v0.AddArg(x)
+			v0.Aux = c
+			v.AddArg(v0)
+			return true
+		}
+		goto endf8ca12fe79290bc82b11cfa463bc9413
+	endf8ca12fe79290bc82b11cfa463bc9413:
+		;
+	case OpConst:
+		// match: (Const <t> [val])
+		// cond: is64BitInt(t)
+		// result: (MOVQconst [val])
+		{
+			t := v.Type
+			val := v.Aux
+			if !(is64BitInt(t)) {
+				goto end7f5c5b34093fbc6860524cb803ee51bf
+			}
+			v.Op = OpMOVQconst
+			v.Aux = nil
+			v.resetArgs()
+			v.Aux = val
+			return true
+		}
+		goto end7f5c5b34093fbc6860524cb803ee51bf
+	end7f5c5b34093fbc6860524cb803ee51bf:
+		;
+	case OpGlobal:
+		// match: (Global [sym])
+		// cond:
+		// result: (LEAQglobal [GlobalOffset{sym,0}])
+		{
+			sym := v.Aux
+			v.Op = OpLEAQglobal
+			v.Aux = nil
+			v.resetArgs()
+			v.Aux = GlobalOffset{sym, 0}
+			return true
+		}
+		goto end3a3c76fac0e2e53c0e1c60b9524e6f1c
+	end3a3c76fac0e2e53c0e1c60b9524e6f1c:
+		;
+	case OpIsInBounds:
+		// match: (IsInBounds idx len)
+		// cond:
+		// result: (SETB (CMPQ <TypeFlags> idx len))
+		{
+			idx := v.Args[0]
+			len := v.Args[1]
+			v.Op = OpSETB
+			v.Aux = nil
+			v.resetArgs()
+			v0 := v.Block.NewValue(OpCMPQ, TypeInvalid, nil)
+			v0.Type = TypeFlags
+			v0.AddArg(idx)
+			v0.AddArg(len)
+			v.AddArg(v0)
+			return true
+		}
+		goto endb51d371171154c0f1613b687757e0576
+	endb51d371171154c0f1613b687757e0576:
+		;
+	case OpIsNonNil:
+		// match: (IsNonNil p)
+		// cond:
+		// result: (SETNE (TESTQ <TypeFlags> p p))
+		{
+			p := v.Args[0]
+			v.Op = OpSETNE
+			v.Aux = nil
+			v.resetArgs()
+			v0 := v.Block.NewValue(OpTESTQ, TypeInvalid, nil)
+			v0.Type = TypeFlags
+			v0.AddArg(p)
+			v0.AddArg(p)
+			v.AddArg(v0)
+			return true
+		}
+		goto endff508c3726edfb573abc6128c177e76c
+	endff508c3726edfb573abc6128c177e76c:
+		;
+	case OpLess:
+		// match: (Less x y)
+		// cond: is64BitInt(v.Args[0].Type) && isSigned(v.Args[0].Type)
+		// result: (SETL (CMPQ <TypeFlags> x y))
+		{
+			x := v.Args[0]
+			y := v.Args[1]
+			if !(is64BitInt(v.Args[0].Type) && isSigned(v.Args[0].Type)) {
+				goto endcecf13a952d4c6c2383561c7d68a3cf9
+			}
+			v.Op = OpSETL
+			v.Aux = nil
+			v.resetArgs()
+			v0 := v.Block.NewValue(OpCMPQ, TypeInvalid, nil)
+			v0.Type = TypeFlags
+			v0.AddArg(x)
+			v0.AddArg(y)
+			v.AddArg(v0)
+			return true
+		}
+		goto endcecf13a952d4c6c2383561c7d68a3cf9
+	endcecf13a952d4c6c2383561c7d68a3cf9:
+		;
+	case OpLoad:
+		// match: (Load <t> ptr mem)
+		// cond: t.IsBoolean()
+		// result: (MOVBload [int64(0)] ptr mem)
+		{
+			t := v.Type
+			ptr := v.Args[0]
+			mem := v.Args[1]
+			if !(t.IsBoolean()) {
+				goto end73f21632e56c3614902d3c29c82dc4ea
+			}
+			v.Op = OpMOVBload
+			v.Aux = nil
+			v.resetArgs()
+			v.Aux = int64(0)
+			v.AddArg(ptr)
+			v.AddArg(mem)
+			return true
+		}
+		goto end73f21632e56c3614902d3c29c82dc4ea
+	end73f21632e56c3614902d3c29c82dc4ea:
+		;
+		// match: (Load <t> ptr mem)
+		// cond: (is64BitInt(t) || isPtr(t))
+		// result: (MOVQload [int64(0)] ptr mem)
+		{
+			t := v.Type
+			ptr := v.Args[0]
+			mem := v.Args[1]
+			if !(is64BitInt(t) || isPtr(t)) {
+				goto end581ce5a20901df1b8143448ba031685b
+			}
+			v.Op = OpMOVQload
+			v.Aux = nil
+			v.resetArgs()
+			v.Aux = int64(0)
+			v.AddArg(ptr)
+			v.AddArg(mem)
+			return true
+		}
+		goto end581ce5a20901df1b8143448ba031685b
+	end581ce5a20901df1b8143448ba031685b:
+		;
+	case OpLsh:
+		// match: (Lsh <t> x y)
+		// cond: is64BitInt(t)
+		// result: (SHLQ x y)
+		{
+			t := v.Type
+			x := v.Args[0]
+			y := v.Args[1]
+			if !(is64BitInt(t)) {
+				goto end9f05c9539e51db6ad557989e0c822e9b
+			}
+			v.Op = OpSHLQ
+			v.Aux = nil
+			v.resetArgs()
+			v.AddArg(x)
+			v.AddArg(y)
+			return true
+		}
+		goto end9f05c9539e51db6ad557989e0c822e9b
+	end9f05c9539e51db6ad557989e0c822e9b:
+		;
+	case OpMOVQload:
+		// match: (MOVQload [off1] (ADDQconst [off2] ptr) mem)
+		// cond:
+		// result: (MOVQload [addOff(off1, off2)] ptr mem)
+		{
+			off1 := v.Aux
+			if v.Args[0].Op != OpADDQconst {
+				goto end843d29b538c4483b432b632e5666d6e3
+			}
+			off2 := v.Args[0].Aux
+			ptr := v.Args[0].Args[0]
+			mem := v.Args[1]
+			v.Op = OpMOVQload
+			v.Aux = nil
+			v.resetArgs()
+			v.Aux = addOff(off1, off2)
+			v.AddArg(ptr)
+			v.AddArg(mem)
+			return true
+		}
+		goto end843d29b538c4483b432b632e5666d6e3
+	end843d29b538c4483b432b632e5666d6e3:
+		;
+		// match: (MOVQload [off1] (LEAQ8 [off2] ptr idx) mem)
+		// cond:
+		// result: (MOVQloadidx8 [addOff(off1, off2)] ptr idx mem)
+		{
+			off1 := v.Aux
+			if v.Args[0].Op != OpLEAQ8 {
+				goto end02f5ad148292c46463e7c20d3b821735
+			}
+			off2 := v.Args[0].Aux
+			ptr := v.Args[0].Args[0]
+			idx := v.Args[0].Args[1]
+			mem := v.Args[1]
+			v.Op = OpMOVQloadidx8
+			v.Aux = nil
+			v.resetArgs()
+			v.Aux = addOff(off1, off2)
+			v.AddArg(ptr)
+			v.AddArg(idx)
+			v.AddArg(mem)
+			return true
+		}
+		goto end02f5ad148292c46463e7c20d3b821735
+	end02f5ad148292c46463e7c20d3b821735:
+		;
+	case OpMOVQloadidx8:
+		// match: (MOVQloadidx8 [off1] (ADDQconst [off2] ptr) idx mem)
+		// cond:
+		// result: (MOVQloadidx8 [addOff(off1, off2)] ptr idx mem)
+		{
+			off1 := v.Aux
+			if v.Args[0].Op != OpADDQconst {
+				goto ende81e44bcfb11f90916ccb440c590121f
+			}
+			off2 := v.Args[0].Aux
+			ptr := v.Args[0].Args[0]
+			idx := v.Args[1]
+			mem := v.Args[2]
+			v.Op = OpMOVQloadidx8
+			v.Aux = nil
+			v.resetArgs()
+			v.Aux = addOff(off1, off2)
+			v.AddArg(ptr)
+			v.AddArg(idx)
+			v.AddArg(mem)
+			return true
+		}
+		goto ende81e44bcfb11f90916ccb440c590121f
+	ende81e44bcfb11f90916ccb440c590121f:
+		;
+	case OpMOVQstore:
+		// match: (MOVQstore [off1] (ADDQconst [off2] ptr) val mem)
+		// cond:
+		// result: (MOVQstore [addOff(off1, off2)] ptr val mem)
+		{
+			off1 := v.Aux
+			if v.Args[0].Op != OpADDQconst {
+				goto end2108c693a43c79aed10b9246c39c80aa
+			}
+			off2 := v.Args[0].Aux
+			ptr := v.Args[0].Args[0]
+			val := v.Args[1]
+			mem := v.Args[2]
+			v.Op = OpMOVQstore
+			v.Aux = nil
+			v.resetArgs()
+			v.Aux = addOff(off1, off2)
+			v.AddArg(ptr)
+			v.AddArg(val)
+			v.AddArg(mem)
+			return true
+		}
+		goto end2108c693a43c79aed10b9246c39c80aa
+	end2108c693a43c79aed10b9246c39c80aa:
+		;
+		// match: (MOVQstore [off1] (LEAQ8 [off2] ptr idx) val mem)
+		// cond:
+		// result: (MOVQstoreidx8 [addOff(off1, off2)] ptr idx val mem)
+		{
+			off1 := v.Aux
+			if v.Args[0].Op != OpLEAQ8 {
+				goto endce1db8c8d37c8397c500a2068a65c215
+			}
+			off2 := v.Args[0].Aux
+			ptr := v.Args[0].Args[0]
+			idx := v.Args[0].Args[1]
+			val := v.Args[1]
+			mem := v.Args[2]
+			v.Op = OpMOVQstoreidx8
+			v.Aux = nil
+			v.resetArgs()
+			v.Aux = addOff(off1, off2)
+			v.AddArg(ptr)
+			v.AddArg(idx)
+			v.AddArg(val)
+			v.AddArg(mem)
+			return true
+		}
+		goto endce1db8c8d37c8397c500a2068a65c215
+	endce1db8c8d37c8397c500a2068a65c215:
+		;
+	case OpMOVQstoreidx8:
+		// match: (MOVQstoreidx8 [off1] (ADDQconst [off2] ptr) idx val mem)
+		// cond:
+		// result: (MOVQstoreidx8 [addOff(off1, off2)] ptr idx val mem)
+		{
+			off1 := v.Aux
+			if v.Args[0].Op != OpADDQconst {
+				goto end01c970657b0fdefeab82458c15022163
+			}
+			off2 := v.Args[0].Aux
+			ptr := v.Args[0].Args[0]
+			idx := v.Args[1]
+			val := v.Args[2]
+			mem := v.Args[3]
+			v.Op = OpMOVQstoreidx8
+			v.Aux = nil
+			v.resetArgs()
+			v.Aux = addOff(off1, off2)
+			v.AddArg(ptr)
+			v.AddArg(idx)
+			v.AddArg(val)
+			v.AddArg(mem)
+			return true
+		}
+		goto end01c970657b0fdefeab82458c15022163
+	end01c970657b0fdefeab82458c15022163:
+		;
+	case OpMULQ:
+		// match: (MULQ x (MOVQconst [c]))
+		// cond: c.(int64) == int64(int32(c.(int64)))
+		// result: (MULQconst [c] x)
+		{
+			x := v.Args[0]
+			if v.Args[1].Op != OpMOVQconst {
+				goto ende8c09b194fcde7d9cdc69f2deff86304
+			}
+			c := v.Args[1].Aux
+			if !(c.(int64) == int64(int32(c.(int64)))) {
+				goto ende8c09b194fcde7d9cdc69f2deff86304
+			}
+			v.Op = OpMULQconst
+			v.Aux = nil
+			v.resetArgs()
+			v.Aux = c
+			v.AddArg(x)
+			return true
+		}
+		goto ende8c09b194fcde7d9cdc69f2deff86304
+	ende8c09b194fcde7d9cdc69f2deff86304:
+		;
+		// match: (MULQ (MOVQconst [c]) x)
+		// cond:
+		// result: (MULQconst [c] x)
+		{
+			if v.Args[0].Op != OpMOVQconst {
+				goto endc6e18d6968175d6e58eafa6dcf40c1b8
+			}
+			c := v.Args[0].Aux
+			x := v.Args[1]
+			v.Op = OpMULQconst
+			v.Aux = nil
+			v.resetArgs()
+			v.Aux = c
+			v.AddArg(x)
+			return true
+		}
+		goto endc6e18d6968175d6e58eafa6dcf40c1b8
+	endc6e18d6968175d6e58eafa6dcf40c1b8:
+		;
+	case OpMULQconst:
+		// match: (MULQconst [c] x)
+		// cond: c.(int64) == 8
+		// result: (SHLQconst [int64(3)] x)
+		{
+			c := v.Aux
+			x := v.Args[0]
+			if !(c.(int64) == 8) {
+				goto end7e16978c56138324ff2abf91fd6d94d4
+			}
+			v.Op = OpSHLQconst
+			v.Aux = nil
+			v.resetArgs()
+			v.Aux = int64(3)
+			v.AddArg(x)
+			return true
+		}
+		goto end7e16978c56138324ff2abf91fd6d94d4
+	end7e16978c56138324ff2abf91fd6d94d4:
+		;
+		// match: (MULQconst [c] x)
+		// cond: c.(int64) == 64
+		// result: (SHLQconst [int64(5)] x)
+		{
+			c := v.Aux
+			x := v.Args[0]
+			if !(c.(int64) == 64) {
+				goto end2c7a02f230e4b311ac3a4e22f70a4f08
+			}
+			v.Op = OpSHLQconst
+			v.Aux = nil
+			v.resetArgs()
+			v.Aux = int64(5)
+			v.AddArg(x)
+			return true
+		}
+		goto end2c7a02f230e4b311ac3a4e22f70a4f08
+	end2c7a02f230e4b311ac3a4e22f70a4f08:
+		;
+	case OpMove:
+		// match: (Move [size] dst src mem)
+		// cond:
+		// result: (REPMOVSB dst src (Const <TypeUInt64> [size.(int64)]) mem)
+		{
+			size := v.Aux
+			dst := v.Args[0]
+			src := v.Args[1]
+			mem := v.Args[2]
+			v.Op = OpREPMOVSB
+			v.Aux = nil
+			v.resetArgs()
+			v.AddArg(dst)
+			v.AddArg(src)
+			v0 := v.Block.NewValue(OpConst, TypeInvalid, nil)
+			v0.Type = TypeUInt64
+			v0.Aux = size.(int64)
+			v.AddArg(v0)
+			v.AddArg(mem)
+			return true
+		}
+		goto end48909259b265a6bb2a076bc2c2dc7d1f
+	end48909259b265a6bb2a076bc2c2dc7d1f:
+		;
+	case OpMul:
+		// match: (Mul <t> x y)
+		// cond: is64BitInt(t)
+		// result: (MULQ x y)
+		{
+			t := v.Type
+			x := v.Args[0]
+			y := v.Args[1]
+			if !(is64BitInt(t)) {
+				goto endfab0d598f376ecba45a22587d50f7aff
+			}
+			v.Op = OpMULQ
+			v.Aux = nil
+			v.resetArgs()
+			v.AddArg(x)
+			v.AddArg(y)
+			return true
+		}
+		goto endfab0d598f376ecba45a22587d50f7aff
+	endfab0d598f376ecba45a22587d50f7aff:
+		;
+	case OpOffPtr:
+		// match: (OffPtr [off] ptr)
+		// cond:
+		// result: (ADDQconst [off] ptr)
+		{
+			off := v.Aux
+			ptr := v.Args[0]
+			v.Op = OpADDQconst
+			v.Aux = nil
+			v.resetArgs()
+			v.Aux = off
+			v.AddArg(ptr)
+			return true
+		}
+		goto end0429f947ee7ac49ff45a243e461a5290
+	end0429f947ee7ac49ff45a243e461a5290:
+		;
+	case OpSETL:
+		// match: (SETL (InvertFlags x))
+		// cond:
+		// result: (SETGE x)
+		{
+			if v.Args[0].Op != OpInvertFlags {
+				goto end456c7681d48305698c1ef462d244bdc6
+			}
+			x := v.Args[0].Args[0]
+			v.Op = OpSETGE
+			v.Aux = nil
+			v.resetArgs()
+			v.AddArg(x)
+			return true
+		}
+		goto end456c7681d48305698c1ef462d244bdc6
+	end456c7681d48305698c1ef462d244bdc6:
+		;
+	case OpSHLQ:
+		// match: (SHLQ x (MOVQconst [c]))
+		// cond:
+		// result: (SHLQconst [c] x)
+		{
+			x := v.Args[0]
+			if v.Args[1].Op != OpMOVQconst {
+				goto endcca412bead06dc3d56ef034a82d184d6
+			}
+			c := v.Args[1].Aux
+			v.Op = OpSHLQconst
+			v.Aux = nil
+			v.resetArgs()
+			v.Aux = c
+			v.AddArg(x)
+			return true
+		}
+		goto endcca412bead06dc3d56ef034a82d184d6
+	endcca412bead06dc3d56ef034a82d184d6:
+		;
+	case OpSUBQ:
+		// match: (SUBQ x (MOVQconst [c]))
+		// cond:
+		// result: (SUBQconst x [c])
+		{
+			x := v.Args[0]
+			if v.Args[1].Op != OpMOVQconst {
+				goto end5a74a63bd9ad15437717c6df3b25eebb
+			}
+			c := v.Args[1].Aux
+			v.Op = OpSUBQconst
+			v.Aux = nil
+			v.resetArgs()
+			v.AddArg(x)
+			v.Aux = c
+			return true
+		}
+		goto end5a74a63bd9ad15437717c6df3b25eebb
+	end5a74a63bd9ad15437717c6df3b25eebb:
+		;
+		// match: (SUBQ <t> (MOVQconst [c]) x)
+		// cond:
+		// result: (NEGQ (SUBQconst <t> x [c]))
+		{
+			t := v.Type
+			if v.Args[0].Op != OpMOVQconst {
+				goto end78e66b6fc298684ff4ac8aec5ce873c9
+			}
+			c := v.Args[0].Aux
+			x := v.Args[1]
+			v.Op = OpNEGQ
+			v.Aux = nil
+			v.resetArgs()
+			v0 := v.Block.NewValue(OpSUBQconst, TypeInvalid, nil)
+			v0.Type = t
+			v0.AddArg(x)
+			v0.Aux = c
+			v.AddArg(v0)
+			return true
+		}
+		goto end78e66b6fc298684ff4ac8aec5ce873c9
+	end78e66b6fc298684ff4ac8aec5ce873c9:
+		;
+	case OpStore:
+		// match: (Store ptr val mem)
+		// cond: (is64BitInt(val.Type) || isPtr(val.Type))
+		// result: (MOVQstore [int64(0)] ptr val mem)
+		{
+			ptr := v.Args[0]
+			val := v.Args[1]
+			mem := v.Args[2]
+			if !(is64BitInt(val.Type) || isPtr(val.Type)) {
+				goto end9680b43f504bc06f9fab000823ce471a
+			}
+			v.Op = OpMOVQstore
+			v.Aux = nil
+			v.resetArgs()
+			v.Aux = int64(0)
+			v.AddArg(ptr)
+			v.AddArg(val)
+			v.AddArg(mem)
+			return true
+		}
+		goto end9680b43f504bc06f9fab000823ce471a
+	end9680b43f504bc06f9fab000823ce471a:
+		;
+	case OpSub:
+		// match: (Sub <t> x y)
+		// cond: is64BitInt(t)
+		// result: (SUBQ x y)
+		{
+			t := v.Type
+			x := v.Args[0]
+			y := v.Args[1]
+			if !(is64BitInt(t)) {
+				goto ende6ef29f885a8ecf3058212bb95917323
+			}
+			v.Op = OpSUBQ
+			v.Aux = nil
+			v.resetArgs()
+			v.AddArg(x)
+			v.AddArg(y)
+			return true
+		}
+		goto ende6ef29f885a8ecf3058212bb95917323
+	ende6ef29f885a8ecf3058212bb95917323:
+	}
+	return false
+}
diff --git a/src/cmd/compile/internal/ssa/op.go b/src/cmd/compile/internal/ssa/op.go
new file mode 100644
index 0000000000..f02c1ae0c0
--- /dev/null
+++ b/src/cmd/compile/internal/ssa/op.go
@@ -0,0 +1,204 @@
+// 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"
+
+// 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.
+// Architecture-independent opcodes appear in this file.
+// Architecture-dependent opcodes appear in op{arch}.go files.
+type Op int32
+
+// Opcode ranges, a generic one and one for each architecture.
+const (
+	opInvalid     Op = 0
+	opGenericBase Op = 1 + 1000*iota
+	opAMD64Base
+	op386Base
+
+	opMax // sentinel
+)
+
+// Generic opcodes
+const (
+	opGenericStart Op = opGenericBase + iota
+
+	// 2-input arithmetic
+	OpAdd // arg0 + arg1
+	OpSub // arg0 - arg1
+	OpMul // arg0 * arg1
+	OpLsh // arg0 << arg1
+	OpRsh // arg0 >> arg1 (signed/unsigned depending on signedness of type)
+
+	// 2-input comparisons
+	OpLess // arg0 < arg1
+
+	// constants.  Constant values are stored in the aux field.
+	// booleans have a bool aux field, strings have a string aux
+	// field, and so on.  All integer types store their value
+	// in the aux field as an int64 (including int, uint64, etc.).
+	// We could store int8 as an int8, but that won't work for int,
+	// as it may be different widths on the host and target.
+	OpConst
+
+	OpArg    // address of a function parameter/result.  Memory input is an arg called ".mem".  aux is a string (TODO: make it something other than a string?)
+	OpGlobal // the address of a global variable aux.(*gc.Sym)
+	OpFunc   // entry address of a function
+	OpFP     // frame pointer
+	OpSP     // stack pointer
+
+	OpCopy // output = arg0
+	OpMove // arg0=destptr, arg1=srcptr, arg2=mem, aux.(int64)=size.  Returns memory.
+	OpPhi  // select an argument based on which predecessor block we came from
+
+	OpSliceMake // arg0=ptr, arg1=len, arg2=cap
+	OpSlicePtr  // ptr(arg0)
+	OpSliceLen  // len(arg0)
+	OpSliceCap  // cap(arg0)
+
+	OpStringMake // arg0=ptr, arg1=len
+	OpStringPtr  // ptr(arg0)
+	OpStringLen  // len(arg0)
+
+	OpLoad       // Load from arg0+aux.(int64).  arg1=memory
+	OpStore      // Store arg1 to arg0+aux.(int64).  arg2=memory.  Returns memory.
+	OpArrayIndex // arg0=array, arg1=index.  Returns a[i]
+	OpPtrIndex   // arg0=ptr, arg1=index. Computes ptr+sizeof(*v.type)*index, where index is extended to ptrwidth type
+	OpIsNonNil   // arg0 != nil
+	OpIsInBounds // 0 <= arg0 < arg1
+
+	// function calls.  Arguments to the call have already been written to the stack.
+	// Return values appear on the stack.  The method receiver, if any, is treated
+	// as a phantom first argument.
+	OpCall       // arg0=code pointer, arg1=context ptr, arg2=memory.  Returns memory.
+	OpStaticCall // call function aux.(*gc.Sym), arg0=memory.  Returns memory.
+
+	OpConvert // convert arg0 to another type
+	OpConvNop // interpret arg0 as another type
+
+	OpOffPtr // arg0 + aux.(int64) (arg0 and result are pointers)
+
+	// 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 without memory
+	// args because we know there is no aliasing of spill slots on the stack.
+	OpStoreReg8
+	OpLoadReg8
+
+	// used during ssa construction.  Like OpCopy, but the arg has not been specified yet.
+	OpFwdRef
+
+	OpGenericEnd
+)
+
+// GlobalOffset represents a fixed offset within a global variable
+type GlobalOffset struct {
+	Global interface{} // holds a *gc.Sym
+	Offset int64
+}
+
+// offset adds x to the location specified by g and returns it.
+func (g GlobalOffset) offset(x int64) GlobalOffset {
+	return GlobalOffset{g.Global, g.Offset + x}
+}
+
+func (g GlobalOffset) String() string {
+	return fmt.Sprintf("%v+%d", g.Global, g.Offset)
+}
+
+//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
+
+	// 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
+}
+
+const (
+	// possible properties of opcodes
+	OpFlagCommutative int32 = 1 << iota
+)
+
+// Opcodes that represent the input Go program
+var genericTable = map[Op]opInfo{
+	// the unknown op is used only during building and should not appear in a
+	// fully formed ssa representation.
+
+	OpAdd:  {flags: OpFlagCommutative},
+	OpSub:  {},
+	OpMul:  {flags: OpFlagCommutative},
+	OpLess: {},
+
+	OpConst:  {}, // aux matches the type (e.g. bool, int64 float64)
+	OpArg:    {}, // aux is the name of the input variable.  Currently only ".mem" is used
+	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:]
+
+	*/
+}
+
+// table of opcodes, indexed by opcode ID
+var opcodeTable [opMax]opInfo
+
+func init() {
+	for op, info := range genericTable {
+		opcodeTable[op] = info
+	}
+}
diff --git a/src/cmd/compile/internal/ssa/op_string.go b/src/cmd/compile/internal/ssa/op_string.go
new file mode 100644
index 0000000000..c8f27bb2e4
--- /dev/null
+++ b/src/cmd/compile/internal/ssa/op_string.go
@@ -0,0 +1,40 @@
+// generated by stringer -type=Op; DO NOT EDIT
+
+package ssa
+
+import "fmt"
+
+const (
+	_Op_name_0 = "opInvalid"
+	_Op_name_1 = "opGenericBaseOpAddOpSubOpMulOpLshOpRshOpLessOpConstOpArgOpGlobalOpFuncOpFPOpSPOpCopyOpMoveOpPhiOpSliceMakeOpSlicePtrOpSliceLenOpSliceCapOpStringMakeOpStringPtrOpStringLenOpLoadOpStoreOpArrayIndexOpPtrIndexOpIsNonNilOpIsInBoundsOpCallOpStaticCallOpConvertOpConvNopOpOffPtrOpStoreReg8OpLoadReg8OpFwdRefOpGenericEnd"
+	_Op_name_2 = "opAMD64BaseOpADDQOpADDQconstOpSUBQOpSUBQconstOpMULQOpMULQconstOpSHLQOpSHLQconstOpNEGQOpADDLOpCMPQOpCMPQconstOpTESTQOpTESTBOpSETEQOpSETNEOpSETLOpSETGEOpSETBOpInvertFlagsOpLEAQOpLEAQ2OpLEAQ4OpLEAQ8OpLEAQglobalOpMOVBloadOpMOVBQZXloadOpMOVBQSXloadOpMOVQloadOpMOVQstoreOpMOVQloadidx8OpMOVQstoreidx8OpMOVQloadglobalOpMOVQstoreglobalOpMOVQconstOpREPMOVSB"
+	_Op_name_3 = "op386Base"
+	_Op_name_4 = "opMax"
+)
+
+var (
+	_Op_index_0 = [...]uint8{0, 9}
+	_Op_index_1 = [...]uint16{0, 13, 18, 23, 28, 33, 38, 44, 51, 56, 64, 70, 74, 78, 84, 90, 95, 106, 116, 126, 136, 148, 159, 170, 176, 183, 195, 205, 215, 227, 233, 245, 254, 263, 271, 282, 292, 300, 312}
+	_Op_index_2 = [...]uint16{0, 11, 17, 28, 34, 45, 51, 62, 68, 79, 85, 91, 97, 108, 115, 122, 129, 136, 142, 149, 155, 168, 174, 181, 188, 195, 207, 217, 230, 243, 253, 264, 278, 293, 309, 326, 337, 347}
+	_Op_index_3 = [...]uint8{0, 9}
+	_Op_index_4 = [...]uint8{0, 5}
+)
+
+func (i Op) String() string {
+	switch {
+	case i == 0:
+		return _Op_name_0
+	case 1001 <= i && i <= 1038:
+		i -= 1001
+		return _Op_name_1[_Op_index_1[i]:_Op_index_1[i+1]]
+	case 2001 <= i && i <= 2037:
+		i -= 2001
+		return _Op_name_2[_Op_index_2[i]:_Op_index_2[i+1]]
+	case i == 3001:
+		return _Op_name_3
+	case i == 4001:
+		return _Op_name_4
+	default:
+		return fmt.Sprintf("Op(%d)", i)
+	}
+}
diff --git a/src/cmd/compile/internal/ssa/opamd64.go b/src/cmd/compile/internal/ssa/opamd64.go
new file mode 100644
index 0000000000..46a0069a18
--- /dev/null
+++ b/src/cmd/compile/internal/ssa/opamd64.go
@@ -0,0 +1,177 @@
+// 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
+
+// amd64-specific opcodes
+
+const (
+	opAMD64start Op = opAMD64Base + iota
+
+	// Suffixes encode the bit width of various instructions.
+	// Q = 64 bit, L = 32 bit, W = 16 bit, B = 8 bit
+
+	// arithmetic
+	OpADDQ      // arg0 + arg1
+	OpADDQconst // arg + aux.(int64)
+	OpSUBQ      // arg0 - arg1
+	OpSUBQconst // arg - aux.(int64)
+	OpMULQ      // arg0 * arg1
+	OpMULQconst // arg * aux.(int64)
+	OpSHLQ      // arg0 << arg1
+	OpSHLQconst // arg << aux.(int64)
+	OpNEGQ      // -arg
+	OpADDL      // arg0 + arg1
+
+	// Flags value generation.
+	// We pretend the flags type is an opaque thing that comparisons generate
+	// and from which we can extract boolean conditions like <, ==, etc.
+	OpCMPQ      // arg0 compare to arg1
+	OpCMPQconst // arg0 compare to aux.(int64)
+	OpTESTQ     // (arg0 & arg1) compare to 0
+	OpTESTB     // (arg0 & arg1) compare to 0
+
+	// These opcodes extract a particular boolean condition from a flags value.
+	OpSETEQ // extract == condition from arg0
+	OpSETNE // extract != condition from arg0
+	OpSETL  // extract signed < condition from arg0
+	OpSETGE // extract signed >= condition from arg0
+	OpSETB  // extract unsigned < condition from arg0
+
+	// InvertFlags reverses the direction of a flags type interpretation:
+	// (InvertFlags (OpCMPQ a b)) == (OpCMPQ b a)
+	// This is a pseudo-op which can't appear in assembly output.
+	OpInvertFlags // reverse direction of arg0
+
+	OpLEAQ       // arg0 + arg1 + aux.(int64)
+	OpLEAQ2      // arg0 + 2*arg1 + aux.(int64)
+	OpLEAQ4      // arg0 + 4*arg1 + aux.(int64)
+	OpLEAQ8      // arg0 + 8*arg1 + aux.(int64)
+	OpLEAQglobal // no args.  address of aux.(GlobalOffset)
+
+	// Load/store from general address
+	OpMOVBload // Load from arg0+aux.(int64).  arg1=memory
+	OpMOVBQZXload
+	OpMOVBQSXload
+	OpMOVQload
+	OpMOVQstore     // Store arg1 to arg0+aux.(int64).  arg2=memory, returns memory.
+	OpMOVQloadidx8  // Load from arg0+arg1*8+aux.(int64).  arg2=memory
+	OpMOVQstoreidx8 // Store arg2 to arg0+arg1*8+aux.(int64).  arg3=memory, returns memory.
+
+	// Load/store from global.  Same as the above loads, but arg0 is missing and aux is a GlobalOffset instead of an int64.
+	OpMOVQloadglobal  // arg0 = memory
+	OpMOVQstoreglobal // store arg0.  arg1=memory, returns memory.
+
+	// materialize a constant into a register
+	OpMOVQconst // (takes no arguments)
+
+	// move memory
+	OpREPMOVSB // arg0=destptr, arg1=srcptr, arg2=len, arg3=mem
+)
+
+type regMask uint64
+
+var regsAMD64 = [...]string{
+	"AX",
+	"CX",
+	"DX",
+	"BX",
+	"SP",
+	"BP",
+	"SI",
+	"DI",
+	"R8",
+	"R9",
+	"R10",
+	"R11",
+	"R12",
+	"R13",
+	"R14",
+	"R15",
+
+	// pseudo registers
+	"FP",
+	"FLAGS",
+	"OVERWRITE0", // the same register as the first input
+}
+
+var gp regMask = 0x1ffff   // all integer registers including SP&FP
+var gpout regMask = 0xffef // integer registers not including SP&FP
+var cx regMask = 1 << 1
+var si regMask = 1 << 6
+var di regMask = 1 << 7
+var flags regMask = 1 << 17
+
+var (
+	// gp = general purpose (integer) registers
+	gp21      = [2][]regMask{{gp, gp}, {gpout}} // 2 input, 1 output
+	gp11      = [2][]regMask{{gp}, {gpout}}     // 1 input, 1 output
+	gp01      = [2][]regMask{{}, {gpout}}       // 0 input, 1 output
+	shift     = [2][]regMask{{gp, cx}, {gpout}} // shift operations
+	gp2_flags = [2][]regMask{{gp, gp}, {flags}} // generate flags from 2 gp regs
+	gp1_flags = [2][]regMask{{gp}, {flags}}     // generate flags from 1 gp reg
+
+	gpload     = [2][]regMask{{gp, 0}, {gpout}}
+	gploadidx  = [2][]regMask{{gp, gp, 0}, {gpout}}
+	gpstore    = [2][]regMask{{gp, gp, 0}, {0}}
+	gpstoreidx = [2][]regMask{{gp, gp, gp, 0}, {0}}
+
+	gpload_stack  = [2][]regMask{{0}, {gpout}}
+	gpstore_stack = [2][]regMask{{gp, 0}, {0}}
+)
+
+// Opcodes that appear in an output amd64 program
+var amd64Table = map[Op]opInfo{
+	OpADDQ:      {flags: OpFlagCommutative, asm: "ADDQ\t%I0,%I1,%O0", reg: gp21}, // TODO: overwrite
+	OpADDQconst: {asm: "ADDQ\t$%A,%I0,%O0", reg: gp11},                           // aux = int64 constant to add
+	OpSUBQ:      {asm: "SUBQ\t%I0,%I1,%O0", reg: gp21},
+	OpSUBQconst: {asm: "SUBQ\t$%A,%I0,%O0", reg: gp11},
+	OpMULQ:      {asm: "MULQ\t%I0,%I1,%O0", reg: gp21},
+	OpMULQconst: {asm: "IMULQ\t$%A,%I0,%O0", reg: gp11},
+	OpSHLQ:      {asm: "SHLQ\t%I0,%I1,%O0", reg: gp21},
+	OpSHLQconst: {asm: "SHLQ\t$%A,%I0,%O0", reg: gp11},
+
+	OpCMPQ:      {asm: "CMPQ\t%I0,%I1", reg: gp2_flags}, // compute arg[0]-arg[1] and produce flags
+	OpCMPQconst: {asm: "CMPQ\t$%A,%I0", reg: gp1_flags},
+	OpTESTQ:     {asm: "TESTQ\t%I0,%I1", reg: gp2_flags},
+	OpTESTB:     {asm: "TESTB\t%I0,%I1", reg: gp2_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"},
+	OpLEAQglobal: {asm: "LEAQ\t%A(SB),%O0", reg: gp01},
+
+	// loads and stores
+	OpMOVBload:      {asm: "MOVB\t%A(%I0),%O0", reg: gpload},
+	OpMOVQload:      {asm: "MOVQ\t%A(%I0),%O0", reg: gpload},
+	OpMOVQstore:     {asm: "MOVQ\t%I1,%A(%I0)", reg: gpstore},
+	OpMOVQloadidx8:  {asm: "MOVQ\t%A(%I0)(%I1*8),%O0", reg: gploadidx},
+	OpMOVQstoreidx8: {asm: "MOVQ\t%I2,%A(%I0)(%I1*8)", reg: gpstoreidx},
+
+	OpMOVQconst: {asm: "MOVQ\t$%A,%O0", reg: gp01},
+
+	OpStaticCall: {asm: "CALL\t%A(SB)"},
+
+	OpCopy:    {asm: "MOVQ\t%I0,%O0", reg: gp11}, // TODO: make arch-specific
+	OpConvNop: {asm: "MOVQ\t%I0,%O0", reg: gp11}, // TODO: make arch-specific.  Or get rid of this altogether.
+
+	// convert from flags back to boolean
+	OpSETL: {},
+
+	// 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"},
+	OpStoreReg8: {asm: "MOVQ\t%I0,%O0"},
+
+	OpREPMOVSB: {asm: "REP MOVSB", reg: [2][]regMask{{di, si, cx, 0}, {0}}}, // TODO: record that si/di/cx are clobbered
+}
+
+func init() {
+	for op, info := range amd64Table {
+		opcodeTable[op] = info
+	}
+}
diff --git a/src/cmd/compile/internal/ssa/opt.go b/src/cmd/compile/internal/ssa/opt.go
new file mode 100644
index 0000000000..ea2bcf0e98
--- /dev/null
+++ b/src/cmd/compile/internal/ssa/opt.go
@@ -0,0 +1,13 @@
+// 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
+
+// machine-independent optimization
+
+//go:generate go run rulegen/rulegen.go rulegen/generic.rules genericRules generic.go
+
+func opt(f *Func) {
+	applyRewrite(f, genericRules)
+}
diff --git a/src/cmd/compile/internal/ssa/phielim.go b/src/cmd/compile/internal/ssa/phielim.go
new file mode 100644
index 0000000000..19c0d077e5
--- /dev/null
+++ b/src/cmd/compile/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/compile/internal/ssa/print.go b/src/cmd/compile/internal/ssa/print.go
new file mode 100644
index 0000000000..eeea30d970
--- /dev/null
+++ b/src/cmd/compile/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/compile/internal/ssa/regalloc.go b/src/cmd/compile/internal/ssa/regalloc.go
new file mode 100644
index 0000000000..c798d2e936
--- /dev/null
+++ b/src/cmd/compile/internal/ssa/regalloc.go
@@ -0,0 +1,456 @@
+package ssa
+
+import (
+	"fmt"
+	"log"
+	"sort"
+)
+
+func setloc(home []Location, v *Value, loc Location) []Location {
+	for v.ID >= ID(len(home)) {
+		home = append(home, nil)
+	}
+	home[v.ID] = loc
+	return home
+}
+
+type register uint
+
+// TODO: make arch-dependent
+var numRegs register = 32
+
+var registers = [...]Register{
+	Register{0, "AX"},
+	Register{1, "CX"},
+	Register{2, "DX"},
+	Register{3, "BX"},
+	Register{4, "SP"},
+	Register{5, "BP"},
+	Register{6, "SI"},
+	Register{7, "DI"},
+	Register{8, "R8"},
+	Register{9, "R9"},
+	Register{10, "R10"},
+	Register{11, "R11"},
+	Register{12, "R12"},
+	Register{13, "R13"},
+	Register{14, "R14"},
+	Register{15, "R15"},
+
+	// TODO X0, ...
+	// TODO: make arch-dependent
+	Register{16, "FP"}, // pseudo-register, actually a constant offset from SP
+	Register{17, "FLAGS"},
+	Register{18, "OVERWRITE"},
+}
+
+// countRegs returns the number of set bits in the register mask.
+func countRegs(r regMask) int {
+	n := 0
+	for r != 0 {
+		n += int(r & 1)
+		r >>= 1
+	}
+	return n
+}
+
+// pickReg picks an arbitrary register from the register mask.
+func pickReg(r regMask) register {
+	// pick the lowest one
+	if r == 0 {
+		panic("can't pick a register from an empty set")
+	}
+	for i := register(0); ; i++ {
+		if r&1 != 0 {
+			return i
+		}
+		r >>= 1
+	}
+}
+
+// regalloc performs register allocation on f.  It sets f.RegAlloc
+// to the resulting allocation.
+func regalloc(f *Func) {
+	// For now, a very simple allocator.  Everything has a home
+	// location on the stack (TBD as a subsequent stackalloc pass).
+	// Values live in the home locations at basic block boundaries.
+	// We use a simple greedy allocator within a basic block.
+	home := make([]Location, f.NumValues())
+
+	addPhiCopies(f) // add copies of phi inputs in preceeding blocks
+
+	// Compute live values at the end of each block.
+	live := live(f)
+	lastUse := make([]int, f.NumValues())
+
+	var oldSched []*Value
+
+	// Hack to find fp, sp Values and assign them a register. (TODO: make not so hacky)
+	var fp, sp *Value
+	for _, v := range f.Entry.Values {
+		switch v.Op {
+		case OpSP:
+			sp = v
+			home = setloc(home, v, &registers[4]) // TODO: arch-dependent
+		case OpFP:
+			fp = v
+			home = setloc(home, v, &registers[16]) // TODO: arch-dependent
+		}
+	}
+
+	// Register allocate each block separately.  All live values will live
+	// in home locations (stack slots) between blocks.
+	for _, b := range f.Blocks {
+
+		// Compute the index of the last use of each Value in the Block.
+		// Scheduling has already happened, so Values are totally ordered.
+		// lastUse[x] = max(i) where b.Value[i] uses Value x.
+		for i, v := range b.Values {
+			lastUse[v.ID] = -1
+			for _, w := range v.Args {
+				// could condition this store on w.Block == b, but no need
+				lastUse[w.ID] = i
+			}
+		}
+		// Values which are live at block exit have a lastUse of len(b.Values).
+		if b.Control != nil {
+			lastUse[b.Control.ID] = len(b.Values)
+		}
+		// Values live after block exit have a lastUse of len(b.Values)+1.
+		for _, vid := range live[b.ID] {
+			lastUse[vid] = len(b.Values) + 1
+		}
+
+		// For each register, store which value it contains
+		type regInfo struct {
+			v     *Value // stack-homed original value (or nil if empty)
+			c     *Value // the register copy of v
+			dirty bool   // if the stack-homed copy is out of date
+		}
+		regs := make([]regInfo, numRegs)
+
+		// TODO: hack: initialize fixed registers
+		regs[4] = regInfo{sp, sp, false}
+		regs[16] = regInfo{fp, fp, false}
+
+		var used regMask  // has a 1 for each non-nil entry in regs
+		var dirty regMask // has a 1 for each dirty entry in regs
+
+		oldSched = append(oldSched[:0], b.Values...)
+		b.Values = b.Values[:0]
+
+		for idx, v := range oldSched {
+			// For each instruction, do:
+			//   set up inputs to v in registers
+			//   pick output register
+			//   run insn
+			//   mark output register as dirty
+			// Note that v represents the Value at "home" (on the stack), and c
+			// is its register equivalent.  There are two ways to establish c:
+			//   - use of v.  c will be a load from v's home.
+			//   - definition of v.  c will be identical to v but will live in
+			//     a register.  v will be modified into a spill of c.
+			regspec := opcodeTable[v.Op].reg
+			inputs := regspec[0]
+			outputs := regspec[1]
+			if len(inputs) == 0 && len(outputs) == 0 {
+				// No register allocation required (or none specified yet)
+				b.Values = append(b.Values, v)
+				continue
+			}
+
+			// Compute a good input ordering.  Start with the most constrained input.
+			order := make([]intPair, len(inputs))
+			for i, input := range inputs {
+				order[i] = intPair{countRegs(input), i}
+			}
+			sort.Sort(byKey(order))
+
+			// nospill contains registers that we can't spill because
+			// we already set them up for use by the current instruction.
+			var nospill regMask
+			nospill |= 0x10010 // SP and FP can't be spilled (TODO: arch-specific)
+
+			// Move inputs into registers
+			for _, o := range order {
+				w := v.Args[o.val]
+				mask := inputs[o.val]
+				if mask == 0 {
+					// Input doesn't need a register
+					continue
+				}
+				// TODO: 2-address overwrite instructions
+
+				// Find registers that w is already in
+				var wreg regMask
+				for r := register(0); r < numRegs; r++ {
+					if regs[r].v == w {
+						wreg |= regMask(1) << r
+					}
+				}
+
+				var r register
+				if mask&wreg != 0 {
+					// w is already in an allowed register.  We're done.
+					r = pickReg(mask & wreg)
+				} else {
+					// Pick a register for w
+					// Priorities (in order)
+					//  - an unused register
+					//  - a clean register
+					//  - a dirty register
+					// TODO: for used registers, pick the one whose next use is the
+					// farthest in the future.
+					mask &^= nospill
+					if mask & ^dirty != 0 {
+						mask &^= dirty
+					}
+					if mask & ^used != 0 {
+						mask &^= used
+					}
+					r = pickReg(mask)
+
+					// Kick out whomever is using this register.
+					if regs[r].v != nil {
+						x := regs[r].v
+						c := regs[r].c
+						if regs[r].dirty && lastUse[x.ID] > idx {
+							// Write x back to home.  Its value is currently held in c.
+							x.Op = OpStoreReg8
+							x.Aux = nil
+							x.resetArgs()
+							x.AddArg(c)
+							b.Values = append(b.Values, x)
+							regs[r].dirty = false
+							dirty &^= regMask(1) << r
+						}
+						regs[r].v = nil
+						regs[r].c = nil
+						used &^= regMask(1) << r
+					}
+
+					// Load w into this register
+					var c *Value
+					if len(w.Args) == 0 {
+						// Materialize w
+						if w.Op == OpFP || w.Op == OpSP || w.Op == OpGlobal {
+							c = b.NewValue1(OpCopy, w.Type, nil, w)
+						} else {
+							c = b.NewValue(w.Op, w.Type, w.Aux)
+						}
+					} else if len(w.Args) == 1 && (w.Args[0].Op == OpFP || w.Args[0].Op == OpSP || w.Args[0].Op == OpGlobal) {
+						// Materialize offsets from SP/FP/Global
+						c = b.NewValue1(w.Op, w.Type, w.Aux, w.Args[0])
+					} else if wreg != 0 {
+						// Copy from another register.
+						// Typically just an optimization, but this is
+						// required if w is dirty.
+						s := pickReg(wreg)
+						// inv: s != r
+						c = b.NewValue(OpCopy, w.Type, nil)
+						c.AddArg(regs[s].c)
+					} else {
+						// Load from home location
+						c = b.NewValue(OpLoadReg8, w.Type, nil)
+						c.AddArg(w)
+					}
+					home = setloc(home, c, &registers[r])
+					// Remember what we did
+					regs[r].v = w
+					regs[r].c = c
+					regs[r].dirty = false
+					used |= regMask(1) << r
+				}
+
+				// Replace w with its in-register copy.
+				v.SetArg(o.val, regs[r].c)
+
+				// Remember not to undo this register assignment until after
+				// the instruction is issued.
+				nospill |= regMask(1) << r
+			}
+
+			// pick a register for v itself.
+			if len(outputs) > 1 {
+				panic("can't do multi-output yet")
+			}
+			if len(outputs) == 0 || outputs[0] == 0 {
+				// output doesn't need a register
+				b.Values = append(b.Values, v)
+			} else {
+				mask := outputs[0]
+				if mask & ^dirty != 0 {
+					mask &^= dirty
+				}
+				if mask & ^used != 0 {
+					mask &^= used
+				}
+				r := pickReg(mask)
+
+				// Kick out whomever is using this register.
+				if regs[r].v != nil {
+					x := regs[r].v
+					c := regs[r].c
+					if regs[r].dirty && lastUse[x.ID] > idx {
+						// Write x back to home.  Its value is currently held in c.
+						x.Op = OpStoreReg8
+						x.Aux = nil
+						x.resetArgs()
+						x.AddArg(c)
+						b.Values = append(b.Values, x)
+						regs[r].dirty = false
+						dirty &^= regMask(1) << r
+					}
+					regs[r].v = nil
+					regs[r].c = nil
+					used &^= regMask(1) << r
+				}
+
+				// Reissue v with new op, with r as its home.
+				c := b.NewValue(v.Op, v.Type, v.Aux)
+				c.AddArgs(v.Args...)
+				home = setloc(home, c, &registers[r])
+
+				// Remember what we did
+				regs[r].v = v
+				regs[r].c = c
+				regs[r].dirty = true
+				used |= regMask(1) << r
+				dirty |= regMask(1) << r
+			}
+		}
+
+		// If the block ends in a call, we must put the call after the spill code.
+		var call *Value
+		if b.Kind == BlockCall {
+			call = b.Control
+			if call != b.Values[len(b.Values)-1] {
+				log.Fatalf("call not at end of block %b %v", b, call)
+			}
+			b.Values = b.Values[:len(b.Values)-1]
+			// TODO: do this for all control types?
+		}
+
+		// at the end of the block, spill any remaining dirty, live values
+		for r := register(0); r < numRegs; r++ {
+			if !regs[r].dirty {
+				continue
+			}
+			v := regs[r].v
+			c := regs[r].c
+			if lastUse[v.ID] <= len(oldSched) {
+				if v == v.Block.Control {
+					// link control value to register version
+					v.Block.Control = c
+				}
+				continue // not live after block
+			}
+
+			// change v to be a copy of c
+			v.Op = OpStoreReg8
+			v.Aux = nil
+			v.resetArgs()
+			v.AddArg(c)
+			b.Values = append(b.Values, v)
+		}
+
+		// add call back after spills
+		if b.Kind == BlockCall {
+			b.Values = append(b.Values, call)
+		}
+	}
+	f.RegAlloc = home
+	deadcode(f) // remove values that had all of their uses rematerialized.  TODO: separate pass?
+}
+
+// addPhiCopies adds copies of phi inputs in the blocks
+// immediately preceding the phi's block.
+func addPhiCopies(f *Func) {
+	for _, b := range f.Blocks {
+		for _, v := range b.Values {
+			if v.Op != OpPhi {
+				break // all phis should appear first
+			}
+			if v.Type.IsMemory() { // TODO: only "regallocable" types
+				continue
+			}
+			for i, w := range v.Args {
+				c := b.Preds[i]
+				cpy := c.NewValue1(OpCopy, v.Type, nil, w)
+				v.Args[i] = cpy
+			}
+		}
+	}
+}
+
+// live returns a map from block ID to a list of value IDs live at the end of that block
+// TODO: this could be quadratic if lots of variables are live across lots of
+// basic blocks.  Figure out a way to make this function (or, more precisely, the user
+// of this function) require only linear size & time.
+func live(f *Func) [][]ID {
+	live := make([][]ID, f.NumBlocks())
+	var phis []*Value
+
+	s := newSparseSet(f.NumValues())
+	t := newSparseSet(f.NumValues())
+	for {
+		for _, b := range f.Blocks {
+			fmt.Printf("live %s %v\n", b, live[b.ID])
+		}
+		changed := false
+
+		for _, b := range f.Blocks {
+			// Start with known live values at the end of the block
+			s.clear()
+			s.addAll(live[b.ID])
+
+			// Propagate backwards to the start of the block
+			// Assumes Values have been scheduled.
+			phis := phis[:0]
+			for i := len(b.Values) - 1; i >= 0; i-- {
+				v := b.Values[i]
+				s.remove(v.ID)
+				if v.Op == OpPhi {
+					// save phi ops for later
+					phis = append(phis, v)
+					continue
+				}
+				s.addAllValues(v.Args)
+			}
+
+			// for each predecessor of b, expand its list of live-at-end values
+			// inv: s contains the values live at the start of b (excluding phi inputs)
+			for i, p := range b.Preds {
+				t.clear()
+				t.addAll(live[p.ID])
+				t.addAll(s.contents())
+				for _, v := range phis {
+					t.add(v.Args[i].ID)
+				}
+				if t.size() == len(live[p.ID]) {
+					continue
+				}
+				// grow p's live set
+				c := make([]ID, t.size())
+				copy(c, t.contents())
+				live[p.ID] = c
+				changed = true
+			}
+		}
+
+		if !changed {
+			break
+		}
+	}
+	return live
+}
+
+// for sorting a pair of integers by key
+type intPair struct {
+	key, val int
+}
+type byKey []intPair
+
+func (a byKey) Len() int           { return len(a) }
+func (a byKey) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }
+func (a byKey) Less(i, j int) bool { return a[i].key < a[j].key }
diff --git a/src/cmd/compile/internal/ssa/rewrite.go b/src/cmd/compile/internal/ssa/rewrite.go
new file mode 100644
index 0000000000..671270d7f2
--- /dev/null
+++ b/src/cmd/compile/internal/ssa/rewrite.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 "log"
+
+func applyRewrite(f *Func, r func(*Value) bool) {
+	// repeat rewrites until we find no more rewrites
+	var curv *Value
+	defer func() {
+		if curv != nil {
+			log.Printf("panic during rewrite of %s\n", curv.LongString())
+			// TODO(khr): print source location also
+		}
+	}()
+	for {
+		change := false
+		for _, b := range f.Blocks {
+			for _, v := range b.Values {
+				// elide any copies generated during rewriting
+				for i, a := range v.Args {
+					if a.Op != OpCopy {
+						continue
+					}
+					for a.Op == OpCopy {
+						a = a.Args[0]
+					}
+					v.Args[i] = a
+				}
+
+				// apply rewrite function
+				curv = v
+				if r(v) {
+					change = true
+				}
+			}
+		}
+		if !change {
+			curv = nil
+			return
+		}
+	}
+}
+
+// Common functions called from rewriting rules
+
+func is64BitInt(t Type) bool {
+	return t.Size() == 8 && t.IsInteger()
+}
+
+func is32BitInt(t Type) bool {
+	return t.Size() == 4 && t.IsInteger()
+}
+
+func isPtr(t Type) bool {
+	return t.IsPtr()
+}
+
+func isSigned(t Type) bool {
+	return t.IsSigned()
+}
+
+func typeSize(t Type) int64 {
+	return t.Size()
+}
+
+// addOff adds two offset aux values.  Each should be an int64.  Fails if wraparound happens.
+func addOff(a, b interface{}) interface{} {
+	return addOffset(a.(int64), b.(int64))
+}
+func addOffset(x, y int64) int64 {
+	z := x + y
+	// x and y have same sign and z has a different sign => overflow
+	if x^y >= 0 && x^z < 0 {
+		log.Panicf("offset overflow %d %d\n", x, y)
+	}
+	return z
+}
+
+func inBounds(idx, len int64) bool {
+	return idx >= 0 && idx < len
+}
diff --git a/src/cmd/compile/internal/ssa/rulegen/generic.rules b/src/cmd/compile/internal/ssa/rulegen/generic.rules
new file mode 100644
index 0000000000..c49d9d9f2e
--- /dev/null
+++ b/src/cmd/compile/internal/ssa/rulegen/generic.rules
@@ -0,0 +1,24 @@
+// 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.
+
+// constant folding
+(Add <t> (Const [c]) (Const [d])) && is64BitInt(t) -> (Const [{c.(int64)+d.(int64)}])
+(Mul <t> (Const [c]) (Const [d])) && is64BitInt(t) -> (Const [{c.(int64)*d.(int64)}])
+(IsInBounds (Const [c]) (Const [d])) -> (Const [inBounds(c.(int64),d.(int64))])
+
+// tear apart slices
+// TODO: anything that generates a slice needs to go in here.
+(SlicePtr (Load ptr mem)) -> (Load ptr mem)
+(SliceLen (Load ptr mem)) -> (Load (Add <ptr.Type> ptr (Const <v.Block.Func.Config.Uintptr> [int64(v.Block.Func.Config.ptrSize)])) mem)
+(SliceCap (Load ptr mem)) -> (Load (Add <ptr.Type> ptr (Const <v.Block.Func.Config.Uintptr> [int64(v.Block.Func.Config.ptrSize*2)])) mem)
+
+// indexing operations
+// Note: bounds check has already been done
+(ArrayIndex (Load ptr mem) idx) -> (Load (PtrIndex <ptr.Type.Elem().Elem().PtrTo()> ptr idx) mem)
+(PtrIndex <t> ptr idx) -> (Add ptr (Mul <v.Block.Func.Config.Uintptr> idx (Const <v.Block.Func.Config.Uintptr> [t.Elem().Size()])))
+// TODO: hopefully this will get rid of all full-width array copies.
+
+// big-object moves
+// TODO: fix size
+(Store dst (Load <t> src mem) mem) && t.Size() > 8 -> (Move [t.Size()] dst src mem)
diff --git a/src/cmd/compile/internal/ssa/rulegen/lower_amd64.rules b/src/cmd/compile/internal/ssa/rulegen/lower_amd64.rules
new file mode 100644
index 0000000000..dc910b70b1
--- /dev/null
+++ b/src/cmd/compile/internal/ssa/rulegen/lower_amd64.rules
@@ -0,0 +1,91 @@
+// 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.
+
+// values are specified using the following format:
+// (op <type> [aux] arg0 arg1 ...)
+// the type and aux fields are optional
+// on the matching side
+//  - the types and aux fields must match if they are specified.
+// on the generated side
+//  - the type of the top-level expression is the same as the one on the left-hand side.
+//  - the type of any subexpressions must be specified explicitly.
+//  - aux will be nil if not specified.
+
+// x86 register conventions:
+//  - Integer types live in the low portion of registers.
+//    Upper portions are correctly extended.
+//  - Boolean types use the low-order byte of a register.  Upper bytes are junk.
+//  - We do not use AH,BH,CH,DH registers.
+//  - Floating-point types will live in the low natural slot of an sse2 register.
+//    Unused portions are junk.
+
+// These are the lowerings themselves
+(Add <t> x y) && (is64BitInt(t) || isPtr(t)) -> (ADDQ x y)
+(Add <t> x y) && is32BitInt(t) -> (ADDL x y)
+
+(Sub <t> x y) && is64BitInt(t) -> (SUBQ x y)
+
+(Mul <t> x y) && is64BitInt(t) -> (MULQ x y)
+(Lsh <t> x y) && is64BitInt(t) -> (SHLQ x y) // TODO: check y>63
+(Less x y) && is64BitInt(v.Args[0].Type) && isSigned(v.Args[0].Type) -> (SETL (CMPQ <TypeFlags> x y))
+
+(Load <t> ptr mem) && t.IsBoolean() -> (MOVBload [int64(0)] ptr mem)
+(Load <t> ptr mem) && (is64BitInt(t) || isPtr(t)) -> (MOVQload [int64(0)] ptr mem)
+(Store ptr val mem) && (is64BitInt(val.Type) || isPtr(val.Type)) -> (MOVQstore [int64(0)] ptr val mem)
+
+// checks
+(IsNonNil p) -> (SETNE (TESTQ <TypeFlags> p p))
+(IsInBounds idx len) -> (SETB (CMPQ <TypeFlags> idx len))
+
+(Move [size] dst src mem) -> (REPMOVSB dst src (Const <TypeUInt64> [size.(int64)]) mem)
+
+(OffPtr [off] ptr) -> (ADDQconst [off] ptr)
+
+(Const <t> [val]) && is64BitInt(t) -> (MOVQconst [val])
+
+// Rules below here apply some simple optimizations after lowering.
+// TODO: Should this be a separate pass?
+
+// global loads/stores
+(Global [sym]) -> (LEAQglobal [GlobalOffset{sym,0}])
+
+// fold constants into instructions
+(ADDQ x (MOVQconst [c])) -> (ADDQconst [c] x) // TODO: restrict c to int32 range?
+(ADDQ (MOVQconst [c]) x) -> (ADDQconst [c] x)
+(SUBQ x (MOVQconst [c])) -> (SUBQconst x [c])
+(SUBQ <t> (MOVQconst [c]) x) -> (NEGQ (SUBQconst <t> x [c]))
+(MULQ x (MOVQconst [c])) && c.(int64) == int64(int32(c.(int64))) -> (MULQconst [c] x)
+(MULQ (MOVQconst [c]) x) -> (MULQconst [c] x)
+(SHLQ x (MOVQconst [c])) -> (SHLQconst [c] x)
+(CMPQ x (MOVQconst [c])) -> (CMPQconst x [c])
+(CMPQ (MOVQconst [c]) x) -> (InvertFlags (CMPQconst <TypeFlags> x [c]))
+
+// strength reduction
+// TODO: do this a lot more generically
+(MULQconst [c] x) && c.(int64) == 8 -> (SHLQconst [int64(3)] x)
+(MULQconst [c] x) && c.(int64) == 64 -> (SHLQconst [int64(5)] x)
+
+// fold add/shift into leaq
+(ADDQ x (SHLQconst [shift] y)) && shift.(int64) == 3 -> (LEAQ8 [int64(0)] x y)
+(ADDQconst [c] (LEAQ8 [d] x y)) -> (LEAQ8 [addOff(c, d)] x y)
+
+// reverse ordering of compare instruction
+(SETL (InvertFlags x)) -> (SETGE x)
+
+// fold constants into memory operations
+// Note that this is not always a good idea because if not all the uses of
+// the ADDQconst get eliminated, we still have to compute the ADDQconst and we now
+// have potentially two live values (ptr and (ADDQconst [off] ptr)) instead of one.
+// Nevertheless, let's do it!
+(MOVQload [off1] (ADDQconst [off2] ptr) mem) -> (MOVQload [addOff(off1, off2)] ptr mem)
+(MOVQstore [off1] (ADDQconst [off2] ptr) val mem) -> (MOVQstore [addOff(off1, off2)] ptr val mem)
+
+// indexed loads and stores
+(MOVQload [off1] (LEAQ8 [off2] ptr idx) mem) -> (MOVQloadidx8 [addOff(off1, off2)] ptr idx mem)
+(MOVQstore [off1] (LEAQ8 [off2] ptr idx) val mem) -> (MOVQstoreidx8 [addOff(off1, off2)] ptr idx val mem)
+
+(MOVQloadidx8 [off1] (ADDQconst [off2] ptr) idx mem) -> (MOVQloadidx8 [addOff(off1, off2)] ptr idx mem)
+(MOVQstoreidx8 [off1] (ADDQconst [off2] ptr) idx val mem) -> (MOVQstoreidx8 [addOff(off1, off2)] ptr idx val mem)
+
+(ADDQconst [off] x) && off.(int64) == 0 -> (Copy x)
diff --git a/src/cmd/compile/internal/ssa/rulegen/rulegen.go b/src/cmd/compile/internal/ssa/rulegen/rulegen.go
new file mode 100644
index 0000000000..4ac930298b
--- /dev/null
+++ b/src/cmd/compile/internal/ssa/rulegen/rulegen.go
@@ -0,0 +1,346 @@
+// 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 program generates Go code that applies rewrite rules to a Value.
+// The generated code implements a function of type func (v *Value) bool
+// which returns true iff if did something.
+// Ideas stolen from Swift: http://www.hpl.hp.com/techreports/Compaq-DEC/WRL-2000-2.html
+
+// Run with something like "go run rulegen.go lower_amd64.rules lowerAmd64 lowerAmd64.go"
+
+package main
+
+import (
+	"bufio"
+	"bytes"
+	"crypto/md5"
+	"fmt"
+	"go/format"
+	"io"
+	"io/ioutil"
+	"log"
+	"os"
+	"sort"
+	"strings"
+)
+
+// rule syntax:
+//  sexpr [&& extra conditions] -> sexpr
+//
+// sexpr are s-expressions (lisp-like parenthesized groupings)
+// sexpr ::= (opcode sexpr*)
+//         | variable
+//         | [aux]
+//         | <type>
+//         | {code}
+//
+// aux      ::= variable | {code}
+// type     ::= variable | {code}
+// variable ::= some token
+// opcode   ::= one of the opcodes from ../op.go (without the Op prefix)
+
+// extra conditions is just a chunk of Go that evaluates to a boolean.  It may use
+// variables declared in the matching sexpr.  The variable "v" is predefined to be
+// the value matched by the entire rule.
+
+// If multiple rules match, the first one in file order is selected.
+
+func main() {
+	if len(os.Args) < 3 || len(os.Args) > 4 {
+		fmt.Printf("usage: go run rulegen.go <rule file> <function name> [<output file>]")
+		os.Exit(1)
+	}
+	rulefile := os.Args[1]
+	rulefn := os.Args[2]
+
+	// Open input file.
+	text, err := os.Open(rulefile)
+	if err != nil {
+		log.Fatalf("can't read rule file: %v", err)
+	}
+
+	// oprules contains a list of rules for each opcode
+	oprules := map[string][]string{}
+
+	// read rule file
+	scanner := bufio.NewScanner(text)
+	for scanner.Scan() {
+		line := scanner.Text()
+		if i := strings.Index(line, "//"); i >= 0 {
+			// Remove comments.  Note that this isn't string safe, so
+			// it will truncate lines with // inside strings.  Oh well.
+			line = line[:i]
+		}
+		line = strings.TrimSpace(line)
+		if line == "" {
+			continue
+		}
+		op := strings.Split(line, " ")[0][1:]
+		oprules[op] = append(oprules[op], line)
+	}
+	if err := scanner.Err(); err != nil {
+		log.Fatalf("scanner failed: %v\n", err)
+	}
+
+	// Start output buffer, write header.
+	w := new(bytes.Buffer)
+	fmt.Fprintf(w, "// autogenerated from %s: do not edit!\n", rulefile)
+	fmt.Fprintf(w, "// generated with: go run rulegen/rulegen.go %s\n", strings.Join(os.Args[1:], " "))
+	fmt.Fprintln(w, "package ssa")
+	fmt.Fprintf(w, "func %s(v *Value) bool {\n", rulefn)
+
+	// generate code for each rule
+	fmt.Fprintf(w, "switch v.Op {\n")
+	var ops []string
+	for op := range oprules {
+		ops = append(ops, op)
+	}
+	sort.Strings(ops)
+	for _, op := range ops {
+		fmt.Fprintf(w, "case Op%s:\n", op)
+		for _, rule := range oprules[op] {
+			// Note: we use a hash to identify the rule so that its
+			// identity is invariant to adding/removing rules elsewhere
+			// in the rules file.  This is useful to squash spurious
+			// diffs that would occur if we used rule index.
+			rulehash := fmt.Sprintf("%02x", md5.Sum([]byte(rule)))
+
+			// split at ->
+			s := strings.Split(rule, "->")
+			if len(s) != 2 {
+				log.Fatalf("no arrow in rule %s", rule)
+			}
+			lhs := strings.Trim(s[0], " \t")
+			result := strings.Trim(s[1], " \t\n")
+
+			// split match into matching part and additional condition
+			match := lhs
+			cond := ""
+			if i := strings.Index(match, "&&"); i >= 0 {
+				cond = strings.Trim(match[i+2:], " \t")
+				match = strings.Trim(match[:i], " \t")
+			}
+
+			fmt.Fprintf(w, "// match: %s\n", match)
+			fmt.Fprintf(w, "// cond: %s\n", cond)
+			fmt.Fprintf(w, "// result: %s\n", result)
+
+			fail := fmt.Sprintf("{\ngoto end%s\n}\n", rulehash)
+
+			fmt.Fprintf(w, "{\n")
+			genMatch(w, match, fail)
+
+			if cond != "" {
+				fmt.Fprintf(w, "if !(%s) %s", cond, fail)
+			}
+
+			genResult(w, result)
+			fmt.Fprintf(w, "return true\n")
+
+			fmt.Fprintf(w, "}\n")
+			fmt.Fprintf(w, "goto end%s\n", rulehash) // use label
+			fmt.Fprintf(w, "end%s:;\n", rulehash)
+		}
+	}
+	fmt.Fprintf(w, "}\n")
+	fmt.Fprintf(w, "return false\n")
+	fmt.Fprintf(w, "}\n")
+
+	// gofmt result
+	b := w.Bytes()
+	b, err = format.Source(b)
+	if err != nil {
+		panic(err)
+	}
+
+	// Write to a file if given, otherwise stdout.
+	if len(os.Args) >= 4 {
+		err = ioutil.WriteFile(os.Args[3], b, 0666)
+	} else {
+		_, err = os.Stdout.Write(b)
+	}
+	if err != nil {
+		log.Fatalf("can't write output: %v\n", err)
+	}
+}
+
+func genMatch(w io.Writer, match, fail string) {
+	genMatch0(w, match, "v", fail, map[string]string{}, true)
+}
+
+func genMatch0(w io.Writer, match, v, fail string, m map[string]string, top bool) {
+	if match[0] != '(' {
+		if x, ok := m[match]; ok {
+			// variable already has a definition.  Check whether
+			// the old definition and the new definition match.
+			// For example, (add x x).  Equality is just pointer equality
+			// on Values (so cse is important to do before lowering).
+			fmt.Fprintf(w, "if %s != %s %s", v, x, fail)
+			return
+		}
+		// remember that this variable references the given value
+		m[match] = v
+		fmt.Fprintf(w, "%s := %s\n", match, v)
+		return
+	}
+
+	// split body up into regions.  Split by spaces/tabs, except those
+	// contained in () or {}.
+	s := split(match[1 : len(match)-1])
+
+	// check op
+	if !top {
+		fmt.Fprintf(w, "if %s.Op != Op%s %s", v, s[0], fail)
+	}
+
+	// check type/aux/args
+	argnum := 0
+	for _, a := range s[1:] {
+		if a[0] == '<' {
+			// type restriction
+			t := a[1 : len(a)-1]
+			if t[0] == '{' {
+				// code.  We must match the results of this code.
+				fmt.Fprintf(w, "if %s.Type != %s %s", v, t[1:len(t)-1], fail)
+			} else {
+				// variable
+				if u, ok := m[t]; ok {
+					// must match previous variable
+					fmt.Fprintf(w, "if %s.Type != %s %s", v, u, fail)
+				} else {
+					m[t] = v + ".Type"
+					fmt.Fprintf(w, "%s := %s.Type\n", t, v)
+				}
+			}
+		} else if a[0] == '[' {
+			// aux restriction
+			x := a[1 : len(a)-1]
+			if x[0] == '{' {
+				// code
+				fmt.Fprintf(w, "if %s.Aux != %s %s", v, x[1:len(x)-1], fail)
+			} else {
+				// variable
+				if y, ok := m[x]; ok {
+					fmt.Fprintf(w, "if %s.Aux != %s %s", v, y, fail)
+				} else {
+					m[x] = v + ".Aux"
+					fmt.Fprintf(w, "%s := %s.Aux\n", x, v)
+				}
+			}
+		} else if a[0] == '{' {
+			fmt.Fprintf(w, "if %s.Args[%d] != %s %s", v, argnum, a[1:len(a)-1], fail)
+			argnum++
+		} else {
+			// variable or sexpr
+			genMatch0(w, a, fmt.Sprintf("%s.Args[%d]", v, argnum), fail, m, false)
+			argnum++
+		}
+	}
+}
+
+func genResult(w io.Writer, result string) {
+	genResult0(w, result, new(int), true)
+}
+func genResult0(w io.Writer, result string, alloc *int, top bool) string {
+	if result[0] != '(' {
+		// variable
+		if top {
+			fmt.Fprintf(w, "v.Op = %s.Op\n", result)
+			fmt.Fprintf(w, "v.Aux = %s.Aux\n", result)
+			fmt.Fprintf(w, "v.resetArgs()\n")
+			fmt.Fprintf(w, "v.AddArgs(%s.Args...)\n", result)
+		}
+		return result
+	}
+
+	s := split(result[1 : len(result)-1])
+	var v string
+	var hasType bool
+	if top {
+		v = "v"
+		fmt.Fprintf(w, "v.Op = Op%s\n", s[0])
+		fmt.Fprintf(w, "v.Aux = nil\n")
+		fmt.Fprintf(w, "v.resetArgs()\n")
+		hasType = true
+	} else {
+		v = fmt.Sprintf("v%d", *alloc)
+		*alloc++
+		fmt.Fprintf(w, "%s := v.Block.NewValue(Op%s, TypeInvalid, nil)\n", v, s[0])
+	}
+	for _, a := range s[1:] {
+		if a[0] == '<' {
+			// type restriction
+			t := a[1 : len(a)-1]
+			if t[0] == '{' {
+				t = t[1 : len(t)-1]
+			}
+			fmt.Fprintf(w, "%s.Type = %s\n", v, t)
+			hasType = true
+		} else if a[0] == '[' {
+			// aux restriction
+			x := a[1 : len(a)-1]
+			if x[0] == '{' {
+				x = x[1 : len(x)-1]
+			}
+			fmt.Fprintf(w, "%s.Aux = %s\n", v, x)
+		} else if a[0] == '{' {
+			fmt.Fprintf(w, "%s.AddArg(%s)\n", v, a[1:len(a)-1])
+		} else {
+			// regular argument (sexpr or variable)
+			x := genResult0(w, a, alloc, false)
+			fmt.Fprintf(w, "%s.AddArg(%s)\n", v, x)
+		}
+	}
+	if !hasType {
+		log.Fatalf("sub-expression %s must have a type", result)
+	}
+	return v
+}
+
+func split(s string) []string {
+	var r []string
+
+outer:
+	for s != "" {
+		d := 0               // depth of ({[<
+		var open, close byte // opening and closing markers ({[< or )}]>
+		nonsp := false       // found a non-space char so far
+		for i := 0; i < len(s); i++ {
+			switch {
+			case d == 0 && s[i] == '(':
+				open, close = '(', ')'
+				d++
+			case d == 0 && s[i] == '<':
+				open, close = '<', '>'
+				d++
+			case d == 0 && s[i] == '[':
+				open, close = '[', ']'
+				d++
+			case d == 0 && s[i] == '{':
+				open, close = '{', '}'
+				d++
+			case d == 0 && (s[i] == ' ' || s[i] == '\t'):
+				if nonsp {
+					r = append(r, strings.TrimSpace(s[:i]))
+					s = s[i:]
+					continue outer
+				}
+			case d > 0 && s[i] == open:
+				d++
+			case d > 0 && s[i] == close:
+				d--
+			default:
+				nonsp = true
+			}
+		}
+		if d != 0 {
+			panic("imbalanced expression: " + s)
+		}
+		if nonsp {
+			r = append(r, strings.TrimSpace(s))
+		}
+		break
+	}
+	return r
+}
diff --git a/src/cmd/compile/internal/ssa/schedule.go b/src/cmd/compile/internal/ssa/schedule.go
new file mode 100644
index 0000000000..0a89ac3773
--- /dev/null
+++ b/src/cmd/compile/internal/ssa/schedule.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 ssa
+
+// Schedule the Values in each Block.  After this phase returns, the
+// order of b.Values matters and is the order in which those values
+// will appear in the assembly output.  For now it generates an
+// arbitrary valid schedule using a topological sort.  TODO(khr):
+// schedule smarter.
+func schedule(f *Func) {
+	const (
+		unmarked = 0
+		found    = 1
+		expanded = 2
+		done     = 3
+	)
+	state := make([]byte, f.NumValues())
+	var queue []*Value //stack-like worklist.  Contains found and expanded nodes.
+	var order []*Value
+
+	for _, b := range f.Blocks {
+		// Topologically sort the values in b.
+		order = order[:0]
+		for _, v := range b.Values {
+			if v.Op == OpPhi {
+				// Phis all go first.  We handle phis specially
+				// because they may have self edges "a = phi(a, b, c)"
+				order = append(order, v)
+				continue
+			}
+			if state[v.ID] != unmarked {
+				if state[v.ID] != done {
+					panic("bad state")
+				}
+				continue
+			}
+			state[v.ID] = found
+			queue = append(queue, v)
+			for len(queue) > 0 {
+				v = queue[len(queue)-1]
+				switch state[v.ID] {
+				case found:
+					state[v.ID] = expanded
+					// Note that v is not popped.  We leave it in place
+					// until all its children have been explored.
+					for _, w := range v.Args {
+						if w.Block == b && w.Op != OpPhi && state[w.ID] == unmarked {
+							state[w.ID] = found
+							queue = append(queue, w)
+						}
+					}
+				case expanded:
+					queue = queue[:len(queue)-1]
+					state[v.ID] = done
+					order = append(order, v)
+				default:
+					panic("bad state")
+				}
+			}
+		}
+		copy(b.Values, order)
+	}
+	// TODO: only allow one live mem type and one live flags type (x86)
+	// This restriction will force any loads (and any flag uses) to appear
+	// before the next store (flag update).  This "anti-dependence" is not
+	// recorded explicitly in ssa form.
+}
diff --git a/src/cmd/compile/internal/ssa/sparseset.go b/src/cmd/compile/internal/ssa/sparseset.go
new file mode 100644
index 0000000000..b79aee8497
--- /dev/null
+++ b/src/cmd/compile/internal/ssa/sparseset.go
@@ -0,0 +1,75 @@
+// 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 := s.sparse[x]
+	if i < len(s.dense) && s.dense[i] == x {
+		return
+	}
+	s.dense = append(s.dense, x)
+	s.sparse[x] = len(s.dense) - 1
+}
+
+func (s *sparseSet) addAll(a []ID) {
+	for _, x := range a {
+		s.add(x)
+	}
+}
+
+func (s *sparseSet) addAllValues(a []*Value) {
+	for _, v := range a {
+		s.add(v.ID)
+	}
+}
+
+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/compile/internal/ssa/stackalloc.go b/src/cmd/compile/internal/ssa/stackalloc.go
new file mode 100644
index 0000000000..ab686470be
--- /dev/null
+++ b/src/cmd/compile/internal/ssa/stackalloc.go
@@ -0,0 +1,111 @@
+package ssa
+
+import "log"
+
+// stackalloc allocates storage in the stack frame for
+// all Values that did not get a register.
+func stackalloc(f *Func) {
+	home := f.RegAlloc
+
+	// First compute the size of the outargs section.
+	n := int64(16) //TODO: compute max of all callsites
+
+	// Include one slot for deferreturn.
+	if false && n < f.Config.ptrSize { //TODO: check for deferreturn
+		n = f.Config.ptrSize
+	}
+
+	// TODO: group variables by ptr/nonptr, size, etc.  Emit ptr vars last
+	// so stackmap is smaller.
+
+	// Assign stack locations to phis first, because we
+	// must also assign the same locations to the phi copies
+	// introduced during regalloc.
+	for _, b := range f.Blocks {
+		for _, v := range b.Values {
+			if v.Op != OpPhi {
+				continue
+			}
+			if v.Type.IsMemory() { // TODO: only "regallocable" types
+				continue
+			}
+			n += v.Type.Size()
+			// a := v.Type.Align()
+			// n = (n + a - 1) / a * a  TODO
+			loc := &LocalSlot{n}
+			home = setloc(home, v, loc)
+			for _, w := range v.Args {
+				home = setloc(home, w, loc)
+			}
+		}
+	}
+
+	// Now do all other unassigned values.
+	for _, b := range f.Blocks {
+		for _, v := range b.Values {
+			if v.ID < ID(len(home)) && home[v.ID] != nil {
+				continue
+			}
+			if v.Type.IsMemory() { // TODO: only "regallocable" types
+				continue
+			}
+			if len(v.Args) == 0 {
+				// v will have been materialized wherever it is needed.
+				continue
+			}
+			if len(v.Args) == 1 && (v.Args[0].Op == OpFP || v.Args[0].Op == OpSP || v.Args[0].Op == OpGlobal) {
+				continue
+			}
+			// a := v.Type.Align()
+			// n = (n + a - 1) / a * a  TODO
+			n += v.Type.Size()
+			loc := &LocalSlot{n}
+			home = setloc(home, v, loc)
+		}
+	}
+
+	// TODO: align n
+	n += f.Config.ptrSize // space for return address.  TODO: arch-dependent
+	f.RegAlloc = home
+	f.FrameSize = n
+
+	// TODO: share stack slots among noninterfering (& gc type compatible) values
+
+	// adjust all uses of FP to SP now that we have the frame size.
+	var fp *Value
+	for _, b := range f.Blocks {
+		for _, v := range b.Values {
+			if v.Op == OpFP {
+				if fp != nil {
+					log.Panicf("multiple FP ops: %s %s", fp, v)
+				}
+				fp = v
+			}
+			for i, a := range v.Args {
+				if a.Op != OpFP {
+					continue
+				}
+				// TODO: do this with arch-specific rewrite rules somehow?
+				switch v.Op {
+				case OpADDQ:
+					// (ADDQ (FP) x) -> (LEAQ [n] (SP) x)
+					v.Op = OpLEAQ
+					v.Aux = n
+				case OpLEAQ, OpMOVQload, OpMOVQstore, OpMOVBload, OpMOVQloadidx8:
+					if v.Op == OpMOVQloadidx8 && i == 1 {
+						// Note: we could do it, but it is probably an error
+						log.Panicf("can't do FP->SP adjust on index slot of load %s", v.Op)
+					}
+					// eg: (MOVQload [c] (FP) mem) -> (MOVQload [c+n] (SP) mem)
+					v.Aux = addOffset(v.Aux.(int64), n)
+				default:
+					log.Panicf("can't do FP->SP adjust on %s", v.Op)
+				}
+			}
+		}
+	}
+	if fp != nil {
+		fp.Op = OpSP
+		home[fp.ID] = &registers[4] // TODO: arch-dependent
+	}
+}
diff --git a/src/cmd/compile/internal/ssa/type.go b/src/cmd/compile/internal/ssa/type.go
new file mode 100644
index 0000000000..611c85834a
--- /dev/null
+++ b/src/cmd/compile/internal/ssa/type.go
@@ -0,0 +1,74 @@
+// 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
+
+// TODO: use go/types instead?
+
+// A type interface used to import cmd/internal/gc:Type
+// Type instances are not guaranteed to be canonical.
+type Type interface {
+	Size() int64 // return the size in bytes
+
+	IsBoolean() bool // is a named or unnamed boolean type
+	IsInteger() bool //  ... ditto for the others
+	IsSigned() bool
+	IsFloat() bool
+	IsPtr() bool
+
+	IsMemory() bool // special ssa-package-only types
+	IsFlags() bool
+
+	Elem() Type  // given []T or *T, return T
+	PtrTo() Type // given T, return *T
+
+	String() string
+}
+
+// Stub implementation for now, until we are completely using ../gc:Type
+type TypeImpl struct {
+	Size_   int64
+	Boolean bool
+	Integer bool
+	Signed  bool
+	Float   bool
+	Ptr     bool
+
+	Memory bool
+	Flags  bool
+
+	Name string
+}
+
+func (t *TypeImpl) Size() int64     { return t.Size_ }
+func (t *TypeImpl) IsBoolean() bool { return t.Boolean }
+func (t *TypeImpl) IsInteger() bool { return t.Integer }
+func (t *TypeImpl) IsSigned() bool  { return t.Signed }
+func (t *TypeImpl) IsFloat() bool   { return t.Float }
+func (t *TypeImpl) IsPtr() bool     { return t.Ptr }
+func (t *TypeImpl) IsMemory() bool  { return t.Memory }
+func (t *TypeImpl) IsFlags() bool   { return t.Flags }
+func (t *TypeImpl) String() string  { return t.Name }
+func (t *TypeImpl) Elem() Type      { panic("not implemented"); return nil }
+func (t *TypeImpl) PtrTo() Type     { panic("not implemented"); return nil }
+
+var (
+	// shortcuts for commonly used basic types
+	TypeInt8   = &TypeImpl{Size_: 1, Integer: true, Signed: true, Name: "int8"}
+	TypeInt16  = &TypeImpl{Size_: 2, Integer: true, Signed: true, Name: "int16"}
+	TypeInt32  = &TypeImpl{Size_: 4, Integer: true, Signed: true, Name: "int32"}
+	TypeInt64  = &TypeImpl{Size_: 8, Integer: true, Signed: true, Name: "int64"}
+	TypeUInt8  = &TypeImpl{Size_: 1, Integer: true, Name: "uint8"}
+	TypeUInt16 = &TypeImpl{Size_: 2, Integer: true, Name: "uint16"}
+	TypeUInt32 = &TypeImpl{Size_: 4, Integer: true, Name: "uint32"}
+	TypeUInt64 = &TypeImpl{Size_: 8, Integer: true, Name: "uint64"}
+	TypeBool   = &TypeImpl{Size_: 1, Boolean: true, Name: "bool"}
+	//TypeString = types.Typ[types.String]
+
+	TypeInvalid = &TypeImpl{Name: "invalid"}
+
+	// Additional compiler-only types go here.
+	TypeMem   = &TypeImpl{Memory: true, Name: "mem"}
+	TypeFlags = &TypeImpl{Flags: true, Name: "flags"}
+)
diff --git a/src/cmd/compile/internal/ssa/value.go b/src/cmd/compile/internal/ssa/value.go
new file mode 100644
index 0000000000..dab6239dee
--- /dev/null
+++ b/src/cmd/compile/internal/ssa/value.go
@@ -0,0 +1,103 @@
+// 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 and 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
+//  OpConst     string      0    string constant
+//  OpConst      int64      0    int64 constant
+//  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) {
+	if v.Args == nil {
+		v.resetArgs() // use argstorage
+	}
+	v.Args = append(v.Args, w)
+}
+func (v *Value) AddArgs(a ...*Value) {
+	if v.Args == nil {
+		v.resetArgs() // use argstorage
+	}
+	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[len(v.Args)-1] = nil // aid GC
+	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]
+}