code review 4634073: gc: Escape analysis.

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.
 //
-// Theory:
+// The base version before this file existed, active with debug['s']
+// == 0, assumes any node that has a reference to it created at some
+// point, may flow to the global scope except
+//   - if its address is dereferenced immediately with only CONVNOPs in
+//     between the * and the &
+//   - if it is for a closure variable and the closure executed at the
+//     place it's defined
 //
-//  A subset of all AST nodes holds values.  These are the 'expression'
-//  nodes.  Nodes have a scope: the function they are defined in or the
-//  global scope.  Nodes are visible in their scope and all scopes
-//  contained in it (closures).  The scope of a function parameter is
-//  that function.
+// Flag -s disables the old codepaths and switches on the code here:
 //
-//  A node ref can be a reference to another node n.  References
-//  to nodes are created with the & operator (OADDR).  Go slices, maps,
-//  and channels are references to arrays, runtime.Hashmap<K,V> and runtime.Chan<T>
-//  resp.  The last two are hidden from the programmer but relevant here.
-//  A final important case form the 'closure variables': any variable from
-//  an outer scope has it's reference implicitly taken.

[rsc, 2011/07/01 17:43:35]

it's == it is
you mean its
below too

[lvd, 2011/07/04 11:33:49]

Done.

+// First escfunc, escstmt and escexpr 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.
 //
-//  References can be 'dereferenced' explicitly or implictly:
-//    - the * operator (OIND) explicitly dereferences·
-//    - the slice index implicitly dereferences the slice (and accesses an element of
-//      the underlying array)
-//    - the map index operator implicitly dereferences the map (and selects an element of it)
-//    - a channel send or receive operation implicitly dereferences the channel (and selects
-//      the head or tail element of it's queue).
-//    - access to a 'closure variable' of an outer scope from the inner scope·
-//      happens by implictly dereferencing it.
+// 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.
 //
-//  The re-slice operator creates a new reference to the array the
-//  slice is a reference to, the index operator on an array does not
-//  dereference the array, as an array is not a reference. It just
-//  selects a part, like the ODOT does on a struct.
+// Watch the variables moved to the heap and parameters tagged as
+// unsafe with -m, more detailed analysis output with -mm
 //
-//  An expression node src, irrespective of whether it's a reference
-//  to another node or not, 'flows' to another node dst, flows(dst, src)
-//  if at any point during the execution of the program
-//    - src is assigned to dst
-//    - src is a struct and one of its fields is assigned to dst
-//    - dst is a struct and src is assigned to one of its fields
-//    - src is an array and one of its elements is assigned to dst
-//    - dst is an array, and src is assigned to one if its elements
-//    - dst is a runtime.Hashmap<K,V> and src is assigned to the key or value part of one of its elements

[rsc, 2011/07/01 17:43:35]

Please don't use C++ notation.  map[K]V,  chan T.

[lvd, 2011/07/04 11:33:49]

no, the map[K]V is a pointer to one of these things.  the distinction is
important.

-//    - src is a runtime.Hashmap<K,V> and the key or value part of one of its elements is assigned to dst
-//    - dst is a runtime.Chan<T> and src is sent to it (inserted as the head element)
-//    - src is a runtime.Chan<T> and dst is assigned the result of a receive operation (the tail element)
-//    - dst is a closure and src is a variable declared in its scope
-//    - dst is a closure and src is the implicit reference taken
-//      to a variable (not that variable itself!) in an enclosing scope. (this is
-//      really a special case of the previous one, combined with an assignment)
-//
-//  Finally, nodes may alias other nodes, which will be defined below, but in
-//  that case src also flows to dst if·
-//     - dst is an alias of src
-//     - src flows to dst', dst' is _not_ an alias of src and dst' is an alias of dst,·
-//
-//  (it may be tempting to just say src is an alias of dst or vice versa,
-//  but that introduces spurious flows)
-//
-//  This way, 'flow' forms edges in directed graph between nodes, so  we can
-//  extend the above pseudo definition of flow with it's transitive
-//  closure:·
-//    - there exists a node n such that flows(dst, n) and flows(n, src)
-//
-//  If we imagine the flow edges as horizontal, we can imagine
-//  referencing as taking a step down, and dereferencing taking a step
-//  up, and we can draw nice pictures to figure out what's going on.
-//  A struct may contain references at different levels in this
-//  picture, so be careful before drawing your whiteboard full of
-//  nonsense.  The Alias rule means that for any arrow you draw /to/
-//  an alias, you have to draw extra ones to the nodes it aliases.
-//
-//  Let's call the downstream of src the set of all nodes dst such
-//  that dst==src or flows(dst, src).  and vice versa the upstream of
-//  dst as the set of all nodes src such that dst==src or flows(dst, src).
-//
-//  Now we can precisely define:
-//  A node img is an alias of a node org, alias(img, org), if
-//     - img is the dereference of a node that is downstream to a reference of org
-//
-//  It looks circular, but it is just recursion: aliassing at one
-//  level happens through the flow of references a level below.
-//
-//  TODO: consider function this,in and out args in detail.
-//
-//  For most values all this is of passing interest and theoretical
-//  navel gazing, but any node src that is aliased to a node outside
-//  of src's scope must be moved to the heap, which is the whole point
-//  of this excercise.  (*note to self: i've muddled lexical scopes
-//  and activations here, untangle)
-//
-//  This can happen in 4 ways, all starting with a node src and a reference ref to it:
-//  - ref is assigned to a global variable
-//  - ref is returned from a function or is one of it's output parameters
-//  - ref is passed as a value to a function f as a parameter p (including the 'this' parameter) , and p leaks from f
-//  - ref is passed as a the function or a value to the function called in a go (OPROC) statement
-//
-//  (we can actually see the last case as a special case of the 3rd: go
-//  foo(a,b,c) is really runtime.closure(foo, a,b,c) and all of
-//  runtime.Closure's parameters are unsafe)
-//
-//  Whether the dereference actually happens is hard to trace, so we
-//  must assume the worst.  (maybe for unexported data we could do
-//  intra-package analysis and eliminate the cases where the ref never
-//  gets dereferenced, but why bother.)
-//
-// Since the implicit references of closure variables, by the
-// definition above, flow to the closure node this covers the cases
-// where the closure gets executed only in its scope or gets returned
-// or exectuted in a go (OPROC) statement.
-//
-// The base version of gc, before this file existed, assumes any node
-// that has a reference to it created at some point, may flow to the global scope except
-//   - if it's address is dereferenced immediately with only CONVNOPs in between
-//   - if it is for a closure variable and the closure executed at the place it's defined
-//
-// First we recurse over the ast of each function to dig out the
-// flow(dst,src) edges and store them in the dst's asrc field.
-// For the 4 cases mentioned above we store a flow(theSink, src) edge
-// to a fake node 'the Sink'.
-//
-// Then we have to complete the 'aliases' edges by following the upstream flows
-// from all dereferences to their origins.·
-//
-//
+
 #include "go.h"
 
-static void flows(Node* dst, Node* src);
-static void eastmtlist(Node* dst, NodeList *l);
-static void eastmt(Node* dst, Node *stmt);
-static void eaexpr(Node *dst, Node *expr);
-static void eawalk(Node *sink);
-
-// Fake node that all return values, global variables and
-// goroutine-used variables leak to.
-static Node theSink;
-
-// lists of derefererence nodes. indexed by derefdepth.
-static int dereftabsize;
-static NodeList** dereftab;
+static void escfunc(Node *func);
+static void escstmtlist(NodeList *stmts);
+static void escstmt(Node *stmt);
+static void escexpr(Node *dst, Node *expr);
+static void escexprcall(Node *dst, Node *callexpr);
+static void escflows(Node* dst, Node* src);
+static void escflood(Node *dst);
+static void escwalk(int level, Node *dst, Node *src);
+static void esctag(Node *func);
+
+// Fake node that all
+//   - return values and output variables
+//   - parameters on imported functions not marked 'safe'
+//   - assignments to global variables
+// flow to.
+static Node     theSink;
+
+static NodeList* dsts;          // all dst nodes
+static int      loopdepth;      // for detecting nested loop scopes
+static int      pdepth;         // for debug printing in recursions.
+static int      floodgen;       // loop prevention in flood/walk
+static Strlit*  safetag;        // gets slapped on safe parameters' field types for export
+static int      dstcount, edgecount;    // diagnostic
 
 void
-escanal()
-{
-        NodeList *l, *ll;
-
-        for(l=xtop; l; l=l->next) {
-                switch(l->n->op) {
-                case ODCL:
-                case OAS:
-                        eastmt(&theSink, l->n);
+escapes(void)
+{
+        NodeList *l;
+
+        theSink.op = ONAME;
+        theSink.class = PEXTERN;
+        theSink.sym = lookup(".sink");
+        theSink.escloopdepth = -1;
+
+        safetag = strlit("noescape");
+
+        // flow-analyze top level functions
+        for(l=xtop; l; l=l->next)
+                if(l->n->op == ODCLFUNC || l->n->op == OCLOSURE)
+                        escfunc(l->n);
+
+        // print("escapes: %d dsts, %d edges\n", dstcount, edgecount);
+
+        // visit the updstream of each dst, mark address nodes with
+        // addrescapes, mark parameters unsafe
+        for (l = dsts; l; l=l->next)
+                escflood(l->n);
+
+        // for all top level functions, tag the typenodes corresponding to the param nodes
+        for(l=xtop; l; l=l->next)
+                if(l->n->op == ODCLFUNC)
+                        esctag(l->n);
+}
+
+static void
+escfunc(Node *func)
+{
+        Node *savefn, *n;
+        NodeList *ll;
+        int saveld;
+
+        saveld = loopdepth;
+        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:
+                        // output parameters flow to the sink
+                        escflows(&theSink, ll->n);
+                        ll->n->escloopdepth = loopdepth;
                         break;
-                case ODCLFUNC:
-                        curfn = l->n;
-                        flows(&theSink, l->n);  // maybe only exported ones?
-                        // all parameters, in and out, flow to the function object itself
-                        for (ll=l->n->dcl; ll; ll=ll->next)
-                                if (ll->n->op == ONAME)
-                                        flows(l->n, ll->n);
-                        eastmtlist(N, l->n->nbody);
-                        curfn = nil;
+                case PPARAM:
+                        ll->n->esc = EscNone;   // prime for escflood later
+                        ll->n->escloopdepth = loopdepth;
                         break;
                 }
         }
 
-        eawalk(&theSink);
-}
-
-static void
-eastmtlist(Node* dst, NodeList* l)
-{
-        for (; l; l = l->next)
-                eastmt(dst, l->n);
-}
-
-static void
-eastmt(Node* fun, Node *stmt)
-{
-        int cl, cr;
+        // walk will take the address of cvar->closure later and assign it to cvar.
+        // handle that here by linking a fake oaddr node directly to the closure.
+        for (ll=curfn->cvars; ll; ll=ll->next) {
+                if(ll->n->op == OXXX)  // see dcl.c:398
+                        continue;
+
+                n = nod(OADDR, ll->n->closure, N);
+                n->lineno = ll->n->lineno;
+                typecheck(&n, Erv);
+                escexpr(curfn, n);
+        }
+
+        escstmtlist(curfn->nbody);
+        curfn = savefn;
+        loopdepth = saveld;
+}
+
+static void
+escstmtlist(NodeList* stmts)
+{
+        for(; stmts; stmts=stmts->next)
+                escstmt(stmts->n);
+}
+
+static void
+escstmt(Node *stmt)
+{
+        int cl, cr, lno;
         NodeList *ll, *lr;
+        Node *dst;
 
         if(stmt == N)
                 return;
 
-        if (stmt->trecur)
-                return;
-        stmt->trecur = 1;
-
-        setlineno(stmt);
-
-        if (stmt->typecheck == 0 && stmt->op != ODCL) {  // todo, something with OAS2
-                dump("eastmt missing typecheck", stmt);
-                fatal("Missing typecheck.");
-        }
-
-        if (fun && fun != &theSink && fun->op != OCLOSURE)
-                fatal("eastmt fun is not a closure: %N", fun);
-
-        eastmtlist(fun, stmt->ninit);
+        lno = setlineno(stmt);
+
+        if(stmt->typecheck == 0 && stmt->op != ODCL) {   // TODO something with OAS2
+                dump("escstmt missing typecheck", stmt);
+                fatal("missing typecheck.");
+        }
+
+        // Common to almost all statements, and nil if n/a.
+        escstmtlist(stmt->ninit);
+
+        if(debug['m'] > 1)
+                print("%L:[%d] %#S statement: %#N\n", lineno, loopdepth,
+                      (curfn && curfn->nname) ? curfn->nname->sym : S, stmt);
 
         switch(stmt->op) {
-        default:
-                // can get here with typecheck errors
-                dump("eastmt", stmt);
-                fatal("eastmt %O", stmt->op);
-                break;
-
         case ODCL:
         case ODCLFIELD:
-                // a declaration ties the node to the current function
-                eaexpr(fun, stmt->left);
-                break;
-
-        case ODCLCONST:
-        case ODCLTYPE:
-        case OBREAK:
-        case OCONTINUE:
-        case OXFALL:
-        case OGOTO:
-        case OLABEL:
-        case OEMPTY:
-        case ORECOVER:
-                // all harmless
-                break;
-
-        case  OBLOCK:
-                eastmtlist(fun, stmt->list);
+                // a declaration ties the node to the current
+                // function, but we already have that edge in
+                // curfn->dcl and will follow it explicitly in
+                // escflood to avoid storing redundant information
+                // What does have to happen here is note if the name
+                // is declared inside a looping scope.
+                stmt->left->escloopdepth = loopdepth;
+                break;
+
+        case OLABEL:  // TODO: new loop/scope only if there are backjumps to it.
+                loopdepth++;
+                break;
+
+        case OBLOCK:
+                escstmtlist(stmt->list);
                 break;
 
         case OFOR:
                 if(stmt->ntest != N) {
-                        eastmtlist(fun, stmt->ntest->ninit);
-                        eaexpr(N, stmt->ntest);
-                }
-                eastmt(N, stmt->nincr);
-                eastmtlist(fun, stmt->nbody);
-                break;
-
-        case ORANGE:            //  for  <list> = range <right> { <nbody> }
+                        escstmtlist(stmt->ntest->ninit);
+                        escexpr(N, stmt->ntest);
+                }
+                escstmt(stmt->nincr);
+                loopdepth++;
+                escstmtlist(stmt->nbody);
+                loopdepth--;
+                break;
+
+        case ORANGE:            //  for  <list> = range <right> { <nbody> }
                 switch(stmt->type->etype) {
-                case TARRAY:    // i, v = range sliceorarrayorstring
-                case TSTRING:
+                case TSTRING:   // never flows
+                        escexpr(stmt->list->n, N);
                         if(stmt->list->next)
-                                eaexpr(stmt->list->next->n, stmt->right);
-                        break;                  
-                case TMAP:      // k, v = range map
-                        eaexpr(stmt->list->n, stmt->right);
+                                escexpr(stmt->list->next->n, N);
+                        escexpr(N, stmt->right);
+                        break;
+                case TARRAY:    // i, v = range sliceorarray
+                        escexpr(stmt->list->n, N);
                         if(stmt->list->next)
-                                eaexpr(stmt->list->next->n, stmt->right);
+                                escexpr(stmt->list->next->n, stmt->right);
+                        break;
+                case TMAP:      // k [, v] = range map
+                        escexpr(stmt->list->n, stmt->right);
+                        if(stmt->list->next)
+                                escexpr(stmt->list->next->n, stmt->right);
                         break;
                 case TCHAN:     // v = range chan
-                        eaexpr(stmt->list->n, stmt->right);
+                        escexpr(stmt->list->n, stmt->right);
                         break;
                 }
-                eastmtlist(fun, stmt->nbody);
+                loopdepth++;
+                escstmtlist(stmt->nbody);
+                loopdepth--;
                 break;
 
         case OIF:
-                eaexpr(N, stmt->ntest);
-                eastmtlist(fun, stmt->nbody);
-                eastmtlist(fun, stmt->nelse);
+                escexpr(N, stmt->ntest);
+                escstmtlist(stmt->nbody);
+                escstmtlist(stmt->nelse);
                 break;
 
         case OSELECT:
                 for(ll=stmt->list; ll; ll=ll->next) {  // cases
-                        eastmt(fun, ll->n->left);
-                        eastmtlist(fun, ll->n->nbody);
-                }
-                break;
-
-        case OSELRECV2:
-                eaexpr(N, stmt->ntest);
+                        escstmt(ll->n->left);
+                        escstmtlist(ll->n->nbody);
+                }
+                break;
+
+        case OSELRECV2:   // v, ok := <-ch  ntest:ok
+                escexpr(N, stmt->ntest);
                 // fallthrough
-        case OSELRECV:
-                eaexpr(stmt->left, stmt->right);
+        case OSELRECV:    // v := <-ch   left: v  right->op = ORECV
+                escexpr(N, stmt->left);
+                escexpr(stmt->left, stmt->right);
                 break;
 
         case OSWITCH:
                 if(stmt->ntest && stmt->ntest->op == OTYPESW) {
-                        eaexpr(stmt->ntest->left, stmt->ntest->right);
-                        for(ll=stmt->list; ll; ll=ll->next)
-                                eastmtlist(fun, ll->n->nbody);
+                        for(ll=stmt->list; ll; ll=ll->next) {  // cases
+                                // ntest->right is the argument of the .(type),
+                                // ll->n->nname is the variable per case
+                                escexpr(ll->n->nname, stmt->ntest->right);
+                                escstmtlist(ll->n->nbody);
+                        }
                 } else {
-                        eaexpr(fun, stmt->ntest);
+                        escexpr(N, stmt->ntest);
                         for(ll=stmt->list; ll; ll=ll->next) {  // cases
-                                for (lr=ll->n->list; lr; lr=lr->next) {
-                                        eaexpr(fun, lr->n);
-                                }
-                                eastmtlist(fun, ll->n->nbody);
+                                for(lr=ll->n->list; lr; lr=lr->next)
+                                        escexpr(N, lr->n);
+                                escstmtlist(ll->n->nbody);
                         }
                 }
                 break;
 
-        case OAS: 
+        case OAS:
         case OASOP:
-                eaexpr(stmt->left, stmt->right);
-                break;
-
-        // escape analysis happens after typecheck, so the
-        // OAS2xxx have already been substituted.
+                escexpr(stmt->left, stmt->right);
+                break;
+
+                // escape analysis happens after typecheck, so the
+                // OAS2xxx have already been substituted.
         case OAS2:      // x,y = a,b
-        case OAS2FUNC:  // x,y,z = f()
                 cl = count(stmt->list);
                 cr = count(stmt->rlist);
-                if (cl > 1 && cr == 1) {
+                if(cl > 1 && cr == 1) {
                         for(ll=stmt->list; ll; ll=ll->next)
-                                eaexpr(ll->n, stmt->rlist->n);  // no, f's outputparams go here
-                } else { 
+                                escexpr(ll->n, stmt->rlist->n);
+                } else {
                         if(cl != cr)
-                                fatal("eastmt: bad OAS2: %N", stmt);
+                                fatal("escstmt: bad OAS2: %N", stmt);
                         for(ll=stmt->list, lr=stmt->rlist; ll; ll=ll->next, lr=lr->next)
-                                eaexpr(ll->n, lr->n);
-                }
-                break;
-                
+                                escexpr(ll->n, lr->n);
+                }
+                break;
+
         case OAS2RECV:          // v, ok = <-ch
         case OAS2MAPR:          // v, ok = m[k]
         case OAS2DOTTYPE:       // v, ok = x.(type)
-        case OAS2MAPW:          // m[k] = x, ok
-                eaexpr(stmt->list->n, stmt->rlist->n);
+                escexpr(stmt->list->n, stmt->rlist->n);
+                escexpr(stmt->list->next->n, N);
+                break;
+
+        case OAS2MAPW:          // m[k] = x, ok.. stmt->list->n is the INDEXMAP, k is handled in escexpr(dst...)
+                escexpr(stmt->list->n, stmt->rlist->n);
+                escexpr(N, stmt->rlist->next->n);
                 break;
 
         case ORECV:             // unary <-ch as statement
-                eaexpr(N, stmt->left);
+                escexpr(N, stmt->left);
                 break;
 
         case OSEND:             // ch <- x
-                eaexpr(stmt->left, stmt->right);
-                break;
-
-        case OCOPY:     // second arguments leaks to the first
-                eaexpr(stmt->left, stmt->right);
+                escexpr(&theSink, stmt->right);  // for now. TODO escexpr(stmt->left, stmt->right);
+                break;
+
+        case OCOPY:     // todo: treat as *dst=*src instead of as dst=src
+                escexpr(stmt->left, stmt->right);
+                break;
+
+        case OAS2FUNC:  // x,y,z = f()
+                for(ll = stmt->list; ll; ll=ll->next)
+                        escexpr(ll->n, N);
+                escexpr(N, stmt->rlist->n);
                 break;
 
         case OCALLINTER:
         case OCALLFUNC:
         case OCALLMETH:
-                stmt->trecur = 0;
-                eaexpr(N, stmt);
-                break;
-
+                escexpr(N, stmt);
+                break;
+
+        case OPROC:
         case ODEFER:
-                eastmt(fun, stmt->left);
+                // stmt->left is a (pseud)ocall, stmt->left->left is
+                // the function being called.  if this defer is at
+                // loopdepth >1, everything leaks.  TODO this is
+                // overly conservative, it's enough if it leaks to a
+                // fake node at the function's top level
+                dst = &theSink;
+                if (stmt->op == ODEFER && loopdepth <= 1)
+                        dst = nil;
+                escexpr(dst, stmt->left->left);
+                for(ll=stmt->left->list; ll; ll=ll->next)
+                        escexpr(dst, ll->n);
                 break;
 
         case ORETURN:
-                for (ll=stmt->list; ll; ll=ll->next)
-                        eaexpr(&theSink, ll->n);  // dont leak to theSink, flow to the PPARAMOUTS in stmt->curfn->decl
-                break;
-
-        case OPROC:
-                // stmt->left is a (pseud)ocall, consider all arguments leaking
-                // stmt->left->left is the function being called. if it's a
-                // method call x.foo, x leaks TODO but other things not..
-                eaexpr(&theSink, stmt->left->left);
-                for (ll=stmt->left->list; ll; ll=ll->next)
-                        eaexpr(&theSink, ll->n);
+                for(ll=stmt->list; ll; ll=ll->next)
+                        escexpr(&theSink, ll->n);
                 break;
 
         case OCLOSE:
         case OPRINT:
         case OPRINTN:
-                eaexpr(N, stmt->left);
+                escexpr(N, stmt->left);
+                for(ll=stmt->list; ll; ll=ll->next)
+                        escexpr(N, ll->n);
                 break;
 
         case OPANIC:
                 // Argument could leak through recover.
-                eaexpr(&theSink, stmt->left);
-                break;
-        }
-
-        stmt->trecur = 0;
-}
-
-static int isreftype(Type* t) {
-        if (t != T)
-                switch(t->etype) {
-                case TARRAY:
-                        if(isfixedarray(t))
-                                break;
+                escexpr(&theSink, stmt->left);
+                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
+escexpr(Node *dst, Node *expr)
+{
+        int lno;
+        NodeList *ll;
+
+        if(isblank(dst)) dst = N;
+
+        // the lhs of an assignment needs recursive analysis too
+        // these are the only interesting cases
+        // todo:check channel case
+        if(dst) {
+                setlineno(dst);
+
+                switch(dst->op) {
+                case OINDEX:
+                case OSLICE:
+                        escexpr(N, dst->right);
+
+                        // slice:  "dst[x] = src"  is like *(underlying array)[x] = src
+                        // TODO maybe this never occurs b/c of OSLICEARR and it's inserted OADDR
+                        if(!isfixedarray(dst->left->type))
+                                goto doref;
+
+                        // fallthrough;  treat "dst[x] = src" as "dst = src"
+                case ODOT:            // treat "dst.x  = src" as "dst = src"
+                        escexpr(dst->left, expr);
+                        return;
+
+                case OINDEXMAP:
+                        escexpr(&theSink, dst->right);  // map key is put in map
                         // fallthrough
-                case TCHAN:
-                case TMAP:
-                        return 1;
-                }
-        return 0;
-}
-
-static int
-derefdepth(Node *n)
-{
-        int d;
-        Type *t;
-
-        d = 0;
-        for (t = n->type; t && isptr[t->etype]; t = t->type)
-                d++;
-        if (isreftype(t)) d++;
-        return d;
-}
-
-
-static int
-isderef(Node* n)
-{
-        switch(n->op) {
-        case OINDEX:
-                if(isfixedarray(n->left->type))
-                        break;
-        case OIND:
-        case ODOTPTR:
-                return 1;
-        }
-
-        if (isreftype(n->type))
-                return 1;
-        return 0;
-}
-
-static void·
-adderef(Node *n) {
-        int d, s;
-
-        d = derefdepth(n);
-        if (d >= dereftabsize) {
-                s = dereftabsize;
-                if (dereftabsize == 0)
-                        dereftabsize = 16;
-                else
-                        dereftabsize = d + (d >> 2);
-                dereftab = realloc(dereftab, dereftabsize * sizeof(dereftab[0]));
-                memset(dereftab + s, 0, (dereftabsize - s) * sizeof(dereftab[0]));
-        }
-        dereftab[d] = list(dereftab[d], n);
-}
-
-static void
-flows(Node* dst, Node* src)
-{
-        if (dst == nil || src == nil)
-                return;
-
-        if (dst == src)
-                fatal("flow to self: %N\n", dst);
-
-        dst->asrc = list(dst->asrc, src);
-
-        if (isderef(src)) adderef(src);
-        if (isderef(dst)) adderef(dst);
-
-        if (debug['s']>1) {
-        if (dst != &theSink)
-                print("%L %S::%N <- %N", lineno, curfn ? curfn->nname->sym : S, dst, src);
-        else
-                print("%L %S:: leaks %N", lineno, curfn ? curfn->nname->sym :S, src);
-
-        if (src->op == OADDR) print(" <= %#N", src->left);
-        print("\n");
-        }
-}
-
-static void
-eaexpr(Node *dst, Node *expr)
-{
-        NodeList *ll;
-
-        if(expr == N || expr == dst)
-                return;
-
-        if (expr->trecur)
-                return;
-        expr->trecur = 1;
-
-        setlineno(expr);
-
-        if (expr->typecheck == 0  && expr->op != ONONAME) {    // TODO where do these come from
-                dump("eaexpr missing typecheck", expr);
-                fatal("Missing typecheck.");
-        }
-
-        if (debug['s'] > 2)
-                print("%L %S:: ... examining %N <= %N\n", lineno, curfn ? curfn->nname->sym : S, dst, expr);
-
-
-//      if (dst && dst != &theSink && !dst->type) dump("typeless dst", dst);
-········
-        if (dst) {
-                switch(dst->op) {
-                // aliasing happens here
                 case OIND:
                 case ODOTPTR:
-                        dst = &theSink;
-                        break;
-
-                case OINDEXMAP:
-                        dst = dst->left;
-                        break;
-
-                case OINDEX:
-                        if(isfixedarray(dst->left->type))
-                                dst = dst->left;
-                        else
-                                dst = &theSink;
-                }
-
-                // channels and maps are reference types, meaning
-                // they can alias all over the place, treat like OIND
-                if (isreftype(dst->type))
-                        dst = &theSink;
-        }
+                case OSLICEARR:  // ->left  is the OADDR of the array
+                doref:
+                        escexpr(N, dst->left);
+                        // assignment to dereferences: for now we lose track
+                        escexpr(&theSink, expr);
+                        return;
+                }
+
+        }
+
+        if(expr == N || expr->op == ONONAME || expr->op == OXXX)
+                return;
+
+        if(expr->typecheck == 0 && expr->op != OKEY) {
+                dump("escexpr missing typecheck", expr);
+                fatal("Missing typecheck.");
+        }
+
+        lno = setlineno(expr);
+        pdepth++;
+
+        if(debug['m'] > 1)
+                print("%L:[%d] %#S \t%hN %.*s<= %hN\n", lineno, loopdepth,
+                      (curfn && curfn->nname) ? curfn->nname->sym : S, dst,
+                      2*pdepth, ".\t.\t.\t.\t.\t", expr);
+
 
         switch(expr->op) {
-        default:
-                // if we get here, typecheck has probably already complained
-                dump("eaexpr", expr);
-                fatal("eaexpr %O", expr->op);
-                break;
-
-        case OADDR:
-                flows(dst, expr);         // dst = &x
-                // to the right of & there can be only an array-,map- or struct- literal, a name (not of a func),·
-                // an index or member selection operation &x[y] (OINDEX),  &x.y (ODOT).·
-                // or an indirection: &*x (OIND), &(*x).y (ODOTPTR, written as &x.y , but x of pointer type)
-                // in the last two cases, the flow is actually not interrupted,
-                if (expr->left->op == OIND || expr->left->op == ODOTPTR)
-                        eaexpr(dst, expr->left);····
-                else
-                        eaexpr(N, expr->left);····
-                break;
-
-        case OIND:                      // dst = *y -> who cares,
-                // even if dst = * .... &x, that doesnt mean &x flows to dst, just x
-                // if this OIND is to the right of an OADDR, things are different, but that's handled above.
-                eaexpr(N, expr->left);
-                break;
-
+        case OADDR:     // dst = &x
+        case OIND:      // dst = *x
+        case ODOTPTR:   // dst = (*x).f
+                // restart the recursion at x to figure out where it came from
+                escexpr(expr->left, expr->left);
+                // fallthrough
         case ONAME:
-        case ONONAME:  // not typechecked yet?
         case OPARAM:
-                flows(dst, expr);
+                // loopdepth was set in the defining statement or function header
+                escflows(dst, expr);
                 break;
 
         case OARRAYLIT:
         case OSTRUCTLIT:
-                flows(dst, expr);
-                // ll->n is key, left is fieldname or constant index
-                for (ll=expr->list; ll; ll=ll->next)
-                        eaexpr(expr, ll->n->right);
-                break;
-        case OMAPLIT:            ·······
-                flows(dst, expr);
-                for (ll=expr->list; ll; ll=ll->next) { // ll->n is key,·
-                        eaexpr(expr, ll->n->left);
-                        eaexpr(expr, ll->n->right);
-                }
-                break;
-
-        case OCOMPLIT:
-        case OLITERAL:
-        case ORECOVER:
-                break;
-
-        // harmless unary
-        case ONOT:      case OCOM:
-        case OCAP:      case OLEN:
-        case OREAL:     case OIMAG:
-        case OARRAYBYTESTR:
-        case OARRAYRUNESTR:
-        case OSTRARRAYBYTE:
-        case OSTRARRAYRUNE:
-        case ORUNESTR:
-                eaexpr(N, expr->left);
-                break;
-
-        // harmless binary
-        case OADD:      case OAND:      case OANDAND:
-        case OANDNOT:   case ODIV:      case OEQ:
-        case OGE:       case OGT:       case OLE:
-        case OLT:       case OLSH:      case ORSH:
-        case OMOD:      case OMUL:      case ONE:
-        case OOR:       case OOROR:     case OSUB:
-        case OXOR:      case OADDSTR:   case OASOP:
-        case OCMPIFACE: case OCMPSTR:   case OCOMPLEX:
-        case OPLUS: case OMINUS:
-                eaexpr(N, expr->left);
-                eaexpr(N, expr->right);
-                break;
-
-        // unaries that pass the value through
-        case OCONV:
+        case OMAPLIT:
+                expr->escloopdepth = loopdepth;
+                escflows(dst, expr);
+                for(ll=expr->list; ll; ll=ll->next) {
+                        escexpr(expr, ll->n->left);
+                        escexpr(expr, ll->n->right);
+                }
+                break;
+
+        case OMAKECHAN:
+        case OMAKEMAP:
+        case OMAKESLICE:
+        case ONEW:
+                expr->curfn = curfn;  // should have been done in parse, but patch it up here.
+                expr->escloopdepth = loopdepth;
+                escflows(dst, expr);
+                // first arg is type, all others need checking
+                for(ll=expr->list->next; ll; ll=ll->next)
+                        escexpr(N, ll->n);
+                break;
+
+        case OCLOSURE:
+                expr->curfn = curfn;  // should have been done in parse, but patch it up here.
+                expr->escloopdepth = loopdepth;
+                escflows(dst, expr);
+                escfunc(expr);
+                break;
+
+        // end of the leaf cases. no calls to escflows() in the cases below.
+
+
+        case OCONV:     // unaries that pass the value through
         case OCONVIFACE:
         case OCONVNOP:
         case ODOTTYPE:
         case ODOTTYPE2:
-        case ORECV:    // leaks the whole channel
-                eaexpr(dst, expr->left);
+        case ORECV:     // leaks the whole channel
+        case ODOTMETH:  // expr->right is just the field or method name
+        case ODOTINTER:
+        case ODOT:
+                escexpr(dst, expr->left);
                 break;
 
         case OCOPY:
                 // left leaks to right, but the return value is harmless
-                eaexpr(expr->left, expr->right);
+                // TODO: treat as *dst = *src, rather than as dst = src
+                escexpr(expr->left, expr->right);
                 break;
 
         case OAPPEND:
-                eaexpr(dst, expr->list->n);
-                for (ll=expr->list->next; ll; ll=ll->next)
-                        eaexpr(expr->list->n, ll->n);
-                break;
-
-        // todo: this and arguments don't leak to the sink but to expr->left->dcl
+                // See TODO for OCOPY
+                escexpr(dst, expr->list->n);
+                for(ll=expr->list->next; ll; ll=ll->next)
+                        escexpr(expr->list->n, ll->n);
+                break;
+
         case OCALLMETH:
+        case OCALLFUNC:
         case OCALLINTER:
-                eaexpr(&theSink, expr->left->left); // DOTMETH->this or DOTINTER->this
-                // fallthrough
+                // Moved to separate function to isolate the hair.
+                escexprcall(dst, expr);
+                break;
+
+        case OSLICEARR:  // like an implicit OIND to the underlying buffer, but typecheck has inserted an OADDR
+        case OSLICESTR:
+        case OSLICE:
+        case OINDEX:
+        case OINDEXMAP:
+                // the big thing flows, the keys just need checking
+                escexpr(dst, expr->left);
+                escexpr(N, expr->right);  // expr->right is the OKEY
+                break;
+
+        default: // all other harmless leaf, unary or binary cases end up here
+                escexpr(N, expr->left);
+                escexpr(N, expr->right);
+                break;
+        }
+
+        pdepth--;
+        lineno = lno;
+}
+
+
+// This is a bit messier than fortunate, pulled out of escexpr's big
+// switch for clarity.  We either have the paramnodes, which may be
+// connected to other things throug flows or we have the parameter type
+// nodes, which may be marked 'n(ofloworescape)'. Navigating the ast is slightly
+// different for methods vs plain functions and for imported vs
+// this-package
+static void
+escexprcall(Node *dst, Node *expr)
+{
+        NodeList *ll, *lr;
+        Node *fn;
+        Type *t, *fntype, *thisarg, *inargs;
+
+        fn = nil;
+        fntype = nil;
+
+        switch(expr->op) {
         case OCALLFUNC:
-                eaexpr(N, expr->left);  // the function itself
-                for (ll=expr->list; ll; ll=ll->next)
-                        eaexpr(&theSink , ll->n);
-                break;
-
-        case ODOTMETH:
-        case ODOTINTER:
-        case ODOT:
+                fn = expr->left;
+                escexpr(N, fn);
+                fntype = fn->type;
+                break;
+
+        case OCALLMETH:
+                fn = expr->left->right;  // ODOTxx name
+                fn = fn->sym->def;       // resolve to definition if we have it
+                if(fn)
+                        fntype = fn->type;
+                else
+                        fntype = expr->left->type;
+                break;
+
+        case OCALLINTER:
+                break;
+
+        default:
+                fatal("escexprcall called with non-call expression");
+        }
+
+        if(fn && fn->ntype) {
+                if(debug['m'] > 2)
+                        print("escexprcall: have param nodes: %N\n", fn->ntype);
+
+                if(expr->op == OCALLMETH) {
+                        if(debug['m'] > 2)
+                                print("escexprcall: this: %N\n",fn->ntype->left->left);
+                        escexpr(fn->ntype->left->left, expr->left->left);
+                }
+
+                // lr->n is the dclfield, ->left is the ONAME param node
+                for(ll=expr->list, lr=fn->ntype->list; ll && lr; ll=ll->next) {
+                        if(debug['m'] > 2)
+                                print("escexprcall: field param: %N\n", lr->n->left);
+                        if (lr->n->left)
+                                escexpr(lr->n->left, ll->n);
+                        else
+                                escexpr(&theSink, ll->n);
+                        if(lr->n->left && !lr->n->left->isddd)
+                                lr=lr->next;
+                }
+                return;
+        }
+
+        if(fntype) {
+                if(debug['m'] > 2)
+                        print("escexprcall: have param types: %T\n", fntype);
+
+                if(expr->op == OCALLMETH) {
+                        thisarg = getthisx(fntype);
+                        t = thisarg->type;
+                        if(debug['m'] > 2)
+                                print("escexprcall: this: %T\n", t);
+                        if(!t->note || strcmp(t->note->s, safetag->s) != 0)
+                                escexpr(&theSink, expr->left->left);
+                        else
+                                escexpr(N, expr->left->left);
+                }
+
+                inargs = getinargx(fntype);
+                for(ll=expr->list, t=inargs->type; ll; ll=ll->next) {
+                        if(debug['m'] > 2)
+                                print("escexprcall: field type: %T\n", t);
+                        if(!t->note || strcmp(t->note->s, safetag->s))
+                                escexpr(&theSink, ll->n);
+                        else
+                                escexpr(N, ll->n);
+                        if(t->down)
+                                t=t->down;
+                }
+
+                return;
+        }
+
+        // fallthrough if we don't have enough information:
+        // can only assume all parameters are unsafe
+        // OCALLINTER always ends up here
+
+        if(debug['m']>1 && expr->op != OCALLINTER) {
+                // dump("escexprcall", expr);
+                print("escexprcall: %O, no nodes, no types: %N\n", expr->op, fn);
+        }
+
+        escexpr(&theSink,  expr->left->left);  // the this argument
+        for(ll=expr->list; ll; ll=ll->next)
+                escexpr(&theSink, ll->n);
+}
+
+// Store the link src->dst in dst, throwing out some quick wins.
+static void
+escflows(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);
+
+        // Assignments to global variables get lumped into theSink.
+        if (dst->op == ONAME && dst->class == PEXTERN)
+                dst = &theSink;
+
+        if (dst->escflowsrc == nil) {
+                dsts = list(dsts, dst);
+                dstcount++;
+        }
+        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/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(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", floodgen, dst,
+                      (dst->curfn && dst->curfn->nname) ? dst->curfn->nname->sym : S,
+                      dst->escloopdepth);
+
+        for (l = dst->escflowsrc; l; l=l->next) {
+                floodgen++;
+                escwalk(0, dst, l->n);
+        }
+}
+
+static void
+escwalk(int level, Node *dst, Node *src)
+{
+        NodeList* ll;
+        int leaks;
+
+        if (src->escfloodgen == floodgen)
+                return;
+        src->escfloodgen = floodgen;
+
+        if(debug['m']>1)
+                print("escwalk: level:%d depth:%d %.*s %hN scope:%#S[%d]\n",
+                      level, pdepth, pdepth, "\t\t\t\t\t\t\t\t\t\t", src,
+                      (src->curfn && src->curfn->nname) ? src->curfn->nname->sym : S, src->escloopdepth);
+
+        pdepth++;
+
+        leaks = (level <= 0) && (dst->escloopdepth < src->escloopdepth);
+
+        switch(src->op) {
+        case ONAME:
+                if (src->class == PPARAM && leaks && src->esc == EscNone) {
+                        src->esc = EscScope;
+                        if(debug['m'])
+                                print("%L:leaking param: %hN\n", src->lineno, src);
+                }
+                break;
+
+        case OADDR:
+                if (leaks)
+                        addrescapes(src->left);
+                escwalk(level-1, dst, src->left);
+                break;
+
+        case OINDEX:
+                if(isfixedarray(src->type))
+                        break;
+        case OSLICE:
         case ODOTPTR:
-                // pretend all of the struct leaked
-                // expr->right is just an (untypechecked) ONAME
-                eaexpr(dst, expr->left);
-                break;
-
-        case OSLICE:   // the big thing leaks, the keys just need checking
-        case OSLICEARR:
-        case OSLICESTR:
-                eaexpr(dst, expr->left);
-                eaexpr(N, expr->right->left);  // the OKEY
-                eaexpr(N, expr->right->right);
-                break;
-
-        case OINDEX:···
         case OINDEXMAP:
-                eaexpr(dst, expr->left);
-                eaexpr(N, expr->right);
-                break;
-
-        case OMAKECHAN:
-        case OMAKEMAP:
-        case OMAKESLICE:
-        case ONEW:              // first arg is type, all others need checking
-                for (ll=expr->list->next; ll; ll=ll->next)
-                        eaexpr(N, ll->n);
-                flows(dst, expr);
-                break;
-
-        case OCLOSURE:
-                flows(dst, expr);  // the closure flows to the lhs of the assignment, or to theSink if we're in a return.
-                // all parameters, in and out, flow to the function object itself
-                for (ll=expr->dcl; ll; ll=ll->next)
-                        if (ll->n->op == ONAME)
-                                flows(l->n, ll->n);
-
-                // the cvars will have their address taken by walk.  introduce a fake OADDR node so eawalk can pick that up.
-                for (ll=expr->cvars; ll; ll=ll->next)
-                        flows(expr, nod(OADDR, ll->n, N));
-                eastmtlist(expr, expr->nbody);  // the declarations in the body flow to the closure
-                break;
-
-        }
-
-        expr->trecur = 0;
-}
-
-static int depth;
-
-static void eawalk(Node *sink) {
+        case OIND:
+                escwalk(level+1, dst, src->left);
+        }
+
+        for (ll=src->escflowsrc; ll; ll=ll->next)
+                escwalk(level, dst, ll->n);
+
+        pdepth--;
+}
+
+static void
+esctag(Node *func)
+{
+        Node *savefn;
         NodeList *ll;
 
-        if (debug['s']>1)
-        print("eawalk %d: %N\n", depth, sink);
-
-        depth++;
-        ll = sink->asrc;
-        sink->asrc = nil;
-
-        for (; ll; ll=ll->next)
-                eawalk(ll->n);
-
-        if (sink->op == OADDR) {
-                addrescapes(sink->left);
-                eawalk(sink->left);
-        }
-
-        if (sink->op == ONAME && sink->class == PPARAMREF) {
-                addrescapes(sink->closure);
-        }
-
-        depth--;
-}
-
-
-
-
-
-
-
-#if 0
-
-        for(tl=tstruct->type; tl; tl=tl->down) {
-                t = tl->type;
-                if(tl->isddd) {
-                        if(isddd) {
-                                if(nl == nil)
-                                        goto notenough;
-                                if(nl->next != nil)
-                                        goto toomany;
-                                n = nl->n;
-                                setlineno(n);
-                                if(n->type != T) {
-                                        nl->n = assignconv(n, t, desc);
-                                        if (call) argused(call, tl, n);
-                                }
-                                goto out;
-                        }
-                        for(; nl; nl=nl->next) {
-                                n = nl->n;
-                                setlineno(nl->n);
-                                if(n->type != T) {
-                                        nl->n = assignconv(n, t->type, desc);
-                                        if (call) argused(call, tl, n);
-                                }
-                        }
-                        goto out;
-                }·
-
-
-// mark that value has been used as the argument arg
-static void argused(Node* func, Type* arg, Node* val) {
-//      if (arg->sym && arg->sym->pkg == localpkg)
-//              arg->note = strlit("used");
-//      print("Using %N :: %#T = %N\n", func, arg, val);
-}
-
-
-/*
- * type check function definition
- */
-static void
-escanalfunc(Node *n)
-{
-//      Type *t, *t1, *rcvr;
-        Type *t, *rcvr;
-
-        typecheck(&n->nname, Erv | Easgn);
-        if((t = n->nname->type) == T)
-                return;
-        n->type = t;
-
-        print("typecheckfunc %T\n", n->type);
-        for(t1=getinargx(t)->type; t1; t1=t1->down) {
-                if (isptr[t1->type->etype])
-                        t1->note = strlit("leaks");
-                print("\t%T\n", t1);
-
-        }
-
-        rcvr = getthisx(t)->type;
-        if(rcvr != nil && n->shortname != N && !isblank(n->shortname))
-                addmethod(n->shortname->sym, t, 1);
-}
-
-#endif
+        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) {
+                case EscNone:   // not touched by escflood
+                        if (haspointers(ll->n->type)) // don't bother tagging for scalars
+                                ll->n->paramfld->note = safetag;
+                case EscHeap:   // touched by escflood, moved to heap
+                case EscScope:  // touched by escflood, value leaves scope
+                        break;
+                default:
+                        fatal("messed up escape tagging: %N::%N", curfn, ll->n);
+                }
+        }
+
+        curfn = savefn;
+}