| package ssa |
| |
| // This file defines the SSA builder. |
| // |
| // The builder has two phases, CREATE and BUILD. In the CREATE |
| // phase, all packages are constructed and type-checked and |
| // definitions of all package members are created, method-sets are |
| // computed, and bridge methods are synthesized. The create phase |
| // proceeds in topological order over the import dependency graph, |
| // initiated by client calls to CreatePackage. |
| // |
| // In the BUILD phase, the Builder traverses the AST of each Go source |
| // function and generates SSA instructions for the function body. |
| // Within each package, building proceeds in a topological order over |
| // the intra-package symbol reference graph, whose roots are the set |
| // of package-level declarations in lexical order. The BUILD phases |
| // for distinct packages are independent and are executed in parallel. |
| // |
| // The Builder's and Program's indices (maps) are populated and |
| // mutated during the CREATE phase, but during the BUILD phase they |
| // remain constant. The sole exception is Prog.methodSets, which is |
| // protected by a dedicated mutex. |
| |
| // TODO(adonovan): |
| // - fix: support f(g()) where g has multiple result parameters. |
| |
| import ( |
| "fmt" |
| "go/ast" |
| "go/token" |
| "os" |
| "strconv" |
| "sync" |
| "sync/atomic" |
| |
| "code.google.com/p/go.exp/go/types" |
| ) |
| |
| var ( |
| varOk = &types.Var{Name: "ok", Type: tBool} |
| |
| // Type constants. |
| tBool = types.Typ[types.Bool] |
| tByte = types.Typ[types.Byte] |
| tFloat32 = types.Typ[types.Float32] |
| tFloat64 = types.Typ[types.Float64] |
| tComplex64 = types.Typ[types.Complex64] |
| tComplex128 = types.Typ[types.Complex128] |
| tInt = types.Typ[types.Int] |
| tInvalid = types.Typ[types.Invalid] |
| tUntypedNil = types.Typ[types.UntypedNil] |
| tRangeIter = &types.Basic{Name: "iter"} // the type of all "range" iterators |
| tEface = new(types.Interface) |
| |
| // The result type of a "select". |
| tSelect = &types.Result{Values: []*types.Var{ |
| {Name: "index", Type: tInt}, |
| {Name: "recv", Type: tInvalid}, |
| varOk, |
| }} |
| |
| // SSA Value constants. |
| vZero = intLiteral(0) |
| vOne = intLiteral(1) |
| vTrue = newLiteral(true, tBool) |
| vFalse = newLiteral(false, tBool) |
| ) |
| |
| // A Builder creates the SSA representation of a single program. |
| // Instances may be created using NewBuilder. |
| // |
| // The SSA Builder constructs a Program containing Package instances |
| // for packages of Go source code, loading, parsing and recursively |
| // constructing packages for all imported dependencies as well. |
| // |
| // If the UseGCImporter mode flag is specified, binary object files |
| // produced by the gc compiler will be loaded instead of source code |
| // for all imported packages. Such files supply only the types of |
| // package-level declarations and values of constants, but no code, so |
| // this mode will not yield a whole program. It is intended for |
| // analyses that perform intraprocedural analysis of a single package. |
| // |
| // A typical client will create a Builder with NewBuilder; call |
| // CreatePackage for the "root" package(s), e.g. main; then call |
| // BuildPackage on the same set of packages to construct SSA-form code |
| // for functions and methods. After that, the representation of the |
| // program (Builder.Prog) is complete and transitively closed, and the |
| // Builder object can be discarded to reclaim its memory. The |
| // client's analysis may then begin. |
| // |
| type Builder struct { |
| Prog *Program // the program being built |
| mode BuilderMode // set of mode bits |
| loader SourceLoader // the loader for imported source files |
| importErrs map[string]error // across-packages import cache of failures |
| packages map[*types.Package]*Package // SSA packages by types.Package |
| types map[ast.Expr]types.Type // inferred types of expressions |
| constants map[ast.Expr]*Literal // values of constant expressions |
| idents map[*ast.Ident]types.Object // canonical type objects of all named entities |
| globals map[types.Object]Value // all package-level funcs and vars, and universal built-ins |
| typechecker types.Context // the typechecker context (stateless) |
| } |
| |
| // BuilderMode is a bitmask of options for diagnostics and checking. |
| type BuilderMode uint |
| |
| const ( |
| LogPackages BuilderMode = 1 << iota // Dump package inventory to stderr |
| LogFunctions // Dump function SSA code to stderr |
| LogSource // Show source locations as SSA builder progresses |
| SanityCheckFunctions // Perform sanity checking of function bodies |
| UseGCImporter // Ignore SourceLoader; use gc-compiled object code for all imports |
| NaiveForm // Build naïve SSA form: don't replace local loads/stores with registers |
| BuildSerially // Build packages serially, not in parallel. |
| ) |
| |
| // NewBuilder creates and returns a new SSA builder. |
| // |
| // mode is a bitfield of options controlling verbosity, logging and |
| // additional sanity checks. |
| // |
| // loader is a SourceLoader function that finds, loads and parses Go |
| // source files for a given import path. (It is ignored if the mode |
| // bits include UseGCImporter.) |
| // |
| // errh is an optional error handler that is called for each error |
| // encountered during type checking; if nil, only the first type error |
| // will be returned, via the result of CreatePackage. |
| // |
| func NewBuilder(mode BuilderMode, loader SourceLoader, errh func(error)) *Builder { |
| b := &Builder{ |
| Prog: &Program{ |
| Files: token.NewFileSet(), |
| Packages: make(map[string]*Package), |
| Builtins: make(map[types.Object]*Builtin), |
| methodSets: make(map[types.Type]MethodSet), |
| concreteMethods: make(map[*types.Method]*Function), |
| mode: mode, |
| }, |
| mode: mode, |
| loader: loader, |
| constants: make(map[ast.Expr]*Literal), |
| globals: make(map[types.Object]Value), |
| idents: make(map[*ast.Ident]types.Object), |
| importErrs: make(map[string]error), |
| packages: make(map[*types.Package]*Package), |
| types: make(map[ast.Expr]types.Type), |
| } |
| |
| // TODO(adonovan): opt: record the Expr/Ident calls into |
| // constants/idents/types maps associated with the containing |
| // package so we can discard them once that package is built. |
| b.typechecker = types.Context{ |
| Error: errh, |
| Expr: func(x ast.Expr, typ types.Type, val interface{}) { |
| b.types[x] = typ |
| if val != nil { |
| b.constants[x] = newLiteral(val, typ) |
| } |
| }, |
| Ident: func(ident *ast.Ident, obj types.Object) { |
| // Invariants: |
| // - obj is non-nil. |
| // - isBlankIdent(ident) <=> obj.GetType()==nil |
| b.idents[ident] = obj |
| }, |
| Import: func(imports map[string]*types.Package, path string) (pkg *types.Package, err error) { |
| return b.doImport(imports, path) |
| }, |
| } |
| |
| // Create Values for built-in functions. |
| for _, obj := range types.Universe.Entries { |
| switch obj := obj.(type) { |
| case *types.Func: |
| v := &Builtin{obj} |
| b.globals[obj] = v |
| b.Prog.Builtins[obj] = v |
| } |
| } |
| return b |
| } |
| |
| // isPackageRef returns the identity of the object if sel is a |
| // package-qualified reference to a named const, var, func or type. |
| // Otherwise it returns nil. |
| // |
| // It's unfortunate that this is a method of builder, but even the |
| // small amount of name resolution required here is no longer |
| // available on the AST. |
| // |
| func (b *Builder) isPackageRef(sel *ast.SelectorExpr) types.Object { |
| if id, ok := sel.X.(*ast.Ident); ok { |
| if obj := b.obj(id); objKind(obj) == ast.Pkg { |
| return obj.(*types.Package).Scope.Lookup(sel.Sel.Name) |
| } |
| } |
| return nil |
| } |
| |
| // isType returns true iff expression e denotes a type. |
| // |
| // It's unfortunate that this is a method of builder, but even the |
| // small amount of name resolution required here is no longer |
| // available on the AST. |
| // |
| func (b *Builder) isType(e ast.Expr) bool { |
| switch e := e.(type) { |
| case *ast.SelectorExpr: // pkg.Type |
| if obj := b.isPackageRef(e); obj != nil { |
| return objKind(obj) == ast.Typ |
| } |
| case *ast.StarExpr: // *T |
| return b.isType(e.X) |
| case *ast.Ident: |
| return objKind(b.obj(e)) == ast.Typ |
| case *ast.ArrayType, *ast.StructType, *ast.FuncType, *ast.InterfaceType, *ast.MapType, *ast.ChanType: |
| return true |
| case *ast.ParenExpr: |
| return b.isType(e.X) |
| } |
| return false |
| } |
| |
| // lookup returns the package-level *Function or *Global (or universal |
| // *Builtin) for the named object obj. |
| // |
| // Intra-package references are edges in the initialization dependency |
| // graph. If the result v is a Function or Global belonging to |
| // 'from', the package on whose behalf this lookup occurs, then lookup |
| // emits initialization code into from.Init if not already done. |
| // |
| func (b *Builder) lookup(from *Package, obj types.Object) (v Value, ok bool) { |
| v, ok = b.globals[obj] |
| if ok { |
| switch v := v.(type) { |
| case *Function: |
| if from == v.Pkg { |
| b.buildFunction(v) |
| } |
| case *Global: |
| if from == v.Pkg { |
| b.buildGlobal(v, obj) |
| } |
| } |
| } |
| return |
| } |
| |
| // exprType(e) returns the type of expression e. |
| // Callers should not access b.types directly since it may lie if |
| // called from within a typeswitch. |
| // |
| func (b *Builder) exprType(e ast.Expr) types.Type { |
| // For Ident, b.types may be more specific than |
| // b.obj(id.(*ast.Ident)).GetType(), |
| // e.g. in the case of typeswitch. |
| if t, ok := b.types[e]; ok { |
| return t |
| } |
| // The typechecker doesn't notify us of all Idents, |
| // e.g. s.Key and s.Value in a RangeStmt. |
| // So we have this fallback. |
| // TODO(gri): Is this a typechecker bug? If so, eliminate |
| // this case and panic. |
| if id, ok := e.(*ast.Ident); ok { |
| return b.obj(id).GetType() |
| } |
| panic("no type for expression") |
| } |
| |
| // obj returns the typechecker object denoted by the specified |
| // identifier. Panic ensues if there is none. |
| // |
| func (b *Builder) obj(id *ast.Ident) types.Object { |
| if obj, ok := b.idents[id]; ok { |
| return obj |
| } |
| panic(fmt.Sprintf("no types.Object for ast.Ident %s @ %p", id.Name, id)) |
| } |
| |
| // cond emits to fn code to evaluate boolean condition e and jump |
| // to t or f depending on its value, performing various simplifications. |
| // |
| // Postcondition: fn.currentBlock is nil. |
| // |
| func (b *Builder) cond(fn *Function, e ast.Expr, t, f *BasicBlock) { |
| switch e := e.(type) { |
| case *ast.ParenExpr: |
| b.cond(fn, e.X, t, f) |
| return |
| |
| case *ast.BinaryExpr: |
| switch e.Op { |
| case token.LAND: |
| ltrue := fn.newBasicBlock("cond.true") |
| b.cond(fn, e.X, ltrue, f) |
| fn.currentBlock = ltrue |
| b.cond(fn, e.Y, t, f) |
| return |
| |
| case token.LOR: |
| lfalse := fn.newBasicBlock("cond.false") |
| b.cond(fn, e.X, t, lfalse) |
| fn.currentBlock = lfalse |
| b.cond(fn, e.Y, t, f) |
| return |
| } |
| |
| case *ast.UnaryExpr: |
| if e.Op == token.NOT { |
| b.cond(fn, e.X, f, t) |
| return |
| } |
| } |
| |
| switch cond := b.expr(fn, e).(type) { |
| case *Literal: |
| // Dispatch constant conditions statically. |
| if cond.Value.(bool) { |
| emitJump(fn, t) |
| } else { |
| emitJump(fn, f) |
| } |
| default: |
| emitIf(fn, cond, t, f) |
| } |
| } |
| |
| // logicalBinop emits code to fn to evaluate e, a &&- or |
| // ||-expression whose reified boolean value is wanted. |
| // The value is returned. |
| // |
| func (b *Builder) logicalBinop(fn *Function, e *ast.BinaryExpr) Value { |
| rhs := fn.newBasicBlock("binop.rhs") |
| done := fn.newBasicBlock("binop.done") |
| |
| var short Value // value of the short-circuit path |
| switch e.Op { |
| case token.LAND: |
| b.cond(fn, e.X, rhs, done) |
| short = vFalse |
| case token.LOR: |
| b.cond(fn, e.X, done, rhs) |
| short = vTrue |
| } |
| |
| // Is rhs unreachable? |
| if rhs.Preds == nil { |
| // Simplify false&&y to false, true||y to true. |
| fn.currentBlock = done |
| return short |
| } |
| |
| // Is done unreachable? |
| if done.Preds == nil { |
| // Simplify true&&y (or false||y) to y. |
| fn.currentBlock = rhs |
| return b.expr(fn, e.Y) |
| } |
| |
| // All edges from e.X to done carry the short-circuit value. |
| var edges []Value |
| for _ = range done.Preds { |
| edges = append(edges, short) |
| } |
| |
| // The edge from e.Y to done carries the value of e.Y. |
| fn.currentBlock = rhs |
| edges = append(edges, b.expr(fn, e.Y)) |
| emitJump(fn, done) |
| fn.currentBlock = done |
| |
| // TODO(adonovan): do we need emitConv on each edge? |
| // Test with named boolean types. |
| phi := &Phi{Edges: edges, Comment: e.Op.String()} |
| phi.Type_ = phi.Edges[0].Type() |
| return done.emit(phi) |
| } |
| |
| // exprN lowers a multi-result expression e to SSA form, emitting code |
| // to fn and returning a single Value whose type is a *types.Results |
| // (tuple). The caller must access the components via Extract. |
| // |
| // Multi-result expressions include CallExprs in a multi-value |
| // assignment or return statement, and "value,ok" uses of |
| // TypeAssertExpr, IndexExpr (when X is a map), and UnaryExpr (when Op |
| // is token.ARROW). |
| // |
| func (b *Builder) exprN(fn *Function, e ast.Expr) Value { |
| var typ types.Type |
| var tuple Value |
| switch e := e.(type) { |
| case *ast.ParenExpr: |
| return b.exprN(fn, e.X) |
| |
| case *ast.CallExpr: |
| // Currently, no built-in function nor type conversion |
| // has multiple results, so we can avoid some of the |
| // cases for single-valued CallExpr. |
| var c Call |
| b.setCall(fn, e, &c.CallCommon) |
| c.Type_ = b.exprType(e) |
| return fn.emit(&c) |
| |
| case *ast.IndexExpr: |
| mapt := underlyingType(b.exprType(e.X)).(*types.Map) |
| typ = mapt.Elt |
| tuple = fn.emit(&Lookup{ |
| X: b.expr(fn, e.X), |
| Index: emitConv(fn, b.expr(fn, e.Index), mapt.Key), |
| CommaOk: true, |
| }) |
| |
| case *ast.TypeAssertExpr: |
| typ = b.exprType(e) |
| tuple = fn.emit(&TypeAssert{ |
| X: b.expr(fn, e.X), |
| AssertedType: typ, |
| CommaOk: true, |
| }) |
| |
| case *ast.UnaryExpr: // must be receive <- |
| typ = underlyingType(b.exprType(e.X)).(*types.Chan).Elt |
| tuple = fn.emit(&UnOp{ |
| Op: token.ARROW, |
| X: b.expr(fn, e.X), |
| CommaOk: true, |
| }) |
| |
| default: |
| panic(fmt.Sprintf("unexpected exprN: %T", e)) |
| } |
| |
| // The typechecker sets the type of the expression to just the |
| // asserted type in the "value, ok" form, not to *types.Result |
| // (though it includes the valueOk operand in its error messages). |
| |
| tuple.(interface { |
| setType(types.Type) |
| }).setType(&types.Result{Values: []*types.Var{ |
| {Name: "value", Type: typ}, |
| varOk, |
| }}) |
| return tuple |
| } |
| |
| // builtin emits to fn SSA instructions to implement a call to the |
| // built-in function called name with the specified arguments |
| // and return type. It returns the value defined by the result. |
| // |
| // The result is nil if no special handling was required; in this case |
| // the caller should treat this like an ordinary library function |
| // call. |
| // |
| func (b *Builder) builtin(fn *Function, name string, args []ast.Expr, typ types.Type) Value { |
| switch name { |
| case "make": |
| switch underlyingType(typ).(type) { |
| case *types.Slice: |
| n := b.expr(fn, args[1]) |
| m := n |
| if len(args) == 3 { |
| m = b.expr(fn, args[2]) |
| } |
| v := &MakeSlice{ |
| Len: n, |
| Cap: m, |
| } |
| v.setType(typ) |
| return fn.emit(v) |
| |
| case *types.Map: |
| var res Value |
| if len(args) == 2 { |
| res = b.expr(fn, args[1]) |
| } |
| v := &MakeMap{Reserve: res} |
| v.setType(typ) |
| return fn.emit(v) |
| |
| case *types.Chan: |
| var sz Value = vZero |
| if len(args) == 2 { |
| sz = b.expr(fn, args[1]) |
| } |
| v := &MakeChan{Size: sz} |
| v.setType(typ) |
| return fn.emit(v) |
| } |
| |
| case "new": |
| return emitNew(fn, indirectType(underlyingType(typ))) |
| |
| case "len", "cap": |
| // Special case: len or cap of an array or *array is |
| // based on the type, not the value which may be nil. |
| // We must still evaluate the value, though. (If it |
| // was side-effect free, the whole call would have |
| // been constant-folded.) |
| t := underlyingType(deref(b.exprType(args[0]))) |
| if at, ok := t.(*types.Array); ok { |
| b.expr(fn, args[0]) // for effects only |
| return intLiteral(at.Len) |
| } |
| // Otherwise treat as normal. |
| |
| case "panic": |
| fn.emit(&Panic{X: emitConv(fn, b.expr(fn, args[0]), tEface)}) |
| fn.currentBlock = fn.newBasicBlock("unreachable") |
| return vFalse // any non-nil Value will do |
| } |
| return nil // treat all others as a regular function call |
| } |
| |
| // selector evaluates the selector expression e and returns its value, |
| // or if wantAddr is true, its address, in which case escaping |
| // indicates whether the caller intends to use the resulting pointer |
| // in a potentially escaping way. |
| // |
| func (b *Builder) selector(fn *Function, e *ast.SelectorExpr, wantAddr, escaping bool) Value { |
| id := makeId(e.Sel.Name, fn.Pkg.Types) |
| st := underlyingType(deref(b.exprType(e.X))).(*types.Struct) |
| index := -1 |
| for i, f := range st.Fields { |
| if IdFromQualifiedName(f.QualifiedName) == id { |
| index = i |
| break |
| } |
| } |
| var path *anonFieldPath |
| if index == -1 { |
| // Not a named field. Use breadth-first algorithm. |
| path, index = findPromotedField(st, id) |
| if path == nil { |
| panic("field not found, even with promotion: " + e.Sel.Name) |
| } |
| } |
| fieldType := b.exprType(e) |
| if wantAddr { |
| return b.fieldAddr(fn, e.X, path, index, fieldType, escaping) |
| } |
| return b.fieldExpr(fn, e.X, path, index, fieldType) |
| } |
| |
| // fieldAddr evaluates the base expression (a struct or *struct), |
| // applies to it any implicit field selections from path, and then |
| // selects the field #index of type fieldType. |
| // Its address is returned. |
| // |
| // (fieldType can be derived from base+index.) |
| // |
| func (b *Builder) fieldAddr(fn *Function, base ast.Expr, path *anonFieldPath, index int, fieldType types.Type, escaping bool) Value { |
| var x Value |
| if path != nil { |
| switch underlyingType(path.field.Type).(type) { |
| case *types.Struct: |
| x = b.fieldAddr(fn, base, path.tail, path.index, path.field.Type, escaping) |
| case *types.Pointer: |
| x = b.fieldExpr(fn, base, path.tail, path.index, path.field.Type) |
| } |
| } else { |
| switch underlyingType(b.exprType(base)).(type) { |
| case *types.Struct: |
| x = b.addr(fn, base, escaping).(address).addr |
| case *types.Pointer: |
| x = b.expr(fn, base) |
| } |
| } |
| v := &FieldAddr{ |
| X: x, |
| Field: index, |
| } |
| v.setType(pointer(fieldType)) |
| return fn.emit(v) |
| } |
| |
| // fieldExpr evaluates the base expression (a struct or *struct), |
| // applies to it any implicit field selections from path, and then |
| // selects the field #index of type fieldType. |
| // Its value is returned. |
| // |
| // (fieldType can be derived from base+index.) |
| // |
| func (b *Builder) fieldExpr(fn *Function, base ast.Expr, path *anonFieldPath, index int, fieldType types.Type) Value { |
| var x Value |
| if path != nil { |
| x = b.fieldExpr(fn, base, path.tail, path.index, path.field.Type) |
| } else { |
| x = b.expr(fn, base) |
| } |
| switch underlyingType(x.Type()).(type) { |
| case *types.Struct: |
| v := &Field{ |
| X: x, |
| Field: index, |
| } |
| v.setType(fieldType) |
| return fn.emit(v) |
| |
| case *types.Pointer: // *struct |
| v := &FieldAddr{ |
| X: x, |
| Field: index, |
| } |
| v.setType(pointer(fieldType)) |
| return emitLoad(fn, fn.emit(v)) |
| } |
| panic("unreachable") |
| } |
| |
| // addr lowers a single-result addressable expression e to SSA form, |
| // emitting code to fn and returning the location (an lvalue) defined |
| // by the expression. |
| // |
| // If escaping is true, addr marks the base variable of the |
| // addressable expression e as being a potentially escaping pointer |
| // value. For example, in this code: |
| // |
| // a := A{ |
| // b: [1]B{B{c: 1}} |
| // } |
| // return &a.b[0].c |
| // |
| // the application of & causes a.b[0].c to have its address taken, |
| // which means that ultimately the local variable a must be |
| // heap-allocated. This is a simple but very conservative escape |
| // analysis. |
| // |
| // Operations forming potentially escaping pointers include: |
| // - &x, including when implicit in method call or composite literals. |
| // - a[:] iff a is an array (not *array) |
| // - references to variables in lexically enclosing functions. |
| // |
| func (b *Builder) addr(fn *Function, e ast.Expr, escaping bool) lvalue { |
| switch e := e.(type) { |
| case *ast.Ident: |
| obj := b.obj(e) |
| v, ok := b.lookup(fn.Pkg, obj) // var (address) |
| if !ok { |
| v = fn.lookup(obj, escaping) |
| } |
| return address{v} |
| |
| case *ast.CompositeLit: |
| t := deref(b.exprType(e)) |
| var v Value |
| if escaping { |
| v = emitNew(fn, t) |
| } else { |
| v = fn.addLocal(t) |
| } |
| b.compLit(fn, v, e, t) // initialize in place |
| return address{v} |
| |
| case *ast.ParenExpr: |
| return b.addr(fn, e.X, escaping) |
| |
| case *ast.SelectorExpr: |
| // p.M where p is a package. |
| if obj := b.isPackageRef(e); obj != nil { |
| if v, ok := b.lookup(fn.Pkg, obj); ok { |
| return address{v} |
| } |
| panic("undefined package-qualified name: " + obj.GetName()) |
| } |
| |
| // e.f where e is an expression. |
| return address{b.selector(fn, e, true, escaping)} |
| |
| case *ast.IndexExpr: |
| var x Value |
| var et types.Type |
| switch t := underlyingType(b.exprType(e.X)).(type) { |
| case *types.Array: |
| x = b.addr(fn, e.X, escaping).(address).addr |
| et = pointer(t.Elt) |
| case *types.Pointer: // *array |
| x = b.expr(fn, e.X) |
| et = pointer(underlyingType(t.Base).(*types.Array).Elt) |
| case *types.Slice: |
| x = b.expr(fn, e.X) |
| et = pointer(t.Elt) |
| case *types.Map: |
| return &element{ |
| m: b.expr(fn, e.X), |
| k: emitConv(fn, b.expr(fn, e.Index), t.Key), |
| t: t.Elt, |
| } |
| default: |
| panic("unexpected container type in IndexExpr: " + t.String()) |
| } |
| v := &IndexAddr{ |
| X: x, |
| Index: emitConv(fn, b.expr(fn, e.Index), tInt), |
| } |
| v.setType(et) |
| return address{fn.emit(v)} |
| |
| case *ast.StarExpr: |
| return address{b.expr(fn, e.X)} |
| } |
| |
| panic(fmt.Sprintf("unexpected address expression: %T", e)) |
| } |
| |
| // exprInPlace emits to fn code to initialize the lvalue loc with the |
| // value of expression e. |
| // |
| // typ is the type of the lvalue, which may be provided by the caller |
| // since it is sometimes only an inherited attribute (e.g. within in |
| // composite literals). |
| // |
| // This is equivalent to loc.store(fn, b.expr(fn, e)) but may |
| // generate better code in some cases, e.g. for composite literals |
| // in an addressable location. |
| // |
| func (b *Builder) exprInPlace(fn *Function, loc lvalue, e ast.Expr) { |
| if addr, ok := loc.(address); ok { |
| if e, ok := e.(*ast.CompositeLit); ok { |
| typ := addr.typ() |
| switch underlyingType(typ).(type) { |
| case *types.Pointer: // implicit & -- possibly escaping |
| ptr := b.addr(fn, e, true).(address).addr |
| addr.store(fn, ptr) // copy address |
| return |
| |
| case *types.Interface: |
| // e.g. var x interface{} = T{...} |
| // Can't in-place initialize an interface value. |
| // Fall back to copying. |
| |
| default: |
| b.compLit(fn, addr.addr, e, typ) // in place |
| return |
| } |
| } |
| } |
| loc.store(fn, b.expr(fn, e)) // copy value |
| } |
| |
| // expr lowers a single-result expression e to SSA form, emitting code |
| // to fn and returning the Value defined by the expression. |
| // |
| func (b *Builder) expr(fn *Function, e ast.Expr) Value { |
| if lit := b.constants[e]; lit != nil { |
| return lit |
| } |
| |
| switch e := e.(type) { |
| case *ast.BasicLit: |
| panic("non-constant BasicLit") // unreachable |
| |
| case *ast.FuncLit: |
| posn := b.Prog.Files.Position(e.Type.Func) |
| fn2 := &Function{ |
| Name_: fmt.Sprintf("func@%d.%d", posn.Line, posn.Column), |
| Signature: underlyingType(b.exprType(e.Type)).(*types.Signature), |
| Pos: e.Type.Func, |
| Enclosing: fn, |
| Pkg: fn.Pkg, |
| Prog: b.Prog, |
| syntax: &funcSyntax{ |
| paramFields: e.Type.Params, |
| resultFields: e.Type.Results, |
| body: e.Body, |
| }, |
| } |
| fn.Pkg.AnonFuncs = append(fn.Pkg.AnonFuncs, fn2) |
| b.buildFunction(fn2) |
| if fn2.FreeVars == nil { |
| return fn2 |
| } |
| v := &MakeClosure{Fn: fn2} |
| v.setType(b.exprType(e)) |
| for _, fv := range fn2.FreeVars { |
| v.Bindings = append(v.Bindings, fv.Outer) |
| } |
| return fn.emit(v) |
| |
| case *ast.ParenExpr: |
| return b.expr(fn, e.X) |
| |
| case *ast.TypeAssertExpr: // single-result form only |
| v := &TypeAssert{ |
| X: b.expr(fn, e.X), |
| AssertedType: b.exprType(e), |
| } |
| v.setType(v.AssertedType) |
| return fn.emit(v) |
| |
| case *ast.CallExpr: |
| typ := b.exprType(e) |
| if b.isType(e.Fun) { |
| // Type conversion, e.g. string(x) or big.Int(x) |
| return emitConv(fn, b.expr(fn, e.Args[0]), typ) |
| } |
| // Call to "intrinsic" built-ins, e.g. new, make, panic. |
| if id, ok := e.Fun.(*ast.Ident); ok { |
| obj := b.obj(id) |
| if _, ok := fn.Prog.Builtins[obj]; ok { |
| if v := b.builtin(fn, id.Name, e.Args, typ); v != nil { |
| return v |
| } |
| } |
| } |
| // Regular function call. |
| var v Call |
| b.setCall(fn, e, &v.CallCommon) |
| v.setType(typ) |
| return fn.emit(&v) |
| |
| case *ast.UnaryExpr: |
| switch e.Op { |
| case token.AND: // &X --- potentially escaping. |
| return b.addr(fn, e.X, true).(address).addr |
| case token.ADD: |
| return b.expr(fn, e.X) |
| case token.NOT, token.ARROW, token.SUB, token.XOR: // ! <- - ^ |
| v := &UnOp{ |
| Op: e.Op, |
| X: b.expr(fn, e.X), |
| } |
| v.setType(b.exprType(e)) |
| return fn.emit(v) |
| default: |
| panic(e.Op) |
| } |
| |
| case *ast.BinaryExpr: |
| switch e.Op { |
| case token.LAND, token.LOR: |
| return b.logicalBinop(fn, e) |
| case token.SHL, token.SHR: |
| fallthrough |
| case token.ADD, token.SUB, token.MUL, token.QUO, token.REM, token.AND, token.OR, token.XOR, token.AND_NOT: |
| return emitArith(fn, e.Op, b.expr(fn, e.X), b.expr(fn, e.Y), b.exprType(e)) |
| |
| case token.EQL, token.NEQ, token.GTR, token.LSS, token.LEQ, token.GEQ: |
| return emitCompare(fn, e.Op, b.expr(fn, e.X), b.expr(fn, e.Y)) |
| default: |
| panic("illegal op in BinaryExpr: " + e.Op.String()) |
| } |
| |
| case *ast.SliceExpr: |
| var low, high Value |
| var x Value |
| switch underlyingType(b.exprType(e.X)).(type) { |
| case *types.Array: |
| // Potentially escaping. |
| x = b.addr(fn, e.X, true).(address).addr |
| case *types.Basic, *types.Slice, *types.Pointer: // *array |
| x = b.expr(fn, e.X) |
| default: |
| unreachable() |
| } |
| if e.High != nil { |
| high = b.expr(fn, e.High) |
| } |
| if e.Low != nil { |
| low = b.expr(fn, e.Low) |
| } |
| v := &Slice{ |
| X: x, |
| Low: low, |
| High: high, |
| } |
| v.setType(b.exprType(e)) |
| return fn.emit(v) |
| |
| case *ast.Ident: |
| obj := b.obj(e) |
| // Global or universal? |
| if v, ok := b.lookup(fn.Pkg, obj); ok { |
| if objKind(obj) == ast.Var { |
| v = emitLoad(fn, v) // var (address) |
| } |
| return v |
| } |
| // Local? |
| return emitLoad(fn, fn.lookup(obj, false)) // var (address) |
| |
| case *ast.SelectorExpr: |
| // p.M where p is a package. |
| if obj := b.isPackageRef(e); obj != nil { |
| return b.expr(fn, e.Sel) |
| } |
| |
| // (*T).f or T.f, the method f from the method-set of type T. |
| if b.isType(e.X) { |
| id := makeId(e.Sel.Name, fn.Pkg.Types) |
| typ := b.exprType(e.X) |
| if m := b.Prog.MethodSet(typ)[id]; m != nil { |
| return m |
| } |
| |
| // T must be an interface; return method thunk. |
| return makeImethodThunk(b.Prog, typ, id) |
| } |
| |
| // e.f where e is an expression. |
| return b.selector(fn, e, false, false) |
| |
| case *ast.IndexExpr: |
| switch t := underlyingType(b.exprType(e.X)).(type) { |
| case *types.Array: |
| // Non-addressable array (in a register). |
| v := &Index{ |
| X: b.expr(fn, e.X), |
| Index: emitConv(fn, b.expr(fn, e.Index), tInt), |
| } |
| v.setType(t.Elt) |
| return fn.emit(v) |
| |
| case *types.Map: |
| // Maps are not addressable. |
| mapt := underlyingType(b.exprType(e.X)).(*types.Map) |
| v := &Lookup{ |
| X: b.expr(fn, e.X), |
| Index: emitConv(fn, b.expr(fn, e.Index), mapt.Key), |
| } |
| v.setType(mapt.Elt) |
| return fn.emit(v) |
| |
| case *types.Basic: // => string |
| // Strings are not addressable. |
| v := &Lookup{ |
| X: b.expr(fn, e.X), |
| Index: b.expr(fn, e.Index), |
| } |
| v.setType(tByte) |
| return fn.emit(v) |
| |
| case *types.Slice, *types.Pointer: // *array |
| // Addressable slice/array; use IndexAddr and Load. |
| return b.addr(fn, e, false).load(fn) |
| |
| default: |
| panic("unexpected container type in IndexExpr: " + t.String()) |
| } |
| |
| case *ast.CompositeLit, *ast.StarExpr: |
| // Addressable types (lvalues) |
| return b.addr(fn, e, false).load(fn) |
| } |
| |
| panic(fmt.Sprintf("unexpected expr: %T", e)) |
| } |
| |
| // stmtList emits to fn code for all statements in list. |
| func (b *Builder) stmtList(fn *Function, list []ast.Stmt) { |
| for _, s := range list { |
| b.stmt(fn, s) |
| } |
| } |
| |
| // setCallFunc populates the function parts of a CallCommon structure |
| // (Func, Method, Recv, Args[0]) based on the kind of invocation |
| // occurring in e. |
| // |
| func (b *Builder) setCallFunc(fn *Function, e *ast.CallExpr, c *CallCommon) { |
| c.Pos = e.Lparen |
| |
| // Is the call of the form x.f()? |
| sel, ok := noparens(e.Fun).(*ast.SelectorExpr) |
| |
| // Case 0: e.Fun evaluates normally to a function. |
| if !ok { |
| c.Func = b.expr(fn, e.Fun) |
| return |
| } |
| |
| // Case 1: call of form x.F() where x is a package name. |
| if obj := b.isPackageRef(sel); obj != nil { |
| // This is a specialization of expr(ast.Ident(obj)). |
| if v, ok := b.lookup(fn.Pkg, obj); ok { |
| if _, ok := v.(*Function); !ok { |
| v = emitLoad(fn, v) // var (address) |
| } |
| c.Func = v |
| return |
| } |
| panic("undefined package-qualified name: " + obj.GetName()) |
| } |
| |
| // Case 2a: X.f() or (*X).f(): a statically dipatched call to |
| // the method f in the method-set of X or *X. X may be |
| // an interface. Treat like case 0. |
| // TODO(adonovan): opt: inline expr() here, to make the call static |
| // and to avoid generation of a stub for an interface method. |
| if b.isType(sel.X) { |
| c.Func = b.expr(fn, e.Fun) |
| return |
| } |
| |
| // Let X be the type of x. |
| typ := b.exprType(sel.X) |
| |
| // Case 2: x.f(): a statically dispatched call to a method |
| // from the method-set of X or perhaps *X (if x is addressable |
| // but not a pointer). |
| id := makeId(sel.Sel.Name, fn.Pkg.Types) |
| // Consult method-set of X. |
| if m := b.Prog.MethodSet(typ)[id]; m != nil { |
| var recv Value |
| aptr := isPointer(typ) |
| fptr := isPointer(m.Signature.Recv.Type) |
| if aptr == fptr { |
| // Actual's and formal's "pointerness" match. |
| recv = b.expr(fn, sel.X) |
| } else { |
| // Actual is a pointer, formal is not. |
| // Load a copy. |
| recv = emitLoad(fn, b.expr(fn, sel.X)) |
| } |
| c.Func = m |
| c.Args = append(c.Args, recv) |
| return |
| } |
| if !isPointer(typ) { |
| // Consult method-set of *X. |
| if m := b.Prog.MethodSet(pointer(typ))[id]; m != nil { |
| // A method found only in MS(*X) must have a |
| // pointer formal receiver; but the actual |
| // value is not a pointer. |
| // Implicit & -- possibly escaping. |
| recv := b.addr(fn, sel.X, true).(address).addr |
| c.Func = m |
| c.Args = append(c.Args, recv) |
| return |
| } |
| } |
| |
| switch t := underlyingType(typ).(type) { |
| case *types.Struct, *types.Pointer: |
| // Case 3: x.f() where x.f is a function value in a |
| // struct field f; not a method call. f is a 'var' |
| // (of function type) in the Fields of types.Struct X. |
| // Treat like case 0. |
| c.Func = b.expr(fn, e.Fun) |
| |
| case *types.Interface: |
| // Case 4: x.f() where a dynamically dispatched call |
| // to an interface method f. f is a 'func' object in |
| // the Methods of types.Interface X |
| c.Method, _ = methodIndex(t, t.Methods, id) |
| c.Recv = b.expr(fn, sel.X) |
| |
| default: |
| panic(fmt.Sprintf("illegal (%s).%s() call; X:%T", t, sel.Sel.Name, sel.X)) |
| } |
| } |
| |
| // setCall emits to fn code to evaluate all the parameters of a function |
| // call e, and populates *c with those values. |
| // |
| func (b *Builder) setCall(fn *Function, e *ast.CallExpr, c *CallCommon) { |
| // First deal with the f(...) part. |
| b.setCallFunc(fn, e, c) |
| |
| // Argument passing. There are 4 cases to consider: |
| // 1. Ordinary call to non-variadic function. |
| // All args are treated in the usual manner. |
| // 2. Ordinary call to variadic function, f(a, b, v1, ..., vn). |
| // Caller constructs a slice from the varargs arguments v_i. |
| // 3. Ellipsis call f(a, b, rest...) to variadic function. |
| // 'rest' is already a slice; all args treated in the usual manner. |
| // 4. f(g()) where g has >1 return parameters. f may also be variadic. |
| // TODO(adonovan): fix: implement. |
| |
| var args, varargs []ast.Expr = e.Args, nil |
| c.HasEllipsis = e.Ellipsis != 0 |
| |
| // Determine which suffix (if any) of Args is a varargs slice. |
| var vt types.Type // element type of the variadic slice |
| switch typ := underlyingType(b.exprType(e.Fun)).(type) { |
| case *types.Signature: |
| np := len(typ.Params) |
| if !c.HasEllipsis { |
| if typ.IsVariadic { |
| // case 2: ordinary call of variadic function. |
| vt = typ.Params[np-1].Type |
| args, varargs = args[:np-1], args[np-1:] |
| } |
| |
| // TODO(adonovan): fix: not disjoint with case above! |
| // Consider f(...int) called with g() (int,int) |
| // Incomplete. |
| if len(args) == 1 && (np > 1 || typ.IsVariadic) { |
| if res, ok := b.exprType(args[0]).(*types.Result); ok { |
| res = res |
| // case 4: f(g()) where g is a multi. |
| // TODO(adonovan): generate: |
| // tuple := g() |
| // args = [extract 0, ... extract n] |
| // f(args) |
| } |
| } |
| } |
| |
| // Non-varargs. |
| for i, arg := range args { |
| // TODO(gri): annoyingly Signature.Params |
| // doesn't reflect the slice type for a final |
| // ...T param. |
| t := typ.Params[i].Type |
| if typ.IsVariadic && c.HasEllipsis && i == len(args)-1 { |
| t = &types.Slice{Elt: t} |
| } |
| v := emitConv(fn, b.expr(fn, arg), t) |
| c.Args = append(c.Args, v) |
| } |
| |
| default: |
| // builtin: ad-hoc typing rules are required for all |
| // variadic (append, print, println) and polymorphic |
| // (append, copy, delete, close) built-ins. |
| // |
| // TODO(adonovan): it would so much cleaner if the |
| // typechecker would ascribe a unique Signature type |
| // to each e.Fun expression calling a built-in. |
| // Then we could use the same logic as above. |
| // |
| // TODO(adonovan): fix: support case 4. But know that the |
| // other tools don't support it for built-ins yet |
| // (http://code.google.com/p/go/issues/detail?id=4573), |
| // so there's no rush. |
| |
| var bptypes []types.Type // formal parameter types of builtins |
| switch builtin := e.Fun.(*ast.Ident).Name; builtin { |
| case "append": |
| // Infer arg types from result type: |
| rt := b.exprType(e) |
| bptypes = append(bptypes, rt) |
| if c.HasEllipsis { |
| // 2-arg '...' call form. No conversions. |
| // append([]T, []T) []T |
| // append([]byte, string) []byte |
| } else { |
| // variadic call form. |
| // append([]T, ...T) []T |
| args, varargs = args[:1], args[1:] |
| vt = underlyingType(rt).(*types.Slice).Elt |
| } |
| case "close": |
| // no conv |
| case "copy": |
| // copy([]T, []T) int |
| // Infer arg types from each other. Sleazy. |
| if st, ok := underlyingType(b.exprType(args[0])).(*types.Slice); ok { |
| bptypes = append(bptypes, st, st) |
| } else if st, ok := underlyingType(b.exprType(args[1])).(*types.Slice); ok { |
| bptypes = append(bptypes, st, st) |
| } else { |
| panic("cannot infer types in call to copy()") |
| } |
| case "delete": |
| // delete(map[K]V, K) |
| tkey := underlyingType(b.exprType(args[0])).(*types.Map).Key |
| bptypes = append(bptypes, nil) // map: no conv |
| bptypes = append(bptypes, tkey) // key |
| case "print", "println": // print{,ln}(any, ...any) |
| vt = tEface // variadic |
| if !c.HasEllipsis { |
| args, varargs = args[:1], args[1:] |
| } |
| case "len": |
| // no conv |
| case "cap": |
| // no conv |
| case "real", "imag": |
| // Reverse conversion to "complex" case below. |
| // Typechecker, help us out. :( |
| var argType types.Type |
| switch b.exprType(e).(*types.Basic).Kind { |
| case types.UntypedFloat: |
| argType = types.Typ[types.UntypedComplex] |
| case types.Float64: |
| argType = tComplex128 |
| case types.Float32: |
| argType = tComplex64 |
| default: |
| unreachable() |
| } |
| bptypes = append(bptypes, argType, argType) |
| case "complex": |
| // Typechecker, help us out. :( |
| var argType types.Type |
| switch b.exprType(e).(*types.Basic).Kind { |
| case types.UntypedComplex: |
| argType = types.Typ[types.UntypedFloat] |
| case types.Complex128: |
| argType = tFloat64 |
| case types.Complex64: |
| argType = tFloat32 |
| default: |
| unreachable() |
| } |
| bptypes = append(bptypes, argType, argType) |
| case "panic": |
| bptypes = append(bptypes, tEface) |
| case "recover": |
| // no-op |
| default: |
| panic("unknown builtin: " + builtin) |
| } |
| |
| // Non-varargs. |
| for i, arg := range args { |
| v := b.expr(fn, arg) |
| if i < len(bptypes) && bptypes[i] != nil { |
| v = emitConv(fn, v, bptypes[i]) |
| } |
| c.Args = append(c.Args, v) |
| } |
| } |
| |
| // Common code for varargs. |
| if vt != nil { // case 2 |
| at := &types.Array{ |
| Elt: vt, |
| Len: int64(len(varargs)), |
| } |
| a := emitNew(fn, at) |
| for i, arg := range varargs { |
| iaddr := &IndexAddr{ |
| X: a, |
| Index: intLiteral(int64(i)), |
| } |
| iaddr.setType(pointer(vt)) |
| fn.emit(iaddr) |
| emitStore(fn, iaddr, b.expr(fn, arg)) |
| } |
| s := &Slice{X: a} |
| s.setType(&types.Slice{Elt: vt}) |
| c.Args = append(c.Args, fn.emit(s)) |
| } |
| } |
| |
| // assignOp emits to fn code to perform loc += incr or loc -= incr. |
| func (b *Builder) assignOp(fn *Function, loc lvalue, incr Value, op token.Token) { |
| oldv := loc.load(fn) |
| loc.store(fn, emitArith(fn, op, oldv, emitConv(fn, incr, oldv.Type()), loc.typ())) |
| } |
| |
| // buildGlobal emits code to the g.Pkg.Init function for the variable |
| // definition(s) of g. Effects occur out of lexical order; see |
| // explanation at globalValueSpec. |
| // Precondition: g == b.globals[obj] |
| // |
| func (b *Builder) buildGlobal(g *Global, obj types.Object) { |
| spec := g.spec |
| if spec == nil { |
| return // already built (or in progress) |
| } |
| b.globalValueSpec(g.Pkg.Init, spec, g, obj) |
| } |
| |
| // globalValueSpec emits to init code to define one or all of the vars |
| // in the package-level ValueSpec spec. |
| // |
| // It implements the build phase for a ValueSpec, ensuring that all |
| // vars are initialized if not already visited by buildGlobal during |
| // the reference graph traversal. |
| // |
| // This function may be called in two modes: |
| // A) with g and obj non-nil, to initialize just a single global. |
| // This occurs during the reference graph traversal. |
| // B) with g and obj nil, to initialize all globals in the same ValueSpec. |
| // This occurs during the left-to-right traversal over the ast.File. |
| // |
| // Precondition: g == b.globals[obj] |
| // |
| // Package-level var initialization order is quite subtle. |
| // The side effects of: |
| // var a, b = f(), g() |
| // are not observed left-to-right if b is referenced before a in the |
| // reference graph traversal. So, we track which Globals have been |
| // initialized by setting Global.spec=nil. |
| // |
| // Blank identifiers make things more complex since they don't have |
| // associated types.Objects or ssa.Globals yet we must still ensure |
| // that their corresponding side effects are observed at the right |
| // moment. Consider: |
| // var a, _, b = f(), g(), h() |
| // Here, the relative ordering of the call to g() is unspecified but |
| // it must occur exactly once, during mode B. So globalValueSpec for |
| // blanks must special-case n:n assigments and just evaluate the RHS |
| // g() for effect. |
| // |
| // In a n:1 assignment: |
| // var a, _, b = f() |
| // a reference to either a or b causes both globals to be initialized |
| // at the same time. Furthermore, no further work is required to |
| // ensure that the effects of the blank assignment occur. We must |
| // keep track of which n:1 specs have been evaluated, independent of |
| // which Globals are on the LHS (possibly none, if all are blank). |
| // |
| // See also localValueSpec. |
| // |
| func (b *Builder) globalValueSpec(init *Function, spec *ast.ValueSpec, g *Global, obj types.Object) { |
| switch { |
| case len(spec.Values) == len(spec.Names): |
| // e.g. var x, y = 0, 1 |
| // 1:1 assignment. |
| // Only the first time for a given GLOBAL has any effect. |
| for i, id := range spec.Names { |
| var lval lvalue = blank{} |
| if g != nil { |
| // Mode A: initialized only a single global, g |
| if isBlankIdent(id) || b.obj(id) != obj { |
| continue |
| } |
| g.spec = nil |
| lval = address{g} |
| } else { |
| // Mode B: initialize all globals. |
| if !isBlankIdent(id) { |
| g2 := b.globals[b.obj(id)].(*Global) |
| if g2.spec == nil { |
| continue // already done |
| } |
| g2.spec = nil |
| lval = address{g2} |
| } |
| } |
| if b.mode&LogSource != 0 { |
| fmt.Fprintln(os.Stderr, "build global", id.Name) |
| } |
| b.exprInPlace(init, lval, spec.Values[i]) |
| if g != nil { |
| break |
| } |
| } |
| |
| case len(spec.Values) == 0: |
| // e.g. var x, y int |
| // Globals are implicitly zero-initialized. |
| |
| default: |
| // e.g. var x, _, y = f() |
| // n:1 assignment. |
| // Only the first time for a given SPEC has any effect. |
| if !init.Pkg.nTo1Vars[spec] { |
| init.Pkg.nTo1Vars[spec] = true |
| if b.mode&LogSource != 0 { |
| defer logStack("build globals %s", spec.Names)() |
| } |
| tuple := b.exprN(init, spec.Values[0]) |
| rtypes := tuple.Type().(*types.Result).Values |
| for i, id := range spec.Names { |
| if !isBlankIdent(id) { |
| g := b.globals[b.obj(id)].(*Global) |
| g.spec = nil // just an optimization |
| emitStore(init, g, |
| emitExtract(init, tuple, i, rtypes[i].Type)) |
| } |
| } |
| } |
| } |
| } |
| |
| // localValueSpec emits to fn code to define all of the vars in the |
| // function-local ValueSpec, spec. |
| // |
| // See also globalValueSpec: the two routines are similar but local |
| // ValueSpecs are much simpler since they are encountered once only, |
| // in their entirety, in lexical order. |
| // |
| func (b *Builder) localValueSpec(fn *Function, spec *ast.ValueSpec) { |
| switch { |
| case len(spec.Values) == len(spec.Names): |
| // e.g. var x, y = 0, 1 |
| // 1:1 assignment |
| for i, id := range spec.Names { |
| var lval lvalue = blank{} |
| if !isBlankIdent(id) { |
| lval = address{fn.addNamedLocal(b.obj(id))} |
| } |
| b.exprInPlace(fn, lval, spec.Values[i]) |
| } |
| |
| case len(spec.Values) == 0: |
| // e.g. var x, y int |
| // Locals are implicitly zero-initialized. |
| for _, id := range spec.Names { |
| if !isBlankIdent(id) { |
| fn.addNamedLocal(b.obj(id)) |
| } |
| } |
| |
| default: |
| // e.g. var x, y = pos() |
| tuple := b.exprN(fn, spec.Values[0]) |
| rtypes := tuple.Type().(*types.Result).Values |
| for i, id := range spec.Names { |
| if !isBlankIdent(id) { |
| lhs := fn.addNamedLocal(b.obj(id)) |
| emitStore(fn, lhs, emitExtract(fn, tuple, i, rtypes[i].Type)) |
| } |
| } |
| } |
| } |
| |
| // assignStmt emits code to fn for a parallel assignment of rhss to lhss. |
| // isDef is true if this is a short variable declaration (:=). |
| // |
| // Note the similarity with localValueSpec. |
| // |
| func (b *Builder) assignStmt(fn *Function, lhss, rhss []ast.Expr, isDef bool) { |
| // Side effects of all LHSs and RHSs must occur in left-to-right order. |
| var lvals []lvalue |
| for _, lhs := range lhss { |
| var lval lvalue = blank{} |
| if !isBlankIdent(lhs) { |
| if isDef { |
| // Local may be "redeclared" in the same |
| // scope, so don't blindly create anew. |
| obj := b.obj(lhs.(*ast.Ident)) |
| if _, ok := fn.objects[obj]; !ok { |
| fn.addNamedLocal(obj) |
| } |
| } |
| lval = b.addr(fn, lhs, false) // non-escaping |
| } |
| lvals = append(lvals, lval) |
| } |
| if len(lhss) == len(rhss) { |
| // e.g. x, y = f(), g() |
| if len(lhss) == 1 { |
| // x = type{...} |
| // Optimization: in-place construction |
| // of composite literals. |
| b.exprInPlace(fn, lvals[0], rhss[0]) |
| } else { |
| // Parallel assignment. All reads must occur |
| // before all updates, precluding exprInPlace. |
| // TODO(adonovan): opt: is it sound to |
| // perform exprInPlace if !isDef? |
| var rvals []Value |
| for _, rval := range rhss { |
| rvals = append(rvals, b.expr(fn, rval)) |
| } |
| for i, lval := range lvals { |
| lval.store(fn, rvals[i]) |
| } |
| } |
| } else { |
| // e.g. x, y = pos() |
| tuple := b.exprN(fn, rhss[0]) |
| rtypes := tuple.Type().(*types.Result).Values |
| for i, lval := range lvals { |
| lval.store(fn, emitExtract(fn, tuple, i, rtypes[i].Type)) |
| } |
| } |
| } |
| |
| // compLit emits to fn code to initialize a composite literal e at |
| // address addr with type typ, typically allocated by Alloc. |
| // Nested composite literals are recursively initialized in place |
| // where possible. |
| // |
| func (b *Builder) compLit(fn *Function, addr Value, e *ast.CompositeLit, typ types.Type) { |
| // TODO(adonovan): test whether typ ever differs from |
| // b.exprType(e) and if so document why. |
| |
| switch t := underlyingType(typ).(type) { |
| case *types.Struct: |
| for i, e := range e.Elts { |
| // Subtle: field index i is updated in KeyValue case. |
| var sf *types.Field |
| if kv, ok := e.(*ast.KeyValueExpr); ok { |
| fname := kv.Key.(*ast.Ident).Name |
| for i, sf = range t.Fields { |
| if sf.Name == fname { |
| e = kv.Value |
| break |
| } |
| } |
| } else { |
| sf = t.Fields[i] |
| } |
| faddr := &FieldAddr{ |
| X: addr, |
| Field: i, |
| } |
| faddr.setType(pointer(sf.Type)) |
| fn.emit(faddr) |
| b.exprInPlace(fn, address{faddr}, e) |
| } |
| |
| case *types.Array, *types.Slice: |
| var at *types.Array |
| var array Value |
| switch t := t.(type) { |
| case *types.Slice: |
| at = &types.Array{Elt: t.Elt} // set Len later |
| array = emitNew(fn, at) |
| case *types.Array: |
| at = t |
| array = addr |
| } |
| var idx *Literal |
| var max int64 = -1 |
| for _, e := range e.Elts { |
| if kv, ok := e.(*ast.KeyValueExpr); ok { |
| idx = b.expr(fn, kv.Key).(*Literal) |
| e = kv.Value |
| } else { |
| var idxval int64 |
| if idx != nil { |
| idxval = idx.Int64() + 1 |
| } |
| idx = intLiteral(idxval) |
| } |
| if idx.Int64() > max { |
| max = idx.Int64() |
| } |
| iaddr := &IndexAddr{ |
| X: array, |
| Index: idx, |
| } |
| iaddr.setType(pointer(at.Elt)) |
| fn.emit(iaddr) |
| b.exprInPlace(fn, address{iaddr}, e) |
| } |
| if t != at { // slice |
| at.Len = max + 1 |
| s := &Slice{X: array} |
| s.setType(t) |
| emitStore(fn, addr, fn.emit(s)) |
| } |
| |
| case *types.Map: |
| m := &MakeMap{Reserve: intLiteral(int64(len(e.Elts)))} |
| m.setType(typ) |
| emitStore(fn, addr, fn.emit(m)) |
| for _, e := range e.Elts { |
| e := e.(*ast.KeyValueExpr) |
| up := &MapUpdate{ |
| Map: m, |
| Key: emitConv(fn, b.expr(fn, e.Key), t.Key), |
| Value: emitConv(fn, b.expr(fn, e.Value), t.Elt), |
| } |
| fn.emit(up) |
| } |
| |
| case *types.Pointer: |
| // Pointers can only occur in the recursive case; we |
| // strip them off in addr() before calling compLit |
| // again, so that we allocate space for a T not a *T. |
| panic("compLit(fn, addr, e, *types.Pointer") |
| |
| default: |
| panic("unexpected CompositeLit type: " + t.String()) |
| } |
| } |
| |
| // switchStmt emits to fn code for the switch statement s, optionally |
| // labelled by label. |
| // |
| func (b *Builder) switchStmt(fn *Function, s *ast.SwitchStmt, label *lblock) { |
| // We treat SwitchStmt like a sequential if-else chain. |
| // More efficient strategies (e.g. multiway dispatch) |
| // are possible if all cases are free of side effects. |
| if s.Init != nil { |
| b.stmt(fn, s.Init) |
| } |
| var tag Value = vTrue |
| if s.Tag != nil { |
| tag = b.expr(fn, s.Tag) |
| } |
| done := fn.newBasicBlock("switch.done") |
| if label != nil { |
| label._break = done |
| } |
| // We pull the default case (if present) down to the end. |
| // But each fallthrough label must point to the next |
| // body block in source order, so we preallocate a |
| // body block (fallthru) for the next case. |
| // Unfortunately this makes for a confusing block order. |
| var dfltBody *[]ast.Stmt |
| var dfltFallthrough *BasicBlock |
| var fallthru, dfltBlock *BasicBlock |
| ncases := len(s.Body.List) |
| for i, clause := range s.Body.List { |
| body := fallthru |
| if body == nil { |
| body = fn.newBasicBlock("switch.body") // first case only |
| } |
| |
| // Preallocate body block for the next case. |
| fallthru = done |
| if i+1 < ncases { |
| fallthru = fn.newBasicBlock("switch.body") |
| } |
| |
| cc := clause.(*ast.CaseClause) |
| if cc.List == nil { |
| // Default case. |
| dfltBody = &cc.Body |
| dfltFallthrough = fallthru |
| dfltBlock = body |
| continue |
| } |
| |
| var nextCond *BasicBlock |
| for _, cond := range cc.List { |
| nextCond = fn.newBasicBlock("switch.next") |
| // TODO(adonovan): opt: when tag==vTrue, we'd |
| // get better much code if we use b.cond(cond) |
| // instead of BinOp(EQL, tag, b.expr(cond)) |
| // followed by If. Don't forget conversions |
| // though. |
| cond := emitCompare(fn, token.EQL, tag, b.expr(fn, cond)) |
| emitIf(fn, cond, body, nextCond) |
| fn.currentBlock = nextCond |
| } |
| fn.currentBlock = body |
| fn.targets = &targets{ |
| tail: fn.targets, |
| _break: done, |
| _fallthrough: fallthru, |
| } |
| b.stmtList(fn, cc.Body) |
| fn.targets = fn.targets.tail |
| emitJump(fn, done) |
| fn.currentBlock = nextCond |
| } |
| if dfltBlock != nil { |
| emitJump(fn, dfltBlock) |
| fn.currentBlock = dfltBlock |
| fn.targets = &targets{ |
| tail: fn.targets, |
| _break: done, |
| _fallthrough: dfltFallthrough, |
| } |
| b.stmtList(fn, *dfltBody) |
| fn.targets = fn.targets.tail |
| } |
| emitJump(fn, done) |
| fn.currentBlock = done |
| } |
| |
| // typeSwitchStmt emits to fn code for the type switch statement s, optionally |
| // labelled by label. |
| // |
| func (b *Builder) typeSwitchStmt(fn *Function, s *ast.TypeSwitchStmt, label *lblock) { |
| // We treat TypeSwitchStmt like a sequential if-else |
| // chain. More efficient strategies (e.g. multiway |
| // dispatch) are possible. |
| |
| // Typeswitch lowering: |
| // |
| // var x X |
| // switch y := x.(type) { |
| // case T1, T2: S1 // >1 (y := x) |
| // default: SD // 0 types (y := x) |
| // case T3: S3 // 1 type (y := x.(T3)) |
| // } |
| // |
| // ...s.Init... |
| // x := eval x |
| // y := x |
| // .caseT1: |
| // t1, ok1 := typeswitch,ok x <T1> |
| // if ok1 then goto S1 else goto .caseT2 |
| // .caseT2: |
| // t2, ok2 := typeswitch,ok x <T2> |
| // if ok2 then goto S1 else goto .caseT3 |
| // .S1: |
| // ...S1... |
| // goto done |
| // .caseT3: |
| // t3, ok3 := typeswitch,ok x <T3> |
| // if ok3 then goto S3 else goto default |
| // .S3: |
| // y' := t3 // Kludge: within scope of S3, y resolves here |
| // ...S3... |
| // goto done |
| // .default: |
| // goto done |
| // .done: |
| |
| if s.Init != nil { |
| b.stmt(fn, s.Init) |
| } |
| |
| var x, y Value |
| var id *ast.Ident |
| switch ass := s.Assign.(type) { |
| case *ast.ExprStmt: // x.(type) |
| x = b.expr(fn, noparens(ass.X).(*ast.TypeAssertExpr).X) |
| case *ast.AssignStmt: // y := x.(type) |
| x = b.expr(fn, noparens(ass.Rhs[0]).(*ast.TypeAssertExpr).X) |
| id = ass.Lhs[0].(*ast.Ident) |
| y = fn.addNamedLocal(b.obj(id)) |
| emitStore(fn, y, x) |
| } |
| |
| done := fn.newBasicBlock("typeswitch.done") |
| if label != nil { |
| label._break = done |
| } |
| var dfltBody []ast.Stmt |
| for _, clause := range s.Body.List { |
| cc := clause.(*ast.CaseClause) |
| if cc.List == nil { |
| dfltBody = cc.Body |
| continue |
| } |
| body := fn.newBasicBlock("typeswitch.body") |
| var next *BasicBlock |
| var casetype types.Type |
| var ti Value // t_i, ok := typeassert,ok x <T_i> |
| for _, cond := range cc.List { |
| next = fn.newBasicBlock("typeswitch.next") |
| casetype = b.exprType(cond) |
| var condv Value |
| if casetype == tUntypedNil { |
| condv = emitCompare(fn, token.EQL, x, nilLiteral(x.Type())) |
| } else { |
| yok := &TypeAssert{ |
| X: x, |
| AssertedType: casetype, |
| CommaOk: true, |
| } |
| yok.setType(&types.Result{Values: []*types.Var{ |
| {Name: "value", Type: casetype}, |
| varOk, |
| }}) |
| fn.emit(yok) |
| ti = emitExtract(fn, yok, 0, casetype) |
| condv = emitExtract(fn, yok, 1, tBool) |
| } |
| emitIf(fn, condv, body, next) |
| fn.currentBlock = next |
| } |
| fn.currentBlock = body |
| if id != nil && len(cc.List) == 1 && casetype != tUntypedNil { |
| // Declare a new shadow local variable of the |
| // same name but a more specific type. |
| // Side effect: reassociates binding for y's object. |
| y2 := fn.addNamedLocal(b.obj(id)) |
| y2.Name_ += "'" // debugging aid |
| y2.Type_ = pointer(casetype) |
| emitStore(fn, y2, ti) |
| } |
| fn.targets = &targets{ |
| tail: fn.targets, |
| _break: done, |
| } |
| b.stmtList(fn, cc.Body) |
| fn.targets = fn.targets.tail |
| if id != nil { |
| fn.objects[b.obj(id)] = y // restore previous y binding |
| } |
| emitJump(fn, done) |
| fn.currentBlock = next |
| } |
| fn.targets = &targets{ |
| tail: fn.targets, |
| _break: done, |
| } |
| b.stmtList(fn, dfltBody) |
| fn.targets = fn.targets.tail |
| emitJump(fn, done) |
| fn.currentBlock = done |
| } |
| |
| // selectStmt emits to fn code for the select statement s, optionally |
| // labelled by label. |
| // |
| func (b *Builder) selectStmt(fn *Function, s *ast.SelectStmt, label *lblock) { |
| // A blocking select of a single case degenerates to a |
| // simple send or receive. |
| // TODO(adonovan): opt: is this optimization worth its weight? |
| if len(s.Body.List) == 1 { |
| clause := s.Body.List[0].(*ast.CommClause) |
| if clause.Comm != nil { |
| b.stmt(fn, clause.Comm) |
| done := fn.newBasicBlock("select.done") |
| if label != nil { |
| label._break = done |
| } |
| fn.targets = &targets{ |
| tail: fn.targets, |
| _break: done, |
| } |
| b.stmtList(fn, clause.Body) |
| fn.targets = fn.targets.tail |
| emitJump(fn, done) |
| fn.currentBlock = done |
| return |
| } |
| } |
| |
| // First evaluate all channels in all cases, and find |
| // the directions of each state. |
| var states []SelectState |
| blocking := true |
| for _, clause := range s.Body.List { |
| switch comm := clause.(*ast.CommClause).Comm.(type) { |
| case nil: // default case |
| blocking = false |
| |
| case *ast.SendStmt: // ch<- i |
| ch := b.expr(fn, comm.Chan) |
| states = append(states, SelectState{ |
| Dir: ast.SEND, |
| Chan: ch, |
| Send: emitConv(fn, b.expr(fn, comm.Value), |
| underlyingType(ch.Type()).(*types.Chan).Elt), |
| }) |
| |
| case *ast.AssignStmt: // x := <-ch |
| states = append(states, SelectState{ |
| Dir: ast.RECV, |
| Chan: b.expr(fn, noparens(comm.Rhs[0]).(*ast.UnaryExpr).X), |
| }) |
| |
| case *ast.ExprStmt: // <-ch |
| states = append(states, SelectState{ |
| Dir: ast.RECV, |
| Chan: b.expr(fn, noparens(comm.X).(*ast.UnaryExpr).X), |
| }) |
| } |
| } |
| |
| // We dispatch on the (fair) result of Select using a |
| // sequential if-else chain, in effect: |
| // |
| // idx, recv, recvOk := select(...) |
| // if idx == 0 { // receive on channel 0 |
| // x, ok := recv, recvOk |
| // ...state0... |
| // } else if v == 1 { // send on channel 1 |
| // ...state1... |
| // } else { |
| // ...default... |
| // } |
| pair := &Select{ |
| States: states, |
| Blocking: blocking, |
| } |
| pair.setType(tSelect) |
| fn.emit(pair) |
| idx := emitExtract(fn, pair, 0, tInt) |
| |
| done := fn.newBasicBlock("select.done") |
| if label != nil { |
| label._break = done |
| } |
| |
| var dfltBody *[]ast.Stmt |
| state := 0 |
| for _, cc := range s.Body.List { |
| clause := cc.(*ast.CommClause) |
| if clause.Comm == nil { |
| dfltBody = &clause.Body |
| continue |
| } |
| body := fn.newBasicBlock("select.body") |
| next := fn.newBasicBlock("select.next") |
| emitIf(fn, emitCompare(fn, token.EQL, idx, intLiteral(int64(state))), body, next) |
| fn.currentBlock = body |
| fn.targets = &targets{ |
| tail: fn.targets, |
| _break: done, |
| } |
| switch comm := clause.Comm.(type) { |
| case *ast.AssignStmt: // x := <-states[state].Chan |
| xdecl := fn.addNamedLocal(b.obj(comm.Lhs[0].(*ast.Ident))) |
| |
| emitStore(fn, xdecl, emitExtract(fn, pair, 1, indirectType(xdecl.Type()))) |
| if len(comm.Lhs) == 2 { // x, ok := ... |
| okdecl := fn.addNamedLocal(b.obj(comm.Lhs[1].(*ast.Ident))) |
| emitStore(fn, okdecl, emitExtract(fn, pair, 2, indirectType(okdecl.Type()))) |
| } |
| } |
| b.stmtList(fn, clause.Body) |
| fn.targets = fn.targets.tail |
| emitJump(fn, done) |
| fn.currentBlock = next |
| state++ |
| } |
| if dfltBody != nil { |
| fn.targets = &targets{ |
| tail: fn.targets, |
| _break: done, |
| } |
| b.stmtList(fn, *dfltBody) |
| fn.targets = fn.targets.tail |
| } |
| emitJump(fn, done) |
| fn.currentBlock = done |
| } |
| |
| // forStmt emits to fn code for the for statement s, optionally |
| // labelled by label. |
| // |
| func (b *Builder) forStmt(fn *Function, s *ast.ForStmt, label *lblock) { |
| // ...init... |
| // jump loop |
| // loop: |
| // if cond goto body else done |
| // body: |
| // ...body... |
| // jump post |
| // post: (target of continue) |
| // ...post... |
| // jump loop |
| // done: (target of break) |
| if s.Init != nil { |
| b.stmt(fn, s.Init) |
| } |
| body := fn.newBasicBlock("for.body") |
| done := fn.newBasicBlock("for.done") // target of 'break' |
| loop := body // target of back-edge |
| if s.Cond != nil { |
| loop = fn.newBasicBlock("for.loop") |
| } |
| cont := loop // target of 'continue' |
| if s.Post != nil { |
| cont = fn.newBasicBlock("for.post") |
| } |
| if label != nil { |
| label._break = done |
| label._continue = cont |
| } |
| emitJump(fn, loop) |
| fn.currentBlock = loop |
| if loop != body { |
| b.cond(fn, s.Cond, body, done) |
| fn.currentBlock = body |
| } |
| fn.targets = &targets{ |
| tail: fn.targets, |
| _break: done, |
| _continue: cont, |
| } |
| b.stmt(fn, s.Body) |
| fn.targets = fn.targets.tail |
| emitJump(fn, cont) |
| |
| if s.Post != nil { |
| fn.currentBlock = cont |
| b.stmt(fn, s.Post) |
| emitJump(fn, loop) // back-edge |
| } |
| fn.currentBlock = done |
| } |
| |
| // rangeIndexed emits to fn the header for an integer indexed loop |
| // over array, *array or slice value x. |
| // The v result is defined only if tv is non-nil. |
| // |
| func (b *Builder) rangeIndexed(fn *Function, x Value, tv types.Type) (k, v Value, loop, done *BasicBlock) { |
| // |
| // length = len(x) |
| // index = -1 |
| // loop: (target of continue) |
| // index++ |
| // if index < length goto body else done |
| // body: |
| // k = index |
| // v = x[index] |
| // ...body... |
| // jump loop |
| // done: (target of break) |
| |
| // Determine number of iterations. |
| var length Value |
| if arr, ok := deref(x.Type()).(*types.Array); ok { |
| // For array or *array, the number of iterations is |
| // known statically thanks to the type. We avoid a |
| // data dependence upon x, permitting later dead-code |
| // elimination if x is pure, static unrolling, etc. |
| // Ranging over a nil *array may have >0 iterations. |
| length = intLiteral(arr.Len) |
| } else { |
| // length = len(x). |
| var call Call |
| call.Func = b.globals[types.Universe.Lookup("len")] |
| call.Args = []Value{x} |
| call.setType(tInt) |
| length = fn.emit(&call) |
| } |
| |
| index := fn.addLocal(tInt) |
| emitStore(fn, index, intLiteral(-1)) |
| |
| loop = fn.newBasicBlock("rangeindex.loop") |
| emitJump(fn, loop) |
| fn.currentBlock = loop |
| |
| incr := &BinOp{ |
| Op: token.ADD, |
| X: emitLoad(fn, index), |
| Y: intLiteral(1), |
| } |
| incr.setType(tInt) |
| emitStore(fn, index, fn.emit(incr)) |
| |
| body := fn.newBasicBlock("rangeindex.body") |
| done = fn.newBasicBlock("rangeindex.done") |
| emitIf(fn, emitCompare(fn, token.LSS, incr, length), body, done) |
| fn.currentBlock = body |
| |
| k = emitLoad(fn, index) |
| if tv != nil { |
| switch t := underlyingType(x.Type()).(type) { |
| case *types.Array: |
| instr := &Index{ |
| X: x, |
| Index: k, |
| } |
| instr.setType(t.Elt) |
| v = fn.emit(instr) |
| |
| case *types.Pointer: // *array |
| instr := &IndexAddr{ |
| X: x, |
| Index: k, |
| } |
| instr.setType(pointer(t.Base.(*types.Array).Elt)) |
| v = emitLoad(fn, fn.emit(instr)) |
| |
| case *types.Slice: |
| instr := &IndexAddr{ |
| X: x, |
| Index: k, |
| } |
| instr.setType(pointer(t.Elt)) |
| v = emitLoad(fn, fn.emit(instr)) |
| |
| default: |
| panic("rangeIndexed x:" + t.String()) |
| } |
| } |
| return |
| } |
| |
| // rangeIter emits to fn the header for a loop using |
| // Range/Next/Extract to iterate over map or string value x. |
| // tk and tv are the types of the key/value results k and v, or nil |
| // if the respective component is not wanted. |
| // |
| func (b *Builder) rangeIter(fn *Function, x Value, tk, tv types.Type) (k, v Value, loop, done *BasicBlock) { |
| // |
| // it = range x |
| // loop: (target of continue) |
| // okv = next it (ok, key, value) |
| // ok = extract okv #0 |
| // if ok goto body else done |
| // body: |
| // k = extract okv #1 |
| // v = extract okv #2 |
| // ...body... |
| // jump loop |
| // done: (target of break) |
| // |
| |
| rng := &Range{X: x} |
| rng.setType(tRangeIter) |
| it := fn.emit(rng) |
| |
| loop = fn.newBasicBlock("rangeiter.loop") |
| emitJump(fn, loop) |
| fn.currentBlock = loop |
| |
| okv := &Next{Iter: it} |
| okv.setType(&types.Result{Values: []*types.Var{ |
| varOk, |
| {Name: "k", Type: tk}, |
| {Name: "v", Type: tv}, |
| }}) |
| fn.emit(okv) |
| |
| body := fn.newBasicBlock("rangeiter.body") |
| done = fn.newBasicBlock("rangeiter.done") |
| emitIf(fn, emitExtract(fn, okv, 0, tBool), body, done) |
| fn.currentBlock = body |
| |
| if tk != nil { |
| k = emitExtract(fn, okv, 1, tk) |
| } |
| if tv != nil { |
| v = emitExtract(fn, okv, 2, tv) |
| } |
| return |
| } |
| |
| // rangeChan emits to fn the header for a loop that receives from |
| // channel x until it fails. |
| // tk is the channel's element type, or nil if the k result is not |
| // wanted |
| // |
| func (b *Builder) rangeChan(fn *Function, x Value, tk types.Type) (k Value, loop, done *BasicBlock) { |
| // |
| // loop: (target of continue) |
| // ko = <-x (key, ok) |
| // ok = extract ko #1 |
| // if ok goto body else done |
| // body: |
| // k = extract ko #0 |
| // ... |
| // goto loop |
| // done: (target of break) |
| |
| loop = fn.newBasicBlock("rangechan.loop") |
| emitJump(fn, loop) |
| fn.currentBlock = loop |
| recv := &UnOp{ |
| Op: token.ARROW, |
| X: x, |
| CommaOk: true, |
| } |
| recv.setType(&types.Result{Values: []*types.Var{ |
| {Name: "k", Type: tk}, |
| varOk, |
| }}) |
| ko := fn.emit(recv) |
| body := fn.newBasicBlock("rangechan.body") |
| done = fn.newBasicBlock("rangechan.done") |
| emitIf(fn, emitExtract(fn, ko, 1, tBool), body, done) |
| fn.currentBlock = body |
| if tk != nil { |
| k = emitExtract(fn, ko, 0, tk) |
| } |
| return |
| } |
| |
| // rangeStmt emits to fn code for the range statement s, optionally |
| // labelled by label. |
| // |
| func (b *Builder) rangeStmt(fn *Function, s *ast.RangeStmt, label *lblock) { |
| var tk, tv types.Type |
| if !isBlankIdent(s.Key) { |
| tk = b.exprType(s.Key) |
| } |
| if s.Value != nil && !isBlankIdent(s.Value) { |
| tv = b.exprType(s.Value) |
| } |
| |
| // If iteration variables are defined (:=), this |
| // occurs once outside the loop. |
| // |
| // Unlike a short variable declaration, a RangeStmt |
| // using := never redeclares an existing variable; it |
| // always creates a new one. |
| if s.Tok == token.DEFINE { |
| if tk != nil { |
| fn.addNamedLocal(b.obj(s.Key.(*ast.Ident))) |
| } |
| if tv != nil { |
| fn.addNamedLocal(b.obj(s.Value.(*ast.Ident))) |
| } |
| } |
| |
| x := b.expr(fn, s.X) |
| |
| var k, v Value |
| var loop, done *BasicBlock |
| switch rt := underlyingType(x.Type()).(type) { |
| case *types.Slice, *types.Array, *types.Pointer: // *array |
| k, v, loop, done = b.rangeIndexed(fn, x, tv) |
| |
| case *types.Chan: |
| k, loop, done = b.rangeChan(fn, x, tk) |
| |
| case *types.Map, *types.Basic: // string |
| k, v, loop, done = b.rangeIter(fn, x, tk, tv) |
| |
| default: |
| panic("Cannot range over: " + rt.String()) |
| } |
| |
| // Evaluate both LHS expressions before we update either. |
| var kl, vl lvalue |
| if tk != nil { |
| kl = b.addr(fn, s.Key, false) // non-escaping |
| } |
| if tv != nil { |
| vl = b.addr(fn, s.Value, false) // non-escaping |
| } |
| if tk != nil { |
| kl.store(fn, k) |
| } |
| if tv != nil { |
| vl.store(fn, v) |
| } |
| |
| if label != nil { |
| label._break = done |
| label._continue = loop |
| } |
| |
| fn.targets = &targets{ |
| tail: fn.targets, |
| _break: done, |
| _continue: loop, |
| } |
| b.stmt(fn, s.Body) |
| fn.targets = fn.targets.tail |
| emitJump(fn, loop) // back-edge |
| fn.currentBlock = done |
| } |
| |
| // stmt lowers statement s to SSA form, emitting code to fn. |
| func (b *Builder) stmt(fn *Function, _s ast.Stmt) { |
| // The label of the current statement. If non-nil, its _goto |
| // target is always set; its _break and _continue are set only |
| // within the body of switch/typeswitch/select/for/range. |
| // It is effectively an additional default-nil parameter of stmt(). |
| var label *lblock |
| start: |
| switch s := _s.(type) { |
| case *ast.EmptyStmt: |
| // ignore. (Usually removed by gofmt.) |
| |
| case *ast.DeclStmt: // Con, Var or Typ |
| d := s.Decl.(*ast.GenDecl) |
| for _, spec := range d.Specs { |
| if vs, ok := spec.(*ast.ValueSpec); ok { |
| b.localValueSpec(fn, vs) |
| } |
| } |
| |
| case *ast.LabeledStmt: |
| label = fn.labelledBlock(s.Label) |
| emitJump(fn, label._goto) |
| fn.currentBlock = label._goto |
| _s = s.Stmt |
| goto start // effectively: tailcall stmt(fn, s.Stmt, label) |
| |
| case *ast.ExprStmt: |
| b.expr(fn, s.X) |
| |
| case *ast.SendStmt: |
| fn.emit(&Send{ |
| Chan: b.expr(fn, s.Chan), |
| X: emitConv(fn, b.expr(fn, s.Value), |
| underlyingType(b.exprType(s.Chan)).(*types.Chan).Elt), |
| }) |
| |
| case *ast.IncDecStmt: |
| op := token.ADD |
| if s.Tok == token.DEC { |
| op = token.SUB |
| } |
| b.assignOp(fn, b.addr(fn, s.X, false), vOne, op) |
| |
| case *ast.AssignStmt: |
| switch s.Tok { |
| case token.ASSIGN, token.DEFINE: |
| b.assignStmt(fn, s.Lhs, s.Rhs, s.Tok == token.DEFINE) |
| |
| default: // +=, etc. |
| op := s.Tok + token.ADD - token.ADD_ASSIGN |
| b.assignOp(fn, b.addr(fn, s.Lhs[0], false), b.expr(fn, s.Rhs[0]), op) |
| } |
| |
| case *ast.GoStmt: |
| // The "intrinsics" new/make/len/cap are forbidden here. |
| // panic is treated like an ordinary function call. |
| var v Go |
| b.setCall(fn, s.Call, &v.CallCommon) |
| fn.emit(&v) |
| |
| case *ast.DeferStmt: |
| // The "intrinsics" new/make/len/cap are forbidden here. |
| // panic is treated like an ordinary function call. |
| var v Defer |
| b.setCall(fn, s.Call, &v.CallCommon) |
| fn.emit(&v) |
| |
| case *ast.ReturnStmt: |
| if fn == fn.Pkg.Init { |
| // A "return" within an init block is treated |
| // like a "goto" to the next init block. We |
| // use the outermost BREAK target for this purpose. |
| var block *BasicBlock |
| for t := fn.targets; t != nil; t = t.tail { |
| if t._break != nil { |
| block = t._break |
| } |
| } |
| // Run function calls deferred in this init |
| // block when explicitly returning from it. |
| fn.emit(new(RunDefers)) |
| emitJump(fn, block) |
| fn.currentBlock = fn.newBasicBlock("unreachable") |
| return |
| } |
| |
| var results []Value |
| if len(s.Results) == 1 && len(fn.Signature.Results) > 1 { |
| // Return of one expression in a multi-valued function. |
| tuple := b.exprN(fn, s.Results[0]) |
| for i, v := range tuple.Type().(*types.Result).Values { |
| results = append(results, emitExtract(fn, tuple, i, v.Type)) |
| } |
| } else { |
| // 1:1 return, or no-arg return in non-void function. |
| for i, r := range s.Results { |
| v := emitConv(fn, b.expr(fn, r), fn.Signature.Results[i].Type) |
| results = append(results, v) |
| } |
| } |
| if fn.namedResults != nil { |
| // Function has named result parameters (NRPs). |
| // Perform parallel assignment of return operands to NRPs. |
| for i, r := range results { |
| emitStore(fn, fn.namedResults[i], r) |
| } |
| } |
| // Run function calls deferred in this |
| // function when explicitly returning from it. |
| fn.emit(new(RunDefers)) |
| if fn.namedResults != nil { |
| // Reload NRPs to form the result tuple. |
| results = results[:0] |
| for _, r := range fn.namedResults { |
| results = append(results, emitLoad(fn, r)) |
| } |
| } |
| fn.emit(&Ret{Results: results}) |
| fn.currentBlock = fn.newBasicBlock("unreachable") |
| |
| case *ast.BranchStmt: |
| var block *BasicBlock |
| switch s.Tok { |
| case token.BREAK: |
| if s.Label != nil { |
| block = fn.labelledBlock(s.Label)._break |
| } else { |
| for t := fn.targets; t != nil && block == nil; t = t.tail { |
| block = t._break |
| } |
| } |
| |
| case token.CONTINUE: |
| if s.Label != nil { |
| block = fn.labelledBlock(s.Label)._continue |
| } else { |
| for t := fn.targets; t != nil && block == nil; t = t.tail { |
| block = t._continue |
| } |
| } |
| |
| case token.FALLTHROUGH: |
| for t := fn.targets; t != nil && block == nil; t = t.tail { |
| block = t._fallthrough |
| } |
| |
| case token.GOTO: |
| block = fn.labelledBlock(s.Label)._goto |
| } |
| if block == nil { |
| // TODO(gri): fix: catch these in the typechecker. |
| fmt.Printf("ignoring illegal branch: %s %s\n", s.Tok, s.Label) |
| } else { |
| emitJump(fn, block) |
| fn.currentBlock = fn.newBasicBlock("unreachable") |
| } |
| |
| case *ast.BlockStmt: |
| b.stmtList(fn, s.List) |
| |
| case *ast.IfStmt: |
| if s.Init != nil { |
| b.stmt(fn, s.Init) |
| } |
| then := fn.newBasicBlock("if.then") |
| done := fn.newBasicBlock("if.done") |
| els := done |
| if s.Else != nil { |
| els = fn.newBasicBlock("if.else") |
| } |
| b.cond(fn, s.Cond, then, els) |
| fn.currentBlock = then |
| b.stmt(fn, s.Body) |
| emitJump(fn, done) |
| |
| if s.Else != nil { |
| fn.currentBlock = els |
| b.stmt(fn, s.Else) |
| emitJump(fn, done) |
| } |
| |
| fn.currentBlock = done |
| |
| case *ast.SwitchStmt: |
| b.switchStmt(fn, s, label) |
| |
| case *ast.TypeSwitchStmt: |
| b.typeSwitchStmt(fn, s, label) |
| |
| case *ast.SelectStmt: |
| b.selectStmt(fn, s, label) |
| |
| case *ast.ForStmt: |
| b.forStmt(fn, s, label) |
| |
| case *ast.RangeStmt: |
| b.rangeStmt(fn, s, label) |
| |
| default: |
| panic(fmt.Sprintf("unexpected statement kind: %T", s)) |
| } |
| } |
| |
| // buildFunction builds SSA code for the body of function fn. Idempotent. |
| func (b *Builder) buildFunction(fn *Function) { |
| if fn.Blocks != nil { |
| return // building already started |
| } |
| if fn.syntax == nil { |
| return // not a Go source function |
| } |
| if fn.syntax.body == nil { |
| return // Go source function with no body (external) |
| } |
| if fn.Prog.mode&LogSource != 0 { |
| defer logStack("build function %s @ %s", |
| fn.FullName(), fn.Prog.Files.Position(fn.Pos))() |
| } |
| fn.start(b.idents) |
| b.stmt(fn, fn.syntax.body) |
| if cb := fn.currentBlock; cb != nil && (cb == fn.Blocks[0] || cb.Preds != nil) { |
| // Run function calls deferred in this function when |
| // falling off the end of the body block. |
| fn.emit(new(RunDefers)) |
| fn.emit(new(Ret)) |
| } |
| fn.finish() |
| } |
| |
| // memberFromObject populates package pkg with a member for the |
| // typechecker object obj. |
| // |
| // For objects from Go source code, syntax is the associated syntax |
| // tree (for funcs and vars only); it will be used during the build |
| // phase. |
| // |
| func (b *Builder) memberFromObject(pkg *Package, obj types.Object, syntax ast.Node) { |
| name := obj.GetName() |
| switch obj := obj.(type) { |
| case *types.TypeName: |
| pkg.Members[name] = &Type{NamedType: obj.Type.(*types.NamedType)} |
| |
| case *types.Const: |
| pkg.Members[name] = newLiteral(obj.Val, obj.Type) |
| |
| case *types.Var: |
| spec, _ := syntax.(*ast.ValueSpec) |
| g := &Global{ |
| Pkg: pkg, |
| Name_: name, |
| Type_: pointer(obj.Type), // address |
| spec: spec, |
| } |
| b.globals[obj] = g |
| pkg.Members[name] = g |
| |
| case *types.Func: |
| var fs *funcSyntax |
| var pos token.Pos |
| if decl, ok := syntax.(*ast.FuncDecl); ok { |
| fs = &funcSyntax{ |
| recvField: decl.Recv, |
| paramFields: decl.Type.Params, |
| resultFields: decl.Type.Results, |
| body: decl.Body, |
| } |
| // TODO(gri): make GcImported types.Object |
| // implement the full object interface |
| // including Pos(). Or at least not crash. |
| pos = obj.GetPos() |
| } |
| sig := obj.Type.(*types.Signature) |
| fn := &Function{ |
| Name_: name, |
| Signature: sig, |
| Pos: pos, |
| Pkg: pkg, |
| Prog: b.Prog, |
| syntax: fs, |
| } |
| if sig.Recv == nil { |
| // Function declaration. |
| b.globals[obj] = fn |
| pkg.Members[name] = fn |
| } else { |
| // Method declaration. |
| nt := deref(sig.Recv.Type).(*types.NamedType) |
| _, method := methodIndex(nt, nt.Methods, makeId(name, pkg.Types)) |
| b.Prog.concreteMethods[method] = fn |
| } |
| |
| default: // (incl. *types.Package) |
| panic(fmt.Sprintf("unexpected Object type: %T", obj)) |
| } |
| } |
| |
| // membersFromDecl populates package pkg with members for each |
| // typechecker object (var, func, const or type) associated with the |
| // specified decl. |
| // |
| func (b *Builder) membersFromDecl(pkg *Package, decl ast.Decl) { |
| switch decl := decl.(type) { |
| case *ast.GenDecl: // import, const, type or var |
| switch decl.Tok { |
| case token.CONST: |
| for _, spec := range decl.Specs { |
| for _, id := range spec.(*ast.ValueSpec).Names { |
| if !isBlankIdent(id) { |
| b.memberFromObject(pkg, b.obj(id), nil) |
| } |
| } |
| } |
| |
| case token.VAR: |
| for _, spec := range decl.Specs { |
| for _, id := range spec.(*ast.ValueSpec).Names { |
| if !isBlankIdent(id) { |
| b.memberFromObject(pkg, b.obj(id), spec) |
| } |
| } |
| } |
| |
| case token.TYPE: |
| for _, spec := range decl.Specs { |
| id := spec.(*ast.TypeSpec).Name |
| if !isBlankIdent(id) { |
| b.memberFromObject(pkg, b.obj(id), nil) |
| } |
| } |
| } |
| |
| case *ast.FuncDecl: |
| id := decl.Name |
| if decl.Recv == nil && id.Name == "init" { |
| return // init blocks aren't functions |
| } |
| if !isBlankIdent(id) { |
| b.memberFromObject(pkg, b.obj(id), decl) |
| } |
| } |
| } |
| |
| // CreatePackage creates a package from the specified set of files, |
| // performs type-checking, and allocates all global SSA Values for the |
| // package. It returns a new SSA Package providing access to these |
| // values. The order of files determines the package initialization order. |
| // |
| // importPath is the full name under which this package is known, such |
| // as appears in an import declaration. e.g. "sync/atomic". |
| // |
| // The ParseFiles() utility may be helpful for parsing a set of Go |
| // source files. |
| // |
| func (b *Builder) CreatePackage(importPath string, files []*ast.File) (*Package, error) { |
| typkg, firstErr := b.typechecker.Check(b.Prog.Files, files) |
| if firstErr != nil { |
| return nil, firstErr |
| } |
| return b.createPackageImpl(typkg, importPath, files), nil |
| } |
| |
| // createPackageImpl constructs an SSA Package from an error-free |
| // types.Package typkg and populates its Members mapping. It returns |
| // the newly constructed ssa.Package. |
| // |
| // The real work of building SSA form for each function is not done |
| // until a subsequent call to BuildPackage. |
| // |
| // If files is non-nil, its declarations will be used to generate code |
| // for functions, methods and init blocks in a subsequent call to |
| // BuildPackage. Otherwise, typkg is assumed to have been imported |
| // from the gc compiler's object files; no code will be available. |
| // |
| func (b *Builder) createPackageImpl(typkg *types.Package, importPath string, files []*ast.File) *Package { |
| // The typechecker sets types.Package.Path only for GcImported |
| // packages, since it doesn't know import path until after typechecking is done. |
| // Here we ensure it is always set, since we know the correct path. |
| if typkg.Path == "" { |
| typkg.Path = importPath |
| } else if typkg.Path != importPath { |
| panic(fmt.Sprintf("%s != %s", typkg.Path, importPath)) |
| } |
| |
| p := &Package{ |
| Prog: b.Prog, |
| Types: typkg, |
| Members: make(map[string]Member), |
| files: files, |
| nTo1Vars: make(map[*ast.ValueSpec]bool), |
| } |
| |
| b.packages[typkg] = p |
| b.Prog.Packages[importPath] = p |
| |
| // CREATE phase. |
| // Allocate all package members: vars, funcs and consts and types. |
| if len(files) > 0 { |
| // Go source package. |
| |
| p.Pos = files[0].Package // arbitrary file |
| |
| // TODO(gri): make it a typechecker error for there to |
| // be duplicate (e.g.) main functions in the same package. |
| for _, file := range p.files { |
| // ast.Print(b.Prog.Files, file) // debugging |
| for _, decl := range file.Decls { |
| b.membersFromDecl(p, decl) |
| } |
| } |
| } else { |
| // GC-compiled binary package. |
| // No code. |
| // No position information. |
| |
| for _, obj := range p.Types.Scope.Entries { |
| b.memberFromObject(p, obj, nil) |
| } |
| } |
| |
| // Compute the method sets |
| for _, mem := range p.Members { |
| switch t := mem.(type) { |
| case *Type: |
| t.Methods = b.Prog.MethodSet(t.NamedType) |
| t.PtrMethods = b.Prog.MethodSet(pointer(t.NamedType)) |
| } |
| } |
| |
| // Add init() function (but not to Members since it can't be referenced). |
| p.Init = &Function{ |
| Name_: "init", |
| Signature: new(types.Signature), |
| Pos: p.Pos, |
| Pkg: p, |
| Prog: b.Prog, |
| } |
| |
| // Add initializer guard variable. |
| initguard := &Global{ |
| Pkg: p, |
| Name_: "init·guard", |
| Type_: pointer(tBool), |
| } |
| p.Members[initguard.Name()] = initguard |
| |
| if b.mode&LogPackages != 0 { |
| p.DumpTo(os.Stderr) |
| } |
| |
| return p |
| } |
| |
| // buildDecl builds SSA code for all globals, functions or methods |
| // declared by decl in package pkg. |
| // |
| func (b *Builder) buildDecl(pkg *Package, decl ast.Decl) { |
| switch decl := decl.(type) { |
| case *ast.GenDecl: |
| switch decl.Tok { |
| // Nothing to do for CONST, IMPORT. |
| case token.VAR: |
| for _, spec := range decl.Specs { |
| b.globalValueSpec(pkg.Init, spec.(*ast.ValueSpec), nil, nil) |
| } |
| case token.TYPE: |
| for _, spec := range decl.Specs { |
| id := spec.(*ast.TypeSpec).Name |
| if isBlankIdent(id) { |
| continue |
| } |
| obj := b.obj(id).(*types.TypeName) |
| for _, method := range obj.Type.(*types.NamedType).Methods { |
| b.buildFunction(b.Prog.concreteMethods[method]) |
| } |
| } |
| } |
| |
| case *ast.FuncDecl: |
| id := decl.Name |
| if isBlankIdent(id) { |
| // no-op |
| |
| } else if decl.Recv == nil && id.Name == "init" { |
| // init() block |
| if b.mode&LogSource != 0 { |
| fmt.Fprintln(os.Stderr, "build init block @", b.Prog.Files.Position(decl.Pos())) |
| } |
| init := pkg.Init |
| |
| // A return statement within an init block is |
| // treated like a "goto" to the the next init |
| // block, which we stuff in the outermost |
| // break label. |
| next := init.newBasicBlock("init.next") |
| init.targets = &targets{ |
| tail: init.targets, |
| _break: next, |
| } |
| b.stmt(init, decl.Body) |
| // Run function calls deferred in this init |
| // block when falling off the end of the block. |
| init.emit(new(RunDefers)) |
| emitJump(init, next) |
| init.targets = init.targets.tail |
| init.currentBlock = next |
| |
| } else if m, ok := b.globals[b.obj(id)]; ok { |
| // Package-level function. |
| b.buildFunction(m.(*Function)) |
| } |
| } |
| |
| } |
| |
| // BuildAllPackages constructs the SSA representation of the bodies of |
| // all functions in all packages known to the Builder. Construction |
| // occurs in parallel unless the BuildSerially mode flag was set. |
| // |
| // BuildAllPackages is idempotent and thread-safe. |
| // |
| func (b *Builder) BuildAllPackages() { |
| var wg sync.WaitGroup |
| for _, p := range b.Prog.Packages { |
| if b.mode&BuildSerially != 0 { |
| b.BuildPackage(p) |
| } else { |
| wg.Add(1) |
| go func(p *Package) { |
| b.BuildPackage(p) |
| wg.Done() |
| }(p) |
| } |
| } |
| wg.Wait() |
| } |
| |
| // BuildPackage builds SSA code for all functions and vars in package p. |
| // |
| // BuildPackage is idempotent and thread-safe. |
| // |
| func (b *Builder) BuildPackage(p *Package) { |
| if !atomic.CompareAndSwapInt32(&p.started, 0, 1) { |
| return // already started |
| } |
| if p.files == nil { |
| return // nothing to do |
| } |
| if b.mode&LogSource != 0 { |
| defer logStack("build package %s", p.Types.Path)() |
| } |
| init := p.Init |
| init.start(b.idents) |
| |
| // Make init() skip if package is already initialized. |
| initguard := p.Var("init·guard") |
| doinit := init.newBasicBlock("init.start") |
| done := init.newBasicBlock("init.done") |
| emitIf(init, emitLoad(init, initguard), done, doinit) |
| init.currentBlock = doinit |
| emitStore(init, initguard, vTrue) |
| |
| // TODO(gri): fix: the types.Package.Imports map may contains |
| // entries for other package's import statements, if produced |
| // by GcImport. Project it down to just the ones for us. |
| imports := make(map[string]*types.Package) |
| for _, file := range p.files { |
| for _, imp := range file.Imports { |
| path, _ := strconv.Unquote(imp.Path.Value) |
| if path != "unsafe" { |
| imports[path] = p.Types.Imports[path] |
| } |
| } |
| } |
| |
| // Call the init() function of each package we import. |
| // Order is unspecified (and is in fact nondeterministic). |
| for name, imported := range imports { |
| p2 := b.packages[imported] |
| if p2 == nil { |
| panic("Building " + p.Name() + ": CreatePackage has not been called for package " + name) |
| } |
| |
| var v Call |
| v.Func = p2.Init |
| v.Pos = init.Pos |
| v.setType(new(types.Result)) |
| init.emit(&v) |
| } |
| |
| // Visit the package's var decls and init funcs in source |
| // order. This causes init() code to be generated in |
| // topological order. We visit them transitively through |
| // functions of the same package, but we don't treat functions |
| // as roots. |
| // |
| // We also ensure all functions and methods are built, even if |
| // they are unreachable. |
| for _, file := range p.files { |
| for _, decl := range file.Decls { |
| b.buildDecl(p, decl) |
| } |
| } |
| p.files = nil |
| p.nTo1Vars = nil |
| |
| // Finish up. |
| emitJump(init, done) |
| init.currentBlock = done |
| init.emit(new(RunDefers)) |
| init.emit(new(Ret)) |
| init.finish() |
| } |