ccgswi.c

KCC , a good c compiler, write by Ken Harrenstien

}
#endif

/*
** Generate code to jump to appropriate case label
**
** If there are less than five cases, we test for each of them successively
** using CAIN R,val followed by a  JRST  to the appropriate label, and all
** followed by a 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 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(VREG *r, struct lablist *caselab, INT ncase, 
	struct lablist *ltable, SYMBOL *xlabel)
{
/*    struct lablist ltable[MAXCASE]; */ /* No more, too wasteful */
    INT min, max, range, val;
    int i, hash;
    SYMBOL *halflab, *jtable, *vtable;

    vrufcreg(r);	/* Flush pointless MOVE R,S changereg if any */
			/* This also ensures register is active! */

    /*
    ** If we have five 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, (VREG *)NULL, xlabel);	/* odd.  but just use default. */
	return;				/* that's it for now. */
    }

    /* 8/91, dump CAIN code for ncase 4 or 5 (was only 3) */
    if (ncase <= 5) {			/* less than six 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 */
	    code6(P_JRST, (VREG *)NULL, caselab[i].label); /* and jump if found value */
	}
	code6(P_JRST, (VREG *)NULL, xlabel);	/* if not found, jump to default */
	return;
    }

    /*
    ** There are more than five 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:
	**	CAIL   R,min
	**	CAIL   R,range+min
	**	JRST   xlabel
	**	JRST   @table-min(R)
	** Note that code6() must be smart enough not to fold the second
	** CAIL together with the JRST into a JUMPGE.
	**
	** Do not ever "optimize" the case of min == 0 into:
	**	CAIGE   R,range
	**	JUMPGE  R,@table(R)
	**	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);
	code6(P_JRST, (VREG *)NULL, xlabel);

	/*
	** 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, (VREG *)NULL, ltable[i].label);
	} else code6(P_JRST, (VREG *)NULL, 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.
	    ** We must use code00 instead of code0 to avoid the premature
	    ** release of r that would otherwise happen; that reg is only
	    ** freed by the caller of casejump.
	    */
	    VREG *r2;
	    if (((hash-1)&hash) == 0) {		/* Power of two? */
		r2 = vrget();			/* Yes, get a new register */
		(void) vrstoreal(r, r2);	/* Ensure both regs active */
		code00(P_MOVM, vrreal(r2), vrreal(r));	/* take abs value */
		code1(P_AND, r2, hash-1); /* % power-of-2 is just AND */
	    } else {
		r2 = vrdget();			/* Get doubleword for div */
		(void) vrstoreal(r, r2);	/* Ensure both regs active */
		code00(P_MOVM, vrreal(r2), vrreal(r));	/* abs value */
		code1(P_IDIV, r2, hash);	/* hash it up */
		vrnarrow(r2 = VR2(r2));		/* just keep rem in 2nd wd */
	    }

	    /* 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, r2); /* what we expected? */
	    code6(P_JRST, (VREG *)NULL, xlabel);	/* no, must be the default case */
	    code15(P_JRST, jtable, 0, r2); /* yes, go to jump table */
	    vrfree(r2);			/* 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, (VREG *)NULL, ltable[i].label);
	    return;
	}
    }

    /*
    ** Cannot find unique hash, break cases into two.
    **
    ** Emit
    **		CAIL R,val
    **		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, (VREG *)NULL, 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)
const void *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 (int hash, struct lablist caselab[], int ncase, 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;
}