new switch implementation
in preparation of type switch.
no functional change (yet).
R=r
OCL=25784
CL=25788
diff --git a/src/cmd/6g/gen.c b/src/cmd/6g/gen.c
index d14ad30..9bc6126 100644
--- a/src/cmd/6g/gen.c
+++ b/src/cmd/6g/gen.c
@@ -260,8 +260,8 @@
break;
case OFOR:
- p1 = gbranch(AJMP, T); // goto test
sbreak = breakpc;
+ p1 = gbranch(AJMP, T); // goto test
breakpc = gbranch(AJMP, T); // break: goto done
scontin = continpc;
continpc = pc;
@@ -299,15 +299,15 @@
break;
case OSWITCH:
- p1 = gbranch(AJMP, T); // goto test
sbreak = breakpc;
+ p1 = gbranch(AJMP, T); // goto test
breakpc = gbranch(AJMP, T); // break: goto done
patch(p1, pc); // test:
if(labloop != L) {
labloop->op = OFOR;
labloop->breakpc = breakpc;
}
- swgen(n); // switch(test) body
+ gen(n->nbody, L); // switch(test) body
patch(breakpc, pc); // done:
breakpc = sbreak;
break;
@@ -367,279 +367,6 @@
lineno = lno;
}
-Case*
-csort(Case *l, int(*f)(Case*, Case*))
-{
- Case *l1, *l2, *le;
-
- if(l == 0 || l->slink == 0)
- return l;
-
- l1 = l;
- l2 = l;
- for(;;) {
- l2 = l2->slink;
- if(l2 == 0)
- break;
- l2 = l2->slink;
- if(l2 == 0)
- break;
- l1 = l1->slink;
- }
-
- l2 = l1->slink;
- l1->slink = 0;
- l1 = csort(l, f);
- l2 = csort(l2, f);
-
- /* set up lead element */
- if((*f)(l1, l2) < 0) {
- l = l1;
- l1 = l1->slink;
- } else {
- l = l2;
- l2 = l2->slink;
- }
- le = l;
-
- for(;;) {
- if(l1 == 0) {
- while(l2) {
- le->slink = l2;
- le = l2;
- l2 = l2->slink;
- }
- le->slink = 0;
- break;
- }
- if(l2 == 0) {
- while(l1) {
- le->slink = l1;
- le = l1;
- l1 = l1->slink;
- }
- break;
- }
- if((*f)(l1, l2) < 0) {
- le->slink = l1;
- le = l1;
- l1 = l1->slink;
- } else {
- le->slink = l2;
- le = l2;
- l2 = l2->slink;
- }
- }
- le->slink = 0;
- return l;
-}
-
-int
-casecmp(Case *c1, Case *c2)
-{
- int w;
-
- w = whatis(c1->scase);
- if(w != whatis(c2->scase))
- fatal("casecmp1");
-
- switch(w) {
- case Wlitfloat:
- return mpcmpfltflt(c1->scase->val.u.fval, c2->scase->val.u.fval);
- case Wlitint:
- return mpcmpfixfix(c1->scase->val.u.xval, c2->scase->val.u.xval);
- case Wlitstr:
- return cmpslit(c1->scase, c2->scase);
-// case Wlitbool:
-// case Wlitnil:
- }
-
- fatal("casecmp2");
- return 0;
-}
-
-void
-swconst(Case *sa, int nc, Node *n1, Node *tmp)
-{
- Case *s, *sb;
- Prog *p1, *p2, *p3;
- int n;
-
- // small number of cases --
- // test them sequentially
- if(nc < 4) {
- for(s=sa; s!=C; s=s->slink) {
- setlineno(s->scase);
- memset(n1, 0, sizeof(*n1));
- n1->op = OEQ;
- n1->left = tmp;
- n1->right = s->scase;
- walktype(n1, Erv);
- bgen(n1, 1, s->sprog);
- }
- return;
- }
-
- // large number of cases --
- // find the middle and recur on each half
-
- n = nc/2;
- for(s=sa; s!=C; s=s->slink) {
- n--;
- if(n == 0)
- break;
- }
- n = nc/2;
- sb = s->slink;
- s->slink = C;
-
- p1 = gbranch(AJMP, T); // goto midcmp
- p2 = pc; // low half of switch
- swconst(sa, n, n1, tmp);
-
- p3 = gbranch(AJMP, T); // goto end
- patch(p1, pc);
-
- setlineno(s->scase);
- memset(n1, 0, sizeof(*n1));
- n1->op = OLE;
- n1->left = tmp;
- n1->right = s->scase;
- walktype(n1, Erv);
- bgen(n1, 1, p2);
-
- swconst(sb, nc-n, n1, tmp); // high half of switch
- patch(p3, pc);
-}
-
-void
-swgen(Node *n)
-{
- Node *c1, *c2;
- Node n1, tmp;
- Case *s0, *se, *s, *sa;
- Prog *p1, *dflt;
- int32 lno;
- int any, nc;
- Iter save1, save2;
-
-// botch - put most of this code in
-// walk. gen binary search for
-// sequence of constant cases
-
- lno = setlineno(n);
-
- p1 = gbranch(AJMP, T);
- s0 = C;
- se = C;
-
- // walk thru the body placing breaks
- // and labels into the case statements
-
- any = 0;
- dflt = P;
- c1 = listfirst(&save1, &n->nbody);
- while(c1 != N) {
- setlineno(c1);
- if(c1->op == OEMPTY)
- break;
- if(c1->op != OCASE) {
- if(s0 == C && dflt == P)
- yyerror("unreachable statements in a switch");
- gen(c1, L);
-
- any = 1;
- if(c1->op == OFALL)
- any = 0;
- c1 = listnext(&save1);
- continue;
- }
-
- // put in the break between cases
- if(any)
- patch(gbranch(AJMP, T), breakpc);
- any = 1;
-
- // loop over case expressions
- c2 = listfirst(&save2, &c1->left);
- if(c2 == N)
- dflt = pc;
-
- while(c2 != N) {
- s = mal(sizeof(*s));
- if(s0 == C)
- s0 = s;
- else
- se->slink = s;
- se = s;
-
- s->scase = c2; // case expression
- s->sprog = pc; // where to go
-
- c2 = listnext(&save2);
- }
-
- c1 = listnext(&save1);
- }
-
- lineno = lno;
-
- if(any)
- patch(gbranch(AJMP, T), breakpc);
-
- patch(p1, pc);
-
- if(n->ntest != N)
- if(n->ntest->ninit != N)
- gen(n->ntest->ninit, L);
- tempname(&tmp, n->ntest->type);
- cgen(n->ntest, &tmp);
-
- sa = C; // base of constant cases
- nc = 0;
- for(s=s0; s!=C; s=s->slink) {
- switch(whatis(s->scase)) {
- case Wlitfloat:
- case Wlitint:
- case Wlitstr:
-// case Wlitbool:
-// case Wlitnil:
- nc++;
- if(sa == C)
- sa = s;
- se = s;
- continue;
- }
- if(sa != C) {
- se->slink = C;
- sa = csort(sa, casecmp);
- swconst(sa, nc, &n1, &tmp);
- nc = 0;
- sa = C;
- }
- setlineno(s->scase);
- memset(&n1, 0, sizeof(n1));
- n1.op = OEQ;
- n1.left = &tmp;
- n1.right = s->scase;
- walktype(&n1, Erv);
- bgen(&n1, 1, s->sprog);
- }
- if(sa != C) {
- se->slink = C;
- sa = csort(sa, casecmp);
- swconst(sa, nc, &n1, &tmp);
- }
- if(dflt != P) {
- patch(gbranch(AJMP, T), dflt);
- goto ret;
- }
- patch(gbranch(AJMP, T), breakpc);
-
-ret:
- lineno = lno;
-}
-
void
inarggen(void)
{
diff --git a/src/cmd/6g/gg.h b/src/cmd/6g/gg.h
index a44f104..741527c 100644
--- a/src/cmd/6g/gg.h
+++ b/src/cmd/6g/gg.h
@@ -64,15 +64,6 @@
Sig* link;
};
-typedef struct Case Case;
-struct Case
-{
- Prog* sprog;
- Node* scase;
- Case* slink;
-};
-#define C ((Case*)0)
-
typedef struct Pool Pool;
struct Pool
{
@@ -143,8 +134,6 @@
void compile(Node*);
void proglist(void);
void gen(Node*, Label*);
-void swgen(Node*);
-void selgen(Node*);
Node* lookdot(Node*, Node*, int);
void inarggen(void);
void cgen_as(Node*, Node*);
diff --git a/src/cmd/gc/Makefile b/src/cmd/gc/Makefile
index 1ab4497..4237e97 100644
--- a/src/cmd/gc/Makefile
+++ b/src/cmd/gc/Makefile
@@ -21,6 +21,7 @@
dcl.$O\
export.$O\
walk.$O\
+ swt.$O\
const.$O\
mparith1.$O\
mparith2.$O\
diff --git a/src/cmd/gc/go.h b/src/cmd/gc/go.h
index 76e440d..dfd975f 100644
--- a/src/cmd/gc/go.h
+++ b/src/cmd/gc/go.h
@@ -812,8 +812,7 @@
void walkconv(Node*);
void walkas(Node*);
void walkbool(Node*);
-Type* walkswitch(Node*, Type*(*)(Node*, Type*));
-int casebody(Node*);
+void walkswitch(Node*);
void walkselect(Node*);
int whatis(Node*);
void walkdot(Node*);
diff --git a/src/cmd/gc/subr.c b/src/cmd/gc/subr.c
index bb2c31e..aa8b01a 100644
--- a/src/cmd/gc/subr.c
+++ b/src/cmd/gc/subr.c
@@ -547,8 +547,11 @@
return;
case OCASE:
- // the right side points to the next case
- print("%O%J\n", n->op, n);
+ // the right side points to label of the body
+ if(n->right != N && n->right->op == OGOTO && n->right->left->op == ONAME)
+ print("%O%J GOTO %N\n", n->op, n, n->right->left);
+ else
+ print("%O%J\n", n->op, n);
dodump(n->left, dep+1);
return;
}
@@ -654,8 +657,8 @@
[OCMP] = "CMP",
[OFALL] = "FALL",
[OCOMPOS] = "COMPOS",
- [ODOTTYPE] = "DOTTYPE",
- [OCONV] = "CONV",
+ [ODOTTYPE] = "DOTTYPE",
+ [OCONV] = "CONV",
[OCOM] = "COM",
[OCONST] = "CONST",
[OCONTINUE] = "CONTINUE",
@@ -724,7 +727,7 @@
[OPRINT] = "PRINT",
[OPRINTN] = "PRINTN",
[OPARAM] = "PARAM",
- [ODCL] = "DCL",
+ [ODCL] = "DCL",
[OXXX] = "XXX",
};
diff --git a/src/cmd/gc/swt.c b/src/cmd/gc/swt.c
new file mode 100644
index 0000000..dc32665
--- /dev/null
+++ b/src/cmd/gc/swt.c
@@ -0,0 +1,333 @@
+// Copyright 2009 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 "go.h"
+
+/*
+ * walktype
+ */
+Type*
+sw0(Node *c, Type *place)
+{
+ Node *r;
+
+ if(c == N)
+ return T;
+ if(c->op != OAS) {
+ walktype(c, Erv);
+ return T;
+ }
+ walktype(c->left, Elv);
+
+ r = c->right;
+ if(c == N)
+ return T;
+
+ switch(r->op) {
+ default:
+ goto bad;
+ case ORECV:
+ // <-chan
+ walktype(r->left, Erv);
+ if(!istype(r->left->type, TCHAN))
+ goto bad;
+ break;
+ case OINDEX:
+ // map[e]
+ walktype(r->left, Erv);
+ if(!istype(r->left->type, TMAP))
+ goto bad;
+ break;
+ case ODOTTYPE:
+ // interface.(type)
+ walktype(r->left, Erv);
+ if(!istype(r->left->type, TINTER))
+ goto bad;
+ break;
+ }
+ c->type = types[TBOOL];
+ return T;
+
+bad:
+ yyerror("inappropriate assignment in a case statement");
+ return T;
+}
+
+/*
+ * return the first type
+ */
+Type*
+sw1(Node *c, Type *place)
+{
+ if(place == T)
+ return c->type;
+ return place;
+}
+
+/*
+ * return a suitable type
+ */
+Type*
+sw2(Node *c, Type *place)
+{
+ return types[TINT]; // botch
+}
+
+/*
+ * check that switch type
+ * is compat with all the cases
+ */
+Type*
+sw3(Node *c, Type *place)
+{
+ if(place == T)
+ return c->type;
+ if(c->type == T)
+ c->type = place;
+ convlit(c, place);
+ if(!ascompat(place, c->type))
+ badtype(OSWITCH, place, c->type);
+ return place;
+}
+
+/*
+ * over all cases, call paramenter function.
+ * four passes of these are used to allocate
+ * types to cases and switch
+ */
+Type*
+walkcases(Node *sw, Type*(*call)(Node*, Type*))
+{
+ Iter save;
+ Node *n;
+ Type *place;
+ int32 lno;
+
+ lno = setlineno(sw);
+ place = call(sw->ntest, T);
+
+ n = listfirst(&save, &sw->nbody->left);
+ if(n->op == OEMPTY)
+ return T;
+
+loop:
+ if(n == N) {
+ lineno = lno;
+ return place;
+ }
+
+ if(n->op != OCASE)
+ fatal("walkcases: not case %O\n", n->op);
+
+ if(n->left != N) {
+ setlineno(n->left);
+ place = call(n->left, place);
+ }
+ n = listnext(&save);
+ goto loop;
+}
+
+Node*
+newlabel()
+{
+ static int label;
+
+ label++;
+ snprint(namebuf, sizeof(namebuf), "%.6d", label);
+ return newname(lookup(namebuf));
+}
+
+/*
+ * build separate list of statements and cases
+ * make labels between cases and statements
+ * deal with fallthrough, break, unreachable statements
+ */
+void
+casebody(Node *sw)
+{
+ Iter save;
+ Node *os, *oc, *t, *c;
+ Node *cas, *stat, *def;
+ Node *go, *br;
+ int32 lno;
+
+ lno = setlineno(sw);
+ t = listfirst(&save, &sw->nbody);
+ if(t == N || t->op == OEMPTY) {
+ sw->nbody = nod(OLIST, N, N);
+ return;
+ }
+
+ cas = N; // cases
+ stat = N; // statements
+ def = N; // defaults
+ os = N; // last statement
+ oc = N; // last case
+ br = nod(OBREAK, N, N);
+
+loop:
+
+ if(t == N) {
+ if(oc == N && os != N)
+ yyerror("first switch statement must be a case");
+
+ stat = list(stat, br);
+ cas = list(cas, def);
+
+ sw->nbody = nod(OLIST, rev(cas), rev(stat));
+//dump("case", sw->nbody->left);
+//dump("stat", sw->nbody->right);
+ lineno = lno;
+ return;
+ }
+
+ lno = setlineno(t);
+
+ switch(t->op) {
+ case OXCASE:
+ t->op = OCASE;
+ if(oc == N && os != N)
+ yyerror("first switch statement must be a case");
+
+ if(os != N && os->op == OXFALL)
+ os->op = OFALL;
+ else
+ stat = list(stat, br);
+
+ go = nod(OGOTO, newlabel(), N);
+
+ c = t->left;
+ if(c == N) {
+ if(def != N)
+ yyerror("more than one default case");
+
+ // reuse original default case
+ t->right = go;
+ def = t;
+ }
+
+ // expand multi-valued cases
+ for(; c!=N; c=c->right) {
+ if(c->op != OLIST) {
+ // reuse original case
+ t->left = c;
+ t->right = go;
+ cas = list(cas, t);
+ break;
+ }
+ cas = list(cas, nod(OCASE, c->left, go));
+ }
+ stat = list(stat, nod(OLABEL, go->left, N));
+ oc = t;
+ os = N;
+ break;
+
+ default:
+ stat = list(stat, t);
+ os = t;
+ break;
+ }
+ t = listnext(&save);
+ goto loop;
+}
+
+/*
+ * rebulid case statements into if .. goto
+ */
+void
+prepsw(Node *sw)
+{
+ Iter save;
+ Node *name, *cas;
+ Node *t, *a;
+ int bool;
+
+ bool = 0;
+ if(whatis(sw->ntest) == Wlitbool) {
+ bool = 1; // true
+ if(sw->ntest->val.u.xval == 0)
+ bool = 2; // false
+ }
+
+ cas = N;
+ name = N;
+ if(bool == 0) {
+ name = nod(OXXX, N, N);
+ tempname(name, sw->ntest->type);
+ cas = nod(OAS, name, sw->ntest);
+ }
+
+ t = listfirst(&save, &sw->nbody->left);
+
+loop:
+ if(t == N) {
+ sw->nbody->left = rev(cas);
+ walkstate(sw->nbody->left);
+//dump("case", sw->nbody->left);
+ return;
+ }
+
+ if(t->left == N) {
+ cas = list(cas, t->right); // goto default
+ t = listnext(&save);
+ goto loop;
+ }
+
+ a = nod(OIF, N, N);
+ a->nbody = t->right; // then goto l
+
+ switch(bool) {
+ default:
+ // not bool const
+ a->ntest = nod(OEQ, name, t->left); // if name == val
+ break;
+
+ case 1:
+ // bool true
+ a->ntest = t->left; // if val
+ break;
+
+ case 2:
+ // bool false
+ a->ntest = nod(ONOT, t->left, N); // if !val
+ break;
+ }
+ cas = list(cas, a);
+
+ t = listnext(&save);
+ goto loop;
+}
+
+void
+walkswitch(Node *n)
+{
+ Type *t;
+
+ casebody(n);
+ if(n->ntest == N)
+ n->ntest = booltrue;
+
+ walkstate(n->ninit);
+ walktype(n->ntest, Erv);
+ walkstate(n->nbody);
+
+ // walktype
+ walkcases(n, sw0);
+
+ // find common type
+ t = n->ntest->type;
+ if(t == T)
+ t = walkcases(n, sw1);
+
+ // if that fails pick a type
+ if(t == T)
+ t = walkcases(n, sw2);
+
+ // set the type on all literals
+ if(t != T) {
+ walkcases(n, sw3);
+ convlit(n->ntest, t);
+ prepsw(n);
+ }
+}
diff --git a/src/cmd/gc/walk.c b/src/cmd/gc/walk.c
index 3ae0f52..d82dfd4 100644
--- a/src/cmd/gc/walk.c
+++ b/src/cmd/gc/walk.c
@@ -4,9 +4,6 @@
#include "go.h"
-static Type* sw1(Node*, Type*);
-static Type* sw2(Node*, Type*);
-static Type* sw3(Node*, Type*);
static Node* curfn;
enum
@@ -318,26 +315,7 @@
if(top != Etop)
goto nottop;
- casebody(n->nbody);
- if(n->ntest == N)
- n->ntest = booltrue;
- walkstate(n->ninit);
- walktype(n->ntest, Erv);
- walkstate(n->nbody);
-
- // find common type
- if(n->ntest->type == T)
- n->ntest->type = walkswitch(n, sw1);
-
- // if that fails pick a type
- if(n->ntest->type == T)
- n->ntest->type = walkswitch(n, sw2);
-
- // set the type on all literals
- if(n->ntest->type != T)
- walkswitch(n, sw3);
- walktype(n->ntest, Erv); // BOTCH is this right
- walktype(n->nincr, Erv);
+ walkswitch(n);
goto ret;
case OSELECT:
@@ -577,7 +555,6 @@
case OCASE:
if(top != Etop)
goto nottop;
- walktype(n->left, Erv);
walkstate(n->right);
goto ret;
@@ -1251,124 +1228,11 @@
bad:
if(l->type != T)
yyerror("invalid conversion: %T to %T", l->type, t);
- else if(n->left->op == OLIST)
+ else
+ if(n->left->op == OLIST)
yyerror("invalid type for composite literal: %T", t);
}
-
-/*
- * return the first type
- */
-Type*
-sw1(Node *c, Type *place)
-{
- if(place == T)
- return c->type;
- return place;
-}
-
-/*
- * return a suitable type
- */
-Type*
-sw2(Node *c, Type *place)
-{
- return types[TINT]; // botch
-}
-
-/*
- * check that switch type
- * is compat with all the cases
- */
-Type*
-sw3(Node *c, Type *place)
-{
- if(place == T)
- return c->type;
- if(c->type == T)
- c->type = place;
- convlit(c, place);
- if(!ascompat(place, c->type))
- badtype(OSWITCH, place, c->type);
- return place;
-}
-
-Type*
-walkswitch(Node *sw, Type*(*call)(Node*, Type*))
-{
- Node *n, *c;
- Type *place;
- place = call(sw->ntest, T);
-
- setlineno(sw);
-
- n = sw->nbody;
- if(n->op == OLIST)
- n = n->left;
- if(n->op == OEMPTY)
- return T;
-
- for(; n!=N; n=n->right) {
- if(n->op != OCASE)
- fatal("walkswitch: not case %O\n", n->op);
- for(c=n->left; c!=N; c=c->right) {
- if(c->op != OLIST) {
- setlineno(c);
- place = call(c, place);
- break;
- }
- setlineno(c);
- place = call(c->left, place);
- }
- }
- return place;
-}
-
-int
-casebody(Node *n)
-{
- Node *oc, *ot, *t;
- Iter save;
-
- /*
- * look to see if statements at top level have
- * case labels attached to them. convert the illegal
- * ops XFALL and XCASE into legal ops FALL and CASE.
- * all unconverted ops will thus be caught as illegal
- */
-
- oc = N; // last case statement
- ot = N; // last statement (look for XFALL)
- t = listfirst(&save, &n);
-
-loop:
- if(t == N) {
- /* empty switch */
- if(oc == N)
- return 0;
- return 1;
- }
- if(t->op == OXCASE) {
- /* rewrite and link top level cases */
- t->op = OCASE;
- if(oc != N)
- oc->right = t;
- oc = t;
-
- /* rewrite top fall that preceed case */
- if(ot != N && ot->op == OXFALL)
- ot->op = OFALL;
- }
-
- /* if first statement is not case */
- if(oc == N)
- return 0;
-
- ot = t;
- t = listnext(&save);
- goto loop;
-}
-
Node*
selcase(Node *n, Node *var)
{
@@ -1477,21 +1341,58 @@
return r;
}
+/*
+ * enumerate the special cases
+ * of the case statement:
+ * case v := <-chan // select and switch
+ * case v := map[] // switch
+ * case v := interface.(TYPE) // switch
+ */
Node*
selectas(Node *name, Node *expr)
{
Node *a;
Type *t;
- if(expr == N || expr->op != ORECV)
+ if(expr == N)
goto bad;
- walktype(expr->left, Erv);
- t = expr->left->type;
- if(t == T)
+ switch(expr->op) {
+ default:
+//dump("case", expr);
goto bad;
- if(t->etype != TCHAN)
- goto bad;
- a = old2new(name, t->type);
+
+ case ORECV:
+ walktype(expr->left, Erv);
+ t = expr->left->type;
+ if(t == T)
+ goto bad;
+ if(t->etype != TCHAN)
+ goto bad;
+ t = t->type;
+ break;
+
+ case OINDEX:
+ walktype(expr->left, Erv);
+ walktype(expr->right, Erv);
+ t = expr->left->type;
+ if(t == T)
+ goto bad;
+ if(t->etype != TMAP)
+ goto bad;
+ t = t->type;
+ break;
+
+ case ODOTTYPE:
+ walktype(expr->left, Erv);
+ t = expr->left->type;
+ if(t == T)
+ goto bad;
+ if(t->etype != TINTER)
+ goto bad;
+ t = expr->type;
+ break;
+ }
+ a = old2new(name, t);
return a;
bad:
@@ -1523,7 +1424,7 @@
oc = N; // last case
def = N; // default case
- for(count=0; n!=N; n=listnext(&iter)) {
+ for(; n!=N; n=listnext(&iter)) {
setlineno(n);
switch(n->op) {
