Enter your search terms Submit search form
	Web pdp-10.trailing-edge.com

/*	CCGSWI.C - Generate code for parse-tree switch statement
**
**	All changes after version 28 (8/8/85), unless otherwise specified, are
**	Copyright 1985, 1986 by Ken Harrenstien, SRI International.
*/
/*
** ccgswi - generate code for switch statements in KCC
** (C) 1981 K.Chen
**
** Several methods are used depending on the number and sparsity of cases.
** See the comment at casejump() for details.
*/

#include "cc.h"
#include "ccgen.h"

/* Exported functions */
void gswitch();

/* Imported functions */
extern VREG *genexpr();
extern void codlabel(), codgolab();	/* CCCODE */
extern SYMBOL *newlabel();		/* CCSYM */

/* Internal functions */
static void casejump();
static int countcases(), labcomp(), unique();


#define abs(x) ((x) >= 0? (x) : -(x))

struct lablist {		/* To hold labs for sorting */
    SYMBOL *label;		/* label itself */
    int caseval;		/* value to jump to label on */
};

/*
** Generate code for switch statement
*/
void
gswitch (n)
NODE *n;
{
    SYMBOL *saveb, *deflab;
    VREG *r;
    int i, ncase;
    struct lablist caselab[MAXCASE];
    struct lablist ltable[MAXCASE];	/* Table for casejump to use */

    saveb = brklabel;			/* save old break label */
    brklabel = (n->Nendlab != NULL)? n->Nendlab : newlabel(); /* get new one */

    r = genexpr (n->Nleft);		/* r selects case */
    deflab = NULL;			/* assume no default */
#if 0
    ncase = countcases(n->Nxswlist, caselab, &deflab, 0, 1);
#else
    ncase = countcases (n->Nright, caselab, &deflab, 0, 1);
#endif

    /* at this point, ready to create jump tables */
    casejump(r, caselab, ncase, ltable, ((deflab)? deflab : brklabel));
    release(r);				/* don't need register after this */
    if (n->Nright) {			/* if we have a body */
	n->Nright->Nendlab = brklabel;	/* remember where to exit to */
	genstmt(n->Nright);		/* make individual cases */
    }
    if (n->Nendlab == NULL) codlabel(brklabel); /* emit new break label */
    brklabel = saveb;			/* and restore old one */
}

#if 0
static int
countcases(n, caselab, deflab, ncase, ismain)
NODE *n;
struct lablist caselab[];
SYMBOL **deflab;
{
    int ncases = 0;
    SYMBOL **thelab;

    for (; n != NULL; n = n->Nright) {
      switch (n->Nop) {
	default:
	    error(EINTNOD, "Non-case node on switch list", n);
	    return -1;

	case Q_CASE:
	    if (ncases >= MAXCASE) {
		error(EINT,"More than %d case statements (%d)",MAXCASE,ncases);
		return -1;
	    }
	    thelab = &caselab[ncases].label;
	    caselab[ncases++].caseval = n->Nxfint;
	    break;

	case Q_DEFAULT:
	    thelab = deflab;
	    break;

      }		/* end of switch */
	/*
	** Here when it was a case label or default.
	**
	** Before making a label for this one, we look for further cases
	** in the statement it is part of so that if we see a break, continue,
	** goto, label, or other case that becomes a label as the statement
	** that this is a label to, we can re-use the same label.
	** Otherwise, we turn this one into a LABEL node so that it
	** can be generated properly.
	*/
	if (optgen) {
	    if (n->Nleft) switch (n->Nleft->Nop) {
	    case N_LABEL:
	    case Q_GOTO:
	    case Q_CASE:
/* PROBLEM: Nxfsym hasn't yet been set for succeeding case labels!
 * this optimization will have to be a separate recursive routine.
 */
		*thelab = (n->Nxfsym = n->Nleft->Nxfsym);
		n->Nop = n->Nleft->Nop;	/* copy node across */
		n->Nleft = n->Nleft->Nleft;	/* so as not to dup label */
		return ncase;
	    case Q_BREAK:
/* PROBLEM: don't have ismain, can't know whether this break is
* the right one or not.  Parser may have to add level numbering.
*/
		if (!ismain) break;		/* only if still top level */
		*thelab = brklabel;		/* use break label */
		n->Nop = Q_BREAK;		/* propagate back */
		return ncase;
	    case Q_CONTINUE:
/* Same ismain problem as for break above. */
		if (!ismain) break;		/* only if still top level */
		*thelab = looplabel;	/* use loop label */
		n->Nop = Q_CONTINUE;		/* propagate back */
		return ncase;
	    }				/* end switch(n->Nleft->Nop) */
	}				/* end if(optimize) */

	/* didn't find other label, just make a new one */
	n->Nop = Q_CASE;		/* remember either case or default */
	n->Nxfsym = (*thelab = newlabel()); /* make label value */

    }		/* end of loop */
    return ncases;
}
#else /* Old stuff */
/*
** Find case labels and defaults
**
** These should have been collected together by casestmt(),
** but for now we go find them all again.  Rewrite me.
*/

static countcases (n, caselab, deflab, ncase, ismain)
NODE *n;
struct lablist caselab[];
SYMBOL **deflab;
{
    int i, val, lab;
    SYMBOL **thelab;

    if (n == NULL) return ncase;

    while (1) {
	switch (n->Nop) {
	case N_STATEMENT:
	    for (; n != NULL; n = n->Nright)
		if (n->Nleft)
		    ncase = countcases(n->Nleft,caselab,deflab,ncase,ismain);
	    return ncase;
	case Q_IF:			/* yes, people really put cases */
	    n = n->Nright;		/* inside these things... */
	    ncase = countcases(n->Nright, caselab, deflab, ncase, ismain);
	case N_LABEL:
	    if ((n = n->Nleft) == NULL) return ncase; /* get body */
	    continue;

	case Q_DO:			/* these clear ismain */
	case Q_FOR:
	case Q_WHILE:
	    ismain = 0;			/* don't pass break up through here */
	    if ((n = n->Nleft) == NULL) return ncase; /* get body */
	    continue;			/* back up to try again */

	case Q_CASE:
	    val = n->Nxfint;
	    if (ncase >= MAXCASE) {
		fatal(EINT,"More than %d case statements (%d)",MAXCASE,ncase);
		return 0;
	    }
	    thelab = &caselab[ncase].label;
	    caselab[ncase++].caseval = val;
	    break;

	case Q_DEFAULT:
	    thelab = deflab;
	    break;

	default:
	    return ncase;
	}
	break;				/* DEFAULT or CASE, break from loop */
    }

    /*
    ** Here when it was a case label or default.
    **
    ** Before making a label for this one, we look for further cases
    ** in the statement it is part of so that if we see a break, continue,
    ** goto, label, or other case that becomes a label as the statement
    ** that this is a label to, we can re-use the same label.
    ** Otherwise, we turn this one into a LABEL node so that it
    ** can be generated properly.
    */

    ncase = countcases(n->Nleft, caselab, deflab, ncase, ismain);
    if (optgen) {
	if (n->Nleft == NULL) {
#if 0
	/* What the HELL was this for??  It's completely wrong and makes
	** broken code!! --KLH
	*/
	    if (ismain) {
		n->Nop = Q_BREAK;	/* turn final null stmt into break */
		*thelab = brklabel;	/* remember where it goes */
		return ncase;
	    }
#endif
	} else switch (n->Nleft->Nop) {
	case N_LABEL:
	case Q_GOTO:
	case Q_CASE:
	    *thelab = (n->Nxfsym = n->Nleft->Nxfsym);
	    n->Nop = n->Nleft->Nop;	/* copy node across */
	    n->Nleft = n->Nleft->Nleft;	/* so as not to dup label */
	    return ncase;
	case Q_BREAK:
	    if (!ismain) break;		/* only if still top level */
	    *thelab = brklabel;		/* use break label */
	    n->Nop = Q_BREAK;		/* propagate back */
	    return ncase;
	case Q_CONTINUE:
	    if (!ismain) break;		/* only if still top level */
	    *thelab = looplabel;	/* use loop label */
	    n->Nop = Q_CONTINUE;		/* propagate back */
	    return ncase;
	}				/* end switch(n->Nleft->Nop) */
    }					/* end if(optimize) */

    /* didn't find other label, just make a new one */
    n->Nop = Q_CASE;			/* remember either case or default */
    n->Nxfsym = (*thelab = newlabel()); /* make label value */
    return ncase;			/* say how many we got */
}
#endif

/*
** Generate code to jump to appropriate case label
**
** If there are less than three cases, we test for each of them successively
** using  P_CAIN R,val  followed by a  P_JRST  to the appropriate label, and all
** followed by a  P_JRST  to the default to the default or the end of the switch
** to catch the case when none of the three tests succeeds.
**
** If the number of cases is greater than half the difference between the
** greatest and least case value (i.e. the density of cases is >= 50%)
** or in any case if the range between greatest and least is less than 16,
** we do a range check by cascading two  P_CAILs  and jump either to the default
** or to a label from a table indexed by the value minus the least value, where
** the places with no corresponding case statement are filled by the default.
**
** The next method we try is a hash table.  We look at formulae of the form
** abs(val)%x  where x ranges between the number of cases and twice that.
** If we find an x which hashes all case values to different moduli, we
** perform our case jump by hashing the value and comparing the original value
** to the contents of a table indexed by the hash and containing the given
** case values at their hashes.  If it matches, we jump to a label from a
** parallel table, and otherwise to the default.  It doesn't matter what
** the values of non-case-value entries are in the first table, because their
** entries in the label table are the default.
**
** If none of these works, we have to split the cases.  We sort the cases,
** split the table into two, compare the value to the start of the second
** half, and go to recursively contructed code for the appropriate half.
**
** Because recursion could gobble so much stack space, we don't keep a
** temporary label array here anymore.  Instead it is allocated in gswitch()
** as "ltable" and pointed to by all calls to casejump.
*/

static void
casejump (reg, caselab, ncase, ltable, xlabel)
VREG *reg;
struct lablist caselab[];
struct lablist ltable[];
SYMBOL *xlabel;
{
/*    struct lablist ltable[MAXCASE]; */ /* No more, too wasteful */
    int min, max, range, i, j, r, hash, val, y;
    SYMBOL *halflab, *jtable, *vtable;

    backreg (reg);			/* skip back over failed change */
    r = realreg (reg);			/* get number for register */

    /*
    ** If we have three or less cases, the fastest way of seeing which one
    ** to use is merely "is it x?  is it y?  is it z?".  Zero cases is even
    ** easier.  We use reverse order in hopes of saving a label.
    */

    if (ncase <= 0) {			/* no cases? */
	code6(P_JRST, 0, xlabel);		/* odd.  but just use default. */
	return;				/* that's it for now. */
    }

    if (ncase <= 3) {			/* less than four cases? */
	for (i = ncase-1; i >= 0; i--) { /* yes, run back through them */
	    code8 (P_CAI+POF_ISSKIP+POS_SKPN, r, caselab[i].caseval); /* test value */
	    code6 (P_JRST, 0, caselab[i].label); /* and jump if found it */
	}
	code6 (P_JRST, 0, xlabel);	/* if not found, jump to default */
	return;
    }

    /*
    ** There are more than three cases.  Next we calculate the range of
    ** all the cases, so we can see if they are dense enough to use a
    ** simple jump table.
    */

    min = max = caselab[0].caseval;	/* get initial value for min and max */
    for (i = 1; i < ncase; i++) {	/* then look through rest of cases */
	val = caselab[i].caseval;	/* find value at that case */
	if (val < min) min = val;	/* and update min */
	else if (val > max) max = val;	/* and max with it */
    }
    range = max - min + 1;		/* range is difference of the two */

    if ((range < 16) || (range < ncase*3)) {	/* use offset table */

	/*
	** Generate test for range and jump into table.
	** The way we do the range check and jump is:
	**        P_CAIL   R,min
	**        P_CAIL   R,range+min
	**        P_JRST   xlabel
	**        P_JRST   @table-min(R)
	** Note that code6() must be smart enough not to fold the second
	** P_CAIL together with the P_JRST into a P_JUMPGE.
	**
	** Do not ever "optimize" the case of min == 0 into:
	**        P_CAIGE   R,range
	**        P_JUMPGE  R,@table(R)
	**        P_JRST    xlabel
	** (causes infinite loop in effective address calc when R contains -2).
	*/

	code8 (P_CAI+POF_ISSKIP+POS_SKPL, r, min);
	code8 (P_CAI+POF_ISSKIP+POS_SKPL, r, range+min);
	setskip (previous);		/* that was a skip */
	code6 (P_JRST, 0, xlabel);	/* so is this but set automatically */

	/*
	** Set up the actual labels in the jump table.  We also take a
	** little effort to detect the case that they are all the same
	** label (yes, I've seen it happen).
	*/

	/* bucket sort (linear!) the labels */
	for (i=0; i < range; i++) ltable[i].label = xlabel;
	for (i=0; i < ncase; i++)
	    ltable[caselab[i].caseval - min].label = caselab[i].label;

	/* look for case where they're all the same */
	jtable = ltable[0].label;	/* start with first label */
	for (i=1; i < range; i++) {	/* then run through rest of labels */
	    if (jtable == ltable[i].label) continue; /* see if same as prev */
	    jtable = NULL;		/* mismatch, remember no one label */
	    break;			/* don't bother to check the rest */
	}

	if (jtable == NULL) {		/* if not all the same */
	    jtable = newlabel();	/* make label for table */
	    code15 (P_JRST, jtable, -min, r); /* make indexed jump */
	    codgolab(jtable);		/* force emission of table label */
	    freelabel(jtable);		/* and forget it once used */
	    for (i=0; i < range; i++)	/* Emit table */
		code6(P_IFIW, 0, ltable[i].label);
	} else code6 (P_JRST, 0, jtable);	/* all same, just simple jump */
	return;
    }

    /*
    ** Here to try using a hash table.
    **
    ** We limit the range of hash searches to something reasonable.
    ** If there are too many cases, a hash that does not introduce
    ** clashes will probably not be found, in which case the number
    ** of cases is divided in two and each of them is done by
    ** recurring on this procedure.
    */

    range = (ncase <= 64) ? ncase+ncase : 128; /* get how many hashes to try */
    if (range < 16) range = 16;		/* make sure it's reasonable */

    for (hash=ncase; hash < range; hash++) {
	if (unique(hash, caselab, ncase, (int *)ltable)) {
	    /* generate code to compute hash value */
	    if (((hash-1)&hash) == 0) {	/* power of two? */
		reg = getreg();		/* yes, get a new register */
		code0 (P_MOVM, reg, r);	/* take absolute value */
		code1 (P_AND, reg, hash - 1); /* mod power of two is just and */
	    } else {
		reg = getpair();	/* get doubleword for div */
		code0 (P_MOVM, reg, r);	/* absolute value */
		code1 (P_IDIV, reg, hash); /* hash it up */
		narrow (reg, 1);	/* just keep remainder */
	    }

	    /* generate code to check hash and jump */
	    vtable = newlabel();	/* label for hash result compare */
	    jtable = newlabel();	/* and for jump table */
	    code16 (P_CAM+POF_ISSKIP+POS_SKPE, r, vtable, reg); /* what we expected? */
	    code6 (P_JRST, 0, xlabel);	/* no, must be the default case */
	    code15 (P_JRST, jtable, 0, reg); /* yes, go to jump table */
	    release (reg);		/* no longer need hash value */

	    /* calculate values for hash and jump tables */
	    for (i=0; i < hash; i++) {	/* initialize tables to false */
		ltable[i].caseval = -1;	/* value here is irrelevant */
   		ltable[i].label = xlabel; /* because always goes to default */
	    }
	    for (i=0; i < ncase; i++)	/* fill tables with vals and labels */
		ltable[abs (caselab[i].caseval % hash)] = caselab[i];

	    /* output hash and jump tables */
	    codgolab(vtable);
	    freelabel(vtable);
	    for (i=0; i < hash; i++)	/* Emit hash table */
		code17(ltable[i].caseval);
	    codgolab(jtable);
	    freelabel(jtable);
	    for (i=0; i < hash; i++)	/* Emit jump table */
		code6(P_IFIW, 0, ltable[i].label);
	    return;
	}
    }

    /*
    ** Cannot find unique hash, break cases into two.
    **
    ** Emit
    **    P_CAIL R,val
    **	  P_JRST lab
    **    (code for first half)
    ** lab::
    **	  (code for second half)
    **
    ** where val is the first value in the second half.
    ** 
    ** Sorting causes this to be O(n log n) rather than the linear time
    ** compilers are supposed to take.  Not checking that it's already
    ** sorted when called recursively adds another factor of log n.  Tough.
    */


    halflab = newlabel();
    range = ncase / 2;
    qsort ((char *) caselab, ncase, sizeof (struct lablist), labcomp);
    code8 (P_CAI+POF_ISSKIP+POS_SKPL, r, caselab[range].caseval);
    code6 (P_JRST, 0, halflab);
    casejump (r, caselab, range, ltable, xlabel);
    codlabel(halflab);
    casejump (r, caselab+range, ncase-range, ltable, xlabel);
}

/*
** Compare two lablist entries.
**
** This is a comparison routine to be passed to qsort() when
** casejump() wants to sort the list and split it in half.
**
** Because this is for qsort(), the arguments are (char *).
*/

static int
labcomp(l1, l2)
char *l1, *l2;
{
    return ((struct lablist *) l1)->caseval - ((struct lablist *) l2)->caseval;
}

/*
** Find out if hash produces unique cases
**
** We divide the absolute values of all the cases by the divisor
** we are testing, to make sure they all hash to different moduli.
** If so, we can use a hash table for the case jump.
*/

static int
unique (hash, caselab, ncase, temptab)
struct lablist caselab[];
register int *temptab;		/* Temp table of at least MAXCASE words */
{
    register int i, n;

    for (i=0; i < hash; i++) temptab[i] = 0;
    for (i=0; i < ncase; i++) {
	n = abs(caselab[i].caseval % hash);
	if (temptab[n]) return 0;
	temptab[n] = 1;
    }
    return 1;
}