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