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> (abusing C++ notation) resp.
-//      The last two are hidden from the programmer but relevant here.
-//    - 'closure variables': any variable from an outer scope has its
-//      reference implicitly taken.
+// 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 its operand
-//    - 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 its 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
-//    - 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) from it
-//    - 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)
-//    - WHAT ABOUT lvalue expressions and function expressions? leak to fun?
-//
-//  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 in cases like this:  x=&y0, x=&y1, y0=z)
-//
-//  This way, 'flow' forms edges in directed graph between nodes, so  we can
-//  extend the above 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.  all calls
-//  end up as edges to the same in parameter nodes and from the same
-//  out parameter nodes.  for imported functions we dont have the full
-//  graph, just if parameters are safe or not, and for exported
-//  functions pretend the outparams flow to theSink.  one interesting
-//  extra case: if we mark the return value of constructors and the
-//  like as 'only flows from here' we can tell the gc its safe to delete
-//  them if the retval doesnt leave the calling function.
-//
-//  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 its output parameters
-//  - ref is passed as a value to a function f as a parameter p (including the 'this' parameter) ,·
-//    and the downstream of p includes nodes outside of the scope 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, closurerefs, a,b,c)
-//  and all of runtime.Closure's parameters are unsafe)
-//
-//  (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.
-//
-//
-// Practice
-// ========
-//
-// 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.·
-//
-// Then...
-//
-// 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
-//   - if it is for a closure variable and the closure executed at the place it's defined
-//
-//  debug['s'] == 1 analyzes the flow of all variables one level of referencing deep
-//  and assumes any assignment of a reference type to a deeper pointer is a flow to the sink.
-//  debug['s'] == 2 does full alias analysis.
-//
-//  Watch the variables moved to the heap and parameters tagged as unsafe with -m.
-//
 
 #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);
-static void resolvealiases();
+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
-//   - global variables (including imported ones),
-//   - return values of exported functions and
+//   - return values and output variables
 //   - parameters on imported functions not marked 'safe'
+//   - assignments to global variables
 // flow to.
-static Node theSink;
-
-// All functions that are not in this package that eaexpr bumped into.
-static NodeList* importfunc;
-
-// Table indexed by derefdepth, of lists of derefererence nodes.
-static NodeList* dereftab[256];
+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
-escapes()
-{
-        NodeList *l, *ll;
-
-        // All extern variables leak to theSink
-        for(l=externdcl; l; l=l->next)
-                if (l->n->op == ONAME)
-                        flows(&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) {
-                        curfn = l->n;
-                        // all out parameters flow to the sink
-                        for (ll=l->n->dcl; ll; ll=ll->next)
-                                if (ll->n->op == ONAME && ll->n->class == PPARAMOUT)
-                                        flows(&theSink, ll->n);
-                        eastmtlist(N, l->n->nbody);
-                        curfn = nil;
-                }
-        }
-
-        // connect the non-safe parameters of all imported functions
-        // we bumped into to the sink.
-        for (l=importfunc; l; l=l->next)
-                print("imported function: %N\n", l->n);
-
-        if (debug['s'] > 1)
-                resolvealiases();
-
-        // find all nodes that reach the sink
-        // marking address nodes with addrescapes
-        // mark parameters unsafe
-        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;
+        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 PPARAM:
+                        ll->n->esc = EscNone;   // prime for escflood later
+                        ll->n->escloopdepth = loopdepth;
+                        break;
+                }
+        }
+
+        // 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);
-
-        if (debug['m'] > 1)
-                print("%L %N eastmt: %N\n", lineno, fun, stmt);
-
-
-        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);
+                        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;           ·······
+                                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)
+                                escexpr(stmt->list->next->n, stmt->right);
+                        break;
                 case TMAP:      // k [, v] = range map
-                        eaexpr(stmt->list->n, stmt->right);
+                        escexpr(stmt->list->n, stmt->right);
                         if(stmt->list->next)
-                                eaexpr(stmt->list->next->n, stmt->right);
+                                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(N, stmt->left);
-                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(N, stmt->ntest->left);
-                        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(N, stmt->left);
-                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
                 cl = count(stmt->list);
                 cr = count(stmt->rlist);
-                if (cl > 1 && cr == 1) {
-                        for(ll=stmt->list; ll; ll=ll->next) {
-//                              eaexpr(N, ll->n);
-                                eaexpr(ll->n, stmt->rlist->n);
-                        }
-                } else { 
+                if(cl > 1 && cr == 1) {
+                        for(ll=stmt->list; ll; ll=ll->next)
+                                escexpr(ll->n, stmt->rlist->n);
+                } else {
                         if(cl != cr)
-                                fatal("eastmt: bad OAS2: %N", stmt);
-                        for(ll=stmt->list, lr=stmt->rlist; ll; ll=ll->next, lr=lr->next) {
-//                              eaexpr(N, ll->n);
-                                eaexpr(ll->n, lr->n);
-                        }
-                }
-                break;
-                
+                                fatal("escstmt: bad OAS2: %N", stmt);
+                        for(ll=stmt->list, lr=stmt->rlist; ll; ll=ll->next, lr=lr->next)
+                                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(N, stmt->list->n);
-                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(N, stmt->left);
-                eaexpr(stmt->left, stmt->right);
-                break;
-
-        case OCOPY:     // second arguments leaks to the first
-//              eaexpr(N, stmt->left);
-                eaexpr(stmt->left, stmt->right);
-                break;
-
+                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)
-//                      eaexpr(N, ll->n);
-                eaexpr(N, stmt->rlist->n);
+                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);
-                break;
-
-        case OPROC:
-                // stmt->left is a (pseud)ocall,
-                // stmt->left->left is the function being called.
-                // everything leaks.
-                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 void
-eaexpr(Node *dst, Node *expr)
-{
-        NodeList *ll, *lr;
-        Node* n;
-
-        if(expr == N || expr == dst)
-                return;
-
-        setlineno(expr);
-
-        if (expr->typecheck == 0  && expr->op != ONONAME) {    // TODO where do these come from
-                dump("eaexpr missing typecheck", expr);
-                fatal("Missing typecheck.");
-        }
-
-        // If dst is a part, make expr go to the whole
-        if (dst) {
+                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))
-                                break;
+                                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 OIND:
                 case ODOTPTR:
-                case OINDEXMAP:
-                        eaexpr(dst->left, expr);
+                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 (debug['m'] > 1)
-                print("%L %S:: ... examining %N <= %N\n", lineno, curfn ? curfn->nname->sym : S, dst, expr);
-
-        if (expr->trecur)
+
+        }
+
+        if(expr == N || expr->op == ONONAME || expr->op == OXXX)
                 return;
-        expr->trecur = 1;
+
+        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, comment out before submitting
-                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) or  &(*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:
-                // 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(dst, 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) {
-                        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
-        // the return values don't leak to theSink but to dst
+                // 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:
+                // 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 LEAKS TO THE CURRENT CLOSURE
-                if (expr->left->ntype && expr->left->ntype->list) {
-                        // lr->n is the dclfield, ->left is the ONAME param node
-                        for (ll=expr->list, lr=expr->left->ntype->list; ll; ll=ll->next) {
-                                eaexpr(lr->n->left, ll->n);
-                                if (!lr->n->isddd) lr=lr->next;
-                        }
-                } else {
-                        // No type with parameter list for this
-                        // function (e.g. the result of an ODOTINTER
-                        // or ODOTMETH or a function variable)
-                        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:
-                // expr->right is just an (untypechecked) ONAME
-                eaexpr(dst, expr->left);
-                break;
-
-        case OSLICE:   // the big thing flows, 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:
-                // the closure flows to the lhs of the assignment, or to theSink if we're in a return.
-                flows(dst, expr);
-                // out parameters flow to the sink
-                for (ll=expr->dcl; ll; ll=ll->next)
-                        if (ll->n->op == ONAME && ll->n->class == PPARAMOUT)
-                                flows(&theSink, ll->n);
-                // the cvars will have their address taken later by walk.
-                // introduce a fake OADDR node so eawalk can pick that up.
-                for (ll=expr->cvars; ll; ll=ll->next) {
-                        if (ll->n->op == OXXX)  // see dcl.c:398, todo: figure out exactly what is going on here
-                                continue;
-                        n = nod(OADDR, ll->n, N);
-                        typecheck(&n, Erv);
-                        flows(expr, n);
-                }
-                eastmtlist(expr, expr->nbody);  // the declarations in the body flow to the closure
-                break;
-        }
-
-        expr->trecur = 0;
-}
-
-// 0 is scalar, 1 is *scalar, 2 is **scalar etc.
-// slices maps and channels count as a reference to their contents
-// arrays count as their contents and structs as the max of any of its fields.
-static int
-derefdepth(Type* t)
-{
-        int d1, d2;
-        Type *t1;
-
-        if (t == T)
-                return 0;
-
-        if (t->recur == 0xff) // being checked
-                return 1;
-
-        // what we store is 1+ what we return
-        // t->recur 0 means not checked.  1 is scalar, 2 is *scalar, 3 is **scalar etc.
-        if (t->recur == 0) {
-                t->recur = 0xff; // being checked
-
-                switch(t->etype) {
-                case TPTR32:
-                case TPTR64:
-                        t->recur = derefdepth(t->type);
-                        break;
-                case TINTER:
-                        t->recur = 1;
-                        break;
-                case TARRAY:
-                        t->recur = derefdepth(t->type);
-                        if(!isfixedarray(t))
-                                t->recur++;
-                        break;
-                case TCHAN:
-                        t->recur = 1 + derefdepth(t->type);
-                        break;
-                case TMAP:
-                        d1 = derefdepth(t->type);
-                        d2 = derefdepth(t->down);
-                        if (d1 > d2)
-                                t->recur = 1 + d1;
-                        else
-                                t->recur = 1 + d2;
-                        break;
-                case TSTRUCT:
-                        d1 = 0;
-                        for(t1=t->type; t1!=T; t1=t1->down) { ··
-                                if(t1->etype != TFIELD) 
-                                        fatal("isreftype struct: not TFIELD: %lT", t1); 
-                                d2 = derefdepth(t1->type);
-                                if (d1 < d2) d1 = d2;
-                        }
-                        t->recur = d1;
+        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;
+
+        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:
-                        t->recur = 1;
-                }
-
-                if (t->recur > 250)
-                        fatal("Reference types too deeply nested: %d", t->recur);  // todo, just tie to sink in flows()
-
-                t->recur++; // what we store is 1+ what we return
-        }
-
-        return t->recur - 1;
-}
-
-static void
-flows(Node* dst, Node* src)
-{
-        int d;
-
-        if (dst == nil || src == nil || dst == src)
-                return;
-
-        d = derefdepth(src->type);  // dst may be theSink
-
-        if (debug['m']>2)
-                print("%L %S:%d:flows(%N <- %N)\n", lineno, curfn ? curfn->nname->sym : S, d, dst, src, src->type);
-
-
-        // external variables arent typechecked yet,·
-        // so they return d==0·
-        if (d == 0 && !(src->op == ONAME && src->class == PEXTERN))     // scalar type, don't bother
-                return;
-
-        // v := &object, w = &v -> treat as global leak
-        if ((d > 1) && (debug['s'] < 2)) {
-                dst = &theSink;
-        } else {
-                if (d > 0)
-                        dereftab[d] = list(dereftab[d], dst);
-        }
-
-        dst->asrc = list(dst->asrc, src);
-
-        if (debug['m'] > 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
-resolvealiases()
-{
-        NodeList* ll;
-        int i;
-
-        for (i = 250; i>= 0; i--) {
-                for (ll=dereftab[i]; ll; ll=ll->next) {
-                        // follow ll->n->left upstream, and copy
-                        // ll->n->asrc to the ->left of any reference
-                        // nodes we find
-                }
-        }
-}
-
-
-static int depth;
-
-static void
-eawalk(Node *sink)
-{
-        NodeList *ll;
-
-        if (debug['m']>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);
-                eawalk(sink->closure);
-        }
-
-        depth--;
-}
+                        fatal("messed up escape tagging: %N::%N", curfn, ll->n);
+                }
+        }
+
+        curfn = savefn;
+}