...
Run Format

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
     3	// license that can be found in the LICENSE file.
     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
    17	// adaptations.
    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) {
    76			// already visited
    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.
   180	// Instead, the compiler assumes that any value whose address
   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*
   225	mktag(int mask)
   226	{
   227		Strlit *s;
   228		char buf[40];
   229	
   230		switch(mask&EscMask) {
   231		case EscNone:
   232		case EscReturn:
   233			break;
   234		default:
   235			fatal("escape mktag");
   236		}
   237	
   238		mask >>= EscBits;
   239	
   240		if(mask < nelem(tags) && tags[mask] != nil)
   241			return tags[mask];
   242	
   243		snprint(buf, sizeof buf, "esc:0x%x", mask);
   244		s = strlit(buf);
   245		if(mask < nelem(tags))
   246			tags[mask] = s;
   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);
   393			// Walk will complain about this label being already defined, but that's not until
   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->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:
   647			// Link addresses of captured variables to closure.
   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	
   667		case OADDR:
   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
   671			// of addressed value.
   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	
   824		case OADD:
   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	
   935			// Receiver.
   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	
   987		// Receiver.
   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	
  1114	static void
  1115	escwalk(EscState *e, int level, Node *dst, Node *src)
  1116	{
  1117		NodeList *ll;
  1118		int leaks, newlevel;
  1119	
  1120		if(src->walkgen == walkgen && src->esclevel <= level)
  1121			return;
  1122		src->walkgen = walkgen;
  1123		src->esclevel = level;
  1124	
  1125		if(debug['m']>1)
  1126			print("escwalk: level:%d depth:%d %.*s %hN(%hJ) scope:%S[%d]\n",
  1127			      level, e->pdepth, e->pdepth, "\t\t\t\t\t\t\t\t\t\t", src, src,
  1128			      (src->curfn && src->curfn->nname) ? src->curfn->nname->sym : S, src->escloopdepth);
  1129	
  1130		e->pdepth++;
  1131	
  1132		// Input parameter flowing to output parameter?
  1133		if(dst->op == ONAME && dst->class == PPARAMOUT && dst->vargen <= 20) {
  1134			if(src->op == ONAME && src->class == PPARAM && src->curfn == dst->curfn && src->esc != EscScope && src->esc != EscHeap) {
  1135				if(level == 0) {
  1136					if(debug['m'])
  1137						warnl(src->lineno, "leaking param: %hN to result %S", src, dst->sym);
  1138					if((src->esc&EscMask) != EscReturn)
  1139						src->esc = EscReturn;
  1140					src->esc |= 1<<((dst->vargen-1) + EscReturnBits);
  1141					goto recurse;
  1142				} else if(level > 0) {
  1143					if(debug['m'])
  1144						warnl(src->lineno, "%N leaking param %hN content to result %S", src->curfn->nname, src, dst->sym);
  1145					if((src->esc&EscMask) != EscReturn)
  1146						src->esc = EscReturn;
  1147					src->esc |= EscContentEscapes;
  1148					goto recurse;
  1149				}
  1150			}
  1151		}
  1152	
  1153		// The second clause is for values pointed at by an object passed to a call
  1154		// that returns something reached via indirect from the object.
  1155		// We don't know which result it is or how many indirects, so we treat it as leaking.
  1156		leaks = level <= 0 && dst->escloopdepth < src->escloopdepth ||
  1157			level < 0 && dst == &e->funcParam && haspointers(src->type);
  1158	
  1159		switch(src->op) {
  1160		case ONAME:
  1161			if(src->class == PPARAM && (leaks || dst->escloopdepth < 0) && src->esc != EscHeap) {
  1162				src->esc = EscScope;
  1163				if(debug['m'])
  1164					warnl(src->lineno, "leaking param: %hN", src);
  1165			}
  1166	
  1167			// Treat a PPARAMREF closure variable as equivalent to the
  1168			// original variable.
  1169			if(src->class == PPARAMREF) {
  1170				if(leaks && debug['m'])
  1171					warnl(src->lineno, "leaking closure reference %hN", src);
  1172				escwalk(e, level, dst, src->closure);
  1173			}
  1174			break;
  1175	
  1176		case OPTRLIT:
  1177		case OADDR:
  1178			if(leaks) {
  1179				src->esc = EscHeap;
  1180				addrescapes(src->left);
  1181				if(debug['m'])
  1182					warnl(src->lineno, "%hN escapes to heap", src);
  1183			}
  1184			newlevel = level;
  1185			if(level > MinLevel)
  1186				newlevel--;
  1187			escwalk(e, newlevel, dst, src->left);
  1188			break;
  1189	
  1190		case OARRAYLIT:
  1191			if(isfixedarray(src->type))
  1192				break;
  1193			// fall through
  1194		case ODDDARG:
  1195		case OMAKECHAN:
  1196		case OMAKEMAP:
  1197		case OMAKESLICE:
  1198		case OMAPLIT:
  1199		case ONEW:
  1200		case OCLOSURE:
  1201		case OCALLPART:
  1202			if(leaks) {
  1203				src->esc = EscHeap;
  1204				if(debug['m'])
  1205					warnl(src->lineno, "%hN escapes to heap", src);
  1206			}
  1207			break;
  1208	
  1209		case ODOT:
  1210		case OSLICE:
  1211		case OSLICEARR:
  1212		case OSLICE3:
  1213		case OSLICE3ARR:
  1214			escwalk(e, level, dst, src->left);
  1215			break;
  1216	
  1217		case OINDEX:
  1218			if(isfixedarray(src->left->type)) {
  1219				escwalk(e, level, dst, src->left);
  1220				break;
  1221			}
  1222			// fall through
  1223		case ODOTPTR:
  1224		case OINDEXMAP:
  1225		case OIND:
  1226			newlevel = level;
  1227			if(level > MinLevel)
  1228				newlevel++;
  1229			escwalk(e, newlevel, dst, src->left);
  1230		}
  1231	
  1232	recurse:
  1233		for(ll=src->escflowsrc; ll; ll=ll->next)
  1234			escwalk(e, level, dst, ll->n);
  1235	
  1236		e->pdepth--;
  1237	}
  1238	
  1239	static void
  1240	esctag(EscState *e, Node *func)
  1241	{
  1242		Node *savefn;
  1243		NodeList *ll;
  1244		Type *t;
  1245	
  1246		USED(e);
  1247		func->esc = EscFuncTagged;
  1248		
  1249		// External functions are assumed unsafe,
  1250		// unless //go:noescape is given before the declaration.
  1251		if(func->nbody == nil) {
  1252			if(func->noescape) {
  1253				for(t=getinargx(func->type)->type; t; t=t->down)
  1254					if(haspointers(t->type))
  1255						t->note = mktag(EscNone);
  1256			}
  1257			return;
  1258		}
  1259	
  1260		savefn = curfn;
  1261		curfn = func;
  1262	
  1263		for(ll=curfn->dcl; ll; ll=ll->next) {
  1264			if(ll->n->op != ONAME || ll->n->class != PPARAM)
  1265				continue;
  1266	
  1267			switch (ll->n->esc&EscMask) {
  1268			case EscNone:	// not touched by escflood
  1269			case EscReturn:	
  1270				if(haspointers(ll->n->type)) // don't bother tagging for scalars
  1271					ll->n->paramfld->note = mktag(ll->n->esc);
  1272				break;
  1273			case EscHeap:	// touched by escflood, moved to heap
  1274			case EscScope:	// touched by escflood, value leaves scope
  1275				break;
  1276			}
  1277		}
  1278	
  1279		curfn = savefn;
  1280	}

View as plain text