path: root/src/cmd/gc/esc.c

// Copyright 2011 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.

// Escape analysis.

#include <u.h>
#include <libc.h>
#include "go.h"

// Run analysis on minimal sets of mutually recursive functions
// or single non-recursive functions, bottom up.
//
// Finding these sets is finding strongly connected components
// in the static call graph.  The algorithm for doing that is taken
// from Sedgewick, Algorithms, Second Edition, p. 482, with two
// adaptations.
//
// First, a hidden closure function (n->curfn != N) cannot be the
// root of a connected component. Refusing to use it as a root
// forces it into the component of the function in which it appears.
// The analysis assumes that closures and the functions in which they
// appear are analyzed together, so that the aliasing between their
// variables can be modeled more precisely.
//
// Second, each function becomes two virtual nodes in the graph,
// with numbers n and n+1. We record the function's node number as n
// but search from node n+1. If the search tells us that the component
// number (min) is n+1, we know that this is a trivial component: one function
// plus its closures. If the search tells us that the component number is
// n, then there was a path from node n+1 back to node n, meaning that
// the function set is mutually recursive. The escape analysis can be
// more precise when analyzing a single non-recursive function than
// when analyzing a set of mutually recursive functions.

static NodeList *stack;
static uint32 visitgen;
static uint32 visit(Node*);
static uint32 visitcode(Node*, uint32);
static uint32 visitcodelist(NodeList*, uint32);

static void analyze(NodeList*, int);

enum
{
	EscFuncUnknown = 0,
	EscFuncPlanned,
	EscFuncStarted,
	EscFuncTagged,
};

void
escapes(NodeList *all)
{
	NodeList *l;

	for(l=all; l; l=l->next)
		l->n->walkgen = 0;

	visitgen = 0;
	for(l=all; l; l=l->next)
		if(l->n->op == ODCLFUNC && l->n->curfn == N)
			visit(l->n);

	for(l=all; l; l=l->next)
		l->n->walkgen = 0;
}

static uint32
visit(Node *n)
{
	uint32 min, recursive;
	NodeList *l, *block;

	if(n->walkgen > 0) {
		// already visited
		return n->walkgen;
	}
	
	visitgen++;
	n->walkgen = visitgen;
	visitgen++;
	min = visitgen;

	l = mal(sizeof *l);
	l->next = stack;
	l->n = n;
	stack = l;
	min = visitcodelist(n->nbody, min);
	if((min == n->walkgen || min == n->walkgen+1) && n->curfn == N) {
		// This node is the root of a strongly connected component.

		// The original min passed to visitcodelist was n->walkgen+1.
		// If visitcodelist found its way back to n->walkgen, then this
		// block is a set of mutually recursive functions.
		// Otherwise it's just a lone function that does not recurse.
		recursive = min == n->walkgen;

		// Remove connected component from stack.
		// Mark walkgen so that future visits return a large number
		// so as not to affect the caller's min.
		block = stack;
		for(l=stack; l->n != n; l=l->next)
			l->n->walkgen = (uint32)~0U;
		n->walkgen = (uint32)~0U;
		stack = l->next;
		l->next = nil;

		// Run escape analysis on this set of functions.
		analyze(block, recursive);
	}

	return min;
}

static uint32
visitcodelist(NodeList *l, uint32 min)
{
	for(; l; l=l->next)
		min = visitcode(l->n, min);
	return min;
}

static uint32
visitcode(Node *n, uint32 min)
{
	Node *fn;
	uint32 m;

	if(n == N)
		return min;

	min = visitcodelist(n->ninit, min);
	min = visitcode(n->left, min);
	min = visitcode(n->right, min);
	min = visitcodelist(n->list, min);
	min = visitcode(n->ntest, min);
	min = visitcode(n->nincr, min);
	min = visitcodelist(n->nbody, min);
	min = visitcodelist(n->nelse, min);
	min = visitcodelist(n->rlist, min);
	
	if(n->op == OCALLFUNC || n->op == OCALLMETH) {
		fn = n->left;
		if(n->op == OCALLMETH)
			fn = n->left->right->sym->def;
		if(fn && fn->op == ONAME && fn->class == PFUNC && fn->defn)
			if((m = visit(fn->defn)) < min)
				min = m;
	}
	
	if(n->op == OCLOSURE)
		if((m = visit(n->closure)) < min)
			min = m;

	return min;
}

// An escape analysis pass for a set of functions.
//
// First escfunc, esc and escassign recurse over the ast of each
// function to dig out flow(dst,src) edges between any
// pointer-containing nodes and store them in dst->escflowsrc.  For
// variables assigned to a variable in an outer scope or used as a
// return value, they store a flow(theSink, src) edge to a fake node
// 'the Sink'.  For variables referenced in closures, an edge
// flow(closure, &var) is recorded and the flow of a closure itself to
// an outer scope is tracked the same way as other variables.
//
// Then escflood walks the graph starting at theSink and tags all
// variables of it can reach an & node as escaping and all function
// parameters it can reach as leaking.
//
// If a value's address is taken but the address does not escape,
// then the value can stay on the stack.  If the value new(T) does
// not escape, then new(T) can be rewritten into a stack allocation.
// The same is true of slice literals.
//
// If optimizations are disabled (-N), this code is not used.
// Instead, the compiler assumes that any value whose address
// is taken without being immediately dereferenced
// needs to be moved to the heap, and new(T) and slice
// literals are always real allocations.

typedef struct EscState EscState;

static void escfunc(EscState*, Node *func);
static void esclist(EscState*, NodeList *l);
static void esc(EscState*, Node *n);
static void escloopdepthlist(EscState*, NodeList *l);
static void escloopdepth(EscState*, Node *n);
static void escassign(EscState*, Node *dst, Node *src);
static void esccall(EscState*, Node*);
static void escflows(EscState*, Node *dst, Node *src);
static void escflood(EscState*, Node *dst);
static void escwalk(EscState*, int level, Node *dst, Node *src);
static void esctag(EscState*, Node *func);

struct EscState {
	// Fake node that all
	//   - return values and output variables
	//   - parameters on imported functions not marked 'safe'
	//   - assignments to global variables
	// flow to.
	Node	theSink;
	
	NodeList*	dsts;		// all dst nodes
	int	loopdepth;	// for detecting nested loop scopes
	int	pdepth;		// for debug printing in recursions.
	int	dstcount, edgecount;	// diagnostic
	NodeList*	noesc;	// list of possible non-escaping nodes, for printing
	int	recursive;	// recursive function or group of mutually recursive functions.
};

static Strlit *tags[16];

static Strlit*
mktag(int mask)
{
	Strlit *s;
	char buf[40];

	switch(mask&EscMask) {
	case EscNone:
	case EscReturn:
		break;
	default:
		fatal("escape mktag");
	}

	mask >>= EscBits;

	if(mask < nelem(tags) && tags[mask] != nil)
		return tags[mask];

	snprint(buf, sizeof buf, "esc:0x%x", mask);
	s = strlit(buf);
	if(mask < nelem(tags))
		tags[mask] = s;
	return s;
}

static int
parsetag(Strlit *note)
{
	int em;

	if(note == nil)
		return EscUnknown;
	if(strncmp(note->s, "esc:", 4) != 0)
		return EscUnknown;
	em = atoi(note->s + 4);
	if (em == 0)
		return EscNone;
	return EscReturn | (em << EscBits);
}

static void
analyze(NodeList *all, int recursive)
{
	NodeList *l;
	EscState es, *e;
	
	memset(&es, 0, sizeof es);
	e = &es;
	e->theSink.op = ONAME;
	e->theSink.orig = &e->theSink;
	e->theSink.class = PEXTERN;
	e->theSink.sym = lookup(".sink");
	e->theSink.escloopdepth = -1;
	e->recursive = recursive;

	for(l=all; l; l=l->next)
		if(l->n->op == ODCLFUNC)
			l->n->esc = EscFuncPlanned;

	// flow-analyze functions
	for(l=all; l; l=l->next)
		if(l->n->op == ODCLFUNC)
			escfunc(e, l->n);

	// print("escapes: %d e->dsts, %d edges\n", e->dstcount, e->edgecount);

	// visit the upstream of each dst, mark address nodes with
	// addrescapes, mark parameters unsafe
	for(l = e->dsts; l; l=l->next)
		escflood(e, l->n);

	// for all top level functions, tag the typenodes corresponding to the param nodes
	for(l=all; l; l=l->next)
		if(l->n->op == ODCLFUNC)
			esctag(e, l->n);

	if(debug['m']) {
		for(l=e->noesc; l; l=l->next)
			if(l->n->esc == EscNone)
				warnl(l->n->lineno, "%S %hN does not escape",
					(l->n->curfn && l->n->curfn->nname) ? l->n->curfn->nname->sym : S,
					l->n);
	}
}


static void
escfunc(EscState *e, Node *func)
{
	Node *savefn;
	NodeList *ll;
	int saveld;

//	print("escfunc %N %s\n", func->nname, e->recursive?"(recursive)":"");

	if(func->esc != 1)
		fatal("repeat escfunc %N", func->nname);
	func->esc = EscFuncStarted;

	saveld = e->loopdepth;
	e->loopdepth = 1;
	savefn = curfn;
	curfn = func;

	for(ll=curfn->dcl; ll; ll=ll->next) {
		if(ll->n->op != ONAME)
			continue;
		switch (ll->n->class) {
		case PPARAMOUT:
			// out params are in a loopdepth between the sink and all local variables
			ll->n->escloopdepth = 0;
			break;
		case PPARAM:
			if(ll->n->type && !haspointers(ll->n->type))
				break;
			if(curfn->nbody == nil && !curfn->noescape)
				ll->n->esc = EscHeap;
			else
				ll->n->esc = EscNone;	// prime for escflood later
			e->noesc = list(e->noesc, ll->n);
			ll->n->escloopdepth = 1; 
			break;
		}
	}

	// in a mutually recursive group we lose track of the return values
	if(e->recursive)
		for(ll=curfn->dcl; ll; ll=ll->next)
			if(ll->n->op == ONAME && ll->n->class == PPARAMOUT)
				escflows(e, &e->theSink, ll->n);

	escloopdepthlist(e, curfn->nbody);
	esclist(e, curfn->nbody);
	curfn = savefn;
	e->loopdepth = saveld;
}

// Mark labels that have no backjumps to them as not increasing e->loopdepth.
// Walk hasn't generated (goto|label)->left->sym->label yet, so we'll cheat
// and set it to one of the following two.  Then in esc we'll clear it again.
static Label looping;
static Label nonlooping;

static void
escloopdepthlist(EscState *e, NodeList *l)
{
	for(; l; l=l->next)
		escloopdepth(e, l->n);
}

static void
escloopdepth(EscState *e, Node *n)
{
	if(n == N)
		return;

	escloopdepthlist(e, n->ninit);

	switch(n->op) {
	case OLABEL:
		if(!n->left || !n->left->sym)
			fatal("esc:label without label: %+N", n);
		// Walk will complain about this label being already defined, but that's not until
		// after escape analysis. in the future, maybe pull label & goto analysis out of walk and put before esc
		// if(n->left->sym->label != nil)
		//	fatal("escape analysis messed up analyzing label: %+N", n);
		n->left->sym->label = &nonlooping;
		break;
	case OGOTO:
		if(!n->left || !n->left->sym)
			fatal("esc:goto without label: %+N", n);
		// If we come past one that's uninitialized, this must be a (harmless) forward jump
		// but if it's set to nonlooping the label must have preceded this goto.
		if(n->left->sym->label == &nonlooping)
			n->left->sym->label = &looping;
		break;
	}

	escloopdepth(e, n->left);
	escloopdepth(e, n->right);
	escloopdepthlist(e, n->list);
	escloopdepth(e, n->ntest);
	escloopdepth(e, n->nincr);
	escloopdepthlist(e, n->nbody);
	escloopdepthlist(e, n->nelse);
	escloopdepthlist(e, n->rlist);

}

static void
esclist(EscState *e, NodeList *l)
{
	for(; l; l=l->next)
		esc(e, l->n);
}

static void
esc(EscState *e, Node *n)
{
	int lno;
	NodeList *ll, *lr;
	Node *a;

	if(n == N)
		return;

	lno = setlineno(n);

	if(n->op == OFOR || n->op == ORANGE)
		e->loopdepth++;

	esc(e, n->left);
	esc(e, n->right);
	esc(e, n->ntest);
	esc(e, n->nincr);
	esclist(e, n->ninit);
	esclist(e, n->nbody);
	esclist(e, n->nelse);
	esclist(e, n->list);
	esclist(e, n->rlist);

	if(n->op == OFOR || n->op == ORANGE)
		e->loopdepth--;

	if(debug['m'] > 1)
		print("%L:[%d] %S esc: %N\n", lineno, e->loopdepth,
		      (curfn && curfn->nname) ? curfn->nname->sym : S, n);

	switch(n->op) {
	case ODCL:
		// Record loop depth at declaration.
		if(n->left)
			n->left->escloopdepth = e->loopdepth;
		break;

	case OLABEL:
		if(n->left->sym->label == &nonlooping) {
			if(debug['m'] > 1)
				print("%L:%N non-looping label\n", lineno, n);
		} else if(n->left->sym->label == &looping) {
			if(debug['m'] > 1)
				print("%L: %N looping label\n", lineno, n);
			e->loopdepth++;
		}
		// See case OLABEL in escloopdepth above
		// else if(n->left->sym->label == nil)
		//	fatal("escape analysis missed or messed up a label: %+N", n);

		n->left->sym->label = nil;
		break;

	case ORANGE:
		// Everything but fixed array is a dereference.
		if(isfixedarray(n->type) && n->list->next)
			escassign(e, n->list->next->n, n->right);
		break;

	case OSWITCH:
		if(n->ntest && n->ntest->op == OTYPESW) {
			for(ll=n->list; ll; ll=ll->next) {  // cases
				// ntest->right is the argument of the .(type),
				// ll->n->nname is the variable per case
				escassign(e, ll->n->nname, n->ntest->right);
			}
		}
		break;

	case OAS:
	case OASOP:
		escassign(e, n->left, n->right);
		break;

	case OAS2:	// x,y = a,b
		if(count(n->list) == count(n->rlist))
			for(ll=n->list, lr=n->rlist; ll; ll=ll->next, lr=lr->next)
				escassign(e, ll->n, lr->n);
		break;

	case OAS2RECV:		// v, ok = <-ch
	case OAS2MAPR:		// v, ok = m[k]
	case OAS2DOTTYPE:	// v, ok = x.(type)
		escassign(e, n->list->n, n->rlist->n);
		break;

	case OSEND:		// ch <- x
		escassign(e, &e->theSink, n->right);
		break;

	case ODEFER:
		if(e->loopdepth == 1)  // top level
			break;
		// arguments leak out of scope
		// TODO: leak to a dummy node instead
		// fallthrough
	case OPROC:
		// go f(x) - f and x escape
		escassign(e, &e->theSink, n->left->left);
		escassign(e, &e->theSink, n->left->right);  // ODDDARG for call
		for(ll=n->left->list; ll; ll=ll->next)
			escassign(e, &e->theSink, ll->n);
		break;

	case OCALLMETH:
	case OCALLFUNC:
	case OCALLINTER:
		esccall(e, n);
		break;

	case OAS2FUNC:	// x,y = f()
		// esccall already done on n->rlist->n. tie it's escretval to n->list
		lr=n->rlist->n->escretval;
		for(ll=n->list; lr && ll; lr=lr->next, ll=ll->next)
			escassign(e, ll->n, lr->n);
		if(lr || ll)
			fatal("esc oas2func");
		break;

	case ORETURN:
		ll=n->list;
		if(count(n->list) == 1 && curfn->type->outtuple > 1) {
			// OAS2FUNC in disguise
			// esccall already done on n->list->n
			// tie n->list->n->escretval to curfn->dcl PPARAMOUT's
			ll = n->list->n->escretval;
		}

		for(lr = curfn->dcl; lr && ll; lr=lr->next) {
			if (lr->n->op != ONAME || lr->n->class != PPARAMOUT)
				continue;
			escassign(e, lr->n, ll->n);
			ll = ll->next;
		}
		if (ll != nil)
			fatal("esc return list");
		break;

	case OPANIC:
		// Argument could leak through recover.
		escassign(e, &e->theSink, n->left);
		break;

	case OAPPEND:
		if(!n->isddd)
			for(ll=n->list->next; ll; ll=ll->next)
				escassign(e, &e->theSink, ll->n);  // lose track of assign to dereference
		break;

	case OCONV:
	case OCONVNOP:
	case OCONVIFACE:
		escassign(e, n, n->left);
		break;

	case OARRAYLIT:
		if(isslice(n->type)) {
			n->esc = EscNone;  // until proven otherwise
			e->noesc = list(e->noesc, n);
			n->escloopdepth = e->loopdepth;
			// Values make it to memory, lose track.
			for(ll=n->list; ll; ll=ll->next)
				escassign(e, &e->theSink, ll->n->right);
		} else {
			// Link values to array.
			for(ll=n->list; ll; ll=ll->next)
				escassign(e, n, ll->n->right);
		}
		break;

	case OSTRUCTLIT:
		// Link values to struct.
		for(ll=n->list; ll; ll=ll->next)
			escassign(e, n, ll->n->right);
		break;
	
	case OPTRLIT:
		n->esc = EscNone;  // until proven otherwise
		e->noesc = list(e->noesc, n);
		n->escloopdepth = e->loopdepth;
		// Contents make it to memory, lose track.
		escassign(e, &e->theSink, n->left);
		break;
	
	case OCALLPART:
		n->esc = EscNone; // until proven otherwise
		e->noesc = list(e->noesc, n);
		n->escloopdepth = e->loopdepth;
		// Contents make it to memory, lose track.
		escassign(e, &e->theSink, n->left);
		break;

	case OMAPLIT:
		n->esc = EscNone;  // until proven otherwise
		e->noesc = list(e->noesc, n);
		n->escloopdepth = e->loopdepth;
		// Keys and values make it to memory, lose track.
		for(ll=n->list; ll; ll=ll->next) {
			escassign(e, &e->theSink, ll->n->left);
			escassign(e, &e->theSink, ll->n->right);
		}
		break;
	
	case OCLOSURE:
		// Link addresses of captured variables to closure.
		for(ll=n->cvars; ll; ll=ll->next) {
			if(ll->n->op == OXXX)  // unnamed out argument; see dcl.c:/^funcargs
				continue;
			a = nod(OADDR, ll->n->closure, N);
			a->lineno = ll->n->lineno;
			a->escloopdepth = e->loopdepth;
			typecheck(&a, Erv);
			escassign(e, n, a);
		}
		// fallthrough
	case OADDR:
	case OMAKECHAN:
	case OMAKEMAP:
	case OMAKESLICE:
	case ONEW:
		n->escloopdepth = e->loopdepth;
		n->esc = EscNone;  // until proven otherwise
		e->noesc = list(e->noesc, n);
		break;
	}

	lineno = lno;
}

// Assert that expr somehow gets assigned to dst, if non nil.  for
// dst==nil, any name node expr still must be marked as being
// evaluated in curfn.	For expr==nil, dst must still be examined for
// evaluations inside it (e.g *f(x) = y)
static void
escassign(EscState *e, Node *dst, Node *src)
{
	int lno;
	NodeList *ll;

	if(isblank(dst) || dst == N || src == N || src->op == ONONAME || src->op == OXXX)
		return;

	if(debug['m'] > 1)
		print("%L:[%d] %S escassign: %hN(%hJ) = %hN(%hJ)\n", lineno, e->loopdepth,
		      (curfn && curfn->nname) ? curfn->nname->sym : S, dst, dst, src, src);

	setlineno(dst);
	
	// Analyze lhs of assignment.
	// Replace dst with e->theSink if we can't track it.
	switch(dst->op) {
	default:
		dump("dst", dst);
		fatal("escassign: unexpected dst");

	case OARRAYLIT:
	case OCLOSURE:
	case OCONV:
	case OCONVIFACE:
	case OCONVNOP:
	case OMAPLIT:
	case OSTRUCTLIT:
	case OCALLPART:
		break;

	case ONAME:
		if(dst->class == PEXTERN)
			dst = &e->theSink;
		break;
	case ODOT:	      // treat "dst.x  = src" as "dst = src"
		escassign(e, dst->left, src);
		return;
	case OINDEX:
		if(isfixedarray(dst->left->type)) {
			escassign(e, dst->left, src);
			return;
		}
		dst = &e->theSink;  // lose track of dereference
		break;
	case OIND:
	case ODOTPTR:
		dst = &e->theSink;  // lose track of dereference
		break;
	case OINDEXMAP:
		// lose track of key and value
		escassign(e, &e->theSink, dst->right);
		dst = &e->theSink;
		break;
	}

	lno = setlineno(src);
	e->pdepth++;

	switch(src->op) {
	case OADDR:	// dst = &x
	case OIND:	// dst = *x
	case ODOTPTR:	// dst = (*x).f
	case ONAME:
	case OPARAM:
	case ODDDARG:
	case OPTRLIT:
	case OARRAYLIT:
	case OMAPLIT:
	case OSTRUCTLIT:
	case OMAKECHAN:
	case OMAKEMAP:
	case OMAKESLICE:
	case ONEW:
	case OCLOSURE:
	case OCALLPART:
		escflows(e, dst, src);
		break;

	case OCALLMETH:
	case OCALLFUNC:
	case OCALLINTER:
		// Flowing multiple returns to a single dst happens when
		// analyzing "go f(g())": here g() flows to sink (issue 4529).
		for(ll=src->escretval; ll; ll=ll->next)
			escflows(e, dst, ll->n);
		break;

	case ODOT:
		// A non-pointer escaping from a struct does not concern us.
		if(src->type && !haspointers(src->type))
			break;
		// fallthrough
	case OCONV:
	case OCONVIFACE:
	case OCONVNOP:
	case ODOTMETH:	// treat recv.meth as a value with recv in it, only happens in ODEFER and OPROC
			// iface.method already leaks iface in esccall, no need to put in extra ODOTINTER edge here
	case ODOTTYPE:
	case ODOTTYPE2:
	case OSLICE:
	case OSLICEARR:
	case OSLICE3:
	case OSLICE3ARR:
		// Conversions, field access, slice all preserve the input value.
		escassign(e, dst, src->left);
		break;

	case OAPPEND:
		// Append returns first argument.
		escassign(e, dst, src->list->n);
		break;
	
	case OINDEX:
		// Index of array preserves input value.
		if(isfixedarray(src->left->type))
			escassign(e, dst, src->left);
		break;

	case OADD:
	case OSUB:
	case OOR:
	case OXOR:
	case OMUL:
	case ODIV:
	case OMOD:
	case OLSH:
	case ORSH:
	case OAND:
	case OANDNOT:
	case OPLUS:
	case OMINUS:
	case OCOM:
		// Might be pointer arithmetic, in which case
		// the operands flow into the result.
		// TODO(rsc): Decide what the story is here.  This is unsettling.
		escassign(e, dst, src->left);
		escassign(e, dst, src->right);
		break;
	}

	e->pdepth--;
	lineno = lno;
}

static void
escassignfromtag(EscState *e, Strlit *note, NodeList *dsts, Node *src)
{
	int em;
	
	em = parsetag(note);
	
	if(em == EscUnknown) {
		escassign(e, &e->theSink, src);
		return;
	}
		
	for(em >>= EscBits; em && dsts; em >>= 1, dsts=dsts->next)
		if(em & 1)
			escassign(e, dsts->n, src);

	if (em != 0 && dsts == nil)
		fatal("corrupt esc tag %Z or messed up escretval list\n", note);
}

// This is a bit messier than fortunate, pulled out of esc's big
// switch for clarity.	We either have the paramnodes, which may be
// connected to other things through flows or we have the parameter type
// nodes, which may be marked "noescape". Navigating the ast is slightly
// different for methods vs plain functions and for imported vs
// this-package
static void
esccall(EscState *e, Node *n)
{
	NodeList *ll, *lr;
	Node *a, *fn, *src;
	Type *t, *fntype;
	char buf[40];
	int i;

	fn = N;
	switch(n->op) {
	default:
		fatal("esccall");

	case OCALLFUNC:
		fn = n->left;
		fntype = fn->type;
		break;

	case OCALLMETH:
		fn = n->left->right->sym->def;
		if(fn)
			fntype = fn->type;
		else
			fntype = n->left->type;
		break;

	case OCALLINTER:
		fntype = n->left->type;
		break;
	}

	ll = n->list;
	if(n->list != nil && n->list->next == nil) {
		a = n->list->n;
		if(a->type->etype == TSTRUCT && a->type->funarg) // f(g()).
			ll = a->escretval;
	}
			
	if(fn && fn->op == ONAME && fn->class == PFUNC && fn->defn && fn->defn->nbody && fn->ntype && fn->defn->esc < EscFuncTagged) {
		// function in same mutually recursive group.  Incorporate into flow graph.
//		print("esc local fn: %N\n", fn->ntype);
		if(fn->defn->esc == EscFuncUnknown || n->escretval != nil)
			fatal("graph inconsistency");

		// set up out list on this call node
		for(lr=fn->ntype->rlist; lr; lr=lr->next)
			n->escretval = list(n->escretval, lr->n->left);  // type.rlist ->  dclfield -> ONAME (PPARAMOUT)

		// Receiver.
		if(n->op != OCALLFUNC)
			escassign(e, fn->ntype->left->left, n->left->left);

		for(lr=fn->ntype->list; ll && lr; ll=ll->next, lr=lr->next) {
			src = ll->n;
			if(lr->n->isddd && !n->isddd) {
				// Introduce ODDDARG node to represent ... allocation.
				src = nod(ODDDARG, N, N);
				src->escloopdepth = e->loopdepth;
				src->lineno = n->lineno;
				src->esc = EscNone;  // until we find otherwise
				e->noesc = list(e->noesc, src);
				n->right = src;
			}
			if(lr->n->left != N)
				escassign(e, lr->n->left, src);
			if(src != ll->n)
				break;
		}
		// "..." arguments are untracked
		for(; ll; ll=ll->next)
			escassign(e, &e->theSink, ll->n);

		return;
	}

	// Imported or completely analyzed function.  Use the escape tags.
	if(n->escretval != nil)
		fatal("esc already decorated call %+N\n", n);

	// set up out list on this call node with dummy auto ONAMES in the current (calling) function.
	i = 0;
	for(t=getoutargx(fntype)->type; t; t=t->down) {
		src = nod(ONAME, N, N);
		snprint(buf, sizeof buf, ".dum%d", i++);
		src->sym = lookup(buf);
		src->type = t->type;
		src->class = PAUTO;
		src->curfn = curfn;
		src->escloopdepth = e->loopdepth;
		src->used = 1;
		src->lineno = n->lineno;
		n->escretval = list(n->escretval, src); 
	}

//	print("esc analyzed fn: %#N (%+T) returning (%+H)\n", fn, fntype, n->escretval);

	// Receiver.
	if(n->op != OCALLFUNC)
		escassignfromtag(e, getthisx(fntype)->type->note, n->escretval, n->left->left);
	
	for(t=getinargx(fntype)->type; ll; ll=ll->next) {
		src = ll->n;
		if(t->isddd && !n->isddd) {
			// Introduce ODDDARG node to represent ... allocation.
			src = nod(ODDDARG, N, N);
			src->escloopdepth = e->loopdepth;
			src->lineno = n->lineno;
			src->esc = EscNone;  // until we find otherwise
			e->noesc = list(e->noesc, src);
			n->right = src;
		}
		escassignfromtag(e, t->note, n->escretval, src);
		if(src != ll->n)
			break;
		t = t->down;
	}
	// "..." arguments are untracked
	for(; ll; ll=ll->next)
		escassign(e, &e->theSink, ll->n);
}

// Store the link src->dst in dst, throwing out some quick wins.
static void
escflows(EscState *e, Node *dst, Node *src)
{
	if(dst == nil || src == nil || dst == src)
		return;

	// Don't bother building a graph for scalars.
	if(src->type && !haspointers(src->type))
		return;

	if(debug['m']>2)
		print("%L::flows:: %hN <- %hN\n", lineno, dst, src);

	if(dst->escflowsrc == nil) {
		e->dsts = list(e->dsts, dst);
		e->dstcount++;
	}
	e->edgecount++;

	dst->escflowsrc = list(dst->escflowsrc, src);
}

// Whenever we hit a reference node, the level goes up by one, and whenever
// we hit an OADDR, the level goes down by one. as long as we're on a level > 0
// finding an OADDR just means we're following the upstream of a dereference,
// so this address doesn't leak (yet).
// If level == 0, it means the /value/ of this node can reach the root of this flood.
// so if this node is an OADDR, it's argument should be marked as escaping iff
// it's currfn/e->loopdepth are different from the flood's root.
// Once an object has been moved to the heap, all of it's upstream should be considered
// escaping to the global scope.
static void
escflood(EscState *e, Node *dst)
{
	NodeList *l;

	switch(dst->op) {
	case ONAME:
	case OCLOSURE:
		break;
	default:
		return;
	}

	if(debug['m']>1)
		print("\nescflood:%d: dst %hN scope:%S[%d]\n", walkgen, dst,
		      (dst->curfn && dst->curfn->nname) ? dst->curfn->nname->sym : S,
		      dst->escloopdepth);

	for(l = dst->escflowsrc; l; l=l->next) {
		walkgen++;
		escwalk(e, 0, dst, l->n);
	}
}

// There appear to be some loops in the escape graph, causing
// arbitrary recursion into deeper and deeper levels.
// Cut this off safely by making minLevel sticky: once you
// get that deep, you cannot go down any further but you also
// cannot go up any further. This is a conservative fix.
// Making minLevel smaller (more negative) would handle more
// complex chains of indirections followed by address-of operations,
// at the cost of repeating the traversal once for each additional
// allowed level when a loop is encountered. Using -2 suffices to
// pass all the tests we have written so far, which we assume matches
// the level of complexity we want the escape analysis code to handle.
#define MinLevel (-2)

static void
escwalk(EscState *e, int level, Node *dst, Node *src)
{
	NodeList *ll;
	int leaks, newlevel;

	if(src->walkgen == walkgen && src->esclevel <= level)
		return;
	src->walkgen = walkgen;
	src->esclevel = level;

	if(debug['m']>1)
		print("escwalk: level:%d depth:%d %.*s %hN(%hJ) scope:%S[%d]\n",
		      level, e->pdepth, e->pdepth, "\t\t\t\t\t\t\t\t\t\t", src, src,
		      (src->curfn && src->curfn->nname) ? src->curfn->nname->sym : S, src->escloopdepth);

	e->pdepth++;

	// Input parameter flowing to output parameter?
	if(dst->op == ONAME && dst->class == PPARAMOUT && dst->vargen <= 20) {
		if(src->op == ONAME && src->class == PPARAM && level == 0 && src->curfn == dst->curfn) {
			if(src->esc != EscScope && src->esc != EscHeap) {
				if(debug['m'])
					warnl(src->lineno, "leaking param: %hN to result %S", src, dst->sym);
				if((src->esc&EscMask) != EscReturn)
					src->esc = EscReturn;
				src->esc |= 1<<((dst->vargen-1) + EscBits);
				goto recurse;
			}
		}
	}

	leaks = (level <= 0) && (dst->escloopdepth < src->escloopdepth);

	switch(src->op) {
	case ONAME:
		if(src->class == PPARAM && (leaks || dst->escloopdepth < 0) && src->esc != EscHeap) {
			src->esc = EscScope;
			if(debug['m'])
				warnl(src->lineno, "leaking param: %hN", src);
		}

		// Treat a PPARAMREF closure variable as equivalent to the
		// original variable.
		if(src->class == PPARAMREF) {
			if(leaks && debug['m'])
				warnl(src->lineno, "leaking closure reference %hN", src);
			escwalk(e, level, dst, src->closure);
		}
		break;

	case OPTRLIT:
	case OADDR:
		if(leaks) {
			src->esc = EscHeap;
			addrescapes(src->left);
			if(debug['m'])
				warnl(src->lineno, "%hN escapes to heap", src);
		}
		newlevel = level;
		if(level > MinLevel)
			newlevel--;
		escwalk(e, newlevel, dst, src->left);
		break;

	case OARRAYLIT:
		if(isfixedarray(src->type))
			break;
		// fall through
	case ODDDARG:
	case OMAKECHAN:
	case OMAKEMAP:
	case OMAKESLICE:
	case OMAPLIT:
	case ONEW:
	case OCLOSURE:
	case OCALLPART:
		if(leaks) {
			src->esc = EscHeap;
			if(debug['m'])
				warnl(src->lineno, "%hN escapes to heap", src);
		}
		break;

	case ODOT:
		escwalk(e, level, dst, src->left);
		break;

	case OINDEX:
		if(isfixedarray(src->left->type)) {
			escwalk(e, level, dst, src->left);
			break;
		}
		// fall through
	case OSLICE:
	case ODOTPTR:
	case OINDEXMAP:
	case OIND:
		newlevel = level;
		if(level > MinLevel)
			newlevel++;
		escwalk(e, newlevel, dst, src->left);
	}

recurse:
	for(ll=src->escflowsrc; ll; ll=ll->next)
		escwalk(e, level, dst, ll->n);

	e->pdepth--;
}

static void
esctag(EscState *e, Node *func)
{
	Node *savefn;
	NodeList *ll;
	Type *t;

	USED(e);
	func->esc = EscFuncTagged;
	
	// External functions are assumed unsafe,
	// unless //go:noescape is given before the declaration.
	if(func->nbody == nil) {
		if(func->noescape) {
			for(t=getinargx(func->type)->type; t; t=t->down)
				if(haspointers(t->type))
					t->note = mktag(EscNone);
		}
		return;
	}

	savefn = curfn;
	curfn = func;

	for(ll=curfn->dcl; ll; ll=ll->next) {
		if(ll->n->op != ONAME || ll->n->class != PPARAM)
			continue;

		switch (ll->n->esc&EscMask) {
		case EscNone:	// not touched by escflood
		case EscReturn:	
			if(haspointers(ll->n->type)) // don't bother tagging for scalars
				ll->n->paramfld->note = mktag(ll->n->esc);
			break;
		case EscHeap:	// touched by escflood, moved to heap
		case EscScope:	// touched by escflood, value leaves scope
			break;
		}
	}

	curfn = savefn;
}