commit 81ce26fac7e8ea5221092d6bf21c8495b38e1090
parent f5e0ed92d0d023e592dacb0152f7161c5b959200
Author: Roberto E. Vargas Caballero <k0ga@shike2.com>
Date: Wed, 1 Jan 2025 18:46:10 +0100
cc2: Rewrite switch data structure
It is better to use an array for the switch table because it makes
easier to sort the values that it is something required for several of
the implementations for switch using jummp tables.
Also, as this transformation is done in sethi() it can be reused for
differnt targets without duplication. Currently, as qbe does not support
computed gotos any jump table is disabled when the name of the backend
has the substring qbe.
Diffstat:
10 files changed, 250 insertions(+), 281 deletions(-)
diff --git a/src/cmd/scc-cc/cc2/Makefile b/src/cmd/scc-cc/cc2/Makefile
@@ -19,11 +19,12 @@ QBE_OBJS =\
main.o\
node.o\
parser.o\
+ sethi.o\
+ swtch.o\
symbol.o\
OBJS =\
cfg.o\
- swtch.o\
$(QBE_OBJS)\
QBE_AMD64_SYSV_OBJS=\
diff --git a/src/cmd/scc-cc/cc2/cc2.h b/src/cmd/scc-cc/cc2/cc2.h
@@ -1,5 +1,13 @@
#define ASLABEL 0
+#ifdef NDEBUG
+#define PRCFG(msg)
+#define PRTREE(msg)
+#else
+#define PRCFG(msg) (enadebug ? prcfg(msg) : NULL)
+#define PRTREE(msg) (enadebug ? prforest(msg) : NULL)
+#endif
+
enum iflags {
BBENTRY = 1, /* basic block entry */
BBEXIT = 2, /* basic block exit */
@@ -160,10 +168,11 @@ typedef struct swtch Swtch;
struct swtch {
int nr;
TINT min, max;
+ Node *bswtch;
+ Node *eswtch;
+ Node **cases;
Node *defnode;
- Node *cases;
- Node *first;
- Node *last;
+
Swtch *next;
};
@@ -281,7 +290,6 @@ extern Node *addstmt(Node *);
extern Node *delstmt(Node *);
extern Node *insstmt(Node *, Node *);
extern void delrange(Node *, Node *);
-extern Node *waftstmt(Node *);
extern Node *unlinkstmt(Node *);
/* symbol.c */
@@ -298,14 +306,16 @@ extern Node *sethi(Node *);
/* swtch.c */
extern void cleanswtch(void);
-extern Swtch *newswitch(Swtch *);
+extern Swtch *newswtch(Swtch *);
extern Node *swtch(Node *);
+extern Node *swtchdefault(Swtch *);
/* globals */
extern Symbol *curfun;
extern Symbol *locals;
extern Inst *pc, *prog;
extern Node *laststmt;
+extern int noswtch;
/* target */
extern Type int8type, int16type, int32type, int64type,
diff --git a/src/cmd/scc-cc/cc2/cfg.c b/src/cmd/scc-cc/cc2/cfg.c
@@ -6,14 +6,6 @@
#include "cc2.h"
-#ifdef NDEBUG
-#define PRCFG(msg)
-#define PRTREE(msg)
-#else
-#define PRCFG(msg) (enadebug ? prcfg(msg) : NULL)
-#define PRTREE(msg) (enadebug ? prforest(msg) : NULL)
-#endif
-
struct cfg {
int nr;
Block *entryb, *exitb;
@@ -26,12 +18,24 @@ static struct cfg cfg;
#ifndef NDEBUG
#include <stdio.h>
+static Node *
+jtarget(Node *np)
+{
+ return np->u.sym->u.stmt;
+}
+
+static Block *
+jtargetbb(Node *np)
+{
+ return jtarget(np)->bb;
+}
+
static void
prbb(Block *bb)
{
- Node *np;
Swtch *swt;
Block *casebb;
+ Node **cases, **bp;
if (!bb || bb->printed)
return;
@@ -54,24 +58,24 @@ prbb(Block *bb)
swt = bb->swtch;
if (!swt)
return;
+ cases = swt->cases;
- for (np = swt->cases; np->op != OESWITCH; np = np->next) {
- casebb = np->u.sym->u.stmt->bb;
-
- if (!np->left) {
- fprintf(stderr,
- "\t%d -> %d [label=\"default\"]\n",
- bb->id,
- casebb->id);
- } else {
- fprintf(stderr,
- "\t%d -> %d [label=\"case %lld\"]\n",
- bb->id,
- casebb->id,
- np->left->u.i);
- }
+ for (bp = cases; bp < &cases[swt->nr]; ++bp) {
+ casebb = jtargetbb(*bp);
+ fprintf(stderr,
+ "\t%d -> %d [label=\"case %lld\"]\n",
+ bb->id,
+ casebb->id,
+ (*bp)->left->u.i);
prbb(casebb);
}
+
+ casebb = jtargetbb(swtchdefault(swt));
+ fprintf(stderr,
+ "\t%d -> %d [label=\"default\"]\n",
+ bb->id,
+ casebb->id);
+ prbb(casebb);
}
static void
@@ -122,6 +126,9 @@ newbb(Node *np)
static Node *
mkcfg(Node *np)
{
+ if ((np->flags & (BBENTRY|BBEXIT)) == 0)
+ return np;
+
if (np->flags & BBENTRY)
cfg.cur = np->bb;
@@ -142,14 +149,12 @@ mkcfg(Node *np)
break;
case OBSWITCH:
cfg.cur->swtch = np->u.swtch;
- break;
- case OESWITCH:
cfg.cur->true = NULL;
break;
case OBRANCH:
cfg.cur->false = np->next->bb;
case OJMP:
- cfg.cur->true = np->u.sym->u.stmt->bb;
+ cfg.cur->true = jtargetbb(np);
break;
}
@@ -183,7 +188,7 @@ static Node *
markbb(Node *np)
{
Swtch *swt;
- Node *p;
+ Node **cases, **bp;
switch (np->op) {
case OBFUN:
@@ -194,16 +199,16 @@ markbb(Node *np)
newentry(np->next);
break;
case OBSWITCH:
- swt = np->u.swtch;
- for (p = swt->cases; p->op != OESWITCH; p = p->next)
- newentry(p->u.sym->u.stmt);
- break;
- case OESWITCH:
np->flags |= BBEXIT;
+ swt = np->u.swtch;
+ cases = swt->cases;
+ for (bp = cases; bp < &cases[swt->nr]; ++bp)
+ newentry(jtarget((*bp)));
+ newentry(jtarget(swtchdefault(swt)));
break;
case OBRANCH:
case OJMP:
- newentry(np->u.sym->u.stmt);
+ newentry(jtarget(np));
newentry(np->next);
break;
}
@@ -213,8 +218,8 @@ markbb(Node *np)
static void
visit(Block *bb)
{
- Node *np;
Swtch *swt;
+ Node **cases, **bp, *p;
if (!bb || bb->visited)
return;
@@ -225,9 +230,11 @@ visit(Block *bb)
swt = bb->swtch;
if (!swt)
return;
+ cases = swt->cases;
- for (np = swt->cases; np->op != OESWITCH; np = np->next)
- visit(np->u.sym->u.stmt->bb);
+ for (bp = swt->cases; bp < &cases[swt->nr]; ++bp)
+ visit(jtargetbb(*bp));
+ visit(jtargetbb(swtchdefault(swt)));
}
static void
@@ -333,49 +340,3 @@ cleancfg(void)
free(cfg.blocks);
memset(&cfg, 0, sizeof(cfg));
}
-
-Node *
-sethi(Node *np)
-{
- Node *l, *r;
-
- if (!np)
- return np;
-
- np->complex = 0;
- np->address = 0;
-
- switch (np->op) {
- case OBSWITCH:
- np = swtch(np);
- break;
- default:
- np = tsethi(np);
- }
-
- l = np->left;
- r = np->right;
-
- if (np->address > 10)
- return np;
- if (l)
- np->complex = l->complex;
- if (r) {
- int d = np->complex - r->complex;
-
- if (d == 0)
- ++np->complex;
- else if (d < 0)
- np->complex = r->complex;
- }
- if (np->complex == 0)
- ++np->complex;
-
- return np;
-}
-
-void
-genaddr(void)
-{
- apply(sethi);
-}
diff --git a/src/cmd/scc-cc/cc2/main.c b/src/cmd/scc-cc/cc2/main.c
@@ -10,6 +10,7 @@
#include "error.h"
char *argv0;
+int noswtch;
void
error(unsigned nerror, ...)
@@ -60,6 +61,9 @@ main(int argc, char *argv[])
if (argv[0] && !freopen(argv[0], "r", stdin))
die("cc2: %s: %s", argv[0], strerror(errno));
+ if (strstr(argv0, "qbe"))
+ noswtch = 1;
+
while (moreinput()) {
parse();
if (curfun) {
diff --git a/src/cmd/scc-cc/cc2/node.c b/src/cmd/scc-cc/cc2/node.c
@@ -100,21 +100,6 @@ unlinkstmt(Node *np)
return np;
}
-/*
- * Move current node after `at' and keep the current
- * pointer to the end of the list
- */
-Node *
-waftstmt(Node *at)
-{
- Node *np = curstmt, *prev = np->prev;
-
- if (prev == at)
- return np;
- curstmt = prev;
- return insstmt(unlinkstmt(np), at);
-}
-
Node *
addstmt(Node *np)
{
diff --git a/src/cmd/scc-cc/cc2/parser.c b/src/cmd/scc-cc/cc2/parser.c
@@ -334,27 +334,26 @@ oreturn(char *token, union tokenop u)
push(np);
}
-/*
- * Move np (which is a OCASE/ODEFAULT/OESWITCH) to be contigous with
- * the last switch table.
- */
static void
-waft(Node *np)
+addcase(Node *np)
{
TINT val;
+ Node **bp;
Swtch *cur;
if (swp == swtbl)
error(EWTACKU);
cur = swp - 1;
- addstmt(np);
- waftstmt(cur->last);
- cur->last = np;
if (np->op == ODEFAULT) {
cur->defnode = np;
- } else if (np->op != OESWITCH) {
+ } else {
cur->nr++;
+ bp = cur->cases;
+ bp = xrealloc(bp, cur->nr * sizeof(Node *));
+ bp[cur->nr-1] = np;
+ cur->cases = bp;
+
val = np->left->u.i;
if (val < cur->min)
cur->min = val;
@@ -376,34 +375,50 @@ bswitch(char *token, union tokenop u)
cur->min = TINT_MAX;
cur->max = TINT_MIN;
cur->defnode = NULL;
+ cur->cases = NULL;
eval(strtok(NULL, "\t\n"));
np->left = pop();
- push(cur->first = cur->last = np);
+ push(cur->bswtch = np);
+}
+
+static int
+cmpcase(const void *p1, const void *p2)
+{
+ TINT d;
+ Node *np1, *np2;
+
+ np1 = *(Node **) p1;
+ np2 = *(Node **) p2;
+ d = np1->left->u.i - np2->left->u.i;
+ if (d < 0)
+ return -1;
+ if (d > 0)
+ return 1;
+ return 0;
}
static void
eswitch(char *token, union tokenop u)
{
- Node *first;
+ Node *p;
Swtch *cur;
if (swp == swtbl)
error(EWTACKU);
jump(token, u);
- waft(pop());
cur = --swp;
- first = cur->first;
- cur->cases = first->next;
- first->u.swtch = newswitch(cur);
+ cur->eswtch = pop();
+ cur->bswtch->u.swtch = newswtch(cur);
+ qsort(cur->cases, cur->nr, sizeof(Node *), cmpcase);
}
static void
ocase(char *token, union tokenop u)
{
jump(token, u);
- waft(pop());
+ addcase(pop());
}
static void
@@ -723,4 +738,6 @@ parse(void)
if (beginf && !endf)
error(EBAFFUN);
+
+ PRTREE("after parsing");
}
diff --git a/src/cmd/scc-cc/cc2/qbe/cgen.c b/src/cmd/scc-cc/cc2/qbe/cgen.c
@@ -136,39 +136,11 @@ static unsigned char i2f_conv[4][4][2] = {
* QBE is AMD64 targered we could do a better job there, and try to
* detect some of the complex addressing modes of these processors.
*/
-static Node *
-complex(Node *np)
-{
- Node *l = np->left, *r = np->right;
-
- if (np->address > 10)
- return np;
- if (l)
- np->complex = l->complex;
- if (r) {
- int d = np->complex - r->complex;
-
- if (d == 0)
- ++np->complex;
- else if (d < 0)
- np->complex = r->complex;
- }
- if (np->complex == 0)
- ++np->complex;
-
- return np;
-}
-
Node *
tsethi(Node *np)
{
Node *l, *r;
- if (!np)
- return np;
-
- np->complex = 0;
- np->address = 0;
l = np->left;
r = np->right;
@@ -189,14 +161,14 @@ tsethi(Node *np)
goto binary;
default:
binary:
- l = tsethi(l);
- r = tsethi(r);
+ l = sethi(l);
+ r = sethi(r);
break;
}
np->left = l;
np->right = r;
- return complex(np);
+ return np;
}
static int
@@ -483,48 +455,6 @@ function(void)
return NULL;
}
-Node *
-swtch(Node *swt)
-{
- Node aux1, aux2, *np, *idx;
- Symbol *deflabel = NULL;
-
- idx = rhs(swt->left);
- for (np = swt->next; ; np = np->next) {
- setlabel(np->label);
-
- switch (np->op) {
- case OESWITCH:
- if (!deflabel)
- deflabel = np->u.sym;
- aux1.op = OJMP;
- aux1.label = NULL;
- aux1.u.sym = deflabel;
- cgen(&aux1);
- delrange(swt->next, np);
- return NULL;
- case OCASE:
- aux1 = *np;
- aux1.op = OBRANCH;
- aux1.label = NULL;
- aux1.left = &aux2;
-
- aux2.op = OEQ;
- aux2.type = idx->type;
- aux2.left = np->left;
- aux2.right = idx;
-
- cgen(&aux1);
- break;
- case ODEFAULT:
- deflabel = np->u.sym;
- break;
- default:
- abort();
- }
- }
-}
-
static int
assignop(Type *tp)
{
@@ -600,7 +530,7 @@ assign(Node *np)
aux.left = ret;
aux.right = r;
aux.type = np->type;
- r = rhs(tsethi(&aux));
+ r = rhs(sethi(&aux));
break;
default:
/* assign abbreviation */
@@ -612,7 +542,7 @@ assign(Node *np)
aux.right = r;
aux.type = int32type;
aux.address = np->address;
- ret = r = tsethi(rhs(&aux));
+ ret = r = sethi(rhs(&aux));
break;
}
@@ -621,8 +551,14 @@ assign(Node *np)
aux.right = r;
aux.type = np->type;
aux.address = np->address;
- r = tsethi(&aux);
+ r = sethi(&aux);
case 0:
+ if (l->op == OTMP) {
+ r = rhs(r);
+ l->u.sym->numid = r->u.sym->numid;
+ return r;
+ }
+
lhs_rhs(&l, &r);
ret = r;
break;
@@ -777,9 +713,6 @@ cgen(Node *np)
p = (np->left) ? rhs(np->left) : NULL;
code(ASRET, NULL, p, NULL);
break;
- case OBSWITCH:
- swtch(np);
- break;
default:
rhs(np);
break;
@@ -826,9 +759,3 @@ genasm(void)
apply(norm);
apply(cgen);
}
-
-void
-genaddr(void)
-{
- apply(tsethi);
-}
diff --git a/src/cmd/scc-cc/cc2/qbe/stubs.c b/src/cmd/scc-cc/cc2/qbe/stubs.c
@@ -20,14 +20,3 @@ void
cleancfg(void)
{
}
-
-Swtch *
-newswitch(Swtch *swt)
-{
- return NULL;
-}
-
-void
-cleanswtch(void)
-{
-}
diff --git a/src/cmd/scc-cc/cc2/sethi.c b/src/cmd/scc-cc/cc2/sethi.c
@@ -0,0 +1,50 @@
+#include <scc/scc.h>
+
+#include "cc2.h"
+
+Node *
+sethi(Node *np)
+{
+ Node *l, *r;
+
+ if (!np)
+ return np;
+
+ np->complex = 0;
+ np->address = 0;
+
+ switch (np->op) {
+ case OBSWITCH:
+ np = swtch(np);
+ break;
+ default:
+ np = tsethi(np);
+ }
+
+ l = np->left;
+ r = np->right;
+
+ if (np->address > 10)
+ return np;
+ if (l)
+ np->complex = l->complex;
+ if (r) {
+ int d = np->complex - r->complex;
+
+ if (d == 0)
+ ++np->complex;
+ else if (d < 0)
+ np->complex = r->complex;
+ }
+ if (np->complex == 0)
+ ++np->complex;
+
+ return np;
+}
+
+void
+genaddr(void)
+{
+ apply(sethi);
+ PRTREE("after sethi");
+}
diff --git a/src/cmd/scc-cc/cc2/swtch.c b/src/cmd/scc-cc/cc2/swtch.c
@@ -8,79 +8,89 @@
static Swtch *list;
static Node *
-swtch_if(Node *idx)
+swtch_if(Node *np)
{
- Node *tmpvar, *next, *tmp, *np;
- Symbol *deflabel = NULL;
-
- tmpvar = tmpnode(&idx->type);
- idx->right = idx->left;
- idx->right = tmpvar;
- idx->op = OASSIG;
-
- for (np = idx->next; ; np = next) {
- next = np->next;
-
- switch (np->op) {
- case OESWITCH:
- if (!deflabel)
- deflabel = np->u.sym;
- np->op = OJMP;
- np->u.sym = deflabel;
- return sethi(idx);
- case OCASE:
- np->op = OBRANCH;
- tmp = node(OEQ);
- tmp->type = idx->type;
- tmp->left = np->left;
- tmp->right = tmpvar;
- np->left = tmp;
- break;
- case ODEFAULT:
- deflabel = np->u.sym;
- delstmt(np);
- break;
- default:
- abort();
- }
+ Type *tp;
+ Swtch *swt;
+ Node **cases, **bp, *tmpvar, *p;
+
+ swt = np->u.swtch;
+ tp = &np->left->type;
+
+ tmpvar = tmpnode(tp);
+ np->type = *tp;
+ np->right = np->left;
+ np->left = tmpvar;
+ np->op = OASSIG;
+ np->u.subop = 0;
+
+ cases = swt->cases;
+ for (bp = cases; bp < &cases[swt->nr]; ++bp) {
+ Node *eq, *tmp = node(OTMP);
+
+ p = *bp;
+ *tmp = *tmpvar;
+ eq = node(OEQ);
+ eq->type = *tp;
+ eq->left = p->left;
+ eq->right = tmp;
+ *bp = NULL;
+
+ p->left = eq;
+ p->op = OBRANCH;
+ addstmt(p);
}
+ p = swtchdefault(swt);
+ p->op = OJMP;
+ addstmt(p);
+
+ free(cases);
+ swt->cases = NULL;
+
+ return sethi(np);
}
static Node *
-swtch_dir(Node *np, int n, TINT min, TINT max)
+swtch_dir(Node *np, TINT min, TINT max)
{
- Node aux, *p, *defnode;
- Node **its, **zero, **ip;
+ int i;
+ TINT cur, nval;
+ Swtch *swt;
Symbol *tbl;
-
- its = xcalloc(n, sizeof(*its));
- zero = its;
- if (min < 0)
- zero -= min;
-
- for (p = np->next; p->op != OESWITCH; p = p->next) {
- if (p->op == ODEFAULT)
- defnode = p;
- else
- its[p->left->u.i] = p;
- p->type = ptrtype;
- p->op = OLABEL;
- }
-
- for (ip = its; ip < &its[n]; ++ip) {
- if (*ip == NULL)
- *ip = defnode;
- }
+ Node *p, *def, **cases;
tbl = getsym(TMPSYM);
tbl->kind = SLOCAL;
tbl->type = ptrtype;
tbl->type.flags |= INITF;
-
defglobal(tbl);
- for (ip = its; ip < &its[n]; ++ip)
- data(*ip);
+
+ swt = np->u.swtch;
+ cases = swt->cases;
+
+ def = swtchdefault(swt);
+ def->type = ptrtype;
+ def->op = OLABEL;
+
+ i = 0;
+ p = NULL;
+ for (cur = min; cur <= max; ++cur) {
+ if (!p && i < swt->nr) {
+ p = cases[i++];
+ p->type = ptrtype;
+ p->op = OLABEL;
+ nval = p->left->u.i;
+ }
+ if (p && nval == cur) {
+ data(p);
+ p = NULL;
+ } else {
+ data(def);
+ }
+ }
endinit();
+
+ return np;
}
Node *
@@ -96,16 +106,24 @@ swtch(Node *np)
range = max - min + 1;
n = swt->nr;
- if (n < 4)
+ if (n < 4 || noswtch)
return swtch_if(np);
- if (range == n)
- return swtch_dir(np, range, min, max);
+ return swtch_dir(np, min, max);
+}
- abort();
+Node *
+swtchdefault(Swtch *swt)
+{
+ Node *np;
+
+ np = swt->defnode;
+ if (!np)
+ np = swt->eswtch;
+ return np;
}
Swtch *
-newswitch(Swtch *swt)
+newswtch(Swtch *swt)
{
Swtch *p = xmalloc(sizeof(*p));
@@ -118,9 +136,16 @@ void
cleanswtch(void)
{
Swtch *p, *next;
+ Node **bp, **cases;
for (p = list; p; p = next) {
- next = p;
+ next = p->next;
+ cases = p->cases;
+ if (cases) {
+ for (bp = cases; bp < &cases[p->nr]; ++p)
+ deltree(*bp);
+ free(cases);
+ }
free(p);
}
}
