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:
-//  Note: this is an attempt at something more general than I actually do below.
+// 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.  The scope of the expression node is either
-//  'global' or the function it is defined in.
+// Flag -s disables the old codepaths and switches on the code here:
 //
-//  An expression node src can 'flow' to another node dst.
-//  Define "flow(dst, src)" iff at one point in the programs execution:
-//    dst = src      - dst is a scalar, struct, array, map or chan, and the value of src is assigned to dst
-//    dst.elem = src - dst is a struct and the value of src is assigned to one of its fields
-//    dst[x] = src   - dst is an array or map and the value of src is assigned to one of its elements
-//    dst[src] = x   - dst is a map and the value of src is used as a key
-//    dst <- src     - dst is a channel and src is sent on it.
+// 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.
 //
-//  Define flow*(dst, src) as "flow(dst, src) or there is an intermediary
-//  Node n such that flow(dst, n) && flow*(n, src)", i.e. if there is a
-//  path trough the directed graph of nodes connected by flow.
+// Then escflood walks the graph starting at theSink and tags all
+// variables of it can reach an & node as escaping and all function
+// parameters it can reach as leaking.
 //
-//  If ref is a pointer or a slice element, consider
-//      ref = &dst           ref = dst[b:e]
-//      ref1 = ref           ref1 = ref
-//      ref2 = ref     or    ref2 = ref
-//      ref3 = ref           ref3 = ref
-//      dst1 = *ref1         dst1 = ref1[y]
-//      *ref2 = src          ref2[x] = src
-//      dst3 = *ref3         dst3 = ref3[y]
+// Watch the variables moved to the heap and parameters tagged as
+// unsafe with -m, more detailed analysis output with -mm
 //
-//  The graph we want to end up with looks like this:
-//
-//    src --> * <~> ref2 <~> ref <~> & <~> dst
-//                           ^
-//   dst1 <-- * <~> ref1 <~  +
-//   dst3 <-- * <~> ref3 <~  +
-//
-//  resp.:
-//
-//    src --> [x] <~> ref2 <~> ref <~> [b:e] <~> dst
-//                             ^
-//   dst1 <-- [y] <~> ref1 <~  +
-//   dst3 <-- [y] <~> ref3 <~  +
-
-//
-// The <~> has to be a new kind of edge, and it has to be symmetric,
-// otherwise the src can not end up in dst3 (even if that leads to a
-// spurious flow(dst1, src), but that can't be helped because we don't
-// want to consider the order of execution).
-//·
-// Call this symmetric relation "alias(p, q)", iff (...alias(q, p) or..)
-//   - p is an OIND and q is it's argument
-//   - p is of pointer type (including an OADDR) and it is assigned to q
-//   - p is an OADDR and q is its argument
-//   - p is an array and q is an OSLICE or OINDEX of it
-//   - p is of slice type and q is assigned to it
-//   ? is that it?
-//
-// The alias*(p,q) between two nodes is then defined as the transitive closure of
-// alias again, and flow(src, dst) needs to be extended with:
-//   - there is a q, such that flow(q, src) and alias*(q, dst)
-//
-// At the same time, &(dst) is a value, and it flows in the first sense:
-//
-//    * <-- ref2 <-- ref <-- &(dst)
-//                   ^
-//    * <-- ref1 <-- +
-//    * <-- ref3 <-- +
-//
-//  That * has to be connected is clear when we add
-//  ref4 = &*ref3.
-//  Another interesting case is dst = *(cast(&src)), which for
-//  the purposes of this discussion looks like dst = * & src
-//  (the cast just paints the ref in the middle a different color):
-//     dst <-- * <~> ref <~> & <~> src
-//             * <-- ref <-- &(src)
-//
-//  That is, the value of src leaks to dst, but the value of its address does not.
-//
-// what about·
-//       ref = &dst
-//       ref2 = ref
-//       ref2 = &dst2
-//
-//      dst2 = src    that should not affect ref, or dest
-//
-//
-//  Now that we have a definition of flow* between nodes, we can define "leak(node)":
-//  a node n leaks the current function if
-//    - it is a global variable
-//    - it is an output variable for the function, or a node in the return expression list
-//    - it is used inside a go statement
-//    - there is another node m such that flow(m, n) and m leaks the current function·
-//    - there is another node m such that flow(m, n) and m is the argument to a
-//      function that itself leaks from /that/ function
-//·
-//  A variable must be moved to the heap (from the stack) if it's *address* leaks, meaning
-//   - the address is taken (with the unary-& operator OADDR)
-//   - AND this (pointer) value leaks outside the current function scope.
-//
 
 #include "go.h"
 
-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;
+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
-escanalfunc(Node *func)
-{
+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;
-        eastmtlist(N, func->nbody);
-        curfn = nil;
-}
-
-void
-escanalfinish()
-{
-        eawalk(&theSink);
-}
-
-
-static void eawalk(Node *sink) {
-        NodeList *ll;
- ·······
-        ll = sink->asrc;
-        sink->asrc = nil;
-        for (; ll; ll=ll->next) {
-                eawalk(ll->n);
-                if (ll->n->op == OADDR) {
-                        addrescapes(ll->n->left);
-                        eawalk(ll->n->left);
-                }
-        }
-}
-
-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(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->op != OCLOSURE) fatal("eastmt fun is not a closure: %N", fun);
+        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:
-                // things i haven't thought of
-                dump("eastmt", stmt);
-                // fallthrough
-                // things that shouldn't happen here
-        case OCASE: case OXCASE:
-        case OFALL:
-        case OCALL:
-                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:
+                // 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) {
+                        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 TSTRING:   // never flows
+                        escexpr(stmt->list->n, N);
+                        if(stmt->list->next)
+                                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
+                        escexpr(stmt->list->n, stmt->right);
+                        if(stmt->list->next)
+                                escexpr(stmt->list->next->n, stmt->right);
+                        break;
+                case TCHAN:     // v = range chan
+                        escexpr(stmt->list->n, stmt->right);
+                        break;
+                }
+                loopdepth++;
+                escstmtlist(stmt->nbody);
+                loopdepth--;
+                break;
+
+        case OIF:
+                escexpr(N, stmt->ntest);
+                escstmtlist(stmt->nbody);
+                escstmtlist(stmt->nelse);
+                break;
+
+        case OSELECT:
+                for(ll=stmt->list; ll; ll=ll->next) {  // cases
+                        escstmt(ll->n->left);
+                        escstmtlist(ll->n->nbody);
+                }
+                break;
+
+        case OSELRECV2:   // v, ok := <-ch  ntest:ok
+                escexpr(N, stmt->ntest);
+                // fallthrough
+        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) {
+                        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 {
+                        escexpr(N, stmt->ntest);
+                        for(ll=stmt->list; ll; ll=ll->next) {  // cases
+                                for(lr=ll->n->list; lr; lr=lr->next)
+                                        escexpr(N, lr->n);
+                                escstmtlist(ll->n->nbody);
+                        }
+                }
+                break;
+
+        case OAS:
+        case OASOP:
+                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)
+                                escexpr(ll->n, stmt->rlist->n);
+                } else {
+                        if(cl != cr)
+                                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)
+                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
+                escexpr(N, stmt->left);
+                break;
+
+        case OSEND:             // ch <- x
+                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:
+                escexpr(N, stmt);
+                break;
+
+        case OPROC:
+        case ODEFER:
+                // 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)
+                        escexpr(&theSink, ll->n);
+                break;
+
         case OCLOSE:
         case OPRINT:
         case OPRINTN:
-        case ORECOVER:
-                // all harmless
-                break;
-
-        case  OBLOCK:
-                eastmtlist(fun, stmt->list);
-                break;
-
-        case OFOR:
-                eastmtlist(fun, stmt->ninit);
-                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> }
-                eastmtlist(fun, stmt->ninit);
-                switch(stmt->type->etype) {
-                case TARRAY:    // i, v = range sliceorarrayorstring
-                case TSTRING:
-                        if(stmt->list->next)
-                                eaexpr(stmt->list->next->n, stmt->right);
-                        break;           ·······
-                case TMAP:      // k, v = range map
-                        eaexpr(stmt->list->n, stmt->right);
-                        if(stmt->list->next)
-                                eaexpr(stmt->list->next->n, stmt->right);
-                        break;
-                case TCHAN:     // v = range chan
-                        eaexpr(stmt->list->n, stmt->right);
-                        break;
-                }
-                eastmtlist(fun, stmt->nbody);
-                break;
-
-        case OIF:
-                eastmtlist(fun, stmt->ninit);
-                eaexpr(N, stmt->ntest);
-                eastmtlist(fun, stmt->nbody);
-                eastmtlist(fun, stmt->nelse);
-                break;
-
-        case OSELECT:
-                eastmtlist(fun, stmt->ninit);
-                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);
-                // fallthrough
-        case OSELRECV:
-                eaexpr(stmt->left, stmt->right);
-                break;
-
-        case OSWITCH:
-                eastmtlist(fun, stmt->ninit);
-                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);
-                } else {
-                        eaexpr(fun, 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);
-                        }
-                }
-                break;
-
-        case OAS:·
-        case OASOP:             // v += x etc.  never applies to pointers, but leave it to eaexpr to figure that out.
-                eaexpr(stmt->left, stmt->right);
-                break;
-
-                // escape analysis happens after typecheck, so the
-                // OAS2xxx have already been substituted.
-        case OAS2:
-                cl = count(stmt->list);
-                cr = count(stmt->rlist);
-                if (cl > 1 && cr == 1) {
-                        for(ll=stmt->list; ll; ll=ll->next)
-                                eaexpr(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(ll->n, lr->n);
-                }
-                break;
-         ·······
-        case OAS2RECV:          // v, ok = <-ch
-        case OAS2MAPR:          // v, ok = m[k]
-        case OAS2DOTTYPE:       // v, ok = x.(type)
-                eaexpr(stmt->list->n, stmt->rlist->n->left);
-                break;
-
-        case OAS2MAPW:          // m[k] = x, ok
-                eaexpr(stmt->list->n->left, stmt->rlist->n);
-                break;
-
-        case ORECV:             // unary <-ch as statement
-                eaexpr(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);
-                break;
-
-        case OAPPEND:   // note: append also leaks all its args in an expression
-                for (ll=stmt->list->next; ll; ll=ll->next)
-                        eaexpr(stmt->list->n, ll->n);
-                break;
-
-        case OAS2FUNC:  // x,y,z = f()
-                // the return values already escape because they're return values
-                // no need to tie them to x, y or z here.
-                eaexpr(N, stmt->rlist->n);
-                break;
-         ·······
-        case OCALLINTER:
-        case OCALLFUNC:
-        case OCALLMETH:
-                stmt->trecur = 0;
-                eaexpr(N, stmt);
-                break;
-
-        case ODEFER:
-                eastmt(fun, stmt->left);
-                break;
-
-        case ORETURN:
-                for (ll=stmt->list; ll; ll=ll->next)
-                        eaexpr(&theSink, ll->n);
-                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);
+                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
-isinteresting(Type *t) {
-        if (t == T)
-                return 1;  // can happen for lhs of type switch assignment
-//              fatal("no type for isinteresting");
-
-        switch(t->etype) {
-        case TPTR32:
-        case TPTR64:
-        case TINTER:
-        case TFUNC:
-        case TARRAY:
-                return 1;
-        case TCHAN:
-                if (t->type == t)
-                        return 1;  // recursive types
-                return isinteresting(t->type);
-                break;
-        case TMAP:
-                if (t->type == t || t->down == t)
-                        return 1;  // recursive types
-
-                return isinteresting(t->type) || isinteresting(t->down);
-                break;
-        case TSTRUCT:
-                for(t=t->type; t!=T; t=t->down) {
-                        if(t->etype != TFIELD)
-                                fatal("isinteresting: not TFIELD: %lT", t);
-                        // can't recurse without going through TPTR
-                        if (isinteresting(t->type))
-                                return 1;
-                }
-                return 0;
-        }
-        return 0;
-}
-
-static void
-flows(Node* dst, Node* src)
-{
-        if (dst == nil || src == nil)
+                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 OIND:
+                case ODOTPTR:
+                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;
-        dst->asrc = list(dst->asrc, src);
-
-        if (debug['s']>1) {
-        if (dst != &theSink)
-                print("%L %S::%N <- %N", lineno, curfn->nname->sym, dst, src);
-        else
-                print("%L %S:: leaks %N", lineno, curfn->nname->sym, 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;
-
-        setlineno(expr);
-
-        if (expr->trecur)
-                return;
-        expr->trecur = 1;
-
-        if (expr->typecheck == 0  && expr->op != ONONAME) {    // TODO where do these come from
-                dump("eaexpr missing typecheck", expr);
+
+        if(expr->typecheck == 0 && expr->op != OKEY) {
+                dump("escexpr missing typecheck", expr);
                 fatal("Missing typecheck.");
         }
 
-
-        // if dst is not interesting, save some work down the recursion
-        if  (dst != &theSink)
-        if ((dst == N) || isblank(dst) || !isinteresting(dst->type))
-                dst = N;
-
-        if (debug['s'] > 1)
-        print("%L %S:: ... examining %N <= %N\n", lineno, curfn->nname->sym, dst, expr);
-
-
-        // here: turn dests x[k] into x, etc. see part-of in top comment
-
-//      if (dst && dst != &theSink && !dst->type) dump("typeless dst", dst);
- ·······
-        if (dst && dst->op == ONAME && dst->class == PEXTERN)
-                dst = &theSink;
-
-        if (dst && dst->op == OIND) dst = &theSink; // aliasing happens here
+        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:
-                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,
-                // which in turn is only interesting if it is a pointer value.
-                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);
-                break;
-
+                // loopdepth was set in the defining statement or function header
+                escflows(dst, expr);
+                break;
+
+        case OARRAYLIT:
+        case OSTRUCTLIT:
         case OMAPLIT:
-        case OSTRUCTLIT:
-        case OARRAYLIT:
-                // pointer members or elements, initialized to &something?
-                // i think for now they're already on the heap anyway
-                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:
+                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;
-
-        // all arguments leak to the parameter nodes.
-        // TODO ...when we figure out how to get our hands at them.
+                // 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(dst, expr->left);
-                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.
-                // 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;
-}
-
-
-
-
-#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
+        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:
+                        fatal("messed up escape tagging: %N::%N", curfn, ll->n);
+                }
+        }
+
+        curfn = savefn;
+}