...

# Text file src/cmd/gc/esc.c

```     1	// Copyright 2011 The Go Authors. All rights reserved.
2	// Use of this source code is governed by a BSD-style
4
5	// Escape analysis.
6
7	#include <u.h>
8	#include <libc.h>
9	#include "go.h"
10
11	// Run analysis on minimal sets of mutually recursive functions
12	// or single non-recursive functions, bottom up.
13	//
14	// Finding these sets is finding strongly connected components
15	// in the static call graph.  The algorithm for doing that is taken
16	// from Sedgewick, Algorithms, Second Edition, p. 482, with two
18	//
19	// First, a hidden closure function (n->curfn != N) cannot be the
20	// root of a connected component. Refusing to use it as a root
21	// forces it into the component of the function in which it appears.
22	// The analysis assumes that closures and the functions in which they
23	// appear are analyzed together, so that the aliasing between their
24	// variables can be modeled more precisely.
25	//
26	// Second, each function becomes two virtual nodes in the graph,
27	// with numbers n and n+1. We record the function's node number as n
28	// but search from node n+1. If the search tells us that the component
29	// number (min) is n+1, we know that this is a trivial component: one function
30	// plus its closures. If the search tells us that the component number is
31	// n, then there was a path from node n+1 back to node n, meaning that
32	// the function set is mutually recursive. The escape analysis can be
33	// more precise when analyzing a single non-recursive function than
34	// when analyzing a set of mutually recursive functions.
35
36	static NodeList *stack;
37	static uint32 visitgen;
38	static uint32 visit(Node*);
39	static uint32 visitcode(Node*, uint32);
40	static uint32 visitcodelist(NodeList*, uint32);
41
42	static void analyze(NodeList*, int);
43
44	enum
45	{
46		EscFuncUnknown = 0,
47		EscFuncPlanned,
48		EscFuncStarted,
49		EscFuncTagged,
50	};
51
52	void
53	escapes(NodeList *all)
54	{
55		NodeList *l;
56
57		for(l=all; l; l=l->next)
58			l->n->walkgen = 0;
59
60		visitgen = 0;
61		for(l=all; l; l=l->next)
62			if(l->n->op == ODCLFUNC && l->n->curfn == N)
63				visit(l->n);
64
65		for(l=all; l; l=l->next)
66			l->n->walkgen = 0;
67	}
68
69	static uint32
70	visit(Node *n)
71	{
72		uint32 min, recursive;
73		NodeList *l, *block;
74
75		if(n->walkgen > 0) {
77			return n->walkgen;
78		}
79
80		visitgen++;
81		n->walkgen = visitgen;
82		visitgen++;
83		min = visitgen;
84
85		l = mal(sizeof *l);
86		l->next = stack;
87		l->n = n;
88		stack = l;
89		min = visitcodelist(n->nbody, min);
90		if((min == n->walkgen || min == n->walkgen+1) && n->curfn == N) {
91			// This node is the root of a strongly connected component.
92
93			// The original min passed to visitcodelist was n->walkgen+1.
94			// If visitcodelist found its way back to n->walkgen, then this
95			// block is a set of mutually recursive functions.
96			// Otherwise it's just a lone function that does not recurse.
97			recursive = min == n->walkgen;
98
99			// Remove connected component from stack.
100			// Mark walkgen so that future visits return a large number
101			// so as not to affect the caller's min.
102			block = stack;
103			for(l=stack; l->n != n; l=l->next)
104				l->n->walkgen = (uint32)~0U;
105			n->walkgen = (uint32)~0U;
106			stack = l->next;
107			l->next = nil;
108
109			// Run escape analysis on this set of functions.
110			analyze(block, recursive);
111		}
112
113		return min;
114	}
115
116	static uint32
117	visitcodelist(NodeList *l, uint32 min)
118	{
119		for(; l; l=l->next)
120			min = visitcode(l->n, min);
121		return min;
122	}
123
124	static uint32
125	visitcode(Node *n, uint32 min)
126	{
127		Node *fn;
128		uint32 m;
129
130		if(n == N)
131			return min;
132
133		min = visitcodelist(n->ninit, min);
134		min = visitcode(n->left, min);
135		min = visitcode(n->right, min);
136		min = visitcodelist(n->list, min);
137		min = visitcode(n->ntest, min);
138		min = visitcode(n->nincr, min);
139		min = visitcodelist(n->nbody, min);
140		min = visitcodelist(n->nelse, min);
141		min = visitcodelist(n->rlist, min);
142
143		if(n->op == OCALLFUNC || n->op == OCALLMETH) {
144			fn = n->left;
145			if(n->op == OCALLMETH)
146				fn = n->left->right->sym->def;
147			if(fn && fn->op == ONAME && fn->class == PFUNC && fn->defn)
148				if((m = visit(fn->defn)) < min)
149					min = m;
150		}
151
152		if(n->op == OCLOSURE)
153			if((m = visit(n->closure)) < min)
154				min = m;
155
156		return min;
157	}
158
159	// An escape analysis pass for a set of functions.
160	//
161	// First escfunc, esc and escassign recurse over the ast of each
162	// function to dig out flow(dst,src) edges between any
163	// pointer-containing nodes and store them in dst->escflowsrc.  For
164	// variables assigned to a variable in an outer scope or used as a
165	// return value, they store a flow(theSink, src) edge to a fake node
166	// 'the Sink'.  For variables referenced in closures, an edge
167	// flow(closure, &var) is recorded and the flow of a closure itself to
168	// an outer scope is tracked the same way as other variables.
169	//
170	// Then escflood walks the graph starting at theSink and tags all
171	// variables of it can reach an & node as escaping and all function
172	// parameters it can reach as leaking.
173	//
174	// If a value's address is taken but the address does not escape,
175	// then the value can stay on the stack.  If the value new(T) does
176	// not escape, then new(T) can be rewritten into a stack allocation.
177	// The same is true of slice literals.
178	//
179	// If optimizations are disabled (-N), this code is not used.
181	// is taken without being immediately dereferenced
182	// needs to be moved to the heap, and new(T) and slice
183	// literals are always real allocations.
184
185	typedef struct EscState EscState;
186
187	static void escfunc(EscState*, Node *func);
188	static void esclist(EscState*, NodeList *l, Node *up);
189	static void esc(EscState*, Node *n, Node *up);
190	static void escloopdepthlist(EscState*, NodeList *l);
191	static void escloopdepth(EscState*, Node *n);
192	static void escassign(EscState*, Node *dst, Node *src);
193	static void esccall(EscState*, Node*, Node *up);
194	static void escflows(EscState*, Node *dst, Node *src);
195	static void escflood(EscState*, Node *dst);
196	static void escwalk(EscState*, int level, Node *dst, Node *src);
197	static void esctag(EscState*, Node *func);
198
199	struct EscState {
200		// Fake node that all
201		//   - return values and output variables
202		//   - parameters on imported functions not marked 'safe'
203		//   - assignments to global variables
204		// flow to.
205		Node	theSink;
206
207		// If an analyzed function is recorded to return
208		// pieces obtained via indirection from a parameter,
209		// and later there is a call f(x) to that function,
210		// we create a link funcParam <- x to record that fact.
211		// The funcParam node is handled specially in escflood.
212		Node	funcParam;
213
214		NodeList*	dsts;		// all dst nodes
215		int	loopdepth;	// for detecting nested loop scopes
216		int	pdepth;		// for debug printing in recursions.
217		int	dstcount, edgecount;	// diagnostic
218		NodeList*	noesc;	// list of possible non-escaping nodes, for printing
219		int	recursive;	// recursive function or group of mutually recursive functions.
220	};
221
222	static Strlit *tags[16];
223
224	static Strlit*
226	{
227		Strlit *s;
228		char buf[40];
229
231		case EscNone:
232		case EscReturn:
233			break;
234		default:
235			fatal("escape mktag");
236		}
237
239
242
243		snprint(buf, sizeof buf, "esc:0x%x", mask);
244		s = strlit(buf);
247		return s;
248	}
249
250	static int
251	parsetag(Strlit *note)
252	{
253		int em;
254
255		if(note == nil)
256			return EscUnknown;
257		if(strncmp(note->s, "esc:", 4) != 0)
258			return EscUnknown;
259		em = atoi(note->s + 4);
260		if (em == 0)
261			return EscNone;
262		return EscReturn | (em << EscBits);
263	}
264
265	static void
266	analyze(NodeList *all, int recursive)
267	{
268		NodeList *l;
269		EscState es, *e;
270
271		memset(&es, 0, sizeof es);
272		e = &es;
273		e->theSink.op = ONAME;
274		e->theSink.orig = &e->theSink;
275		e->theSink.class = PEXTERN;
276		e->theSink.sym = lookup(".sink");
277		e->theSink.escloopdepth = -1;
278		e->recursive = recursive;
279
280		e->funcParam.op = ONAME;
281		e->funcParam.orig = &e->funcParam;
282		e->funcParam.class = PAUTO;
283		e->funcParam.sym = lookup(".param");
284		e->funcParam.escloopdepth = 10000000;
285
286		for(l=all; l; l=l->next)
287			if(l->n->op == ODCLFUNC)
288				l->n->esc = EscFuncPlanned;
289
290		// flow-analyze functions
291		for(l=all; l; l=l->next)
292			if(l->n->op == ODCLFUNC)
293				escfunc(e, l->n);
294
295		// print("escapes: %d e->dsts, %d edges\n", e->dstcount, e->edgecount);
296
297		// visit the upstream of each dst, mark address nodes with
298		// addrescapes, mark parameters unsafe
299		for(l = e->dsts; l; l=l->next)
300			escflood(e, l->n);
301
302		// for all top level functions, tag the typenodes corresponding to the param nodes
303		for(l=all; l; l=l->next)
304			if(l->n->op == ODCLFUNC)
305				esctag(e, l->n);
306
307		if(debug['m']) {
308			for(l=e->noesc; l; l=l->next)
309				if(l->n->esc == EscNone)
310					warnl(l->n->lineno, "%S %hN does not escape",
311						(l->n->curfn && l->n->curfn->nname) ? l->n->curfn->nname->sym : S,
312						l->n);
313		}
314	}
315
316
317	static void
318	escfunc(EscState *e, Node *func)
319	{
320		Node *savefn;
321		NodeList *ll;
322		int saveld;
323
324	//	print("escfunc %N %s\n", func->nname, e->recursive?"(recursive)":"");
325
326		if(func->esc != 1)
327			fatal("repeat escfunc %N", func->nname);
328		func->esc = EscFuncStarted;
329
330		saveld = e->loopdepth;
331		e->loopdepth = 1;
332		savefn = curfn;
333		curfn = func;
334
335		for(ll=curfn->dcl; ll; ll=ll->next) {
336			if(ll->n->op != ONAME)
337				continue;
338			switch (ll->n->class) {
339			case PPARAMOUT:
340				// out params are in a loopdepth between the sink and all local variables
341				ll->n->escloopdepth = 0;
342				break;
343			case PPARAM:
344				ll->n->escloopdepth = 1;
345				if(ll->n->type && !haspointers(ll->n->type))
346					break;
347				if(curfn->nbody == nil && !curfn->noescape)
348					ll->n->esc = EscHeap;
349				else
350					ll->n->esc = EscNone;	// prime for escflood later
351				e->noesc = list(e->noesc, ll->n);
352				break;
353			}
354		}
355
356		// in a mutually recursive group we lose track of the return values
357		if(e->recursive)
358			for(ll=curfn->dcl; ll; ll=ll->next)
359				if(ll->n->op == ONAME && ll->n->class == PPARAMOUT)
360					escflows(e, &e->theSink, ll->n);
361
362		escloopdepthlist(e, curfn->nbody);
363		esclist(e, curfn->nbody, curfn);
364		curfn = savefn;
365		e->loopdepth = saveld;
366	}
367
368	// Mark labels that have no backjumps to them as not increasing e->loopdepth.
369	// Walk hasn't generated (goto|label)->left->sym->label yet, so we'll cheat
370	// and set it to one of the following two.  Then in esc we'll clear it again.
371	static Label looping;
372	static Label nonlooping;
373
374	static void
375	escloopdepthlist(EscState *e, NodeList *l)
376	{
377		for(; l; l=l->next)
378			escloopdepth(e, l->n);
379	}
380
381	static void
382	escloopdepth(EscState *e, Node *n)
383	{
384		if(n == N)
385			return;
386
387		escloopdepthlist(e, n->ninit);
388
389		switch(n->op) {
390		case OLABEL:
391			if(!n->left || !n->left->sym)
392				fatal("esc:label without label: %+N", n);
394			// after escape analysis. in the future, maybe pull label & goto analysis out of walk and put before esc
395			// if(n->left->sym->label != nil)
396			//	fatal("escape analysis messed up analyzing label: %+N", n);
397			n->left->sym->label = &nonlooping;
398			break;
399		case OGOTO:
400			if(!n->left || !n->left->sym)
401				fatal("esc:goto without label: %+N", n);
402			// If we come past one that's uninitialized, this must be a (harmless) forward jump
403			// but if it's set to nonlooping the label must have preceded this goto.
404			if(n->left->sym->label == &nonlooping)
405				n->left->sym->label = &looping;
406			break;
407		}
408
409		escloopdepth(e, n->left);
410		escloopdepth(e, n->right);
411		escloopdepthlist(e, n->list);
412		escloopdepth(e, n->ntest);
413		escloopdepth(e, n->nincr);
414		escloopdepthlist(e, n->nbody);
415		escloopdepthlist(e, n->nelse);
416		escloopdepthlist(e, n->rlist);
417
418	}
419
420	static void
421	esclist(EscState *e, NodeList *l, Node *up)
422	{
423		for(; l; l=l->next)
424			esc(e, l->n, up);
425	}
426
427	static void
428	esc(EscState *e, Node *n, Node *up)
429	{
430		int lno;
431		NodeList *ll, *lr;
432		Node *a;
433
434		if(n == N)
435			return;
436
437		lno = setlineno(n);
438
439		// ninit logically runs at a different loopdepth than the rest of the for loop.
440		esclist(e, n->ninit, n);
441
442		if(n->op == OFOR || n->op == ORANGE)
443			e->loopdepth++;
444
445		// type switch variables have no ODCL.
446		// process type switch as declaration.
447		// must happen before processing of switch body,
448		// so before recursion.
449		if(n->op == OSWITCH && n->ntest && n->ntest->op == OTYPESW) {
450			for(ll=n->list; ll; ll=ll->next) {  // cases
451				// ll->n->nname is the variable per case
452				if(ll->n->nname)
453					ll->n->nname->escloopdepth = e->loopdepth;
454			}
455		}
456
457		esc(e, n->left, n);
458		esc(e, n->right, n);
459		esc(e, n->ntest, n);
460		esc(e, n->nincr, n);
461		esclist(e, n->nbody, n);
462		esclist(e, n->nelse, n);
463		esclist(e, n->list, n);
464		esclist(e, n->rlist, n);
465
466		if(n->op == OFOR || n->op == ORANGE)
467			e->loopdepth--;
468
469		if(debug['m'] > 1)
470			print("%L:[%d] %S esc: %N\n", lineno, e->loopdepth,
471			      (curfn && curfn->nname) ? curfn->nname->sym : S, n);
472
473		switch(n->op) {
474		case ODCL:
475			// Record loop depth at declaration.
476			if(n->left)
477				n->left->escloopdepth = e->loopdepth;
478			break;
479
480		case OLABEL:
481			if(n->left->sym->label == &nonlooping) {
482				if(debug['m'] > 1)
483					print("%L:%N non-looping label\n", lineno, n);
484			} else if(n->left->sym->label == &looping) {
485				if(debug['m'] > 1)
486					print("%L: %N looping label\n", lineno, n);
487				e->loopdepth++;
488			}
489			// See case OLABEL in escloopdepth above
490			// else if(n->left->sym->label == nil)
491			//	fatal("escape analysis missed or messed up a label: %+N", n);
492
493			n->left->sym->label = nil;
494			break;
495
496		case ORANGE:
497			// Everything but fixed array is a dereference.
498			if(isfixedarray(n->type) && n->list && n->list->next)
499				escassign(e, n->list->next->n, n->right);
500			break;
501
502		case OSWITCH:
503			if(n->ntest && n->ntest->op == OTYPESW) {
504				for(ll=n->list; ll; ll=ll->next) {  // cases
505					// ntest->right is the argument of the .(type),
506					// ll->n->nname is the variable per case
507					escassign(e, ll->n->nname, n->ntest->right);
508				}
509			}
510			break;
511
512		case OAS:
513		case OASOP:
514			escassign(e, n->left, n->right);
515			break;
516
517		case OAS2:	// x,y = a,b
518			if(count(n->list) == count(n->rlist))
519				for(ll=n->list, lr=n->rlist; ll; ll=ll->next, lr=lr->next)
520					escassign(e, ll->n, lr->n);
521			break;
522
523		case OAS2RECV:		// v, ok = <-ch
524		case OAS2MAPR:		// v, ok = m[k]
525		case OAS2DOTTYPE:	// v, ok = x.(type)
526			escassign(e, n->list->n, n->rlist->n);
527			break;
528
529		case OSEND:		// ch <- x
530			escassign(e, &e->theSink, n->right);
531			break;
532
533		case ODEFER:
534			if(e->loopdepth == 1)  // top level
535				break;
536			// arguments leak out of scope
537			// TODO: leak to a dummy node instead
538			// fallthrough
539		case OPROC:
540			// go f(x) - f and x escape
541			escassign(e, &e->theSink, n->left->left);
542			escassign(e, &e->theSink, n->left->right);  // ODDDARG for call
543			for(ll=n->left->list; ll; ll=ll->next)
544				escassign(e, &e->theSink, ll->n);
545			break;
546
547		case OCALLMETH:
548		case OCALLFUNC:
549		case OCALLINTER:
550			esccall(e, n, up);
551			break;
552
553		case OAS2FUNC:	// x,y = f()
554			// esccall already done on n->rlist->n. tie it's escretval to n->list
555			lr=n->rlist->n->escretval;
556			for(ll=n->list; lr && ll; lr=lr->next, ll=ll->next)
557				escassign(e, ll->n, lr->n);
558			if(lr || ll)
559				fatal("esc oas2func");
560			break;
561
562		case ORETURN:
563			ll=n->list;
564			if(count(n->list) == 1 && curfn->type->outtuple > 1) {
565				// OAS2FUNC in disguise
566				// esccall already done on n->list->n
567				// tie n->list->n->escretval to curfn->dcl PPARAMOUT's
568				ll = n->list->n->escretval;
569			}
570
571			for(lr = curfn->dcl; lr && ll; lr=lr->next) {
572				if (lr->n->op != ONAME || lr->n->class != PPARAMOUT)
573					continue;
574				escassign(e, lr->n, ll->n);
575				ll = ll->next;
576			}
577			if (ll != nil)
578				fatal("esc return list");
579			break;
580
581		case OPANIC:
582			// Argument could leak through recover.
583			escassign(e, &e->theSink, n->left);
584			break;
585
586		case OAPPEND:
587			if(!n->isddd)
588				for(ll=n->list->next; ll; ll=ll->next)
589					escassign(e, &e->theSink, ll->n);  // lose track of assign to dereference
590			break;
591
592		case OCONV:
593		case OCONVNOP:
594		case OCONVIFACE:
595			escassign(e, n, n->left);
596			break;
597
598		case OARRAYLIT:
599			if(isslice(n->type)) {
600				n->esc = EscNone;  // until proven otherwise
601				e->noesc = list(e->noesc, n);
602				n->escloopdepth = e->loopdepth;
603				// Values make it to memory, lose track.
604				for(ll=n->list; ll; ll=ll->next)
605					escassign(e, &e->theSink, ll->n->right);
606			} else {
607				// Link values to array.
608				for(ll=n->list; ll; ll=ll->next)
609					escassign(e, n, ll->n->right);
610			}
611			break;
612
613		case OSTRUCTLIT:
614			// Link values to struct.
615			for(ll=n->list; ll; ll=ll->next)
616				escassign(e, n, ll->n->right);
617			break;
618
619		case OPTRLIT:
620			n->esc = EscNone;  // until proven otherwise
621			e->noesc = list(e->noesc, n);
622			n->escloopdepth = e->loopdepth;
623			// Contents make it to memory, lose track.
624			escassign(e, &e->theSink, n->left);
625			break;
626
627		case OCALLPART:
628			n->esc = EscNone; // until proven otherwise
629			e->noesc = list(e->noesc, n);
630			n->escloopdepth = e->loopdepth;
631			// Contents make it to memory, lose track.
632			escassign(e, &e->theSink, n->left);
633			break;
634
635		case OMAPLIT:
636			n->esc = EscNone;  // until proven otherwise
637			e->noesc = list(e->noesc, n);
638			n->escloopdepth = e->loopdepth;
639			// Keys and values make it to memory, lose track.
640			for(ll=n->list; ll; ll=ll->next) {
641				escassign(e, &e->theSink, ll->n->left);
642				escassign(e, &e->theSink, ll->n->right);
643			}
644			break;
645
646		case OCLOSURE:
648			for(ll=n->cvars; ll; ll=ll->next) {
649				if(ll->n->op == OXXX)  // unnamed out argument; see dcl.c:/^funcargs
650					continue;
651				a = nod(OADDR, ll->n->closure, N);
652				a->lineno = ll->n->lineno;
653				a->escloopdepth = e->loopdepth;
654				typecheck(&a, Erv);
655				escassign(e, n, a);
656			}
657			// fallthrough
658		case OMAKECHAN:
659		case OMAKEMAP:
660		case OMAKESLICE:
661		case ONEW:
662			n->escloopdepth = e->loopdepth;
663			n->esc = EscNone;  // until proven otherwise
664			e->noesc = list(e->noesc, n);
665			break;
666
668			n->esc = EscNone;  // until proven otherwise
669			e->noesc = list(e->noesc, n);
670			// current loop depth is an upper bound on actual loop depth
672			n->escloopdepth = e->loopdepth;
673			// for &x, use loop depth of x if known.
674			// it should always be known, but if not, be conservative
675			// and keep the current loop depth.
676			if(n->left->op == ONAME) {
677				switch(n->left->class) {
678				case PAUTO:
679					if(n->left->escloopdepth != 0)
680						n->escloopdepth = n->left->escloopdepth;
681					break;
682				case PPARAM:
683				case PPARAMOUT:
684					// PPARAM is loop depth 1 always.
685					// PPARAMOUT is loop depth 0 for writes
686					// but considered loop depth 1 for address-of,
687					// so that writing the address of one result
688					// to another (or the same) result makes the
689					// first result move to the heap.
690					n->escloopdepth = 1;
691					break;
692				}
693			}
694			break;
695		}
696
697		lineno = lno;
698	}
699
700	// Assert that expr somehow gets assigned to dst, if non nil.  for
701	// dst==nil, any name node expr still must be marked as being
702	// evaluated in curfn.	For expr==nil, dst must still be examined for
703	// evaluations inside it (e.g *f(x) = y)
704	static void
705	escassign(EscState *e, Node *dst, Node *src)
706	{
707		int lno;
708		NodeList *ll;
709
710		if(isblank(dst) || dst == N || src == N || src->op == ONONAME || src->op == OXXX)
711			return;
712
713		if(debug['m'] > 1)
714			print("%L:[%d] %S escassign: %hN(%hJ) = %hN(%hJ)\n", lineno, e->loopdepth,
715			      (curfn && curfn->nname) ? curfn->nname->sym : S, dst, dst, src, src);
716
717		setlineno(dst);
718
719		// Analyze lhs of assignment.
720		// Replace dst with e->theSink if we can't track it.
721		switch(dst->op) {
722		default:
723			dump("dst", dst);
724			fatal("escassign: unexpected dst");
725
726		case OARRAYLIT:
727		case OCLOSURE:
728		case OCONV:
729		case OCONVIFACE:
730		case OCONVNOP:
731		case OMAPLIT:
732		case OSTRUCTLIT:
733		case OCALLPART:
734			break;
735
736		case ONAME:
737			if(dst->class == PEXTERN)
738				dst = &e->theSink;
739			break;
740		case ODOT:	      // treat "dst.x  = src" as "dst = src"
741			escassign(e, dst->left, src);
742			return;
743		case OINDEX:
744			if(isfixedarray(dst->left->type)) {
745				escassign(e, dst->left, src);
746				return;
747			}
748			dst = &e->theSink;  // lose track of dereference
749			break;
750		case OIND:
751		case ODOTPTR:
752			dst = &e->theSink;  // lose track of dereference
753			break;
754		case OINDEXMAP:
755			// lose track of key and value
756			escassign(e, &e->theSink, dst->right);
757			dst = &e->theSink;
758			break;
759		}
760
761		lno = setlineno(src);
762		e->pdepth++;
763
764		switch(src->op) {
765		case OADDR:	// dst = &x
766		case OIND:	// dst = *x
767		case ODOTPTR:	// dst = (*x).f
768		case ONAME:
769		case OPARAM:
770		case ODDDARG:
771		case OPTRLIT:
772		case OARRAYLIT:
773		case OMAPLIT:
774		case OSTRUCTLIT:
775		case OMAKECHAN:
776		case OMAKEMAP:
777		case OMAKESLICE:
778		case ONEW:
779		case OCLOSURE:
780		case OCALLPART:
781			escflows(e, dst, src);
782			break;
783
784		case OCALLMETH:
785		case OCALLFUNC:
786		case OCALLINTER:
787			// Flowing multiple returns to a single dst happens when
788			// analyzing "go f(g())": here g() flows to sink (issue 4529).
789			for(ll=src->escretval; ll; ll=ll->next)
790				escflows(e, dst, ll->n);
791			break;
792
793		case ODOT:
794			// A non-pointer escaping from a struct does not concern us.
795			if(src->type && !haspointers(src->type))
796				break;
797			// fallthrough
798		case OCONV:
799		case OCONVIFACE:
800		case OCONVNOP:
801		case ODOTMETH:	// treat recv.meth as a value with recv in it, only happens in ODEFER and OPROC
802				// iface.method already leaks iface in esccall, no need to put in extra ODOTINTER edge here
803		case ODOTTYPE:
804		case ODOTTYPE2:
805		case OSLICE:
806		case OSLICE3:
807		case OSLICEARR:
808		case OSLICE3ARR:
809			// Conversions, field access, slice all preserve the input value.
810			escassign(e, dst, src->left);
811			break;
812
813		case OAPPEND:
814			// Append returns first argument.
815			escassign(e, dst, src->list->n);
816			break;
817
818		case OINDEX:
819			// Index of array preserves input value.
820			if(isfixedarray(src->left->type))
821				escassign(e, dst, src->left);
822			break;
823
825		case OSUB:
826		case OOR:
827		case OXOR:
828		case OMUL:
829		case ODIV:
830		case OMOD:
831		case OLSH:
832		case ORSH:
833		case OAND:
834		case OANDNOT:
835		case OPLUS:
836		case OMINUS:
837		case OCOM:
838			// Might be pointer arithmetic, in which case
839			// the operands flow into the result.
840			// TODO(rsc): Decide what the story is here.  This is unsettling.
841			escassign(e, dst, src->left);
842			escassign(e, dst, src->right);
843			break;
844		}
845
846		e->pdepth--;
847		lineno = lno;
848	}
849
850	static int
851	escassignfromtag(EscState *e, Strlit *note, NodeList *dsts, Node *src)
852	{
853		int em, em0;
854
855		em = parsetag(note);
856
857		if(em == EscUnknown) {
858			escassign(e, &e->theSink, src);
859			return em;
860		}
861
862		if(em == EscNone)
863			return em;
864
865		// If content inside parameter (reached via indirection)
866		// escapes back to results, mark as such.
867		if(em & EscContentEscapes)
868			escassign(e, &e->funcParam, src);
869
870		em0 = em;
871		for(em >>= EscReturnBits; em && dsts; em >>= 1, dsts=dsts->next)
872			if(em & 1)
873				escassign(e, dsts->n, src);
874
875		if (em != 0 && dsts == nil)
876			fatal("corrupt esc tag %Z or messed up escretval list\n", note);
877		return em0;
878	}
879
880	// This is a bit messier than fortunate, pulled out of esc's big
881	// switch for clarity.	We either have the paramnodes, which may be
882	// connected to other things through flows or we have the parameter type
883	// nodes, which may be marked "noescape". Navigating the ast is slightly
884	// different for methods vs plain functions and for imported vs
885	// this-package
886	static void
887	esccall(EscState *e, Node *n, Node *up)
888	{
889		NodeList *ll, *lr;
890		Node *a, *fn, *src;
891		Type *t, *fntype;
892		char buf[40];
893		int i;
894
895		fn = N;
896		switch(n->op) {
897		default:
898			fatal("esccall");
899
900		case OCALLFUNC:
901			fn = n->left;
902			fntype = fn->type;
903			break;
904
905		case OCALLMETH:
906			fn = n->left->right->sym->def;
907			if(fn)
908				fntype = fn->type;
909			else
910				fntype = n->left->type;
911			break;
912
913		case OCALLINTER:
914			fntype = n->left->type;
915			break;
916		}
917
918		ll = n->list;
919		if(n->list != nil && n->list->next == nil) {
920			a = n->list->n;
921			if(a->type->etype == TSTRUCT && a->type->funarg) // f(g()).
922				ll = a->escretval;
923		}
924
925		if(fn && fn->op == ONAME && fn->class == PFUNC && fn->defn && fn->defn->nbody && fn->ntype && fn->defn->esc < EscFuncTagged) {
926			// function in same mutually recursive group.  Incorporate into flow graph.
927	//		print("esc local fn: %N\n", fn->ntype);
928			if(fn->defn->esc == EscFuncUnknown || n->escretval != nil)
929				fatal("graph inconsistency");
930
931			// set up out list on this call node
932			for(lr=fn->ntype->rlist; lr; lr=lr->next)
933				n->escretval = list(n->escretval, lr->n->left);  // type.rlist ->  dclfield -> ONAME (PPARAMOUT)
934
936			if(n->op != OCALLFUNC)
937				escassign(e, fn->ntype->left->left, n->left->left);
938
939			for(lr=fn->ntype->list; ll && lr; ll=ll->next, lr=lr->next) {
940				src = ll->n;
941				if(lr->n->isddd && !n->isddd) {
942					// Introduce ODDDARG node to represent ... allocation.
943					src = nod(ODDDARG, N, N);
944					src->type = typ(TARRAY);
945					src->type->type = lr->n->type->type;
946					src->type->bound = count(ll);
947					src->type = ptrto(src->type); // make pointer so it will be tracked
948					src->escloopdepth = e->loopdepth;
949					src->lineno = n->lineno;
950					src->esc = EscNone;  // until we find otherwise
951					e->noesc = list(e->noesc, src);
952					n->right = src;
953				}
954				if(lr->n->left != N)
955					escassign(e, lr->n->left, src);
956				if(src != ll->n)
957					break;
958			}
959			// "..." arguments are untracked
960			for(; ll; ll=ll->next)
961				escassign(e, &e->theSink, ll->n);
962
963			return;
964		}
965
966		// Imported or completely analyzed function.  Use the escape tags.
967		if(n->escretval != nil)
968			fatal("esc already decorated call %+N\n", n);
969
970		// set up out list on this call node with dummy auto ONAMES in the current (calling) function.
971		i = 0;
972		for(t=getoutargx(fntype)->type; t; t=t->down) {
973			src = nod(ONAME, N, N);
974			snprint(buf, sizeof buf, ".dum%d", i++);
975			src->sym = lookup(buf);
976			src->type = t->type;
977			src->class = PAUTO;
978			src->curfn = curfn;
979			src->escloopdepth = e->loopdepth;
980			src->used = 1;
981			src->lineno = n->lineno;
982			n->escretval = list(n->escretval, src);
983		}
984
985	//	print("esc analyzed fn: %#N (%+T) returning (%+H)\n", fn, fntype, n->escretval);
986
988		if(n->op != OCALLFUNC) {
989			t = getthisx(fntype)->type;
990			src = n->left->left;
991			if(haspointers(t->type))
992				escassignfromtag(e, t->note, n->escretval, src);
993		}
994
995		for(t=getinargx(fntype)->type; ll; ll=ll->next) {
996			src = ll->n;
997			if(t->isddd && !n->isddd) {
998				// Introduce ODDDARG node to represent ... allocation.
999				src = nod(ODDDARG, N, N);
1000				src->escloopdepth = e->loopdepth;
1001				src->lineno = n->lineno;
1002				src->type = typ(TARRAY);
1003				src->type->type = t->type->type;
1004				src->type->bound = count(ll);
1005				src->type = ptrto(src->type); // make pointer so it will be tracked
1006				src->esc = EscNone;  // until we find otherwise
1007				e->noesc = list(e->noesc, src);
1008				n->right = src;
1009			}
1010			if(haspointers(t->type)) {
1011				if(escassignfromtag(e, t->note, n->escretval, src) == EscNone && up->op != ODEFER && up->op != OPROC) {
1012					a = src;
1013					while(a->op == OCONVNOP)
1014						a = a->left;
1015					switch(a->op) {
1016					case OCALLPART:
1017					case OCLOSURE:
1018					case ODDDARG:
1019					case OARRAYLIT:
1020					case OPTRLIT:
1021					case OSTRUCTLIT:
1022						// The callee has already been analyzed, so its arguments have esc tags.
1023						// The argument is marked as not escaping at all.
1024						// Record that fact so that any temporary used for
1025						// synthesizing this expression can be reclaimed when
1026						// the function returns.
1027						// This 'noescape' is even stronger than the usual esc == EscNone.
1028						// src->esc == EscNone means that src does not escape the current function.
1029						// src->noescape = 1 here means that src does not escape this statement
1030						// in the current function.
1031						a->noescape = 1;
1032						break;
1033					}
1034				}
1035			}
1036			if(src != ll->n)
1037				break;
1038			t = t->down;
1039		}
1040		// "..." arguments are untracked
1041		for(; ll; ll=ll->next)
1042			escassign(e, &e->theSink, ll->n);
1043	}
1044
1045	// Store the link src->dst in dst, throwing out some quick wins.
1046	static void
1047	escflows(EscState *e, Node *dst, Node *src)
1048	{
1049		if(dst == nil || src == nil || dst == src)
1050			return;
1051
1052		// Don't bother building a graph for scalars.
1053		if(src->type && !haspointers(src->type))
1054			return;
1055
1056		if(debug['m']>2)
1057			print("%L::flows:: %hN <- %hN\n", lineno, dst, src);
1058
1059		if(dst->escflowsrc == nil) {
1060			e->dsts = list(e->dsts, dst);
1061			e->dstcount++;
1062		}
1063		e->edgecount++;
1064
1065		dst->escflowsrc = list(dst->escflowsrc, src);
1066	}
1067
1068	// Whenever we hit a reference node, the level goes up by one, and whenever
1069	// we hit an OADDR, the level goes down by one. as long as we're on a level > 0
1070	// finding an OADDR just means we're following the upstream of a dereference,
1071	// so this address doesn't leak (yet).
1072	// If level == 0, it means the /value/ of this node can reach the root of this flood.
1073	// so if this node is an OADDR, it's argument should be marked as escaping iff
1074	// it's currfn/e->loopdepth are different from the flood's root.
1075	// Once an object has been moved to the heap, all of it's upstream should be considered
1076	// escaping to the global scope.
1077	static void
1078	escflood(EscState *e, Node *dst)
1079	{
1080		NodeList *l;
1081
1082		switch(dst->op) {
1083		case ONAME:
1084		case OCLOSURE:
1085			break;
1086		default:
1087			return;
1088		}
1089
1090		if(debug['m']>1)
1091			print("\nescflood:%d: dst %hN scope:%S[%d]\n", walkgen, dst,
1092			      (dst->curfn && dst->curfn->nname) ? dst->curfn->nname->sym : S,
1093			      dst->escloopdepth);
1094
1095		for(l = dst->escflowsrc; l; l=l->next) {
1096			walkgen++;
1097			escwalk(e, 0, dst, l->n);
1098		}
1099	}
1100
1101	// There appear to be some loops in the escape graph, causing
1102	// arbitrary recursion into deeper and deeper levels.
1103	// Cut this off safely by making minLevel sticky: once you
1104	// get that deep, you cannot go down any further but you also
1105	// cannot go up any further. This is a conservative fix.
1106	// Making minLevel smaller (more negative) would handle more
1107	// complex chains of indirections followed by address-of operations,
1108	// at the cost of repeating the traversal once for each additional
1109	// allowed level when a loop is encountered. Using -2 suffices to
1110	// pass all the tests we have written so far, which we assume matches
1111	// the level of complexity we want the escape analysis code to handle.
1112	#define MinLevel (-2)
1113	/*c2go enum { MinLevel = -2 };*/
1114
1115	static void
1116	escwalk(EscState *e, int level, Node *dst, Node *src)
1117	{
1118		NodeList *ll;
1119		int leaks, newlevel;
1120
1121		if(src->walkgen == walkgen && src->esclevel <= level)
1122			return;
1123		src->walkgen = walkgen;
1124		src->esclevel = level;
1125
1126		if(debug['m']>1)
1127			print("escwalk: level:%d depth:%d %.*s %hN(%hJ) scope:%S[%d]\n",
1128			      level, e->pdepth, e->pdepth, "\t\t\t\t\t\t\t\t\t\t", src, src,
1129			      (src->curfn && src->curfn->nname) ? src->curfn->nname->sym : S, src->escloopdepth);
1130
1131		e->pdepth++;
1132
1133		// Input parameter flowing to output parameter?
1134		if(dst->op == ONAME && dst->class == PPARAMOUT && dst->vargen <= 20) {
1135			if(src->op == ONAME && src->class == PPARAM && src->curfn == dst->curfn && src->esc != EscScope && src->esc != EscHeap) {
1136				if(level == 0) {
1137					if(debug['m'])
1138						warnl(src->lineno, "leaking param: %hN to result %S", src, dst->sym);
1140						src->esc = EscReturn;
1141					src->esc |= 1<<((dst->vargen-1) + EscReturnBits);
1142					goto recurse;
1143				} else if(level > 0) {
1144					if(debug['m'])
1145						warnl(src->lineno, "%N leaking param %hN content to result %S", src->curfn->nname, src, dst->sym);
1147						src->esc = EscReturn;
1148					src->esc |= EscContentEscapes;
1149					goto recurse;
1150				}
1151			}
1152		}
1153
1154		// The second clause is for values pointed at by an object passed to a call
1155		// that returns something reached via indirect from the object.
1156		// We don't know which result it is or how many indirects, so we treat it as leaking.
1157		leaks = level <= 0 && dst->escloopdepth < src->escloopdepth ||
1158			level < 0 && dst == &e->funcParam && haspointers(src->type);
1159
1160		switch(src->op) {
1161		case ONAME:
1162			if(src->class == PPARAM && (leaks || dst->escloopdepth < 0) && src->esc != EscHeap) {
1163				src->esc = EscScope;
1164				if(debug['m'])
1165					warnl(src->lineno, "leaking param: %hN", src);
1166			}
1167
1168			// Treat a PPARAMREF closure variable as equivalent to the
1169			// original variable.
1170			if(src->class == PPARAMREF) {
1171				if(leaks && debug['m'])
1172					warnl(src->lineno, "leaking closure reference %hN", src);
1173				escwalk(e, level, dst, src->closure);
1174			}
1175			break;
1176
1177		case OPTRLIT:
1179			if(leaks) {
1180				src->esc = EscHeap;
1182				if(debug['m'])
1183					warnl(src->lineno, "%hN escapes to heap", src);
1184			}
1185			newlevel = level;
1186			if(level > MinLevel)
1187				newlevel--;
1188			escwalk(e, newlevel, dst, src->left);
1189			break;
1190
1191		case OARRAYLIT:
1192			if(isfixedarray(src->type))
1193				break;
1194			// fall through
1195		case ODDDARG:
1196		case OMAKECHAN:
1197		case OMAKEMAP:
1198		case OMAKESLICE:
1199		case OMAPLIT:
1200		case ONEW:
1201		case OCLOSURE:
1202		case OCALLPART:
1203			if(leaks) {
1204				src->esc = EscHeap;
1205				if(debug['m'])
1206					warnl(src->lineno, "%hN escapes to heap", src);
1207			}
1208			break;
1209
1210		case ODOT:
1211		case OSLICE:
1212		case OSLICEARR:
1213		case OSLICE3:
1214		case OSLICE3ARR:
1215			escwalk(e, level, dst, src->left);
1216			break;
1217
1218		case OINDEX:
1219			if(isfixedarray(src->left->type)) {
1220				escwalk(e, level, dst, src->left);
1221				break;
1222			}
1223			// fall through
1224		case ODOTPTR:
1225		case OINDEXMAP:
1226		case OIND:
1227			newlevel = level;
1228			if(level > MinLevel)
1229				newlevel++;
1230			escwalk(e, newlevel, dst, src->left);
1231		}
1232
1233	recurse:
1234		for(ll=src->escflowsrc; ll; ll=ll->next)
1235			escwalk(e, level, dst, ll->n);
1236
1237		e->pdepth--;
1238	}
1239
1240	static void
1241	esctag(EscState *e, Node *func)
1242	{
1243		Node *savefn;
1244		NodeList *ll;
1245		Type *t;
1246
1247		USED(e);
1248		func->esc = EscFuncTagged;
1249
1250		// External functions are assumed unsafe,
1251		// unless //go:noescape is given before the declaration.
1252		if(func->nbody == nil) {
1253			if(func->noescape) {
1254				for(t=getinargx(func->type)->type; t; t=t->down)
1255					if(haspointers(t->type))
1256						t->note = mktag(EscNone);
1257			}
1258			return;
1259		}
1260
1261		savefn = curfn;
1262		curfn = func;
1263
1264		for(ll=curfn->dcl; ll; ll=ll->next) {
1265			if(ll->n->op != ONAME || ll->n->class != PPARAM)
1266				continue;
1267
1269			case EscNone:	// not touched by escflood
1270			case EscReturn:
1271				if(haspointers(ll->n->type)) // don't bother tagging for scalars
1272					ll->n->paramfld->note = mktag(ll->n->esc);
1273				break;
1274			case EscHeap:	// touched by escflood, moved to heap
1275			case EscScope:	// touched by escflood, value leaves scope
1276				break;
1277			}
1278		}
1279
1280		curfn = savefn;
1281	}
```

View as plain text