Rietveld Code Review Tool
Help | Bug tracker | Discussion group | Source code | Sign in
(1543)

Unified Diff: src/cmd/gc/esc.c

Issue 4954043: code review 4954043: gc: tweak and enable escape analysis (Closed)
Patch Set: diff -r 5e1053337103 https://go.googlecode.com/hg/ Created 12 years, 7 months ago
Use n/p to move between diff chunks; N/P to move between comments. Please Sign in to add in-line comments.
Jump to:
View side-by-side diff with in-line comments
Download patch
« no previous file with comments | « src/cmd/gc/doc.go ('k') | src/cmd/gc/gen.c » ('j') | no next file with comments »
Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
Index: src/cmd/gc/esc.c
===================================================================
--- a/src/cmd/gc/esc.c
+++ b/src/cmd/gc/esc.c
@@ -2,22 +2,14 @@
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.
//
-// 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
-//
-// Flag -s disables the old codepaths and switches on the code here:
+// Escape analysis.
//
// First escfunc, esc and escassign recurse over the ast of each
// function to dig out flow(dst,src) edges between any
// pointer-containing nodes and store them in dst->escflowsrc. For
// variables assigned to a variable in an outer scope or used as a
// return value, they store a flow(theSink, src) edge to a fake node
-// 'the Sink'. For variables referenced in closures, an edge
+// '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.
//
@@ -25,9 +17,16 @@
// variables of it can reach an & node as escaping and all function
// parameters it can reach as leaking.
//
-// Watch the variables moved to the heap and parameters tagged as
-// unsafe with -m, more detailed analysis output with -mm
+// If a value's address is taken but the address does not escape,
+// then the value can stay on the stack. If the value new(T) does
+// not escape, then new(T) can be rewritten into a stack allocation.
+// The same is true of slice literals.
//
+// If escape analysis is disabled (-s), this code is not used.
+// Instead, the compiler assumes that any value whose address
+// is taken without being immediately dereferenced
+// needs to be moved to the heap, and new(T) and slice
+// literals are always real allocations.
#include <u.h>
#include <libc.h>
@@ -53,9 +52,9 @@
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
+static NodeList* noesc; // list of possible non-escaping nodes, for printing
void
escapes(void)
@@ -85,8 +84,17 @@
for(l=xtop; l; l=l->next)
if(l->n->op == ODCLFUNC)
esctag(l->n);
+
+ if(debug['m']) {
+ for(l=noesc; l; l=l->next)
+ if(l->n->esc == EscNone)
+ warnl(l->n->lineno, "%S %#N does not escape",
+ (l->n->curfn && l->n->curfn->nname) ? l->n->curfn->nname->sym : S,
+ l->n);
+ }
}
+
static void
escfunc(Node *func)
{
@@ -109,7 +117,10 @@
ll->n->escloopdepth = loopdepth;
break;
case PPARAM:
+ if(ll->n->type && !haspointers(ll->n->type))
+ break;
ll->n->esc = EscNone; // prime for escflood later
+ noesc = list(noesc, ll->n);
ll->n->escloopdepth = loopdepth;
break;
}
@@ -143,7 +154,7 @@
esc(Node *n)
{
int lno;
- NodeList *ll, *lr, *l;
+ NodeList *ll, *lr;
if(n == N)
return;
@@ -153,14 +164,15 @@
if(n->op == OFOR || n->op == ORANGE)
loopdepth++;
+ esc(n->left);
+ esc(n->right);
+ esc(n->ntest);
+ esc(n->nincr);
esclist(n->ninit);
+ esclist(n->nbody);
+ esclist(n->nelse);
esclist(n->list);
esclist(n->rlist);
- esc(n->ntest);
- esc(n->nincr);
- esclist(n->nbody);
- esc(n->left);
- esc(n->right);
if(n->op == OFOR || n->op == ORANGE)
loopdepth--;
@@ -182,7 +194,7 @@
case ORANGE:
// Everything but fixed array is a dereference.
- if(isfixedarray(n->type))
+ if(isfixedarray(n->type) && n->list->next)
escassign(n->list->next->n, n->right);
break;
@@ -192,7 +204,6 @@
// ntest->right is the argument of the .(type),
// ll->n->nname is the variable per case
escassign(ll->n->nname, n->ntest->right);
- esclist(ll->n->nbody);
}
}
break;
@@ -253,23 +264,54 @@
case OCALLINTER:
esccall(n);
break;
-
+
case OCONV:
case OCONVNOP:
case OCONVIFACE:
escassign(n, n->left);
break;
+
+ case OARRAYLIT:
+ if(isslice(n->type)) {
+ n->esc = EscNone; // until proven otherwise
+ noesc = list(noesc, n);
+ n->escloopdepth = loopdepth;
+ // Values make it to memory, lose track.
+ for(ll=n->list; ll; ll=ll->next)
+ escassign(&theSink, ll->n->right);
+ } else {
+ // Link values to array.
+ for(ll=n->list; ll; ll=ll->next)
+ escassign(n, ll->n->right);
+ }
+ break;
+
+ case OSTRUCTLIT:
+ // Link values to struct.
+ for(ll=n->list; ll; ll=ll->next)
+ escassign(n, ll->n->right);
+ break;
+
+ case OMAPLIT:
+ n->esc = EscNone; // until proven otherwise
+ noesc = list(noesc, n);
+ n->escloopdepth = loopdepth;
+ // Keys and values make it to memory, lose track.
+ for(ll=n->list; ll; ll=ll->next) {
+ escassign(&theSink, ll->n->left);
+ escassign(&theSink, ll->n->right);
+ }
+ break;
- case OARRAYLIT:
- case OSTRUCTLIT:
- for(l=n->list; l; l=l->next)
- escassign(n, l->n->right);
- break;
- case OMAPLIT:
- for(l=n->list; l; l=l->next) {
- escassign(n, l->n->left);
- escassign(n, l->n->right);
- }
+ case OADDR:
+ case OCLOSURE:
+ case OMAKECHAN:
+ case OMAKEMAP:
+ case OMAKESLICE:
+ case ONEW:
+ n->escloopdepth = loopdepth;
+ n->esc = EscNone; // until proven otherwise
+ noesc = list(noesc, n);
break;
}
@@ -284,7 +326,6 @@
escassign(Node *dst, Node *src)
{
int lno;
- NodeList *ll;
if(isblank(dst) || dst == N || src == N || src->op == ONONAME || src->op == OXXX)
return;
@@ -336,11 +377,6 @@
break;
}
- if(src->typecheck == 0 && src->op != OKEY) {
- dump("escassign missing typecheck", src);
- fatal("escassign");
- }
-
lno = setlineno(src);
pdepth++;
@@ -350,6 +386,10 @@
case ODOTPTR: // dst = (*x).f
case ONAME:
case OPARAM:
+ case ODDDARG:
+ case OARRAYLIT:
+ case OMAPLIT:
+ case OSTRUCTLIT:
// loopdepth was set in the defining statement or function header
escflows(dst, src);
break;
@@ -377,32 +417,39 @@
escassign(dst, src->left);
break;
- case OARRAYLIT:
- case OSTRUCTLIT:
- case OMAPLIT:
- src->escloopdepth = loopdepth;
- escflows(dst, src);
- for(ll=src->list; ll; ll=ll->next) {
- escassign(src, ll->n->left);
- escassign(src, ll->n->right);
- }
- break;
-
case OMAKECHAN:
case OMAKEMAP:
case OMAKESLICE:
case ONEW:
- src->curfn = curfn; // should have been done in parse, but patch it up here.
- src->escloopdepth = loopdepth;
escflows(dst, src);
break;
case OCLOSURE:
- src->curfn = curfn; // should have been done in parse, but patch it up here.
- src->escloopdepth = loopdepth;
escflows(dst, src);
escfunc(src);
break;
+
+ case OADD:
+ case OSUB:
+ case OOR:
+ case OXOR:
+ case OMUL:
+ case ODIV:
+ case OMOD:
+ case OLSH:
+ case ORSH:
+ case OAND:
+ case OANDNOT:
+ case OPLUS:
+ case OMINUS:
+ case OCOM:
+ // Might be pointer arithmetic, in which case
+ // the operands flow into the result.
+ // TODO(rsc): Decide what the story is here. This is unsettling.
+ escassign(dst, src->left);
+ escassign(dst, src->right);
+ break;
+
}
pdepth--;
@@ -420,7 +467,7 @@
esccall(Node *n)
{
NodeList *ll, *lr;
- Node *a, *fn;
+ Node *a, *fn, *src;
Type *t, *fntype;
fn = N;
@@ -458,21 +505,32 @@
}
}
- if(fn && fn->ntype) {
+ if(fn && fn->op == ONAME && fn->class == PFUNC && fn->ntype) {
// Local function. Incorporate into flow graph.
// Receiver.
if(n->op != OCALLFUNC)
escassign(fn->ntype->left->left, n->left->left);
- for(ll=n->list, lr=fn->ntype->list; ll && lr; ll=ll->next) {
- if (lr->n->left)
- escassign(lr->n->left, ll->n);
- else
- escassign(&theSink, ll->n);
- if(lr->n->left && !lr->n->left->isddd)
- lr=lr->next;
+ for(lr=fn->ntype->list; ll && lr; ll=ll->next, lr=lr->next) {
+ src = ll->n;
+ if(lr->n->isddd && !n->isddd) {
+ // Introduce ODDDARG node to represent ... allocation.
+ src = nod(ODDDARG, N, N);
+ src->escloopdepth = loopdepth;
+ src->lineno = n->lineno;
+ src->esc = EscNone; // until we find otherwise
+ noesc = list(noesc, src);
+ n->right = src;
+ }
+ if(lr->n->left != N)
+ escassign(lr->n->left, src);
+ if(src != ll->n)
+ break;
}
+ // "..." arguments are untracked
+ for(; ll; ll=ll->next)
+ escassign(&theSink, ll->n);
return;
}
@@ -483,11 +541,25 @@
escassign(&theSink, n->left->left);
}
for(t=getinargx(fntype)->type; ll; ll=ll->next) {
+ src = ll->n;
+ if(t->isddd && !n->isddd) {
+ // Introduce ODDDARG node to represent ... allocation.
+ src = nod(ODDDARG, N, N);
+ src->escloopdepth = loopdepth;
+ src->lineno = n->lineno;
+ src->esc = EscNone; // until we find otherwise
+ noesc = list(noesc, src);
+ n->right = src;
+ }
if(!t->note || strcmp(t->note->s, safetag->s) != 0)
- escassign(&theSink, ll->n);
- if(t->down)
- t = t->down;
+ escassign(&theSink, src);
+ if(src != ll->n)
+ break;
+ t = t->down;
}
+ // "..." arguments are untracked
+ for(; ll; ll=ll->next)
+ escassign(&theSink, ll->n);
}
// Store the link src->dst in dst, throwing out some quick wins.
@@ -536,12 +608,12 @@
}
if(debug['m']>1)
- print("\nescflood:%d: dst %hN scope:%#S[%d]\n", floodgen, dst,
+ print("\nescflood:%d: dst %hN scope:%#S[%d]\n", walkgen, dst,
(dst->curfn && dst->curfn->nname) ? dst->curfn->nname->sym : S,
dst->escloopdepth);
for(l = dst->escflowsrc; l; l=l->next) {
- floodgen++;
+ walkgen++;
escwalk(0, dst, l->n);
}
}
@@ -552,9 +624,9 @@
NodeList *ll;
int leaks;
- if(src->escfloodgen == floodgen)
+ if(src->walkgen == walkgen)
return;
- src->escfloodgen = floodgen;
+ src->walkgen = walkgen;
if(debug['m']>1)
print("escwalk: level:%d depth:%d %.*s %hN scope:%#S[%d]\n",
@@ -570,19 +642,42 @@
if(src->class == PPARAM && leaks && src->esc == EscNone) {
src->esc = EscScope;
if(debug['m'])
- print("%L:leaking param: %hN\n", src->lineno, src);
+ warnl(src->lineno, "leaking param: %hN", src);
}
break;
case OADDR:
- if(leaks)
+ if(leaks) {
+ src->esc = EscHeap;
addrescapes(src->left);
+ if(debug['m'])
+ warnl(src->lineno, "%#N escapes to heap", src);
+ }
escwalk(level-1, dst, src->left);
break;
+ case OARRAYLIT:
+ if(isfixedarray(src->type))
+ break;
+ // fall through
+ case ODDDARG:
+ case OMAKECHAN:
+ case OMAKEMAP:
+ case OMAKESLICE:
+ case OMAPLIT:
+ case ONEW:
+ case OCLOSURE:
+ if(leaks) {
+ src->esc = EscHeap;
+ if(debug['m'])
+ warnl(src->lineno, "%#N escapes to heap", src);
+ }
+ break;
+
case OINDEX:
if(isfixedarray(src->type))
break;
+ // fall through
case OSLICE:
case ODOTPTR:
case OINDEXMAP:
@@ -616,8 +711,6 @@
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);
}
}
« no previous file with comments | « src/cmd/gc/doc.go ('k') | src/cmd/gc/gen.c » ('j') | no next file with comments »

Powered by Google App Engine
RSS Feeds Recent Issues | This issue
This is Rietveld f62528b