/*	CCGSWI.C - Generate code for parse-tree switch statement
**
**	(c) Copyright Ken Harrenstien 1989
**		All changes after v.52, 8-Apr-1988
**	(c) Copyright Ken Harrenstien, SRI International 1985, 1986
**		All changes after v.28, 8-Aug-1985
**
**	Original version (C) 1981  K. Chen
*/

#include "cc.h"
#include "ccgen.h"
#include <stdlib.h>	/* qsort */

/* Exported functions */
void gswitch(NODE *n);

/* Imported functions */
extern VREG *genexpr(NODE *);
extern void codlabel(SYMBOL *), codgolab(SYMBOL *);	/* CCCODE */
extern SYMBOL *newlabel(void);		/* CCSYM */
extern void genstmt(NODE *);			/* CCGEN1 */
extern void code00(int, int, int), code1(int, VREG *, INT), 
	code6(int, VREG *, SYMBOL *), code8(int, VREG *, INT), 
	code15(int, SYMBOL *, INT, VREG *), 
	code16(int, VREG *, SYMBOL *, VREG *), code17(INT);
extern void freelabel(SYMBOL *);
extern VREG *vrdget(void);
extern void vrfree (VREG *);
extern VREG *vrget(void);
extern void vrnarrow (VREG *);
extern int vrreal (VREG *);
extern int vrstoreal (VREG *, VREG *);
extern void vrufcreg(VREG *);

/* Internal functions */
struct lablist {		/* To hold labs for sorting */
    SYMBOL *label;		/* label itself */
    int caseval;		/* value to jump to label on */
};
static void casejump(VREG *a, struct lablist *b, INT c, struct lablist *d, 
	SYMBOL *e);
static INT countcases(NODE *a, struct lablist b[], SYMBOL **c, int d, int e);
static int labcomp(const void *, const void *),
	   unique(int a, struct lablist b[], int c, INT *d);

/*
** Generate code for switch statement
*/
void
gswitch (NODE *n)
{
    SYMBOL *saveb, *deflab;
    VREG *r;
    INT 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));
    vrfree(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:		/* Non-case node on switch list?? */
	    int_error("countcases: non-case %N", n);
	    return -1;

	case Q_CASE:
	    if (ncases >= MAXCASE) {
		int_error("countcases: %ld cases", (INT) 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 INT
countcases (n, caselab, deflab, ncase, ismain)
NODE *n;
struct lablist caselab[];
SYMBOL **deflab;
{
    INT val;
    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) {
		int_error("countcases: %d cases", 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;
	default:
	    ;	/* do nothing */
	}				/* 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 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;
}