cmd/5l, cmd/6l, cmd/8l, cmd/gc, runtime: generate and use bitmaps of argument pointer locations

With this change the compiler emits a bitmap for each function
covering its stack frame arguments area.  If an argument word
is known to contain a pointer, a bit is set.  The garbage
collector reads this information when scanning the stack by
frames and uses it to ignores locations known to not contain a
pointer.

R=golang-dev, bradfitz, daniel.morsing, dvyukov, khr, khr, iant, cshapiro
CC=golang-dev
https://codereview.appspot.com/9223046

3 files changed, 258 insertions, 0 deletions

diff --git a/src/cmd/gc/bv.c b/src/cmd/gc/bv.c
new file mode 100644
index 000000000..929834097
--- /dev/null
+++ b/src/cmd/gc/bv.c
@@ -0,0 +1,95 @@
+// Copyright 2013 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.
+
+#include <u.h>
+#include <libc.h>
+#include "go.h"
+
+enum {
+	WORDSIZE = sizeof(uint32),
+	WORDBITS = 32,
+};
+
+uintptr
+bvsize(uintptr n)
+{
+	return ((n + WORDBITS - 1) / WORDBITS) * WORDSIZE;
+}
+
+Bvec*
+bvalloc(int32 n)
+{
+	Bvec *bv;
+	uintptr nbytes;
+
+	if(n < 0)
+		fatal("bvalloc: initial size is negative\n");
+	nbytes = sizeof(Bvec) + bvsize(n);
+	bv = malloc(nbytes);
+	if(bv == nil)
+		fatal("bvalloc: malloc failed\n");
+	memset(bv, 0, nbytes);
+	bv->n = n;
+	return bv;
+}
+
+void
+bvset(Bvec *bv, int32 i)
+{
+	uint32 mask;
+
+	if(i < 0 || i >= bv->n)
+		fatal("bvset: index %d is out of bounds with length %d\n", i, bv->n);
+	mask = 1 << (i % WORDBITS);
+	bv->b[i / WORDBITS] |= mask;
+}
+
+void
+bvres(Bvec *bv, int32 i)
+{
+	uint32 mask;
+
+	if(i < 0 || i >= bv->n)
+		fatal("bvres: index %d is out of bounds with length %d\n", i, bv->n);
+	mask = ~(1 << (i % WORDBITS));
+	bv->b[i / WORDBITS] &= mask;
+}
+
+int
+bvget(Bvec *bv, int32 i)
+{
+	uint32 mask, word;
+
+	if(i < 0 || i >= bv->n)
+		fatal("bvget: index %d is out of bounds with length %d\n", i, bv->n);
+	mask = 1 << (i % WORDBITS);
+	word = bv->b[i / WORDBITS] & mask;
+	return word ? 1 : 0;
+}
+
+int
+bvisempty(Bvec *bv)
+{
+	int32 i;
+
+	for(i = 0; i < bv->n; i += WORDBITS)
+		if(bv->b[i / WORDBITS] != 0)
+			return 0;
+	return 1;
+}
+
+int bvcmp(Bvec *bv1, Bvec *bv2)
+{
+	int32 i;
+
+	if(bv1->n != bv2->n) {
+		fatal("bvcmp: size %d != %d\n", bv1->n, bv2->n);
+	}
+	for(i = 0; i < bv1->n; i += WORDBITS) {
+		if(bv1->b[i / WORDBITS] != bv2->b[i / WORDBITS]) {
+			fatal("bvcmp: element %x != %x @ %d\n", bv1->b[i/WORDBITS], bv2->b[i/WORDBITS], i/WORDBITS);
+		}
+	}
+	return 0;
+}
diff --git a/src/cmd/gc/go.h b/src/cmd/gc/go.h
index 48bcf0233..6a3a7d8cf 100644
--- a/src/cmd/gc/go.h
+++ b/src/cmd/gc/go.h
@@ -127,6 +127,7 @@ struct	Val
 	} u;
 };
 
+typedef	struct	Bvec	Bvec;
 typedef	struct	Pkg Pkg;
 typedef	struct	Sym	Sym;
 typedef	struct	Node	Node;
@@ -696,6 +697,12 @@ struct	Bits
 
 EXTERN	Bits	zbits;
 
+struct Bvec
+{
+	int32	n;	// number of bits
+	uint32	b[];
+};
+
 typedef	struct	Var	Var;
 struct	Var
 {
@@ -986,6 +993,16 @@ Bits	bor(Bits a, Bits b);
 int	bset(Bits a, uint n);
 
 /*
+ *	bv.c
+ */
+Bvec*	bvalloc(int32 n);
+void	bvset(Bvec *bv, int32 i);
+void	bvres(Bvec *bv, int32 i);
+int	bvget(Bvec *bv, int32 i);
+int	bvisempty(Bvec *bv);
+int	bvcmp(Bvec *bv1, Bvec *bv2);
+
+/*
  *	closure.c
  */
 Node*	closurebody(NodeList *body);
diff --git a/src/cmd/gc/pgen.c b/src/cmd/gc/pgen.c
index 82d8186b0..7fcbf19b1 100644
--- a/src/cmd/gc/pgen.c
+++ b/src/cmd/gc/pgen.c
@@ -8,6 +8,7 @@
 #include	"opt.h"
 
 static void allocauto(Prog* p);
+static void pointermap(Node* fn);
 
 void
 compile(Node *fn)
@@ -108,6 +109,8 @@ compile(Node *fn)
 		}
 	}
 
+	pointermap(fn);
+
 	genlist(curfn->enter);
 
 	retpc = nil;
@@ -168,6 +171,149 @@ 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);
+		*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);
+		*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);
+		bvset(bv, (*xoffset + widthptr) / widthptr);
+		*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);
+			*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 describes the pointer containing locations
+// in the argument list.
+static void
+pointermap(Node *fn)
+{
+	Type *thistype, *inargtype, *outargtype;
+	Bvec *bv;
+	Prog *prog;
+	int32 i;
+
+	thistype = getthisx(fn->type);
+	inargtype = getinargx(fn->type);
+	outargtype = getoutargx(fn->type);
+	bv = bvalloc(fn->type->argwid / widthptr);
+	if(thistype != nil)
+		walktype(thistype, bv);
+	if(inargtype != nil)
+		walktype(inargtype, bv);
+	if(outargtype != nil)
+		walktype(outargtype, bv);
+	if(bvisempty(bv)) {
+		prog = gins(ANPTRS, N, N);
+		prog->to.type = D_CONST;
+		prog->to.offset = 0;
+	} else {
+		prog = gins(ANPTRS, N, N);
+		prog->to.type = D_CONST;
+		prog->to.offset = bv->n;
+		for(i = 0; i < bv->n; i += 32) {
+			prog = gins(APTRS, N, N);
+			prog->from.type = D_CONST;
+			prog->from.offset = i / 32;
+			prog->to.type = D_CONST;
+			prog->to.offset = bv->b[i / 32];
+		}
+	}
+	free(bv);
+}
 
 // Sort the list of stack variables.  autos after anything else,
 // within autos, unused after used, and within used on reverse alignment.