| // Copyright 2013 The Go Authors. All rights reserved. |
| // Use of this source code is governed by a BSD-style |
| // license that can be found in the LICENSE file. |
| |
| package ssa |
| |
| // This file implements the BUILD phase of SSA construction. |
| // |
| // SSA construction has two phases, CREATE and BUILD. In the CREATE phase |
| // (create.go), all packages are constructed and type-checked and |
| // definitions of all package members are created, method-sets are |
| // computed, and wrapper methods are synthesized. |
| // ssa.Packages are created in arbitrary order. |
| // |
| // In the BUILD phase (builder.go), the builder traverses the AST of |
| // each Go source function and generates SSA instructions for the |
| // function body. Initializer expressions for package-level variables |
| // are emitted to the package's init() function in the order specified |
| // by go/types.Info.InitOrder, then code for each function in the |
| // package is generated in lexical order. |
| // The BUILD phases for distinct packages are independent and are |
| // executed in parallel. |
| // |
| // TODO(adonovan): indeed, building functions is now embarrassingly parallel. |
| // Audit for concurrency then benchmark using more goroutines. |
| // |
| // State: |
| // |
| // The Package'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 and its |
| // related maps, which are protected by a dedicated mutex. |
| // |
| // Generic functions declared in a package P can be instantiated from functions |
| // outside of P. This happens independently of the CREATE and BUILD phase of P. |
| // |
| // Locks: |
| // |
| // Mutexes are currently acquired according to the following order: |
| // Prog.methodsMu ⊃ canonizer.mu ⊃ printMu |
| // where x ⊃ y denotes that y can be acquired while x is held |
| // and x cannot be acquired while y is held. |
| // |
| // Synthetics: |
| // |
| // During the BUILD phase new functions can be created and built. These include: |
| // - wrappers (wrappers, bounds, thunks) |
| // - generic function instantiations |
| // These functions do not belong to a specific Pkg (Pkg==nil). Instead the |
| // Package that led to them being CREATED is obligated to ensure these |
| // are BUILT during the BUILD phase of the Package. |
| // |
| // Runtime types: |
| // |
| // A concrete type is a type that is fully monomorphized with concrete types, |
| // i.e. it cannot reach a TypeParam type. |
| // Some concrete types require full runtime type information. Cases |
| // include checking whether a type implements an interface or |
| // interpretation by the reflect package. All such types that may require |
| // this information will have all of their method sets built and will be added to Prog.methodSets. |
| // A type T is considered to require runtime type information if it is |
| // a runtime type and has a non-empty method set and either: |
| // - T flows into a MakeInterface instructions, |
| // - T appears in a concrete exported member, or |
| // - T is a type reachable from a type S that has non-empty method set. |
| // For any such type T, method sets must be created before the BUILD |
| // phase of the package is done. |
| // |
| // Function literals: |
| // |
| // The BUILD phase of a function literal (anonymous function) is tied to the |
| // BUILD phase of the enclosing parent function. The FreeVars of an anonymous |
| // function are discovered by building the anonymous function. This in turn |
| // changes which variables must be bound in a MakeClosure instruction in the |
| // parent. Anonymous functions also track where they are referred to in their |
| // parent function. |
| // |
| // Happens-before: |
| // |
| // The above discussion leads to the following happens-before relation for |
| // the BUILD and CREATE phases. |
| // The happens-before relation (with X<Y denoting X happens-before Y) are: |
| // - CREATE fn < fn.startBody() < fn.finishBody() < fn.built |
| // for any function fn. |
| // - anon.parent.startBody() < CREATE anon, and |
| // anon.finishBody() < anon.parent().finishBody() < anon.built < fn.built |
| // for an anonymous function anon (i.e. anon.parent() != nil). |
| // - CREATE fn.Pkg < CREATE fn |
| // for a declared function fn (i.e. fn.Pkg != nil) |
| // - fn.built < BUILD pkg done |
| // for any function fn created during the CREATE or BUILD phase of a package |
| // pkg. This includes declared and synthetic functions. |
| // |
| // Program.MethodValue: |
| // |
| // Program.MethodValue may trigger new wrapper and instantiation functions to |
| // be created. It has the same obligation to BUILD created functions as a |
| // Package. |
| // |
| // Program.NewFunction: |
| // |
| // This is a low level operation for creating functions that do not exist in |
| // the source. Use with caution. |
| // |
| // TODO(taking): Use consistent terminology for "concrete". |
| // TODO(taking): Use consistent terminology for "monomorphization"/"instantiate"/"expand". |
| |
| import ( |
| "fmt" |
| "go/ast" |
| "go/constant" |
| "go/token" |
| "go/types" |
| "os" |
| "sync" |
| |
| "golang.org/x/tools/internal/typeparams" |
| ) |
| |
| type opaqueType struct { |
| types.Type |
| name string |
| } |
| |
| func (t *opaqueType) String() string { return t.name } |
| |
| var ( |
| varOk = newVar("ok", tBool) |
| varIndex = newVar("index", tInt) |
| |
| // Type constants. |
| tBool = types.Typ[types.Bool] |
| tByte = types.Typ[types.Byte] |
| tInt = types.Typ[types.Int] |
| tInvalid = types.Typ[types.Invalid] |
| tString = types.Typ[types.String] |
| tUntypedNil = types.Typ[types.UntypedNil] |
| tRangeIter = &opaqueType{nil, "iter"} // the type of all "range" iterators |
| tEface = types.NewInterfaceType(nil, nil).Complete() |
| |
| // SSA Value constants. |
| vZero = intConst(0) |
| vOne = intConst(1) |
| vTrue = NewConst(constant.MakeBool(true), tBool) |
| ) |
| |
| // builder holds state associated with the package currently being built. |
| // Its methods contain all the logic for AST-to-SSA conversion. |
| type builder struct { |
| // Invariant: 0 <= rtypes <= finished <= created.Len() |
| created *creator // functions created during building |
| finished int // Invariant: create[i].built holds for i in [0,finished) |
| rtypes int // Invariant: all of the runtime types for create[i] have been added for i in [0,rtypes) |
| } |
| |
| // 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 |
| } |
| } |
| |
| // A traditional compiler would simplify "if false" (etc) here |
| // but we do not, for better fidelity to the source code. |
| // |
| // The value of a constant condition may be platform-specific, |
| // and may cause blocks that are reachable in some configuration |
| // to be hidden from subsequent analyses such as bug-finding tools. |
| emitIf(fn, b.expr(fn, e), 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") |
| |
| // T(e) = T(e.X) = T(e.Y) after untyped constants have been |
| // eliminated. |
| // TODO(adonovan): not true; MyBool==MyBool yields UntypedBool. |
| t := fn.typeOf(e) |
| |
| var short Value // value of the short-circuit path |
| switch e.Op { |
| case token.LAND: |
| b.cond(fn, e.X, rhs, done) |
| short = NewConst(constant.MakeBool(false), t) |
| |
| case token.LOR: |
| b.cond(fn, e.X, done, rhs) |
| short = NewConst(constant.MakeBool(true), t) |
| } |
| |
| // 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 |
| |
| phi := &Phi{Edges: edges, Comment: e.Op.String()} |
| phi.pos = e.OpPos |
| phi.typ = t |
| 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.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 { |
| typ := fn.typeOf(e).(*types.Tuple) |
| 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.Call) |
| c.typ = typ |
| return fn.emit(&c) |
| |
| case *ast.IndexExpr: |
| mapt := typeparams.CoreType(fn.typeOf(e.X)).(*types.Map) // ,ok must be a map. |
| lookup := &Lookup{ |
| X: b.expr(fn, e.X), |
| Index: emitConv(fn, b.expr(fn, e.Index), mapt.Key()), |
| CommaOk: true, |
| } |
| lookup.setType(typ) |
| lookup.setPos(e.Lbrack) |
| return fn.emit(lookup) |
| |
| case *ast.TypeAssertExpr: |
| return emitTypeTest(fn, b.expr(fn, e.X), typ.At(0).Type(), e.Lparen) |
| |
| case *ast.UnaryExpr: // must be receive <- |
| unop := &UnOp{ |
| Op: token.ARROW, |
| X: b.expr(fn, e.X), |
| CommaOk: true, |
| } |
| unop.setType(typ) |
| unop.setPos(e.OpPos) |
| return fn.emit(unop) |
| } |
| panic(fmt.Sprintf("exprN(%T) in %s", e, fn)) |
| } |
| |
| // builtin emits to fn SSA instructions to implement a call to the |
| // built-in function obj 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, obj *types.Builtin, args []ast.Expr, typ types.Type, pos token.Pos) Value { |
| typ = fn.typ(typ) |
| switch obj.Name() { |
| case "make": |
| switch ct := typeparams.CoreType(typ).(type) { |
| case *types.Slice: |
| n := b.expr(fn, args[1]) |
| m := n |
| if len(args) == 3 { |
| m = b.expr(fn, args[2]) |
| } |
| if m, ok := m.(*Const); ok { |
| // treat make([]T, n, m) as new([m]T)[:n] |
| cap := m.Int64() |
| at := types.NewArray(ct.Elem(), cap) |
| alloc := emitNew(fn, at, pos) |
| alloc.Comment = "makeslice" |
| v := &Slice{ |
| X: alloc, |
| High: n, |
| } |
| v.setPos(pos) |
| v.setType(typ) |
| return fn.emit(v) |
| } |
| v := &MakeSlice{ |
| Len: n, |
| Cap: m, |
| } |
| v.setPos(pos) |
| 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.setPos(pos) |
| 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.setPos(pos) |
| v.setType(typ) |
| return fn.emit(v) |
| } |
| |
| case "new": |
| alloc := emitNew(fn, deref(typ), pos) |
| alloc.Comment = "new" |
| return alloc |
| |
| 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.) |
| // |
| // Type parameters are always non-constant so use Underlying. |
| t := deref(fn.typeOf(args[0])).Underlying() |
| if at, ok := t.(*types.Array); ok { |
| b.expr(fn, args[0]) // for effects only |
| return intConst(at.Len()) |
| } |
| // Otherwise treat as normal. |
| |
| case "panic": |
| fn.emit(&Panic{ |
| X: emitConv(fn, b.expr(fn, args[0]), tEface), |
| pos: pos, |
| }) |
| fn.currentBlock = fn.newBasicBlock("unreachable") |
| return vTrue // any non-nil Value will do |
| } |
| return nil // treat all others as a regular function call |
| } |
| |
| // 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: |
| if isBlankIdent(e) { |
| return blank{} |
| } |
| obj := fn.objectOf(e) |
| var v Value |
| if g := fn.Prog.packageLevelMember(obj); g != nil { |
| v = g.(*Global) // var (address) |
| } else { |
| v = fn.lookup(obj, escaping) |
| } |
| return &address{addr: v, pos: e.Pos(), expr: e} |
| |
| case *ast.CompositeLit: |
| t := deref(fn.typeOf(e)) |
| var v *Alloc |
| if escaping { |
| v = emitNew(fn, t, e.Lbrace) |
| } else { |
| v = fn.addLocal(t, e.Lbrace) |
| } |
| v.Comment = "complit" |
| var sb storebuf |
| b.compLit(fn, v, e, true, &sb) |
| sb.emit(fn) |
| return &address{addr: v, pos: e.Lbrace, expr: e} |
| |
| case *ast.ParenExpr: |
| return b.addr(fn, e.X, escaping) |
| |
| case *ast.SelectorExpr: |
| sel := fn.selection(e) |
| if sel == nil { |
| // qualified identifier |
| return b.addr(fn, e.Sel, escaping) |
| } |
| if sel.kind != types.FieldVal { |
| panic(sel) |
| } |
| wantAddr := true |
| v := b.receiver(fn, e.X, wantAddr, escaping, sel) |
| index := sel.index[len(sel.index)-1] |
| fld := typeparams.CoreType(deref(v.Type())).(*types.Struct).Field(index) |
| |
| // Due to the two phases of resolving AssignStmt, a panic from x.f = p() |
| // when x is nil is required to come after the side-effects of |
| // evaluating x and p(). |
| emit := func(fn *Function) Value { |
| return emitFieldSelection(fn, v, index, true, e.Sel) |
| } |
| return &lazyAddress{addr: emit, t: fld.Type(), pos: e.Sel.Pos(), expr: e.Sel} |
| |
| case *ast.IndexExpr: |
| xt := fn.typeOf(e.X) |
| elem, mode := indexType(xt) |
| var x Value |
| var et types.Type |
| switch mode { |
| case ixArrVar: // array, array|slice, array|*array, or array|*array|slice. |
| x = b.addr(fn, e.X, escaping).address(fn) |
| et = types.NewPointer(elem) |
| case ixVar: // *array, slice, *array|slice |
| x = b.expr(fn, e.X) |
| et = types.NewPointer(elem) |
| case ixMap: |
| mt := typeparams.CoreType(xt).(*types.Map) |
| return &element{ |
| m: b.expr(fn, e.X), |
| k: emitConv(fn, b.expr(fn, e.Index), mt.Key()), |
| t: mt.Elem(), |
| pos: e.Lbrack, |
| } |
| default: |
| panic("unexpected container type in IndexExpr: " + xt.String()) |
| } |
| index := b.expr(fn, e.Index) |
| if isUntyped(index.Type()) { |
| index = emitConv(fn, index, tInt) |
| } |
| // Due to the two phases of resolving AssignStmt, a panic from x[i] = p() |
| // when x is nil or i is out-of-bounds is required to come after the |
| // side-effects of evaluating x, i and p(). |
| emit := func(fn *Function) Value { |
| v := &IndexAddr{ |
| X: x, |
| Index: index, |
| } |
| v.setPos(e.Lbrack) |
| v.setType(et) |
| return fn.emit(v) |
| } |
| return &lazyAddress{addr: emit, t: deref(et), pos: e.Lbrack, expr: e} |
| |
| case *ast.StarExpr: |
| return &address{addr: b.expr(fn, e.X), pos: e.Star, expr: e} |
| } |
| |
| panic(fmt.Sprintf("unexpected address expression: %T", e)) |
| } |
| |
| type store struct { |
| lhs lvalue |
| rhs Value |
| } |
| |
| type storebuf struct{ stores []store } |
| |
| func (sb *storebuf) store(lhs lvalue, rhs Value) { |
| sb.stores = append(sb.stores, store{lhs, rhs}) |
| } |
| |
| func (sb *storebuf) emit(fn *Function) { |
| for _, s := range sb.stores { |
| s.lhs.store(fn, s.rhs) |
| } |
| } |
| |
| // assign emits to fn code to initialize the lvalue loc with the value |
| // of expression e. If isZero is true, assign assumes that loc holds |
| // the zero value for its type. |
| // |
| // 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. |
| // |
| // If sb is not nil, assign generates code to evaluate expression e, but |
| // not to update loc. Instead, the necessary stores are appended to the |
| // storebuf sb so that they can be executed later. This allows correct |
| // in-place update of existing variables when the RHS is a composite |
| // literal that may reference parts of the LHS. |
| func (b *builder) assign(fn *Function, loc lvalue, e ast.Expr, isZero bool, sb *storebuf) { |
| // Can we initialize it in place? |
| if e, ok := unparen(e).(*ast.CompositeLit); ok { |
| // A CompositeLit never evaluates to a pointer, |
| // so if the type of the location is a pointer, |
| // an &-operation is implied. |
| if _, ok := loc.(blank); !ok { // avoid calling blank.typ() |
| if isPointer(loc.typ()) { |
| ptr := b.addr(fn, e, true).address(fn) |
| // copy address |
| if sb != nil { |
| sb.store(loc, ptr) |
| } else { |
| loc.store(fn, ptr) |
| } |
| return |
| } |
| } |
| |
| if _, ok := loc.(*address); ok { |
| if isNonTypeParamInterface(loc.typ()) { |
| // e.g. var x interface{} = T{...} |
| // Can't in-place initialize an interface value. |
| // Fall back to copying. |
| } else { |
| // x = T{...} or x := T{...} |
| addr := loc.address(fn) |
| if sb != nil { |
| b.compLit(fn, addr, e, isZero, sb) |
| } else { |
| var sb storebuf |
| b.compLit(fn, addr, e, isZero, &sb) |
| sb.emit(fn) |
| } |
| |
| // Subtle: emit debug ref for aggregate types only; |
| // slice and map are handled by store ops in compLit. |
| switch loc.typ().Underlying().(type) { |
| case *types.Struct, *types.Array: |
| emitDebugRef(fn, e, addr, true) |
| } |
| |
| return |
| } |
| } |
| } |
| |
| // simple case: just copy |
| rhs := b.expr(fn, e) |
| if sb != nil { |
| sb.store(loc, rhs) |
| } else { |
| loc.store(fn, rhs) |
| } |
| } |
| |
| // 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 { |
| e = unparen(e) |
| |
| tv := fn.info.Types[e] |
| |
| // Is expression a constant? |
| if tv.Value != nil { |
| return NewConst(tv.Value, fn.typ(tv.Type)) |
| } |
| |
| var v Value |
| if tv.Addressable() { |
| // Prefer pointer arithmetic ({Index,Field}Addr) followed |
| // by Load over subelement extraction (e.g. Index, Field), |
| // to avoid large copies. |
| v = b.addr(fn, e, false).load(fn) |
| } else { |
| v = b.expr0(fn, e, tv) |
| } |
| if fn.debugInfo() { |
| emitDebugRef(fn, e, v, false) |
| } |
| return v |
| } |
| |
| func (b *builder) expr0(fn *Function, e ast.Expr, tv types.TypeAndValue) Value { |
| switch e := e.(type) { |
| case *ast.BasicLit: |
| panic("non-constant BasicLit") // unreachable |
| |
| case *ast.FuncLit: |
| fn2 := &Function{ |
| name: fmt.Sprintf("%s$%d", fn.Name(), 1+len(fn.AnonFuncs)), |
| Signature: fn.typeOf(e.Type).(*types.Signature), |
| pos: e.Type.Func, |
| parent: fn, |
| anonIdx: int32(len(fn.AnonFuncs)), |
| Pkg: fn.Pkg, |
| Prog: fn.Prog, |
| syntax: e, |
| topLevelOrigin: nil, // use anonIdx to lookup an anon instance's origin. |
| typeparams: fn.typeparams, // share the parent's type parameters. |
| typeargs: fn.typeargs, // share the parent's type arguments. |
| info: fn.info, |
| subst: fn.subst, // share the parent's type substitutions. |
| } |
| fn.AnonFuncs = append(fn.AnonFuncs, fn2) |
| b.created.Add(fn2) |
| b.buildFunctionBody(fn2) |
| // fn2 is not done BUILDing. fn2.referrers can still be updated. |
| // fn2 is done BUILDing after fn.finishBody(). |
| if fn2.FreeVars == nil { |
| return fn2 |
| } |
| v := &MakeClosure{Fn: fn2} |
| v.setType(fn.typ(tv.Type)) |
| for _, fv := range fn2.FreeVars { |
| v.Bindings = append(v.Bindings, fv.outer) |
| fv.outer = nil |
| } |
| return fn.emit(v) |
| |
| case *ast.TypeAssertExpr: // single-result form only |
| return emitTypeAssert(fn, b.expr(fn, e.X), fn.typ(tv.Type), e.Lparen) |
| |
| case *ast.CallExpr: |
| if fn.info.Types[e.Fun].IsType() { |
| // Explicit type conversion, e.g. string(x) or big.Int(x) |
| x := b.expr(fn, e.Args[0]) |
| y := emitConv(fn, x, fn.typ(tv.Type)) |
| if y != x { |
| switch y := y.(type) { |
| case *Convert: |
| y.pos = e.Lparen |
| case *ChangeType: |
| y.pos = e.Lparen |
| case *MakeInterface: |
| y.pos = e.Lparen |
| case *SliceToArrayPointer: |
| y.pos = e.Lparen |
| case *UnOp: // conversion from slice to array. |
| y.pos = e.Lparen |
| } |
| } |
| return y |
| } |
| // Call to "intrinsic" built-ins, e.g. new, make, panic. |
| if id, ok := unparen(e.Fun).(*ast.Ident); ok { |
| if obj, ok := fn.info.Uses[id].(*types.Builtin); ok { |
| if v := b.builtin(fn, obj, e.Args, fn.typ(tv.Type), e.Lparen); v != nil { |
| return v |
| } |
| } |
| } |
| // Regular function call. |
| var v Call |
| b.setCall(fn, e, &v.Call) |
| v.setType(fn.typ(tv.Type)) |
| return fn.emit(&v) |
| |
| case *ast.UnaryExpr: |
| switch e.Op { |
| case token.AND: // &X --- potentially escaping. |
| addr := b.addr(fn, e.X, true) |
| if _, ok := unparen(e.X).(*ast.StarExpr); ok { |
| // &*p must panic if p is nil (http://golang.org/s/go12nil). |
| // For simplicity, we'll just (suboptimally) rely |
| // on the side effects of a load. |
| // TODO(adonovan): emit dedicated nilcheck. |
| addr.load(fn) |
| } |
| return addr.address(fn) |
| 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.setPos(e.OpPos) |
| v.setType(fn.typ(tv.Type)) |
| 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), fn.typ(tv.Type), e.OpPos) |
| |
| case token.EQL, token.NEQ, token.GTR, token.LSS, token.LEQ, token.GEQ: |
| cmp := emitCompare(fn, e.Op, b.expr(fn, e.X), b.expr(fn, e.Y), e.OpPos) |
| // The type of x==y may be UntypedBool. |
| return emitConv(fn, cmp, types.Default(fn.typ(tv.Type))) |
| default: |
| panic("illegal op in BinaryExpr: " + e.Op.String()) |
| } |
| |
| case *ast.SliceExpr: |
| var low, high, max Value |
| var x Value |
| xtyp := fn.typeOf(e.X) |
| switch typeparams.CoreType(xtyp).(type) { |
| case *types.Array: |
| // Potentially escaping. |
| x = b.addr(fn, e.X, true).address(fn) |
| case *types.Basic, *types.Slice, *types.Pointer: // *array |
| x = b.expr(fn, e.X) |
| default: |
| // core type exception? |
| if isBytestring(xtyp) { |
| x = b.expr(fn, e.X) // bytestring is handled as string and []byte. |
| } else { |
| panic("unexpected sequence type in SliceExpr") |
| } |
| } |
| if e.Low != nil { |
| low = b.expr(fn, e.Low) |
| } |
| if e.High != nil { |
| high = b.expr(fn, e.High) |
| } |
| if e.Slice3 { |
| max = b.expr(fn, e.Max) |
| } |
| v := &Slice{ |
| X: x, |
| Low: low, |
| High: high, |
| Max: max, |
| } |
| v.setPos(e.Lbrack) |
| v.setType(fn.typ(tv.Type)) |
| return fn.emit(v) |
| |
| case *ast.Ident: |
| obj := fn.info.Uses[e] |
| // Universal built-in or nil? |
| switch obj := obj.(type) { |
| case *types.Builtin: |
| return &Builtin{name: obj.Name(), sig: fn.instanceType(e).(*types.Signature)} |
| case *types.Nil: |
| return zeroConst(fn.instanceType(e)) |
| } |
| // Package-level func or var? |
| if v := fn.Prog.packageLevelMember(obj); v != nil { |
| if g, ok := v.(*Global); ok { |
| return emitLoad(fn, g) // var (address) |
| } |
| callee := v.(*Function) // (func) |
| if callee.typeparams.Len() > 0 { |
| targs := fn.subst.types(instanceArgs(fn.info, e)) |
| callee = fn.Prog.needsInstance(callee, targs, b.created) |
| } |
| return callee |
| } |
| // Local var. |
| return emitLoad(fn, fn.lookup(obj, false)) // var (address) |
| |
| case *ast.SelectorExpr: |
| sel := fn.selection(e) |
| if sel == nil { |
| // builtin unsafe.{Add,Slice} |
| if obj, ok := fn.info.Uses[e.Sel].(*types.Builtin); ok { |
| return &Builtin{name: obj.Name(), sig: fn.typ(tv.Type).(*types.Signature)} |
| } |
| // qualified identifier |
| return b.expr(fn, e.Sel) |
| } |
| switch sel.kind { |
| case types.MethodExpr: |
| // (*T).f or T.f, the method f from the method-set of type T. |
| // The result is a "thunk". |
| thunk := makeThunk(fn.Prog, sel, b.created) |
| return emitConv(fn, thunk, fn.typ(tv.Type)) |
| |
| case types.MethodVal: |
| // e.f where e is an expression and f is a method. |
| // The result is a "bound". |
| obj := sel.obj.(*types.Func) |
| rt := fn.typ(recvType(obj)) |
| wantAddr := isPointer(rt) |
| escaping := true |
| v := b.receiver(fn, e.X, wantAddr, escaping, sel) |
| |
| if types.IsInterface(rt) { |
| // If v may be an interface type I (after instantiating), |
| // we must emit a check that v is non-nil. |
| if recv, ok := sel.recv.(*typeparams.TypeParam); ok { |
| // Emit a nil check if any possible instantiation of the |
| // type parameter is an interface type. |
| if typeSetOf(recv).Len() > 0 { |
| // recv has a concrete term its typeset. |
| // So it cannot be instantiated as an interface. |
| // |
| // Example: |
| // func _[T interface{~int; Foo()}] () { |
| // var v T |
| // _ = v.Foo // <-- MethodVal |
| // } |
| } else { |
| // rt may be instantiated as an interface. |
| // Emit nil check: typeassert (any(v)).(any). |
| emitTypeAssert(fn, emitConv(fn, v, tEface), tEface, token.NoPos) |
| } |
| } else { |
| // non-type param interface |
| // Emit nil check: typeassert v.(I). |
| emitTypeAssert(fn, v, rt, token.NoPos) |
| } |
| } |
| if targs := receiverTypeArgs(obj); len(targs) > 0 { |
| // obj is generic. |
| obj = fn.Prog.canon.instantiateMethod(obj, fn.subst.types(targs), fn.Prog.ctxt) |
| } |
| c := &MakeClosure{ |
| Fn: makeBound(fn.Prog, obj, b.created), |
| Bindings: []Value{v}, |
| } |
| c.setPos(e.Sel.Pos()) |
| c.setType(fn.typ(tv.Type)) |
| return fn.emit(c) |
| |
| case types.FieldVal: |
| indices := sel.index |
| last := len(indices) - 1 |
| v := b.expr(fn, e.X) |
| v = emitImplicitSelections(fn, v, indices[:last], e.Pos()) |
| v = emitFieldSelection(fn, v, indices[last], false, e.Sel) |
| return v |
| } |
| |
| panic("unexpected expression-relative selector") |
| |
| case *typeparams.IndexListExpr: |
| // f[X, Y] must be a generic function |
| if !instance(fn.info, e.X) { |
| panic("unexpected expression-could not match index list to instantiation") |
| } |
| return b.expr(fn, e.X) // Handle instantiation within the *Ident or *SelectorExpr cases. |
| |
| case *ast.IndexExpr: |
| if instance(fn.info, e.X) { |
| return b.expr(fn, e.X) // Handle instantiation within the *Ident or *SelectorExpr cases. |
| } |
| // not a generic instantiation. |
| xt := fn.typeOf(e.X) |
| switch et, mode := indexType(xt); mode { |
| case ixVar: |
| // Addressable slice/array; use IndexAddr and Load. |
| return b.addr(fn, e, false).load(fn) |
| |
| case ixArrVar, ixValue: |
| // An array in a register, a string or a combined type that contains |
| // either an [_]array (ixArrVar) or string (ixValue). |
| |
| // Note: for ixArrVar and CoreType(xt)==nil can be IndexAddr and Load. |
| index := b.expr(fn, e.Index) |
| if isUntyped(index.Type()) { |
| index = emitConv(fn, index, tInt) |
| } |
| v := &Index{ |
| X: b.expr(fn, e.X), |
| Index: index, |
| } |
| v.setPos(e.Lbrack) |
| v.setType(et) |
| return fn.emit(v) |
| |
| case ixMap: |
| ct := typeparams.CoreType(xt).(*types.Map) |
| v := &Lookup{ |
| X: b.expr(fn, e.X), |
| Index: emitConv(fn, b.expr(fn, e.Index), ct.Key()), |
| } |
| v.setPos(e.Lbrack) |
| v.setType(ct.Elem()) |
| return fn.emit(v) |
| default: |
| panic("unexpected container type in IndexExpr: " + xt.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) |
| } |
| } |
| |
| // receiver emits to fn code for expression e in the "receiver" |
| // position of selection e.f (where f may be a field or a method) and |
| // returns the effective receiver after applying the implicit field |
| // selections of sel. |
| // |
| // wantAddr requests that the result is an an address. If |
| // !sel.indirect, this may require that e be built in addr() mode; it |
| // must thus be addressable. |
| // |
| // escaping is defined as per builder.addr(). |
| func (b *builder) receiver(fn *Function, e ast.Expr, wantAddr, escaping bool, sel *selection) Value { |
| var v Value |
| if wantAddr && !sel.indirect && !isPointer(fn.typeOf(e)) { |
| v = b.addr(fn, e, escaping).address(fn) |
| } else { |
| v = b.expr(fn, e) |
| } |
| |
| last := len(sel.index) - 1 |
| // The position of implicit selection is the position of the inducing receiver expression. |
| v = emitImplicitSelections(fn, v, sel.index[:last], e.Pos()) |
| if !wantAddr && isPointer(v.Type()) { |
| v = emitLoad(fn, v) |
| } |
| return v |
| } |
| |
| // 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 this a method call? |
| if selector, ok := unparen(e.Fun).(*ast.SelectorExpr); ok { |
| sel := fn.selection(selector) |
| if sel != nil && sel.kind == types.MethodVal { |
| obj := sel.obj.(*types.Func) |
| recv := recvType(obj) |
| |
| wantAddr := isPointer(recv) |
| escaping := true |
| v := b.receiver(fn, selector.X, wantAddr, escaping, sel) |
| if types.IsInterface(recv) { |
| // Invoke-mode call. |
| c.Value = v // possibly type param |
| c.Method = obj |
| } else { |
| // "Call"-mode call. |
| callee := fn.Prog.originFunc(obj) |
| if callee.typeparams.Len() > 0 { |
| callee = fn.Prog.needsInstance(callee, receiverTypeArgs(obj), b.created) |
| } |
| c.Value = callee |
| c.Args = append(c.Args, v) |
| } |
| return |
| } |
| |
| // sel.kind==MethodExpr indicates T.f() or (*T).f(): |
| // a statically dispatched call to the method f in the |
| // method-set of T or *T. T may be an interface. |
| // |
| // e.Fun would evaluate to a concrete method, interface |
| // wrapper function, or promotion wrapper. |
| // |
| // For now, we evaluate it in the usual way. |
| // |
| // TODO(adonovan): opt: inline expr() here, to make the |
| // call static and to avoid generation of wrappers. |
| // It's somewhat tricky as it may consume the first |
| // actual parameter if the call is "invoke" mode. |
| // |
| // Examples: |
| // type T struct{}; func (T) f() {} // "call" mode |
| // type T interface { f() } // "invoke" mode |
| // |
| // type S struct{ T } |
| // |
| // var s S |
| // S.f(s) |
| // (*S).f(&s) |
| // |
| // Suggested approach: |
| // - consume the first actual parameter expression |
| // and build it with b.expr(). |
| // - apply implicit field selections. |
| // - use MethodVal logic to populate fields of c. |
| } |
| |
| // Evaluate the function operand in the usual way. |
| c.Value = b.expr(fn, e.Fun) |
| } |
| |
| // emitCallArgs emits to f code for the actual parameters of call e to |
| // a (possibly built-in) function of effective type sig. |
| // The argument values are appended to args, which is then returned. |
| func (b *builder) emitCallArgs(fn *Function, sig *types.Signature, e *ast.CallExpr, args []Value) []Value { |
| // f(x, y, z...): pass slice z straight through. |
| if e.Ellipsis != 0 { |
| for i, arg := range e.Args { |
| v := emitConv(fn, b.expr(fn, arg), sig.Params().At(i).Type()) |
| args = append(args, v) |
| } |
| return args |
| } |
| |
| offset := len(args) // 1 if call has receiver, 0 otherwise |
| |
| // Evaluate actual parameter expressions. |
| // |
| // If this is a chained call of the form f(g()) where g has |
| // multiple return values (MRV), they are flattened out into |
| // args; a suffix of them may end up in a varargs slice. |
| for _, arg := range e.Args { |
| v := b.expr(fn, arg) |
| if ttuple, ok := v.Type().(*types.Tuple); ok { // MRV chain |
| for i, n := 0, ttuple.Len(); i < n; i++ { |
| args = append(args, emitExtract(fn, v, i)) |
| } |
| } else { |
| args = append(args, v) |
| } |
| } |
| |
| // Actual->formal assignability conversions for normal parameters. |
| np := sig.Params().Len() // number of normal parameters |
| if sig.Variadic() { |
| np-- |
| } |
| for i := 0; i < np; i++ { |
| args[offset+i] = emitConv(fn, args[offset+i], sig.Params().At(i).Type()) |
| } |
| |
| // Actual->formal assignability conversions for variadic parameter, |
| // and construction of slice. |
| if sig.Variadic() { |
| varargs := args[offset+np:] |
| st := sig.Params().At(np).Type().(*types.Slice) |
| vt := st.Elem() |
| if len(varargs) == 0 { |
| args = append(args, zeroConst(st)) |
| } else { |
| // Replace a suffix of args with a slice containing it. |
| at := types.NewArray(vt, int64(len(varargs))) |
| a := emitNew(fn, at, token.NoPos) |
| a.setPos(e.Rparen) |
| a.Comment = "varargs" |
| for i, arg := range varargs { |
| iaddr := &IndexAddr{ |
| X: a, |
| Index: intConst(int64(i)), |
| } |
| iaddr.setType(types.NewPointer(vt)) |
| fn.emit(iaddr) |
| emitStore(fn, iaddr, arg, arg.Pos()) |
| } |
| s := &Slice{X: a} |
| s.setType(st) |
| args[offset+np] = fn.emit(s) |
| args = args[:offset+np+1] |
| } |
| } |
| return args |
| } |
| |
| // 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 and optional receiver. |
| b.setCallFunc(fn, e, c) |
| |
| // Then append the other actual parameters. |
| sig, _ := typeparams.CoreType(fn.typeOf(e.Fun)).(*types.Signature) |
| if sig == nil { |
| panic(fmt.Sprintf("no signature for call of %s", e.Fun)) |
| } |
| c.Args = b.emitCallArgs(fn, sig, e, c.Args) |
| } |
| |
| // assignOp emits to fn code to perform loc <op>= val. |
| func (b *builder) assignOp(fn *Function, loc lvalue, val Value, op token.Token, pos token.Pos) { |
| loc.store(fn, emitArith(fn, op, loc.load(fn), val, loc.typ(), pos)) |
| } |
| |
| // localValueSpec emits to fn code to define all of the vars in the |
| // function-local ValueSpec, spec. |
| 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 { |
| if !isBlankIdent(id) { |
| fn.addLocalForIdent(id) |
| } |
| lval := b.addr(fn, id, false) // non-escaping |
| b.assign(fn, lval, spec.Values[i], true, nil) |
| } |
| |
| case len(spec.Values) == 0: |
| // e.g. var x, y int |
| // Locals are implicitly zero-initialized. |
| for _, id := range spec.Names { |
| if !isBlankIdent(id) { |
| lhs := fn.addLocalForIdent(id) |
| if fn.debugInfo() { |
| emitDebugRef(fn, id, lhs, true) |
| } |
| } |
| } |
| |
| default: |
| // e.g. var x, y = pos() |
| tuple := b.exprN(fn, spec.Values[0]) |
| for i, id := range spec.Names { |
| if !isBlankIdent(id) { |
| fn.addLocalForIdent(id) |
| lhs := b.addr(fn, id, false) // non-escaping |
| lhs.store(fn, emitExtract(fn, tuple, i)) |
| } |
| } |
| } |
| } |
| |
| // 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. |
| lvals := make([]lvalue, len(lhss)) |
| isZero := make([]bool, len(lhss)) |
| for i, lhs := range lhss { |
| var lval lvalue = blank{} |
| if !isBlankIdent(lhs) { |
| if isDef { |
| if obj := fn.info.Defs[lhs.(*ast.Ident)]; obj != nil { |
| fn.addNamedLocal(obj) |
| isZero[i] = true |
| } |
| } |
| lval = b.addr(fn, lhs, false) // non-escaping |
| } |
| lvals[i] = lval |
| } |
| if len(lhss) == len(rhss) { |
| // Simple assignment: x = f() (!isDef) |
| // Parallel assignment: x, y = f(), g() (!isDef) |
| // or short var decl: x, y := f(), g() (isDef) |
| // |
| // In all cases, the RHSs may refer to the LHSs, |
| // so we need a storebuf. |
| var sb storebuf |
| for i := range rhss { |
| b.assign(fn, lvals[i], rhss[i], isZero[i], &sb) |
| } |
| sb.emit(fn) |
| } else { |
| // e.g. x, y = pos() |
| tuple := b.exprN(fn, rhss[0]) |
| emitDebugRef(fn, rhss[0], tuple, false) |
| for i, lval := range lvals { |
| lval.store(fn, emitExtract(fn, tuple, i)) |
| } |
| } |
| } |
| |
| // arrayLen returns the length of the array whose composite literal elements are elts. |
| func (b *builder) arrayLen(fn *Function, elts []ast.Expr) int64 { |
| var max int64 = -1 |
| var i int64 = -1 |
| for _, e := range elts { |
| if kv, ok := e.(*ast.KeyValueExpr); ok { |
| i = b.expr(fn, kv.Key).(*Const).Int64() |
| } else { |
| i++ |
| } |
| if i > max { |
| max = i |
| } |
| } |
| return max + 1 |
| } |
| |
| // compLit emits to fn code to initialize a composite literal e at |
| // address addr with type typ. |
| // |
| // Nested composite literals are recursively initialized in place |
| // where possible. If isZero is true, compLit assumes that addr |
| // holds the zero value for typ. |
| // |
| // Because the elements of a composite literal may refer to the |
| // variables being updated, as in the second line below, |
| // |
| // x := T{a: 1} |
| // x = T{a: x.a} |
| // |
| // all the reads must occur before all the writes. Thus all stores to |
| // loc are emitted to the storebuf sb for later execution. |
| // |
| // A CompositeLit may have pointer type only in the recursive (nested) |
| // case when the type name is implicit. e.g. in []*T{{}}, the inner |
| // literal has type *T behaves like &T{}. |
| // In that case, addr must hold a T, not a *T. |
| func (b *builder) compLit(fn *Function, addr Value, e *ast.CompositeLit, isZero bool, sb *storebuf) { |
| typ := deref(fn.typeOf(e)) // type with name [may be type param] |
| t := deref(typeparams.CoreType(typ)).Underlying() // core type for comp lit case |
| // Computing typ and t is subtle as these handle pointer types. |
| // For example, &T{...} is valid even for maps and slices. |
| // Also typ should refer to T (not *T) while t should be the core type of T. |
| // |
| // To show the ordering to take into account, consider the composite literal |
| // expressions `&T{f: 1}` and `{f: 1}` within the expression `[]S{{f: 1}}` here: |
| // type N struct{f int} |
| // func _[T N, S *N]() { |
| // _ = &T{f: 1} |
| // _ = []S{{f: 1}} |
| // } |
| // For `&T{f: 1}`, we compute `typ` and `t` as: |
| // typeOf(&T{f: 1}) == *T |
| // deref(*T) == T (typ) |
| // CoreType(T) == N |
| // deref(N) == N |
| // N.Underlying() == struct{f int} (t) |
| // For `{f: 1}` in `[]S{{f: 1}}`, we compute `typ` and `t` as: |
| // typeOf({f: 1}) == S |
| // deref(S) == S (typ) |
| // CoreType(S) == *N |
| // deref(*N) == N |
| // N.Underlying() == struct{f int} (t) |
| switch t := t.(type) { |
| case *types.Struct: |
| if !isZero && len(e.Elts) != t.NumFields() { |
| // memclear |
| sb.store(&address{addr, e.Lbrace, nil}, zeroConst(deref(addr.Type()))) |
| isZero = true |
| } |
| for i, e := range e.Elts { |
| fieldIndex := i |
| pos := e.Pos() |
| if kv, ok := e.(*ast.KeyValueExpr); ok { |
| fname := kv.Key.(*ast.Ident).Name |
| for i, n := 0, t.NumFields(); i < n; i++ { |
| sf := t.Field(i) |
| if sf.Name() == fname { |
| fieldIndex = i |
| pos = kv.Colon |
| e = kv.Value |
| break |
| } |
| } |
| } |
| sf := t.Field(fieldIndex) |
| faddr := &FieldAddr{ |
| X: addr, |
| Field: fieldIndex, |
| } |
| faddr.setPos(pos) |
| faddr.setType(types.NewPointer(sf.Type())) |
| fn.emit(faddr) |
| b.assign(fn, &address{addr: faddr, pos: pos, expr: e}, e, isZero, sb) |
| } |
| |
| case *types.Array, *types.Slice: |
| var at *types.Array |
| var array Value |
| switch t := t.(type) { |
| case *types.Slice: |
| at = types.NewArray(t.Elem(), b.arrayLen(fn, e.Elts)) |
| alloc := emitNew(fn, at, e.Lbrace) |
| alloc.Comment = "slicelit" |
| array = alloc |
| case *types.Array: |
| at = t |
| array = addr |
| |
| if !isZero && int64(len(e.Elts)) != at.Len() { |
| // memclear |
| sb.store(&address{array, e.Lbrace, nil}, zeroConst(deref(array.Type()))) |
| } |
| } |
| |
| var idx *Const |
| for _, e := range e.Elts { |
| pos := e.Pos() |
| if kv, ok := e.(*ast.KeyValueExpr); ok { |
| idx = b.expr(fn, kv.Key).(*Const) |
| pos = kv.Colon |
| e = kv.Value |
| } else { |
| var idxval int64 |
| if idx != nil { |
| idxval = idx.Int64() + 1 |
| } |
| idx = intConst(idxval) |
| } |
| iaddr := &IndexAddr{ |
| X: array, |
| Index: idx, |
| } |
| iaddr.setType(types.NewPointer(at.Elem())) |
| fn.emit(iaddr) |
| if t != at { // slice |
| // backing array is unaliased => storebuf not needed. |
| b.assign(fn, &address{addr: iaddr, pos: pos, expr: e}, e, true, nil) |
| } else { |
| b.assign(fn, &address{addr: iaddr, pos: pos, expr: e}, e, true, sb) |
| } |
| } |
| |
| if t != at { // slice |
| s := &Slice{X: array} |
| s.setPos(e.Lbrace) |
| s.setType(typ) |
| sb.store(&address{addr: addr, pos: e.Lbrace, expr: e}, fn.emit(s)) |
| } |
| |
| case *types.Map: |
| m := &MakeMap{Reserve: intConst(int64(len(e.Elts)))} |
| m.setPos(e.Lbrace) |
| m.setType(typ) |
| fn.emit(m) |
| for _, e := range e.Elts { |
| e := e.(*ast.KeyValueExpr) |
| |
| // If a key expression in a map literal is itself a |
| // composite literal, the type may be omitted. |
| // For example: |
| // map[*struct{}]bool{{}: true} |
| // An &-operation may be implied: |
| // map[*struct{}]bool{&struct{}{}: true} |
| var key Value |
| if _, ok := unparen(e.Key).(*ast.CompositeLit); ok && isPointer(t.Key()) { |
| // A CompositeLit never evaluates to a pointer, |
| // so if the type of the location is a pointer, |
| // an &-operation is implied. |
| key = b.addr(fn, e.Key, true).address(fn) |
| } else { |
| key = b.expr(fn, e.Key) |
| } |
| |
| loc := element{ |
| m: m, |
| k: emitConv(fn, key, t.Key()), |
| t: t.Elem(), |
| pos: e.Colon, |
| } |
| |
| // We call assign() only because it takes care |
| // of any &-operation required in the recursive |
| // case, e.g., |
| // map[int]*struct{}{0: {}} implies &struct{}{}. |
| // In-place update is of course impossible, |
| // and no storebuf is needed. |
| b.assign(fn, &loc, e.Value, true, nil) |
| } |
| sb.store(&address{addr: addr, pos: e.Lbrace, expr: e}, m) |
| |
| 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. |
| // Multiway dispatch can be recovered later by ssautil.Switches() |
| // to those cases that 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 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), cond.Pos()) |
| 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. |
| // Multiway dispatch can be recovered later by ssautil.Switches(). |
| |
| // Typeswitch lowering: |
| // |
| // var x X |
| // switch y := x.(type) { |
| // case T1, T2: S1 // >1 (y := x) |
| // case nil: SN // nil (y := x) |
| // default: SD // 0 types (y := x) |
| // case T3: S3 // 1 type (y := x.(T3)) |
| // } |
| // |
| // ...s.Init... |
| // x := eval 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 .caseNil |
| // .S1: |
| // y := x |
| // ...S1... |
| // goto done |
| // .caseNil: |
| // if t2, ok2 := typeswitch,ok x <T2> |
| // if x == nil then goto SN else goto .caseT3 |
| // .SN: |
| // y := x |
| // ...SN... |
| // goto done |
| // .caseT3: |
| // t3, ok3 := typeswitch,ok x <T3> |
| // if ok3 then goto S3 else goto default |
| // .S3: |
| // y := t3 |
| // ...S3... |
| // goto done |
| // .default: |
| // y := x |
| // ...SD... |
| // goto done |
| // .done: |
| if s.Init != nil { |
| b.stmt(fn, s.Init) |
| } |
| |
| var x Value |
| switch ass := s.Assign.(type) { |
| case *ast.ExprStmt: // x.(type) |
| x = b.expr(fn, unparen(ass.X).(*ast.TypeAssertExpr).X) |
| case *ast.AssignStmt: // y := x.(type) |
| x = b.expr(fn, unparen(ass.Rhs[0]).(*ast.TypeAssertExpr).X) |
| } |
| |
| done := fn.newBasicBlock("typeswitch.done") |
| if label != nil { |
| label._break = done |
| } |
| var default_ *ast.CaseClause |
| for _, clause := range s.Body.List { |
| cc := clause.(*ast.CaseClause) |
| if cc.List == nil { |
| default_ = cc |
| continue |
| } |
| body := fn.newBasicBlock("typeswitch.body") |
| var next *BasicBlock |
| var casetype types.Type |
| var ti Value // ti, ok := typeassert,ok x <Ti> |
| for _, cond := range cc.List { |
| next = fn.newBasicBlock("typeswitch.next") |
| casetype = fn.typeOf(cond) |
| var condv Value |
| if casetype == tUntypedNil { |
| condv = emitCompare(fn, token.EQL, x, zeroConst(x.Type()), cond.Pos()) |
| ti = x |
| } else { |
| yok := emitTypeTest(fn, x, casetype, cc.Case) |
| ti = emitExtract(fn, yok, 0) |
| condv = emitExtract(fn, yok, 1) |
| } |
| emitIf(fn, condv, body, next) |
| fn.currentBlock = next |
| } |
| if len(cc.List) != 1 { |
| ti = x |
| } |
| fn.currentBlock = body |
| b.typeCaseBody(fn, cc, ti, done) |
| fn.currentBlock = next |
| } |
| if default_ != nil { |
| b.typeCaseBody(fn, default_, x, done) |
| } else { |
| emitJump(fn, done) |
| } |
| fn.currentBlock = done |
| } |
| |
| func (b *builder) typeCaseBody(fn *Function, cc *ast.CaseClause, x Value, done *BasicBlock) { |
| if obj := fn.info.Implicits[cc]; obj != nil { |
| // In a switch y := x.(type), each case clause |
| // implicitly declares a distinct object y. |
| // In a single-type case, y has that type. |
| // In multi-type cases, 'case nil' and default, |
| // y has the same type as the interface operand. |
| emitStore(fn, fn.addNamedLocal(obj), x, obj.Pos()) |
| } |
| fn.targets = &targets{ |
| tail: fn.targets, |
| _break: done, |
| } |
| b.stmtList(fn, cc.Body) |
| fn.targets = fn.targets.tail |
| emitJump(fn, 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 |
| debugInfo := fn.debugInfo() |
| for _, clause := range s.Body.List { |
| var st *SelectState |
| switch comm := clause.(*ast.CommClause).Comm.(type) { |
| case nil: // default case |
| blocking = false |
| continue |
| |
| case *ast.SendStmt: // ch<- i |
| ch := b.expr(fn, comm.Chan) |
| chtyp := typeparams.CoreType(fn.typ(ch.Type())).(*types.Chan) |
| st = &SelectState{ |
| Dir: types.SendOnly, |
| Chan: ch, |
| Send: emitConv(fn, b.expr(fn, comm.Value), chtyp.Elem()), |
| Pos: comm.Arrow, |
| } |
| if debugInfo { |
| st.DebugNode = comm |
| } |
| |
| case *ast.AssignStmt: // x := <-ch |
| recv := unparen(comm.Rhs[0]).(*ast.UnaryExpr) |
| st = &SelectState{ |
| Dir: types.RecvOnly, |
| Chan: b.expr(fn, recv.X), |
| Pos: recv.OpPos, |
| } |
| if debugInfo { |
| st.DebugNode = recv |
| } |
| |
| case *ast.ExprStmt: // <-ch |
| recv := unparen(comm.X).(*ast.UnaryExpr) |
| st = &SelectState{ |
| Dir: types.RecvOnly, |
| Chan: b.expr(fn, recv.X), |
| Pos: recv.OpPos, |
| } |
| if debugInfo { |
| st.DebugNode = recv |
| } |
| } |
| states = append(states, st) |
| } |
| |
| // We dispatch on the (fair) result of Select using a |
| // sequential if-else chain, in effect: |
| // |
| // idx, recvOk, r0...r_n-1 := select(...) |
| // if idx == 0 { // receive on channel 0 (first receive => r0) |
| // x, ok := r0, recvOk |
| // ...state0... |
| // } else if v == 1 { // send on channel 1 |
| // ...state1... |
| // } else { |
| // ...default... |
| // } |
| sel := &Select{ |
| States: states, |
| Blocking: blocking, |
| } |
| sel.setPos(s.Select) |
| var vars []*types.Var |
| vars = append(vars, varIndex, varOk) |
| for _, st := range states { |
| if st.Dir == types.RecvOnly { |
| chtyp := typeparams.CoreType(fn.typ(st.Chan.Type())).(*types.Chan) |
| vars = append(vars, anonVar(chtyp.Elem())) |
| } |
| } |
| sel.setType(types.NewTuple(vars...)) |
| |
| fn.emit(sel) |
| idx := emitExtract(fn, sel, 0) |
| |
| done := fn.newBasicBlock("select.done") |
| if label != nil { |
| label._break = done |
| } |
| |
| var defaultBody *[]ast.Stmt |
| state := 0 |
| r := 2 // index in 'sel' tuple of value; increments if st.Dir==RECV |
| for _, cc := range s.Body.List { |
| clause := cc.(*ast.CommClause) |
| if clause.Comm == nil { |
| defaultBody = &clause.Body |
| continue |
| } |
| body := fn.newBasicBlock("select.body") |
| next := fn.newBasicBlock("select.next") |
| emitIf(fn, emitCompare(fn, token.EQL, idx, intConst(int64(state)), token.NoPos), body, next) |
| fn.currentBlock = body |
| fn.targets = &targets{ |
| tail: fn.targets, |
| _break: done, |
| } |
| switch comm := clause.Comm.(type) { |
| case *ast.ExprStmt: // <-ch |
| if debugInfo { |
| v := emitExtract(fn, sel, r) |
| emitDebugRef(fn, states[state].DebugNode.(ast.Expr), v, false) |
| } |
| r++ |
| |
| case *ast.AssignStmt: // x := <-states[state].Chan |
| if comm.Tok == token.DEFINE { |
| fn.addLocalForIdent(comm.Lhs[0].(*ast.Ident)) |
| } |
| x := b.addr(fn, comm.Lhs[0], false) // non-escaping |
| v := emitExtract(fn, sel, r) |
| if debugInfo { |
| emitDebugRef(fn, states[state].DebugNode.(ast.Expr), v, false) |
| } |
| x.store(fn, v) |
| |
| if len(comm.Lhs) == 2 { // x, ok := ... |
| if comm.Tok == token.DEFINE { |
| fn.addLocalForIdent(comm.Lhs[1].(*ast.Ident)) |
| } |
| ok := b.addr(fn, comm.Lhs[1], false) // non-escaping |
| ok.store(fn, emitExtract(fn, sel, 1)) |
| } |
| r++ |
| } |
| b.stmtList(fn, clause.Body) |
| fn.targets = fn.targets.tail |
| emitJump(fn, done) |
| fn.currentBlock = next |
| state++ |
| } |
| if defaultBody != nil { |
| fn.targets = &targets{ |
| tail: fn.targets, |
| _break: done, |
| } |
| b.stmtList(fn, *defaultBody) |
| fn.targets = fn.targets.tail |
| } else { |
| // A blocking select must match some case. |
| // (This should really be a runtime.errorString, not a string.) |
| fn.emit(&Panic{ |
| X: emitConv(fn, stringConst("blocking select matched no case"), tEface), |
| }) |
| fn.currentBlock = fn.newBasicBlock("unreachable") |
| } |
| 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. |
| // forPos is the position of the "for" token. |
| func (b *builder) rangeIndexed(fn *Function, x Value, tv types.Type, pos token.Pos) (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()).Underlying().(*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. |
| // We still generate code for x, in case it has effects. |
| // |
| // TypeParams do not have constant length. Use underlying instead of core type. |
| length = intConst(arr.Len()) |
| } else { |
| // length = len(x). |
| var c Call |
| c.Call.Value = makeLen(x.Type()) |
| c.Call.Args = []Value{x} |
| c.setType(tInt) |
| length = fn.emit(&c) |
| } |
| |
| index := fn.addLocal(tInt, token.NoPos) |
| emitStore(fn, index, intConst(-1), pos) |
| |
| loop = fn.newBasicBlock("rangeindex.loop") |
| emitJump(fn, loop) |
| fn.currentBlock = loop |
| |
| incr := &BinOp{ |
| Op: token.ADD, |
| X: emitLoad(fn, index), |
| Y: vOne, |
| } |
| incr.setType(tInt) |
| emitStore(fn, index, fn.emit(incr), pos) |
| |
| body := fn.newBasicBlock("rangeindex.body") |
| done = fn.newBasicBlock("rangeindex.done") |
| emitIf(fn, emitCompare(fn, token.LSS, incr, length, token.NoPos), body, done) |
| fn.currentBlock = body |
| |
| k = emitLoad(fn, index) |
| if tv != nil { |
| switch t := typeparams.CoreType(x.Type()).(type) { |
| case *types.Array: |
| instr := &Index{ |
| X: x, |
| Index: k, |
| } |
| instr.setType(t.Elem()) |
| instr.setPos(x.Pos()) |
| v = fn.emit(instr) |
| |
| case *types.Pointer: // *array |
| instr := &IndexAddr{ |
| X: x, |
| Index: k, |
| } |
| instr.setType(types.NewPointer(t.Elem().Underlying().(*types.Array).Elem())) |
| instr.setPos(x.Pos()) |
| v = emitLoad(fn, fn.emit(instr)) |
| |
| case *types.Slice: |
| instr := &IndexAddr{ |
| X: x, |
| Index: k, |
| } |
| instr.setType(types.NewPointer(t.Elem())) |
| instr.setPos(x.Pos()) |
| 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, pos token.Pos) (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) |
| // |
| |
| if tk == nil { |
| tk = tInvalid |
| } |
| if tv == nil { |
| tv = tInvalid |
| } |
| |
| rng := &Range{X: x} |
| rng.setPos(pos) |
| rng.setType(tRangeIter) |
| it := fn.emit(rng) |
| |
| loop = fn.newBasicBlock("rangeiter.loop") |
| emitJump(fn, loop) |
| fn.currentBlock = loop |
| |
| okv := &Next{ |
| Iter: it, |
| IsString: isBasic(typeparams.CoreType(x.Type())), |
| } |
| okv.setType(types.NewTuple( |
| varOk, |
| newVar("k", tk), |
| newVar("v", tv), |
| )) |
| fn.emit(okv) |
| |
| body := fn.newBasicBlock("rangeiter.body") |
| done = fn.newBasicBlock("rangeiter.done") |
| emitIf(fn, emitExtract(fn, okv, 0), body, done) |
| fn.currentBlock = body |
| |
| if tk != tInvalid { |
| k = emitExtract(fn, okv, 1) |
| } |
| if tv != tInvalid { |
| v = emitExtract(fn, okv, 2) |
| } |
| 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 |
| // pos is the position of the '=' or ':=' token. |
| func (b *builder) rangeChan(fn *Function, x Value, tk types.Type, pos token.Pos) (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.setPos(pos) |
| recv.setType(types.NewTuple( |
| newVar("k", typeparams.CoreType(x.Type()).(*types.Chan).Elem()), |
| varOk, |
| )) |
| ko := fn.emit(recv) |
| body := fn.newBasicBlock("rangechan.body") |
| done = fn.newBasicBlock("rangechan.done") |
| emitIf(fn, emitExtract(fn, ko, 1), body, done) |
| fn.currentBlock = body |
| if tk != nil { |
| k = emitExtract(fn, ko, 0) |
| } |
| 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 s.Key != nil && !isBlankIdent(s.Key) { |
| tk = fn.typeOf(s.Key) |
| } |
| if s.Value != nil && !isBlankIdent(s.Value) { |
| tv = fn.typeOf(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.addLocalForIdent(s.Key.(*ast.Ident)) |
| } |
| if tv != nil { |
| fn.addLocalForIdent(s.Value.(*ast.Ident)) |
| } |
| } |
| |
| x := b.expr(fn, s.X) |
| |
| var k, v Value |
| var loop, done *BasicBlock |
| switch rt := typeparams.CoreType(x.Type()).(type) { |
| case *types.Slice, *types.Array, *types.Pointer: // *array |
| k, v, loop, done = b.rangeIndexed(fn, x, tv, s.For) |
| |
| case *types.Chan: |
| k, loop, done = b.rangeChan(fn, x, tk, s.For) |
| |
| case *types.Map, *types.Basic: // string |
| k, v, loop, done = b.rangeIter(fn, x, tk, tv, s.For) |
| |
| 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) |
| if d.Tok == token.VAR { |
| 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: |
| chtyp := typeparams.CoreType(fn.typeOf(s.Chan)).(*types.Chan) |
| fn.emit(&Send{ |
| Chan: b.expr(fn, s.Chan), |
| X: emitConv(fn, b.expr(fn, s.Value), chtyp.Elem()), |
| pos: s.Arrow, |
| }) |
| |
| case *ast.IncDecStmt: |
| op := token.ADD |
| if s.Tok == token.DEC { |
| op = token.SUB |
| } |
| loc := b.addr(fn, s.X, false) |
| b.assignOp(fn, loc, NewConst(constant.MakeInt64(1), loc.typ()), op, s.Pos()) |
| |
| 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, s.Pos()) |
| } |
| |
| case *ast.GoStmt: |
| // The "intrinsics" new/make/len/cap are forbidden here. |
| // panic is treated like an ordinary function call. |
| v := Go{pos: s.Go} |
| b.setCall(fn, s.Call, &v.Call) |
| fn.emit(&v) |
| |
| case *ast.DeferStmt: |
| // The "intrinsics" new/make/len/cap are forbidden here. |
| // panic is treated like an ordinary function call. |
| v := Defer{pos: s.Defer} |
| b.setCall(fn, s.Call, &v.Call) |
| fn.emit(&v) |
| |
| // A deferred call can cause recovery from panic, |
| // and control resumes at the Recover block. |
| createRecoverBlock(fn) |
| |
| case *ast.ReturnStmt: |
| var results []Value |
| if len(s.Results) == 1 && fn.Signature.Results().Len() > 1 { |
| // Return of one expression in a multi-valued function. |
| tuple := b.exprN(fn, s.Results[0]) |
| ttuple := tuple.Type().(*types.Tuple) |
| for i, n := 0, ttuple.Len(); i < n; i++ { |
| results = append(results, |
| emitConv(fn, emitExtract(fn, tuple, i), |
| fn.Signature.Results().At(i).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().At(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, s.Return) |
| } |
| } |
| // 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(&Return{Results: results, pos: s.Return}) |
| 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 |
| } |
| 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.built { |
| assert(fn.parent == nil, "anonymous functions should not be built by buildFunction()") |
| b.buildFunctionBody(fn) |
| fn.done() |
| } |
| } |
| |
| // buildFunctionBody builds SSA code for the body of function fn. |
| // |
| // fn is not done building until fn.done() is called. |
| func (b *builder) buildFunctionBody(fn *Function) { |
| // TODO(taking): see if this check is reachable. |
| if fn.Blocks != nil { |
| return // building already started |
| } |
| |
| var recvField *ast.FieldList |
| var body *ast.BlockStmt |
| var functype *ast.FuncType |
| switch n := fn.syntax.(type) { |
| case nil: |
| if fn.Params != nil { |
| return // not a Go source function. (Synthetic, or from object file.) |
| } |
| case *ast.FuncDecl: |
| functype = n.Type |
| recvField = n.Recv |
| body = n.Body |
| case *ast.FuncLit: |
| functype = n.Type |
| body = n.Body |
| default: |
| panic(n) |
| } |
| |
| if body == nil { |
| // External function. |
| if fn.Params == nil { |
| // This condition ensures we add a non-empty |
| // params list once only, but we may attempt |
| // the degenerate empty case repeatedly. |
| // TODO(adonovan): opt: don't do that. |
| |
| // We set Function.Params even though there is no body |
| // code to reference them. This simplifies clients. |
| if recv := fn.Signature.Recv(); recv != nil { |
| fn.addParamObj(recv) |
| } |
| params := fn.Signature.Params() |
| for i, n := 0, params.Len(); i < n; i++ { |
| fn.addParamObj(params.At(i)) |
| } |
| } |
| return |
| } |
| |
| // Build instantiation wrapper around generic body? |
| if fn.topLevelOrigin != nil && fn.subst == nil { |
| buildInstantiationWrapper(fn) |
| return |
| } |
| |
| if fn.Prog.mode&LogSource != 0 { |
| defer logStack("build function %s @ %s", fn, fn.Prog.Fset.Position(fn.pos))() |
| } |
| fn.startBody() |
| fn.createSyntacticParams(recvField, functype) |
| b.stmt(fn, body) |
| if cb := fn.currentBlock; cb != nil && (cb == fn.Blocks[0] || cb == fn.Recover || cb.Preds != nil) { |
| // Control fell off the end of the function's body block. |
| // |
| // Block optimizations eliminate the current block, if |
| // unreachable. It is a builder invariant that |
| // if this no-arg return is ill-typed for |
| // fn.Signature.Results, this block must be |
| // unreachable. The sanity checker checks this. |
| fn.emit(new(RunDefers)) |
| fn.emit(new(Return)) |
| } |
| fn.finishBody() |
| } |
| |
| // buildCreated does the BUILD phase for each function created by builder that is not yet BUILT. |
| // Functions are built using buildFunction. |
| // |
| // May add types that require runtime type information to builder. |
| func (b *builder) buildCreated() { |
| for ; b.finished < b.created.Len(); b.finished++ { |
| fn := b.created.At(b.finished) |
| b.buildFunction(fn) |
| } |
| } |
| |
| // Adds any needed runtime type information for the created functions. |
| // |
| // May add newly CREATEd functions that may need to be built or runtime type information. |
| // |
| // EXCLUSIVE_LOCKS_ACQUIRED(prog.methodsMu) |
| func (b *builder) needsRuntimeTypes() { |
| if b.created.Len() == 0 { |
| return |
| } |
| prog := b.created.At(0).Prog |
| |
| var rtypes []types.Type |
| for ; b.rtypes < b.finished; b.rtypes++ { |
| fn := b.created.At(b.rtypes) |
| rtypes = append(rtypes, mayNeedRuntimeTypes(fn)...) |
| } |
| |
| // Calling prog.needMethodsOf(T) on a basic type T is a no-op. |
| // Filter out the basic types to reduce acquiring prog.methodsMu. |
| rtypes = nonbasicTypes(rtypes) |
| |
| for _, T := range rtypes { |
| prog.needMethodsOf(T, b.created) |
| } |
| } |
| |
| func (b *builder) done() bool { |
| return b.rtypes >= b.created.Len() |
| } |
| |
| // Build calls Package.Build for each package in prog. |
| // Building occurs in parallel unless the BuildSerially mode flag was set. |
| // |
| // Build is intended for whole-program analysis; a typical compiler |
| // need only build a single package. |
| // |
| // Build is idempotent and thread-safe. |
| func (prog *Program) Build() { |
| var wg sync.WaitGroup |
| for _, p := range prog.packages { |
| if prog.mode&BuildSerially != 0 { |
| p.Build() |
| } else { |
| wg.Add(1) |
| go func(p *Package) { |
| p.Build() |
| wg.Done() |
| }(p) |
| } |
| } |
| wg.Wait() |
| } |
| |
| // Build builds SSA code for all functions and vars in package p. |
| // |
| // Precondition: CreatePackage must have been called for all of p's |
| // direct imports (and hence its direct imports must have been |
| // error-free). |
| // |
| // Build is idempotent and thread-safe. |
| func (p *Package) Build() { p.buildOnce.Do(p.build) } |
| |
| func (p *Package) build() { |
| if p.info == nil { |
| return // synthetic package, e.g. "testmain" |
| } |
| |
| // Ensure we have runtime type info for all exported members. |
| // Additionally filter for just concrete types that can be runtime types. |
| // |
| // TODO(adonovan): ideally belongs in memberFromObject, but |
| // that would require package creation in topological order. |
| for name, mem := range p.Members { |
| isGround := func(m Member) bool { |
| switch m := m.(type) { |
| case *Type: |
| named, _ := m.Type().(*types.Named) |
| return named == nil || typeparams.ForNamed(named) == nil |
| case *Function: |
| return m.typeparams.Len() == 0 |
| } |
| return true // *NamedConst, *Global |
| } |
| if ast.IsExported(name) && isGround(mem) { |
| p.Prog.needMethodsOf(mem.Type(), &p.created) |
| } |
| } |
| if p.Prog.mode&LogSource != 0 { |
| defer logStack("build %s", p)() |
| } |
| |
| b := builder{created: &p.created} |
| init := p.init |
| init.startBody() |
| |
| var done *BasicBlock |
| |
| if p.Prog.mode&BareInits == 0 { |
| // 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, token.NoPos) |
| |
| // Call the init() function of each package we import. |
| for _, pkg := range p.Pkg.Imports() { |
| prereq := p.Prog.packages[pkg] |
| if prereq == nil { |
| panic(fmt.Sprintf("Package(%q).Build(): unsatisfied import: Program.CreatePackage(%q) was not called", p.Pkg.Path(), pkg.Path())) |
| } |
| var v Call |
| v.Call.Value = prereq.init |
| v.Call.pos = init.pos |
| v.setType(types.NewTuple()) |
| init.emit(&v) |
| } |
| } |
| |
| // Initialize package-level vars in correct order. |
| if len(p.info.InitOrder) > 0 && len(p.files) == 0 { |
| panic("no source files provided for package. cannot initialize globals") |
| } |
| for _, varinit := range p.info.InitOrder { |
| if init.Prog.mode&LogSource != 0 { |
| fmt.Fprintf(os.Stderr, "build global initializer %v @ %s\n", |
| varinit.Lhs, p.Prog.Fset.Position(varinit.Rhs.Pos())) |
| } |
| if len(varinit.Lhs) == 1 { |
| // 1:1 initialization: var x, y = a(), b() |
| var lval lvalue |
| if v := varinit.Lhs[0]; v.Name() != "_" { |
| lval = &address{addr: p.objects[v].(*Global), pos: v.Pos()} |
| } else { |
| lval = blank{} |
| } |
| b.assign(init, lval, varinit.Rhs, true, nil) |
| } else { |
| // n:1 initialization: var x, y := f() |
| tuple := b.exprN(init, varinit.Rhs) |
| for i, v := range varinit.Lhs { |
| if v.Name() == "_" { |
| continue |
| } |
| emitStore(init, p.objects[v].(*Global), emitExtract(init, tuple, i), v.Pos()) |
| } |
| } |
| } |
| |
| // Call all of the declared init() functions in source order. |
| for _, file := range p.files { |
| for _, decl := range file.Decls { |
| if decl, ok := decl.(*ast.FuncDecl); ok { |
| id := decl.Name |
| if !isBlankIdent(id) && id.Name == "init" && decl.Recv == nil { |
| fn := p.objects[p.info.Defs[id]].(*Function) |
| var v Call |
| v.Call.Value = fn |
| v.setType(types.NewTuple()) |
| p.init.emit(&v) |
| } |
| } |
| } |
| } |
| |
| // Finish up init(). |
| if p.Prog.mode&BareInits == 0 { |
| emitJump(init, done) |
| init.currentBlock = done |
| } |
| init.emit(new(Return)) |
| init.finishBody() |
| init.done() |
| |
| // Build all CREATEd functions and add runtime types. |
| // These Functions include package-level functions, init functions, methods, and synthetic (including unreachable/blank ones). |
| // Builds any functions CREATEd while building this package. |
| // |
| // Initially the created functions for the package are: |
| // [init, decl0, ... , declN] |
| // Where decl0, ..., declN are declared functions in source order, but it's not significant. |
| // |
| // As these are built, more functions (function literals, wrappers, etc.) can be CREATEd. |
| // Iterate until we reach a fixed point. |
| // |
| // Wait for init() to be BUILT as that cannot be built by buildFunction(). |
| // |
| for !b.done() { |
| b.buildCreated() // build any CREATEd and not BUILT function. May add runtime types. |
| b.needsRuntimeTypes() // Add all of the runtime type information. May CREATE Functions. |
| } |
| |
| p.info = nil // We no longer need ASTs or go/types deductions. |
| p.created = nil // We no longer need created functions. |
| |
| if p.Prog.mode&SanityCheckFunctions != 0 { |
| sanityCheckPackage(p) |
| } |
| } |