From 12f980bc85c1ded76ba8b861b5ec4a50146f868f Mon Sep 17 00:00:00 2001 From: Keith Randall Date: Wed, 13 May 2015 14:18:12 -0700 Subject: [PATCH] [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 --- src/cmd/internal/ssa/ssac/.gitignore | 1 - src/cmd/internal/ssa/ssac/fib.goir | 47 --- src/cmd/internal/ssa/ssac/fibiter.goir | 62 ---- src/cmd/internal/ssa/ssac/main.go | 439 ------------------------- src/cmd/internal/ssa/ssac/sexpr.go | 82 ----- src/cmd/internal/ssa/ssac/sparsemap.go | 69 ---- 6 files changed, 700 deletions(-) delete mode 100644 src/cmd/internal/ssa/ssac/.gitignore delete mode 100644 src/cmd/internal/ssa/ssac/fib.goir delete mode 100644 src/cmd/internal/ssa/ssac/fibiter.goir delete mode 100644 src/cmd/internal/ssa/ssac/main.go delete mode 100644 src/cmd/internal/ssa/ssac/sexpr.go delete mode 100644 src/cmd/internal/ssa/ssac/sparsemap.go diff --git a/src/cmd/internal/ssa/ssac/.gitignore b/src/cmd/internal/ssa/ssac/.gitignore deleted file mode 100644 index ab17b9d28e..0000000000 --- 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 0875d63ca3..0000000000 --- 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 98b2b2b576..0000000000 --- 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 2afa7c6aa9..0000000000 --- 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 77e8923dd0..0000000000 --- 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 b7a0fb0fde..0000000000 --- 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 -} -- 2.48.1