ccjskp.c

KCC , a good c compiler, write by Ken Harrenstien

/*	CCJSKP.C - Peephole Optimizer - skips and jumps
**
**	(c) Copyright Ken Harrenstien 1989
**		All changes after v.101, 29-Jul-1988
**	(c) Copyright Ken Harrenstien, SRI International 1985, 1986
**		All changes after v.67, 8-Aug-1985
**
** Original version by David Eppstein / Stanford University / 12 Jun 85
*/

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

/* Imported functions */
extern PCODE *before(PCODE *), *after(PCODE *);
extern void reflabel(SYMBOL *, int), dropinstr(PCODE *);
extern int unsetz(PCODE *), oneinstr(PCODE *);
extern int rinaddr(PCODE *, int), rrchg(PCODE *, int), rinreg(PCODE *, int);
extern int sameaddr(PCODE *, PCODE *, INT);
extern int changereg(int, int, PCODE *), immedop(int);
extern void swappseudo(PCODE *, PCODE *);

/* Exported functions */
typedef SYMBOL *label;

void foldskip(PCODE *p, int safechange);	/* CCCODE */
void foldjump(PCODE *prev, label lab);	/* CCCODE */
int deadjump(void);		/* CCGEN1 */
int dropsout(PCODE *);		/* CCCREG, CCCSE, CCOPT */
void unskip(PCODE *);		/* CCCREG */
int unjump(label lab);		/* CCGEN2 */
void optlab(label lab);		/* CCCODE */
int foldtrna(PCODE *);		/* CCOUT */
void inskip(PCODE *);		/* CCCODE, CCOPT */

/* Internal functions */
static void dropjump(PCODE *), crossjump(PCODE *, SYMBOL *),
	    jumptoskip(PCODE *);
static int  invskip(PCODE *), newskip(PCODE *);
#if 0
static void dropjump(), crossjump(), jumptoskip();
static int invskip(), newskip();
#endif



/* DEADJUMP(p) - See if currently emitted code will be dead.
**
** There are three cases (yes the third one actually happens):
**  (1) The last op was an unskipped P_JRST, i.e. an unconditional jump
**  (2) The last op was an unskipped P_POPJ, i.e. an unconditional return
**  (3) The last op was an P_IFIW, i.e. we're in a switch jump table
*/

int
deadjump(void)
{
    if (previous) switch (previous->Pop) {
	case P_JRST:		/* jump, return, or jump table? */
	case P_POPJ:
	case P_IFIW:
	    return !prevskips(previous); /* yes, verify not skipped over */
    }
    return 0;				/* can't see or not jump, fail */
}

/* DROPSOUT(p) - See if operation can possibly affect following instructions
**
** It can't if it's a JRST, it's a POPJ, or its POF_OPSKIP field is POS_SKPA
** and it skips to an operation that can't affect the stream.
*/

int
dropsout(PCODE *p)
{
    if (p == NULL) return 0;
    if (p->Pop == P_JRST || p->Pop == P_POPJ) return 1;
    if ((p->Pop & POF_OPSKIP) != POS_SKPA) return 0;
    if ((p = after(p)) == NULL || (p = after(p)) == NULL) return 0;
    return dropsout(p);
}

/* DROPJUMP(p) - Remove a jump instruction
**
** Actually this removes any instruction, but it is necessary to use if
** the instruction might be a jump so the label's refcount can be maintained.
*/

static void
dropjump(p)
PCODE *p;
{
    if ((p->Ptype & PTF_ADRMODE) == PTA_MINDEXED)
	reflabel(p->Pptr, -1);
    dropinstr(p);	/* drop the instruction & fix up previous */
}

/* INVSKIP(p) - Invert an embedded skip
**
** Takes a skip instruction in the peephole buffer and makes the code there
** skip on the opposite condition.  No new code is emmited (unlike makeskip()).
** Checks to make sure skip can't be itself skipped over.
*/

static int
invskip(p)
PCODE *p;
{
    int r;
    PCODE *q, *b;

    if (p == NULL) return 0;		/* nothing to invert */

    if (!isskip(p->Pop)) return 0;

    if (p->Pop == P_CAI+POF_ISSKIP+POS_SKPLE
      && p->Ptype == PTA_RCONST+PTF_SKIPPED
      && (q = before(p)) != NULL
      && q->Ptype == PTA_RCONST
      && q->Preg == p->Preg
      && q->Pop == P_CAI+POF_ISSKIP+POS_SKPL
      && q->Pvalue == p->Pvalue - 1) {		/* Invert the sequence: */
	q->Pop = P_CAI+POF_ISSKIP+POS_SKPE;	/*    CAIL R,n / CAILE R,n+1 */
	p->Pop = P_CAI+POF_ISSKIP+POS_SKPN;	/* to CAIE R,n / CAIN R,n+1 */
	return 1;
    }

    r = revop(p->Pop);
    if (!(r & POF_OPSKIP)) {		/* was POS_SKPA, now no skip at all */
	r &=~ POF_ISSKIP;		/* so don't think of it as a skip */
	if (r == P_TRN) {		/* was TRNA, don't need to check */
	    dropinstr(p);		/* if skipped, just drop it entirely */
	    return 1;			/* that's all for now. */
	}
	if ((q = before (p)) != NULL && (q->Pop & POF_OPSKIP) == POS_SKPA) {
	    if (!invskip(before(q))) return 0; /* two unflippable POS_SKPAs */
	    swappseudo(p, q);		/* flipped before, now them */
	    return 1;			/* win win */
	}
    }

    if (!prevskips (p)) {
	p->Pop = r;			/* single skip, invert it */
	return 1;			/* return success */
    }

    /* look for three-word flip from double comparison */
    if ((p->Ptype & PTF_ADRMODE) != PTA_REGIS || !(p->Pop & POSF_CMPSKIP) ||
	(p->Pop & POF_OPCODE) != P_CAM || (q = before (p)) == NULL ||
	(b = before (q)) == NULL || b->Pop != (p->Pop ^ POSF_EQSKIP) ||
	(b->Ptype & PTF_ADRMODE) != PTA_REGIS || b->Preg != p->Preg ||
	b->Pr2 != p->Pr2) return 0;

    /* have a doubleword compare, invert the whole thing */
    q->Pop = revop(q->Pop);
    p->Pop = revop(b->Pop);
    b->Pop = r;
    return 1;
}

/* FOLDSKIP(p) - Turn P_CAIx R,0 into something better
**
** The safechange argument is zero if it might be part of a switch
** (in which case we can't safely change the value in the reg).
*/

void
foldskip(PCODE *p, int safechange)
{
    PCODE *q;

#if SYS_CSI		/*  Reg linkage */
    if (Register_Preserve (p->Pr2))
	return;			/* avoid faulty optimizations */
#endif

    if (p == NULL) return;

    /*
    ** fold:  P_MOVE S,x
    ** 	      P_ADD S,y
    ** 	      P_CAMN R,S
    **
    ** into:  P_SUB R,x
    ** 	      P_SUB R,y
    ** 	      P_CAIN R,0
    **
    ** (only for P_CAMN and P_CAME, to avoid wrap problems).
    */

    if ((p->Pop == P_CAM+POF_ISSKIP+POS_SKPE
      || p->Pop == P_CAM+POF_ISSKIP+POS_SKPN) &&
	p->Ptype == PTA_REGIS)
    for (q = before (p); q != NULL; q = before (q)) {
	if (prevskips (q) || q->Preg != p->Pr2) break;
	switch (q->Pop) {
	case P_ADD: case P_SUB:
	    q->Preg = p->Preg;		/* swap adds across to other reg */
	    q->Pop ^= (P_ADD ^ P_SUB);	/* making them subtracts instead */
	    continue;

	case P_MOVE: case P_MOVN:
	    q->Preg = p->Preg;		/* same for P_MOVE and P_MOVN */
	    q->Pop = (q->Pop == P_MOVE? P_SUB : P_ADD); /* turned into P_SUB and P_ADD */
	    p->Pop ^= (P_CAM ^ P_CAI);	/* make immediate comparison */
	    p->Ptype = PTA_RCONST;		/* against number */
	    p->Pvalue = 0;		/* number is zero */
	}
	break;				/* escape loop if not explicit cont */
    }

    if ((p->Pop & POF_OPCODE) != P_CAI) return; /* must be P_CAIx */
    q = before(p);			/* look before it */

    if (q != NULL && q->Ptype == PTA_REGIS /* !prevskips */
#if SYS_CSI		/*  Reg linkage */
     && (Register_Nopreserve (q->Pr2))/* avoid faulty optimizations */
#endif
     && q->Preg == p->Preg && q->Pop == P_MOVE && safechange) {

	/*
	** fold:  P_MOVE  R,S
	**        P_CAIx  R,c
	**
	** into:  P_CAIx  S,c
	*/

	p->Preg = (char) (q->Pr2);		/* flatten tested register */ // FW KCC-NT
	q->Pop = P_NOP;			/* flush useless move */
	q = before(q);			/* try for more optimizations */
    }

    if (q->Preg == p->Preg && q->Ptype == PTV_IMMED && safechange)
	switch(q->Pop) {
	    case P_SUB:
		if (!unsetz (q)) break;
	    case P_ADD:

		/*
		** fold:  P_ADDI  R,n
		**        P_CAIx  R,m
		**
		** into:  P_CAIx  R,m-n
		*/

		p->Pvalue -= q->Pvalue;
		q->Pop = P_NOP;			/* flush folded addition */
		q = before(q);			/* look for more before it */
	}

    /*
    ** fold:  P_CAIGE R,1
    ** into:  P_CAIG  R,0
    */

    if ((p->Ptype & PTF_ADRMODE) != PTA_RCONST) return;	/* rest of opts need numbers */

    switch (p->Pop & POF_OPSKIP) {
    case POS_SKPG:    case POS_SKPLE:		/* skip that can be adjusted up? */
	if (p->Pvalue == -1 || p->Pvalue == -2) { /* worthwhile to do it? */
	    p->Pvalue++;		/* yes, increment value */
	    p->Pop ^= POSF_EQSKIP;		/* and adjust skip to match */
	}
	break;

    case POS_SKPL:    case POS_SKPGE:		/* skip that can be adjusted down? */
	if (p->Pvalue == 1 || p->Pvalue == 2) {	/* worthwhile to do it? */
	    p->Pvalue--;		/* yes, decrement value */
	    p->Pop ^= POSF_EQSKIP;		/* and adjust skip to match */
	}
	break;
    }

    /*
    ** Fold remaining comparisons against one into P_AOSx which will
    ** later become P_AOJx.  We make P_AOS R,R rather than P_AOS R so we
    ** don't confuse the rest of code generation too badly.
    ** 
    ** All optimizations after this one can safely assume that the
    ** value being compared against is zero.
    */

    switch ((int) p->Pvalue) {
    case 1:
	if (!safechange) return;	/* not for switch you don't */
	p->Pop ^= (P_CAI ^ P_SOS);		/* make P_SOSx */
	p->Ptype ^= (PTA_RCONST ^ PTA_REGIS);	/* from and to register */
	p->Pr2 = p->Preg;		/* same register */
	return;				/* that's all */

    case -1:
	if (!safechange) return;	/* not for switch you don't */
	p->Pop ^= (P_CAI ^ P_AOS);		/* make P_AOSx */
	p->Ptype ^= (PTA_RCONST ^ PTA_REGIS);	/* from and to register */
	p->Pr2 = p->Preg;		/* same register */
	return;				/* that's all */

    case 0: break;			/* zero is ok to continue with */
    default: return;			/* anything else we can't handle */
    }

    /*
    ** The remaining optimizations fold a test against zero with
    ** the previous instruction.
    */

    if (q->Preg != p->Preg) {
	if ((q->Pop == P_IDIV || q->Pop == P_UIDIV)
		&& q->Preg + 1 == p->Preg
		&& safechange
		&& q->Ptype == PTV_IMMED /* !prvsk */
		&& ((q->Pvalue-1)&q->Pvalue) == 0) {

	    /*
	    ** fold:  P_IDIVI R-1,2^n
	    **        P_CAIx  R,0
	    **
	    ** into:  P_TRNx  R,2^n-1
	    */

	    switch (p->Pop & POF_OPSKIP) {
	    case POS_SKPE:
	    case POS_SKPN:
		p->Pop ^= (P_CAI ^ P_TRN);
		p->Preg = q->Preg;
		p->Ptype = PTA_RCONST;
		p->Pvalue = q->Pvalue - 1;
		q->Pop = P_NOP;
		q = before(q);		/* now look at before the P_IDIVI */
		if (q->Ptype == PTA_REGIS /* !prevskips */ && q->Pop == P_MOVE &&
		    q->Preg == p->Preg) {
		    p->Preg = (char) (q->Pr2);	// FW KCC-NT
		    q->Pop = P_NOP;	/* flatten failed changereg() */
		}
	    }
	}
	return;
    }

    if (prevskips (q)) return;
    switch (q->Pop) {
    case P_AND:
	if (!safechange) return;
	switch (p->Pop & POF_OPSKIP) {
	case POS_SKPE:
	case POS_SKPN:

	    /*
	    ** fold:  P_AND  R,mask
	    **	      P_CAIE R,0
	    **
	    ** into:  P_TDNE R,mask
	    */

	    if (q->Ptype == PTV_IMMED) {
		q->Ptype = PTA_RCONST;
		q->Pop = p->Pop ^ (P_CAI ^ P_TRN);
	    } else q->Pop = p->Pop ^ (P_CAI ^ P_TDN);
	    break;

	default: return;
	}
	break;

    case P_MOVE:
	/*
	** fold:  P_MOVE  R,addr
	**        P_CAIx  R,0
	**
	** into:  P_SKIPx R,addr
	*/
	q->Pop = p->Pop ^ (P_CAI ^ P_SKIP);
	break;

    case P_ADD:
	if (q->Ptype != PTV_IMMED || !safechange) return;
	if (p->Pop != P_CAI+POF_ISSKIP+POS_SKPE && p->Pop != P_CAI+POF_ISSKIP+POS_SKPN) return;
	/* Now that we know we'll do the optimization, safe to clobber instr */
	q->Pvalue = - q->Pvalue;