[dev.ssa] cmd/internal/ssa: delete ssac
We don't need this standalone tool any more. We can now feed the
ssa compiler directly from the Go frontend.
Change-Id: I922f1e061c2d3db6bf77acc137d4d1fc7dc86c0d
Reviewed-on: https://go-review.googlesource.com/10034
Reviewed-by: Alan Donovan <adonovan@google.com>
diff --git a/src/cmd/internal/ssa/ssac/.gitignore b/src/cmd/internal/ssa/ssac/.gitignore
deleted file mode 100644
index ab17b9d..0000000
--- a/src/cmd/internal/ssa/ssac/.gitignore
+++ /dev/null
@@ -1 +0,0 @@
-ssac
diff --git a/src/cmd/internal/ssa/ssac/fib.goir b/src/cmd/internal/ssa/ssac/fib.goir
deleted file mode 100644
index 0875d63..0000000
--- a/src/cmd/internal/ssa/ssac/fib.goir
+++ /dev/null
@@ -1,47 +0,0 @@
- (TYPE T127bd68 int)
- (TYPE T127bd68 int)
- (TYPE T127bd68 int)
- (TYPE T127bd68 int)
- (TYPE T7faedc523360 (FUNC (int) (int)))
- (TYPE T127bd68 int)
- (TYPE T127bd68 int)
- (TYPE T7faedc523360 (FUNC (int) (int)))
- (TYPE T127bd68 int)
- (TYPE T127bd68 int)
- (TYPE T127bd68 int)
- (TYPE T127bd68 int)
- (TYPE T127bd68 int)
- (TYPE T127bd68 int)
- (DCL n T127bd68)
- (AS n (LOAD (FP T127bd68 0)))
- (DCL ~r1 T127bd68)
- (DCL n T127bd68)
- (DCL autotmp_0000 T127bd68)
- (DCL fib T7faedc523360)
- (DCL n T127bd68)
- (DCL autotmp_0001 T127bd68)
- (DCL fib T7faedc523360)
- (DCL n T127bd68)
- (DCL ~r1 T127bd68)
- (DCL autotmp_0000 T127bd68)
- (DCL autotmp_0001 T127bd68)
- (DCL autotmp_0001 T127bd68)
- (DCL autotmp_0000 T127bd68)
- (IF (LT n (CINT 2)) .then0 .else0)
- (LABEL .then0)
- (AS ~r1 n)
- (AS (FP T127bd68 8) ~r1)
- (RETURN)
- (GOTO .end0)
- (LABEL .else0)
- (GOTO .end0)
- (LABEL .end0)
- (AS (SP T127bd68 0) (SUB n (CINT 1)))
- (CALL fib)
- (AS autotmp_0000 (LOAD (SP T127bd68 8)))
- (AS (SP T127bd68 0) (SUB n (CINT 2)))
- (CALL fib)
- (AS autotmp_0001 (LOAD (SP T127bd68 8)))
- (AS ~r1 (ADD autotmp_0000 autotmp_0001))
- (AS (FP T127bd68 8) ~r1)
- (RETURN)
diff --git a/src/cmd/internal/ssa/ssac/fibiter.goir b/src/cmd/internal/ssa/ssac/fibiter.goir
deleted file mode 100644
index 98b2b2b..0000000
--- a/src/cmd/internal/ssa/ssac/fibiter.goir
+++ /dev/null
@@ -1,62 +0,0 @@
- (NAME runtime·fibiter)
- (TYPE Tf5dd68 int)
- (TYPE Tf5dd68 int)
- (TYPE Tf5dd68 int)
- (TYPE Tf5dd68 int)
- (TYPE Tf5dd68 int)
- (TYPE Tf5dd68 int)
- (TYPE Tf5dd68 int)
- (TYPE Tf5dd68 int)
- (TYPE Tf5dd68 int)
- (TYPE Tf5dd68 int)
- (TYPE Tf5dd68 int)
- (TYPE Tf5dd68 int)
- (TYPE Tf5dd68 int)
- (TYPE Tf5dd68 int)
- (TYPE Tf5dd68 int)
- (TYPE Tf5dd68 int)
- (TYPE Tf5dd68 int)
- (TYPE Tf5dd68 int)
- (TYPE Tf5dd68 int)
- (TYPE Tf5dd68 int)
- (TYPE Tf5dd68 int)
- (TYPE Tf5dd68 int)
- (DCL a Tf5dd68)
- (DCL a Tf5dd68)
- (DCL b Tf5dd68)
- (DCL b Tf5dd68)
- (DCL i Tf5dd68)
- (DCL i Tf5dd68)
- (DCL i Tf5dd68)
- (DCL n Tf5dd68)
- (DCL autotmp_0002 Tf5dd68)
- (DCL i Tf5dd68)
- (DCL i Tf5dd68)
- (DCL autotmp_0002 Tf5dd68)
- (DCL autotmp_0002 Tf5dd68)
- (DCL autotmp_0003 Tf5dd68)
- (DCL a Tf5dd68)
- (DCL b Tf5dd68)
- (DCL a Tf5dd68)
- (DCL b Tf5dd68)
- (DCL b Tf5dd68)
- (DCL autotmp_0003 Tf5dd68)
- (DCL ~r1 Tf5dd68)
- (DCL a Tf5dd68)
- (AS n (LOAD (FP Tf5dd68 0)))
- (AS a (CINT 0))
- (AS b (CINT 1))
- (AS i (CINT 0))
- (GOTO .top0)
- (LABEL .top0)
- (IF (LT i n) .body0 .end0)
- (LABEL .body0)
- (AS autotmp_0003 (ADD a b))
- (AS a b)
- (AS b autotmp_0003)
- (AS autotmp_0002 i)
- (AS i (ADD autotmp_0002 (CINT 1)))
- (GOTO .top0)
- (LABEL .end0)
- (AS (FP Tf5dd68 8) a)
- (RETURN)
diff --git a/src/cmd/internal/ssa/ssac/main.go b/src/cmd/internal/ssa/ssac/main.go
deleted file mode 100644
index 2afa7c6..0000000
--- a/src/cmd/internal/ssa/ssac/main.go
+++ /dev/null
@@ -1,439 +0,0 @@
-// Copyright 2015 The Go Authors. All rights reserved.
-// Use of this source code is governed by a BSD-style
-// license that can be found in the LICENSE file.
-
-package main
-
-// Stub package for testing ssa compiler backend. Will eventually
-// be deleted when ssa is called directly from the main compiler.
-
-import (
- "bufio"
- "flag"
- "fmt"
- "io"
- "os"
- "strconv"
- "strings"
-
- "cmd/internal/ssa"
-)
-
-// testing harness which runs the compiler using an IR read from a file
-func main() {
- flag.Parse()
- file := flag.Arg(0)
- r, err := os.Open(file)
- if err != nil {
- panic(err)
- }
- f := buildFunc(readFunc(r))
- ssa.Compile(f)
- // TODO: output f
-}
-
-// readFunc reads the intermediate representation generated by the
-// compiler frontend and returns it as a list of sexpressions.
-func readFunc(r io.Reader) []sexpr {
- var lines []sexpr
- s := bufio.NewScanner(r)
- for s.Scan() {
- line := s.Text()
- e := parseSexpr(strings.Trim(line, " "))
-
- if !e.compound {
- panic("bad stmt: " + line)
- }
- if e.parts[0].compound {
- panic("bad op: " + line)
- }
- lines = append(lines, e)
- }
- return lines
-}
-
-// buildFunc converts from the 6g IR dump format to the internal
-// form. Builds SSA and all that.
-func buildFunc(lines []sexpr) *ssa.Func {
- f := new(ssa.Func)
-
- // We construct SSA using an algorithm similar to
- // Brau, Buchwald, Hack, Leißa, Mallon, and Zwinkau
- // http://pp.info.uni-karlsruhe.de/uploads/publikationen/braun13cc.pdf
-
- // allocate starting block
- f.Entry = f.NewBlock(ssa.BlockPlain)
- // TODO: all args. Make a struct containing args/returnvals, declare
- // an FP which contains a pointer to that struct.
-
- var exit *ssa.Block // all returns (if any) branch to here TODO: defers & panics?
-
- // add a block for each label
- // Also a few other preprocessing steps, all in one pass.
- labels := map[string]*ssa.Block{}
- types := map[string]ssa.Type{}
- callFallthrough := map[int]*ssa.Block{}
- for i, e := range lines {
- switch e.parts[0].name {
- case "LABEL":
- labels[e.parts[1].name] = f.NewBlock(ssa.BlockPlain)
- case "NAME":
- f.Name = e.parts[1].name
- case "RETURN":
- if exit == nil {
- exit = f.NewBlock(ssa.BlockExit)
- }
- case "TYPE":
- types[e.parts[1].name] = parseSexprType(e.parts[2])
- case "CALL":
- // allocate a new block for fallthrough
- callFallthrough[i] = f.NewBlock(ssa.BlockPlain)
- if exit == nil {
- exit = f.NewBlock(ssa.BlockExit)
- }
- }
- }
-
- // map from block id to sexprs in that block
- blocklines := make([][]sexpr, f.NumBlocks())
-
- // Add sexprs to the correct block. Add edges between blocks.
- b := f.Entry
- var i int
- for j, e := range lines {
- if b == nil && e.parts[0].name != "LABEL" {
- // dead code (e.g. return in "if" branch makes the "goto end" statement dead)
- continue
- }
- switch e.parts[0].name {
- case "IF":
- if b.Kind != ssa.BlockPlain {
- panic("bad b state")
- }
- b.Kind = ssa.BlockIf
- edge(b, labels[e.parts[2].name])
- edge(b, labels[e.parts[3].name])
- blocklines[b.ID] = lines[i : j+1]
- b = nil
- case "GOTO":
- edge(b, labels[e.parts[1].name])
- blocklines[b.ID] = lines[i:j]
- b = nil
- case "LABEL":
- b = labels[e.parts[1].name]
- i = j + 1
- case "RETURN":
- if b.Kind != ssa.BlockPlain {
- panic("bad b state")
- }
- edge(b, exit)
- blocklines[b.ID] = lines[i:j]
- b = nil
- case "CALL":
- if b.Kind != ssa.BlockPlain {
- panic("bad b state")
- }
- b.Kind = ssa.BlockCall
- c := callFallthrough[j]
- edge(b, c)
- edge(b, exit)
- blocklines[b.ID] = lines[i : j+1]
- b = c
- i = j + 1
- }
- // note that we don't keep goto/label/return sexprs
- }
- if b != nil {
- panic("control flow falls off end of function")
- }
-
- // Read types for each variable
- // Number the variables densely
- varids := map[string]int{} // map from variable name to id
- var varnames []string // map from id to variable name
- var vartypes []ssa.Type // map from variable id to type
- for _, e := range lines {
- if e.parts[0].name != "DCL" {
- continue
- }
- name := e.parts[1].name
- if _, ok := varids[name]; ok {
- continue
- }
- id := len(varids)
- if id == 1<<31-1 {
- panic("too many variables")
- }
- fmt.Printf("var %d = %s\n", id, name)
- varids[name] = id
- varnames = append(varnames, name)
- vartypes = append(vartypes, types[e.parts[2].name])
- }
- memID := len(varids)
- fmt.Printf("var %d = .mem\n", memID)
- varids[".mem"] = memID // TODO: need .mem here?
- varnames = append(varnames, ".mem")
- vartypes = append(vartypes, ssa.TypeMem)
-
- // map from variable ID to current Value of that variable
- curBlock := NewSparseMap(len(varids))
-
- var state ssaFuncState
- state.types = types
- state.varids = varids
- state.varnames = varnames
- state.vartypes = vartypes
- state.curBlock = curBlock
- state.done = make([]bool, f.NumBlocks())
- state.defs = map[blockvar]*ssa.Value{}
- state.memID = memID
-
- // Convert each block to ssa
- // TODO: order blocks for maximum happiness - we want to process
- // all the predecessors of a block before processing the block itself,
- // if at all possible.
- for _, b := range f.Blocks {
- fmt.Printf("processing block %d\n", b.ID)
- curBlock.Clear()
- for _, e := range blocklines[b.ID] {
- switch e.parts[0].name {
- case "AS":
- if e.parts[1].compound {
- // store expression
- lhs := genExpr(&state, b, e.parts[1])
- rhs := genExpr(&state, b, e.parts[2])
- mem := genVar(&state, b, memID)
- v := b.NewValue(ssa.OpStore, ssa.TypeMem, nil)
- v.AddArg(lhs)
- v.AddArg(rhs)
- v.AddArg(mem)
- curBlock.Put(memID, v)
- } else {
- // variable assignment
- v := genExpr(&state, b, e.parts[2])
- curBlock.Put(varids[e.parts[1].name], v)
- }
- case "DCL":
- // nothing to do
- case "IF":
- b.Control = genExpr(&state, b, e.parts[1])
- case "CALL":
- // only direct call for now - indirect call takes addr value as well
- v := b.NewValue(ssa.OpStaticCall, ssa.TypeMem, e.parts[1].name)
- v.AddArg(genVar(&state, b, memID))
- curBlock.Put(memID, v)
- b.Control = v
- }
- }
- // link up forward references to their actual values
- for _, v := range b.Values {
- if v.Op != ssa.OpFwdRef {
- continue
- }
- varid := v.Aux.(int)
- w := genVar(&state, b, varid)
- v.Op = ssa.OpCopy
- v.Aux = nil
- v.AddArg(w)
- }
-
- // record final values at the end of the block
- for _, e := range curBlock.Contents() {
- state.defs[blockvar{b.ID, e.Key}] = e.Val
- // TODO: somehow avoid storing dead values to this map.
- }
- curBlock.Clear()
- state.done[b.ID] = true
- }
-
- // the final store value is returned
- if exit != nil {
- exit.Control = genVar(&state, exit, memID)
- }
-
- return f
-}
-
-func edge(a, b *ssa.Block) {
- a.Succs = append(a.Succs, b)
- b.Preds = append(b.Preds, a)
-}
-
-func genVar(state *ssaFuncState, b *ssa.Block, id int) *ssa.Value {
- // look up variable
- v := state.curBlock.Get(id)
- if v != nil {
- // variable was defined previously in this block
- // (or we memoized the result)
- return v
- }
-
- // Variable comes in from outside of basic block.
- v = lookupVarIncoming(state, b, id)
-
- // memoize result so future callers will not look it up again
- state.curBlock.Put(id, v)
- return v
-}
-
-func genExpr(state *ssaFuncState, b *ssa.Block, e sexpr) *ssa.Value {
- if !e.compound {
- return genVar(state, b, state.varids[e.name])
- }
- switch e.parts[0].name {
- case "ADD":
- x := genExpr(state, b, e.parts[1])
- y := genExpr(state, b, e.parts[2])
- v := b.NewValue(ssa.OpAdd, x.Type, nil)
- v.AddArg(x)
- v.AddArg(y)
- return v
- case "SUB":
- x := genExpr(state, b, e.parts[1])
- y := genExpr(state, b, e.parts[2])
- v := b.NewValue(ssa.OpSub, x.Type, nil)
- v.AddArg(x)
- v.AddArg(y)
- return v
- case "CINT":
- c, err := strconv.ParseInt(e.parts[1].name, 10, 64)
- if err != nil {
- panic("bad cint value")
- }
- return b.Func.ConstInt(ssa.TypeInt64, c)
- case "LT":
- x := genExpr(state, b, e.parts[1])
- y := genExpr(state, b, e.parts[2])
- v := b.NewValue(ssa.OpLess, ssa.TypeBool, nil)
- v.AddArg(x)
- v.AddArg(y)
- return v
- /*
- case "FP":
- typ := state.types[e.parts[1].name]
- offset, err := strconv.ParseInt(e.parts[2].name, 10, 64)
- if err != nil {
- panic(err)
- }
- v := b.NewValue(ssa.OpFPAddr, types.NewPointer(typ), offset)
- return v
- case "SP":
- typ := state.types[e.parts[1].name]
- offset, err := strconv.ParseInt(e.parts[2].name, 10, 64)
- if err != nil {
- panic(err)
- }
- v := b.NewValue(ssa.OpSPAddr, types.NewPointer(typ), offset)
- return v
- case "LOAD":
- p := genExpr(state, b, e.parts[1])
- v := b.NewValue(ssa.OpLoad, p.Type.(*types.Pointer).Elem(), nil)
- v.AddArg(p)
- v.AddArg(genVar(state, b, state.memID))
- return v
- */
- default:
- fmt.Println(e.parts[0].name)
- panic("unknown op")
- }
-}
-
-// map key combining block id and variable id
-type blockvar struct {
- bid ssa.ID
- varid int
-}
-
-type ssaFuncState struct {
- types map[string]ssa.Type
- varnames []string
- varids map[string]int
- vartypes []ssa.Type
- curBlock *SparseMap // value of each variable in block we're working on
- defs map[blockvar]*ssa.Value // values for variables at the end of blocks
- done []bool
- memID int
-}
-
-// Find the value of the variable with the given id leaving block b.
-func lookupVarOutgoing(state *ssaFuncState, b *ssa.Block, id int) *ssa.Value {
- fmt.Printf("lookupOutgoing var=%d block=%d\n", id, b.ID)
- v := state.defs[blockvar{b.ID, id}]
- if v != nil {
- return v
- }
- if state.done[b.ID] {
- // The variable was not defined in this block, and we haven't
- // memoized the answer yet. Look it up recursively. This might
- // cause infinite recursion, so add a copy first.
- v = b.NewValue(ssa.OpCopy, state.vartypes[id], nil)
- state.defs[blockvar{b.ID, id}] = v
- v.AddArg(lookupVarIncoming(state, b, id))
- return v
- }
- // We don't know about defined variables in this block (yet).
- // Make a forward reference for this variable.
- fmt.Printf("making fwdRef for var=%d in block=%d\n", id, b.ID)
- v = b.NewValue(ssa.OpFwdRef, state.vartypes[id], id)
-
- // memoize result
- state.defs[blockvar{b.ID, id}] = v
- return v
-}
-
-// Find the Value of the variable coming into block b.
-func lookupVarIncoming(state *ssaFuncState, b *ssa.Block, id int) *ssa.Value {
- fmt.Printf("lookupIncoming var=%d block=%d\n", id, b.ID)
- var v *ssa.Value
- switch len(b.Preds) {
- case 0:
- // TODO: handle function args some other way (assignments in starting block?)
- // TODO: error if variable isn't a function arg (including mem input)
- v = b.NewValue(ssa.OpArg, state.vartypes[id], state.varnames[id])
- case 1:
- v = lookupVarOutgoing(state, b.Preds[0], id)
- default:
- v = b.NewValue(ssa.OpCopy, state.vartypes[id], nil)
-
- args := make([]*ssa.Value, len(b.Preds))
- for i, p := range b.Preds {
- args[i] = lookupVarOutgoing(state, p, id)
- }
-
- // if <=1 value that isn't this variable's fwdRef, don't make phi
- v.Op = ssa.OpPhi
- v.AddArgs(args...) // note: order corresponding to b.Pred
- }
- return v
-}
-
-func parseSexprType(e sexpr) ssa.Type {
- if !e.compound {
- switch e.name {
- case "int":
- // TODO: pick correct width
- return ssa.TypeInt64
- default:
- fmt.Println(e.name)
- panic("unknown type")
- }
- }
- /*
- if e.parts[0].name == "FUNC" {
- // TODO: receiver? Already folded into args? Variadic?
- var args, rets []*types.Var
- for _, s := range e.parts[1].parts {
- t := parseSexprType(s)
- args = append(args, types.NewParam(0, nil, "noname", t))
- }
- for _, s := range e.parts[2].parts {
- t := parseSexprType(s)
- rets = append(rets, types.NewParam(0, nil, "noname", t))
- }
- sig := types.NewSignature(nil, nil, types.NewTuple(args...), types.NewTuple(rets...), false)
- return ssa.Type(sig)
- }
- */
- // TODO: array/struct/...
- panic("compound type")
-}
diff --git a/src/cmd/internal/ssa/ssac/sexpr.go b/src/cmd/internal/ssa/ssac/sexpr.go
deleted file mode 100644
index 77e8923..0000000
--- a/src/cmd/internal/ssa/ssac/sexpr.go
+++ /dev/null
@@ -1,82 +0,0 @@
-// Copyright 2015 The Go Authors. All rights reserved.
-// Use of this source code is governed by a BSD-style
-// license that can be found in the LICENSE file.
-
-package main
-
-import "strings"
-
-// an sexpr is an s-expression. It is either a token or a
-// parenthesized list of s-expressions.
-//
-// Used just for initial development. Should we keep it for testing, or
-// ditch it once we've plugged into the main compiler output?
-
-type sexpr struct {
- compound bool
- name string // !compound
- parts []sexpr // compound
-}
-
-func (s *sexpr) String() string {
- if !s.compound {
- return s.name
- }
- x := "("
- for i, p := range s.parts {
- if i != 0 {
- x += " "
- }
- x += p.String()
- }
- return x + ")"
-}
-
-func parseSexpr(s string) sexpr {
- var e string
- e, s = grabOne(s)
- if len(e) > 0 && e[0] == '(' {
- e = e[1 : len(e)-1]
- var parts []sexpr
- for e != "" {
- var p string
- p, e = grabOne(e)
- parts = append(parts, parseSexpr(p))
- }
- return sexpr{true, "", parts}
- }
- return sexpr{false, e, nil}
-}
-
-// grabOne peels off first token or parenthesized string from s.
-// returns first thing and the remainder of s.
-func grabOne(s string) (string, string) {
- for len(s) > 0 && s[0] == ' ' {
- s = s[1:]
- }
- if len(s) == 0 || s[0] != '(' {
- i := strings.Index(s, " ")
- if i < 0 {
- return s, ""
- }
- return s[:i], s[i:]
- }
- d := 0
- i := 0
- for {
- if len(s) == i {
- panic("unterminated s-expression: " + s)
- }
- if s[i] == '(' {
- d++
- }
- if s[i] == ')' {
- d--
- if d == 0 {
- i++
- return s[:i], s[i:]
- }
- }
- i++
- }
-}
diff --git a/src/cmd/internal/ssa/ssac/sparsemap.go b/src/cmd/internal/ssa/ssac/sparsemap.go
deleted file mode 100644
index b7a0fb0..0000000
--- a/src/cmd/internal/ssa/ssac/sparsemap.go
+++ /dev/null
@@ -1,69 +0,0 @@
-// Copyright 2015 The Go Authors. All rights reserved.
-// Use of this source code is governed by a BSD-style
-// license that can be found in the LICENSE file.
-
-package main
-
-// Maintains a map[int]*ssa.Value, but cheaper.
-
-// from http://research.swtch.com/sparse
-// in turn, from Briggs and Torczon
-
-import (
- "cmd/internal/ssa"
-)
-
-type SparseMap struct {
- dense []SparseMapEntry
- sparse []int
-}
-type SparseMapEntry struct {
- Key int
- Val *ssa.Value
-}
-
-// NewSparseMap returns a SparseMap that can have
-// integers between 0 and n-1 as keys.
-func NewSparseMap(n int) *SparseMap {
- return &SparseMap{nil, make([]int, n)}
-}
-
-func (s *SparseMap) Get(x int) *ssa.Value {
- i := s.sparse[x]
- if i < len(s.dense) && s.dense[i].Key == x {
- return s.dense[i].Val
- }
- return nil
-}
-
-func (s *SparseMap) Put(x int, v *ssa.Value) {
- i := s.sparse[x]
- if i < len(s.dense) && s.dense[i].Key == x {
- s.dense[i].Val = v
- return
- }
- i = len(s.dense)
- s.dense = append(s.dense, SparseMapEntry{x, v})
- s.sparse[x] = i
-}
-
-func (s *SparseMap) Remove(x int) {
- i := s.sparse[x]
- if i < len(s.dense) && s.dense[i].Key == x {
- y := s.dense[len(s.dense)-1]
- s.dense[i] = y
- s.sparse[y.Key] = i
- s.dense = s.dense[:len(s.dense)-1]
- }
-}
-
-func (s *SparseMap) Clear() {
- s.dense = s.dense[:0]
-}
-
-// Contents returns a slice of key/value pairs.
-// Caller must not modify any returned entries.
-// The return value is invalid after the SparseMap is modified in any way.
-func (s *SparseMap) Contents() []SparseMapEntry {
- return s.dense
-}
