gc: fix label recursion bugs

Was keeping a pointer to the labeled statement in n->right,
which meant that generic traversals of the tree visited it twice.
That combined with aggressive flattening of the block
structure when possible during parsing meant that
the kinds of label: code label: code label: code sequences
generated by yacc were giving the recursion 2ⁿ paths
through the program.

Fixes #2212.

R=lvd
CC=golang-dev
https://golang.org/cl/4960050

5 files changed, 218 insertions, 8 deletions

diff --git a/src/cmd/gc/gen.c b/src/cmd/gc/gen.c
index 7dbe2c4cb8..d585c451a2 100644
--- a/src/cmd/gc/gen.c
+++ b/src/cmd/gc/gen.c
@@ -287,7 +287,7 @@ stmtlabel(Node *n)
 	if(n->sym != S)
 	if((lab = n->sym->label) != L)
 	if(lab->def != N)
-	if(lab->def->right == n)
+	if(lab->def->defn == n)
 		return lab;
 	return L;
 }
@@ -355,13 +355,13 @@ gen(Node *n)
 		if(lab->labelpc == P)
 			lab->labelpc = pc;
 
-		if(n->right) {
-			switch(n->right->op) {
+		if(n->defn) {
+			switch(n->defn->op) {
 			case OFOR:
 			case OSWITCH:
 			case OSELECT:
 				// so stmtlabel can find the label
-				n->right->sym = lab->sym;
+				n->defn->sym = lab->sym;
 			}
 		}
 		break;
diff --git a/src/cmd/gc/go.h b/src/cmd/gc/go.h
index 4367c9cb40..42f2140255 100644
--- a/src/cmd/gc/go.h
+++ b/src/cmd/gc/go.h
@@ -286,7 +286,7 @@ struct	Node
 
 	// ONAME
 	Node*	ntype;
-	Node*	defn;
+	Node*	defn;	// ONAME: initializing assignment; OLABEL: labeled statement
 	Node*	pack;	// real package for import . names
 	Node*	curfn;	// function for local variables
 	Type*	paramfld; // TFIELD for this PPARAM
diff --git a/src/cmd/gc/go.y b/src/cmd/gc/go.y
index 373d42f136..2ec8d888b5 100644
--- a/src/cmd/gc/go.y
+++ b/src/cmd/gc/go.y
@@ -1496,7 +1496,7 @@ non_dcl_stmt:
 	{
 		NodeList *l;
 
-		$1->right = $4;
+		$1->defn = $4;
 		l = list1($1);
 		if($4)
 			l = list(l, $4);
diff --git a/src/cmd/gc/subr.c b/src/cmd/gc/subr.c
index 795c128109..5ebb150212 100644
--- a/src/cmd/gc/subr.c
+++ b/src/cmd/gc/subr.c
@@ -3446,8 +3446,13 @@ list1(Node *n)
 
 	if(n == nil)
 		return nil;
-	if(n->op == OBLOCK && n->ninit == nil)
-		return n->list;
+	if(n->op == OBLOCK && n->ninit == nil) {
+		// Flatten list and steal storage.
+		// Poison pointer to catch errant uses.
+		l = n->list;
+		n->list = (NodeList*)1;
+		return l;
+	}
 	l = mal(sizeof *l);
 	l->n = n;
 	l->end = l;
diff --git a/test/escape2.go b/test/escape2.go
index 0b78624b6c..c21a188308 100644
--- a/test/escape2.go
+++ b/test/escape2.go
@@ -780,3 +780,208 @@ func external(*int)
 func foo119(x *int) {  // ERROR "leaking param: NAME-x"
 	external(x)
 }
+
+func foo120() {
+	// formerly exponential time analysis
+L1:
+L2:
+L3:
+L4:
+L5:
+L6:
+L7:
+L8:
+L9:
+L10:
+L11:
+L12:
+L13:
+L14:
+L15:
+L16:
+L17:
+L18:
+L19:
+L20:
+L21:
+L22:
+L23:
+L24:
+L25:
+L26:
+L27:
+L28:
+L29:
+L30:
+L31:
+L32:
+L33:
+L34:
+L35:
+L36:
+L37:
+L38:
+L39:
+L40:
+L41:
+L42:
+L43:
+L44:
+L45:
+L46:
+L47:
+L48:
+L49:
+L50:
+L51:
+L52:
+L53:
+L54:
+L55:
+L56:
+L57:
+L58:
+L59:
+L60:
+L61:
+L62:
+L63:
+L64:
+L65:
+L66:
+L67:
+L68:
+L69:
+L70:
+L71:
+L72:
+L73:
+L74:
+L75:
+L76:
+L77:
+L78:
+L79:
+L80:
+L81:
+L82:
+L83:
+L84:
+L85:
+L86:
+L87:
+L88:
+L89:
+L90:
+L91:
+L92:
+L93:
+L94:
+L95:
+L96:
+L97:
+L98:
+L99:
+L100:
+	// use the labels to silence compiler errors
+	goto L1
+	goto L2
+	goto L3
+	goto L4
+	goto L5
+	goto L6
+	goto L7
+	goto L8
+	goto L9
+	goto L10
+	goto L11
+	goto L12
+	goto L13
+	goto L14
+	goto L15
+	goto L16
+	goto L17
+	goto L18
+	goto L19
+	goto L20
+	goto L21
+	goto L22
+	goto L23
+	goto L24
+	goto L25
+	goto L26
+	goto L27
+	goto L28
+	goto L29
+	goto L30
+	goto L31
+	goto L32
+	goto L33
+	goto L34
+	goto L35
+	goto L36
+	goto L37
+	goto L38
+	goto L39
+	goto L40
+	goto L41
+	goto L42
+	goto L43
+	goto L44
+	goto L45
+	goto L46
+	goto L47
+	goto L48
+	goto L49
+	goto L50
+	goto L51
+	goto L52
+	goto L53
+	goto L54
+	goto L55
+	goto L56
+	goto L57
+	goto L58
+	goto L59
+	goto L60
+	goto L61
+	goto L62
+	goto L63
+	goto L64
+	goto L65
+	goto L66
+	goto L67
+	goto L68
+	goto L69
+	goto L70
+	goto L71
+	goto L72
+	goto L73
+	goto L74
+	goto L75
+	goto L76
+	goto L77
+	goto L78
+	goto L79
+	goto L80
+	goto L81
+	goto L82
+	goto L83
+	goto L84
+	goto L85
+	goto L86
+	goto L87
+	goto L88
+	goto L89
+	goto L90
+	goto L91
+	goto L92
+	goto L93
+	goto L94
+	goto L95
+	goto L96
+	goto L97
+	goto L98
+	goto L99
+	goto L100
+}