cmd/gc: emit write barriers

A write *p = x that needs a write barrier (not all do)
now turns into runtime.writebarrierptr(p, x)
or one of the other variants.

The write barrier implementations are trivial.
The goal here is to emit the calls in the correct places
and to incur the cost of those function calls in the Go 1.4 cycle.

Performance on the Go 1 benchmark suite below.
Remember, the goal is to slow things down (and be correct).

We will look into optimizations in separate CLs, as part of
the process of comparing Go 1.3 against tip in order to make
sure Go 1.4 runs at least as fast as Go 1.3.

benchmark                          old ns/op      new ns/op      delta
BenchmarkBinaryTree17              3118336716     3452876110     +10.73%
BenchmarkFannkuch11                3184497677     3211552284     +0.85%
BenchmarkFmtFprintfEmpty           89.9           107            +19.02%
BenchmarkFmtFprintfString          236            287            +21.61%
BenchmarkFmtFprintfInt             246            278            +13.01%
BenchmarkFmtFprintfIntInt          395            458            +15.95%
BenchmarkFmtFprintfPrefixedInt     343            378            +10.20%
BenchmarkFmtFprintfFloat           477            525            +10.06%
BenchmarkFmtManyArgs               1446           1707           +18.05%
BenchmarkGobDecode                 14398047       14685958       +2.00%
BenchmarkGobEncode                 12557718       12947104       +3.10%
BenchmarkGzip                      453462345      472413285      +4.18%
BenchmarkGunzip                    114226016      115127398      +0.79%
BenchmarkHTTPClientServer          114689         112122         -2.24%
BenchmarkJSONEncode                24914536       26135942       +4.90%
BenchmarkJSONDecode                86832877       103620289      +19.33%
BenchmarkMandelbrot200             4833452        4898780        +1.35%
BenchmarkGoParse                   4317976        4835474        +11.98%
BenchmarkRegexpMatchEasy0_32       150            166            +10.67%
BenchmarkRegexpMatchEasy0_1K       393            402            +2.29%
BenchmarkRegexpMatchEasy1_32       125            142            +13.60%
BenchmarkRegexpMatchEasy1_1K       1010           1236           +22.38%
BenchmarkRegexpMatchMedium_32      232            301            +29.74%
BenchmarkRegexpMatchMedium_1K      76963          102721         +33.47%
BenchmarkRegexpMatchHard_32        3833           5463           +42.53%
BenchmarkRegexpMatchHard_1K        119668         161614         +35.05%
BenchmarkRevcomp                   763449047      706768534      -7.42%
BenchmarkTemplate                  124954724      134834549      +7.91%
BenchmarkTimeParse                 517            511            -1.16%
BenchmarkTimeFormat                501            514            +2.59%

benchmark                         old MB/s     new MB/s     speedup
BenchmarkGobDecode                53.31        52.26        0.98x
BenchmarkGobEncode                61.12        59.28        0.97x
BenchmarkGzip                     42.79        41.08        0.96x
BenchmarkGunzip                   169.88       168.55       0.99x
BenchmarkJSONEncode               77.89        74.25        0.95x
BenchmarkJSONDecode               22.35        18.73        0.84x
BenchmarkGoParse                  13.41        11.98        0.89x
BenchmarkRegexpMatchEasy0_32      213.30       191.72       0.90x
BenchmarkRegexpMatchEasy0_1K      2603.92      2542.74      0.98x
BenchmarkRegexpMatchEasy1_32      254.00       224.93       0.89x
BenchmarkRegexpMatchEasy1_1K      1013.53      827.98       0.82x
BenchmarkRegexpMatchMedium_32     4.30         3.31         0.77x
BenchmarkRegexpMatchMedium_1K     13.30        9.97         0.75x
BenchmarkRegexpMatchHard_32       8.35         5.86         0.70x
BenchmarkRegexpMatchHard_1K       8.56         6.34         0.74x
BenchmarkRevcomp                  332.92       359.62       1.08x
BenchmarkTemplate                 15.53        14.39        0.93x

LGTM=rlh
R=rlh
CC=dvyukov, golang-codereviews, iant, khr, r
https://codereview.appspot.com/136380043

10 files changed, 218 insertions, 15 deletions

diff --git a/src/cmd/gc/builtin.c b/src/cmd/gc/builtin.c
index 60b7c2f97..ee1ac1da4 100644
--- a/src/cmd/gc/builtin.c
+++ b/src/cmd/gc/builtin.c
@@ -83,6 +83,11 @@ char *runtimeimport =
 	"func @\"\".chanrecv2 (@\"\".chanType·2 *byte, @\"\".hchan·3 <-chan any, @\"\".elem·4 *any) (? bool)\n"
 	"func @\"\".chansend1 (@\"\".chanType·1 *byte, @\"\".hchan·2 chan<- any, @\"\".elem·3 *any)\n"
 	"func @\"\".closechan (@\"\".hchan·1 any)\n"
+	"func @\"\".writebarrierptr (@\"\".dst·1 *any, @\"\".src·2 any)\n"
+	"func @\"\".writebarrieriface (@\"\".dst·1 *any, @\"\".src·2 any)\n"
+	"func @\"\".writebarrierstring (@\"\".dst·1 *any, @\"\".src·2 any)\n"
+	"func @\"\".writebarrierslice (@\"\".dst·1 *any, @\"\".src·2 any)\n"
+	"func @\"\".writebarrierfat (@\"\".typ·1 *byte, @\"\".dst·2 *any, @\"\".src·3 *any)\n"
 	"func @\"\".selectnbsend (@\"\".chanType·2 *byte, @\"\".hchan·3 chan<- any, @\"\".elem·4 *any) (? bool)\n"
 	"func @\"\".selectnbrecv (@\"\".chanType·2 *byte, @\"\".elem·3 *any, @\"\".hchan·4 <-chan any) (? bool)\n"
 	"func @\"\".selectnbrecv2 (@\"\".chanType·2 *byte, @\"\".elem·3 *any, @\"\".received·4 *bool, @\"\".hchan·5 <-chan any) (? bool)\n"
diff --git a/src/cmd/gc/go.h b/src/cmd/gc/go.h
index 12c1e9853..8178f7272 100644
--- a/src/cmd/gc/go.h
+++ b/src/cmd/gc/go.h
@@ -973,6 +973,7 @@ EXTERN	int	funcdepth;
 EXTERN	int	typecheckok;
 EXTERN	int	compiling_runtime;
 EXTERN	int	compiling_wrappers;
+EXTERN	int	use_writebarrier;
 EXTERN	int	pure_go;
 EXTERN	char*	flag_installsuffix;
 EXTERN	int	flag_race;
@@ -1284,6 +1285,7 @@ LSym*	linksym(Sym*);
  *	order.c
  */
 void	order(Node *fn);
+void	orderstmtinplace(Node **stmt);
 
 /*
  *	range.c
@@ -1464,6 +1466,7 @@ void	walkstmt(Node **np);
 void	walkstmtlist(NodeList *l);
 Node*	conv(Node*, Type*);
 int	candiscard(Node*);
+int	needwritebarrier(Node*, Node*);
 Node*	outervalue(Node*);
 void	usefield(Node*);
 
diff --git a/src/cmd/gc/lex.c b/src/cmd/gc/lex.c
index b8252a225..6d8317747 100644
--- a/src/cmd/gc/lex.c
+++ b/src/cmd/gc/lex.c
@@ -312,6 +312,8 @@ main(int argc, char *argv[])
 	flagcount("u", "reject unsafe code", &safemode);
 	flagcount("v", "increase debug verbosity", &debug['v']);
 	flagcount("w", "debug type checking", &debug['w']);
+	use_writebarrier = 1;
+	flagcount("wb", "enable write barrier", &use_writebarrier);
 	flagcount("x", "debug lexer", &debug['x']);
 	flagcount("y", "debug declarations in canned imports (with -d)", &debug['y']);
 	if(thechar == '6')
diff --git a/src/cmd/gc/order.c b/src/cmd/gc/order.c
index d11e9828c..9e64eb775 100644
--- a/src/cmd/gc/order.c
+++ b/src/cmd/gc/order.c
@@ -317,7 +317,7 @@ orderexprinplace(Node **np, Order *outer)
 
 // Orderstmtinplace orders the side effects of the single statement *np
 // and replaces it with the resulting statement list.
-static void
+void
 orderstmtinplace(Node **np)
 {
 	Node *n;
@@ -451,7 +451,7 @@ ordermapassign(Node *n, Order *order)
 
 	case OAS:
 		order->out = list(order->out, n);
-		if(n->left->op == OINDEXMAP && !isaddrokay(n->right)) {
+		if((n->left->op == OINDEXMAP || (needwritebarrier(n->left, n->right) && n->left->type->width > widthptr)) && !isaddrokay(n->right)) {
 			m = n->left;
 			n->left = ordertemp(m->type, order, 0);
 			a = nod(OAS, m, n->left);
diff --git a/src/cmd/gc/runtime.go b/src/cmd/gc/runtime.go
index 128fd1a31..fa927a58a 100644
--- a/src/cmd/gc/runtime.go
+++ b/src/cmd/gc/runtime.go
@@ -107,6 +107,13 @@ func chanrecv2(chanType *byte, hchan <-chan any, elem *any) bool
 func chansend1(chanType *byte, hchan chan<- any, elem *any)
 func closechan(hchan any)
 
+// *byte is really *runtime.Type
+func writebarrierptr(dst *any, src any)
+func writebarrierstring(dst *any, src any)
+func writebarrierslice(dst *any, src any)
+func writebarrieriface(dst *any, src any)
+func writebarrierfat(typ *byte, dst *any, src *any)
+
 func selectnbsend(chanType *byte, hchan chan<- any, elem *any) bool
 func selectnbrecv(chanType *byte, elem *any, hchan <-chan any) bool
 func selectnbrecv2(chanType *byte, elem *any, received *bool, hchan <-chan any) bool
diff --git a/src/cmd/gc/sinit.c b/src/cmd/gc/sinit.c
index 59804cd8d..508747e5a 100644
--- a/src/cmd/gc/sinit.c
+++ b/src/cmd/gc/sinit.c
@@ -633,11 +633,14 @@ structlit(int ctxt, int pass, Node *n, Node *var, NodeList **init)
 		a = nod(ODOT, var, newname(index->sym));
 		a = nod(OAS, a, value);
 		typecheck(&a, Etop);
-		walkexpr(&a, init);
 		if(pass == 1) {
+			walkexpr(&a, init);	// add any assignments in r to top
 			if(a->op != OAS)
 				fatal("structlit: not as");
 			a->dodata = 2;
+		} else {
+			orderstmtinplace(&a);
+			walkstmt(&a);
 		}
 		*init = list(*init, a);
 	}
@@ -693,11 +696,14 @@ arraylit(int ctxt, int pass, Node *n, Node *var, NodeList **init)
 		a = nod(OINDEX, var, index);
 		a = nod(OAS, a, value);
 		typecheck(&a, Etop);
-		walkexpr(&a, init);	// add any assignments in r to top
 		if(pass == 1) {
+			walkexpr(&a, init);
 			if(a->op != OAS)
-				fatal("structlit: not as");
+				fatal("arraylit: not as");
 			a->dodata = 2;
+		} else {
+			orderstmtinplace(&a);
+			walkstmt(&a);
 		}
 		*init = list(*init, a);
 	}
@@ -807,7 +813,8 @@ slicelit(int ctxt, Node *n, Node *var, NodeList **init)
 	// make slice out of heap (5)
 	a = nod(OAS, var, nod(OSLICE, vauto, nod(OKEY, N, N)));
 	typecheck(&a, Etop);
-	walkexpr(&a, init);
+	orderstmtinplace(&a);
+	walkstmt(&a);
 	*init = list(*init, a);
 
 	// put dynamics into slice (6)
@@ -839,7 +846,8 @@ slicelit(int ctxt, Node *n, Node *var, NodeList **init)
 		// build list of var[c] = expr
 		a = nod(OAS, a, value);
 		typecheck(&a, Etop);
-		walkexpr(&a, init);
+		orderstmtinplace(&a);
+		walkstmt(&a);
 		*init = list(*init, a);
 	}
 }
diff --git a/src/cmd/gc/walk.c b/src/cmd/gc/walk.c
index 5f24db2b0..ce0f3eb95 100644
--- a/src/cmd/gc/walk.c
+++ b/src/cmd/gc/walk.c
@@ -8,6 +8,8 @@
 #include	"../ld/textflag.h"
 
 static	Node*	walkprint(Node*, NodeList**, int);
+static	Node*	writebarrierfn(char*, Type*, Type*);
+static	Node*	applywritebarrier(Node*, NodeList**);
 static	Node*	mapfn(char*, Type*);
 static	Node*	mapfndel(char*, Type*);
 static	Node*	ascompatee1(int, Node*, Node*, NodeList**);
@@ -633,6 +635,7 @@ walkexpr(Node **np, NodeList **init)
 			r = convas(nod(OAS, n->left, n->right), init);
 			r->dodata = n->dodata;
 			n = r;
+			n = applywritebarrier(n, init);
 		}
 
 		goto ret;
@@ -644,6 +647,8 @@ walkexpr(Node **np, NodeList **init)
 		walkexprlistsafe(n->rlist, init);
 		ll = ascompatee(OAS, n->list, n->rlist, init);
 		ll = reorder3(ll);
+		for(lr = ll; lr != nil; lr = lr->next)
+			lr->n = applywritebarrier(lr->n, init);
 		n = liststmt(ll);
 		goto ret;
 
@@ -656,6 +661,8 @@ walkexpr(Node **np, NodeList **init)
 		walkexpr(&r, init);
 
 		ll = ascompatet(n->op, n->list, &r->type, 0, init);
+		for(lr = ll; lr != nil; lr = lr->next)
+			lr->n = applywritebarrier(lr->n, init);
 		n = liststmt(concat(list1(r), ll));
 		goto ret;
 
@@ -1481,8 +1488,13 @@ ascompatee(int op, NodeList *nl, NodeList *nr, NodeList **init)
 static int
 fncall(Node *l, Type *rt)
 {
+	Node r;
+
 	if(l->ullman >= UINF || l->op == OINDEXMAP)
 		return 1;
+	r.op = 0;
+	if(needwritebarrier(l, &r))
+		return 1;
 	if(eqtype(l->type, rt))
 		return 0;
 	return 1;
@@ -1533,8 +1545,10 @@ ascompatet(int op, NodeList *nl, Type **nr, int fp, NodeList **init)
 		a = nod(OAS, l, nodarg(r, fp));
 		a = convas(a, init);
 		ullmancalc(a);
-		if(a->ullman >= UINF)
+		if(a->ullman >= UINF) {
+			dump("ascompatet ucount", a);
 			ucount++;
+		}
 		nn = list(nn, a);
 		r = structnext(&saver);
 	}
@@ -1932,6 +1946,127 @@ callnew(Type *t)
 	return mkcall1(fn, ptrto(t), nil, typename(t));
 }
 
+static int
+isstack(Node *n)
+{
+	while(n->op == ODOT || n->op == OPAREN || n->op == OCONVNOP || n->op == OINDEX && isfixedarray(n->left->type))
+		n = n->left;
+	
+	switch(n->op) {
+	case OINDREG:
+		// OINDREG only ends up in walk if it's indirect of SP.
+		return 1;
+
+	case ONAME:
+		switch(n->class) {
+		case PAUTO:
+		case PPARAM:
+		case PPARAMOUT:
+			return 1;
+		}
+		break;
+	}
+	
+	return 0;
+}
+
+static int
+isglobal(Node *n)
+{
+	while(n->op == ODOT || n->op == OPAREN || n->op == OCONVNOP || n->op == OINDEX && isfixedarray(n->left->type))
+		n = n->left;
+	
+	switch(n->op) {
+	case ONAME:
+		switch(n->class) {
+		case PEXTERN:
+			return 1;
+		}
+		break;
+	}
+	
+	return 0;
+}
+
+// Do we need a write barrier for the assignment l = r?
+int
+needwritebarrier(Node *l, Node *r)
+{
+	if(!use_writebarrier)
+		return 0;
+
+	if(l == N || isblank(l))
+		return 0;
+
+	// No write barrier for write of non-pointers.
+	dowidth(l->type);
+	if(!haspointers(l->type))
+		return 0;
+
+	// No write barrier for write to stack.
+	if(isstack(l))
+		return 0;
+
+	// No write barrier for zeroing.
+	if(r == N)
+		return 0;
+
+	// No write barrier for initialization to constant.
+	if(r->op == OLITERAL)
+		return 0;
+
+	// No write barrier for storing static (read-only) data.
+	if(r->op == ONAME && strncmp(r->sym->name, "statictmp_", 10) == 0)
+		return 0;
+
+	// No write barrier for storing address of stack values,
+	// which are guaranteed only to be written to the stack.
+	if(r->op == OADDR && isstack(r->left))
+		return 0;
+
+	// No write barrier for storing address of global, which
+	// is live no matter what.
+	if(r->op == OADDR && isglobal(r->left))
+		return 0;
+
+	// Otherwise, be conservative and use write barrier.
+	return 1;
+}
+
+// TODO(rsc): Perhaps componentgen should run before this.
+static Node*
+applywritebarrier(Node *n, NodeList **init)
+{
+	Node *l, *r;
+
+	if(n->left && n->right && needwritebarrier(n->left, n->right)) {
+		l = nod(OADDR, n->left, N);
+		l->etype = 1; // addr does not escape
+		if(n->left->type->width == widthptr) {
+			n = mkcall1(writebarrierfn("writebarrierptr", n->left->type, n->right->type), T, init,
+				l, n->right);
+		} else if(n->left->type->etype == TSTRING) {
+			n = mkcall1(writebarrierfn("writebarrierstring", n->left->type, n->right->type), T, init,
+				l, n->right);
+		} else if(isslice(n->left->type)) {
+			n = mkcall1(writebarrierfn("writebarrierslice", n->left->type, n->right->type), T, init,
+				l, n->right);
+		} else if(isinter(n->left->type)) {
+			n = mkcall1(writebarrierfn("writebarrieriface", n->left->type, n->right->type), T, init,
+				l, n->right);
+		} else {
+			r = n->right;
+			while(r->op == OCONVNOP)
+				r = r->left;
+			r = nod(OADDR, r, N);
+			r->etype = 1; // addr does not escape
+			n = mkcall1(writebarrierfn("writebarrierfat", n->left->type, r->left->type), T, init,
+				typename(n->left->type), l, r);
+		}
+	}
+	return n;
+}
+
 static Node*
 convas(Node *n, NodeList **init)
 {
@@ -1971,11 +2106,10 @@ convas(Node *n, NodeList **init)
 		goto out;
 	}
 
-	if(eqtype(lt, rt))
-		goto out;
-
-	n->right = assignconv(n->right, lt, "assignment");
-	walkexpr(&n->right, init);
+	if(!eqtype(lt, rt)) {
+		n->right = assignconv(n->right, lt, "assignment");
+		walkexpr(&n->right, init);
+	}
 
 out:
 	ullmancalc(n);
@@ -2527,6 +2661,17 @@ mapfndel(char *name, Type *t)
 }
 
 static Node*
+writebarrierfn(char *name, Type *l, Type *r)
+{
+	Node *fn;
+
+	fn = syslook(name, 1);
+	argtype(fn, l);
+	argtype(fn, r);
+	return fn;
+}
+
+static Node*
 addstr(Node *n, NodeList **init)
 {
 	Node *r, *cat, *slice;
diff --git a/src/runtime/mgc0.go b/src/runtime/mgc0.go
index ec5edb024..5d6d91875 100644
--- a/src/runtime/mgc0.go
+++ b/src/runtime/mgc0.go
@@ -4,6 +4,8 @@
 
 package runtime
 
+import "unsafe"
+
 // Called from C. Returns the Go type *m.
 func gc_m_ptr(ret *interface{}) {
 	*ret = (*m)(nil)
@@ -101,3 +103,34 @@ func bgsweep() {
 		goparkunlock(&gclock, "GC sweep wait")
 	}
 }
+
+// NOTE: Really dst *unsafe.Pointer, src unsafe.Pointer,
+// but if we do that, Go inserts a write barrier on *dst = src.
+//go:nosplit
+func writebarrierptr(dst *uintptr, src uintptr) {
+	*dst = src
+}
+
+//go:nosplit
+func writebarrierstring(dst *[2]uintptr, src [2]uintptr) {
+	dst[0] = src[0]
+	dst[1] = src[1]
+}
+
+//go:nosplit
+func writebarrierslice(dst *[3]uintptr, src [3]uintptr) {
+	dst[0] = src[0]
+	dst[1] = src[1]
+	dst[2] = src[2]
+}
+
+//go:nosplit
+func writebarrieriface(dst *[2]uintptr, src [2]uintptr) {
+	dst[0] = src[0]
+	dst[1] = src[1]
+}
+
+//go:nosplit
+func writebarrierfat(typ *_type, dst, src unsafe.Pointer) {
+	memmove(dst, src, typ.size)
+}
diff --git a/test/live.go b/test/live.go
index 35099d18b..ad2db27fa 100644
--- a/test/live.go
+++ b/test/live.go
@@ -1,4 +1,4 @@
-// errorcheck -0 -l -live
+// errorcheck -0 -l -live -wb=0
 
 // Copyright 2014 The Go Authors.  All rights reserved.
 // Use of this source code is governed by a BSD-style
diff --git a/test/live2.go b/test/live2.go
index 1e3279402..5762b2e28 100644
--- a/test/live2.go
+++ b/test/live2.go
@@ -1,4 +1,4 @@
-// errorcheck -0 -live
+// errorcheck -0 -live -wb=0
 
 // Copyright 2014 The Go Authors.  All rights reserved.
 // Use of this source code is governed by a BSD-style