cmd/5g, cmd/5l, cmd/6g, cmd/6l, cmd/8g, cmd/8l, cmd/gc, runtime: generate pointer maps by liveness analysis

This change allows the garbage collector to examine stack
slots that are determined as live and containing a pointer
value by the garbage collector.  This results in a mean
reduction of 65% in the number of stack slots scanned during
an invocation of "GOGC=1 all.bash".

Unfortunately, this does not yet allow garbage collection to
be precise for the stack slots computed as live.  Pointers
confound the determination of what definitions reach a given
instruction.  In general, this problem is not solvable without
runtime cost but some advanced cooperation from the compiler
might mitigate common cases.

R=golang-dev, rsc, cshapiro
CC=golang-dev
https://codereview.appspot.com/14430048

1 files changed, 56 insertions, 192 deletions

diff --git a/src/cmd/gc/pgen.c b/src/cmd/gc/pgen.c
index 2d364529e..c9ba89397 100644
--- a/src/cmd/gc/pgen.c
+++ b/src/cmd/gc/pgen.c
@@ -12,26 +12,66 @@
 #include	"opt.h"
 #include	"../../pkg/runtime/funcdata.h"
 
-enum { BitsPerPointer = 2 };
-
 static void allocauto(Prog* p);
-static void dumpgcargs(Node*, Sym*);
-static Bvec* dumpgclocals(Node*, Sym*);
+
+static Sym*
+makefuncdatasym(char *namefmt, int64 funcdatakind)
+{
+	Node nod;
+	Node *pnod;
+	Sym *sym;
+	static int32 nsym;
+
+	snprint(namebuf, sizeof(namebuf), namefmt, nsym++);
+	sym = lookup(namebuf);
+	pnod = newname(sym);
+	pnod->class = PEXTERN;
+	nodconst(&nod, types[TINT32], funcdatakind);
+	gins(AFUNCDATA, &nod, pnod);
+	return sym;
+}
+
+void
+gfatvardef(Node *n)
+{
+	if(n == N || !isfat(n->type))
+		fatal("gfatvardef: node is not fat");
+	switch(n->class) {
+	case PAUTO:
+	case PPARAM:
+	case PPARAMOUT:
+		gins(AFATVARDEF, N, n);
+	}
+}
+
+static void
+removefatvardef(Prog *firstp)
+{
+	Prog *p;
+
+	for(p = firstp; p != P; p = p->link) {
+		while(p->link != P && p->link->as == AFATVARDEF)
+			p->link = p->link->link;
+		if(p->to.type == D_BRANCH)
+			while(p->to.u.branch != P && p->to.u.branch->as == AFATVARDEF)
+				p->to.u.branch = p->to.u.branch->link;
+	}
+}
 
 void
 compile(Node *fn)
 {
-	Bvec *bv;
 	Plist *pl;
-	Node nod1, *n, *gcargsnod, *gclocalsnod;
+	Node nod1, *n;
 	Prog *ptxt, *p, *p1;
 	int32 lno;
 	Type *t;
 	Iter save;
 	vlong oldstksize;
 	NodeList *l;
-	Sym *gcargssym, *gclocalssym;
-	static int ngcargs, ngclocals;
+	Sym *gcargs;
+	Sym *gclocals;
+	Sym *gcdead;
 
 	if(newproc == N) {
 		newproc = sysfunc("newproc");
@@ -111,21 +151,9 @@ compile(Node *fn)
 
 	ginit();
 
-	snprint(namebuf, sizeof namebuf, "gcargs·%d", ngcargs++);
-	gcargssym = lookup(namebuf);
-	gcargsnod = newname(gcargssym);
-	gcargsnod->class = PEXTERN;
-
-	nodconst(&nod1, types[TINT32], FUNCDATA_GCArgs);
-	gins(AFUNCDATA, &nod1, gcargsnod);
-
-	snprint(namebuf, sizeof(namebuf), "gclocals·%d", ngclocals++);
-	gclocalssym = lookup(namebuf);
-	gclocalsnod = newname(gclocalssym);
-	gclocalsnod->class = PEXTERN;
-
-	nodconst(&nod1, types[TINT32], FUNCDATA_GCLocals);
-	gins(AFUNCDATA, &nod1, gclocalsnod);
+	gcargs = makefuncdatasym("gcargs·%d", FUNCDATA_ArgsPointerMaps);
+	gclocals = makefuncdatasym("gclocals·%d", FUNCDATA_LocalsPointerMaps);
+	gcdead = makefuncdatasym("gcdead·%d", FUNCDATA_DeadPointerMaps);
 
 	for(t=curfn->paramfld; t; t=t->down)
 		gtrack(tracksym(t->type));
@@ -184,6 +212,7 @@ compile(Node *fn)
 	pc->as = ARET;	// overwrite AEND
 	pc->lineno = lineno;
 
+	fixjmp(ptxt);
 	if(!debug['N'] || debug['R'] || debug['P']) {
 		regopt(ptxt);
 		nilopt(ptxt);
@@ -203,184 +232,19 @@ compile(Node *fn)
 	}
 
 	// Emit garbage collection symbols.
-	dumpgcargs(fn, gcargssym);
-	bv = dumpgclocals(curfn, gclocalssym);
+	liveness(curfn, ptxt, gcargs, gclocals, gcdead);
 
-	defframe(ptxt, bv);
-	free(bv);
+	defframe(ptxt);
 
 	if(0)
 		frame(0);
 
+	// Remove leftover instrumentation from the instruction stream.
+	removefatvardef(ptxt);
 ret:
 	lineno = lno;
 }
 
-static void
-walktype1(Type *t, vlong *xoffset, Bvec *bv)
-{
-	vlong fieldoffset, i, o;
-	Type *t1;
-
-	if(t->align > 0 && (*xoffset % t->align) != 0)
-	 	fatal("walktype1: invalid initial alignment, %T", t);
-
-	switch(t->etype) {
-	case TINT8:
-	case TUINT8:
-	case TINT16:
-	case TUINT16:
-	case TINT32:
-	case TUINT32:
-	case TINT64:
-	case TUINT64:
-	case TINT:
-	case TUINT:
-	case TUINTPTR:
-	case TBOOL:
-	case TFLOAT32:
-	case TFLOAT64:
-	case TCOMPLEX64:
-	case TCOMPLEX128:
-		*xoffset += t->width;
-		break;
-
-	case TPTR32:
-	case TPTR64:
-	case TUNSAFEPTR:
-	case TFUNC:
-	case TCHAN:
-	case TMAP:
-		if(*xoffset % widthptr != 0)
-			fatal("walktype1: invalid alignment, %T", t);
-		bvset(bv, (*xoffset / widthptr) * BitsPerPointer);
-		*xoffset += t->width;
-		break;
-
-	case TSTRING:
-		// struct { byte *str; intgo len; }
-		if(*xoffset % widthptr != 0)
-			fatal("walktype1: invalid alignment, %T", t);
-		bvset(bv, (*xoffset / widthptr) * BitsPerPointer);
-		*xoffset += t->width;
-		break;
-
-	case TINTER:
-		// struct { Itab* tab;  union { void* ptr, uintptr val } data; }
-		// or, when isnilinter(t)==true:
-		// struct { Type* type; union { void* ptr, uintptr val } data; }
-		if(*xoffset % widthptr != 0)
-			fatal("walktype1: invalid alignment, %T", t);
-		bvset(bv, ((*xoffset / widthptr) * BitsPerPointer) + 1);
-		if(isnilinter(t))
-			bvset(bv, ((*xoffset / widthptr) * BitsPerPointer));
-		*xoffset += t->width;
-		break;
-
-	case TARRAY:
-		// The value of t->bound is -1 for slices types and >0 for
-		// for fixed array types.  All other values are invalid.
-		if(t->bound < -1)
-			fatal("walktype1: invalid bound, %T", t);
-		if(isslice(t)) {
-			// struct { byte* array; uintgo len; uintgo cap; }
-			if(*xoffset % widthptr != 0)
-				fatal("walktype1: invalid TARRAY alignment, %T", t);
-			bvset(bv, (*xoffset / widthptr) * BitsPerPointer);
-			*xoffset += t->width;
-		} else if(!haspointers(t->type))
-				*xoffset += t->width;
-		else
-			for(i = 0; i < t->bound; ++i)
-				walktype1(t->type, xoffset, bv);
-		break;
-
-	case TSTRUCT:
-		o = 0;
-		for(t1 = t->type; t1 != T; t1 = t1->down) {
-			fieldoffset = t1->width;
-			*xoffset += fieldoffset - o;
-			walktype1(t1->type, xoffset, bv);
-			o = fieldoffset + t1->type->width;
-		}
-		*xoffset += t->width - o;
-		break;
-
-	default:
-		fatal("walktype1: unexpected type, %T", t);
-	}
-}
-
-static void
-walktype(Type *type, Bvec *bv)
-{
-	vlong xoffset;
-
-	// Start the walk at offset 0.  The correct offset will be
-	// filled in by the first type encountered during the walk.
-	xoffset = 0;
-	walktype1(type, &xoffset, bv);
-}
-
-// Compute a bit vector to describe the pointer-containing locations
-// in the in and out argument list and dump the bitvector length and
-// data to the provided symbol.
-static void
-dumpgcargs(Node *fn, Sym *sym)
-{
-	Type *thistype, *inargtype, *outargtype;
-	Bvec *bv;
-	int32 i;
-	int off;
-
-	thistype = getthisx(fn->type);
-	inargtype = getinargx(fn->type);
-	outargtype = getoutargx(fn->type);
-	bv = bvalloc((fn->type->argwid / widthptr) * BitsPerPointer);
-	if(thistype != nil)
-		walktype(thistype, bv);
-	if(inargtype != nil)
-		walktype(inargtype, bv);
-	if(outargtype != nil)
-		walktype(outargtype, bv);
-	off = duint32(sym, 0, bv->n);
-	for(i = 0; i < bv->n; i += 32)
-		off = duint32(sym, off, bv->b[i/32]);
-	free(bv);
-	ggloblsym(sym, off, 0, 1);
-}
-
-// Compute a bit vector to describe the pointer-containing locations
-// in local variables and dump the bitvector length and data out to
-// the provided symbol. Return the vector for use and freeing by caller.
-static Bvec*
-dumpgclocals(Node* fn, Sym *sym)
-{
-	Bvec *bv;
-	NodeList *ll;
-	Node *node;
-	vlong xoffset;
-	int32 i;
-	int off;
-
-	bv = bvalloc((stkptrsize / widthptr) * BitsPerPointer);
-	for(ll = fn->dcl; ll != nil; ll = ll->next) {
-		node = ll->n;
-		if(node->class == PAUTO && node->op == ONAME) {
-			if(haspointers(node->type)) {
-				xoffset = node->xoffset + stkptrsize;
-				walktype1(node->type, &xoffset, bv);
-			}
-		}
-	}
-	off = duint32(sym, 0, bv->n);
-	for(i = 0; i < bv->n; i += 32) {
-		off = duint32(sym, off, bv->b[i/32]);
-	}
-	ggloblsym(sym, off, 0, 1);
-	return bv;
-}
-
 // Sort the list of stack variables. Autos after anything else,
 // within autos, unused after used, within used, things with
 // pointers first, zeroed things first, and then decreasing size.