package ssa import ( "git.smesh.lol/moxie/pkg/token" "git.smesh.lol/moxie/pkg/types" ) type SelectDir int32 const ( SelectDirRecv SelectDir = 0 SelectDirSend SelectDir = 1 ) // SSA operator codes (replacing go/token.Token for BinOp/UnOp). type SSAOp int32 const ( OpIllegal SSAOp = iota OpAdd OpSub OpMul OpQuo OpRem OpAnd OpXor OpShl OpShr OpOr OpAndNot OpLand OpLor OpArrow OpNot OpEql OpNeq OpLss OpLeq OpGtr OpGeq ) func (op SSAOp) String() (s string) { switch op { case OpAdd: return "+" case OpSub: return "-" case OpMul: return "*" case OpQuo: return "/" case OpRem: return "%" case OpAnd: return "&" case OpXor: return "^" case OpOr: return "|" case OpShl: return "<<" case OpShr: return ">>" case OpAndNot: return "&^" case OpLand: return "&&" case OpLor: return "||" case OpArrow: return "<-" case OpNot: return "!" case OpEql: return "==" case OpNeq: return "!=" case OpLss: return "<" case OpLeq: return "<=" case OpGtr: return ">" case OpGeq: return ">=" } return "?" } // ssaConstString returns a string representation of a constant value. func ssaConstString(val types.ConstVal) (s string) { if val == nil { return "nil" } return val.String() } // SSA Value interface. type SSAValue interface { SSAName() string String() string SSAType() types.Type SSAParent() *SSAFunction SSAPos() int32 } // SSA Instruction interface. type SSAInstruction interface { InstrBlock() *SSABasicBlock InstrParent() *SSAFunction InstrPos() int32 InstrString() string setBlock(*SSABasicBlock) } // SSA Member interface (package-level declaration). type SSAMember interface { MemberName() string MemberString() string MemberType() types.Type MemberPkg() *SSAPackage } // SSA Program - top-level container. type SSAProgram struct { imported map[string]*SSAPackage packages map[*types.TCPackage]*SSAPackage } func NewSSAProgram() (s *SSAProgram) { return &SSAProgram{ imported: map[string]*SSAPackage{}, packages: map[*types.TCPackage]*SSAPackage{}, } } func (prog *SSAProgram) ImportedPackage(path string) (s *SSAPackage) { return prog.imported[path] } func (prog *SSAProgram) release() { } // SSA Package. type SSAPackage struct { Prog *SSAProgram Pkg *types.TCPackage Members map[string]SSAMember } func (p *SSAPackage) Func(name string) (s *SSAFunction) { m := p.Members[name] if m == nil { return nil } fn, _ := m.(*SSAFunction) return fn } func (p *SSAPackage) ExternalFunc(name string, sig *types.Signature) (s *SSAFunction) { if fn := p.Func(name); fn != nil { return fn } fn := &SSAFunction{ name: name, Signature: sig, Pkg: p, Prog: p.Prog, } p.Members[name] = fn return fn } func (p *SSAPackage) release() { for _, m := range p.Members { if fn, ok := m.(*SSAFunction); ok { } } } // SSA Function. type SSAFunction struct { name string object *types.TCFunc Signature *types.Signature pos int32 Synthetic string externalSymbol string isExternC bool Pkg *SSAPackage Prog *SSAProgram Params []*SSAParameter FreeVars []*SSAFreeVar Locals []*SSAAlloc Blocks []*SSABasicBlock AnonFuncs []*SSAFunction NamedResults []*SSAAlloc parent *SSAFunction vars map[types.Object]SSAValue } func (f *SSAFunction) MemberName() (s string) { return f.name } func (f *SSAFunction) MemberString() (s string) { return f.name } func (f *SSAFunction) MemberType() (t types.Type) { if f.Signature == nil { return nil } return f.Signature } func (f *SSAFunction) MemberPkg() (s *SSAPackage) { return f.Pkg } func (f *SSAFunction) SSAName() (s string) { return f.name } func (f *SSAFunction) String() (s string) { return f.name } func (f *SSAFunction) SSAType() (t types.Type) { return f.MemberType() } func (f *SSAFunction) SSAParent() (s *SSAFunction) { return f.parent } func (f *SSAFunction) SSAPos() (n int32) { return f.pos } func (f *SSAFunction) IsExternC() (ok bool) { return f.isExternC } func (f *SSAFunction) ExternalSymbol() (s string) { return f.externalSymbol } // SSA BasicBlock. type SSABasicBlock struct { Index int32 Comment string ScopeID int32 parent *SSAFunction Instrs []SSAInstruction Preds []*SSABasicBlock Succs []*SSABasicBlock } func (b *SSABasicBlock) Parent() (s *SSAFunction) { return b.parent } func NewSSABasicBlock(parent *SSAFunction, comment string) (s *SSABasicBlock) { b := &SSABasicBlock{ Index: len(parent.Blocks), Comment: comment, parent: parent, } parent.Blocks = append(parent.Blocks, b) return b } // ssaRegister - shared base for instructions that produce a value. type ssaRegister struct { ssaInstr name string typ types.Type pos int32 } func (r *ssaRegister) SSAName() (s string) { return r.name } func (r *ssaRegister) SSAType() (t types.Type) { return r.typ } func (r *ssaRegister) SSAPos() (n int32) { return r.pos } func (r *ssaRegister) SSAParent() (s *SSAFunction) { if r.block != nil { return r.block.parent }; return nil } func (r *ssaRegister) String() (s string) { return r.name } func (r *ssaRegister) InstrBlock() (s *SSABasicBlock) { return r.block } func (r *ssaRegister) InstrParent() (s *SSAFunction) { if r.block != nil { return r.block.parent }; return nil } func (r *ssaRegister) setBlock(b *SSABasicBlock) { r.block = b } // ssaInstr - base for all instructions. type ssaInstr struct { block *SSABasicBlock } func (a *ssaInstr) InstrBlock() (s *SSABasicBlock) { return a.block } func (a *ssaInstr) InstrParent() (s *SSAFunction) { return a.block.parent } func (a *ssaInstr) setBlock(b *SSABasicBlock) { a.block = b } // Package-level global variable. type SSAGlobal struct { name string object *types.TCVar typ types.Type pos int32 pkg *SSAPackage } func (g *SSAGlobal) MemberName() (s string) { return g.name } func (g *SSAGlobal) MemberString() (s string) { return g.pkg.Pkg.Path() | "." | g.name } func (g *SSAGlobal) MemberType() (t types.Type) { return g.typ } func (g *SSAGlobal) MemberPkg() (s *SSAPackage) { return g.pkg } func (g *SSAGlobal) SSAName() (s string) { return g.name } func (g *SSAGlobal) String() (s string) { return g.MemberString() } func (g *SSAGlobal) SSAType() (t types.Type) { return g.typ } func (g *SSAGlobal) SSAParent() (s *SSAFunction) { return nil } func (g *SSAGlobal) SSAPos() (n int32) { return g.pos } // Package-level named type. type SSAType_ struct { object *types.TypeName pkg *SSAPackage } func (t *SSAType_) MemberName() (s string) { return t.object.Name() } func (t *SSAType_) MemberString() (s string) { return t.pkg.Pkg.Path() | "." | t.object.Name() } func (t *SSAType_) MemberType() (tv types.Type) { return t.object.Type() } func (t *SSAType_) MemberPkg() (s *SSAPackage) { return t.pkg } // Package-level named constant. type SSANamedConst struct { object *types.TCConst Value *SSAConst pkg *SSAPackage } func (c *SSANamedConst) MemberName() (s string) { return c.object.Name() } func (c *SSANamedConst) MemberString() (s string) { return c.pkg.Pkg.Path() | "." | c.object.Name() } func (c *SSANamedConst) MemberType() (t types.Type) { return c.object.Type() } func (c *SSANamedConst) MemberPkg() (s *SSAPackage) { return c.pkg } // Parameter. type SSAParameter struct { name string object *types.TCVar typ types.Type pos int32 parent *SSAFunction } func (p *SSAParameter) SSAName() (s string) { return p.name } func (p *SSAParameter) String() (s string) { return p.name } func (p *SSAParameter) SSAType() (t types.Type) { return p.typ } func (p *SSAParameter) SSAParent() (s *SSAFunction) { return p.parent } func (p *SSAParameter) SSAPos() (n int32) { return p.pos } // FreeVar (closure capture). type SSAFreeVar struct { name string typ types.Type pos int32 parent *SSAFunction } func (v *SSAFreeVar) SSAName() (s string) { return v.name } func (v *SSAFreeVar) String() (s string) { return v.name } func (v *SSAFreeVar) SSAType() (t types.Type) { return v.typ } func (v *SSAFreeVar) SSAParent() (s *SSAFunction) { return v.parent } func (v *SSAFreeVar) SSAPos() (n int32) { return v.pos } // Const value. type SSAConst struct { typ types.Type val types.ConstVal } func NewSSAConst(val types.ConstVal, typ types.Type) (s *SSAConst) { return &SSAConst{typ: typ, val: val} } func (c *SSAConst) SSAName() (s string) { return ssaConstString(c.val) } func (c *SSAConst) String() (s string) { return ssaConstString(c.val) } func (c *SSAConst) SSAType() (t types.Type) { return c.typ } func (c *SSAConst) SSAParent() (s *SSAFunction) { return nil } func (c *SSAConst) SSAPos() (n int32) { return 0 } func (c *SSAConst) Value() (cv types.ConstVal) { return c.val } func (c *SSAConst) SetValue(v types.ConstVal) { c.val = v } func (c *SSAConst) SetSSAType(t types.Type) { c.typ = t } type SSABuiltin struct { id types.BuiltinID name string } func (b *SSABuiltin) SSAName() (s string) { return b.name } func (b *SSABuiltin) String() (s string) { return b.name } func (b *SSABuiltin) SSAType() (t types.Type) { return nil } func (b *SSABuiltin) SSAParent() (s *SSAFunction) { return nil } func (b *SSABuiltin) SSAPos() (n int32) { return 0 } // CallCommon describes a function/method call. type SSACallCommon struct { Value SSAValue Args []SSAValue pos int32 HasDots bool } // -- Instruction types -- // Alloc allocates space for a variable. type SSAAlloc struct { ssaRegister Heap bool Comment string } func (a *SSAAlloc) InstrPos() (n int32) { return a.pos } func (a *SSAAlloc) InstrString() (s string) { if a.Heap { return "new " | a.typ.String() } return "local " | a.typ.String() } // Phi node. type SSAPhi struct { ssaRegister Comment string Edges []SSAValue } func (p *SSAPhi) InstrPos() (n int32) { return p.pos } func (p *SSAPhi) InstrString() (s string) { return "phi " | p.Comment } // Call instruction. type SSACall struct { ssaRegister Call SSACallCommon } func (c *SSACall) InstrPos() (n int32) { return c.Call.pos } func (c *SSACall) InstrString() (s string) { return "call " | c.Call.Value.SSAName() } // BinOp. type SSABinOp struct { ssaRegister Op SSAOp X SSAValue Y SSAValue } func (b *SSABinOp) InstrPos() (n int32) { return b.pos } func (b *SSABinOp) InstrString() (s string) { return "binop " | b.Op.String() } // UnOp. type SSAUnOp struct { ssaRegister Op SSAOp X SSAValue CommaOk bool } func (u *SSAUnOp) InstrPos() (n int32) { return u.pos } func (u *SSAUnOp) InstrString() (s string) { return "unop " | u.Op.String() } // ChangeType. type SSAChangeType struct { ssaRegister X SSAValue } func (c *SSAChangeType) InstrPos() (n int32) { return c.pos } func (c *SSAChangeType) InstrString() (s string) { return "changetype" } // Convert. type SSAConvert struct { ssaRegister X SSAValue } func (c *SSAConvert) InstrPos() (n int32) { return c.pos } func (c *SSAConvert) InstrString() (s string) { return "convert" } // MakeInterface. type SSAMakeInterface struct { ssaRegister X SSAValue IType types.Type } func (m *SSAMakeInterface) InstrPos() (n int32) { return m.pos } func (m *SSAMakeInterface) InstrString() (s string) { return "makeinterface" } // Invoke - interface method call. type SSAInvoke struct { ssaRegister X SSAValue MethodName string IfaceType *types.TCInterface Args []SSAValue } func (inv *SSAInvoke) InstrPos() (n int32) { return inv.pos } func (inv *SSAInvoke) InstrString() (s string) { return "invoke " | inv.MethodName } // MakeClosure. type SSAMakeClosure struct { ssaRegister Fn SSAValue Bindings []SSAValue } func (m *SSAMakeClosure) InstrPos() (n int32) { return m.pos } func (m *SSAMakeClosure) InstrString() (s string) { return "makeclosure" } // MakeMap. type SSAMakeMap struct { ssaRegister Reserve SSAValue } func (m *SSAMakeMap) InstrPos() (n int32) { return m.pos } func (m *SSAMakeMap) InstrString() (s string) { return "makemap" } // MakeChan. type SSAMakeChan struct { ssaRegister Size SSAValue } func (m *SSAMakeChan) InstrPos() (n int32) { return m.pos } func (m *SSAMakeChan) InstrString() (s string) { return "makechan" } // MakeSlice. type SSAMakeSlice struct { ssaRegister Len SSAValue Cap SSAValue Data SSAValue } func (m *SSAMakeSlice) InstrPos() (n int32) { return m.pos } func (m *SSAMakeSlice) InstrString() (s string) { return "makeslice" } // Slice. type SSASlice struct { ssaRegister X SSAValue Low SSAValue High SSAValue Max SSAValue } func (s *SSASlice) InstrPos() (n int32) { return s.pos } func (s *SSASlice) InstrString() (sv string) { return "slice" } // FieldAddr. type SSAFieldAddr struct { ssaRegister X SSAValue Field int32 } func (f *SSAFieldAddr) InstrPos() (n int32) { return f.pos } func (f *SSAFieldAddr) InstrString() (s string) { return "fieldaddr" } // IndexAddr. type SSAIndexAddr struct { ssaRegister X SSAValue Index SSAValue } func (i *SSAIndexAddr) InstrPos() (n int32) { return i.pos } func (i *SSAIndexAddr) InstrString() (s string) { return "indexaddr" } // Lookup (map[k]). type SSALookup struct { ssaRegister X SSAValue Index SSAValue CommaOk bool } func (l *SSALookup) InstrPos() (n int32) { return l.pos } func (l *SSALookup) InstrString() (s string) { return "lookup" } // Range. type SSARange struct { ssaRegister X SSAValue } func (r *SSARange) InstrPos() (n int32) { return r.pos } func (r *SSARange) InstrString() (s string) { return "range" } // Next (iterator advance). type SSANext struct { ssaRegister Iter SSAValue IsString bool } func (n *SSANext) InstrPos() (nv int32) { return n.pos } func (n *SSANext) InstrString() (s string) { return "next" } // TypeAssert. type SSATypeAssert struct { ssaRegister X SSAValue AssertedType types.Type CommaOk bool } func (t *SSATypeAssert) InstrPos() (n int32) { return t.pos } func (t *SSATypeAssert) InstrString() (s string) { return "typeassert" } // Extract (tuple component). type SSAExtract struct { ssaRegister Tuple SSAValue Index int32 } func (e *SSAExtract) InstrPos() (n int32) { return e.pos } func (e *SSAExtract) InstrString() (s string) { return "extract" } // -- Terminator instructions -- // Jump. type SSAJump struct { ssaInstr Comment string } func (j *SSAJump) InstrPos() (n int32) { return 0 } func (j *SSAJump) InstrString() (s string) { return "jump " | j.Comment } // If. type SSAIf struct { ssaInstr Cond SSAValue } func (i *SSAIf) InstrPos() (n int32) { return 0 } func (i *SSAIf) InstrString() (s string) { return "if" } // Return. type SSAReturn struct { ssaInstr Results []SSAValue pos int32 } func (r *SSAReturn) InstrPos() (n int32) { return r.pos } func (r *SSAReturn) InstrString() (s string) { return "return" } // RunDefers. type SSARunDefers struct { ssaInstr } func (rd *SSARunDefers) InstrPos() (n int32) { return 0 } func (rd *SSARunDefers) InstrString() (s string) { return "rundefers" } // Panic. type SSAPanic struct { ssaInstr X SSAValue pos int32 } func (p *SSAPanic) InstrPos() (n int32) { return p.pos } func (p *SSAPanic) InstrString() (s string) { return "panic" } // Go (spawn). type SSAGo struct { ssaInstr Call SSACallCommon pos int32 } func (g *SSAGo) InstrPos() (n int32) { return g.pos } func (g *SSAGo) InstrString() (s string) { return "go" } // Defer. type SSADefer struct { ssaInstr Call SSACallCommon pos int32 } func (d *SSADefer) InstrPos() (n int32) { return d.pos } func (d *SSADefer) InstrString() (s string) { return "defer" } // -- Side-effecting instructions -- // Send. type SSASend struct { ssaInstr Chan SSAValue X SSAValue pos int32 } func (s *SSASend) InstrPos() (n int32) { return s.pos } func (s *SSASend) InstrString() (sv string) { return "send" } // Store. type SSAStore struct { ssaInstr Addr SSAValue Val SSAValue pos int32 } func (s *SSAStore) InstrPos() (n int32) { return s.pos } func (s *SSAStore) InstrString() (sv string) { return "store" } // MapUpdate. type SSAMapUpdate struct { ssaInstr Map SSAValue Key SSAValue Value SSAValue pos int32 } func (m *SSAMapUpdate) InstrPos() (n int32) { return m.pos } func (m *SSAMapUpdate) InstrString() (s string) { return "mapupdate" } // SelectState describes one case of a select statement. type SSASelectState struct { Dir SelectDir Chan SSAValue Send SSAValue } // Select instruction. type SSASelect struct { ssaRegister States []*SSASelectState Blocking bool } func (s *SSASelect) InstrPos() (n int32) { return s.pos } func (s *SSASelect) InstrString() (sv string) { return "select" } // Operator mapping from token.Operator to SSAOp. func syntaxOpToSSAOp(op token.Operator, unary bool) (s SSAOp) { if unary { switch op { case token.Not: return OpNot case token.Recv: return OpArrow case token.And: return OpAnd case token.Mul: return OpMul case token.Sub: return OpSub case token.Xor: return OpXor } } switch op { case token.Add: return OpAdd case token.Or: return OpOr case token.Sub: return OpSub case token.Mul: return OpMul case token.Div: return OpQuo case token.Rem: return OpRem case token.And: return OpAnd case token.Xor: return OpXor case token.Shl: return OpShl case token.Shr: return OpShr case token.AndNot: return OpAndNot case token.OrOr: return OpLor case token.AndAnd: return OpLand case token.Eql: return OpEql case token.Neq: return OpNeq case token.Lss: return OpLss case token.Leq: return OpLeq case token.Gtr: return OpGtr case token.Geq: return OpGeq } return OpIllegal } func compoundOp(op token.Operator) (s SSAOp) { switch op { case token.Add: return OpAdd case token.Or: return OpOr case token.Sub: return OpSub case token.Mul: return OpMul case token.Div: return OpQuo case token.Rem: return OpRem case token.And: return OpAnd case token.Xor: return OpXor case token.Shl: return OpShl case token.Shr: return OpShr case token.AndNot: return OpAndNot } return OpIllegal } func ssaBuiltinID(name string) (types.BuiltinID, bool) { switch name { case "append": return types.BuiltinAppend, true case "cap": return types.BuiltinCap, true case "clear": return types.BuiltinClear, true case "close": return types.BuiltinClose, true case "copy": return types.BuiltinCopy, true case "delete": return types.BuiltinDelete, true case "len": return types.BuiltinLen, true case "__slicealloc", "make": return types.BuiltinMake, true case "max": return types.BuiltinMax, true case "min": return types.BuiltinMin, true case "__ptralloc", "new": return types.BuiltinNew, true case "panic": return types.BuiltinPanic, true case "print": return types.BuiltinPrint, true case "println": return types.BuiltinPrintln, true case "recover": return types.BuiltinRecover, true case "spawn": return types.BuiltinSpawn, true } return 0, false } func ssaItoa(n int32) (s string) { if n == 0 { return "0" } neg := n < 0 if neg { n = -n } buf := []byte{:0:20} for n > 0 { buf = append(buf, byte('0'+n%10)) n /= 10 } if neg { buf = append(buf, '-') } for i, j := 0, len(buf)-1; i < j; i, j = i+1, j-1 { buf[i], buf[j] = buf[j], buf[i] } return string(buf) } // Type helpers for SSA builder. func ssaElemType(t types.Type) (tv types.Type) { if t == nil { return nil } switch t := types.SafeUnderlying(t).(type) { case *types.Slice: return t.Elem() case *types.Array: return t.Elem() case *types.TCMap: return t.Elem() case *types.Pointer: return t.Elem() case *types.Basic: if t.Info()&types.IsString != 0 { return types.Typ[types.Uint8] } } return nil } func ssaChanElemType(t types.Type) (tv types.Type) { if t == nil { return nil } if ch, ok := types.SafeUnderlying(t).(*types.TCChan); ok { return ch.Elem() } return nil } func ssaIsStringType(t types.Type) (ok bool) { if t == nil { return false } if b, ok := types.SafeUnderlying(t).(*types.Basic); ok { return b.Info()&types.IsString != 0 } return false } func ssaSliceOf(t types.Type) (tv types.Type) { if t == nil { return nil } if b, ok := types.SafeUnderlying(t).(*types.Basic); ok && b.Info()&types.IsString != 0 { return t } switch t := types.SafeUnderlying(t).(type) { case *types.Slice: return t case *types.Array: if b, ok := t.Elem().(*types.Basic); ok && b.Kind() == types.Uint8 { return types.Typ[types.TCString] } return types.NewSlice(t.Elem()) case *types.Pointer: if t.Elem() != nil { return ssaSliceOf(t.Elem()) } } return types.Typ[types.TCString] } func ssaTupleElemType(t types.Type, i int32) (tv types.Type) { if t == nil { return nil } if tup, ok := t.(*types.Tuple); ok && i < tup.Len() { return tup.At(i).Type() } return nil } func ssaParseInt64(s string) (n int64) { var n int64 for i := 0; i < len(s); i++ { c := s[i] if c < '0' || c > '9' { break } n = n*10 + int64(c-'0') } return n }