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 defines the builder, which builds SSA-form IR for function bodies.
8 //
9 // SSA construction has two phases, "create" and "build". First, one
10 // or more packages are created in any order by a sequence of calls to
11 // CreatePackage, either from syntax or from mere type information.
12 // Each created package has a complete set of Members (const, var,
13 // type, func) that can be accessed through methods like
14 // Program.FuncValue.
15 //
16 // It is not necessary to call CreatePackage for all dependencies of
17 // each syntax package, only for its direct imports. (In future
18 // perhaps even this restriction may be lifted.)
19 //
20 // Second, packages created from syntax are built, by one or more
21 // calls to Package.Build, which may be concurrent; or by a call to
22 // Program.Build, which builds all packages in parallel. Building
23 // traverses the type-annotated syntax tree of each function body and
24 // creates SSA-form IR, a control-flow graph of instructions,
25 // populating fields such as Function.Body, .Params, and others.
26 //
27 // Building may create additional methods, including:
28 // - wrapper methods (e.g. for embedding, or implicit &recv)
29 // - bound method closures (e.g. for use(recv.f))
30 // - thunks (e.g. for use(I.f) or use(T.f))
31 // - generic instances (e.g. to produce f[int] from f[any]).
32 // As these methods are created, they are added to the build queue,
33 // and then processed in turn, until a fixed point is reached,
34 // Since these methods might belong to packages that were not
35 // created (by a call to CreatePackage), their Pkg field is unset.
36 //
37 // Instances of generic functions may be either instantiated (f[int]
38 // is a copy of f[T] with substitutions) or wrapped (f[int] delegates
39 // to f[T]), depending on the availability of generic syntax and the
40 // InstantiateGenerics mode flag.
41 //
42 // Each package has an initializer function named "init" that calls
43 // the initializer functions of each direct import, computes and
44 // assigns the initial value of each global variable, and calls each
45 // source-level function named "init". (These generate SSA functions
46 // named "init#1", "init#2", etc.)
47 //
48 // Runtime types
49 //
50 // Each MakeInterface operation is a conversion from a non-interface
51 // type to an interface type. The semantics of this operation requires
52 // a runtime type descriptor, which is the type portion of an
53 // interface, and the value abstracted by reflect.Type.
54 //
55 // The program accumulates all non-parameterized types that are
56 // encountered as MakeInterface operands, along with all types that
57 // may be derived from them using reflection. This set is available as
58 // Program.RuntimeTypes, and the methods of these types may be
59 // reachable via interface calls or reflection even if they are never
60 // referenced from the SSA IR. (In practice, algorithms such as RTA
61 // that compute reachability from package main perform their own
62 // tracking of runtime types at a finer grain, so this feature is not
63 // very useful.)
64 //
65 // Function literals
66 //
67 // Anonymous functions must be built as soon as they are encountered,
68 // as it may affect locals of the enclosing function, but they are not
69 // marked 'built' until the end of the outermost enclosing function.
70 // (Among other things, this causes them to be logged in top-down order.)
71 //
72 // The Function.build fields determines the algorithm for building the
73 // function body. It is cleared to mark that building is complete.
74 75 import (
76 "fmt"
77 "go/ast"
78 "go/constant"
79 "go/token"
80 "go/types"
81 "os"
82 "runtime"
83 "sync"
84 85 "slices"
86 87 "golang.org/x/tools/internal/typeparams"
88 "golang.org/x/tools/internal/versions"
89 )
90 91 type opaqueType struct{ name string }
92 93 func (t *opaqueType) String() string { return t.name }
94 func (t *opaqueType) Underlying() types.Type { return t }
95 96 var (
97 varOk = newVar("ok", tBool)
98 varIndex = newVar("index", tInt)
99 100 // Type constants.
101 tBool = types.Typ[types.Bool]
102 tByte = types.Typ[types.Byte]
103 tInt = types.Typ[types.Int]
104 tInvalid = types.Typ[types.Invalid]
105 tString = types.Typ[types.String]
106 tUntypedNil = types.Typ[types.UntypedNil]
107 108 tRangeIter = &opaqueType{"iter"} // the type of all "range" iterators
109 tDeferStack = types.NewPointer(&opaqueType{"deferStack"}) // the type of a "deferStack" from ssa:deferstack()
110 tEface = types.NewInterfaceType(nil, nil).Complete()
111 112 // SSA Value constants.
113 vZero = intConst(0)
114 vOne = intConst(1)
115 vTrue = NewConst(constant.MakeBool(true), tBool)
116 vFalse = NewConst(constant.MakeBool(false), tBool)
117 vNoReturn = NewConst(constant.MakeString("noreturn"), tString)
118 119 jReady = intConst(0) // range-over-func jump is READY
120 jBusy = intConst(-1) // range-over-func jump is BUSY
121 jDone = intConst(-2) // range-over-func jump is DONE
122 123 // The ssa:deferstack intrinsic returns the current function's defer stack.
124 vDeferStack = &Builtin{
125 name: "ssa:deferstack",
126 sig: types.NewSignatureType(nil, nil, nil, nil, types.NewTuple(anonVar(tDeferStack)), false),
127 }
128 )
129 130 // builder holds state associated with the package currently being built.
131 // Its methods contain all the logic for AST-to-SSA conversion.
132 //
133 // All Functions belong to the same Program.
134 //
135 // builders are not thread-safe.
136 type builder struct {
137 fns []*Function // Functions that have finished their CREATE phases.
138 139 finished int // finished is the length of the prefix of fns containing built functions.
140 141 // The task of building shared functions within the builder.
142 // Shared functions are ones the builder may either create or lookup.
143 // These may be built by other builders in parallel.
144 // The task is done when the builder has finished iterating, and it
145 // waits for all shared functions to finish building.
146 // nil implies there are no hared functions to wait on.
147 buildshared *task
148 }
149 150 // shared is done when the builder has built all of the
151 // enqueued functions to a fixed-point.
152 func (b *builder) shared() *task {
153 if b.buildshared == nil { // lazily-initialize
154 b.buildshared = &task{done: make(chan unit)}
155 }
156 return b.buildshared
157 }
158 159 // enqueue fn to be built by the builder.
160 func (b *builder) enqueue(fn *Function) {
161 b.fns = append(b.fns, fn)
162 }
163 164 // waitForSharedFunction indicates that the builder should wait until
165 // the potentially shared function fn has finished building.
166 //
167 // This should include any functions that may be built by other
168 // builders.
169 func (b *builder) waitForSharedFunction(fn *Function) {
170 if fn.buildshared != nil { // maybe need to wait?
171 s := b.shared()
172 s.addEdge(fn.buildshared)
173 }
174 }
175 176 // cond emits to fn code to evaluate boolean condition e and jump
177 // to t or f depending on its value, performing various simplifications.
178 //
179 // Postcondition: fn.currentBlock is nil.
180 func (b *builder) cond(fn *Function, e ast.Expr, t, f *BasicBlock) {
181 switch e := e.(type) {
182 case *ast.ParenExpr:
183 b.cond(fn, e.X, t, f)
184 return
185 186 case *ast.BinaryExpr:
187 switch e.Op {
188 case token.LAND:
189 ltrue := fn.newBasicBlock("cond.true")
190 b.cond(fn, e.X, ltrue, f)
191 fn.currentBlock = ltrue
192 b.cond(fn, e.Y, t, f)
193 return
194 195 case token.LOR:
196 lfalse := fn.newBasicBlock("cond.false")
197 b.cond(fn, e.X, t, lfalse)
198 fn.currentBlock = lfalse
199 b.cond(fn, e.Y, t, f)
200 return
201 }
202 203 case *ast.UnaryExpr:
204 if e.Op == token.NOT {
205 b.cond(fn, e.X, f, t)
206 return
207 }
208 }
209 210 // A traditional compiler would simplify "if false" (etc) here
211 // but we do not, for better fidelity to the source code.
212 //
213 // The value of a constant condition may be platform-specific,
214 // and may cause blocks that are reachable in some configuration
215 // to be hidden from subsequent analyses such as bug-finding tools.
216 emitIf(fn, b.expr(fn, e), t, f)
217 }
218 219 // logicalBinop emits code to fn to evaluate e, a &&- or
220 // ||-expression whose reified boolean value is wanted.
221 // The value is returned.
222 func (b *builder) logicalBinop(fn *Function, e *ast.BinaryExpr) Value {
223 rhs := fn.newBasicBlock("binop.rhs")
224 done := fn.newBasicBlock("binop.done")
225 226 // T(e) = T(e.X) = T(e.Y) after untyped constants have been
227 // eliminated.
228 // TODO(adonovan): not true; MyBool==MyBool yields UntypedBool.
229 t := fn.typeOf(e)
230 231 var short Value // value of the short-circuit path
232 switch e.Op {
233 case token.LAND:
234 b.cond(fn, e.X, rhs, done)
235 short = NewConst(constant.MakeBool(false), t)
236 237 case token.LOR:
238 b.cond(fn, e.X, done, rhs)
239 short = NewConst(constant.MakeBool(true), t)
240 }
241 242 // Is rhs unreachable?
243 if rhs.Preds == nil {
244 // Simplify false&&y to false, true||y to true.
245 fn.currentBlock = done
246 return short
247 }
248 249 // Is done unreachable?
250 if done.Preds == nil {
251 // Simplify true&&y (or false||y) to y.
252 fn.currentBlock = rhs
253 return b.expr(fn, e.Y)
254 }
255 256 // All edges from e.X to done carry the short-circuit value.
257 var edges []Value
258 for range done.Preds {
259 edges = append(edges, short)
260 }
261 262 // The edge from e.Y to done carries the value of e.Y.
263 fn.currentBlock = rhs
264 edges = append(edges, b.expr(fn, e.Y))
265 emitJump(fn, done)
266 fn.currentBlock = done
267 268 phi := &Phi{Edges: edges, Comment: e.Op.String()}
269 phi.pos = e.OpPos
270 phi.typ = t
271 return done.emit(phi)
272 }
273 274 // exprN lowers a multi-result expression e to SSA form, emitting code
275 // to fn and returning a single Value whose type is a *types.Tuple.
276 // The caller must access the components via Extract.
277 //
278 // Multi-result expressions include CallExprs in a multi-value
279 // assignment or return statement, and "value,ok" uses of
280 // TypeAssertExpr, IndexExpr (when X is a map), and UnaryExpr (when Op
281 // is token.ARROW).
282 func (b *builder) exprN(fn *Function, e ast.Expr) Value {
283 typ := fn.typeOf(e).(*types.Tuple)
284 switch e := e.(type) {
285 case *ast.ParenExpr:
286 return b.exprN(fn, e.X)
287 288 case *ast.CallExpr:
289 // Currently, no built-in function nor type conversion
290 // has multiple results, so we can avoid some of the
291 // cases for single-valued CallExpr.
292 var c Call
293 b.setCall(fn, e, &c.Call)
294 c.typ = typ
295 return emitCall(fn, &c)
296 297 case *ast.IndexExpr:
298 mapt := typeparams.CoreType(fn.typeOf(e.X)).(*types.Map) // ,ok must be a map.
299 lookup := &Lookup{
300 X: b.expr(fn, e.X),
301 Index: emitConv(fn, b.expr(fn, e.Index), mapt.Key()),
302 CommaOk: true,
303 }
304 lookup.setType(typ)
305 lookup.setPos(e.Lbrack)
306 return fn.emit(lookup)
307 308 case *ast.TypeAssertExpr:
309 return emitTypeTest(fn, b.expr(fn, e.X), typ.At(0).Type(), e.Lparen)
310 311 case *ast.UnaryExpr: // must be receive <-
312 unop := &UnOp{
313 Op: token.ARROW,
314 X: b.expr(fn, e.X),
315 CommaOk: true,
316 }
317 unop.setType(typ)
318 unop.setPos(e.OpPos)
319 return fn.emit(unop)
320 }
321 panic(fmt.Sprintf("exprN(%T) in %s", e, fn))
322 }
323 324 // builtin emits to fn SSA instructions to implement a call to the
325 // built-in function obj with the specified arguments
326 // and return type. It returns the value defined by the result.
327 //
328 // The result is nil if no special handling was required; in this case
329 // the caller should treat this like an ordinary library function
330 // call.
331 func (b *builder) builtin(fn *Function, obj *types.Builtin, args []ast.Expr, typ types.Type, pos token.Pos) Value {
332 typ = fn.typ(typ)
333 switch obj.Name() {
334 case "make":
335 switch ct := typeparams.CoreType(typ).(type) {
336 case *types.Slice:
337 n := b.expr(fn, args[1])
338 m := n
339 if len(args) == 3 {
340 m = b.expr(fn, args[2])
341 }
342 if m, ok := m.(*Const); ok {
343 // treat make([]T, n, m) as new([m]T)[:n]
344 cap := m.Int64()
345 at := types.NewArray(ct.Elem(), cap)
346 v := &Slice{
347 X: emitNew(fn, at, pos, "makeslice"),
348 High: n,
349 }
350 v.setPos(pos)
351 v.setType(typ)
352 return fn.emit(v)
353 }
354 v := &MakeSlice{
355 Len: n,
356 Cap: m,
357 }
358 v.setPos(pos)
359 v.setType(typ)
360 return fn.emit(v)
361 362 case *types.Map:
363 var res Value
364 if len(args) == 2 {
365 res = b.expr(fn, args[1])
366 }
367 v := &MakeMap{Reserve: res}
368 v.setPos(pos)
369 v.setType(typ)
370 return fn.emit(v)
371 372 case *types.Chan:
373 var sz Value = vZero
374 if len(args) == 2 {
375 sz = b.expr(fn, args[1])
376 }
377 v := &MakeChan{Size: sz}
378 v.setPos(pos)
379 v.setType(typ)
380 return fn.emit(v)
381 }
382 383 case "new":
384 alloc := emitNew(fn, typeparams.MustDeref(typ), pos, "new")
385 if !fn.info.Types[args[0]].IsType() {
386 // new(expr), requires go1.26
387 v := b.expr(fn, args[0])
388 emitStore(fn, alloc, v, pos)
389 }
390 return alloc
391 392 case "len", "cap":
393 // Special case: len or cap of an array or *array is
394 // based on the type, not the value which may be nil.
395 // We must still evaluate the value, though. (If it
396 // was side-effect free, the whole call would have
397 // been constant-folded.)
398 t := typeparams.Deref(fn.typeOf(args[0]))
399 if at, ok := typeparams.CoreType(t).(*types.Array); ok {
400 b.expr(fn, args[0]) // for effects only
401 return intConst(at.Len())
402 }
403 // Otherwise treat as normal.
404 405 case "panic":
406 fn.emit(&Panic{
407 X: emitConv(fn, b.expr(fn, args[0]), tEface),
408 pos: pos,
409 })
410 fn.currentBlock = fn.newBasicBlock("unreachable")
411 return vTrue // any non-nil Value will do
412 }
413 return nil // treat all others as a regular function call
414 }
415 416 // addr lowers a single-result addressable expression e to SSA form,
417 // emitting code to fn and returning the location (an lvalue) defined
418 // by the expression.
419 //
420 // If escaping is true, addr marks the base variable of the
421 // addressable expression e as being a potentially escaping pointer
422 // value. For example, in this code:
423 //
424 // a := A{
425 // b: [1]B{B{c: 1}}
426 // }
427 // return &a.b[0].c
428 //
429 // the application of & causes a.b[0].c to have its address taken,
430 // which means that ultimately the local variable a must be
431 // heap-allocated. This is a simple but very conservative escape
432 // analysis.
433 //
434 // Operations forming potentially escaping pointers include:
435 // - &x, including when implicit in method call or composite literals.
436 // - a[:] iff a is an array (not *array)
437 // - references to variables in lexically enclosing functions.
438 func (b *builder) addr(fn *Function, e ast.Expr, escaping bool) lvalue {
439 switch e := e.(type) {
440 case *ast.Ident:
441 if isBlankIdent(e) {
442 return blank{}
443 }
444 obj := fn.objectOf(e).(*types.Var)
445 var v Value
446 if g := fn.Prog.packageLevelMember(obj); g != nil {
447 v = g.(*Global) // var (address)
448 } else {
449 v = fn.lookup(obj, escaping)
450 }
451 return &address{addr: v, pos: e.Pos(), expr: e}
452 453 case *ast.CompositeLit:
454 typ := typeparams.Deref(fn.typeOf(e))
455 var v *Alloc
456 if escaping {
457 v = emitNew(fn, typ, e.Lbrace, "complit")
458 } else {
459 v = emitLocal(fn, typ, e.Lbrace, "complit")
460 }
461 var sb storebuf
462 b.compLit(fn, v, e, true, &sb)
463 sb.emit(fn)
464 return &address{addr: v, pos: e.Lbrace, expr: e}
465 466 case *ast.ParenExpr:
467 return b.addr(fn, e.X, escaping)
468 469 case *ast.SelectorExpr:
470 sel := fn.selection(e)
471 if sel == nil {
472 // qualified identifier
473 return b.addr(fn, e.Sel, escaping)
474 }
475 if sel.kind != types.FieldVal {
476 panic(sel)
477 }
478 wantAddr := true
479 v := b.receiver(fn, e.X, wantAddr, escaping, sel)
480 index := sel.index[len(sel.index)-1]
481 fld := fieldOf(typeparams.MustDeref(v.Type()), index) // v is an addr.
482 483 // Due to the two phases of resolving AssignStmt, a panic from x.f = p()
484 // when x is nil is required to come after the side-effects of
485 // evaluating x and p().
486 emit := func(fn *Function) Value {
487 return emitFieldSelection(fn, v, index, true, e.Sel)
488 }
489 return &lazyAddress{addr: emit, t: fld.Type(), pos: e.Sel.Pos(), expr: e.Sel}
490 491 case *ast.IndexExpr:
492 xt := fn.typeOf(e.X)
493 elem, mode := indexType(xt)
494 var x Value
495 var et types.Type
496 switch mode {
497 case ixArrVar: // array, array|slice, array|*array, or array|*array|slice.
498 x = b.addr(fn, e.X, escaping).address(fn)
499 et = types.NewPointer(elem)
500 case ixVar: // *array, slice, *array|slice
501 x = b.expr(fn, e.X)
502 et = types.NewPointer(elem)
503 case ixMap:
504 mt := typeparams.CoreType(xt).(*types.Map)
505 return &element{
506 m: b.expr(fn, e.X),
507 k: emitConv(fn, b.expr(fn, e.Index), mt.Key()),
508 t: mt.Elem(),
509 pos: e.Lbrack,
510 }
511 default:
512 panic("unexpected container type in IndexExpr: " + xt.String())
513 }
514 index := b.expr(fn, e.Index)
515 if isUntyped(index.Type()) {
516 index = emitConv(fn, index, tInt)
517 }
518 // Due to the two phases of resolving AssignStmt, a panic from x[i] = p()
519 // when x is nil or i is out-of-bounds is required to come after the
520 // side-effects of evaluating x, i and p().
521 emit := func(fn *Function) Value {
522 v := &IndexAddr{
523 X: x,
524 Index: index,
525 }
526 v.setPos(e.Lbrack)
527 v.setType(et)
528 return fn.emit(v)
529 }
530 return &lazyAddress{addr: emit, t: typeparams.MustDeref(et), pos: e.Lbrack, expr: e}
531 532 case *ast.StarExpr:
533 return &address{addr: b.expr(fn, e.X), pos: e.Star, expr: e}
534 }
535 536 panic(fmt.Sprintf("unexpected address expression: %T", e))
537 }
538 539 type store struct {
540 lhs lvalue
541 rhs Value
542 }
543 544 type storebuf struct{ stores []store }
545 546 func (sb *storebuf) store(lhs lvalue, rhs Value) {
547 sb.stores = append(sb.stores, store{lhs, rhs})
548 }
549 550 func (sb *storebuf) emit(fn *Function) {
551 for _, s := range sb.stores {
552 s.lhs.store(fn, s.rhs)
553 }
554 }
555 556 // assign emits to fn code to initialize the lvalue loc with the value
557 // of expression e. If isZero is true, assign assumes that loc holds
558 // the zero value for its type.
559 //
560 // This is equivalent to loc.store(fn, b.expr(fn, e)), but may generate
561 // better code in some cases, e.g., for composite literals in an
562 // addressable location.
563 //
564 // If sb is not nil, assign generates code to evaluate expression e, but
565 // not to update loc. Instead, the necessary stores are appended to the
566 // storebuf sb so that they can be executed later. This allows correct
567 // in-place update of existing variables when the RHS is a composite
568 // literal that may reference parts of the LHS.
569 func (b *builder) assign(fn *Function, loc lvalue, e ast.Expr, isZero bool, sb *storebuf) {
570 // Can we initialize it in place?
571 if e, ok := ast.Unparen(e).(*ast.CompositeLit); ok {
572 // A CompositeLit never evaluates to a pointer,
573 // so if the type of the location is a pointer,
574 // an &-operation is implied.
575 if !is[blank](loc) && isPointerCore(loc.typ()) { // avoid calling blank.typ()
576 ptr := b.addr(fn, e, true).address(fn)
577 // copy address
578 if sb != nil {
579 sb.store(loc, ptr)
580 } else {
581 loc.store(fn, ptr)
582 }
583 return
584 }
585 586 if _, ok := loc.(*address); ok {
587 if isNonTypeParamInterface(loc.typ()) {
588 // e.g. var x interface{} = T{...}
589 // Can't in-place initialize an interface value.
590 // Fall back to copying.
591 } else {
592 // x = T{...} or x := T{...}
593 addr := loc.address(fn)
594 if sb != nil {
595 b.compLit(fn, addr, e, isZero, sb)
596 } else {
597 var sb storebuf
598 b.compLit(fn, addr, e, isZero, &sb)
599 sb.emit(fn)
600 }
601 602 // Subtle: emit debug ref for aggregate types only;
603 // slice and map are handled by store ops in compLit.
604 switch typeparams.CoreType(loc.typ()).(type) {
605 case *types.Struct, *types.Array:
606 emitDebugRef(fn, e, addr, true)
607 }
608 609 return
610 }
611 }
612 }
613 614 // simple case: just copy
615 rhs := b.expr(fn, e)
616 if sb != nil {
617 sb.store(loc, rhs)
618 } else {
619 loc.store(fn, rhs)
620 }
621 }
622 623 // expr lowers a single-result expression e to SSA form, emitting code
624 // to fn and returning the Value defined by the expression.
625 func (b *builder) expr(fn *Function, e ast.Expr) Value {
626 e = ast.Unparen(e)
627 628 tv := fn.info.Types[e]
629 630 // Is expression a constant?
631 if tv.Value != nil {
632 return NewConst(tv.Value, fn.typ(tv.Type))
633 }
634 635 var v Value
636 if tv.Addressable() {
637 // Prefer pointer arithmetic ({Index,Field}Addr) followed
638 // by Load over subelement extraction (e.g. Index, Field),
639 // to avoid large copies.
640 v = b.addr(fn, e, false).load(fn)
641 } else {
642 v = b.expr0(fn, e, tv)
643 }
644 if fn.debugInfo() {
645 emitDebugRef(fn, e, v, false)
646 }
647 return v
648 }
649 650 func (b *builder) expr0(fn *Function, e ast.Expr, tv types.TypeAndValue) Value {
651 switch e := e.(type) {
652 case *ast.BasicLit:
653 panic("non-constant BasicLit") // unreachable
654 655 case *ast.FuncLit:
656 /* function literal */
657 anon := &Function{
658 name: fmt.Sprintf("%s$%d", fn.Name(), 1+len(fn.AnonFuncs)),
659 Signature: fn.typeOf(e.Type).(*types.Signature),
660 pos: e.Type.Func,
661 parent: fn,
662 anonIdx: int32(len(fn.AnonFuncs)),
663 Pkg: fn.Pkg,
664 Prog: fn.Prog,
665 syntax: e,
666 info: fn.info,
667 goversion: fn.goversion,
668 build: (*builder).buildFromSyntax,
669 topLevelOrigin: nil, // use anonIdx to lookup an anon instance's origin.
670 typeparams: fn.typeparams, // share the parent's type parameters.
671 typeargs: fn.typeargs, // share the parent's type arguments.
672 subst: fn.subst, // share the parent's type substitutions.
673 uniq: fn.uniq, // start from parent's unique values
674 }
675 fn.AnonFuncs = append(fn.AnonFuncs, anon)
676 // Build anon immediately, as it may cause fn's locals to escape.
677 // (It is not marked 'built' until the end of the enclosing FuncDecl.)
678 anon.build(b, anon)
679 fn.uniq = anon.uniq // resume after anon's unique values
680 if anon.FreeVars == nil {
681 return anon
682 }
683 v := &MakeClosure{Fn: anon}
684 v.setType(fn.typ(tv.Type))
685 for _, fv := range anon.FreeVars {
686 v.Bindings = append(v.Bindings, fv.outer)
687 fv.outer = nil
688 }
689 return fn.emit(v)
690 691 case *ast.TypeAssertExpr: // single-result form only
692 return emitTypeAssert(fn, b.expr(fn, e.X), fn.typ(tv.Type), e.Lparen)
693 694 case *ast.CallExpr:
695 if fn.info.Types[e.Fun].IsType() {
696 // Explicit type conversion, e.g. string(x) or big.Int(x)
697 x := b.expr(fn, e.Args[0])
698 y := emitConv(fn, x, fn.typ(tv.Type))
699 if y != x {
700 switch y := y.(type) {
701 case *Convert:
702 y.pos = e.Lparen
703 case *ChangeType:
704 y.pos = e.Lparen
705 case *MakeInterface:
706 y.pos = e.Lparen
707 case *SliceToArrayPointer:
708 y.pos = e.Lparen
709 case *UnOp: // conversion from slice to array.
710 y.pos = e.Lparen
711 }
712 }
713 return y
714 }
715 // Call to "intrinsic" built-ins, e.g. new, make, panic.
716 if id, ok := ast.Unparen(e.Fun).(*ast.Ident); ok {
717 if obj, ok := fn.info.Uses[id].(*types.Builtin); ok {
718 if v := b.builtin(fn, obj, e.Args, fn.typ(tv.Type), e.Lparen); v != nil {
719 return v
720 }
721 }
722 }
723 // Regular function call.
724 var v Call
725 b.setCall(fn, e, &v.Call)
726 v.setType(fn.typ(tv.Type))
727 return emitCall(fn, &v)
728 729 case *ast.UnaryExpr:
730 switch e.Op {
731 case token.AND: // &X --- potentially escaping.
732 addr := b.addr(fn, e.X, true)
733 if _, ok := ast.Unparen(e.X).(*ast.StarExpr); ok {
734 // &*p must panic if p is nil (http://golang.org/s/go12nil).
735 // For simplicity, we'll just (suboptimally) rely
736 // on the side effects of a load.
737 // TODO(adonovan): emit dedicated nilcheck.
738 addr.load(fn)
739 }
740 return addr.address(fn)
741 case token.ADD:
742 return b.expr(fn, e.X)
743 case token.NOT, token.ARROW, token.SUB, token.XOR: // ! <- - ^
744 v := &UnOp{
745 Op: e.Op,
746 X: b.expr(fn, e.X),
747 }
748 v.setPos(e.OpPos)
749 v.setType(fn.typ(tv.Type))
750 return fn.emit(v)
751 default:
752 panic(e.Op)
753 }
754 755 case *ast.BinaryExpr:
756 switch e.Op {
757 case token.LAND, token.LOR:
758 return b.logicalBinop(fn, e)
759 case token.SHL, token.SHR:
760 fallthrough
761 case token.ADD, token.SUB, token.MUL, token.QUO, token.REM, token.AND, token.OR, token.XOR, token.AND_NOT:
762 return emitArith(fn, e.Op, b.expr(fn, e.X), b.expr(fn, e.Y), fn.typ(tv.Type), e.OpPos)
763 764 case token.EQL, token.NEQ, token.GTR, token.LSS, token.LEQ, token.GEQ:
765 cmp := emitCompare(fn, e.Op, b.expr(fn, e.X), b.expr(fn, e.Y), e.OpPos)
766 // The type of x==y may be UntypedBool.
767 return emitConv(fn, cmp, types.Default(fn.typ(tv.Type)))
768 default:
769 panic("illegal op in BinaryExpr: " + e.Op.String())
770 }
771 772 case *ast.SliceExpr:
773 var low, high, max Value
774 var x Value
775 xtyp := fn.typeOf(e.X)
776 switch typeparams.CoreType(xtyp).(type) {
777 case *types.Array:
778 // Potentially escaping.
779 x = b.addr(fn, e.X, true).address(fn)
780 case *types.Basic, *types.Slice, *types.Pointer: // *array
781 x = b.expr(fn, e.X)
782 default:
783 // core type exception?
784 if isBytestring(xtyp) {
785 x = b.expr(fn, e.X) // bytestring is handled as string and []byte.
786 } else {
787 panic("unexpected sequence type in SliceExpr")
788 }
789 }
790 if e.Low != nil {
791 low = b.expr(fn, e.Low)
792 }
793 if e.High != nil {
794 high = b.expr(fn, e.High)
795 }
796 if e.Slice3 {
797 max = b.expr(fn, e.Max)
798 }
799 v := &Slice{
800 X: x,
801 Low: low,
802 High: high,
803 Max: max,
804 }
805 v.setPos(e.Lbrack)
806 v.setType(fn.typ(tv.Type))
807 return fn.emit(v)
808 809 case *ast.Ident:
810 obj := fn.info.Uses[e]
811 // Universal built-in or nil?
812 switch obj := obj.(type) {
813 case *types.Builtin:
814 return &Builtin{name: obj.Name(), sig: fn.instanceType(e).(*types.Signature)}
815 case *types.Nil:
816 return zeroConst(fn.instanceType(e))
817 }
818 819 // Package-level func or var?
820 // (obj must belong to same package or a direct import.)
821 if v := fn.Prog.packageLevelMember(obj); v != nil {
822 if g, ok := v.(*Global); ok {
823 return emitLoad(fn, g) // var (address)
824 }
825 callee := v.(*Function) // (func)
826 if callee.typeparams.Len() > 0 {
827 targs := fn.subst.types(instanceArgs(fn.info, e))
828 callee = callee.instance(targs, b)
829 }
830 return callee
831 }
832 // Local var.
833 return emitLoad(fn, fn.lookup(obj.(*types.Var), false)) // var (address)
834 835 case *ast.SelectorExpr:
836 sel := fn.selection(e)
837 if sel == nil {
838 // builtin unsafe.{Add,Slice}
839 if obj, ok := fn.info.Uses[e.Sel].(*types.Builtin); ok {
840 return &Builtin{name: obj.Name(), sig: fn.typ(tv.Type).(*types.Signature)}
841 }
842 // qualified identifier
843 return b.expr(fn, e.Sel)
844 }
845 switch sel.kind {
846 case types.MethodExpr:
847 // (*T).f or T.f, the method f from the method-set of type T.
848 // The result is a "thunk".
849 thunk := createThunk(fn.Prog, sel)
850 b.enqueue(thunk)
851 return emitConv(fn, thunk, fn.typ(tv.Type))
852 853 case types.MethodVal:
854 // e.f where e is an expression and f is a method.
855 // The result is a "bound".
856 obj := sel.obj.(*types.Func)
857 rt := fn.typ(recvType(obj))
858 wantAddr := isPointer(rt)
859 escaping := true
860 v := b.receiver(fn, e.X, wantAddr, escaping, sel)
861 862 if types.IsInterface(rt) {
863 // If v may be an interface type I (after instantiating),
864 // we must emit a check that v is non-nil.
865 if recv, ok := types.Unalias(sel.recv).(*types.TypeParam); ok {
866 // Emit a nil check if any possible instantiation of the
867 // type parameter is an interface type.
868 if !typeSetIsEmpty(recv) {
869 // recv has a concrete term its typeset.
870 // So it cannot be instantiated as an interface.
871 //
872 // Example:
873 // func _[T interface{~int; Foo()}] () {
874 // var v T
875 // _ = v.Foo // <-- MethodVal
876 // }
877 } else {
878 // rt may be instantiated as an interface.
879 // Emit nil check: typeassert (any(v)).(any).
880 emitTypeAssert(fn, emitConv(fn, v, tEface), tEface, token.NoPos)
881 }
882 } else {
883 // non-type param interface
884 // Emit nil check: typeassert v.(I).
885 emitTypeAssert(fn, v, rt, e.Sel.Pos())
886 }
887 }
888 if targs := receiverTypeArgs(obj); len(targs) > 0 {
889 // obj is generic.
890 obj = fn.Prog.canon.instantiateMethod(obj, fn.subst.types(targs), fn.Prog.ctxt)
891 }
892 bound := createBound(fn.Prog, obj)
893 b.enqueue(bound)
894 895 c := &MakeClosure{
896 Fn: bound,
897 Bindings: []Value{v},
898 }
899 c.setPos(e.Sel.Pos())
900 c.setType(fn.typ(tv.Type))
901 return fn.emit(c)
902 903 case types.FieldVal:
904 indices := sel.index
905 last := len(indices) - 1
906 v := b.expr(fn, e.X)
907 v = emitImplicitSelections(fn, v, indices[:last], e.Pos())
908 v = emitFieldSelection(fn, v, indices[last], false, e.Sel)
909 return v
910 }
911 912 panic("unexpected expression-relative selector")
913 914 case *ast.IndexListExpr:
915 // f[X, Y] must be a generic function
916 if !instance(fn.info, e.X) {
917 panic("unexpected expression-could not match index list to instantiation")
918 }
919 return b.expr(fn, e.X) // Handle instantiation within the *Ident or *SelectorExpr cases.
920 921 case *ast.IndexExpr:
922 if instance(fn.info, e.X) {
923 return b.expr(fn, e.X) // Handle instantiation within the *Ident or *SelectorExpr cases.
924 }
925 // not a generic instantiation.
926 xt := fn.typeOf(e.X)
927 switch et, mode := indexType(xt); mode {
928 case ixVar:
929 // Addressable slice/array; use IndexAddr and Load.
930 return b.addr(fn, e, false).load(fn)
931 932 case ixArrVar, ixValue:
933 // An array in a register, a string or a combined type that contains
934 // either an [_]array (ixArrVar) or string (ixValue).
935 936 // Note: for ixArrVar and CoreType(xt)==nil can be IndexAddr and Load.
937 index := b.expr(fn, e.Index)
938 if isUntyped(index.Type()) {
939 index = emitConv(fn, index, tInt)
940 }
941 v := &Index{
942 X: b.expr(fn, e.X),
943 Index: index,
944 }
945 v.setPos(e.Lbrack)
946 v.setType(et)
947 return fn.emit(v)
948 949 case ixMap:
950 ct := typeparams.CoreType(xt).(*types.Map)
951 v := &Lookup{
952 X: b.expr(fn, e.X),
953 Index: emitConv(fn, b.expr(fn, e.Index), ct.Key()),
954 }
955 v.setPos(e.Lbrack)
956 v.setType(ct.Elem())
957 return fn.emit(v)
958 default:
959 panic("unexpected container type in IndexExpr: " + xt.String())
960 }
961 962 case *ast.CompositeLit, *ast.StarExpr:
963 // Addressable types (lvalues)
964 return b.addr(fn, e, false).load(fn)
965 }
966 967 panic(fmt.Sprintf("unexpected expr: %T", e))
968 }
969 970 // stmtList emits to fn code for all statements in list.
971 func (b *builder) stmtList(fn *Function, list []ast.Stmt) {
972 for _, s := range list {
973 b.stmt(fn, s)
974 }
975 }
976 977 // receiver emits to fn code for expression e in the "receiver"
978 // position of selection e.f (where f may be a field or a method) and
979 // returns the effective receiver after applying the implicit field
980 // selections of sel.
981 //
982 // wantAddr requests that the result is an address. If
983 // !sel.indirect, this may require that e be built in addr() mode; it
984 // must thus be addressable.
985 //
986 // escaping is defined as per builder.addr().
987 func (b *builder) receiver(fn *Function, e ast.Expr, wantAddr, escaping bool, sel *selection) Value {
988 var v Value
989 if wantAddr && !sel.indirect && !isPointerCore(fn.typeOf(e)) {
990 v = b.addr(fn, e, escaping).address(fn)
991 } else {
992 v = b.expr(fn, e)
993 }
994 995 last := len(sel.index) - 1
996 // The position of implicit selection is the position of the inducing receiver expression.
997 v = emitImplicitSelections(fn, v, sel.index[:last], e.Pos())
998 if types.IsInterface(v.Type()) {
999 // When v is an interface, sel.Kind()==MethodValue and v.f is invoked.
1000 // So v is not loaded, even if v has a pointer core type.
1001 } else if !wantAddr && isPointerCore(v.Type()) {
1002 v = emitLoad(fn, v)
1003 }
1004 return v
1005 }
1006 1007 // setCallFunc populates the function parts of a CallCommon structure
1008 // (Func, Method, Recv, Args[0]) based on the kind of invocation
1009 // occurring in e.
1010 func (b *builder) setCallFunc(fn *Function, e *ast.CallExpr, c *CallCommon) {
1011 c.pos = e.Lparen
1012 1013 // Is this a method call?
1014 if selector, ok := ast.Unparen(e.Fun).(*ast.SelectorExpr); ok {
1015 sel := fn.selection(selector)
1016 if sel != nil && sel.kind == types.MethodVal {
1017 obj := sel.obj.(*types.Func)
1018 recv := recvType(obj)
1019 1020 wantAddr := isPointer(recv)
1021 escaping := true
1022 v := b.receiver(fn, selector.X, wantAddr, escaping, sel)
1023 if types.IsInterface(recv) {
1024 // Invoke-mode call.
1025 c.Value = v // possibly type param
1026 c.Method = obj
1027 } else {
1028 // "Call"-mode call.
1029 c.Value = fn.Prog.objectMethod(obj, b)
1030 c.Args = append(c.Args, v)
1031 }
1032 return
1033 }
1034 1035 // sel.kind==MethodExpr indicates T.f() or (*T).f():
1036 // a statically dispatched call to the method f in the
1037 // method-set of T or *T. T may be an interface.
1038 //
1039 // e.Fun would evaluate to a concrete method, interface
1040 // wrapper function, or promotion wrapper.
1041 //
1042 // For now, we evaluate it in the usual way.
1043 //
1044 // TODO(adonovan): opt: inline expr() here, to make the
1045 // call static and to avoid generation of wrappers.
1046 // It's somewhat tricky as it may consume the first
1047 // actual parameter if the call is "invoke" mode.
1048 //
1049 // Examples:
1050 // type T struct{}; func (T) f() {} // "call" mode
1051 // type T interface { f() } // "invoke" mode
1052 //
1053 // type S struct{ T }
1054 //
1055 // var s S
1056 // S.f(s)
1057 // (*S).f(&s)
1058 //
1059 // Suggested approach:
1060 // - consume the first actual parameter expression
1061 // and build it with b.expr().
1062 // - apply implicit field selections.
1063 // - use MethodVal logic to populate fields of c.
1064 }
1065 1066 // Evaluate the function operand in the usual way.
1067 c.Value = b.expr(fn, e.Fun)
1068 }
1069 1070 // emitCallArgs emits to f code for the actual parameters of call e to
1071 // a (possibly built-in) function of effective type sig.
1072 // The argument values are appended to args, which is then returned.
1073 func (b *builder) emitCallArgs(fn *Function, sig *types.Signature, e *ast.CallExpr, args []Value) []Value {
1074 // f(x, y, z...): pass slice z straight through.
1075 if e.Ellipsis != 0 {
1076 for i, arg := range e.Args {
1077 v := emitConv(fn, b.expr(fn, arg), sig.Params().At(i).Type())
1078 args = append(args, v)
1079 }
1080 return args
1081 }
1082 1083 offset := len(args) // 1 if call has receiver, 0 otherwise
1084 1085 // Evaluate actual parameter expressions.
1086 //
1087 // If this is a chained call of the form f(g()) where g has
1088 // multiple return values (MRV), they are flattened out into
1089 // args; a suffix of them may end up in a varargs slice.
1090 for _, arg := range e.Args {
1091 v := b.expr(fn, arg)
1092 if ttuple, ok := v.Type().(*types.Tuple); ok { // MRV chain
1093 for i, n := 0, ttuple.Len(); i < n; i++ {
1094 args = append(args, emitExtract(fn, v, i))
1095 }
1096 } else {
1097 args = append(args, v)
1098 }
1099 }
1100 1101 // Actual->formal assignability conversions for normal parameters.
1102 np := sig.Params().Len() // number of normal parameters
1103 if sig.Variadic() {
1104 np--
1105 }
1106 for i := 0; i < np; i++ {
1107 args[offset+i] = emitConv(fn, args[offset+i], sig.Params().At(i).Type())
1108 }
1109 1110 // Actual->formal assignability conversions for variadic parameter,
1111 // and construction of slice.
1112 if sig.Variadic() {
1113 varargs := args[offset+np:]
1114 st := sig.Params().At(np).Type().(*types.Slice)
1115 vt := st.Elem()
1116 if len(varargs) == 0 {
1117 args = append(args, zeroConst(st))
1118 } else {
1119 // Replace a suffix of args with a slice containing it.
1120 at := types.NewArray(vt, int64(len(varargs)))
1121 a := emitNew(fn, at, token.NoPos, "varargs")
1122 a.setPos(e.Rparen)
1123 for i, arg := range varargs {
1124 iaddr := &IndexAddr{
1125 X: a,
1126 Index: intConst(int64(i)),
1127 }
1128 iaddr.setType(types.NewPointer(vt))
1129 fn.emit(iaddr)
1130 emitStore(fn, iaddr, arg, arg.Pos())
1131 }
1132 s := &Slice{X: a}
1133 s.setType(st)
1134 args[offset+np] = fn.emit(s)
1135 args = args[:offset+np+1]
1136 }
1137 }
1138 return args
1139 }
1140 1141 // setCall emits to fn code to evaluate all the parameters of a function
1142 // call e, and populates *c with those values.
1143 func (b *builder) setCall(fn *Function, e *ast.CallExpr, c *CallCommon) {
1144 // First deal with the f(...) part and optional receiver.
1145 b.setCallFunc(fn, e, c)
1146 1147 // Then append the other actual parameters.
1148 sig, _ := typeparams.CoreType(fn.typeOf(e.Fun)).(*types.Signature)
1149 if sig == nil {
1150 panic(fmt.Sprintf("no signature for call of %s", e.Fun))
1151 }
1152 c.Args = b.emitCallArgs(fn, sig, e, c.Args)
1153 }
1154 1155 // assignOp emits to fn code to perform loc <op>= val.
1156 func (b *builder) assignOp(fn *Function, loc lvalue, val Value, op token.Token, pos token.Pos) {
1157 loc.store(fn, emitArith(fn, op, loc.load(fn), val, loc.typ(), pos))
1158 }
1159 1160 // localValueSpec emits to fn code to define all of the vars in the
1161 // function-local ValueSpec, spec.
1162 func (b *builder) localValueSpec(fn *Function, spec *ast.ValueSpec) {
1163 switch {
1164 case len(spec.Values) == len(spec.Names):
1165 // e.g. var x, y = 0, 1
1166 // 1:1 assignment
1167 for i, id := range spec.Names {
1168 if !isBlankIdent(id) {
1169 emitLocalVar(fn, identVar(fn, id))
1170 }
1171 lval := b.addr(fn, id, false) // non-escaping
1172 b.assign(fn, lval, spec.Values[i], true, nil)
1173 }
1174 1175 case len(spec.Values) == 0:
1176 // e.g. var x, y int
1177 // Locals are implicitly zero-initialized.
1178 for _, id := range spec.Names {
1179 if !isBlankIdent(id) {
1180 lhs := emitLocalVar(fn, identVar(fn, id))
1181 if fn.debugInfo() {
1182 emitDebugRef(fn, id, lhs, true)
1183 }
1184 }
1185 }
1186 1187 default:
1188 // e.g. var x, y = pos()
1189 tuple := b.exprN(fn, spec.Values[0])
1190 for i, id := range spec.Names {
1191 if !isBlankIdent(id) {
1192 emitLocalVar(fn, identVar(fn, id))
1193 lhs := b.addr(fn, id, false) // non-escaping
1194 lhs.store(fn, emitExtract(fn, tuple, i))
1195 }
1196 }
1197 }
1198 }
1199 1200 // assignStmt emits code to fn for a parallel assignment of rhss to lhss.
1201 // isDef is true if this is a short variable declaration (:=).
1202 //
1203 // Note the similarity with localValueSpec.
1204 func (b *builder) assignStmt(fn *Function, lhss, rhss []ast.Expr, isDef bool) {
1205 // Side effects of all LHSs and RHSs must occur in left-to-right order.
1206 lvals := make([]lvalue, len(lhss))
1207 isZero := make([]bool, len(lhss))
1208 for i, lhs := range lhss {
1209 var lval lvalue = blank{}
1210 if !isBlankIdent(lhs) {
1211 if isDef {
1212 if obj, ok := fn.info.Defs[lhs.(*ast.Ident)].(*types.Var); ok {
1213 emitLocalVar(fn, obj)
1214 isZero[i] = true
1215 }
1216 }
1217 lval = b.addr(fn, lhs, false) // non-escaping
1218 }
1219 lvals[i] = lval
1220 }
1221 if len(lhss) == len(rhss) {
1222 // Simple assignment: x = f() (!isDef)
1223 // Parallel assignment: x, y = f(), g() (!isDef)
1224 // or short var decl: x, y := f(), g() (isDef)
1225 //
1226 // In all cases, the RHSs may refer to the LHSs,
1227 // so we need a storebuf.
1228 var sb storebuf
1229 for i := range rhss {
1230 b.assign(fn, lvals[i], rhss[i], isZero[i], &sb)
1231 }
1232 sb.emit(fn)
1233 } else {
1234 // e.g. x, y = pos()
1235 tuple := b.exprN(fn, rhss[0])
1236 emitDebugRef(fn, rhss[0], tuple, false)
1237 for i, lval := range lvals {
1238 lval.store(fn, emitExtract(fn, tuple, i))
1239 }
1240 }
1241 }
1242 1243 // arrayLen returns the length of the array whose composite literal elements are elts.
1244 func (b *builder) arrayLen(fn *Function, elts []ast.Expr) int64 {
1245 var max int64 = -1
1246 var i int64 = -1
1247 for _, e := range elts {
1248 if kv, ok := e.(*ast.KeyValueExpr); ok {
1249 i = b.expr(fn, kv.Key).(*Const).Int64()
1250 } else {
1251 i++
1252 }
1253 if i > max {
1254 max = i
1255 }
1256 }
1257 return max + 1
1258 }
1259 1260 // compLit emits to fn code to initialize a composite literal e at
1261 // address addr with type typ.
1262 //
1263 // Nested composite literals are recursively initialized in place
1264 // where possible. If isZero is true, compLit assumes that addr
1265 // holds the zero value for typ.
1266 //
1267 // Because the elements of a composite literal may refer to the
1268 // variables being updated, as in the second line below,
1269 //
1270 // x := T{a: 1}
1271 // x = T{a: x.a}
1272 //
1273 // all the reads must occur before all the writes. Thus all stores to
1274 // loc are emitted to the storebuf sb for later execution.
1275 //
1276 // A CompositeLit may have pointer type only in the recursive (nested)
1277 // case when the type name is implicit. e.g. in []*T{{}}, the inner
1278 // literal has type *T behaves like &T{}.
1279 // In that case, addr must hold a T, not a *T.
1280 func (b *builder) compLit(fn *Function, addr Value, e *ast.CompositeLit, isZero bool, sb *storebuf) {
1281 typ := typeparams.Deref(fn.typeOf(e)) // retain the named/alias/param type, if any
1282 switch t := typeparams.CoreType(typ).(type) {
1283 case *types.Struct:
1284 if !isZero && len(e.Elts) != t.NumFields() {
1285 // memclear
1286 zt := typeparams.MustDeref(addr.Type())
1287 sb.store(&address{addr, e.Lbrace, nil}, zeroConst(zt))
1288 isZero = true
1289 }
1290 for i, e := range e.Elts {
1291 fieldIndex := i
1292 pos := e.Pos()
1293 if kv, ok := e.(*ast.KeyValueExpr); ok {
1294 fname := kv.Key.(*ast.Ident).Name
1295 for i, n := 0, t.NumFields(); i < n; i++ {
1296 sf := t.Field(i)
1297 if sf.Name() == fname {
1298 fieldIndex = i
1299 pos = kv.Colon
1300 e = kv.Value
1301 break
1302 }
1303 }
1304 }
1305 sf := t.Field(fieldIndex)
1306 faddr := &FieldAddr{
1307 X: addr,
1308 Field: fieldIndex,
1309 }
1310 faddr.setPos(pos)
1311 faddr.setType(types.NewPointer(sf.Type()))
1312 fn.emit(faddr)
1313 b.assign(fn, &address{addr: faddr, pos: pos, expr: e}, e, isZero, sb)
1314 }
1315 1316 case *types.Array, *types.Slice:
1317 var at *types.Array
1318 var array Value
1319 switch t := t.(type) {
1320 case *types.Slice:
1321 at = types.NewArray(t.Elem(), b.arrayLen(fn, e.Elts))
1322 array = emitNew(fn, at, e.Lbrace, "slicelit")
1323 case *types.Array:
1324 at = t
1325 array = addr
1326 1327 if !isZero && int64(len(e.Elts)) != at.Len() {
1328 // memclear
1329 zt := typeparams.MustDeref(array.Type())
1330 sb.store(&address{array, e.Lbrace, nil}, zeroConst(zt))
1331 }
1332 }
1333 1334 var idx *Const
1335 for _, e := range e.Elts {
1336 pos := e.Pos()
1337 if kv, ok := e.(*ast.KeyValueExpr); ok {
1338 idx = b.expr(fn, kv.Key).(*Const)
1339 pos = kv.Colon
1340 e = kv.Value
1341 } else {
1342 var idxval int64
1343 if idx != nil {
1344 idxval = idx.Int64() + 1
1345 }
1346 idx = intConst(idxval)
1347 }
1348 iaddr := &IndexAddr{
1349 X: array,
1350 Index: idx,
1351 }
1352 iaddr.setType(types.NewPointer(at.Elem()))
1353 fn.emit(iaddr)
1354 if t != at { // slice
1355 // backing array is unaliased => storebuf not needed.
1356 b.assign(fn, &address{addr: iaddr, pos: pos, expr: e}, e, true, nil)
1357 } else {
1358 b.assign(fn, &address{addr: iaddr, pos: pos, expr: e}, e, true, sb)
1359 }
1360 }
1361 1362 if t != at { // slice
1363 s := &Slice{X: array}
1364 s.setPos(e.Lbrace)
1365 s.setType(typ)
1366 sb.store(&address{addr: addr, pos: e.Lbrace, expr: e}, fn.emit(s))
1367 }
1368 1369 case *types.Map:
1370 m := &MakeMap{Reserve: intConst(int64(len(e.Elts)))}
1371 m.setPos(e.Lbrace)
1372 m.setType(typ)
1373 fn.emit(m)
1374 for _, e := range e.Elts {
1375 e := e.(*ast.KeyValueExpr)
1376 1377 // If a key expression in a map literal is itself a
1378 // composite literal, the type may be omitted.
1379 // For example:
1380 // map[*struct{}]bool{{}: true}
1381 // An &-operation may be implied:
1382 // map[*struct{}]bool{&struct{}{}: true}
1383 wantAddr := false
1384 if _, ok := ast.Unparen(e.Key).(*ast.CompositeLit); ok {
1385 wantAddr = isPointerCore(t.Key())
1386 }
1387 1388 var key Value
1389 if wantAddr {
1390 // A CompositeLit never evaluates to a pointer,
1391 // so if the type of the location is a pointer,
1392 // an &-operation is implied.
1393 key = b.addr(fn, e.Key, true).address(fn)
1394 } else {
1395 key = b.expr(fn, e.Key)
1396 }
1397 1398 loc := element{
1399 m: m,
1400 k: emitConv(fn, key, t.Key()),
1401 t: t.Elem(),
1402 pos: e.Colon,
1403 }
1404 1405 // We call assign() only because it takes care
1406 // of any &-operation required in the recursive
1407 // case, e.g.,
1408 // map[int]*struct{}{0: {}} implies &struct{}{}.
1409 // In-place update is of course impossible,
1410 // and no storebuf is needed.
1411 b.assign(fn, &loc, e.Value, true, nil)
1412 }
1413 sb.store(&address{addr: addr, pos: e.Lbrace, expr: e}, m)
1414 1415 default:
1416 panic("unexpected CompositeLit type: " + typ.String())
1417 }
1418 }
1419 1420 // switchStmt emits to fn code for the switch statement s, optionally
1421 // labelled by label.
1422 func (b *builder) switchStmt(fn *Function, s *ast.SwitchStmt, label *lblock) {
1423 // We treat SwitchStmt like a sequential if-else chain.
1424 // Multiway dispatch can be recovered later by ssautil.Switches()
1425 // to those cases that are free of side effects.
1426 if s.Init != nil {
1427 b.stmt(fn, s.Init)
1428 }
1429 var tag Value = vTrue
1430 if s.Tag != nil {
1431 tag = b.expr(fn, s.Tag)
1432 }
1433 done := fn.newBasicBlock("switch.done")
1434 if label != nil {
1435 label._break = done
1436 }
1437 // We pull the default case (if present) down to the end.
1438 // But each fallthrough label must point to the next
1439 // body block in source order, so we preallocate a
1440 // body block (fallthru) for the next case.
1441 // Unfortunately this makes for a confusing block order.
1442 var dfltBody *[]ast.Stmt
1443 var dfltFallthrough *BasicBlock
1444 var fallthru, dfltBlock *BasicBlock
1445 ncases := len(s.Body.List)
1446 for i, clause := range s.Body.List {
1447 body := fallthru
1448 if body == nil {
1449 body = fn.newBasicBlock("switch.body") // first case only
1450 }
1451 1452 // Preallocate body block for the next case.
1453 fallthru = done
1454 if i+1 < ncases {
1455 fallthru = fn.newBasicBlock("switch.body")
1456 }
1457 1458 cc := clause.(*ast.CaseClause)
1459 if cc.List == nil {
1460 // Default case.
1461 dfltBody = &cc.Body
1462 dfltFallthrough = fallthru
1463 dfltBlock = body
1464 continue
1465 }
1466 1467 var nextCond *BasicBlock
1468 for _, cond := range cc.List {
1469 nextCond = fn.newBasicBlock("switch.next")
1470 // For boolean switches, emit short-circuit control flow,
1471 // just like an if/else-chain.
1472 if tag == vTrue && !isNonTypeParamInterface(fn.info.Types[cond].Type) {
1473 b.cond(fn, cond, body, nextCond)
1474 } else {
1475 c := emitCompare(fn, token.EQL, tag, b.expr(fn, cond), cond.Pos())
1476 emitIf(fn, c, body, nextCond)
1477 }
1478 fn.currentBlock = nextCond
1479 }
1480 fn.currentBlock = body
1481 fn.targets = &targets{
1482 tail: fn.targets,
1483 _break: done,
1484 _fallthrough: fallthru,
1485 }
1486 b.stmtList(fn, cc.Body)
1487 fn.targets = fn.targets.tail
1488 emitJump(fn, done)
1489 fn.currentBlock = nextCond
1490 }
1491 if dfltBlock != nil {
1492 emitJump(fn, dfltBlock)
1493 fn.currentBlock = dfltBlock
1494 fn.targets = &targets{
1495 tail: fn.targets,
1496 _break: done,
1497 _fallthrough: dfltFallthrough,
1498 }
1499 b.stmtList(fn, *dfltBody)
1500 fn.targets = fn.targets.tail
1501 }
1502 emitJump(fn, done)
1503 fn.currentBlock = done
1504 }
1505 1506 // typeSwitchStmt emits to fn code for the type switch statement s, optionally
1507 // labelled by label.
1508 func (b *builder) typeSwitchStmt(fn *Function, s *ast.TypeSwitchStmt, label *lblock) {
1509 // We treat TypeSwitchStmt like a sequential if-else chain.
1510 // Multiway dispatch can be recovered later by ssautil.Switches().
1511 1512 // Typeswitch lowering:
1513 //
1514 // var x X
1515 // switch y := x.(type) {
1516 // case T1, T2: S1 // >1 (y := x)
1517 // case nil: SN // nil (y := x)
1518 // default: SD // 0 types (y := x)
1519 // case T3: S3 // 1 type (y := x.(T3))
1520 // }
1521 //
1522 // ...s.Init...
1523 // x := eval x
1524 // .caseT1:
1525 // t1, ok1 := typeswitch,ok x <T1>
1526 // if ok1 then goto S1 else goto .caseT2
1527 // .caseT2:
1528 // t2, ok2 := typeswitch,ok x <T2>
1529 // if ok2 then goto S1 else goto .caseNil
1530 // .S1:
1531 // y := x
1532 // ...S1...
1533 // goto done
1534 // .caseNil:
1535 // if t2, ok2 := typeswitch,ok x <T2>
1536 // if x == nil then goto SN else goto .caseT3
1537 // .SN:
1538 // y := x
1539 // ...SN...
1540 // goto done
1541 // .caseT3:
1542 // t3, ok3 := typeswitch,ok x <T3>
1543 // if ok3 then goto S3 else goto default
1544 // .S3:
1545 // y := t3
1546 // ...S3...
1547 // goto done
1548 // .default:
1549 // y := x
1550 // ...SD...
1551 // goto done
1552 // .done:
1553 if s.Init != nil {
1554 b.stmt(fn, s.Init)
1555 }
1556 1557 var x Value
1558 switch ass := s.Assign.(type) {
1559 case *ast.ExprStmt: // x.(type)
1560 x = b.expr(fn, ast.Unparen(ass.X).(*ast.TypeAssertExpr).X)
1561 case *ast.AssignStmt: // y := x.(type)
1562 x = b.expr(fn, ast.Unparen(ass.Rhs[0]).(*ast.TypeAssertExpr).X)
1563 }
1564 1565 done := fn.newBasicBlock("typeswitch.done")
1566 if label != nil {
1567 label._break = done
1568 }
1569 var default_ *ast.CaseClause
1570 for _, clause := range s.Body.List {
1571 cc := clause.(*ast.CaseClause)
1572 if cc.List == nil {
1573 default_ = cc
1574 continue
1575 }
1576 body := fn.newBasicBlock("typeswitch.body")
1577 var next *BasicBlock
1578 var casetype types.Type
1579 var ti Value // ti, ok := typeassert,ok x <Ti>
1580 for _, cond := range cc.List {
1581 next = fn.newBasicBlock("typeswitch.next")
1582 casetype = fn.typeOf(cond)
1583 var condv Value
1584 if casetype == tUntypedNil {
1585 condv = emitCompare(fn, token.EQL, x, zeroConst(x.Type()), cond.Pos())
1586 ti = x
1587 } else {
1588 yok := emitTypeTest(fn, x, casetype, cc.Case)
1589 ti = emitExtract(fn, yok, 0)
1590 condv = emitExtract(fn, yok, 1)
1591 }
1592 emitIf(fn, condv, body, next)
1593 fn.currentBlock = next
1594 }
1595 if len(cc.List) != 1 {
1596 ti = x
1597 }
1598 fn.currentBlock = body
1599 b.typeCaseBody(fn, cc, ti, done)
1600 fn.currentBlock = next
1601 }
1602 if default_ != nil {
1603 b.typeCaseBody(fn, default_, x, done)
1604 } else {
1605 emitJump(fn, done)
1606 }
1607 fn.currentBlock = done
1608 }
1609 1610 func (b *builder) typeCaseBody(fn *Function, cc *ast.CaseClause, x Value, done *BasicBlock) {
1611 if obj, ok := fn.info.Implicits[cc].(*types.Var); ok {
1612 // In a switch y := x.(type), each case clause
1613 // implicitly declares a distinct object y.
1614 // In a single-type case, y has that type.
1615 // In multi-type cases, 'case nil' and default,
1616 // y has the same type as the interface operand.
1617 emitStore(fn, emitLocalVar(fn, obj), x, obj.Pos())
1618 }
1619 fn.targets = &targets{
1620 tail: fn.targets,
1621 _break: done,
1622 }
1623 b.stmtList(fn, cc.Body)
1624 fn.targets = fn.targets.tail
1625 emitJump(fn, done)
1626 }
1627 1628 // selectStmt emits to fn code for the select statement s, optionally
1629 // labelled by label.
1630 func (b *builder) selectStmt(fn *Function, s *ast.SelectStmt, label *lblock) {
1631 // A blocking select of a single case degenerates to a
1632 // simple send or receive.
1633 // TODO(adonovan): opt: is this optimization worth its weight?
1634 if len(s.Body.List) == 1 {
1635 clause := s.Body.List[0].(*ast.CommClause)
1636 if clause.Comm != nil {
1637 b.stmt(fn, clause.Comm)
1638 done := fn.newBasicBlock("select.done")
1639 if label != nil {
1640 label._break = done
1641 }
1642 fn.targets = &targets{
1643 tail: fn.targets,
1644 _break: done,
1645 }
1646 b.stmtList(fn, clause.Body)
1647 fn.targets = fn.targets.tail
1648 emitJump(fn, done)
1649 fn.currentBlock = done
1650 return
1651 }
1652 }
1653 1654 // First evaluate all channels in all cases, and find
1655 // the directions of each state.
1656 var states []*SelectState
1657 blocking := true
1658 debugInfo := fn.debugInfo()
1659 for _, clause := range s.Body.List {
1660 var st *SelectState
1661 switch comm := clause.(*ast.CommClause).Comm.(type) {
1662 case nil: // default case
1663 blocking = false
1664 continue
1665 1666 case *ast.SendStmt: // ch<- i
1667 ch := b.expr(fn, comm.Chan)
1668 chtyp := typeparams.CoreType(fn.typ(ch.Type())).(*types.Chan)
1669 st = &SelectState{
1670 Dir: types.SendOnly,
1671 Chan: ch,
1672 Send: emitConv(fn, b.expr(fn, comm.Value), chtyp.Elem()),
1673 Pos: comm.Arrow,
1674 }
1675 if debugInfo {
1676 st.DebugNode = comm
1677 }
1678 1679 case *ast.AssignStmt: // x := <-ch
1680 recv := ast.Unparen(comm.Rhs[0]).(*ast.UnaryExpr)
1681 st = &SelectState{
1682 Dir: types.RecvOnly,
1683 Chan: b.expr(fn, recv.X),
1684 Pos: recv.OpPos,
1685 }
1686 if debugInfo {
1687 st.DebugNode = recv
1688 }
1689 1690 case *ast.ExprStmt: // <-ch
1691 recv := ast.Unparen(comm.X).(*ast.UnaryExpr)
1692 st = &SelectState{
1693 Dir: types.RecvOnly,
1694 Chan: b.expr(fn, recv.X),
1695 Pos: recv.OpPos,
1696 }
1697 if debugInfo {
1698 st.DebugNode = recv
1699 }
1700 }
1701 states = append(states, st)
1702 }
1703 1704 // We dispatch on the (fair) result of Select using a
1705 // sequential if-else chain, in effect:
1706 //
1707 // idx, recvOk, r0...r_n-1 := select(...)
1708 // if idx == 0 { // receive on channel 0 (first receive => r0)
1709 // x, ok := r0, recvOk
1710 // ...state0...
1711 // } else if v == 1 { // send on channel 1
1712 // ...state1...
1713 // } else {
1714 // ...default...
1715 // }
1716 sel := &Select{
1717 States: states,
1718 Blocking: blocking,
1719 }
1720 sel.setPos(s.Select)
1721 var vars []*types.Var
1722 vars = append(vars, varIndex, varOk)
1723 for _, st := range states {
1724 if st.Dir == types.RecvOnly {
1725 chtyp := typeparams.CoreType(fn.typ(st.Chan.Type())).(*types.Chan)
1726 vars = append(vars, anonVar(chtyp.Elem()))
1727 }
1728 }
1729 sel.setType(types.NewTuple(vars...))
1730 1731 fn.emit(sel)
1732 idx := emitExtract(fn, sel, 0)
1733 1734 done := fn.newBasicBlock("select.done")
1735 if label != nil {
1736 label._break = done
1737 }
1738 1739 var defaultBody *[]ast.Stmt
1740 state := 0
1741 r := 2 // index in 'sel' tuple of value; increments if st.Dir==RECV
1742 for _, cc := range s.Body.List {
1743 clause := cc.(*ast.CommClause)
1744 if clause.Comm == nil {
1745 defaultBody = &clause.Body
1746 continue
1747 }
1748 body := fn.newBasicBlock("select.body")
1749 next := fn.newBasicBlock("select.next")
1750 emitIf(fn, emitCompare(fn, token.EQL, idx, intConst(int64(state)), token.NoPos), body, next)
1751 fn.currentBlock = body
1752 fn.targets = &targets{
1753 tail: fn.targets,
1754 _break: done,
1755 }
1756 switch comm := clause.Comm.(type) {
1757 case *ast.ExprStmt: // <-ch
1758 if debugInfo {
1759 v := emitExtract(fn, sel, r)
1760 emitDebugRef(fn, states[state].DebugNode.(ast.Expr), v, false)
1761 }
1762 r++
1763 1764 case *ast.AssignStmt: // x := <-states[state].Chan
1765 if comm.Tok == token.DEFINE {
1766 emitLocalVar(fn, identVar(fn, comm.Lhs[0].(*ast.Ident)))
1767 }
1768 x := b.addr(fn, comm.Lhs[0], false) // non-escaping
1769 v := emitExtract(fn, sel, r)
1770 if debugInfo {
1771 emitDebugRef(fn, states[state].DebugNode.(ast.Expr), v, false)
1772 }
1773 x.store(fn, v)
1774 1775 if len(comm.Lhs) == 2 { // x, ok := ...
1776 if comm.Tok == token.DEFINE {
1777 emitLocalVar(fn, identVar(fn, comm.Lhs[1].(*ast.Ident)))
1778 }
1779 ok := b.addr(fn, comm.Lhs[1], false) // non-escaping
1780 ok.store(fn, emitExtract(fn, sel, 1))
1781 }
1782 r++
1783 }
1784 b.stmtList(fn, clause.Body)
1785 fn.targets = fn.targets.tail
1786 emitJump(fn, done)
1787 fn.currentBlock = next
1788 state++
1789 }
1790 if defaultBody != nil {
1791 fn.targets = &targets{
1792 tail: fn.targets,
1793 _break: done,
1794 }
1795 b.stmtList(fn, *defaultBody)
1796 fn.targets = fn.targets.tail
1797 } else {
1798 // A blocking select must match some case.
1799 // (This should really be a runtime.errorString, not a string.)
1800 fn.emit(&Panic{
1801 X: emitConv(fn, stringConst("blocking select matched no case"), tEface),
1802 })
1803 fn.currentBlock = fn.newBasicBlock("unreachable")
1804 }
1805 emitJump(fn, done)
1806 fn.currentBlock = done
1807 }
1808 1809 // forStmt emits to fn code for the for statement s, optionally
1810 // labelled by label.
1811 func (b *builder) forStmt(fn *Function, s *ast.ForStmt, label *lblock) {
1812 // Use forStmtGo122 instead if it applies.
1813 if s.Init != nil {
1814 if assign, ok := s.Init.(*ast.AssignStmt); ok && assign.Tok == token.DEFINE {
1815 if versions.AtLeast(fn.goversion, versions.Go1_22) {
1816 b.forStmtGo122(fn, s, label)
1817 return
1818 }
1819 }
1820 }
1821 1822 // ...init...
1823 // jump loop
1824 // loop:
1825 // if cond goto body else done
1826 // body:
1827 // ...body...
1828 // jump post
1829 // post: (target of continue)
1830 // ...post...
1831 // jump loop
1832 // done: (target of break)
1833 if s.Init != nil {
1834 b.stmt(fn, s.Init)
1835 }
1836 1837 body := fn.newBasicBlock("for.body")
1838 done := fn.newBasicBlock("for.done") // target of 'break'
1839 loop := body // target of back-edge
1840 if s.Cond != nil {
1841 loop = fn.newBasicBlock("for.loop")
1842 }
1843 cont := loop // target of 'continue'
1844 if s.Post != nil {
1845 cont = fn.newBasicBlock("for.post")
1846 }
1847 if label != nil {
1848 label._break = done
1849 label._continue = cont
1850 }
1851 emitJump(fn, loop)
1852 fn.currentBlock = loop
1853 if loop != body {
1854 b.cond(fn, s.Cond, body, done)
1855 fn.currentBlock = body
1856 }
1857 fn.targets = &targets{
1858 tail: fn.targets,
1859 _break: done,
1860 _continue: cont,
1861 }
1862 b.stmt(fn, s.Body)
1863 fn.targets = fn.targets.tail
1864 emitJump(fn, cont)
1865 1866 if s.Post != nil {
1867 fn.currentBlock = cont
1868 b.stmt(fn, s.Post)
1869 emitJump(fn, loop) // back-edge
1870 }
1871 fn.currentBlock = done
1872 }
1873 1874 // forStmtGo122 emits to fn code for the for statement s, optionally
1875 // labelled by label. s must define its variables.
1876 //
1877 // This allocates once per loop iteration. This is only correct in
1878 // GoVersions >= go1.22.
1879 func (b *builder) forStmtGo122(fn *Function, s *ast.ForStmt, label *lblock) {
1880 // i_outer = alloc[T]
1881 // *i_outer = ...init... // under objects[i] = i_outer
1882 // jump loop
1883 // loop:
1884 // i = phi [head: i_outer, loop: i_next]
1885 // ...cond... // under objects[i] = i
1886 // if cond goto body else done
1887 // body:
1888 // ...body... // under objects[i] = i (same as loop)
1889 // jump post
1890 // post:
1891 // tmp = *i
1892 // i_next = alloc[T]
1893 // *i_next = tmp
1894 // ...post... // under objects[i] = i_next
1895 // goto loop
1896 // done:
1897 1898 init := s.Init.(*ast.AssignStmt)
1899 startingBlocks := len(fn.Blocks)
1900 1901 pre := fn.currentBlock // current block before starting
1902 loop := fn.newBasicBlock("for.loop") // target of back-edge
1903 body := fn.newBasicBlock("for.body")
1904 post := fn.newBasicBlock("for.post") // target of 'continue'
1905 done := fn.newBasicBlock("for.done") // target of 'break'
1906 1907 // For each of the n loop variables, we create five SSA values,
1908 // outer, phi, next, load, and store in pre, loop, and post.
1909 // There is no limit on n.
1910 type loopVar struct {
1911 obj *types.Var
1912 outer *Alloc
1913 phi *Phi
1914 load *UnOp
1915 next *Alloc
1916 store *Store
1917 }
1918 vars := make([]loopVar, len(init.Lhs))
1919 for i, lhs := range init.Lhs {
1920 v := identVar(fn, lhs.(*ast.Ident))
1921 typ := fn.typ(v.Type())
1922 1923 fn.currentBlock = pre
1924 outer := emitLocal(fn, typ, v.Pos(), v.Name())
1925 1926 fn.currentBlock = loop
1927 phi := &Phi{Comment: v.Name()}
1928 phi.pos = v.Pos()
1929 phi.typ = outer.Type()
1930 fn.emit(phi)
1931 1932 fn.currentBlock = post
1933 // If next is local, it reuses the address and zeroes the old value so
1934 // load before allocating next.
1935 load := emitLoad(fn, phi)
1936 next := emitLocal(fn, typ, v.Pos(), v.Name())
1937 store := emitStore(fn, next, load, token.NoPos)
1938 1939 phi.Edges = []Value{outer, next} // pre edge is emitted before post edge.
1940 1941 vars[i] = loopVar{v, outer, phi, load, next, store}
1942 }
1943 1944 // ...init... under fn.objects[v] = i_outer
1945 fn.currentBlock = pre
1946 for _, v := range vars {
1947 fn.vars[v.obj] = v.outer
1948 }
1949 const isDef = false // assign to already-allocated outers
1950 b.assignStmt(fn, init.Lhs, init.Rhs, isDef)
1951 if label != nil {
1952 label._break = done
1953 label._continue = post
1954 }
1955 emitJump(fn, loop)
1956 1957 // ...cond... under fn.objects[v] = i
1958 fn.currentBlock = loop
1959 for _, v := range vars {
1960 fn.vars[v.obj] = v.phi
1961 }
1962 if s.Cond != nil {
1963 b.cond(fn, s.Cond, body, done)
1964 } else {
1965 emitJump(fn, body)
1966 }
1967 1968 // ...body... under fn.objects[v] = i
1969 fn.currentBlock = body
1970 fn.targets = &targets{
1971 tail: fn.targets,
1972 _break: done,
1973 _continue: post,
1974 }
1975 b.stmt(fn, s.Body)
1976 fn.targets = fn.targets.tail
1977 emitJump(fn, post)
1978 1979 // ...post... under fn.objects[v] = i_next
1980 for _, v := range vars {
1981 fn.vars[v.obj] = v.next
1982 }
1983 fn.currentBlock = post
1984 if s.Post != nil {
1985 b.stmt(fn, s.Post)
1986 }
1987 emitJump(fn, loop) // back-edge
1988 fn.currentBlock = done
1989 1990 // For each loop variable that does not escape,
1991 // (the common case), fuse its next cells into its
1992 // (local) outer cell as they have disjoint live ranges.
1993 //
1994 // It is sufficient to test whether i_next escapes,
1995 // because its Heap flag will be marked true if either
1996 // the cond or post expression causes i to escape
1997 // (because escape distributes over phi).
1998 var nlocals int
1999 for _, v := range vars {
2000 if !v.next.Heap {
2001 nlocals++
2002 }
2003 }
2004 if nlocals > 0 {
2005 replace := make(map[Value]Value, 2*nlocals)
2006 dead := make(map[Instruction]bool, 4*nlocals)
2007 for _, v := range vars {
2008 if !v.next.Heap {
2009 replace[v.next] = v.outer
2010 replace[v.phi] = v.outer
2011 dead[v.phi], dead[v.next], dead[v.load], dead[v.store] = true, true, true, true
2012 }
2013 }
2014 2015 // Replace all uses of i_next and phi with i_outer.
2016 // Referrers have not been built for fn yet so only update Instruction operands.
2017 // We need only look within the blocks added by the loop.
2018 var operands []*Value // recycle storage
2019 for _, b := range fn.Blocks[startingBlocks:] {
2020 for _, instr := range b.Instrs {
2021 operands = instr.Operands(operands[:0])
2022 for _, ptr := range operands {
2023 k := *ptr
2024 if v := replace[k]; v != nil {
2025 *ptr = v
2026 }
2027 }
2028 }
2029 }
2030 2031 // Remove instructions for phi, load, and store.
2032 // lift() will remove the unused i_next *Alloc.
2033 isDead := func(i Instruction) bool { return dead[i] }
2034 loop.Instrs = slices.DeleteFunc(loop.Instrs, isDead)
2035 post.Instrs = slices.DeleteFunc(post.Instrs, isDead)
2036 }
2037 }
2038 2039 // rangeIndexed emits to fn the header for an integer-indexed loop
2040 // over array, *array or slice value x.
2041 // The v result is defined only if tv is non-nil.
2042 // forPos is the position of the "for" token.
2043 func (b *builder) rangeIndexed(fn *Function, x Value, tv types.Type, pos token.Pos) (k, v Value, loop, done *BasicBlock) {
2044 //
2045 // length = len(x)
2046 // index = -1
2047 // loop: (target of continue)
2048 // index++
2049 // if index < length goto body else done
2050 // body:
2051 // k = index
2052 // v = x[index]
2053 // ...body...
2054 // jump loop
2055 // done: (target of break)
2056 2057 // Determine number of iterations.
2058 var length Value
2059 dt := typeparams.Deref(x.Type())
2060 if arr, ok := typeparams.CoreType(dt).(*types.Array); ok {
2061 // For array or *array, the number of iterations is
2062 // known statically thanks to the type. We avoid a
2063 // data dependence upon x, permitting later dead-code
2064 // elimination if x is pure, static unrolling, etc.
2065 // Ranging over a nil *array may have >0 iterations.
2066 // We still generate code for x, in case it has effects.
2067 length = intConst(arr.Len())
2068 } else {
2069 // length = len(x).
2070 var c Call
2071 c.Call.Value = makeLen(x.Type())
2072 c.Call.Args = []Value{x}
2073 c.setType(tInt)
2074 length = fn.emit(&c)
2075 }
2076 2077 index := emitLocal(fn, tInt, token.NoPos, "rangeindex")
2078 emitStore(fn, index, intConst(-1), pos)
2079 2080 loop = fn.newBasicBlock("rangeindex.loop")
2081 emitJump(fn, loop)
2082 fn.currentBlock = loop
2083 2084 incr := &BinOp{
2085 Op: token.ADD,
2086 X: emitLoad(fn, index),
2087 Y: vOne,
2088 }
2089 incr.setType(tInt)
2090 emitStore(fn, index, fn.emit(incr), pos)
2091 2092 body := fn.newBasicBlock("rangeindex.body")
2093 done = fn.newBasicBlock("rangeindex.done")
2094 emitIf(fn, emitCompare(fn, token.LSS, incr, length, token.NoPos), body, done)
2095 fn.currentBlock = body
2096 2097 k = emitLoad(fn, index)
2098 if tv != nil {
2099 switch t := typeparams.CoreType(x.Type()).(type) {
2100 case *types.Array:
2101 instr := &Index{
2102 X: x,
2103 Index: k,
2104 }
2105 instr.setType(t.Elem())
2106 instr.setPos(x.Pos())
2107 v = fn.emit(instr)
2108 2109 case *types.Pointer: // *array
2110 instr := &IndexAddr{
2111 X: x,
2112 Index: k,
2113 }
2114 instr.setType(types.NewPointer(t.Elem().Underlying().(*types.Array).Elem()))
2115 instr.setPos(x.Pos())
2116 v = emitLoad(fn, fn.emit(instr))
2117 2118 case *types.Slice:
2119 instr := &IndexAddr{
2120 X: x,
2121 Index: k,
2122 }
2123 instr.setType(types.NewPointer(t.Elem()))
2124 instr.setPos(x.Pos())
2125 v = emitLoad(fn, fn.emit(instr))
2126 2127 case *types.Basic: // Moxie: string=[]byte, range yields bytes
2128 instr := &Index{
2129 X: x,
2130 Index: k,
2131 }
2132 instr.setType(types.Typ[types.Byte])
2133 instr.setPos(x.Pos())
2134 v = fn.emit(instr)
2135 2136 default:
2137 panic("rangeIndexed x:" + t.String())
2138 }
2139 }
2140 return
2141 }
2142 2143 // rangeIter emits to fn the header for a loop using
2144 // Range/Next/Extract to iterate over map or string value x.
2145 // tk and tv are the types of the key/value results k and v, or nil
2146 // if the respective component is not wanted.
2147 func (b *builder) rangeIter(fn *Function, x Value, tk, tv types.Type, pos token.Pos) (k, v Value, loop, done *BasicBlock) {
2148 //
2149 // it = range x
2150 // loop: (target of continue)
2151 // okv = next it (ok, key, value)
2152 // ok = extract okv #0
2153 // if ok goto body else done
2154 // body:
2155 // k = extract okv #1
2156 // v = extract okv #2
2157 // ...body...
2158 // jump loop
2159 // done: (target of break)
2160 //
2161 2162 if tk == nil {
2163 tk = tInvalid
2164 }
2165 if tv == nil {
2166 tv = tInvalid
2167 }
2168 2169 rng := &Range{X: x}
2170 rng.setPos(pos)
2171 rng.setType(tRangeIter)
2172 it := fn.emit(rng)
2173 2174 loop = fn.newBasicBlock("rangeiter.loop")
2175 emitJump(fn, loop)
2176 fn.currentBlock = loop
2177 2178 okv := &Next{
2179 Iter: it,
2180 IsString: isBasic(typeparams.CoreType(x.Type())),
2181 }
2182 okv.setType(types.NewTuple(
2183 varOk,
2184 newVar("k", tk),
2185 newVar("v", tv),
2186 ))
2187 fn.emit(okv)
2188 2189 body := fn.newBasicBlock("rangeiter.body")
2190 done = fn.newBasicBlock("rangeiter.done")
2191 emitIf(fn, emitExtract(fn, okv, 0), body, done)
2192 fn.currentBlock = body
2193 2194 if tk != tInvalid {
2195 k = emitExtract(fn, okv, 1)
2196 }
2197 if tv != tInvalid {
2198 v = emitExtract(fn, okv, 2)
2199 }
2200 return
2201 }
2202 2203 // rangeChan emits to fn the header for a loop that receives from
2204 // channel x until it fails.
2205 // tk is the channel's element type, or nil if the k result is
2206 // not wanted
2207 // pos is the position of the '=' or ':=' token.
2208 func (b *builder) rangeChan(fn *Function, x Value, tk types.Type, pos token.Pos) (k Value, loop, done *BasicBlock) {
2209 //
2210 // loop: (target of continue)
2211 // ko = <-x (key, ok)
2212 // ok = extract ko #1
2213 // if ok goto body else done
2214 // body:
2215 // k = extract ko #0
2216 // ...body...
2217 // goto loop
2218 // done: (target of break)
2219 2220 loop = fn.newBasicBlock("rangechan.loop")
2221 emitJump(fn, loop)
2222 fn.currentBlock = loop
2223 recv := &UnOp{
2224 Op: token.ARROW,
2225 X: x,
2226 CommaOk: true,
2227 }
2228 recv.setPos(pos)
2229 recv.setType(types.NewTuple(
2230 newVar("k", typeparams.CoreType(x.Type()).(*types.Chan).Elem()),
2231 varOk,
2232 ))
2233 ko := fn.emit(recv)
2234 body := fn.newBasicBlock("rangechan.body")
2235 done = fn.newBasicBlock("rangechan.done")
2236 emitIf(fn, emitExtract(fn, ko, 1), body, done)
2237 fn.currentBlock = body
2238 if tk != nil {
2239 k = emitExtract(fn, ko, 0)
2240 }
2241 return
2242 }
2243 2244 // rangeInt emits to fn the header for a range loop with an integer operand.
2245 // tk is the key value's type, or nil if the k result is not wanted.
2246 // pos is the position of the "for" token.
2247 func (b *builder) rangeInt(fn *Function, x Value, tk types.Type, pos token.Pos) (k Value, loop, done *BasicBlock) {
2248 //
2249 // iter = 0
2250 // if 0 < x goto body else done
2251 // loop: (target of continue)
2252 // iter++
2253 // if iter < x goto body else done
2254 // body:
2255 // k = x
2256 // ...body...
2257 // jump loop
2258 // done: (target of break)
2259 2260 if isUntyped(x.Type()) {
2261 x = emitConv(fn, x, tInt)
2262 }
2263 2264 T := x.Type()
2265 iter := emitLocal(fn, T, token.NoPos, "rangeint.iter")
2266 // x may be unsigned. Avoid initializing x to -1.
2267 2268 body := fn.newBasicBlock("rangeint.body")
2269 done = fn.newBasicBlock("rangeint.done")
2270 emitIf(fn, emitCompare(fn, token.LSS, zeroConst(T), x, token.NoPos), body, done)
2271 2272 loop = fn.newBasicBlock("rangeint.loop")
2273 fn.currentBlock = loop
2274 2275 incr := &BinOp{
2276 Op: token.ADD,
2277 X: emitLoad(fn, iter),
2278 Y: emitConv(fn, vOne, T),
2279 }
2280 incr.setType(T)
2281 emitStore(fn, iter, fn.emit(incr), pos)
2282 emitIf(fn, emitCompare(fn, token.LSS, incr, x, token.NoPos), body, done)
2283 fn.currentBlock = body
2284 2285 if tk != nil {
2286 // Integer types (int, uint8, etc.) are named and
2287 // we know that k is assignable to x when tk != nil.
2288 // This implies tk and T are identical so no conversion is needed.
2289 k = emitLoad(fn, iter)
2290 }
2291 2292 return
2293 }
2294 2295 // rangeStmt emits to fn code for the range statement s, optionally
2296 // labelled by label.
2297 func (b *builder) rangeStmt(fn *Function, s *ast.RangeStmt, label *lblock) {
2298 var tk, tv types.Type
2299 if s.Key != nil && !isBlankIdent(s.Key) {
2300 tk = fn.typeOf(s.Key)
2301 }
2302 if s.Value != nil && !isBlankIdent(s.Value) {
2303 tv = fn.typeOf(s.Value)
2304 }
2305 2306 // create locals for s.Key and s.Value.
2307 createVars := func() {
2308 // Unlike a short variable declaration, a RangeStmt
2309 // using := never redeclares an existing variable; it
2310 // always creates a new one.
2311 if tk != nil {
2312 emitLocalVar(fn, identVar(fn, s.Key.(*ast.Ident)))
2313 }
2314 if tv != nil {
2315 emitLocalVar(fn, identVar(fn, s.Value.(*ast.Ident)))
2316 }
2317 }
2318 2319 afterGo122 := versions.AtLeast(fn.goversion, versions.Go1_22)
2320 if s.Tok == token.DEFINE && !afterGo122 {
2321 // pre-go1.22: If iteration variables are defined (:=), this
2322 // occurs once outside the loop.
2323 createVars()
2324 }
2325 2326 x := b.expr(fn, s.X)
2327 2328 var k, v Value
2329 var loop, done *BasicBlock
2330 switch rt := typeparams.CoreType(x.Type()).(type) {
2331 case *types.Slice, *types.Array, *types.Pointer: // *array
2332 k, v, loop, done = b.rangeIndexed(fn, x, tv, s.For)
2333 2334 case *types.Chan:
2335 k, loop, done = b.rangeChan(fn, x, tk, s.For)
2336 2337 case *types.Map:
2338 k, v, loop, done = b.rangeIter(fn, x, tk, tv, s.For)
2339 2340 case *types.Basic:
2341 switch {
2342 case rt.Info()&types.IsString != 0:
2343 // Moxie: string=[]byte, range yields bytes not runes.
2344 k, v, loop, done = b.rangeIndexed(fn, x, tv, s.For)
2345 2346 case rt.Info()&types.IsInteger != 0:
2347 k, loop, done = b.rangeInt(fn, x, tk, s.For)
2348 2349 default:
2350 panic("Cannot range over basic type: " + rt.String())
2351 }
2352 2353 case *types.Signature:
2354 // Special case rewrite (fn.goversion >= go1.23):
2355 // for x := range f { ... }
2356 // into
2357 // f(func(x T) bool { ... })
2358 b.rangeFunc(fn, x, s, label)
2359 return
2360 2361 default:
2362 panic("Cannot range over: " + rt.String())
2363 }
2364 2365 if s.Tok == token.DEFINE && afterGo122 {
2366 // go1.22: If iteration variables are defined (:=), this occurs inside the loop.
2367 createVars()
2368 }
2369 2370 // Evaluate both LHS expressions before we update either.
2371 var kl, vl lvalue
2372 if tk != nil {
2373 kl = b.addr(fn, s.Key, false) // non-escaping
2374 }
2375 if tv != nil {
2376 vl = b.addr(fn, s.Value, false) // non-escaping
2377 }
2378 if tk != nil {
2379 kl.store(fn, k)
2380 }
2381 if tv != nil {
2382 vl.store(fn, v)
2383 }
2384 2385 if label != nil {
2386 label._break = done
2387 label._continue = loop
2388 }
2389 2390 fn.targets = &targets{
2391 tail: fn.targets,
2392 _break: done,
2393 _continue: loop,
2394 }
2395 b.stmt(fn, s.Body)
2396 fn.targets = fn.targets.tail
2397 emitJump(fn, loop) // back-edge
2398 fn.currentBlock = done
2399 }
2400 2401 // rangeFunc emits to fn code for the range-over-func rng.Body of the iterator
2402 // function x, optionally labelled by label. It creates a new anonymous function
2403 // yield for rng and builds the function.
2404 func (b *builder) rangeFunc(fn *Function, x Value, rng *ast.RangeStmt, label *lblock) {
2405 // Consider the SSA code for the outermost range-over-func in fn:
2406 //
2407 // func fn(...) (ret R) {
2408 // ...
2409 // for k, v = range x {
2410 // ...
2411 // }
2412 // ...
2413 // }
2414 //
2415 // The code emitted into fn will look something like this.
2416 //
2417 // loop:
2418 // jump := READY
2419 // y := make closure yield [ret, deferstack, jump, k, v]
2420 // x(y)
2421 // switch jump {
2422 // [see resuming execution]
2423 // }
2424 // goto done
2425 // done:
2426 // ...
2427 //
2428 // where yield is a new synthetic yield function:
2429 //
2430 // func yield(_k tk, _v tv) bool
2431 // free variables: [ret, stack, jump, k, v]
2432 // {
2433 // entry:
2434 // if jump != READY then goto invalid else valid
2435 // invalid:
2436 // panic("iterator called when it is not in a ready state")
2437 // valid:
2438 // jump = BUSY
2439 // k = _k
2440 // v = _v
2441 // ...
2442 // cont:
2443 // jump = READY
2444 // return true
2445 // }
2446 //
2447 // Yield state:
2448 //
2449 // Each range loop has an associated jump variable that records
2450 // the state of the iterator. A yield function is initially
2451 // in a READY (0) and callable state. If the yield function is called
2452 // and is not in READY state, it panics. When it is called in a callable
2453 // state, it becomes BUSY. When execution reaches the end of the body
2454 // of the loop (or a continue statement targeting the loop is executed),
2455 // the yield function returns true and resumes being in a READY state.
2456 // After the iterator function x(y) returns, then if the yield function
2457 // is in a READY state, the yield enters the DONE state.
2458 //
2459 // Each lowered control statement (break X, continue X, goto Z, or return)
2460 // that exits the loop sets the variable to a unique positive EXIT value,
2461 // before returning false from the yield function.
2462 //
2463 // If the yield function returns abruptly due to a panic or GoExit,
2464 // it remains in a BUSY state. The generated code asserts that, after
2465 // the iterator call x(y) returns normally, the jump variable state
2466 // is DONE.
2467 //
2468 // Resuming execution:
2469 //
2470 // The code generated for the range statement checks the jump
2471 // variable to determine how to resume execution.
2472 //
2473 // switch jump {
2474 // case BUSY: panic("...")
2475 // case DONE: goto done
2476 // case READY: state = DONE; goto done
2477 // case 123: ... // action for exit 123.
2478 // case 456: ... // action for exit 456.
2479 // ...
2480 // }
2481 //
2482 // Forward goto statements within a yield are jumps to labels that
2483 // have not yet been traversed in fn. They may be in the Body of the
2484 // function. What we emit for these is:
2485 //
2486 // goto target
2487 // target:
2488 // ...
2489 //
2490 // We leave an unresolved exit in yield.exits to check at the end
2491 // of building yield if it encountered target in the body. If it
2492 // encountered target, no additional work is required. Otherwise,
2493 // the yield emits a new early exit in the basic block for target.
2494 // We expect that blockopt will fuse the early exit into the case
2495 // block later. The unresolved exit is then added to yield.parent.exits.
2496 2497 loop := fn.newBasicBlock("rangefunc.loop")
2498 done := fn.newBasicBlock("rangefunc.done")
2499 2500 // These are targets within y.
2501 fn.targets = &targets{
2502 tail: fn.targets,
2503 _break: done,
2504 // _continue is within y.
2505 }
2506 if label != nil {
2507 label._break = done
2508 // _continue is within y
2509 }
2510 2511 emitJump(fn, loop)
2512 fn.currentBlock = loop
2513 2514 // loop:
2515 // jump := READY
2516 2517 anonIdx := len(fn.AnonFuncs)
2518 2519 jump := newVar(fmt.Sprintf("jump$%d", anonIdx+1), tInt)
2520 emitLocalVar(fn, jump) // zero value is READY
2521 2522 xsig := typeparams.CoreType(x.Type()).(*types.Signature)
2523 ysig := typeparams.CoreType(xsig.Params().At(0).Type()).(*types.Signature)
2524 2525 /* synthetic yield function for body of range-over-func loop */
2526 y := &Function{
2527 name: fmt.Sprintf("%s$%d", fn.Name(), anonIdx+1),
2528 Signature: ysig,
2529 Synthetic: "range-over-func yield",
2530 pos: rng.Range,
2531 parent: fn,
2532 anonIdx: int32(len(fn.AnonFuncs)),
2533 Pkg: fn.Pkg,
2534 Prog: fn.Prog,
2535 syntax: rng,
2536 info: fn.info,
2537 goversion: fn.goversion,
2538 build: (*builder).buildYieldFunc,
2539 topLevelOrigin: nil,
2540 typeparams: fn.typeparams,
2541 typeargs: fn.typeargs,
2542 subst: fn.subst,
2543 jump: jump,
2544 deferstack: fn.deferstack,
2545 returnVars: fn.returnVars, // use the parent's return variables
2546 uniq: fn.uniq, // start from parent's unique values
2547 }
2548 2549 // If the RangeStmt has a label, this is how it is passed to buildYieldFunc.
2550 if label != nil {
2551 y.lblocks = map[*types.Label]*lblock{label.label: nil}
2552 }
2553 fn.AnonFuncs = append(fn.AnonFuncs, y)
2554 2555 // Build y immediately. It may:
2556 // * cause fn's locals to escape, and
2557 // * create new exit nodes in exits.
2558 // (y is not marked 'built' until the end of the enclosing FuncDecl.)
2559 unresolved := len(fn.exits)
2560 y.build(b, y)
2561 fn.uniq = y.uniq // resume after y's unique values
2562 2563 // Emit the call of y.
2564 // c := MakeClosure y
2565 // x(c)
2566 c := &MakeClosure{Fn: y}
2567 c.setType(ysig)
2568 for _, fv := range y.FreeVars {
2569 c.Bindings = append(c.Bindings, fv.outer)
2570 fv.outer = nil
2571 }
2572 fn.emit(c)
2573 call := Call{
2574 Call: CallCommon{
2575 Value: x,
2576 Args: []Value{c},
2577 pos: token.NoPos,
2578 },
2579 }
2580 call.setType(xsig.Results())
2581 fn.emit(&call)
2582 2583 exits := fn.exits[unresolved:]
2584 b.buildYieldResume(fn, jump, exits, done)
2585 2586 emitJump(fn, done)
2587 fn.currentBlock = done
2588 // pop the stack for the range-over-func
2589 fn.targets = fn.targets.tail
2590 }
2591 2592 // buildYieldResume emits to fn code for how to resume execution once a call to
2593 // the iterator function over the yield function returns x(y). It does this by building
2594 // a switch over the value of jump for when it is READY, BUSY, or EXIT(id).
2595 func (b *builder) buildYieldResume(fn *Function, jump *types.Var, exits []*exit, done *BasicBlock) {
2596 // v := *jump
2597 // switch v {
2598 // case BUSY: panic("...")
2599 // case READY: jump = DONE; goto done
2600 // case EXIT(a): ...
2601 // case EXIT(b): ...
2602 // ...
2603 // }
2604 v := emitLoad(fn, fn.lookup(jump, false))
2605 2606 // case BUSY: panic("...")
2607 isbusy := fn.newBasicBlock("rangefunc.resume.busy")
2608 ifready := fn.newBasicBlock("rangefunc.resume.ready.check")
2609 emitIf(fn, emitCompare(fn, token.EQL, v, jBusy, token.NoPos), isbusy, ifready)
2610 fn.currentBlock = isbusy
2611 fn.emit(&Panic{
2612 X: emitConv(fn, stringConst("iterator call did not preserve panic"), tEface),
2613 })
2614 fn.currentBlock = ifready
2615 2616 // case READY: jump = DONE; goto done
2617 isready := fn.newBasicBlock("rangefunc.resume.ready")
2618 ifexit := fn.newBasicBlock("rangefunc.resume.exits")
2619 emitIf(fn, emitCompare(fn, token.EQL, v, jReady, token.NoPos), isready, ifexit)
2620 fn.currentBlock = isready
2621 storeVar(fn, jump, jDone, token.NoPos)
2622 emitJump(fn, done)
2623 fn.currentBlock = ifexit
2624 2625 for _, e := range exits {
2626 id := intConst(e.id)
2627 2628 // case EXIT(id): { /* do e */ }
2629 cond := emitCompare(fn, token.EQL, v, id, e.pos)
2630 matchb := fn.newBasicBlock("rangefunc.resume.match")
2631 cndb := fn.newBasicBlock("rangefunc.resume.cnd")
2632 emitIf(fn, cond, matchb, cndb)
2633 fn.currentBlock = matchb
2634 2635 // Cases to fill in the { /* do e */ } bit.
2636 switch {
2637 case e.label != nil: // forward goto?
2638 // case EXIT(id): goto lb // label
2639 lb := fn.lblockOf(e.label)
2640 // Do not mark lb as resolved.
2641 // If fn does not contain label, lb remains unresolved and
2642 // fn must itself be a range-over-func function. lb will be:
2643 // lb:
2644 // fn.jump = id
2645 // return false
2646 emitJump(fn, lb._goto)
2647 2648 case e.to != fn: // e jumps to an ancestor of fn?
2649 // case EXIT(id): { fn.jump = id; return false }
2650 // fn is a range-over-func function.
2651 storeVar(fn, fn.jump, id, token.NoPos)
2652 fn.emit(&Return{Results: []Value{vFalse}, pos: e.pos})
2653 2654 case e.block == nil && e.label == nil: // return from fn?
2655 // case EXIT(id): { return ... }
2656 fn.emit(new(RunDefers))
2657 results := make([]Value, len(fn.results))
2658 for i, r := range fn.results {
2659 results[i] = emitLoad(fn, r)
2660 }
2661 fn.emit(&Return{Results: results, pos: e.pos})
2662 2663 case e.block != nil:
2664 // case EXIT(id): goto block
2665 emitJump(fn, e.block)
2666 2667 default:
2668 panic("unreachable")
2669 }
2670 fn.currentBlock = cndb
2671 }
2672 }
2673 2674 // stmt lowers statement s to SSA form, emitting code to fn.
2675 func (b *builder) stmt(fn *Function, _s ast.Stmt) {
2676 // The label of the current statement. If non-nil, its _goto
2677 // target is always set; its _break and _continue are set only
2678 // within the body of switch/typeswitch/select/for/range.
2679 // It is effectively an additional default-nil parameter of stmt().
2680 var label *lblock
2681 start:
2682 switch s := _s.(type) {
2683 case *ast.EmptyStmt:
2684 // ignore. (Usually removed by gofmt.)
2685 2686 case *ast.DeclStmt: // Con, Var or Typ
2687 d := s.Decl.(*ast.GenDecl)
2688 if d.Tok == token.VAR {
2689 for _, spec := range d.Specs {
2690 if vs, ok := spec.(*ast.ValueSpec); ok {
2691 b.localValueSpec(fn, vs)
2692 }
2693 }
2694 }
2695 2696 case *ast.LabeledStmt:
2697 if s.Label.Name == "_" {
2698 // Blank labels can't be the target of a goto, break,
2699 // or continue statement, so we don't need a new block.
2700 _s = s.Stmt
2701 goto start
2702 }
2703 label = fn.lblockOf(fn.label(s.Label))
2704 label.resolved = true
2705 emitJump(fn, label._goto)
2706 fn.currentBlock = label._goto
2707 _s = s.Stmt
2708 goto start // effectively: tailcall stmt(fn, s.Stmt, label)
2709 2710 case *ast.ExprStmt:
2711 b.expr(fn, s.X)
2712 2713 case *ast.SendStmt:
2714 chtyp := typeparams.CoreType(fn.typeOf(s.Chan)).(*types.Chan)
2715 fn.emit(&Send{
2716 Chan: b.expr(fn, s.Chan),
2717 X: emitConv(fn, b.expr(fn, s.Value), chtyp.Elem()),
2718 pos: s.Arrow,
2719 })
2720 2721 case *ast.IncDecStmt:
2722 op := token.ADD
2723 if s.Tok == token.DEC {
2724 op = token.SUB
2725 }
2726 loc := b.addr(fn, s.X, false)
2727 b.assignOp(fn, loc, NewConst(constant.MakeInt64(1), loc.typ()), op, s.Pos())
2728 2729 case *ast.AssignStmt:
2730 switch s.Tok {
2731 case token.ASSIGN, token.DEFINE:
2732 b.assignStmt(fn, s.Lhs, s.Rhs, s.Tok == token.DEFINE)
2733 2734 default: // +=, etc.
2735 op := s.Tok + token.ADD - token.ADD_ASSIGN
2736 b.assignOp(fn, b.addr(fn, s.Lhs[0], false), b.expr(fn, s.Rhs[0]), op, s.Pos())
2737 }
2738 2739 case *ast.GoStmt:
2740 // The "intrinsics" new/make/len/cap are forbidden here.
2741 // panic is treated like an ordinary function call.
2742 v := Go{pos: s.Go}
2743 b.setCall(fn, s.Call, &v.Call)
2744 fn.emit(&v)
2745 2746 case *ast.DeferStmt:
2747 // The "intrinsics" new/make/len/cap are forbidden here.
2748 // panic is treated like an ordinary function call.
2749 deferstack := emitLoad(fn, fn.lookup(fn.deferstack, false))
2750 v := Defer{pos: s.Defer, DeferStack: deferstack}
2751 b.setCall(fn, s.Call, &v.Call)
2752 fn.emit(&v)
2753 2754 // A deferred call can cause recovery from panic,
2755 // and control resumes at the Recover block.
2756 createRecoverBlock(fn.source)
2757 2758 case *ast.ReturnStmt:
2759 b.returnStmt(fn, s)
2760 2761 case *ast.BranchStmt:
2762 b.branchStmt(fn, s)
2763 2764 case *ast.BlockStmt:
2765 b.stmtList(fn, s.List)
2766 2767 case *ast.IfStmt:
2768 if s.Init != nil {
2769 b.stmt(fn, s.Init)
2770 }
2771 then := fn.newBasicBlock("if.then")
2772 done := fn.newBasicBlock("if.done")
2773 els := done
2774 if s.Else != nil {
2775 els = fn.newBasicBlock("if.else")
2776 }
2777 b.cond(fn, s.Cond, then, els)
2778 fn.currentBlock = then
2779 b.stmt(fn, s.Body)
2780 emitJump(fn, done)
2781 2782 if s.Else != nil {
2783 fn.currentBlock = els
2784 b.stmt(fn, s.Else)
2785 emitJump(fn, done)
2786 }
2787 2788 fn.currentBlock = done
2789 2790 case *ast.SwitchStmt:
2791 b.switchStmt(fn, s, label)
2792 2793 case *ast.TypeSwitchStmt:
2794 b.typeSwitchStmt(fn, s, label)
2795 2796 case *ast.SelectStmt:
2797 b.selectStmt(fn, s, label)
2798 2799 case *ast.ForStmt:
2800 b.forStmt(fn, s, label)
2801 2802 case *ast.RangeStmt:
2803 b.rangeStmt(fn, s, label)
2804 2805 default:
2806 panic(fmt.Sprintf("unexpected statement kind: %T", s))
2807 }
2808 }
2809 2810 func (b *builder) branchStmt(fn *Function, s *ast.BranchStmt) {
2811 var block *BasicBlock
2812 if s.Label == nil {
2813 block = targetedBlock(fn, s.Tok)
2814 } else {
2815 target := fn.label(s.Label)
2816 block = labelledBlock(fn, target, s.Tok)
2817 if block == nil { // forward goto
2818 lb := fn.lblockOf(target)
2819 block = lb._goto // jump to lb._goto
2820 if fn.jump != nil {
2821 // fn is a range-over-func and the goto may exit fn.
2822 // Create an exit and resolve it at the end of
2823 // builder.buildYieldFunc.
2824 labelExit(fn, target, s.Pos())
2825 }
2826 }
2827 }
2828 to := block.parent
2829 2830 if to == fn {
2831 emitJump(fn, block)
2832 } else { // break outside of fn.
2833 // fn must be a range-over-func
2834 e := blockExit(fn, block, s.Pos())
2835 storeVar(fn, fn.jump, intConst(e.id), e.pos)
2836 fn.emit(&Return{Results: []Value{vFalse}, pos: e.pos})
2837 }
2838 fn.currentBlock = fn.newBasicBlock("unreachable")
2839 }
2840 2841 func (b *builder) returnStmt(fn *Function, s *ast.ReturnStmt) {
2842 var results []Value
2843 2844 sig := fn.source.Signature // signature of the enclosing source function
2845 2846 // Convert return operands to result type.
2847 if len(s.Results) == 1 && sig.Results().Len() > 1 {
2848 // Return of one expression in a multi-valued function.
2849 tuple := b.exprN(fn, s.Results[0])
2850 ttuple := tuple.Type().(*types.Tuple)
2851 for i, n := 0, ttuple.Len(); i < n; i++ {
2852 results = append(results,
2853 emitConv(fn, emitExtract(fn, tuple, i),
2854 sig.Results().At(i).Type()))
2855 }
2856 } else {
2857 // 1:1 return, or no-arg return in non-void function.
2858 for i, r := range s.Results {
2859 v := emitConv(fn, b.expr(fn, r), sig.Results().At(i).Type())
2860 results = append(results, v)
2861 }
2862 }
2863 2864 // Store the results.
2865 for i, r := range results {
2866 var result Value // fn.source.result[i] conceptually
2867 if fn == fn.source {
2868 result = fn.results[i]
2869 } else { // lookup needed?
2870 result = fn.lookup(fn.returnVars[i], false)
2871 }
2872 emitStore(fn, result, r, s.Return)
2873 }
2874 2875 if fn.jump != nil {
2876 // Return from body of a range-over-func.
2877 // The return statement is syntactically within the loop,
2878 // but the generated code is in the 'switch jump {...}' after it.
2879 e := returnExit(fn, s.Pos())
2880 storeVar(fn, fn.jump, intConst(e.id), e.pos)
2881 fn.emit(&Return{Results: []Value{vFalse}, pos: e.pos})
2882 fn.currentBlock = fn.newBasicBlock("unreachable")
2883 return
2884 }
2885 2886 // Run function calls deferred in this
2887 // function when explicitly returning from it.
2888 fn.emit(new(RunDefers))
2889 // Reload (potentially) named result variables to form the result tuple.
2890 results = results[:0]
2891 for _, nr := range fn.results {
2892 results = append(results, emitLoad(fn, nr))
2893 }
2894 fn.emit(&Return{Results: results, pos: s.Return})
2895 fn.currentBlock = fn.newBasicBlock("unreachable")
2896 }
2897 2898 // A buildFunc is a strategy for building the SSA body for a function.
2899 type buildFunc = func(*builder, *Function)
2900 2901 // iterate causes all created but unbuilt functions to be built. As
2902 // this may create new methods, the process is iterated until it
2903 // converges.
2904 //
2905 // Waits for any dependencies to finish building.
2906 func (b *builder) iterate() {
2907 for ; b.finished < len(b.fns); b.finished++ {
2908 fn := b.fns[b.finished]
2909 b.buildFunction(fn)
2910 }
2911 2912 b.buildshared.markDone()
2913 b.buildshared.wait()
2914 }
2915 2916 // buildFunction builds SSA code for the body of function fn. Idempotent.
2917 func (b *builder) buildFunction(fn *Function) {
2918 if fn.build != nil {
2919 assert(fn.parent == nil, "anonymous functions should not be built by buildFunction()")
2920 2921 if fn.Prog.mode&LogSource != 0 {
2922 defer logStack("build %s @ %s", fn, fn.Prog.Fset.Position(fn.pos))()
2923 }
2924 fn.build(b, fn)
2925 fn.done()
2926 }
2927 }
2928 2929 // buildParamsOnly builds fn.Params from fn.Signature, but does not build fn.Body.
2930 func (b *builder) buildParamsOnly(fn *Function) {
2931 // For external (C, asm) functions or functions loaded from
2932 // export data, we must set fn.Params even though there is no
2933 // body code to reference them.
2934 if recv := fn.Signature.Recv(); recv != nil {
2935 fn.addParamVar(recv)
2936 }
2937 params := fn.Signature.Params()
2938 for i, n := 0, params.Len(); i < n; i++ {
2939 fn.addParamVar(params.At(i))
2940 }
2941 2942 // clear out other function state (keep consistent with finishBody)
2943 fn.subst = nil
2944 }
2945 2946 // buildFromSyntax builds fn.Body from fn.syntax, which must be non-nil.
2947 func (b *builder) buildFromSyntax(fn *Function) {
2948 var (
2949 recvField *ast.FieldList
2950 body *ast.BlockStmt
2951 functype *ast.FuncType
2952 )
2953 switch syntax := fn.syntax.(type) {
2954 case *ast.FuncDecl:
2955 functype = syntax.Type
2956 recvField = syntax.Recv
2957 body = syntax.Body
2958 if body == nil {
2959 b.buildParamsOnly(fn) // no body (non-Go function)
2960 return
2961 }
2962 case *ast.FuncLit:
2963 functype = syntax.Type
2964 body = syntax.Body
2965 case nil:
2966 panic("no syntax")
2967 default:
2968 panic(syntax) // unexpected syntax
2969 }
2970 fn.source = fn
2971 fn.startBody()
2972 fn.createSyntacticParams(recvField, functype)
2973 fn.createDeferStack()
2974 b.stmt(fn, body)
2975 if cb := fn.currentBlock; cb != nil && (cb == fn.Blocks[0] || cb == fn.Recover || cb.Preds != nil) {
2976 // Control fell off the end of the function's body block.
2977 //
2978 // Block optimizations eliminate the current block, if
2979 // unreachable. It is a builder invariant that
2980 // if this no-arg return is ill-typed for
2981 // fn.Signature.Results, this block must be
2982 // unreachable. The sanity checker checks this.
2983 fn.emit(new(RunDefers))
2984 fn.emit(new(Return))
2985 }
2986 fn.finishBody()
2987 }
2988 2989 // buildYieldFunc builds the body of the yield function created
2990 // from a range-over-func *ast.RangeStmt.
2991 func (b *builder) buildYieldFunc(fn *Function) {
2992 // See builder.rangeFunc for detailed documentation on how fn is set up.
2993 //
2994 // In pseudo-Go this roughly builds:
2995 // func yield(_k tk, _v tv) bool {
2996 // if jump != READY { panic("yield function called after range loop exit") }
2997 // jump = BUSY
2998 // k, v = _k, _v // assign the iterator variable (if needed)
2999 // ... // rng.Body
3000 // continue:
3001 // jump = READY
3002 // return true
3003 // }
3004 s := fn.syntax.(*ast.RangeStmt)
3005 fn.source = fn.parent.source
3006 fn.startBody()
3007 params := fn.Signature.Params()
3008 for v := range params.Variables() {
3009 fn.addParamVar(v)
3010 }
3011 3012 // Initial targets
3013 ycont := fn.newBasicBlock("yield-continue")
3014 // lblocks is either {} or is {label: nil} where label is the label of syntax.
3015 for label := range fn.lblocks {
3016 fn.lblocks[label] = &lblock{
3017 label: label,
3018 resolved: true,
3019 _goto: ycont,
3020 _continue: ycont,
3021 // `break label` statement targets fn.parent.targets._break
3022 }
3023 }
3024 fn.targets = &targets{
3025 tail: fn.targets,
3026 _continue: ycont,
3027 // `break` statement targets fn.parent.targets._break.
3028 }
3029 3030 // continue:
3031 // jump = READY
3032 // return true
3033 saved := fn.currentBlock
3034 fn.currentBlock = ycont
3035 storeVar(fn, fn.jump, jReady, s.Body.Rbrace)
3036 // A yield function's own deferstack is always empty, so rundefers is not needed.
3037 fn.emit(&Return{Results: []Value{vTrue}, pos: token.NoPos})
3038 3039 // Emit header:
3040 //
3041 // if jump != READY { panic("yield iterator accessed after exit") }
3042 // jump = BUSY
3043 // k, v = _k, _v
3044 fn.currentBlock = saved
3045 yloop := fn.newBasicBlock("yield-loop")
3046 invalid := fn.newBasicBlock("yield-invalid")
3047 3048 jumpVal := emitLoad(fn, fn.lookup(fn.jump, true))
3049 emitIf(fn, emitCompare(fn, token.EQL, jumpVal, jReady, token.NoPos), yloop, invalid)
3050 fn.currentBlock = invalid
3051 fn.emit(&Panic{
3052 X: emitConv(fn, stringConst("yield function called after range loop exit"), tEface),
3053 })
3054 3055 fn.currentBlock = yloop
3056 storeVar(fn, fn.jump, jBusy, s.Body.Rbrace)
3057 3058 // Initialize k and v from params.
3059 var tk, tv types.Type
3060 if s.Key != nil && !isBlankIdent(s.Key) {
3061 tk = fn.typeOf(s.Key) // fn.parent.typeOf is identical
3062 }
3063 if s.Value != nil && !isBlankIdent(s.Value) {
3064 tv = fn.typeOf(s.Value)
3065 }
3066 if s.Tok == token.DEFINE {
3067 if tk != nil {
3068 emitLocalVar(fn, identVar(fn, s.Key.(*ast.Ident)))
3069 }
3070 if tv != nil {
3071 emitLocalVar(fn, identVar(fn, s.Value.(*ast.Ident)))
3072 }
3073 }
3074 var k, v Value
3075 if len(fn.Params) > 0 {
3076 k = fn.Params[0]
3077 }
3078 if len(fn.Params) > 1 {
3079 v = fn.Params[1]
3080 }
3081 var kl, vl lvalue
3082 if tk != nil {
3083 kl = b.addr(fn, s.Key, false) // non-escaping
3084 }
3085 if tv != nil {
3086 vl = b.addr(fn, s.Value, false) // non-escaping
3087 }
3088 if tk != nil {
3089 kl.store(fn, k)
3090 }
3091 if tv != nil {
3092 vl.store(fn, v)
3093 }
3094 3095 // Build the body of the range loop.
3096 b.stmt(fn, s.Body)
3097 if cb := fn.currentBlock; cb != nil && (cb == fn.Blocks[0] || cb == fn.Recover || cb.Preds != nil) {
3098 // Control fell off the end of the function's body block.
3099 // Block optimizations eliminate the current block, if
3100 // unreachable.
3101 emitJump(fn, ycont)
3102 }
3103 // pop the stack for the yield function
3104 fn.targets = fn.targets.tail
3105 3106 // Clean up exits and promote any unresolved exits to fn.parent.
3107 for _, e := range fn.exits {
3108 if e.label != nil {
3109 lb := fn.lblocks[e.label]
3110 if lb.resolved {
3111 // label was resolved. Do not turn lb into an exit.
3112 // e does not need to be handled by the parent.
3113 continue
3114 }
3115 3116 // _goto becomes an exit.
3117 // _goto:
3118 // jump = id
3119 // return false
3120 fn.currentBlock = lb._goto
3121 id := intConst(e.id)
3122 storeVar(fn, fn.jump, id, e.pos)
3123 fn.emit(&Return{Results: []Value{vFalse}, pos: e.pos})
3124 }
3125 3126 if e.to != fn { // e needs to be handled by the parent too.
3127 fn.parent.exits = append(fn.parent.exits, e)
3128 }
3129 }
3130 3131 fn.finishBody()
3132 }
3133 3134 // addMakeInterfaceType records non-interface type t as the type of
3135 // the operand a MakeInterface operation, for [Program.RuntimeTypes].
3136 //
3137 // Acquires prog.makeInterfaceTypesMu.
3138 func addMakeInterfaceType(prog *Program, t types.Type) {
3139 prog.makeInterfaceTypesMu.Lock()
3140 defer prog.makeInterfaceTypesMu.Unlock()
3141 if prog.makeInterfaceTypes == nil {
3142 prog.makeInterfaceTypes = make(map[types.Type]unit)
3143 }
3144 prog.makeInterfaceTypes[t] = unit{}
3145 }
3146 3147 // Build calls Package.Build for each package in prog.
3148 // Building occurs in parallel unless the BuildSerially mode flag was set.
3149 //
3150 // Build is intended for whole-program analysis; a typical compiler
3151 // need only build a single package.
3152 //
3153 // Build is idempotent and thread-safe.
3154 func (prog *Program) Build() {
3155 var wg sync.WaitGroup
3156 for _, p := range prog.packages {
3157 if prog.mode&BuildSerially != 0 {
3158 p.Build()
3159 } else {
3160 wg.Add(1)
3161 cpuLimit <- unit{} // acquire a token
3162 go func(p *Package) {
3163 p.Build()
3164 wg.Done()
3165 <-cpuLimit // release a token
3166 }(p)
3167 }
3168 }
3169 wg.Wait()
3170 }
3171 3172 // cpuLimit is a counting semaphore to limit CPU parallelism.
3173 var cpuLimit = make(chan unit, runtime.GOMAXPROCS(0))
3174 3175 // Build builds SSA code for all functions and vars in package p.
3176 //
3177 // CreatePackage must have been called for all of p's direct imports
3178 // (and hence its direct imports must have been error-free). It is not
3179 // necessary to call CreatePackage for indirect dependencies.
3180 // Functions will be created for all necessary methods in those
3181 // packages on demand.
3182 //
3183 // Build is idempotent and thread-safe.
3184 func (p *Package) Build() { p.buildOnce.Do(p.build) }
3185 3186 func (p *Package) build() {
3187 if p.info == nil {
3188 return // synthetic package, e.g. "testmain"
3189 }
3190 if p.Prog.mode&LogSource != 0 {
3191 defer logStack("build %s", p)()
3192 }
3193 3194 b := builder{fns: p.created}
3195 b.iterate()
3196 3197 // We no longer need transient information: ASTs or go/types deductions.
3198 p.info = nil
3199 p.created = nil
3200 p.files = nil
3201 p.initVersion = nil
3202 3203 if p.Prog.mode&SanityCheckFunctions != 0 {
3204 sanityCheckPackage(p)
3205 }
3206 }
3207 3208 // buildPackageInit builds fn.Body for the synthetic package initializer.
3209 func (b *builder) buildPackageInit(fn *Function) {
3210 p := fn.Pkg
3211 fn.startBody()
3212 3213 var done *BasicBlock
3214 3215 if p.Prog.mode&BareInits == 0 {
3216 // Make init() skip if package is already initialized.
3217 initguard := p.Var("init$guard")
3218 doinit := fn.newBasicBlock("init.start")
3219 done = fn.newBasicBlock("init.done")
3220 emitIf(fn, emitLoad(fn, initguard), done, doinit)
3221 fn.currentBlock = doinit
3222 emitStore(fn, initguard, vTrue, token.NoPos)
3223 3224 // Call the init() function of each package we import.
3225 for _, pkg := range p.Pkg.Imports() {
3226 prereq := p.Prog.packages[pkg]
3227 if prereq == nil {
3228 panic(fmt.Sprintf("Package(%q).Build(): unsatisfied import: Program.CreatePackage(%q) was not called", p.Pkg.Path(), pkg.Path()))
3229 }
3230 var v Call
3231 v.Call.Value = prereq.init
3232 v.Call.pos = fn.pos
3233 v.setType(types.NewTuple())
3234 fn.emit(&v)
3235 }
3236 }
3237 3238 // Initialize package-level vars in correct order.
3239 if len(p.info.InitOrder) > 0 && len(p.files) == 0 {
3240 panic("no source files provided for package. cannot initialize globals")
3241 }
3242 3243 for _, varinit := range p.info.InitOrder {
3244 if fn.Prog.mode&LogSource != 0 {
3245 fmt.Fprintf(os.Stderr, "build global initializer %v @ %s\n",
3246 varinit.Lhs, p.Prog.Fset.Position(varinit.Rhs.Pos()))
3247 }
3248 // Initializers for global vars are evaluated in dependency
3249 // order, but may come from arbitrary files of the package
3250 // with different versions, so we transiently update
3251 // fn.goversion for each one. (Since init is a synthetic
3252 // function it has no syntax of its own that needs a version.)
3253 fn.goversion = p.initVersion[varinit.Rhs]
3254 if len(varinit.Lhs) == 1 {
3255 // 1:1 initialization: var x, y = a(), b()
3256 var lval lvalue
3257 if v := varinit.Lhs[0]; v.Name() != "_" {
3258 lval = &address{addr: p.objects[v].(*Global), pos: v.Pos()}
3259 } else {
3260 lval = blank{}
3261 }
3262 b.assign(fn, lval, varinit.Rhs, true, nil)
3263 } else {
3264 // n:1 initialization: var x, y := f()
3265 tuple := b.exprN(fn, varinit.Rhs)
3266 for i, v := range varinit.Lhs {
3267 if v.Name() == "_" {
3268 continue
3269 }
3270 emitStore(fn, p.objects[v].(*Global), emitExtract(fn, tuple, i), v.Pos())
3271 }
3272 }
3273 }
3274 3275 // The rest of the init function is synthetic:
3276 // no syntax, info, goversion.
3277 fn.info = nil
3278 fn.goversion = ""
3279 3280 // Call all of the declared init() functions in source order.
3281 for _, file := range p.files {
3282 for _, decl := range file.Decls {
3283 if decl, ok := decl.(*ast.FuncDecl); ok {
3284 id := decl.Name
3285 if !isBlankIdent(id) && id.Name == "init" && decl.Recv == nil {
3286 declaredInit := p.objects[p.info.Defs[id]].(*Function)
3287 var v Call
3288 v.Call.Value = declaredInit
3289 v.setType(types.NewTuple())
3290 p.init.emit(&v)
3291 }
3292 }
3293 }
3294 }
3295 3296 // Finish up init().
3297 if p.Prog.mode&BareInits == 0 {
3298 emitJump(fn, done)
3299 fn.currentBlock = done
3300 }
3301 fn.emit(new(Return))
3302 fn.finishBody()
3303 }
3304