Source file src/golang.org/x/tools/go/ssa/builder.go

Documentation: golang.org/x/tools/go/ssa

     1  // Copyright 2013 The Go Authors. All rights reserved.
     2  // Use of this source code is governed by a BSD-style
     3  // license that can be found in the LICENSE file.
     4  
     5  package ssa
     6  
     7  // This file implements the BUILD phase of SSA construction.
     8  //
     9  // SSA construction has two phases, CREATE and BUILD.  In the CREATE phase
    10  // (create.go), all packages are constructed and type-checked and
    11  // definitions of all package members are created, method-sets are
    12  // computed, and wrapper methods are synthesized.
    13  // ssa.Packages are created in arbitrary order.
    14  //
    15  // In the BUILD phase (builder.go), the builder traverses the AST of
    16  // each Go source function and generates SSA instructions for the
    17  // function body.  Initializer expressions for package-level variables
    18  // are emitted to the package's init() function in the order specified
    19  // by go/types.Info.InitOrder, then code for each function in the
    20  // package is generated in lexical order.
    21  // The BUILD phases for distinct packages are independent and are
    22  // executed in parallel.
    23  //
    24  // TODO(adonovan): indeed, building functions is now embarrassingly parallel.
    25  // Audit for concurrency then benchmark using more goroutines.
    26  //
    27  // State:
    28  //
    29  // The Package's and Program's indices (maps) are populated and
    30  // mutated during the CREATE phase, but during the BUILD phase they
    31  // remain constant.  The sole exception is Prog.methodSets and its
    32  // related maps, which are protected by a dedicated mutex.
    33  //
    34  // Generic functions declared in a package P can be instantiated from functions
    35  // outside of P. This happens independently of the CREATE and BUILD phase of P.
    36  //
    37  // Locks:
    38  //
    39  // Mutexes are currently acquired according to the following order:
    40  //     Prog.methodsMu ⊃ canonizer.mu ⊃ printMu
    41  // where x ⊃ y denotes that y can be acquired while x is held
    42  // and x cannot be acquired while y is held.
    43  //
    44  // Synthetics:
    45  //
    46  // During the BUILD phase new functions can be created and built. These include:
    47  // - wrappers (wrappers, bounds, thunks)
    48  // - generic function instantiations
    49  // These functions do not belong to a specific Pkg (Pkg==nil). Instead the
    50  // Package that led to them being CREATED is obligated to ensure these
    51  // are BUILT during the BUILD phase of the Package.
    52  //
    53  // Runtime types:
    54  //
    55  // A concrete type is a type that is fully monomorphized with concrete types,
    56  // i.e. it cannot reach a TypeParam type.
    57  // Some concrete types require full runtime type information. Cases
    58  // include checking whether a type implements an interface or
    59  // interpretation by the reflect package. All such types that may require
    60  // this information will have all of their method sets built and will be added to Prog.methodSets.
    61  // A type T is considered to require runtime type information if it is
    62  // a runtime type and has a non-empty method set and either:
    63  // - T flows into a MakeInterface instructions,
    64  // - T appears in a concrete exported member, or
    65  // - T is a type reachable from a type S that has non-empty method set.
    66  // For any such type T, method sets must be created before the BUILD
    67  // phase of the package is done.
    68  //
    69  // Function literals:
    70  //
    71  // The BUILD phase of a function literal (anonymous function) is tied to the
    72  // BUILD phase of the enclosing parent function. The FreeVars of an anonymous
    73  // function are discovered by building the anonymous function. This in turn
    74  // changes which variables must be bound in a MakeClosure instruction in the
    75  // parent. Anonymous functions also track where they are referred to in their
    76  // parent function.
    77  //
    78  // Happens-before:
    79  //
    80  // The above discussion leads to the following happens-before relation for
    81  // the BUILD and CREATE phases.
    82  // The happens-before relation (with X<Y denoting X happens-before Y) are:
    83  // - CREATE fn < fn.startBody() < fn.finishBody() < fn.built
    84  //   for any function fn.
    85  // - anon.parent.startBody() < CREATE anon, and
    86  //   anon.finishBody() < anon.parent().finishBody() < anon.built < fn.built
    87  //   for an anonymous function anon (i.e. anon.parent() != nil).
    88  // - CREATE fn.Pkg < CREATE fn
    89  //   for a declared function fn (i.e. fn.Pkg != nil)
    90  // - fn.built < BUILD pkg done
    91  //   for any function fn created during the CREATE or BUILD phase of a package
    92  //   pkg. This includes declared and synthetic functions.
    93  //
    94  // Program.MethodValue:
    95  //
    96  // Program.MethodValue may trigger new wrapper and instantiation functions to
    97  // be created. It has the same obligation to BUILD created functions as a
    98  // Package.
    99  //
   100  // Program.NewFunction:
   101  //
   102  // This is a low level operation for creating functions that do not exist in
   103  // the source. Use with caution.
   104  //
   105  // TODO(taking): Use consistent terminology for "concrete".
   106  // TODO(taking): Use consistent terminology for "monomorphization"/"instantiate"/"expand".
   107  
   108  import (
   109  	"fmt"
   110  	"go/ast"
   111  	"go/constant"
   112  	"go/token"
   113  	"go/types"
   114  	"os"
   115  	"sync"
   116  
   117  	"golang.org/x/tools/internal/typeparams"
   118  )
   119  
   120  type opaqueType struct {
   121  	types.Type
   122  	name string
   123  }
   124  
   125  func (t *opaqueType) String() string { return t.name }
   126  
   127  var (
   128  	varOk    = newVar("ok", tBool)
   129  	varIndex = newVar("index", tInt)
   130  
   131  	// Type constants.
   132  	tBool       = types.Typ[types.Bool]
   133  	tByte       = types.Typ[types.Byte]
   134  	tInt        = types.Typ[types.Int]
   135  	tInvalid    = types.Typ[types.Invalid]
   136  	tString     = types.Typ[types.String]
   137  	tUntypedNil = types.Typ[types.UntypedNil]
   138  	tRangeIter  = &opaqueType{nil, "iter"} // the type of all "range" iterators
   139  	tEface      = types.NewInterfaceType(nil, nil).Complete()
   140  
   141  	// SSA Value constants.
   142  	vZero = intConst(0)
   143  	vOne  = intConst(1)
   144  	vTrue = NewConst(constant.MakeBool(true), tBool)
   145  )
   146  
   147  // builder holds state associated with the package currently being built.
   148  // Its methods contain all the logic for AST-to-SSA conversion.
   149  type builder struct {
   150  	// Invariant: 0 <= rtypes <= finished <= created.Len()
   151  	created  *creator // functions created during building
   152  	finished int      // Invariant: create[i].built holds for i in [0,finished)
   153  	rtypes   int      // Invariant: all of the runtime types for create[i] have been added for i in [0,rtypes)
   154  }
   155  
   156  // cond emits to fn code to evaluate boolean condition e and jump
   157  // to t or f depending on its value, performing various simplifications.
   158  //
   159  // Postcondition: fn.currentBlock is nil.
   160  func (b *builder) cond(fn *Function, e ast.Expr, t, f *BasicBlock) {
   161  	switch e := e.(type) {
   162  	case *ast.ParenExpr:
   163  		b.cond(fn, e.X, t, f)
   164  		return
   165  
   166  	case *ast.BinaryExpr:
   167  		switch e.Op {
   168  		case token.LAND:
   169  			ltrue := fn.newBasicBlock("cond.true")
   170  			b.cond(fn, e.X, ltrue, f)
   171  			fn.currentBlock = ltrue
   172  			b.cond(fn, e.Y, t, f)
   173  			return
   174  
   175  		case token.LOR:
   176  			lfalse := fn.newBasicBlock("cond.false")
   177  			b.cond(fn, e.X, t, lfalse)
   178  			fn.currentBlock = lfalse
   179  			b.cond(fn, e.Y, t, f)
   180  			return
   181  		}
   182  
   183  	case *ast.UnaryExpr:
   184  		if e.Op == token.NOT {
   185  			b.cond(fn, e.X, f, t)
   186  			return
   187  		}
   188  	}
   189  
   190  	// A traditional compiler would simplify "if false" (etc) here
   191  	// but we do not, for better fidelity to the source code.
   192  	//
   193  	// The value of a constant condition may be platform-specific,
   194  	// and may cause blocks that are reachable in some configuration
   195  	// to be hidden from subsequent analyses such as bug-finding tools.
   196  	emitIf(fn, b.expr(fn, e), t, f)
   197  }
   198  
   199  // logicalBinop emits code to fn to evaluate e, a &&- or
   200  // ||-expression whose reified boolean value is wanted.
   201  // The value is returned.
   202  func (b *builder) logicalBinop(fn *Function, e *ast.BinaryExpr) Value {
   203  	rhs := fn.newBasicBlock("binop.rhs")
   204  	done := fn.newBasicBlock("binop.done")
   205  
   206  	// T(e) = T(e.X) = T(e.Y) after untyped constants have been
   207  	// eliminated.
   208  	// TODO(adonovan): not true; MyBool==MyBool yields UntypedBool.
   209  	t := fn.typeOf(e)
   210  
   211  	var short Value // value of the short-circuit path
   212  	switch e.Op {
   213  	case token.LAND:
   214  		b.cond(fn, e.X, rhs, done)
   215  		short = NewConst(constant.MakeBool(false), t)
   216  
   217  	case token.LOR:
   218  		b.cond(fn, e.X, done, rhs)
   219  		short = NewConst(constant.MakeBool(true), t)
   220  	}
   221  
   222  	// Is rhs unreachable?
   223  	if rhs.Preds == nil {
   224  		// Simplify false&&y to false, true||y to true.
   225  		fn.currentBlock = done
   226  		return short
   227  	}
   228  
   229  	// Is done unreachable?
   230  	if done.Preds == nil {
   231  		// Simplify true&&y (or false||y) to y.
   232  		fn.currentBlock = rhs
   233  		return b.expr(fn, e.Y)
   234  	}
   235  
   236  	// All edges from e.X to done carry the short-circuit value.
   237  	var edges []Value
   238  	for range done.Preds {
   239  		edges = append(edges, short)
   240  	}
   241  
   242  	// The edge from e.Y to done carries the value of e.Y.
   243  	fn.currentBlock = rhs
   244  	edges = append(edges, b.expr(fn, e.Y))
   245  	emitJump(fn, done)
   246  	fn.currentBlock = done
   247  
   248  	phi := &Phi{Edges: edges, Comment: e.Op.String()}
   249  	phi.pos = e.OpPos
   250  	phi.typ = t
   251  	return done.emit(phi)
   252  }
   253  
   254  // exprN lowers a multi-result expression e to SSA form, emitting code
   255  // to fn and returning a single Value whose type is a *types.Tuple.
   256  // The caller must access the components via Extract.
   257  //
   258  // Multi-result expressions include CallExprs in a multi-value
   259  // assignment or return statement, and "value,ok" uses of
   260  // TypeAssertExpr, IndexExpr (when X is a map), and UnaryExpr (when Op
   261  // is token.ARROW).
   262  func (b *builder) exprN(fn *Function, e ast.Expr) Value {
   263  	typ := fn.typeOf(e).(*types.Tuple)
   264  	switch e := e.(type) {
   265  	case *ast.ParenExpr:
   266  		return b.exprN(fn, e.X)
   267  
   268  	case *ast.CallExpr:
   269  		// Currently, no built-in function nor type conversion
   270  		// has multiple results, so we can avoid some of the
   271  		// cases for single-valued CallExpr.
   272  		var c Call
   273  		b.setCall(fn, e, &c.Call)
   274  		c.typ = typ
   275  		return fn.emit(&c)
   276  
   277  	case *ast.IndexExpr:
   278  		mapt := typeparams.CoreType(fn.typeOf(e.X)).(*types.Map) // ,ok must be a map.
   279  		lookup := &Lookup{
   280  			X:       b.expr(fn, e.X),
   281  			Index:   emitConv(fn, b.expr(fn, e.Index), mapt.Key()),
   282  			CommaOk: true,
   283  		}
   284  		lookup.setType(typ)
   285  		lookup.setPos(e.Lbrack)
   286  		return fn.emit(lookup)
   287  
   288  	case *ast.TypeAssertExpr:
   289  		return emitTypeTest(fn, b.expr(fn, e.X), typ.At(0).Type(), e.Lparen)
   290  
   291  	case *ast.UnaryExpr: // must be receive <-
   292  		unop := &UnOp{
   293  			Op:      token.ARROW,
   294  			X:       b.expr(fn, e.X),
   295  			CommaOk: true,
   296  		}
   297  		unop.setType(typ)
   298  		unop.setPos(e.OpPos)
   299  		return fn.emit(unop)
   300  	}
   301  	panic(fmt.Sprintf("exprN(%T) in %s", e, fn))
   302  }
   303  
   304  // builtin emits to fn SSA instructions to implement a call to the
   305  // built-in function obj with the specified arguments
   306  // and return type.  It returns the value defined by the result.
   307  //
   308  // The result is nil if no special handling was required; in this case
   309  // the caller should treat this like an ordinary library function
   310  // call.
   311  func (b *builder) builtin(fn *Function, obj *types.Builtin, args []ast.Expr, typ types.Type, pos token.Pos) Value {
   312  	typ = fn.typ(typ)
   313  	switch obj.Name() {
   314  	case "make":
   315  		switch ct := typeparams.CoreType(typ).(type) {
   316  		case *types.Slice:
   317  			n := b.expr(fn, args[1])
   318  			m := n
   319  			if len(args) == 3 {
   320  				m = b.expr(fn, args[2])
   321  			}
   322  			if m, ok := m.(*Const); ok {
   323  				// treat make([]T, n, m) as new([m]T)[:n]
   324  				cap := m.Int64()
   325  				at := types.NewArray(ct.Elem(), cap)
   326  				alloc := emitNew(fn, at, pos)
   327  				alloc.Comment = "makeslice"
   328  				v := &Slice{
   329  					X:    alloc,
   330  					High: n,
   331  				}
   332  				v.setPos(pos)
   333  				v.setType(typ)
   334  				return fn.emit(v)
   335  			}
   336  			v := &MakeSlice{
   337  				Len: n,
   338  				Cap: m,
   339  			}
   340  			v.setPos(pos)
   341  			v.setType(typ)
   342  			return fn.emit(v)
   343  
   344  		case *types.Map:
   345  			var res Value
   346  			if len(args) == 2 {
   347  				res = b.expr(fn, args[1])
   348  			}
   349  			v := &MakeMap{Reserve: res}
   350  			v.setPos(pos)
   351  			v.setType(typ)
   352  			return fn.emit(v)
   353  
   354  		case *types.Chan:
   355  			var sz Value = vZero
   356  			if len(args) == 2 {
   357  				sz = b.expr(fn, args[1])
   358  			}
   359  			v := &MakeChan{Size: sz}
   360  			v.setPos(pos)
   361  			v.setType(typ)
   362  			return fn.emit(v)
   363  		}
   364  
   365  	case "new":
   366  		alloc := emitNew(fn, deref(typ), pos)
   367  		alloc.Comment = "new"
   368  		return alloc
   369  
   370  	case "len", "cap":
   371  		// Special case: len or cap of an array or *array is
   372  		// based on the type, not the value which may be nil.
   373  		// We must still evaluate the value, though.  (If it
   374  		// was side-effect free, the whole call would have
   375  		// been constant-folded.)
   376  		//
   377  		// Type parameters are always non-constant so use Underlying.
   378  		t := deref(fn.typeOf(args[0])).Underlying()
   379  		if at, ok := t.(*types.Array); ok {
   380  			b.expr(fn, args[0]) // for effects only
   381  			return intConst(at.Len())
   382  		}
   383  		// Otherwise treat as normal.
   384  
   385  	case "panic":
   386  		fn.emit(&Panic{
   387  			X:   emitConv(fn, b.expr(fn, args[0]), tEface),
   388  			pos: pos,
   389  		})
   390  		fn.currentBlock = fn.newBasicBlock("unreachable")
   391  		return vTrue // any non-nil Value will do
   392  	}
   393  	return nil // treat all others as a regular function call
   394  }
   395  
   396  // addr lowers a single-result addressable expression e to SSA form,
   397  // emitting code to fn and returning the location (an lvalue) defined
   398  // by the expression.
   399  //
   400  // If escaping is true, addr marks the base variable of the
   401  // addressable expression e as being a potentially escaping pointer
   402  // value.  For example, in this code:
   403  //
   404  //	a := A{
   405  //	  b: [1]B{B{c: 1}}
   406  //	}
   407  //	return &a.b[0].c
   408  //
   409  // the application of & causes a.b[0].c to have its address taken,
   410  // which means that ultimately the local variable a must be
   411  // heap-allocated.  This is a simple but very conservative escape
   412  // analysis.
   413  //
   414  // Operations forming potentially escaping pointers include:
   415  // - &x, including when implicit in method call or composite literals.
   416  // - a[:] iff a is an array (not *array)
   417  // - references to variables in lexically enclosing functions.
   418  func (b *builder) addr(fn *Function, e ast.Expr, escaping bool) lvalue {
   419  	switch e := e.(type) {
   420  	case *ast.Ident:
   421  		if isBlankIdent(e) {
   422  			return blank{}
   423  		}
   424  		obj := fn.objectOf(e)
   425  		var v Value
   426  		if g := fn.Prog.packageLevelMember(obj); g != nil {
   427  			v = g.(*Global) // var (address)
   428  		} else {
   429  			v = fn.lookup(obj, escaping)
   430  		}
   431  		return &address{addr: v, pos: e.Pos(), expr: e}
   432  
   433  	case *ast.CompositeLit:
   434  		t := deref(fn.typeOf(e))
   435  		var v *Alloc
   436  		if escaping {
   437  			v = emitNew(fn, t, e.Lbrace)
   438  		} else {
   439  			v = fn.addLocal(t, e.Lbrace)
   440  		}
   441  		v.Comment = "complit"
   442  		var sb storebuf
   443  		b.compLit(fn, v, e, true, &sb)
   444  		sb.emit(fn)
   445  		return &address{addr: v, pos: e.Lbrace, expr: e}
   446  
   447  	case *ast.ParenExpr:
   448  		return b.addr(fn, e.X, escaping)
   449  
   450  	case *ast.SelectorExpr:
   451  		sel := fn.selection(e)
   452  		if sel == nil {
   453  			// qualified identifier
   454  			return b.addr(fn, e.Sel, escaping)
   455  		}
   456  		if sel.kind != types.FieldVal {
   457  			panic(sel)
   458  		}
   459  		wantAddr := true
   460  		v := b.receiver(fn, e.X, wantAddr, escaping, sel)
   461  		index := sel.index[len(sel.index)-1]
   462  		fld := typeparams.CoreType(deref(v.Type())).(*types.Struct).Field(index)
   463  
   464  		// Due to the two phases of resolving AssignStmt, a panic from x.f = p()
   465  		// when x is nil is required to come after the side-effects of
   466  		// evaluating x and p().
   467  		emit := func(fn *Function) Value {
   468  			return emitFieldSelection(fn, v, index, true, e.Sel)
   469  		}
   470  		return &lazyAddress{addr: emit, t: fld.Type(), pos: e.Sel.Pos(), expr: e.Sel}
   471  
   472  	case *ast.IndexExpr:
   473  		xt := fn.typeOf(e.X)
   474  		elem, mode := indexType(xt)
   475  		var x Value
   476  		var et types.Type
   477  		switch mode {
   478  		case ixArrVar: // array, array|slice, array|*array, or array|*array|slice.
   479  			x = b.addr(fn, e.X, escaping).address(fn)
   480  			et = types.NewPointer(elem)
   481  		case ixVar: // *array, slice, *array|slice
   482  			x = b.expr(fn, e.X)
   483  			et = types.NewPointer(elem)
   484  		case ixMap:
   485  			mt := typeparams.CoreType(xt).(*types.Map)
   486  			return &element{
   487  				m:   b.expr(fn, e.X),
   488  				k:   emitConv(fn, b.expr(fn, e.Index), mt.Key()),
   489  				t:   mt.Elem(),
   490  				pos: e.Lbrack,
   491  			}
   492  		default:
   493  			panic("unexpected container type in IndexExpr: " + xt.String())
   494  		}
   495  		index := b.expr(fn, e.Index)
   496  		if isUntyped(index.Type()) {
   497  			index = emitConv(fn, index, tInt)
   498  		}
   499  		// Due to the two phases of resolving AssignStmt, a panic from x[i] = p()
   500  		// when x is nil or i is out-of-bounds is required to come after the
   501  		// side-effects of evaluating x, i and p().
   502  		emit := func(fn *Function) Value {
   503  			v := &IndexAddr{
   504  				X:     x,
   505  				Index: index,
   506  			}
   507  			v.setPos(e.Lbrack)
   508  			v.setType(et)
   509  			return fn.emit(v)
   510  		}
   511  		return &lazyAddress{addr: emit, t: deref(et), pos: e.Lbrack, expr: e}
   512  
   513  	case *ast.StarExpr:
   514  		return &address{addr: b.expr(fn, e.X), pos: e.Star, expr: e}
   515  	}
   516  
   517  	panic(fmt.Sprintf("unexpected address expression: %T", e))
   518  }
   519  
   520  type store struct {
   521  	lhs lvalue
   522  	rhs Value
   523  }
   524  
   525  type storebuf struct{ stores []store }
   526  
   527  func (sb *storebuf) store(lhs lvalue, rhs Value) {
   528  	sb.stores = append(sb.stores, store{lhs, rhs})
   529  }
   530  
   531  func (sb *storebuf) emit(fn *Function) {
   532  	for _, s := range sb.stores {
   533  		s.lhs.store(fn, s.rhs)
   534  	}
   535  }
   536  
   537  // assign emits to fn code to initialize the lvalue loc with the value
   538  // of expression e.  If isZero is true, assign assumes that loc holds
   539  // the zero value for its type.
   540  //
   541  // This is equivalent to loc.store(fn, b.expr(fn, e)), but may generate
   542  // better code in some cases, e.g., for composite literals in an
   543  // addressable location.
   544  //
   545  // If sb is not nil, assign generates code to evaluate expression e, but
   546  // not to update loc.  Instead, the necessary stores are appended to the
   547  // storebuf sb so that they can be executed later.  This allows correct
   548  // in-place update of existing variables when the RHS is a composite
   549  // literal that may reference parts of the LHS.
   550  func (b *builder) assign(fn *Function, loc lvalue, e ast.Expr, isZero bool, sb *storebuf) {
   551  	// Can we initialize it in place?
   552  	if e, ok := unparen(e).(*ast.CompositeLit); ok {
   553  		// A CompositeLit never evaluates to a pointer,
   554  		// so if the type of the location is a pointer,
   555  		// an &-operation is implied.
   556  		if _, ok := loc.(blank); !ok { // avoid calling blank.typ()
   557  			if isPointer(loc.typ()) {
   558  				ptr := b.addr(fn, e, true).address(fn)
   559  				// copy address
   560  				if sb != nil {
   561  					sb.store(loc, ptr)
   562  				} else {
   563  					loc.store(fn, ptr)
   564  				}
   565  				return
   566  			}
   567  		}
   568  
   569  		if _, ok := loc.(*address); ok {
   570  			if isNonTypeParamInterface(loc.typ()) {
   571  				// e.g. var x interface{} = T{...}
   572  				// Can't in-place initialize an interface value.
   573  				// Fall back to copying.
   574  			} else {
   575  				// x = T{...} or x := T{...}
   576  				addr := loc.address(fn)
   577  				if sb != nil {
   578  					b.compLit(fn, addr, e, isZero, sb)
   579  				} else {
   580  					var sb storebuf
   581  					b.compLit(fn, addr, e, isZero, &sb)
   582  					sb.emit(fn)
   583  				}
   584  
   585  				// Subtle: emit debug ref for aggregate types only;
   586  				// slice and map are handled by store ops in compLit.
   587  				switch loc.typ().Underlying().(type) {
   588  				case *types.Struct, *types.Array:
   589  					emitDebugRef(fn, e, addr, true)
   590  				}
   591  
   592  				return
   593  			}
   594  		}
   595  	}
   596  
   597  	// simple case: just copy
   598  	rhs := b.expr(fn, e)
   599  	if sb != nil {
   600  		sb.store(loc, rhs)
   601  	} else {
   602  		loc.store(fn, rhs)
   603  	}
   604  }
   605  
   606  // expr lowers a single-result expression e to SSA form, emitting code
   607  // to fn and returning the Value defined by the expression.
   608  func (b *builder) expr(fn *Function, e ast.Expr) Value {
   609  	e = unparen(e)
   610  
   611  	tv := fn.info.Types[e]
   612  
   613  	// Is expression a constant?
   614  	if tv.Value != nil {
   615  		return NewConst(tv.Value, fn.typ(tv.Type))
   616  	}
   617  
   618  	var v Value
   619  	if tv.Addressable() {
   620  		// Prefer pointer arithmetic ({Index,Field}Addr) followed
   621  		// by Load over subelement extraction (e.g. Index, Field),
   622  		// to avoid large copies.
   623  		v = b.addr(fn, e, false).load(fn)
   624  	} else {
   625  		v = b.expr0(fn, e, tv)
   626  	}
   627  	if fn.debugInfo() {
   628  		emitDebugRef(fn, e, v, false)
   629  	}
   630  	return v
   631  }
   632  
   633  func (b *builder) expr0(fn *Function, e ast.Expr, tv types.TypeAndValue) Value {
   634  	switch e := e.(type) {
   635  	case *ast.BasicLit:
   636  		panic("non-constant BasicLit") // unreachable
   637  
   638  	case *ast.FuncLit:
   639  		fn2 := &Function{
   640  			name:           fmt.Sprintf("%s$%d", fn.Name(), 1+len(fn.AnonFuncs)),
   641  			Signature:      fn.typeOf(e.Type).(*types.Signature),
   642  			pos:            e.Type.Func,
   643  			parent:         fn,
   644  			anonIdx:        int32(len(fn.AnonFuncs)),
   645  			Pkg:            fn.Pkg,
   646  			Prog:           fn.Prog,
   647  			syntax:         e,
   648  			topLevelOrigin: nil,           // use anonIdx to lookup an anon instance's origin.
   649  			typeparams:     fn.typeparams, // share the parent's type parameters.
   650  			typeargs:       fn.typeargs,   // share the parent's type arguments.
   651  			info:           fn.info,
   652  			subst:          fn.subst, // share the parent's type substitutions.
   653  		}
   654  		fn.AnonFuncs = append(fn.AnonFuncs, fn2)
   655  		b.created.Add(fn2)
   656  		b.buildFunctionBody(fn2)
   657  		// fn2 is not done BUILDing. fn2.referrers can still be updated.
   658  		// fn2 is done BUILDing after fn.finishBody().
   659  		if fn2.FreeVars == nil {
   660  			return fn2
   661  		}
   662  		v := &MakeClosure{Fn: fn2}
   663  		v.setType(fn.typ(tv.Type))
   664  		for _, fv := range fn2.FreeVars {
   665  			v.Bindings = append(v.Bindings, fv.outer)
   666  			fv.outer = nil
   667  		}
   668  		return fn.emit(v)
   669  
   670  	case *ast.TypeAssertExpr: // single-result form only
   671  		return emitTypeAssert(fn, b.expr(fn, e.X), fn.typ(tv.Type), e.Lparen)
   672  
   673  	case *ast.CallExpr:
   674  		if fn.info.Types[e.Fun].IsType() {
   675  			// Explicit type conversion, e.g. string(x) or big.Int(x)
   676  			x := b.expr(fn, e.Args[0])
   677  			y := emitConv(fn, x, fn.typ(tv.Type))
   678  			if y != x {
   679  				switch y := y.(type) {
   680  				case *Convert:
   681  					y.pos = e.Lparen
   682  				case *ChangeType:
   683  					y.pos = e.Lparen
   684  				case *MakeInterface:
   685  					y.pos = e.Lparen
   686  				case *SliceToArrayPointer:
   687  					y.pos = e.Lparen
   688  				case *UnOp: // conversion from slice to array.
   689  					y.pos = e.Lparen
   690  				}
   691  			}
   692  			return y
   693  		}
   694  		// Call to "intrinsic" built-ins, e.g. new, make, panic.
   695  		if id, ok := unparen(e.Fun).(*ast.Ident); ok {
   696  			if obj, ok := fn.info.Uses[id].(*types.Builtin); ok {
   697  				if v := b.builtin(fn, obj, e.Args, fn.typ(tv.Type), e.Lparen); v != nil {
   698  					return v
   699  				}
   700  			}
   701  		}
   702  		// Regular function call.
   703  		var v Call
   704  		b.setCall(fn, e, &v.Call)
   705  		v.setType(fn.typ(tv.Type))
   706  		return fn.emit(&v)
   707  
   708  	case *ast.UnaryExpr:
   709  		switch e.Op {
   710  		case token.AND: // &X --- potentially escaping.
   711  			addr := b.addr(fn, e.X, true)
   712  			if _, ok := unparen(e.X).(*ast.StarExpr); ok {
   713  				// &*p must panic if p is nil (http://golang.org/s/go12nil).
   714  				// For simplicity, we'll just (suboptimally) rely
   715  				// on the side effects of a load.
   716  				// TODO(adonovan): emit dedicated nilcheck.
   717  				addr.load(fn)
   718  			}
   719  			return addr.address(fn)
   720  		case token.ADD:
   721  			return b.expr(fn, e.X)
   722  		case token.NOT, token.ARROW, token.SUB, token.XOR: // ! <- - ^
   723  			v := &UnOp{
   724  				Op: e.Op,
   725  				X:  b.expr(fn, e.X),
   726  			}
   727  			v.setPos(e.OpPos)
   728  			v.setType(fn.typ(tv.Type))
   729  			return fn.emit(v)
   730  		default:
   731  			panic(e.Op)
   732  		}
   733  
   734  	case *ast.BinaryExpr:
   735  		switch e.Op {
   736  		case token.LAND, token.LOR:
   737  			return b.logicalBinop(fn, e)
   738  		case token.SHL, token.SHR:
   739  			fallthrough
   740  		case token.ADD, token.SUB, token.MUL, token.QUO, token.REM, token.AND, token.OR, token.XOR, token.AND_NOT:
   741  			return emitArith(fn, e.Op, b.expr(fn, e.X), b.expr(fn, e.Y), fn.typ(tv.Type), e.OpPos)
   742  
   743  		case token.EQL, token.NEQ, token.GTR, token.LSS, token.LEQ, token.GEQ:
   744  			cmp := emitCompare(fn, e.Op, b.expr(fn, e.X), b.expr(fn, e.Y), e.OpPos)
   745  			// The type of x==y may be UntypedBool.
   746  			return emitConv(fn, cmp, types.Default(fn.typ(tv.Type)))
   747  		default:
   748  			panic("illegal op in BinaryExpr: " + e.Op.String())
   749  		}
   750  
   751  	case *ast.SliceExpr:
   752  		var low, high, max Value
   753  		var x Value
   754  		xtyp := fn.typeOf(e.X)
   755  		switch typeparams.CoreType(xtyp).(type) {
   756  		case *types.Array:
   757  			// Potentially escaping.
   758  			x = b.addr(fn, e.X, true).address(fn)
   759  		case *types.Basic, *types.Slice, *types.Pointer: // *array
   760  			x = b.expr(fn, e.X)
   761  		default:
   762  			// core type exception?
   763  			if isBytestring(xtyp) {
   764  				x = b.expr(fn, e.X) // bytestring is handled as string and []byte.
   765  			} else {
   766  				panic("unexpected sequence type in SliceExpr")
   767  			}
   768  		}
   769  		if e.Low != nil {
   770  			low = b.expr(fn, e.Low)
   771  		}
   772  		if e.High != nil {
   773  			high = b.expr(fn, e.High)
   774  		}
   775  		if e.Slice3 {
   776  			max = b.expr(fn, e.Max)
   777  		}
   778  		v := &Slice{
   779  			X:    x,
   780  			Low:  low,
   781  			High: high,
   782  			Max:  max,
   783  		}
   784  		v.setPos(e.Lbrack)
   785  		v.setType(fn.typ(tv.Type))
   786  		return fn.emit(v)
   787  
   788  	case *ast.Ident:
   789  		obj := fn.info.Uses[e]
   790  		// Universal built-in or nil?
   791  		switch obj := obj.(type) {
   792  		case *types.Builtin:
   793  			return &Builtin{name: obj.Name(), sig: fn.instanceType(e).(*types.Signature)}
   794  		case *types.Nil:
   795  			return zeroConst(fn.instanceType(e))
   796  		}
   797  		// Package-level func or var?
   798  		if v := fn.Prog.packageLevelMember(obj); v != nil {
   799  			if g, ok := v.(*Global); ok {
   800  				return emitLoad(fn, g) // var (address)
   801  			}
   802  			callee := v.(*Function) // (func)
   803  			if callee.typeparams.Len() > 0 {
   804  				targs := fn.subst.types(instanceArgs(fn.info, e))
   805  				callee = fn.Prog.needsInstance(callee, targs, b.created)
   806  			}
   807  			return callee
   808  		}
   809  		// Local var.
   810  		return emitLoad(fn, fn.lookup(obj, false)) // var (address)
   811  
   812  	case *ast.SelectorExpr:
   813  		sel := fn.selection(e)
   814  		if sel == nil {
   815  			// builtin unsafe.{Add,Slice}
   816  			if obj, ok := fn.info.Uses[e.Sel].(*types.Builtin); ok {
   817  				return &Builtin{name: obj.Name(), sig: fn.typ(tv.Type).(*types.Signature)}
   818  			}
   819  			// qualified identifier
   820  			return b.expr(fn, e.Sel)
   821  		}
   822  		switch sel.kind {
   823  		case types.MethodExpr:
   824  			// (*T).f or T.f, the method f from the method-set of type T.
   825  			// The result is a "thunk".
   826  			thunk := makeThunk(fn.Prog, sel, b.created)
   827  			return emitConv(fn, thunk, fn.typ(tv.Type))
   828  
   829  		case types.MethodVal:
   830  			// e.f where e is an expression and f is a method.
   831  			// The result is a "bound".
   832  			obj := sel.obj.(*types.Func)
   833  			rt := fn.typ(recvType(obj))
   834  			wantAddr := isPointer(rt)
   835  			escaping := true
   836  			v := b.receiver(fn, e.X, wantAddr, escaping, sel)
   837  
   838  			if types.IsInterface(rt) {
   839  				// If v may be an interface type I (after instantiating),
   840  				// we must emit a check that v is non-nil.
   841  				if recv, ok := sel.recv.(*typeparams.TypeParam); ok {
   842  					// Emit a nil check if any possible instantiation of the
   843  					// type parameter is an interface type.
   844  					if typeSetOf(recv).Len() > 0 {
   845  						// recv has a concrete term its typeset.
   846  						// So it cannot be instantiated as an interface.
   847  						//
   848  						// Example:
   849  						// func _[T interface{~int; Foo()}] () {
   850  						//    var v T
   851  						//    _ = v.Foo // <-- MethodVal
   852  						// }
   853  					} else {
   854  						// rt may be instantiated as an interface.
   855  						// Emit nil check: typeassert (any(v)).(any).
   856  						emitTypeAssert(fn, emitConv(fn, v, tEface), tEface, token.NoPos)
   857  					}
   858  				} else {
   859  					// non-type param interface
   860  					// Emit nil check: typeassert v.(I).
   861  					emitTypeAssert(fn, v, rt, token.NoPos)
   862  				}
   863  			}
   864  			if targs := receiverTypeArgs(obj); len(targs) > 0 {
   865  				// obj is generic.
   866  				obj = fn.Prog.canon.instantiateMethod(obj, fn.subst.types(targs), fn.Prog.ctxt)
   867  			}
   868  			c := &MakeClosure{
   869  				Fn:       makeBound(fn.Prog, obj, b.created),
   870  				Bindings: []Value{v},
   871  			}
   872  			c.setPos(e.Sel.Pos())
   873  			c.setType(fn.typ(tv.Type))
   874  			return fn.emit(c)
   875  
   876  		case types.FieldVal:
   877  			indices := sel.index
   878  			last := len(indices) - 1
   879  			v := b.expr(fn, e.X)
   880  			v = emitImplicitSelections(fn, v, indices[:last], e.Pos())
   881  			v = emitFieldSelection(fn, v, indices[last], false, e.Sel)
   882  			return v
   883  		}
   884  
   885  		panic("unexpected expression-relative selector")
   886  
   887  	case *typeparams.IndexListExpr:
   888  		// f[X, Y] must be a generic function
   889  		if !instance(fn.info, e.X) {
   890  			panic("unexpected expression-could not match index list to instantiation")
   891  		}
   892  		return b.expr(fn, e.X) // Handle instantiation within the *Ident or *SelectorExpr cases.
   893  
   894  	case *ast.IndexExpr:
   895  		if instance(fn.info, e.X) {
   896  			return b.expr(fn, e.X) // Handle instantiation within the *Ident or *SelectorExpr cases.
   897  		}
   898  		// not a generic instantiation.
   899  		xt := fn.typeOf(e.X)
   900  		switch et, mode := indexType(xt); mode {
   901  		case ixVar:
   902  			// Addressable slice/array; use IndexAddr and Load.
   903  			return b.addr(fn, e, false).load(fn)
   904  
   905  		case ixArrVar, ixValue:
   906  			// An array in a register, a string or a combined type that contains
   907  			// either an [_]array (ixArrVar) or string (ixValue).
   908  
   909  			// Note: for ixArrVar and CoreType(xt)==nil can be IndexAddr and Load.
   910  			index := b.expr(fn, e.Index)
   911  			if isUntyped(index.Type()) {
   912  				index = emitConv(fn, index, tInt)
   913  			}
   914  			v := &Index{
   915  				X:     b.expr(fn, e.X),
   916  				Index: index,
   917  			}
   918  			v.setPos(e.Lbrack)
   919  			v.setType(et)
   920  			return fn.emit(v)
   921  
   922  		case ixMap:
   923  			ct := typeparams.CoreType(xt).(*types.Map)
   924  			v := &Lookup{
   925  				X:     b.expr(fn, e.X),
   926  				Index: emitConv(fn, b.expr(fn, e.Index), ct.Key()),
   927  			}
   928  			v.setPos(e.Lbrack)
   929  			v.setType(ct.Elem())
   930  			return fn.emit(v)
   931  		default:
   932  			panic("unexpected container type in IndexExpr: " + xt.String())
   933  		}
   934  
   935  	case *ast.CompositeLit, *ast.StarExpr:
   936  		// Addressable types (lvalues)
   937  		return b.addr(fn, e, false).load(fn)
   938  	}
   939  
   940  	panic(fmt.Sprintf("unexpected expr: %T", e))
   941  }
   942  
   943  // stmtList emits to fn code for all statements in list.
   944  func (b *builder) stmtList(fn *Function, list []ast.Stmt) {
   945  	for _, s := range list {
   946  		b.stmt(fn, s)
   947  	}
   948  }
   949  
   950  // receiver emits to fn code for expression e in the "receiver"
   951  // position of selection e.f (where f may be a field or a method) and
   952  // returns the effective receiver after applying the implicit field
   953  // selections of sel.
   954  //
   955  // wantAddr requests that the result is an an address.  If
   956  // !sel.indirect, this may require that e be built in addr() mode; it
   957  // must thus be addressable.
   958  //
   959  // escaping is defined as per builder.addr().
   960  func (b *builder) receiver(fn *Function, e ast.Expr, wantAddr, escaping bool, sel *selection) Value {
   961  	var v Value
   962  	if wantAddr && !sel.indirect && !isPointer(fn.typeOf(e)) {
   963  		v = b.addr(fn, e, escaping).address(fn)
   964  	} else {
   965  		v = b.expr(fn, e)
   966  	}
   967  
   968  	last := len(sel.index) - 1
   969  	// The position of implicit selection is the position of the inducing receiver expression.
   970  	v = emitImplicitSelections(fn, v, sel.index[:last], e.Pos())
   971  	if !wantAddr && isPointer(v.Type()) {
   972  		v = emitLoad(fn, v)
   973  	}
   974  	return v
   975  }
   976  
   977  // setCallFunc populates the function parts of a CallCommon structure
   978  // (Func, Method, Recv, Args[0]) based on the kind of invocation
   979  // occurring in e.
   980  func (b *builder) setCallFunc(fn *Function, e *ast.CallExpr, c *CallCommon) {
   981  	c.pos = e.Lparen
   982  
   983  	// Is this a method call?
   984  	if selector, ok := unparen(e.Fun).(*ast.SelectorExpr); ok {
   985  		sel := fn.selection(selector)
   986  		if sel != nil && sel.kind == types.MethodVal {
   987  			obj := sel.obj.(*types.Func)
   988  			recv := recvType(obj)
   989  
   990  			wantAddr := isPointer(recv)
   991  			escaping := true
   992  			v := b.receiver(fn, selector.X, wantAddr, escaping, sel)
   993  			if types.IsInterface(recv) {
   994  				// Invoke-mode call.
   995  				c.Value = v // possibly type param
   996  				c.Method = obj
   997  			} else {
   998  				// "Call"-mode call.
   999  				callee := fn.Prog.originFunc(obj)
  1000  				if callee.typeparams.Len() > 0 {
  1001  					callee = fn.Prog.needsInstance(callee, receiverTypeArgs(obj), b.created)
  1002  				}
  1003  				c.Value = callee
  1004  				c.Args = append(c.Args, v)
  1005  			}
  1006  			return
  1007  		}
  1008  
  1009  		// sel.kind==MethodExpr indicates T.f() or (*T).f():
  1010  		// a statically dispatched call to the method f in the
  1011  		// method-set of T or *T.  T may be an interface.
  1012  		//
  1013  		// e.Fun would evaluate to a concrete method, interface
  1014  		// wrapper function, or promotion wrapper.
  1015  		//
  1016  		// For now, we evaluate it in the usual way.
  1017  		//
  1018  		// TODO(adonovan): opt: inline expr() here, to make the
  1019  		// call static and to avoid generation of wrappers.
  1020  		// It's somewhat tricky as it may consume the first
  1021  		// actual parameter if the call is "invoke" mode.
  1022  		//
  1023  		// Examples:
  1024  		//  type T struct{}; func (T) f() {}   // "call" mode
  1025  		//  type T interface { f() }           // "invoke" mode
  1026  		//
  1027  		//  type S struct{ T }
  1028  		//
  1029  		//  var s S
  1030  		//  S.f(s)
  1031  		//  (*S).f(&s)
  1032  		//
  1033  		// Suggested approach:
  1034  		// - consume the first actual parameter expression
  1035  		//   and build it with b.expr().
  1036  		// - apply implicit field selections.
  1037  		// - use MethodVal logic to populate fields of c.
  1038  	}
  1039  
  1040  	// Evaluate the function operand in the usual way.
  1041  	c.Value = b.expr(fn, e.Fun)
  1042  }
  1043  
  1044  // emitCallArgs emits to f code for the actual parameters of call e to
  1045  // a (possibly built-in) function of effective type sig.
  1046  // The argument values are appended to args, which is then returned.
  1047  func (b *builder) emitCallArgs(fn *Function, sig *types.Signature, e *ast.CallExpr, args []Value) []Value {
  1048  	// f(x, y, z...): pass slice z straight through.
  1049  	if e.Ellipsis != 0 {
  1050  		for i, arg := range e.Args {
  1051  			v := emitConv(fn, b.expr(fn, arg), sig.Params().At(i).Type())
  1052  			args = append(args, v)
  1053  		}
  1054  		return args
  1055  	}
  1056  
  1057  	offset := len(args) // 1 if call has receiver, 0 otherwise
  1058  
  1059  	// Evaluate actual parameter expressions.
  1060  	//
  1061  	// If this is a chained call of the form f(g()) where g has
  1062  	// multiple return values (MRV), they are flattened out into
  1063  	// args; a suffix of them may end up in a varargs slice.
  1064  	for _, arg := range e.Args {
  1065  		v := b.expr(fn, arg)
  1066  		if ttuple, ok := v.Type().(*types.Tuple); ok { // MRV chain
  1067  			for i, n := 0, ttuple.Len(); i < n; i++ {
  1068  				args = append(args, emitExtract(fn, v, i))
  1069  			}
  1070  		} else {
  1071  			args = append(args, v)
  1072  		}
  1073  	}
  1074  
  1075  	// Actual->formal assignability conversions for normal parameters.
  1076  	np := sig.Params().Len() // number of normal parameters
  1077  	if sig.Variadic() {
  1078  		np--
  1079  	}
  1080  	for i := 0; i < np; i++ {
  1081  		args[offset+i] = emitConv(fn, args[offset+i], sig.Params().At(i).Type())
  1082  	}
  1083  
  1084  	// Actual->formal assignability conversions for variadic parameter,
  1085  	// and construction of slice.
  1086  	if sig.Variadic() {
  1087  		varargs := args[offset+np:]
  1088  		st := sig.Params().At(np).Type().(*types.Slice)
  1089  		vt := st.Elem()
  1090  		if len(varargs) == 0 {
  1091  			args = append(args, zeroConst(st))
  1092  		} else {
  1093  			// Replace a suffix of args with a slice containing it.
  1094  			at := types.NewArray(vt, int64(len(varargs)))
  1095  			a := emitNew(fn, at, token.NoPos)
  1096  			a.setPos(e.Rparen)
  1097  			a.Comment = "varargs"
  1098  			for i, arg := range varargs {
  1099  				iaddr := &IndexAddr{
  1100  					X:     a,
  1101  					Index: intConst(int64(i)),
  1102  				}
  1103  				iaddr.setType(types.NewPointer(vt))
  1104  				fn.emit(iaddr)
  1105  				emitStore(fn, iaddr, arg, arg.Pos())
  1106  			}
  1107  			s := &Slice{X: a}
  1108  			s.setType(st)
  1109  			args[offset+np] = fn.emit(s)
  1110  			args = args[:offset+np+1]
  1111  		}
  1112  	}
  1113  	return args
  1114  }
  1115  
  1116  // setCall emits to fn code to evaluate all the parameters of a function
  1117  // call e, and populates *c with those values.
  1118  func (b *builder) setCall(fn *Function, e *ast.CallExpr, c *CallCommon) {
  1119  	// First deal with the f(...) part and optional receiver.
  1120  	b.setCallFunc(fn, e, c)
  1121  
  1122  	// Then append the other actual parameters.
  1123  	sig, _ := typeparams.CoreType(fn.typeOf(e.Fun)).(*types.Signature)
  1124  	if sig == nil {
  1125  		panic(fmt.Sprintf("no signature for call of %s", e.Fun))
  1126  	}
  1127  	c.Args = b.emitCallArgs(fn, sig, e, c.Args)
  1128  }
  1129  
  1130  // assignOp emits to fn code to perform loc <op>= val.
  1131  func (b *builder) assignOp(fn *Function, loc lvalue, val Value, op token.Token, pos token.Pos) {
  1132  	loc.store(fn, emitArith(fn, op, loc.load(fn), val, loc.typ(), pos))
  1133  }
  1134  
  1135  // localValueSpec emits to fn code to define all of the vars in the
  1136  // function-local ValueSpec, spec.
  1137  func (b *builder) localValueSpec(fn *Function, spec *ast.ValueSpec) {
  1138  	switch {
  1139  	case len(spec.Values) == len(spec.Names):
  1140  		// e.g. var x, y = 0, 1
  1141  		// 1:1 assignment
  1142  		for i, id := range spec.Names {
  1143  			if !isBlankIdent(id) {
  1144  				fn.addLocalForIdent(id)
  1145  			}
  1146  			lval := b.addr(fn, id, false) // non-escaping
  1147  			b.assign(fn, lval, spec.Values[i], true, nil)
  1148  		}
  1149  
  1150  	case len(spec.Values) == 0:
  1151  		// e.g. var x, y int
  1152  		// Locals are implicitly zero-initialized.
  1153  		for _, id := range spec.Names {
  1154  			if !isBlankIdent(id) {
  1155  				lhs := fn.addLocalForIdent(id)
  1156  				if fn.debugInfo() {
  1157  					emitDebugRef(fn, id, lhs, true)
  1158  				}
  1159  			}
  1160  		}
  1161  
  1162  	default:
  1163  		// e.g. var x, y = pos()
  1164  		tuple := b.exprN(fn, spec.Values[0])
  1165  		for i, id := range spec.Names {
  1166  			if !isBlankIdent(id) {
  1167  				fn.addLocalForIdent(id)
  1168  				lhs := b.addr(fn, id, false) // non-escaping
  1169  				lhs.store(fn, emitExtract(fn, tuple, i))
  1170  			}
  1171  		}
  1172  	}
  1173  }
  1174  
  1175  // assignStmt emits code to fn for a parallel assignment of rhss to lhss.
  1176  // isDef is true if this is a short variable declaration (:=).
  1177  //
  1178  // Note the similarity with localValueSpec.
  1179  func (b *builder) assignStmt(fn *Function, lhss, rhss []ast.Expr, isDef bool) {
  1180  	// Side effects of all LHSs and RHSs must occur in left-to-right order.
  1181  	lvals := make([]lvalue, len(lhss))
  1182  	isZero := make([]bool, len(lhss))
  1183  	for i, lhs := range lhss {
  1184  		var lval lvalue = blank{}
  1185  		if !isBlankIdent(lhs) {
  1186  			if isDef {
  1187  				if obj := fn.info.Defs[lhs.(*ast.Ident)]; obj != nil {
  1188  					fn.addNamedLocal(obj)
  1189  					isZero[i] = true
  1190  				}
  1191  			}
  1192  			lval = b.addr(fn, lhs, false) // non-escaping
  1193  		}
  1194  		lvals[i] = lval
  1195  	}
  1196  	if len(lhss) == len(rhss) {
  1197  		// Simple assignment:   x     = f()        (!isDef)
  1198  		// Parallel assignment: x, y  = f(), g()   (!isDef)
  1199  		// or short var decl:   x, y := f(), g()   (isDef)
  1200  		//
  1201  		// In all cases, the RHSs may refer to the LHSs,
  1202  		// so we need a storebuf.
  1203  		var sb storebuf
  1204  		for i := range rhss {
  1205  			b.assign(fn, lvals[i], rhss[i], isZero[i], &sb)
  1206  		}
  1207  		sb.emit(fn)
  1208  	} else {
  1209  		// e.g. x, y = pos()
  1210  		tuple := b.exprN(fn, rhss[0])
  1211  		emitDebugRef(fn, rhss[0], tuple, false)
  1212  		for i, lval := range lvals {
  1213  			lval.store(fn, emitExtract(fn, tuple, i))
  1214  		}
  1215  	}
  1216  }
  1217  
  1218  // arrayLen returns the length of the array whose composite literal elements are elts.
  1219  func (b *builder) arrayLen(fn *Function, elts []ast.Expr) int64 {
  1220  	var max int64 = -1
  1221  	var i int64 = -1
  1222  	for _, e := range elts {
  1223  		if kv, ok := e.(*ast.KeyValueExpr); ok {
  1224  			i = b.expr(fn, kv.Key).(*Const).Int64()
  1225  		} else {
  1226  			i++
  1227  		}
  1228  		if i > max {
  1229  			max = i
  1230  		}
  1231  	}
  1232  	return max + 1
  1233  }
  1234  
  1235  // compLit emits to fn code to initialize a composite literal e at
  1236  // address addr with type typ.
  1237  //
  1238  // Nested composite literals are recursively initialized in place
  1239  // where possible. If isZero is true, compLit assumes that addr
  1240  // holds the zero value for typ.
  1241  //
  1242  // Because the elements of a composite literal may refer to the
  1243  // variables being updated, as in the second line below,
  1244  //
  1245  //	x := T{a: 1}
  1246  //	x = T{a: x.a}
  1247  //
  1248  // all the reads must occur before all the writes.  Thus all stores to
  1249  // loc are emitted to the storebuf sb for later execution.
  1250  //
  1251  // A CompositeLit may have pointer type only in the recursive (nested)
  1252  // case when the type name is implicit.  e.g. in []*T{{}}, the inner
  1253  // literal has type *T behaves like &T{}.
  1254  // In that case, addr must hold a T, not a *T.
  1255  func (b *builder) compLit(fn *Function, addr Value, e *ast.CompositeLit, isZero bool, sb *storebuf) {
  1256  	typ := deref(fn.typeOf(e))                        // type with name [may be type param]
  1257  	t := deref(typeparams.CoreType(typ)).Underlying() // core type for comp lit case
  1258  	// Computing typ and t is subtle as these handle pointer types.
  1259  	// For example, &T{...} is valid even for maps and slices.
  1260  	// Also typ should refer to T (not *T) while t should be the core type of T.
  1261  	//
  1262  	// To show the ordering to take into account, consider the composite literal
  1263  	// expressions `&T{f: 1}` and `{f: 1}` within the expression `[]S{{f: 1}}` here:
  1264  	//   type N struct{f int}
  1265  	//   func _[T N, S *N]() {
  1266  	//     _ = &T{f: 1}
  1267  	//     _ = []S{{f: 1}}
  1268  	//   }
  1269  	// For `&T{f: 1}`, we compute `typ` and `t` as:
  1270  	//     typeOf(&T{f: 1}) == *T
  1271  	//     deref(*T)        == T (typ)
  1272  	//     CoreType(T)      == N
  1273  	//     deref(N)         == N
  1274  	//     N.Underlying()   == struct{f int} (t)
  1275  	// For `{f: 1}` in `[]S{{f: 1}}`,  we compute `typ` and `t` as:
  1276  	//     typeOf({f: 1})   == S
  1277  	//     deref(S)         == S (typ)
  1278  	//     CoreType(S)      == *N
  1279  	//     deref(*N)        == N
  1280  	//     N.Underlying()   == struct{f int} (t)
  1281  	switch t := t.(type) {
  1282  	case *types.Struct:
  1283  		if !isZero && len(e.Elts) != t.NumFields() {
  1284  			// memclear
  1285  			sb.store(&address{addr, e.Lbrace, nil},
  1286  				zeroValue(fn, deref(addr.Type())))
  1287  			isZero = true
  1288  		}
  1289  		for i, e := range e.Elts {
  1290  			fieldIndex := i
  1291  			pos := e.Pos()
  1292  			if kv, ok := e.(*ast.KeyValueExpr); ok {
  1293  				fname := kv.Key.(*ast.Ident).Name
  1294  				for i, n := 0, t.NumFields(); i < n; i++ {
  1295  					sf := t.Field(i)
  1296  					if sf.Name() == fname {
  1297  						fieldIndex = i
  1298  						pos = kv.Colon
  1299  						e = kv.Value
  1300  						break
  1301  					}
  1302  				}
  1303  			}
  1304  			sf := t.Field(fieldIndex)
  1305  			faddr := &FieldAddr{
  1306  				X:     addr,
  1307  				Field: fieldIndex,
  1308  			}
  1309  			faddr.setPos(pos)
  1310  			faddr.setType(types.NewPointer(sf.Type()))
  1311  			fn.emit(faddr)
  1312  			b.assign(fn, &address{addr: faddr, pos: pos, expr: e}, e, isZero, sb)
  1313  		}
  1314  
  1315  	case *types.Array, *types.Slice:
  1316  		var at *types.Array
  1317  		var array Value
  1318  		switch t := t.(type) {
  1319  		case *types.Slice:
  1320  			at = types.NewArray(t.Elem(), b.arrayLen(fn, e.Elts))
  1321  			alloc := emitNew(fn, at, e.Lbrace)
  1322  			alloc.Comment = "slicelit"
  1323  			array = alloc
  1324  		case *types.Array:
  1325  			at = t
  1326  			array = addr
  1327  
  1328  			if !isZero && int64(len(e.Elts)) != at.Len() {
  1329  				// memclear
  1330  				sb.store(&address{array, e.Lbrace, nil},
  1331  					zeroValue(fn, deref(array.Type())))
  1332  			}
  1333  		}
  1334  
  1335  		var idx *Const
  1336  		for _, e := range e.Elts {
  1337  			pos := e.Pos()
  1338  			if kv, ok := e.(*ast.KeyValueExpr); ok {
  1339  				idx = b.expr(fn, kv.Key).(*Const)
  1340  				pos = kv.Colon
  1341  				e = kv.Value
  1342  			} else {
  1343  				var idxval int64
  1344  				if idx != nil {
  1345  					idxval = idx.Int64() + 1
  1346  				}
  1347  				idx = intConst(idxval)
  1348  			}
  1349  			iaddr := &IndexAddr{
  1350  				X:     array,
  1351  				Index: idx,
  1352  			}
  1353  			iaddr.setType(types.NewPointer(at.Elem()))
  1354  			fn.emit(iaddr)
  1355  			if t != at { // slice
  1356  				// backing array is unaliased => storebuf not needed.
  1357  				b.assign(fn, &address{addr: iaddr, pos: pos, expr: e}, e, true, nil)
  1358  			} else {
  1359  				b.assign(fn, &address{addr: iaddr, pos: pos, expr: e}, e, true, sb)
  1360  			}
  1361  		}
  1362  
  1363  		if t != at { // slice
  1364  			s := &Slice{X: array}
  1365  			s.setPos(e.Lbrace)
  1366  			s.setType(typ)
  1367  			sb.store(&address{addr: addr, pos: e.Lbrace, expr: e}, fn.emit(s))
  1368  		}
  1369  
  1370  	case *types.Map:
  1371  		m := &MakeMap{Reserve: intConst(int64(len(e.Elts)))}
  1372  		m.setPos(e.Lbrace)
  1373  		m.setType(typ)
  1374  		fn.emit(m)
  1375  		for _, e := range e.Elts {
  1376  			e := e.(*ast.KeyValueExpr)
  1377  
  1378  			// If a key expression in a map literal is itself a
  1379  			// composite literal, the type may be omitted.
  1380  			// For example:
  1381  			//	map[*struct{}]bool{{}: true}
  1382  			// An &-operation may be implied:
  1383  			//	map[*struct{}]bool{&struct{}{}: true}
  1384  			var key Value
  1385  			if _, ok := unparen(e.Key).(*ast.CompositeLit); ok && isPointer(t.Key()) {
  1386  				// A CompositeLit never evaluates to a pointer,
  1387  				// so if the type of the location is a pointer,
  1388  				// an &-operation is implied.
  1389  				key = b.addr(fn, e.Key, true).address(fn)
  1390  			} else {
  1391  				key = b.expr(fn, e.Key)
  1392  			}
  1393  
  1394  			loc := element{
  1395  				m:   m,
  1396  				k:   emitConv(fn, key, t.Key()),
  1397  				t:   t.Elem(),
  1398  				pos: e.Colon,
  1399  			}
  1400  
  1401  			// We call assign() only because it takes care
  1402  			// of any &-operation required in the recursive
  1403  			// case, e.g.,
  1404  			// map[int]*struct{}{0: {}} implies &struct{}{}.
  1405  			// In-place update is of course impossible,
  1406  			// and no storebuf is needed.
  1407  			b.assign(fn, &loc, e.Value, true, nil)
  1408  		}
  1409  		sb.store(&address{addr: addr, pos: e.Lbrace, expr: e}, m)
  1410  
  1411  	default:
  1412  		panic("unexpected CompositeLit type: " + t.String())
  1413  	}
  1414  }
  1415  
  1416  // switchStmt emits to fn code for the switch statement s, optionally
  1417  // labelled by label.
  1418  func (b *builder) switchStmt(fn *Function, s *ast.SwitchStmt, label *lblock) {
  1419  	// We treat SwitchStmt like a sequential if-else chain.
  1420  	// Multiway dispatch can be recovered later by ssautil.Switches()
  1421  	// to those cases that are free of side effects.
  1422  	if s.Init != nil {
  1423  		b.stmt(fn, s.Init)
  1424  	}
  1425  	var tag Value = vTrue
  1426  	if s.Tag != nil {
  1427  		tag = b.expr(fn, s.Tag)
  1428  	}
  1429  	done := fn.newBasicBlock("switch.done")
  1430  	if label != nil {
  1431  		label._break = done
  1432  	}
  1433  	// We pull the default case (if present) down to the end.
  1434  	// But each fallthrough label must point to the next
  1435  	// body block in source order, so we preallocate a
  1436  	// body block (fallthru) for the next case.
  1437  	// Unfortunately this makes for a confusing block order.
  1438  	var dfltBody *[]ast.Stmt
  1439  	var dfltFallthrough *BasicBlock
  1440  	var fallthru, dfltBlock *BasicBlock
  1441  	ncases := len(s.Body.List)
  1442  	for i, clause := range s.Body.List {
  1443  		body := fallthru
  1444  		if body == nil {
  1445  			body = fn.newBasicBlock("switch.body") // first case only
  1446  		}
  1447  
  1448  		// Preallocate body block for the next case.
  1449  		fallthru = done
  1450  		if i+1 < ncases {
  1451  			fallthru = fn.newBasicBlock("switch.body")
  1452  		}
  1453  
  1454  		cc := clause.(*ast.CaseClause)
  1455  		if cc.List == nil {
  1456  			// Default case.
  1457  			dfltBody = &cc.Body
  1458  			dfltFallthrough = fallthru
  1459  			dfltBlock = body
  1460  			continue
  1461  		}
  1462  
  1463  		var nextCond *BasicBlock
  1464  		for _, cond := range cc.List {
  1465  			nextCond = fn.newBasicBlock("switch.next")
  1466  			// TODO(adonovan): opt: when tag==vTrue, we'd
  1467  			// get better code if we use b.cond(cond)
  1468  			// instead of BinOp(EQL, tag, b.expr(cond))
  1469  			// followed by If.  Don't forget conversions
  1470  			// though.
  1471  			cond := emitCompare(fn, token.EQL, tag, b.expr(fn, cond), cond.Pos())
  1472  			emitIf(fn, cond, body, nextCond)
  1473  			fn.currentBlock = nextCond
  1474  		}
  1475  		fn.currentBlock = body
  1476  		fn.targets = &targets{
  1477  			tail:         fn.targets,
  1478  			_break:       done,
  1479  			_fallthrough: fallthru,
  1480  		}
  1481  		b.stmtList(fn, cc.Body)
  1482  		fn.targets = fn.targets.tail
  1483  		emitJump(fn, done)
  1484  		fn.currentBlock = nextCond
  1485  	}
  1486  	if dfltBlock != nil {
  1487  		emitJump(fn, dfltBlock)
  1488  		fn.currentBlock = dfltBlock
  1489  		fn.targets = &targets{
  1490  			tail:         fn.targets,
  1491  			_break:       done,
  1492  			_fallthrough: dfltFallthrough,
  1493  		}
  1494  		b.stmtList(fn, *dfltBody)
  1495  		fn.targets = fn.targets.tail
  1496  	}
  1497  	emitJump(fn, done)
  1498  	fn.currentBlock = done
  1499  }
  1500  
  1501  // typeSwitchStmt emits to fn code for the type switch statement s, optionally
  1502  // labelled by label.
  1503  func (b *builder) typeSwitchStmt(fn *Function, s *ast.TypeSwitchStmt, label *lblock) {
  1504  	// We treat TypeSwitchStmt like a sequential if-else chain.
  1505  	// Multiway dispatch can be recovered later by ssautil.Switches().
  1506  
  1507  	// Typeswitch lowering:
  1508  	//
  1509  	// var x X
  1510  	// switch y := x.(type) {
  1511  	// case T1, T2: S1                  // >1 	(y := x)
  1512  	// case nil:    SN                  // nil 	(y := x)
  1513  	// default:     SD                  // 0 types 	(y := x)
  1514  	// case T3:     S3                  // 1 type 	(y := x.(T3))
  1515  	// }
  1516  	//
  1517  	//      ...s.Init...
  1518  	// 	x := eval x
  1519  	// .caseT1:
  1520  	// 	t1, ok1 := typeswitch,ok x <T1>
  1521  	// 	if ok1 then goto S1 else goto .caseT2
  1522  	// .caseT2:
  1523  	// 	t2, ok2 := typeswitch,ok x <T2>
  1524  	// 	if ok2 then goto S1 else goto .caseNil
  1525  	// .S1:
  1526  	//      y := x
  1527  	// 	...S1...
  1528  	// 	goto done
  1529  	// .caseNil:
  1530  	// 	if t2, ok2 := typeswitch,ok x <T2>
  1531  	// 	if x == nil then goto SN else goto .caseT3
  1532  	// .SN:
  1533  	//      y := x
  1534  	// 	...SN...
  1535  	// 	goto done
  1536  	// .caseT3:
  1537  	// 	t3, ok3 := typeswitch,ok x <T3>
  1538  	// 	if ok3 then goto S3 else goto default
  1539  	// .S3:
  1540  	//      y := t3
  1541  	// 	...S3...
  1542  	// 	goto done
  1543  	// .default:
  1544  	//      y := x
  1545  	// 	...SD...
  1546  	// 	goto done
  1547  	// .done:
  1548  	if s.Init != nil {
  1549  		b.stmt(fn, s.Init)
  1550  	}
  1551  
  1552  	var x Value
  1553  	switch ass := s.Assign.(type) {
  1554  	case *ast.ExprStmt: // x.(type)
  1555  		x = b.expr(fn, unparen(ass.X).(*ast.TypeAssertExpr).X)
  1556  	case *ast.AssignStmt: // y := x.(type)
  1557  		x = b.expr(fn, unparen(ass.Rhs[0]).(*ast.TypeAssertExpr).X)
  1558  	}
  1559  
  1560  	done := fn.newBasicBlock("typeswitch.done")
  1561  	if label != nil {
  1562  		label._break = done
  1563  	}
  1564  	var default_ *ast.CaseClause
  1565  	for _, clause := range s.Body.List {
  1566  		cc := clause.(*ast.CaseClause)
  1567  		if cc.List == nil {
  1568  			default_ = cc
  1569  			continue
  1570  		}
  1571  		body := fn.newBasicBlock("typeswitch.body")
  1572  		var next *BasicBlock
  1573  		var casetype types.Type
  1574  		var ti Value // ti, ok := typeassert,ok x <Ti>
  1575  		for _, cond := range cc.List {
  1576  			next = fn.newBasicBlock("typeswitch.next")
  1577  			casetype = fn.typeOf(cond)
  1578  			var condv Value
  1579  			if casetype == tUntypedNil {
  1580  				condv = emitCompare(fn, token.EQL, x, zeroConst(x.Type()), cond.Pos())
  1581  				ti = x
  1582  			} else {
  1583  				yok := emitTypeTest(fn, x, casetype, cc.Case)
  1584  				ti = emitExtract(fn, yok, 0)
  1585  				condv = emitExtract(fn, yok, 1)
  1586  			}
  1587  			emitIf(fn, condv, body, next)
  1588  			fn.currentBlock = next
  1589  		}
  1590  		if len(cc.List) != 1 {
  1591  			ti = x
  1592  		}
  1593  		fn.currentBlock = body
  1594  		b.typeCaseBody(fn, cc, ti, done)
  1595  		fn.currentBlock = next
  1596  	}
  1597  	if default_ != nil {
  1598  		b.typeCaseBody(fn, default_, x, done)
  1599  	} else {
  1600  		emitJump(fn, done)
  1601  	}
  1602  	fn.currentBlock = done
  1603  }
  1604  
  1605  func (b *builder) typeCaseBody(fn *Function, cc *ast.CaseClause, x Value, done *BasicBlock) {
  1606  	if obj := fn.info.Implicits[cc]; obj != nil {
  1607  		// In a switch y := x.(type), each case clause
  1608  		// implicitly declares a distinct object y.
  1609  		// In a single-type case, y has that type.
  1610  		// In multi-type cases, 'case nil' and default,
  1611  		// y has the same type as the interface operand.
  1612  		emitStore(fn, fn.addNamedLocal(obj), x, obj.Pos())
  1613  	}
  1614  	fn.targets = &targets{
  1615  		tail:   fn.targets,
  1616  		_break: done,
  1617  	}
  1618  	b.stmtList(fn, cc.Body)
  1619  	fn.targets = fn.targets.tail
  1620  	emitJump(fn, done)
  1621  }
  1622  
  1623  // selectStmt emits to fn code for the select statement s, optionally
  1624  // labelled by label.
  1625  func (b *builder) selectStmt(fn *Function, s *ast.SelectStmt, label *lblock) {
  1626  	// A blocking select of a single case degenerates to a
  1627  	// simple send or receive.
  1628  	// TODO(adonovan): opt: is this optimization worth its weight?
  1629  	if len(s.Body.List) == 1 {
  1630  		clause := s.Body.List[0].(*ast.CommClause)
  1631  		if clause.Comm != nil {
  1632  			b.stmt(fn, clause.Comm)
  1633  			done := fn.newBasicBlock("select.done")
  1634  			if label != nil {
  1635  				label._break = done
  1636  			}
  1637  			fn.targets = &targets{
  1638  				tail:   fn.targets,
  1639  				_break: done,
  1640  			}
  1641  			b.stmtList(fn, clause.Body)
  1642  			fn.targets = fn.targets.tail
  1643  			emitJump(fn, done)
  1644  			fn.currentBlock = done
  1645  			return
  1646  		}
  1647  	}
  1648  
  1649  	// First evaluate all channels in all cases, and find
  1650  	// the directions of each state.
  1651  	var states []*SelectState
  1652  	blocking := true
  1653  	debugInfo := fn.debugInfo()
  1654  	for _, clause := range s.Body.List {
  1655  		var st *SelectState
  1656  		switch comm := clause.(*ast.CommClause).Comm.(type) {
  1657  		case nil: // default case
  1658  			blocking = false
  1659  			continue
  1660  
  1661  		case *ast.SendStmt: // ch<- i
  1662  			ch := b.expr(fn, comm.Chan)
  1663  			chtyp := typeparams.CoreType(fn.typ(ch.Type())).(*types.Chan)
  1664  			st = &SelectState{
  1665  				Dir:  types.SendOnly,
  1666  				Chan: ch,
  1667  				Send: emitConv(fn, b.expr(fn, comm.Value), chtyp.Elem()),
  1668  				Pos:  comm.Arrow,
  1669  			}
  1670  			if debugInfo {
  1671  				st.DebugNode = comm
  1672  			}
  1673  
  1674  		case *ast.AssignStmt: // x := <-ch
  1675  			recv := unparen(comm.Rhs[0]).(*ast.UnaryExpr)
  1676  			st = &SelectState{
  1677  				Dir:  types.RecvOnly,
  1678  				Chan: b.expr(fn, recv.X),
  1679  				Pos:  recv.OpPos,
  1680  			}
  1681  			if debugInfo {
  1682  				st.DebugNode = recv
  1683  			}
  1684  
  1685  		case *ast.ExprStmt: // <-ch
  1686  			recv := unparen(comm.X).(*ast.UnaryExpr)
  1687  			st = &SelectState{
  1688  				Dir:  types.RecvOnly,
  1689  				Chan: b.expr(fn, recv.X),
  1690  				Pos:  recv.OpPos,
  1691  			}
  1692  			if debugInfo {
  1693  				st.DebugNode = recv
  1694  			}
  1695  		}
  1696  		states = append(states, st)
  1697  	}
  1698  
  1699  	// We dispatch on the (fair) result of Select using a
  1700  	// sequential if-else chain, in effect:
  1701  	//
  1702  	// idx, recvOk, r0...r_n-1 := select(...)
  1703  	// if idx == 0 {  // receive on channel 0  (first receive => r0)
  1704  	//     x, ok := r0, recvOk
  1705  	//     ...state0...
  1706  	// } else if v == 1 {   // send on channel 1
  1707  	//     ...state1...
  1708  	// } else {
  1709  	//     ...default...
  1710  	// }
  1711  	sel := &Select{
  1712  		States:   states,
  1713  		Blocking: blocking,
  1714  	}
  1715  	sel.setPos(s.Select)
  1716  	var vars []*types.Var
  1717  	vars = append(vars, varIndex, varOk)
  1718  	for _, st := range states {
  1719  		if st.Dir == types.RecvOnly {
  1720  			chtyp := typeparams.CoreType(fn.typ(st.Chan.Type())).(*types.Chan)
  1721  			vars = append(vars, anonVar(chtyp.Elem()))
  1722  		}
  1723  	}
  1724  	sel.setType(types.NewTuple(vars...))
  1725  
  1726  	fn.emit(sel)
  1727  	idx := emitExtract(fn, sel, 0)
  1728  
  1729  	done := fn.newBasicBlock("select.done")
  1730  	if label != nil {
  1731  		label._break = done
  1732  	}
  1733  
  1734  	var defaultBody *[]ast.Stmt
  1735  	state := 0
  1736  	r := 2 // index in 'sel' tuple of value; increments if st.Dir==RECV
  1737  	for _, cc := range s.Body.List {
  1738  		clause := cc.(*ast.CommClause)
  1739  		if clause.Comm == nil {
  1740  			defaultBody = &clause.Body
  1741  			continue
  1742  		}
  1743  		body := fn.newBasicBlock("select.body")
  1744  		next := fn.newBasicBlock("select.next")
  1745  		emitIf(fn, emitCompare(fn, token.EQL, idx, intConst(int64(state)), token.NoPos), body, next)
  1746  		fn.currentBlock = body
  1747  		fn.targets = &targets{
  1748  			tail:   fn.targets,
  1749  			_break: done,
  1750  		}
  1751  		switch comm := clause.Comm.(type) {
  1752  		case *ast.ExprStmt: // <-ch
  1753  			if debugInfo {
  1754  				v := emitExtract(fn, sel, r)
  1755  				emitDebugRef(fn, states[state].DebugNode.(ast.Expr), v, false)
  1756  			}
  1757  			r++
  1758  
  1759  		case *ast.AssignStmt: // x := <-states[state].Chan
  1760  			if comm.Tok == token.DEFINE {
  1761  				fn.addLocalForIdent(comm.Lhs[0].(*ast.Ident))
  1762  			}
  1763  			x := b.addr(fn, comm.Lhs[0], false) // non-escaping
  1764  			v := emitExtract(fn, sel, r)
  1765  			if debugInfo {
  1766  				emitDebugRef(fn, states[state].DebugNode.(ast.Expr), v, false)
  1767  			}
  1768  			x.store(fn, v)
  1769  
  1770  			if len(comm.Lhs) == 2 { // x, ok := ...
  1771  				if comm.Tok == token.DEFINE {
  1772  					fn.addLocalForIdent(comm.Lhs[1].(*ast.Ident))
  1773  				}
  1774  				ok := b.addr(fn, comm.Lhs[1], false) // non-escaping
  1775  				ok.store(fn, emitExtract(fn, sel, 1))
  1776  			}
  1777  			r++
  1778  		}
  1779  		b.stmtList(fn, clause.Body)
  1780  		fn.targets = fn.targets.tail
  1781  		emitJump(fn, done)
  1782  		fn.currentBlock = next
  1783  		state++
  1784  	}
  1785  	if defaultBody != nil {
  1786  		fn.targets = &targets{
  1787  			tail:   fn.targets,
  1788  			_break: done,
  1789  		}
  1790  		b.stmtList(fn, *defaultBody)
  1791  		fn.targets = fn.targets.tail
  1792  	} else {
  1793  		// A blocking select must match some case.
  1794  		// (This should really be a runtime.errorString, not a string.)
  1795  		fn.emit(&Panic{
  1796  			X: emitConv(fn, stringConst("blocking select matched no case"), tEface),
  1797  		})
  1798  		fn.currentBlock = fn.newBasicBlock("unreachable")
  1799  	}
  1800  	emitJump(fn, done)
  1801  	fn.currentBlock = done
  1802  }
  1803  
  1804  // forStmt emits to fn code for the for statement s, optionally
  1805  // labelled by label.
  1806  func (b *builder) forStmt(fn *Function, s *ast.ForStmt, label *lblock) {
  1807  	//	...init...
  1808  	//      jump loop
  1809  	// loop:
  1810  	//      if cond goto body else done
  1811  	// body:
  1812  	//      ...body...
  1813  	//      jump post
  1814  	// post:				 (target of continue)
  1815  	//      ...post...
  1816  	//      jump loop
  1817  	// done:                                 (target of break)
  1818  	if s.Init != nil {
  1819  		b.stmt(fn, s.Init)
  1820  	}
  1821  	body := fn.newBasicBlock("for.body")
  1822  	done := fn.newBasicBlock("for.done") // target of 'break'
  1823  	loop := body                         // target of back-edge
  1824  	if s.Cond != nil {
  1825  		loop = fn.newBasicBlock("for.loop")
  1826  	}
  1827  	cont := loop // target of 'continue'
  1828  	if s.Post != nil {
  1829  		cont = fn.newBasicBlock("for.post")
  1830  	}
  1831  	if label != nil {
  1832  		label._break = done
  1833  		label._continue = cont
  1834  	}
  1835  	emitJump(fn, loop)
  1836  	fn.currentBlock = loop
  1837  	if loop != body {
  1838  		b.cond(fn, s.Cond, body, done)
  1839  		fn.currentBlock = body
  1840  	}
  1841  	fn.targets = &targets{
  1842  		tail:      fn.targets,
  1843  		_break:    done,
  1844  		_continue: cont,
  1845  	}
  1846  	b.stmt(fn, s.Body)
  1847  	fn.targets = fn.targets.tail
  1848  	emitJump(fn, cont)
  1849  
  1850  	if s.Post != nil {
  1851  		fn.currentBlock = cont
  1852  		b.stmt(fn, s.Post)
  1853  		emitJump(fn, loop) // back-edge
  1854  	}
  1855  	fn.currentBlock = done
  1856  }
  1857  
  1858  // rangeIndexed emits to fn the header for an integer-indexed loop
  1859  // over array, *array or slice value x.
  1860  // The v result is defined only if tv is non-nil.
  1861  // forPos is the position of the "for" token.
  1862  func (b *builder) rangeIndexed(fn *Function, x Value, tv types.Type, pos token.Pos) (k, v Value, loop, done *BasicBlock) {
  1863  	//
  1864  	//      length = len(x)
  1865  	//      index = -1
  1866  	// loop:                                   (target of continue)
  1867  	//      index++
  1868  	// 	if index < length goto body else done
  1869  	// body:
  1870  	//      k = index
  1871  	//      v = x[index]
  1872  	//      ...body...
  1873  	// 	jump loop
  1874  	// done:                                   (target of break)
  1875  
  1876  	// Determine number of iterations.
  1877  	var length Value
  1878  	if arr, ok := deref(x.Type()).Underlying().(*types.Array); ok {
  1879  		// For array or *array, the number of iterations is
  1880  		// known statically thanks to the type.  We avoid a
  1881  		// data dependence upon x, permitting later dead-code
  1882  		// elimination if x is pure, static unrolling, etc.
  1883  		// Ranging over a nil *array may have >0 iterations.
  1884  		// We still generate code for x, in case it has effects.
  1885  		//
  1886  		// TypeParams do not have constant length. Use underlying instead of core type.
  1887  		length = intConst(arr.Len())
  1888  	} else {
  1889  		// length = len(x).
  1890  		var c Call
  1891  		c.Call.Value = makeLen(x.Type())
  1892  		c.Call.Args = []Value{x}
  1893  		c.setType(tInt)
  1894  		length = fn.emit(&c)
  1895  	}
  1896  
  1897  	index := fn.addLocal(tInt, token.NoPos)
  1898  	emitStore(fn, index, intConst(-1), pos)
  1899  
  1900  	loop = fn.newBasicBlock("rangeindex.loop")
  1901  	emitJump(fn, loop)
  1902  	fn.currentBlock = loop
  1903  
  1904  	incr := &BinOp{
  1905  		Op: token.ADD,
  1906  		X:  emitLoad(fn, index),
  1907  		Y:  vOne,
  1908  	}
  1909  	incr.setType(tInt)
  1910  	emitStore(fn, index, fn.emit(incr), pos)
  1911  
  1912  	body := fn.newBasicBlock("rangeindex.body")
  1913  	done = fn.newBasicBlock("rangeindex.done")
  1914  	emitIf(fn, emitCompare(fn, token.LSS, incr, length, token.NoPos), body, done)
  1915  	fn.currentBlock = body
  1916  
  1917  	k = emitLoad(fn, index)
  1918  	if tv != nil {
  1919  		switch t := typeparams.CoreType(x.Type()).(type) {
  1920  		case *types.Array:
  1921  			instr := &Index{
  1922  				X:     x,
  1923  				Index: k,
  1924  			}
  1925  			instr.setType(t.Elem())
  1926  			instr.setPos(x.Pos())
  1927  			v = fn.emit(instr)
  1928  
  1929  		case *types.Pointer: // *array
  1930  			instr := &IndexAddr{
  1931  				X:     x,
  1932  				Index: k,
  1933  			}
  1934  			instr.setType(types.NewPointer(t.Elem().Underlying().(*types.Array).Elem()))
  1935  			instr.setPos(x.Pos())
  1936  			v = emitLoad(fn, fn.emit(instr))
  1937  
  1938  		case *types.Slice:
  1939  			instr := &IndexAddr{
  1940  				X:     x,
  1941  				Index: k,
  1942  			}
  1943  			instr.setType(types.NewPointer(t.Elem()))
  1944  			instr.setPos(x.Pos())
  1945  			v = emitLoad(fn, fn.emit(instr))
  1946  
  1947  		default:
  1948  			panic("rangeIndexed x:" + t.String())
  1949  		}
  1950  	}
  1951  	return
  1952  }
  1953  
  1954  // rangeIter emits to fn the header for a loop using
  1955  // Range/Next/Extract to iterate over map or string value x.
  1956  // tk and tv are the types of the key/value results k and v, or nil
  1957  // if the respective component is not wanted.
  1958  func (b *builder) rangeIter(fn *Function, x Value, tk, tv types.Type, pos token.Pos) (k, v Value, loop, done *BasicBlock) {
  1959  	//
  1960  	//	it = range x
  1961  	// loop:                                   (target of continue)
  1962  	//	okv = next it                      (ok, key, value)
  1963  	//  	ok = extract okv #0
  1964  	// 	if ok goto body else done
  1965  	// body:
  1966  	// 	k = extract okv #1
  1967  	// 	v = extract okv #2
  1968  	//      ...body...
  1969  	// 	jump loop
  1970  	// done:                                   (target of break)
  1971  	//
  1972  
  1973  	if tk == nil {
  1974  		tk = tInvalid
  1975  	}
  1976  	if tv == nil {
  1977  		tv = tInvalid
  1978  	}
  1979  
  1980  	rng := &Range{X: x}
  1981  	rng.setPos(pos)
  1982  	rng.setType(tRangeIter)
  1983  	it := fn.emit(rng)
  1984  
  1985  	loop = fn.newBasicBlock("rangeiter.loop")
  1986  	emitJump(fn, loop)
  1987  	fn.currentBlock = loop
  1988  
  1989  	okv := &Next{
  1990  		Iter:     it,
  1991  		IsString: isBasic(typeparams.CoreType(x.Type())),
  1992  	}
  1993  	okv.setType(types.NewTuple(
  1994  		varOk,
  1995  		newVar("k", tk),
  1996  		newVar("v", tv),
  1997  	))
  1998  	fn.emit(okv)
  1999  
  2000  	body := fn.newBasicBlock("rangeiter.body")
  2001  	done = fn.newBasicBlock("rangeiter.done")
  2002  	emitIf(fn, emitExtract(fn, okv, 0), body, done)
  2003  	fn.currentBlock = body
  2004  
  2005  	if tk != tInvalid {
  2006  		k = emitExtract(fn, okv, 1)
  2007  	}
  2008  	if tv != tInvalid {
  2009  		v = emitExtract(fn, okv, 2)
  2010  	}
  2011  	return
  2012  }
  2013  
  2014  // rangeChan emits to fn the header for a loop that receives from
  2015  // channel x until it fails.
  2016  // tk is the channel's element type, or nil if the k result is
  2017  // not wanted
  2018  // pos is the position of the '=' or ':=' token.
  2019  func (b *builder) rangeChan(fn *Function, x Value, tk types.Type, pos token.Pos) (k Value, loop, done *BasicBlock) {
  2020  	//
  2021  	// loop:                                   (target of continue)
  2022  	//      ko = <-x                           (key, ok)
  2023  	//      ok = extract ko #1
  2024  	//      if ok goto body else done
  2025  	// body:
  2026  	//      k = extract ko #0
  2027  	//      ...
  2028  	//      goto loop
  2029  	// done:                                   (target of break)
  2030  
  2031  	loop = fn.newBasicBlock("rangechan.loop")
  2032  	emitJump(fn, loop)
  2033  	fn.currentBlock = loop
  2034  	recv := &UnOp{
  2035  		Op:      token.ARROW,
  2036  		X:       x,
  2037  		CommaOk: true,
  2038  	}
  2039  	recv.setPos(pos)
  2040  	recv.setType(types.NewTuple(
  2041  		newVar("k", typeparams.CoreType(x.Type()).(*types.Chan).Elem()),
  2042  		varOk,
  2043  	))
  2044  	ko := fn.emit(recv)
  2045  	body := fn.newBasicBlock("rangechan.body")
  2046  	done = fn.newBasicBlock("rangechan.done")
  2047  	emitIf(fn, emitExtract(fn, ko, 1), body, done)
  2048  	fn.currentBlock = body
  2049  	if tk != nil {
  2050  		k = emitExtract(fn, ko, 0)
  2051  	}
  2052  	return
  2053  }
  2054  
  2055  // rangeStmt emits to fn code for the range statement s, optionally
  2056  // labelled by label.
  2057  func (b *builder) rangeStmt(fn *Function, s *ast.RangeStmt, label *lblock) {
  2058  	var tk, tv types.Type
  2059  	if s.Key != nil && !isBlankIdent(s.Key) {
  2060  		tk = fn.typeOf(s.Key)
  2061  	}
  2062  	if s.Value != nil && !isBlankIdent(s.Value) {
  2063  		tv = fn.typeOf(s.Value)
  2064  	}
  2065  
  2066  	// If iteration variables are defined (:=), this
  2067  	// occurs once outside the loop.
  2068  	//
  2069  	// Unlike a short variable declaration, a RangeStmt
  2070  	// using := never redeclares an existing variable; it
  2071  	// always creates a new one.
  2072  	if s.Tok == token.DEFINE {
  2073  		if tk != nil {
  2074  			fn.addLocalForIdent(s.Key.(*ast.Ident))
  2075  		}
  2076  		if tv != nil {
  2077  			fn.addLocalForIdent(s.Value.(*ast.Ident))
  2078  		}
  2079  	}
  2080  
  2081  	x := b.expr(fn, s.X)
  2082  
  2083  	var k, v Value
  2084  	var loop, done *BasicBlock
  2085  	switch rt := typeparams.CoreType(x.Type()).(type) {
  2086  	case *types.Slice, *types.Array, *types.Pointer: // *array
  2087  		k, v, loop, done = b.rangeIndexed(fn, x, tv, s.For)
  2088  
  2089  	case *types.Chan:
  2090  		k, loop, done = b.rangeChan(fn, x, tk, s.For)
  2091  
  2092  	case *types.Map, *types.Basic: // string
  2093  		k, v, loop, done = b.rangeIter(fn, x, tk, tv, s.For)
  2094  
  2095  	default:
  2096  		panic("Cannot range over: " + rt.String())
  2097  	}
  2098  
  2099  	// Evaluate both LHS expressions before we update either.
  2100  	var kl, vl lvalue
  2101  	if tk != nil {
  2102  		kl = b.addr(fn, s.Key, false) // non-escaping
  2103  	}
  2104  	if tv != nil {
  2105  		vl = b.addr(fn, s.Value, false) // non-escaping
  2106  	}
  2107  	if tk != nil {
  2108  		kl.store(fn, k)
  2109  	}
  2110  	if tv != nil {
  2111  		vl.store(fn, v)
  2112  	}
  2113  
  2114  	if label != nil {
  2115  		label._break = done
  2116  		label._continue = loop
  2117  	}
  2118  
  2119  	fn.targets = &targets{
  2120  		tail:      fn.targets,
  2121  		_break:    done,
  2122  		_continue: loop,
  2123  	}
  2124  	b.stmt(fn, s.Body)
  2125  	fn.targets = fn.targets.tail
  2126  	emitJump(fn, loop) // back-edge
  2127  	fn.currentBlock = done
  2128  }
  2129  
  2130  // stmt lowers statement s to SSA form, emitting code to fn.
  2131  func (b *builder) stmt(fn *Function, _s ast.Stmt) {
  2132  	// The label of the current statement.  If non-nil, its _goto
  2133  	// target is always set; its _break and _continue are set only
  2134  	// within the body of switch/typeswitch/select/for/range.
  2135  	// It is effectively an additional default-nil parameter of stmt().
  2136  	var label *lblock
  2137  start:
  2138  	switch s := _s.(type) {
  2139  	case *ast.EmptyStmt:
  2140  		// ignore.  (Usually removed by gofmt.)
  2141  
  2142  	case *ast.DeclStmt: // Con, Var or Typ
  2143  		d := s.Decl.(*ast.GenDecl)
  2144  		if d.Tok == token.VAR {
  2145  			for _, spec := range d.Specs {
  2146  				if vs, ok := spec.(*ast.ValueSpec); ok {
  2147  					b.localValueSpec(fn, vs)
  2148  				}
  2149  			}
  2150  		}
  2151  
  2152  	case *ast.LabeledStmt:
  2153  		label = fn.labelledBlock(s.Label)
  2154  		emitJump(fn, label._goto)
  2155  		fn.currentBlock = label._goto
  2156  		_s = s.Stmt
  2157  		goto start // effectively: tailcall stmt(fn, s.Stmt, label)
  2158  
  2159  	case *ast.ExprStmt:
  2160  		b.expr(fn, s.X)
  2161  
  2162  	case *ast.SendStmt:
  2163  		chtyp := typeparams.CoreType(fn.typeOf(s.Chan)).(*types.Chan)
  2164  		fn.emit(&Send{
  2165  			Chan: b.expr(fn, s.Chan),
  2166  			X:    emitConv(fn, b.expr(fn, s.Value), chtyp.Elem()),
  2167  			pos:  s.Arrow,
  2168  		})
  2169  
  2170  	case *ast.IncDecStmt:
  2171  		op := token.ADD
  2172  		if s.Tok == token.DEC {
  2173  			op = token.SUB
  2174  		}
  2175  		loc := b.addr(fn, s.X, false)
  2176  		b.assignOp(fn, loc, NewConst(constant.MakeInt64(1), loc.typ()), op, s.Pos())
  2177  
  2178  	case *ast.AssignStmt:
  2179  		switch s.Tok {
  2180  		case token.ASSIGN, token.DEFINE:
  2181  			b.assignStmt(fn, s.Lhs, s.Rhs, s.Tok == token.DEFINE)
  2182  
  2183  		default: // +=, etc.
  2184  			op := s.Tok + token.ADD - token.ADD_ASSIGN
  2185  			b.assignOp(fn, b.addr(fn, s.Lhs[0], false), b.expr(fn, s.Rhs[0]), op, s.Pos())
  2186  		}
  2187  
  2188  	case *ast.GoStmt:
  2189  		// The "intrinsics" new/make/len/cap are forbidden here.
  2190  		// panic is treated like an ordinary function call.
  2191  		v := Go{pos: s.Go}
  2192  		b.setCall(fn, s.Call, &v.Call)
  2193  		fn.emit(&v)
  2194  
  2195  	case *ast.DeferStmt:
  2196  		// The "intrinsics" new/make/len/cap are forbidden here.
  2197  		// panic is treated like an ordinary function call.
  2198  		v := Defer{pos: s.Defer}
  2199  		b.setCall(fn, s.Call, &v.Call)
  2200  		fn.emit(&v)
  2201  
  2202  		// A deferred call can cause recovery from panic,
  2203  		// and control resumes at the Recover block.
  2204  		createRecoverBlock(fn)
  2205  
  2206  	case *ast.ReturnStmt:
  2207  		var results []Value
  2208  		if len(s.Results) == 1 && fn.Signature.Results().Len() > 1 {
  2209  			// Return of one expression in a multi-valued function.
  2210  			tuple := b.exprN(fn, s.Results[0])
  2211  			ttuple := tuple.Type().(*types.Tuple)
  2212  			for i, n := 0, ttuple.Len(); i < n; i++ {
  2213  				results = append(results,
  2214  					emitConv(fn, emitExtract(fn, tuple, i),
  2215  						fn.Signature.Results().At(i).Type()))
  2216  			}
  2217  		} else {
  2218  			// 1:1 return, or no-arg return in non-void function.
  2219  			for i, r := range s.Results {
  2220  				v := emitConv(fn, b.expr(fn, r), fn.Signature.Results().At(i).Type())
  2221  				results = append(results, v)
  2222  			}
  2223  		}
  2224  		if fn.namedResults != nil {
  2225  			// Function has named result parameters (NRPs).
  2226  			// Perform parallel assignment of return operands to NRPs.
  2227  			for i, r := range results {
  2228  				emitStore(fn, fn.namedResults[i], r, s.Return)
  2229  			}
  2230  		}
  2231  		// Run function calls deferred in this
  2232  		// function when explicitly returning from it.
  2233  		fn.emit(new(RunDefers))
  2234  		if fn.namedResults != nil {
  2235  			// Reload NRPs to form the result tuple.
  2236  			results = results[:0]
  2237  			for _, r := range fn.namedResults {
  2238  				results = append(results, emitLoad(fn, r))
  2239  			}
  2240  		}
  2241  		fn.emit(&Return{Results: results, pos: s.Return})
  2242  		fn.currentBlock = fn.newBasicBlock("unreachable")
  2243  
  2244  	case *ast.BranchStmt:
  2245  		var block *BasicBlock
  2246  		switch s.Tok {
  2247  		case token.BREAK:
  2248  			if s.Label != nil {
  2249  				block = fn.labelledBlock(s.Label)._break
  2250  			} else {
  2251  				for t := fn.targets; t != nil && block == nil; t = t.tail {
  2252  					block = t._break
  2253  				}
  2254  			}
  2255  
  2256  		case token.CONTINUE:
  2257  			if s.Label != nil {
  2258  				block = fn.labelledBlock(s.Label)._continue
  2259  			} else {
  2260  				for t := fn.targets; t != nil && block == nil; t = t.tail {
  2261  					block = t._continue
  2262  				}
  2263  			}
  2264  
  2265  		case token.FALLTHROUGH:
  2266  			for t := fn.targets; t != nil && block == nil; t = t.tail {
  2267  				block = t._fallthrough
  2268  			}
  2269  
  2270  		case token.GOTO:
  2271  			block = fn.labelledBlock(s.Label)._goto
  2272  		}
  2273  		emitJump(fn, block)
  2274  		fn.currentBlock = fn.newBasicBlock("unreachable")
  2275  
  2276  	case *ast.BlockStmt:
  2277  		b.stmtList(fn, s.List)
  2278  
  2279  	case *ast.IfStmt:
  2280  		if s.Init != nil {
  2281  			b.stmt(fn, s.Init)
  2282  		}
  2283  		then := fn.newBasicBlock("if.then")
  2284  		done := fn.newBasicBlock("if.done")
  2285  		els := done
  2286  		if s.Else != nil {
  2287  			els = fn.newBasicBlock("if.else")
  2288  		}
  2289  		b.cond(fn, s.Cond, then, els)
  2290  		fn.currentBlock = then
  2291  		b.stmt(fn, s.Body)
  2292  		emitJump(fn, done)
  2293  
  2294  		if s.Else != nil {
  2295  			fn.currentBlock = els
  2296  			b.stmt(fn, s.Else)
  2297  			emitJump(fn, done)
  2298  		}
  2299  
  2300  		fn.currentBlock = done
  2301  
  2302  	case *ast.SwitchStmt:
  2303  		b.switchStmt(fn, s, label)
  2304  
  2305  	case *ast.TypeSwitchStmt:
  2306  		b.typeSwitchStmt(fn, s, label)
  2307  
  2308  	case *ast.SelectStmt:
  2309  		b.selectStmt(fn, s, label)
  2310  
  2311  	case *ast.ForStmt:
  2312  		b.forStmt(fn, s, label)
  2313  
  2314  	case *ast.RangeStmt:
  2315  		b.rangeStmt(fn, s, label)
  2316  
  2317  	default:
  2318  		panic(fmt.Sprintf("unexpected statement kind: %T", s))
  2319  	}
  2320  }
  2321  
  2322  // buildFunction builds SSA code for the body of function fn.  Idempotent.
  2323  func (b *builder) buildFunction(fn *Function) {
  2324  	if !fn.built {
  2325  		assert(fn.parent == nil, "anonymous functions should not be built by buildFunction()")
  2326  		b.buildFunctionBody(fn)
  2327  		fn.done()
  2328  	}
  2329  }
  2330  
  2331  // buildFunctionBody builds SSA code for the body of function fn.
  2332  //
  2333  // fn is not done building until fn.done() is called.
  2334  func (b *builder) buildFunctionBody(fn *Function) {
  2335  	// TODO(taking): see if this check is reachable.
  2336  	if fn.Blocks != nil {
  2337  		return // building already started
  2338  	}
  2339  
  2340  	var recvField *ast.FieldList
  2341  	var body *ast.BlockStmt
  2342  	var functype *ast.FuncType
  2343  	switch n := fn.syntax.(type) {
  2344  	case nil:
  2345  		if fn.Params != nil {
  2346  			return // not a Go source function.  (Synthetic, or from object file.)
  2347  		}
  2348  	case *ast.FuncDecl:
  2349  		functype = n.Type
  2350  		recvField = n.Recv
  2351  		body = n.Body
  2352  	case *ast.FuncLit:
  2353  		functype = n.Type
  2354  		body = n.Body
  2355  	default:
  2356  		panic(n)
  2357  	}
  2358  
  2359  	if body == nil {
  2360  		// External function.
  2361  		if fn.Params == nil {
  2362  			// This condition ensures we add a non-empty
  2363  			// params list once only, but we may attempt
  2364  			// the degenerate empty case repeatedly.
  2365  			// TODO(adonovan): opt: don't do that.
  2366  
  2367  			// We set Function.Params even though there is no body
  2368  			// code to reference them.  This simplifies clients.
  2369  			if recv := fn.Signature.Recv(); recv != nil {
  2370  				fn.addParamObj(recv)
  2371  			}
  2372  			params := fn.Signature.Params()
  2373  			for i, n := 0, params.Len(); i < n; i++ {
  2374  				fn.addParamObj(params.At(i))
  2375  			}
  2376  		}
  2377  		return
  2378  	}
  2379  
  2380  	// Build instantiation wrapper around generic body?
  2381  	if fn.topLevelOrigin != nil && fn.subst == nil {
  2382  		buildInstantiationWrapper(fn)
  2383  		return
  2384  	}
  2385  
  2386  	if fn.Prog.mode&LogSource != 0 {
  2387  		defer logStack("build function %s @ %s", fn, fn.Prog.Fset.Position(fn.pos))()
  2388  	}
  2389  	fn.startBody()
  2390  	fn.createSyntacticParams(recvField, functype)
  2391  	b.stmt(fn, body)
  2392  	if cb := fn.currentBlock; cb != nil && (cb == fn.Blocks[0] || cb == fn.Recover || cb.Preds != nil) {
  2393  		// Control fell off the end of the function's body block.
  2394  		//
  2395  		// Block optimizations eliminate the current block, if
  2396  		// unreachable.  It is a builder invariant that
  2397  		// if this no-arg return is ill-typed for
  2398  		// fn.Signature.Results, this block must be
  2399  		// unreachable.  The sanity checker checks this.
  2400  		fn.emit(new(RunDefers))
  2401  		fn.emit(new(Return))
  2402  	}
  2403  	fn.finishBody()
  2404  }
  2405  
  2406  // buildCreated does the BUILD phase for each function created by builder that is not yet BUILT.
  2407  // Functions are built using buildFunction.
  2408  //
  2409  // May add types that require runtime type information to builder.
  2410  func (b *builder) buildCreated() {
  2411  	for ; b.finished < b.created.Len(); b.finished++ {
  2412  		fn := b.created.At(b.finished)
  2413  		b.buildFunction(fn)
  2414  	}
  2415  }
  2416  
  2417  // Adds any needed runtime type information for the created functions.
  2418  //
  2419  // May add newly CREATEd functions that may need to be built or runtime type information.
  2420  //
  2421  // EXCLUSIVE_LOCKS_ACQUIRED(prog.methodsMu)
  2422  func (b *builder) needsRuntimeTypes() {
  2423  	if b.created.Len() == 0 {
  2424  		return
  2425  	}
  2426  	prog := b.created.At(0).Prog
  2427  
  2428  	var rtypes []types.Type
  2429  	for ; b.rtypes < b.finished; b.rtypes++ {
  2430  		fn := b.created.At(b.rtypes)
  2431  		rtypes = append(rtypes, mayNeedRuntimeTypes(fn)...)
  2432  	}
  2433  
  2434  	// Calling prog.needMethodsOf(T) on a basic type T is a no-op.
  2435  	// Filter out the basic types to reduce acquiring prog.methodsMu.
  2436  	rtypes = nonbasicTypes(rtypes)
  2437  
  2438  	for _, T := range rtypes {
  2439  		prog.needMethodsOf(T, b.created)
  2440  	}
  2441  }
  2442  
  2443  func (b *builder) done() bool {
  2444  	return b.rtypes >= b.created.Len()
  2445  }
  2446  
  2447  // Build calls Package.Build for each package in prog.
  2448  // Building occurs in parallel unless the BuildSerially mode flag was set.
  2449  //
  2450  // Build is intended for whole-program analysis; a typical compiler
  2451  // need only build a single package.
  2452  //
  2453  // Build is idempotent and thread-safe.
  2454  func (prog *Program) Build() {
  2455  	var wg sync.WaitGroup
  2456  	for _, p := range prog.packages {
  2457  		if prog.mode&BuildSerially != 0 {
  2458  			p.Build()
  2459  		} else {
  2460  			wg.Add(1)
  2461  			go func(p *Package) {
  2462  				p.Build()
  2463  				wg.Done()
  2464  			}(p)
  2465  		}
  2466  	}
  2467  	wg.Wait()
  2468  }
  2469  
  2470  // Build builds SSA code for all functions and vars in package p.
  2471  //
  2472  // Precondition: CreatePackage must have been called for all of p's
  2473  // direct imports (and hence its direct imports must have been
  2474  // error-free).
  2475  //
  2476  // Build is idempotent and thread-safe.
  2477  func (p *Package) Build() { p.buildOnce.Do(p.build) }
  2478  
  2479  func (p *Package) build() {
  2480  	if p.info == nil {
  2481  		return // synthetic package, e.g. "testmain"
  2482  	}
  2483  
  2484  	// Ensure we have runtime type info for all exported members.
  2485  	// Additionally filter for just concrete types that can be runtime types.
  2486  	//
  2487  	// TODO(adonovan): ideally belongs in memberFromObject, but
  2488  	// that would require package creation in topological order.
  2489  	for name, mem := range p.Members {
  2490  		isGround := func(m Member) bool {
  2491  			switch m := m.(type) {
  2492  			case *Type:
  2493  				named, _ := m.Type().(*types.Named)
  2494  				return named == nil || typeparams.ForNamed(named) == nil
  2495  			case *Function:
  2496  				return m.typeparams.Len() == 0
  2497  			}
  2498  			return true // *NamedConst, *Global
  2499  		}
  2500  		if ast.IsExported(name) && isGround(mem) {
  2501  			p.Prog.needMethodsOf(mem.Type(), &p.created)
  2502  		}
  2503  	}
  2504  	if p.Prog.mode&LogSource != 0 {
  2505  		defer logStack("build %s", p)()
  2506  	}
  2507  
  2508  	b := builder{created: &p.created}
  2509  	init := p.init
  2510  	init.startBody()
  2511  
  2512  	var done *BasicBlock
  2513  
  2514  	if p.Prog.mode&BareInits == 0 {
  2515  		// Make init() skip if package is already initialized.
  2516  		initguard := p.Var("init$guard")
  2517  		doinit := init.newBasicBlock("init.start")
  2518  		done = init.newBasicBlock("init.done")
  2519  		emitIf(init, emitLoad(init, initguard), done, doinit)
  2520  		init.currentBlock = doinit
  2521  		emitStore(init, initguard, vTrue, token.NoPos)
  2522  
  2523  		// Call the init() function of each package we import.
  2524  		for _, pkg := range p.Pkg.Imports() {
  2525  			prereq := p.Prog.packages[pkg]
  2526  			if prereq == nil {
  2527  				panic(fmt.Sprintf("Package(%q).Build(): unsatisfied import: Program.CreatePackage(%q) was not called", p.Pkg.Path(), pkg.Path()))
  2528  			}
  2529  			var v Call
  2530  			v.Call.Value = prereq.init
  2531  			v.Call.pos = init.pos
  2532  			v.setType(types.NewTuple())
  2533  			init.emit(&v)
  2534  		}
  2535  	}
  2536  
  2537  	// Initialize package-level vars in correct order.
  2538  	if len(p.info.InitOrder) > 0 && len(p.files) == 0 {
  2539  		panic("no source files provided for package. cannot initialize globals")
  2540  	}
  2541  	for _, varinit := range p.info.InitOrder {
  2542  		if init.Prog.mode&LogSource != 0 {
  2543  			fmt.Fprintf(os.Stderr, "build global initializer %v @ %s\n",
  2544  				varinit.Lhs, p.Prog.Fset.Position(varinit.Rhs.Pos()))
  2545  		}
  2546  		if len(varinit.Lhs) == 1 {
  2547  			// 1:1 initialization: var x, y = a(), b()
  2548  			var lval lvalue
  2549  			if v := varinit.Lhs[0]; v.Name() != "_" {
  2550  				lval = &address{addr: p.objects[v].(*Global), pos: v.Pos()}
  2551  			} else {
  2552  				lval = blank{}
  2553  			}
  2554  			b.assign(init, lval, varinit.Rhs, true, nil)
  2555  		} else {
  2556  			// n:1 initialization: var x, y :=  f()
  2557  			tuple := b.exprN(init, varinit.Rhs)
  2558  			for i, v := range varinit.Lhs {
  2559  				if v.Name() == "_" {
  2560  					continue
  2561  				}
  2562  				emitStore(init, p.objects[v].(*Global), emitExtract(init, tuple, i), v.Pos())
  2563  			}
  2564  		}
  2565  	}
  2566  
  2567  	// Call all of the declared init() functions in source order.
  2568  	for _, file := range p.files {
  2569  		for _, decl := range file.Decls {
  2570  			if decl, ok := decl.(*ast.FuncDecl); ok {
  2571  				id := decl.Name
  2572  				if !isBlankIdent(id) && id.Name == "init" && decl.Recv == nil {
  2573  					fn := p.objects[p.info.Defs[id]].(*Function)
  2574  					var v Call
  2575  					v.Call.Value = fn
  2576  					v.setType(types.NewTuple())
  2577  					p.init.emit(&v)
  2578  				}
  2579  			}
  2580  		}
  2581  	}
  2582  
  2583  	// Finish up init().
  2584  	if p.Prog.mode&BareInits == 0 {
  2585  		emitJump(init, done)
  2586  		init.currentBlock = done
  2587  	}
  2588  	init.emit(new(Return))
  2589  	init.finishBody()
  2590  	init.done()
  2591  
  2592  	// Build all CREATEd functions and add runtime types.
  2593  	// These Functions include package-level functions, init functions, methods, and synthetic (including unreachable/blank ones).
  2594  	// Builds any functions CREATEd while building this package.
  2595  	//
  2596  	// Initially the created functions for the package are:
  2597  	//   [init, decl0, ... , declN]
  2598  	// Where decl0, ..., declN are declared functions in source order, but it's not significant.
  2599  	//
  2600  	// As these are built, more functions (function literals, wrappers, etc.) can be CREATEd.
  2601  	// Iterate until we reach a fixed point.
  2602  	//
  2603  	// Wait for init() to be BUILT as that cannot be built by buildFunction().
  2604  	//
  2605  	for !b.done() {
  2606  		b.buildCreated()      // build any CREATEd and not BUILT function. May add runtime types.
  2607  		b.needsRuntimeTypes() // Add all of the runtime type information. May CREATE Functions.
  2608  	}
  2609  
  2610  	p.info = nil    // We no longer need ASTs or go/types deductions.
  2611  	p.created = nil // We no longer need created functions.
  2612  
  2613  	if p.Prog.mode&SanityCheckFunctions != 0 {
  2614  		sanityCheckPackage(p)
  2615  	}
  2616  }
  2617  

View as plain text