closure.go 14.8 KB
Newer Older
1 2 3 4 5 6 7
// Copyright 2009 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

package gc

import (
8
	"cmd/compile/internal/syntax"
9
	"cmd/compile/internal/types"
10 11 12
	"fmt"
)

13
func (p *noder) funcLit(expr *syntax.FuncLit) *Node {
14
	xtype := p.typeExpr(expr.Type)
15 16
	ntype := p.typeExpr(expr.Type)

17 18
	xfunc := p.nod(expr, ODCLFUNC, nil, nil)
	xfunc.Func.SetIsHiddenClosure(Curfn != nil)
19
	xfunc.Func.Nname = p.setlineno(expr, newfuncname(nblank.Sym)) // filled in by typecheckclosure
20 21
	xfunc.Func.Nname.Name.Param.Ntype = xtype
	xfunc.Func.Nname.Name.Defn = xfunc
22

23 24
	clo := p.nod(expr, OCLOSURE, nil, nil)
	clo.Func.Ntype = ntype
25

26 27 28
	xfunc.Func.Closure = clo
	clo.Func.Closure = xfunc

29
	p.funcBody(xfunc, expr.Body)
30 31 32 33 34

	// closure-specific variables are hanging off the
	// ordinary ones in the symbol table; see oldname.
	// unhook them.
	// make the list of pointers for the closure call.
35
	for _, v := range xfunc.Func.Cvars.Slice() {
36 37 38
		// Unlink from v1; see comment in syntax.go type Param for these fields.
		v1 := v.Name.Defn
		v1.Name.Param.Innermost = v.Name.Param.Outer
39

40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68
		// If the closure usage of v is not dense,
		// we need to make it dense; now that we're out
		// of the function in which v appeared,
		// look up v.Sym in the enclosing function
		// and keep it around for use in the compiled code.
		//
		// That is, suppose we just finished parsing the innermost
		// closure f4 in this code:
		//
		//	func f() {
		//		v := 1
		//		func() { // f2
		//			use(v)
		//			func() { // f3
		//				func() { // f4
		//					use(v)
		//				}()
		//			}()
		//		}()
		//	}
		//
		// At this point v.Outer is f2's v; there is no f3's v.
		// To construct the closure f4 from within f3,
		// we need to use f3's v and in this case we need to create f3's v.
		// We are now in the context of f3, so calling oldname(v.Sym)
		// obtains f3's v, creating it if necessary (as it is in the example).
		//
		// capturevars will decide whether to use v directly or &v.
		v.Name.Param.Outer = oldname(v.Sym)
69 70
	}

71
	return clo
72 73
}

74 75 76 77
func typecheckclosure(clo *Node, top int) {
	xfunc := clo.Func.Closure

	for _, ln := range xfunc.Func.Cvars.Slice() {
78
		n := ln.Name.Defn
79 80
		if !n.Name.Captured() {
			n.Name.SetCaptured(true)
81
			if n.Name.Decldepth == 0 {
82
				Fatalf("typecheckclosure: var %S does not have decldepth assigned", n)
83 84 85 86
			}

			// Ignore assignments to the variable in straightline code
			// preceding the first capturing by a closure.
87
			if n.Name.Decldepth == decldepth {
88
				n.SetAssigned(false)
89 90 91 92
			}
		}
	}

93
	xfunc.Func.Nname.Sym = closurename(Curfn)
94
	disableExport(xfunc.Func.Nname.Sym)
95 96
	declare(xfunc.Func.Nname, PFUNC)
	xfunc = typecheck(xfunc, Etop)
97

98 99 100
	clo.Func.Ntype = typecheck(clo.Func.Ntype, Etype)
	clo.Type = clo.Func.Ntype.Type
	clo.Func.Top = top
101 102 103 104 105

	// Type check the body now, but only if we're inside a function.
	// At top level (in a variable initialization: curfn==nil) we're not
	// ready to type check code yet; we'll check it later, because the
	// underlying closure function we create is added to xtop.
106 107 108
	if Curfn != nil && clo.Type != nil {
		oldfn := Curfn
		Curfn = xfunc
109
		olddd := decldepth
110
		decldepth = 1
111
		typecheckslice(xfunc.Nbody.Slice(), Etop)
112 113 114 115
		decldepth = olddd
		Curfn = oldfn
	}

116
	xtop = append(xtop, xfunc)
117 118
}

119 120
// globClosgen is like Func.Closgen, but for the global scope.
var globClosgen int
121

122 123 124 125 126 127
// closurename generates a new unique name for a closure within
// outerfunc.
func closurename(outerfunc *Node) *types.Sym {
	outer := "glob."
	prefix := "func"
	gen := &globClosgen
128

129 130 131
	if outerfunc != nil {
		if outerfunc.Func.Closure != nil {
			prefix = ""
132
		}
133

134
		outer = outerfunc.funcname()
135

136 137 138
		// There may be multiple functions named "_". In those
		// cases, we can't use their individual Closgens as it
		// would lead to name clashes.
139
		if !outerfunc.Func.Nname.isBlank() {
140 141
			gen = &outerfunc.Func.Closgen
		}
142 143
	}

144 145
	*gen++
	return lookup(fmt.Sprintf("%s.%s%d", outer, prefix, *gen))
146 147
}

148 149 150
// capturevarscomplete is set to true when the capturevars phase is done.
var capturevarscomplete bool

151 152 153 154 155 156
// capturevars is called in a separate phase after all typechecking is done.
// It decides whether each variable captured by a closure should be captured
// by value or by reference.
// We use value capturing for values <= 128 bytes that are never reassigned
// after capturing (effectively constant).
func capturevars(xfunc *Node) {
157
	lno := lineno
158
	lineno = xfunc.Pos
159

160 161 162 163
	clo := xfunc.Func.Closure
	cvars := xfunc.Func.Cvars.Slice()
	out := cvars[:0]
	for _, v := range cvars {
164
		if v.Type == nil {
165 166 167 168 169 170
			// If v.Type is nil, it means v looked like it
			// was going to be used in the closure, but
			// isn't. This happens in struct literals like
			// s{f: x} where we can't distinguish whether
			// f is a field identifier or expression until
			// resolving s.
171 172
			continue
		}
173
		out = append(out, v)
174 175 176 177 178

		// type check the & of closed variables outside the closure,
		// so that the outer frame also grabs them and knows they escape.
		dowidth(v.Type)

179 180
		outer := v.Name.Param.Outer
		outermost := v.Name.Defn
181 182

		// out parameters will be assigned to implicitly upon return.
183
		if outer.Class() != PPARAMOUT && !outermost.Addrtaken() && !outermost.Assigned() && v.Type.Width <= 128 {
184
			v.Name.SetByval(true)
185
		} else {
186
			outermost.SetAddrtaken(true)
187
			outer = nod(OADDR, outer, nil)
188 189 190
		}

		if Debug['m'] > 1 {
191
			var name *types.Sym
192 193
			if v.Name.Curfn != nil && v.Name.Curfn.Func.Nname != nil {
				name = v.Name.Curfn.Func.Nname.Sym
194
			}
195
			how := "ref"
196
			if v.Name.Byval() {
197 198
				how = "value"
			}
199
			Warnl(v.Pos, "%v capturing by %s: %v (addr=%v assign=%v width=%d)", name, how, v.Sym, outermost.Addrtaken(), outermost.Assigned(), int32(v.Type.Width))
200 201
		}

202
		outer = typecheck(outer, Erv)
203
		clo.Func.Enter.Append(outer)
204 205
	}

206
	xfunc.Func.Cvars.Set(out)
207
	lineno = lno
208 209 210 211 212
}

// transformclosure is called in a separate phase after escape analysis.
// It transform closure bodies to properly reference captured variables.
func transformclosure(xfunc *Node) {
213
	lno := lineno
214
	lineno = xfunc.Pos
215
	clo := xfunc.Func.Closure
216

217
	if clo.Func.Top&Ecall != 0 {
218 219 220 221 222 223 224 225 226 227
		// If the closure is directly called, we transform it to a plain function call
		// with variables passed as args. This avoids allocation of a closure object.
		// Here we do only a part of the transformation. Walk of OCALLFUNC(OCLOSURE)
		// will complete the transformation later.
		// For illustration, the following closure:
		//	func(a int) {
		//		println(byval)
		//		byref++
		//	}(42)
		// becomes:
228
		//	func(byval int, &byref *int, a int) {
229 230
		//		println(byval)
		//		(*&byref)++
231
		//	}(byval, &byref, 42)
232 233

		// f is ONAME of the actual function.
234
		f := xfunc.Func.Nname
235

236
		// We are going to insert captured variables before input args.
237
		var params []*types.Field
238
		var decls []*Node
239 240
		for _, v := range xfunc.Func.Cvars.Slice() {
			if !v.Name.Byval() {
241 242
				// If v of type T is captured by reference,
				// we introduce function param &v *T
243
				// and v remains PAUTOHEAP with &v heapaddr
244
				// (accesses will implicitly deref &v).
245
				addr := newname(lookup("&" + v.Sym.Name))
246
				addr.Type = types.NewPtr(v.Type)
247
				v.Name.Param.Heapaddr = addr
248
				v = addr
249 250
			}

251 252
			v.SetClass(PPARAM)
			decls = append(decls, v)
253

254 255 256 257
			fld := types.NewField()
			fld.Nname = asTypesNode(v)
			fld.Type = v.Type
			fld.Sym = v.Sym
258 259
			params = append(params, fld)
		}
260

261 262 263 264
		if len(params) > 0 {
			// Prepend params and decls.
			f.Type.Params().SetFields(append(params, f.Type.Params().FieldSlice()...))
			xfunc.Func.Dcl = append(decls, xfunc.Func.Dcl...)
265 266 267 268 269 270
		}

		dowidth(f.Type)
		xfunc.Type = f.Type // update type of ODCLFUNC
	} else {
		// The closure is not called, so it is going to stay as closure.
271
		var body []*Node
272
		offset := int64(Widthptr)
273
		for _, v := range xfunc.Func.Cvars.Slice() {
274
			// cv refers to the field inside of closure OSTRUCTLIT.
275
			cv := nod(OCLOSUREVAR, nil, nil)
276 277

			cv.Type = v.Type
278
			if !v.Name.Byval() {
279
				cv.Type = types.NewPtr(v.Type)
280 281 282 283 284
			}
			offset = Rnd(offset, int64(cv.Type.Align))
			cv.Xoffset = offset
			offset += cv.Type.Width

285
			if v.Name.Byval() && v.Type.Width <= int64(2*Widthptr) {
286
				// If it is a small variable captured by value, downgrade it to PAUTO.
287
				v.SetClass(PAUTO)
288
				xfunc.Func.Dcl = append(xfunc.Func.Dcl, v)
289
				body = append(body, nod(OAS, v, cv))
290 291 292
			} else {
				// Declare variable holding addresses taken from closure
				// and initialize in entry prologue.
293
				addr := newname(lookup("&" + v.Sym.Name))
294
				addr.Type = types.NewPtr(v.Type)
295
				addr.SetClass(PAUTO)
296
				addr.Name.SetUsed(true)
297
				addr.Name.Curfn = xfunc
298
				xfunc.Func.Dcl = append(xfunc.Func.Dcl, addr)
299
				v.Name.Param.Heapaddr = addr
300
				if v.Name.Byval() {
301
					cv = nod(OADDR, cv, nil)
302
				}
303
				body = append(body, nod(OAS, addr, cv))
304 305 306
			}
		}

307 308 309
		if len(body) > 0 {
			typecheckslice(body, Etop)
			xfunc.Func.Enter.Set(body)
310
			xfunc.Func.SetNeedctxt(true)
311
		}
312 313
	}

314
	lineno = lno
315 316
}

317 318 319 320 321
// hasemptycvars returns true iff closure clo has an
// empty list of captured vars.
func hasemptycvars(clo *Node) bool {
	xfunc := clo.Func.Closure
	return xfunc.Func.Cvars.Len() == 0
322 323 324 325
}

// closuredebugruntimecheck applies boilerplate checks for debug flags
// and compiling runtime
326
func closuredebugruntimecheck(clo *Node) {
327
	if Debug_closure > 0 {
328 329 330
		xfunc := clo.Func.Closure
		if clo.Esc == EscHeap {
			Warnl(clo.Pos, "heap closure, captured vars = %v", xfunc.Func.Cvars)
331
		} else {
332
			Warnl(clo.Pos, "stack closure, captured vars = %v", xfunc.Func.Cvars)
333 334
		}
	}
335 336
	if compiling_runtime && clo.Esc == EscHeap {
		yyerrorl(clo.Pos, "heap-allocated closure, not allowed in runtime.")
337 338 339
	}
}

340 341 342 343
// closureType returns the struct type used to hold all the information
// needed in the closure for clo (clo must be a OCLOSURE node).
// The address of a variable of the returned type can be cast to a func.
func closureType(clo *Node) *types.Type {
344 345 346 347 348
	// Create closure in the form of a composite literal.
	// supposing the closure captures an int i and a string s
	// and has one float64 argument and no results,
	// the generated code looks like:
	//
349
	//	clos = &struct{.F uintptr; i *int; s *string}{func.1, &i, &s}
350 351 352 353 354 355 356
	//
	// The use of the struct provides type information to the garbage
	// collector so that it can walk the closure. We could use (in this case)
	// [3]unsafe.Pointer instead, but that would leave the gc in the dark.
	// The information appears in the binary in the form of type descriptors;
	// the struct is unnamed so that closures in multiple packages with the
	// same struct type can share the descriptor.
357 358 359
	fields := []*Node{
		namedfield(".F", types.Types[TUINTPTR]),
	}
360
	for _, v := range clo.Func.Closure.Func.Cvars.Slice() {
361
		typ := v.Type
362
		if !v.Name.Byval() {
363
			typ = types.NewPtr(typ)
364
		}
365
		fields = append(fields, symfield(v.Sym, typ))
366
	}
367 368
	typ := tostruct(fields)
	typ.SetNoalg(true)
369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384
	return typ
}

func walkclosure(clo *Node, init *Nodes) *Node {
	xfunc := clo.Func.Closure

	// If no closure vars, don't bother wrapping.
	if hasemptycvars(clo) {
		if Debug_closure > 0 {
			Warnl(clo.Pos, "closure converted to global")
		}
		return xfunc.Func.Nname
	}
	closuredebugruntimecheck(clo)

	typ := closureType(clo)
385

386
	clos := nod(OCOMPLIT, nil, nod(OIND, typenod(typ), nil))
387
	clos.Esc = clo.Esc
388
	clos.Right.SetImplicit(true)
389
	clos.List.Set(append([]*Node{nod(OCFUNC, xfunc.Func.Nname, nil)}, clo.Func.Enter.Slice()...))
390 391

	// Force type conversion from *struct to the func type.
392
	clos = convnop(clos, clo.Type)
393 394 395

	// typecheck will insert a PTRLIT node under CONVNOP,
	// tag it with escape analysis result.
396
	clos.Left.Esc = clo.Esc
397 398

	// non-escaping temp to use, if any.
399
	if x := prealloc[clo]; x != nil {
400 401 402
		if !eqtype(typ, x.Type) {
			panic("closure type does not match order's assigned type")
		}
Russ Cox's avatar
Russ Cox committed
403
		clos.Left.Right = x
404
		delete(prealloc, clo)
405 406
	}

407
	return walkexpr(clos, init)
408 409
}

410
func typecheckpartialcall(fn *Node, sym *types.Sym) {
411
	switch fn.Op {
412
	case ODOTINTER, ODOTMETH:
413 414 415
		break

	default:
416
		Fatalf("invalid typecheckpartialcall")
417 418 419
	}

	// Create top-level function.
420 421
	xfunc := makepartialcall(fn, fn.Type, sym)
	fn.Func = xfunc.Func
422
	fn.Right = newname(sym)
423
	fn.Op = OCALLPART
424
	fn.Type = xfunc.Type
425 426
}

427
func makepartialcall(fn *Node, t0 *types.Type, meth *types.Sym) *Node {
428
	rcvrtype := fn.Left.Type
429
	sym := methodSymSuffix(rcvrtype, meth, "-fm")
430

431
	if sym.Uniq() {
432
		return asNode(sym.Def)
433
	}
434
	sym.SetUniq(true)
435

436
	savecurfn := Curfn
437 438
	Curfn = nil

439 440 441
	tfn := nod(OTFUNC, nil, nil)
	tfn.List.Set(structargs(t0.Params(), true))
	tfn.Rlist.Set(structargs(t0.Results(), false))
442

443 444
	disableExport(sym)
	xfunc := dclfunc(sym, tfn)
445
	xfunc.Func.SetDupok(true)
446
	xfunc.Func.SetNeedctxt(true)
447

448 449
	tfn.Type.SetPkg(t0.Pkg())

450 451
	// Declare and initialize variable holding receiver.

452
	cv := nod(OCLOSUREVAR, nil, nil)
453
	cv.Type = rcvrtype
454 455
	cv.Xoffset = Rnd(int64(Widthptr), int64(cv.Type.Align))

456 457
	ptr := newname(lookup(".this"))
	declare(ptr, PAUTO)
458
	ptr.Name.SetUsed(true)
459
	var body []*Node
460
	if rcvrtype.IsPtr() || rcvrtype.IsInterface() {
461
		ptr.Type = rcvrtype
462
		body = append(body, nod(OAS, ptr, cv))
463
	} else {
464
		ptr.Type = types.NewPtr(rcvrtype)
465
		body = append(body, nod(OAS, ptr, nod(OADDR, cv, nil)))
466 467
	}

468
	call := nod(OCALL, nodSym(OXDOT, ptr, meth), nil)
469 470 471 472 473 474
	call.List.Set(paramNnames(tfn.Type))
	call.SetIsddd(tfn.Type.IsVariadic())
	if t0.NumResults() != 0 {
		n := nod(ORETURN, nil, nil)
		n.List.Set1(call)
		call = n
475
	}
476
	body = append(body, call)
477

478
	xfunc.Nbody.Set(body)
479
	funcbody()
480

481
	xfunc = typecheck(xfunc, Etop)
482
	sym.Def = asTypesNode(xfunc)
483
	xtop = append(xtop, xfunc)
484 485 486 487 488
	Curfn = savecurfn

	return xfunc
}

489 490 491 492 493 494 495 496 497 498 499 500
// partialCallType returns the struct type used to hold all the information
// needed in the closure for n (n must be a OCALLPART node).
// The address of a variable of the returned type can be cast to a func.
func partialCallType(n *Node) *types.Type {
	t := tostruct([]*Node{
		namedfield("F", types.Types[TUINTPTR]),
		namedfield("R", n.Left.Type),
	})
	t.SetNoalg(true)
	return t
}

501
func walkpartialcall(n *Node, init *Nodes) *Node {
502 503 504 505 506 507 508
	// Create closure in the form of a composite literal.
	// For x.M with receiver (x) type T, the generated code looks like:
	//
	//	clos = &struct{F uintptr; R T}{M.T·f, x}
	//
	// Like walkclosure above.

509
	if n.Left.Type.IsInterface() {
510 511 512 513 514 515 516
		// Trigger panic for method on nil interface now.
		// Otherwise it happens in the wrapper and is confusing.
		n.Left = cheapexpr(n.Left, init)

		checknil(n.Left, init)
	}

517
	typ := partialCallType(n)
518

519
	clos := nod(OCOMPLIT, nil, nod(OIND, typenod(typ), nil))
520
	clos.Esc = n.Esc
521
	clos.Right.SetImplicit(true)
522
	clos.List.Set2(nod(OCFUNC, n.Func.Nname, nil), n.Left)
523 524

	// Force type conversion from *struct to the func type.
525
	clos = convnop(clos, n.Type)
526

527 528
	// The typecheck inside convnop will insert a PTRLIT node under CONVNOP.
	// Tag it with escape analysis result.
529 530 531
	clos.Left.Esc = n.Esc

	// non-escaping temp to use, if any.
Russ Cox's avatar
Russ Cox committed
532
	if x := prealloc[n]; x != nil {
533 534 535
		if !eqtype(typ, x.Type) {
			panic("partial call type does not match order's assigned type")
		}
Russ Cox's avatar
Russ Cox committed
536 537
		clos.Left.Right = x
		delete(prealloc, n)
538 539
	}

540
	return walkexpr(clos, init)
541
}