gopls/go/ssa/builder.go

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