package ssa import ( "git.smesh.lol/moxie/pkg/token" "git.smesh.lol/moxie/pkg/syntax" "git.smesh.lol/moxie/pkg/types" ) func newSSAFuncBuilder(fn *SSAFunction, info *types.Info) (p *ssaFuncBuilder) { return &ssaFuncBuilder{ fn: fn, info: info, vars: map[types.Object]*SSAAlloc{}, localTypes: map[string]types.Type{}, } } func (fb *ssaFuncBuilder) newBlock(comment string) (s *SSABasicBlock) { b := NewSSABasicBlock(fb.fn, comment) b.ScopeID = fb.scopeID return b } func (fb *ssaFuncBuilder) enterScope() int32 { fb.nextScopeID++ old := fb.scopeID fb.scopeID = fb.nextScopeID return old } func (fb *ssaFuncBuilder) exitScope(old int32) { fb.scopeID = old } func (fb *ssaFuncBuilder) labelBlock(name string) (s *SSABasicBlock) { if fb.labels == nil { fb.labels = map[string]*SSABasicBlock{} } if b := fb.labels[name]; b != nil { return b } b := fb.newBlock("label." | name) fb.labels[name] = b return b } func (fb *ssaFuncBuilder) emit(instr SSAInstruction) { if fb.currentBlock == nil { return } instr.setBlock(fb.currentBlock) fb.currentBlock.Instrs = append(fb.currentBlock.Instrs, instr) } func (fb *ssaFuncBuilder) nextName() (s string) { fb.counter++ return "t" | ssaItoa(fb.counter) } func (fb *ssaFuncBuilder) buildBody(d *syntax.FuncDecl) { entry := fb.newBlock("entry") fb.currentBlock = entry sig := fb.fn.Signature if sig == nil { return } params := sig.Params() if d.Recv != nil { recv := sig.Recv() if recv != nil { recvName := recv.Name() if recvName == "" && d.Recv.Name != nil { recvName = d.Recv.Name.Value } p := &SSAParameter{ name: recvName, typ: recv.Type(), pos: 0, parent: fb.fn, } fb.fn.Params = append(fb.fn.Params, p) if recvName != "" && recvName != "_" { recvObj := types.NewTCVar(fb.fn.Pkg.Pkg, recvName, recv.Type()) p.object = recvObj alloc := fb.emitAlloc(recv.Type(), 0) fb.vars[recvObj] = alloc fb.paramAllocas = append(fb.paramAllocas, alloc) fb.emitStore(alloc, p) } } } if params != nil { for i := 0; i < params.Len(); i++ { pvar := params.At(i) p := &SSAParameter{ name: pvar.Name(), typ: pvar.Type(), pos: fb.fn.pos, parent: fb.fn, } fb.fn.Params = append(fb.fn.Params, p) if pvar.Name() != "" && pvar.Name() != "_" { obj := types.NewTCVar(fb.fn.Pkg.Pkg, pvar.Name(), pvar.Type()) alloc := fb.emitAlloc(pvar.Type(), p.pos) fb.vars[obj] = alloc fb.paramAllocas = append(fb.paramAllocas, alloc) fb.emitStore(alloc, p) } } } if sig.Results() != nil { for i := 0; i < sig.Results().Len(); i++ { r := sig.Results().At(i) if r.Name() != "" && r.Name() != "_" { alloc := fb.emitAlloc(r.Type(), fb.fn.pos) fb.namedResults = append(fb.namedResults, alloc) fb.fn.Locals = append(fb.fn.Locals, alloc) fb.vars[r] = alloc } } } if len(fb.paramAllocas) > 0 { fb.tailBlock = fb.newBlock("tailcall") fb.emit(&SSAJump{Comment: "enter.body"}) fb.currentBlock.Succs = append(fb.currentBlock.Succs, fb.tailBlock) fb.tailBlock.Preds = append(fb.tailBlock.Preds, fb.currentBlock) fb.currentBlock = fb.tailBlock } if d.Body != nil { fb.buildBlock(d.Body) } if fb.currentBlock != nil && !fb.blockTerminated(fb.currentBlock) { if len(fb.namedResults) > 0 { var vals []SSAValue for _, nr := range fb.namedResults { elemType := nr.SSAType() if p, ok := elemType.(*types.Pointer); ok { elemType = p.Elem() } vals = append(vals, fb.emitLoad(nr, elemType)) } fb.emitReturn(vals, 0) } else { fb.emitReturn(nil, 0) } } fb.fn.NamedResults = fb.namedResults } func (fb *ssaFuncBuilder) emitAlloc(typ types.Type, pos int32) (s *SSAAlloc) { a := &SSAAlloc{Heap: false} a.typ = types.NewPointer(typ) a.pos = pos a.name = fb.nextName() fb.emit(a) fb.fn.Locals = append(fb.fn.Locals, a) return a } func (fb *ssaFuncBuilder) emitStore(addr SSAValue, val SSAValue) { fb.emit(&SSAStore{Addr: addr, Val: val}) } func (fb *ssaFuncBuilder) emitLoad(addr SSAValue, typ types.Type) (s SSAValue) { u := &SSAUnOp{Op: OpMul, X: addr} u.typ = typ u.name = fb.nextName() fb.emit(u) return u } func (fb *ssaFuncBuilder) emitReturn(vals []SSAValue, pos int32) { fb.emit(&SSAReturn{Results: vals, pos: pos}) fb.currentBlock = nil } func (fb *ssaFuncBuilder) blockTerminated(b *SSABasicBlock) (ok bool) { if len(b.Instrs) == 0 { return false } switch b.Instrs[len(b.Instrs)-1].(type) { case *SSAReturn, *SSAJump, *SSAIf, *SSAPanic: return true } return false } // Statement builders. func (fb *ssaFuncBuilder) buildBlock(b *syntax.BlockStmt) { if b == nil { return } for _, s := range b.List { fb.buildStmt(s) } } func (fb *ssaFuncBuilder) buildStmt(s syntax.Stmt) { if s == nil { return } if ls, ok := s.(*syntax.LabeledStmt); ok { if ls.Label != nil { fb.pendingLabel = ls.Label.Value lblBlock := fb.labelBlock(ls.Label.Value) if fb.currentBlock != nil { fb.emit(&SSAJump{Comment: "goto.label." | ls.Label.Value}) fb.currentBlock.Succs = append(fb.currentBlock.Succs, lblBlock) lblBlock.Preds = append(lblBlock.Preds, fb.currentBlock) } fb.currentBlock = lblBlock } fb.buildStmt(ls.Stmt) fb.pendingLabel = "" return } if fb.currentBlock == nil { return } switch s := s.(type) { case *syntax.EmptyStmt: // nothing case *syntax.ExprStmt: fb.buildExpr(s.X) case *syntax.AssignStmt: fb.buildAssign(s) case *syntax.BlockStmt: fb.buildBlock(s) case *syntax.DeclStmt: for _, d := range s.DeclList { fb.buildLocalDecl(d) } case *syntax.IfStmt: fb.buildIf(s) case *syntax.ForStmt: fb.buildFor(s) case *syntax.SwitchStmt: fb.buildSwitch(s) case *syntax.SelectStmt: fb.buildSelect(s) case *syntax.ReturnStmt: fb.buildReturn(s) case *syntax.BranchStmt: fb.buildBranch(s) case *syntax.SendStmt: ch := fb.buildExpr(s.Chan) val := fb.buildExpr(s.Value) if ch != nil && val != nil { fb.emit(&SSASend{Chan: ch, X: val}) } case *syntax.CallStmt: call, _ := s.Call.(*syntax.CallExpr) switch s.Tok { case token.Go: if call != nil { fb.buildGoStmt(call) } case token.Defer: if call != nil { fb.buildDeferStmt(call) } default: fb.buildExpr(s.Call) } } } func (fb *ssaFuncBuilder) buildAssign(s *syntax.AssignStmt) { if s.Rhs == nil { lv := fb.buildExpr(s.Lhs) if lv == nil { return } one := &SSAConst{typ: lv.SSAType(), val: &types.ConstInt{V:1}} op := OpAdd if s.Op == token.Sub { op = OpSub } bin := &SSABinOp{Op: op, X: lv, Y: one} bin.typ = lv.SSAType() bin.name = fb.nextName() fb.emit(bin) fb.buildStore(s.Lhs, bin) return } if s.Op == token.Def { fb.buildShortVarDecl(s) return } if s.Op != 0 { lv := fb.buildExpr(s.Lhs) rv := fb.buildExpr(s.Rhs) if lv == nil || rv == nil { return } op := compoundOp(s.Op) bin := &SSABinOp{Op: op, X: lv, Y: rv} bin.typ = lv.SSAType() bin.name = fb.nextName() fb.emit(bin) fb.buildStore(s.Lhs, bin) return } lhsList, lhsIsList := s.Lhs.(*syntax.ListExpr) rhsList, rhsIsList := s.Rhs.(*syntax.ListExpr) if lhsIsList && rhsIsList && len(lhsList.ElemList) == len(rhsList.ElemList) { vals := []SSAValue{:len(rhsList.ElemList)} for i, re := range rhsList.ElemList { vals[i] = fb.buildExpr(re) } for i, le := range lhsList.ElemList { if vals[i] != nil { fb.buildStore(le, vals[i]) } } return } if lhsIsList && len(lhsList.ElemList) == 2 { if ae, ok := s.Rhs.(*syntax.AssertExpr); ok { x := fb.buildExpr(ae.X) assertedType := fb.resolveType(ae.Type) if x != nil && assertedType != nil { ta := &SSATypeAssert{X: x, AssertedType: assertedType, CommaOk: true} ta.typ = types.NewTuple( types.NewTCVar(nil, "val", assertedType), types.NewTCVar(nil, "ok", types.Typ[types.Bool]), ) ta.name = fb.nextName() fb.emit(ta) for i, le := range lhsList.ElemList { if n, ok := le.(*syntax.Name); ok && n.Value == "_" { continue } ext := &SSAExtract{Tuple: ta, Index: i} ext.typ = ssaTupleElemType(ta.typ, i) ext.name = fb.nextName() fb.emit(ext) fb.buildStore(le, ext) } return } } if ie, ok := s.Rhs.(*syntax.IndexExpr); ok { x := fb.buildExpr(ie.X) idx := fb.buildExpr(ie.Index) if x != nil && idx != nil { if mt, ok2 := types.SafeUnderlying(x.SSAType()).(*types.TCMap); ok2 { idx = fb.coerceToInterface(idx, mt.Key()) l := &SSALookup{X: x, Index: idx, CommaOk: true} l.typ = types.NewTuple( types.NewTCVar(nil, "v", mt.Elem()), types.NewTCVar(nil, "ok", types.Typ[types.Bool]), ) l.name = fb.nextName() fb.emit(l) for i, le := range lhsList.ElemList { if n, ok := le.(*syntax.Name); ok && n.Value == "_" { continue } ext := &SSAExtract{Tuple: l, Index: i} ext.typ = ssaTupleElemType(l.typ, i) ext.name = fb.nextName() fb.emit(ext) fb.buildStore(le, ext) } return } } } } rhs := fb.buildExpr(s.Rhs) if rhs == nil { return } fb.buildStore(s.Lhs, rhs) } func (fb *ssaFuncBuilder) coerceToInterface(val SSAValue, targetType types.Type) (s SSAValue) { if targetType == nil || val == nil || val.SSAType() == nil { return val } if _, isIface := types.SafeUnderlying(targetType).(*types.TCInterface); isIface { if _, alreadyIface := types.SafeUnderlying(val.SSAType()).(*types.TCInterface); !alreadyIface { mi := &SSAMakeInterface{X: val} mi.typ = targetType mi.name = fb.nextName() fb.emit(mi) return mi } } return val } func (fb *ssaFuncBuilder) buildStore(lhs syntax.Expr, val SSAValue) { if lhs == nil { panic("buildStore: nil lhs") } switch lhs := lhs.(type) { case *syntax.Name: if lhs == nil { panic("buildStore: nil *syntax.Name after type switch") } if lhs.Value == "_" { return } obj := fb.lookupObject(lhs.Value) if obj == nil { return } if alloc, ok := fb.vars[obj]; ok { val = fb.coerceToInterface(val, obj.Type()) fb.emitStore(alloc, val) } else if fv, ok := fb.freeVarPtrs[lhs.Value]; ok { val = fb.coerceToInterface(val, obj.Type()) fb.emitStore(fv, val) } else if g, ok := fb.fn.Pkg.Members[lhs.Value].(*SSAGlobal); ok { if p, ok2 := g.SSAType().(*types.Pointer); ok2 && p.Elem() != nil { val = fb.coerceToInterface(val, p.Elem()) } fb.emitStore(g, val) } case *syntax.Operation: if lhs.Y == nil && lhs.Op == token.Mul { ptr := fb.buildExpr(lhs.X) if ptr != nil { if p, ok2 := ptr.SSAType().(*types.Pointer); ok2 && p.Elem() != nil { val = fb.coerceToInterface(val, p.Elem()) } fb.emitStore(ptr, val) } } case *syntax.SelectorExpr: addr := fb.buildSelectorAddr(lhs) if addr == nil { return } if p, ok2 := addr.SSAType().(*types.Pointer); ok2 && p.Elem() != nil { val = fb.coerceToInterface(val, p.Elem()) } fb.emitStore(addr, val) case *syntax.IndexExpr: base := fb.buildExpr(lhs.X) idx := fb.buildExpr(lhs.Index) if base == nil || idx == nil { return } if m, isMap := types.SafeUnderlying(base.SSAType()).(*types.TCMap); isMap { idx = fb.coerceToInterface(idx, m.Key()) val = fb.coerceToInterface(val, m.Elem()) fb.emit(&SSAMapUpdate{Map: base, Key: idx, Value: val}) return } // For array LHS assignment, resolve the address of the base directly // so SSAIndexAddr GEPs into the original, not a stack copy. var baseAddr SSAValue if n, ok := lhs.X.(*syntax.Name); ok { obj := fb.lookupObject(n.Value) if obj != nil { if alloc, ok2 := fb.vars[obj]; ok2 { baseAddr = alloc } else if g, ok2 := fb.fn.Pkg.Members[n.Value].(*SSAGlobal); ok2 { baseAddr = g } } } else if sel, ok := lhs.X.(*syntax.SelectorExpr); ok { baseAddr = fb.buildSelectorAddr(sel) } if baseAddr != nil { if _, isArr := types.SafeUnderlying(base.SSAType()).(*types.Array); isArr { ia := &SSAIndexAddr{X: baseAddr, Index: idx} ia.typ = types.NewPointer(ssaElemType(base.SSAType())) ia.name = fb.nextName() fb.emit(ia) if p, ok2 := ia.SSAType().(*types.Pointer); ok2 && p.Elem() != nil { val = fb.coerceToInterface(val, p.Elem()) } fb.emitStore(ia, val) return } } ia := &SSAIndexAddr{X: base, Index: idx} ia.typ = types.NewPointer(ssaElemType(base.SSAType())) ia.name = fb.nextName() fb.emit(ia) if p, ok2 := ia.SSAType().(*types.Pointer); ok2 && p.Elem() != nil { val = fb.coerceToInterface(val, p.Elem()) } fb.emitStore(ia, val) case *syntax.ListExpr: for i, e := range lhs.ElemList { ext := &SSAExtract{Tuple: val, Index: i} ext.typ = ssaTupleElemType(val.SSAType(), i) ext.name = fb.nextName() fb.emit(ext) fb.buildStore(e, ext) } } } func (fb *ssaFuncBuilder) buildShortVarDecl(s *syntax.AssignStmt) { names := ssaExprNames(s.Lhs) if len(names) == 2 { if ae, ok := s.Rhs.(*syntax.AssertExpr); ok { x := fb.buildExpr(ae.X) assertedType := fb.resolveType(ae.Type) if assertedType != nil { if x == nil { x = &SSAConst{typ: types.NewTCInterface(nil, nil)} } ta := &SSATypeAssert{X: x, AssertedType: assertedType, CommaOk: true} ta.typ = types.NewTuple( types.NewTCVar(nil, "val", assertedType), types.NewTCVar(nil, "ok", types.Typ[types.Bool]), ) ta.name = fb.nextName() fb.emit(ta) for i, name := range names { if name.Value == "_" { continue } ext := &SSAExtract{Tuple: ta, Index: i} ext.typ = ssaTupleElemType(ta.typ, i) ext.name = fb.nextName() fb.emit(ext) fb.removeVar(name.Value) obj := types.NewTCVar(fb.fn.Pkg.Pkg, name.Value, ext.typ) alloc := fb.emitAlloc(ext.typ, 0) fb.vars[obj] = alloc fb.emitStore(alloc, ext) } return } } if ie, ok := s.Rhs.(*syntax.IndexExpr); ok { x := fb.buildExpr(ie.X) idx := fb.buildExpr(ie.Index) if x != nil && idx != nil { if mt, ok2 := types.SafeUnderlying(x.SSAType()).(*types.TCMap); ok2 { idx = fb.coerceToInterface(idx, mt.Key()) l := &SSALookup{X: x, Index: idx, CommaOk: true} l.typ = types.NewTuple( types.NewTCVar(nil, "v", mt.Elem()), types.NewTCVar(nil, "ok", types.Typ[types.Bool]), ) l.name = fb.nextName() fb.emit(l) for i, name := range names { if name.Value == "_" { continue } ext := &SSAExtract{Tuple: l, Index: i} ext.typ = ssaTupleElemType(l.typ, i) ext.name = fb.nextName() fb.emit(ext) fb.removeVar(name.Value) var obj types.Object if fb.info != nil { obj = fb.info.Defs[name] } if obj == nil { obj = types.NewTCVar(fb.fn.Pkg.Pkg, name.Value, ext.typ) } alloc := fb.emitAlloc(ext.typ, 0) fb.vars[obj] = alloc fb.emitStore(alloc, ext) } return } } } } if rhsList, ok := s.Rhs.(*syntax.ListExpr); ok && len(rhsList.ElemList) == len(names) { vals := []SSAValue{:len(rhsList.ElemList)} for i, re := range rhsList.ElemList { vals[i] = fb.buildExpr(re) } for i, name := range names { if name.Value == "_" { continue } var typ types.Type if vals[i] != nil { typ = vals[i].SSAType() } fb.removeVar(name.Value) var obj types.Object if fb.info != nil { obj = fb.info.Defs[name] } if obj == nil { obj = types.NewTCVar(fb.fn.Pkg.Pkg, name.Value, typ) } alloc := fb.emitAlloc(typ, 0) fb.vars[obj] = alloc if vals[i] != nil { fb.emitStore(alloc, vals[i]) } } return } rhs := fb.buildExpr(s.Rhs) isTuple := false var tup *types.Tuple if rhs != nil { tup, isTuple = rhs.SSAType().(*types.Tuple) } for i, name := range names { if name.Value == "_" { continue } var typ types.Type if rhs != nil { if isTuple && i < tup.Len() { typ = tup.At(i).Type() } else if i == 0 { typ = rhs.SSAType() } } if typ == nil { rhsInfo := "nil" if rhs != nil { if rhs.SSAType() == nil { rhsInfo = "ssatype=nil" } else if tup2, ok2 := rhs.SSAType().(*types.Tuple); ok2 { rhsInfo = "tuple[" | simpleItoa(tup2.Len()) | "] i=" | simpleItoa(i) if i < tup2.Len() { if tup2.At(i).Type() == nil { rhsInfo = rhsInfo | " At.Type=nil" } else { rhsInfo = rhsInfo | " At.Type=set" } } } else { rhsInfo = "non-tuple" } } typ = types.Typ[types.Int32] } fb.removeVar(name.Value) var obj types.Object if fb.info != nil { obj = fb.info.Defs[name] } if obj == nil { obj = types.NewTCVar(fb.fn.Pkg.Pkg, name.Value, typ) } alloc := fb.emitAlloc(typ, 0) fb.vars[obj] = alloc var initVal SSAValue if rhs != nil { if isTuple { ext := &SSAExtract{Tuple: rhs, Index: i} ext.typ = typ ext.name = fb.nextName() fb.emit(ext) initVal = ext } else if i == 0 { initVal = rhs } } if initVal != nil { fb.emitStore(alloc, initVal) } } } func (fb *ssaFuncBuilder) buildLocalDecl(d syntax.Decl) { switch d := d.(type) { case *syntax.VarDecl: var typ types.Type if fb.info != nil && len(d.NameList) > 0 { if obj := fb.info.Defs[d.NameList[0]]; obj != nil { typ = obj.Type() } } if typ == nil && d.Type != nil { typ = fb.resolveType(d.Type) } initVal := fb.buildExpr(d.Values) for _, name := range d.NameList { if name.Value == "_" { continue } fb.removeVar(name.Value) var obj types.Object if fb.info != nil { obj = fb.info.Defs[name] } if obj == nil { obj = types.NewTCVar(fb.fn.Pkg.Pkg, name.Value, typ) } alloc := fb.emitAlloc(obj.Type(), 0) fb.vars[obj] = alloc fb.fn.Locals = append(fb.fn.Locals, alloc) if initVal != nil { initVal = fb.coerceToInterface(initVal, obj.Type()) fb.emitStore(alloc, initVal) } else { fb.emitStore(alloc, &SSAConst{typ: obj.Type(), val: nil}) } } case *syntax.ConstDecl: if d.Values != nil && len(d.NameList) > 0 { if fb.localConsts == nil { fb.localConsts = map[string]*SSAConst{} } if list, ok := d.Values.(*syntax.ListExpr); ok { for i, name := range d.NameList { if i < len(list.ElemList) { if v := fb.buildExpr(list.ElemList[i]); v != nil { if c := ssaExtractConst(v); c != nil { fb.localConsts[name.Value] = c } } } } } else if len(d.NameList) == 1 { if v := fb.buildExpr(d.Values); v != nil { if c := ssaExtractConst(v); c != nil { fb.localConsts[d.NameList[0].Value] = c } } } } case *types.TypeDecl: if d.Name != nil { resolved := fb.resolveTypeAST(d.Type) if resolved != nil { fb.localTypes[d.Name.Value] = resolved } } } } func (fb *ssaFuncBuilder) evalLocalConstExpr(e syntax.Expr) (c types.ConstVal) { if e == nil { return nil } switch e := e.(type) { case *syntax.BasicLit: return evalBasicLitLocal(e) case *syntax.Name: if c, ok := fb.localConsts[e.Value]; ok && c != nil && c.val != nil { return c.val } return tcEvalConstExpr(e, fb.fn.Pkg.Pkg.Scope(), -1) case *syntax.Operation: if e.Y == nil { xr := fb.evalLocalConstExpr(e.X) if xr == nil { return nil } return evalUnaryLocal(e.Op, xr) } xr := fb.evalLocalConstExpr(e.X) yr := fb.evalLocalConstExpr(e.Y) if xr == nil || yr == nil { return nil } return evalBinaryLocal(e.Op, xr, yr) case *syntax.ParenExpr: return fb.evalLocalConstExpr(e.X) } return nil }