cccreg.c

KCC , a good c compiler, write by Ken Harrenstien

/*	CCCREG.C -Peephole Optimizer functions for retroactively changing regs
**
**	(c) Copyright Ken Harrenstien 1989
**		All changes after v.63, 26-Apr-1988
**	(c) Copyright Ken Harrenstien, SRI International 1985, 1986
**		All changes after v.30, 8-Aug-1985
**
** Original version by David Eppstein / Stanford University / 2 July 1985
*/

#include "cc.h"
#include "ccgen.h"			/* get pseudo code defs */


/* Exported functions */
int changereg(int, int, PCODE *), ufcreg(int);
SYMBOL *cregupto(SYMBOL *);
int pushneg(int, PCODE *), pnegreg(int, PCODE *);
int rbincode(PCODE *), rbinreg(PCODE *), rbinaddr(PCODE *);
int rruse(PCODE *, int);	/* CCOPT */
int rrchg(PCODE *, int);	/* CCCODE */
int rinreg(PCODE *, int), rinaddr(PCODE *, int), rincode(PCODE *, int);

/* Imported functions */
extern PCODE *before(PCODE *), *after(PCODE *);	/* from CCCODE */
extern void dropinstr(PCODE *), unskip(PCODE *);
extern int dropsout(PCODE *);
extern int rfree (int);

/* Local functions */
static void rvsset(PCODE *);
static int  creg(int, int, PCODE *, PCODE *, PCODE *), 
	    cregbefore(int, int, PCODE *, PCODE *, PCODE *), 
	    cregok(PCODE *, int), craddhack(int, int, PCODE *), 
	    crossfence(int, int, PCODE *, PCODE *, PCODE *);
static int  rbinmem(PCODE *, int);
static SYMBOL *jumplab(PCODE *);
#if 0
static void rvsset();
static int creg(), cregbefore(), cregok(), craddhack(), crossfence();
static SYMBOL *jumplab();
static int rbinmem();
#endif

/* Data defs - see macros in ccreg.h and "rb" utilities herein */
int rbits[NREGS] = {		/* Single-register bits */
	regbit(0), regbit(1), regbit(2), regbit(3),
	regbit(4), regbit(5), regbit(6), regbit(7),
	regbit(8), regbit(9), regbit(10), regbit(11),
	regbit(12), regbit(13), regbit(14), regbit(15)
};

int drbits[NREGS] = {		/* Double-register bits */
	dregbit(0), dregbit(1), dregbit(2), dregbit(3),
	dregbit(4), dregbit(5), dregbit(6), dregbit(7),
	dregbit(8), dregbit(9), dregbit(10), dregbit(11),
	dregbit(12), dregbit(13), dregbit(14),
	regbit(15)|regbit(0)	/* Note last reg pair wraps around! */
};

/*
** Change register retroactively.
**
** changereg (to, from, p)
**    tries to change the code at and before p in the peephole buffer
**    so that the value that was previously calculated into register from
**    has now been calculated into register to.  The contents of from
**    are not defined after this operation.
**
**    The return value is 1 if the operation was a success, and 0 otherwise.
*/

int
changereg(to, from, p)
int to, from;
PCODE *p;
{
#if SYS_CSI		/*  Reg linkage */
    if (Register_Preserve (from))
	return 0;			/* avoid faulty optimizations */
#endif
    return creg(to, from, p, (PCODE *)NULL, previous);
}

/* CREGUPTO - routine used by gternary() in CCGEN2 for special
**	situation where trying to make "from" be the same as "to".
**	Beyond a certain point in the buffer, "to" already contains
**	the result value for a previous evaluation, and we can no
**	longer clobber it with something else.  This point is
**	identified by any jump-type instruction to the given label;
**	we cannot scan past this without special care.
**	We use uptolab as a "fence" indicator.
*/
static SYMBOL *uptolab = NULL;

SYMBOL *
cregupto(lab)
SYMBOL *lab;		/* Label identifying the jump we can't pass over */
{
    SYMBOL *tmp = uptolab;
    uptolab = lab;
    return tmp;
}

static SYMBOL *
jumplab(p)		/* Return label for jump instr, NULL if not jump */
PCODE *p;
{
    switch (p->Pop&POF_OPCODE) {
	case P_JRST:
	case P_JUMP:
	case P_AOJ:
	case P_SOJ:
	    return p->Pptr;		/* Return label jumped to */
	default:
	    ;	/* do nothing */
    }
    return NULL;
}

/* CROSSFENCE - called when jumplab() finds we're trying to cross fence.
**	Checks to see whether this is OK or not.  Currently only permits
**	a simple case; anything else is not understood and will fail.
**	Allows:
**		...
**		SKIPA To,X
**		 TRNA		; or any skip not referencing To or From
**		  JRST $upto
**		...
*/
static int
crossfence(to, from, p, dguard, dstart)
int to, from;
PCODE *p, *dguard, *dstart;
{
    if (p->Pop == P_JRST && prevskips(p)	/* A JRST, skipped over by */
      && (p = before(p)) != NULL
      && (p->Pop&POF_OPSKIP)==POS_SKPA		/* an unconditional skip */
      && prevskips(p)				/* that is itself skipped */
      && !(rbincode(p)&(rbits[to]|rbits[from]))	/* and doesn't ref our regs */
      && (p = before(p)) != NULL
      && p->Pop == P_SKIP+POF_ISSKIP+POS_SKPA	/* and prev is SKIPA to, */
      && p->Preg == to)
	return cregbefore(to, from, p, dguard, dstart);
    else return 0;
}

/*
** Fold negation into other ops
**
** pushneg (r, p)
**    attempts to negate the value previously calculated into r by the
**    instructions up to p.  No new instructions are added.
**    If the register is marked by the register allocator as in use,
**    we will not touch it, but no checks are made about the use
**    of the register in the instructions following p.
** pnegreg(r, p) - Same, but doesn't check for register in use.  This
**	is necessary in order for code0 to hack MOVN R,S where R == S.
*/

int
pushneg(int r, PCODE *p)
{
    if (!rfree(r)) return 0;		/* only mung finished regs */
    else return pnegreg(r, p);
}

int
pnegreg(int r, PCODE *p)
{
    while (p != NULL) {
	switch (p->Pop & (POF_OPCODE | POF_BOTH)) {
	case P_MOVN:
	case P_MOVE:
	    if (p->Preg != r) break;
	    if (prevskips (p) && !pushneg (r, before (p))) return 0;
	    p->Pop ^= (P_MOVE ^ P_MOVN);	/* turn P_MOVE into P_MOVN, vice versa */
	    return 1;

	case P_FDVR:	case P_FMPR:	case P_IMUL:
	    if (p->Preg != r) break;
	    if (!prevskips (p) && p->Ptype == PTA_REGIS &&
		pushneg (p->Pr2, before (p))) return 1;
	    break;			/* neg of either op works */

	case P_IDIV: case P_UIDIV:
	    if (p->Preg + 1 == r) r--;	/* negate dividend for remainder */
	    break;

	case P_ADD:	case P_SUB:
	    if (p->Preg != r) break;
	    if (!pushneg (r, before (p))) return 0;
	    p->Pop ^= (P_ADD ^ P_SUB);	/* swap P_ADD <=> P_SUB */
	    return 1;			/* return success */

	case P_SETZ:
	    if (p->Preg != r || prevskips (p)) break;
	    return 1;

	case P_SETO:
	    if (p->Preg != r) break;
	    if ((p->Ptype & PTF_ADRMODE) != PTA_ONEREG) return 0;
	    if (prevskips (p) && !pushneg (r, before (p))) return 0;
	    p->Pop = P_MOVE;
	    p->Ptype ^= (PTA_ONEREG ^ PTV_IMMED);
	    p->Pvalue = 1;
	    return 1;

	case P_JUMP:
	    if (p->Preg != r) break;
	    if (!pushneg (r, before (p))) return 0;
	    p->Pop = swapop (p->Pop);
	    return 1;

	case P_AOJ:   case P_SOJ:
	    if (p->Preg != r) break;
	    if (!pushneg (r, before (p))) return 0;
	    p->Pop ^= P_AOJ ^ P_SOJ ^ POSF_SWPSKIP;
	    return 1;

	case P_JRST:  case P_POPJ:
	    break;

	case P_CAI:
	    if (p->Preg != r) break;
	    if ((p->Ptype & PTF_ADRMODE) != PTA_RCONST || !pushneg (r, before (p)))
		return 0;
	    p->Pvalue = - p->Pvalue;	/* now neg, so negate comparand */
	    p->Pop = swapop (p->Pop);	/* and comparison */
	    return 1;

	case P_TRN:   case P_TDN:	case P_CAM:   case P_SKIP:
	case P_FLTR:  case P_FADR:	case P_FSBR:
	    if (p->Preg != r) break;
	default:
	    return 0;
	}
	if (p->Pindex == r) return 0;	/* can't back over index use */
	p = before (p);			/* back another op */
    }
    return 0;
}

/* UFCREG - Undo failed changereg when we don't care which register it is.
**
** We take as argument a register that might have been the destination
** reg of a call to changereg(), and look back for the P_MOVE R,S that
** would have been emitted if the register couldn't be changed.
** If we find it, we drop it and return S; otherwise we return R.
** Note that R and S are PDP-10 registers, not virtual registers.
*/

int
ufcreg(r)
int r;
{
    if (previous && previous->Ptype == PTA_REGIS /* && !prevskips */
      && previous->Pop == P_MOVE
      && previous->Preg == r
#if SYS_CSI		/*  Reg linkage */
      && Register_Nopreserve (r)
      && Register_Nopreserve (previous->Pr2) /* avoid faulty opts */
#endif
      && optobj) {
	r = previous->Pr2;	/* Remember the new reg */
	dropinstr(previous);	/* Flush now-useless move, fix "previous" */
    }
    return r;			/* Return the register to use */
}

/*
** Worker routine for changereg.
**
** This has the same calling conventions as changereg(), with the addition
** of two more arguments: dguard and dstart.  These are used to change
** registers for doubleword operations.
**
** It is mutually recursive with cregbefore().
*/

static int
creg(to, from, p, dguard, dstart)
PCODE *p, *dguard, *dstart;
{
    if (to == from) return 1;		/* already right */
    if (p == NULL) return 0;		/* nothing to change */
#if 1
    if (uptolab && uptolab == jumplab(p))	/* Moving past boundary? */
	return crossfence(to, from, p, dguard,dstart);	/* Yeah, stop. */
#endif
    if (dropsout(p)) {			/* in an alternate universe? */
	if (from == R_RETVAL)		/* want this register saved, lose */
		return 0;
	return cregbefore (to, from, p, dguard, dstart);
    }

#if 0		/*  Reg linkage */
    if (Register_Preserve (from))
	return 0;			/* avoid faulty optimizations */
#endif
    switch (rchange (p->Pop)) {		/* else classify op by reg changes */
    case PRC_RSET:
	if (p->Preg == to) return 0;	/* conflict, lose */
	if (p->Preg != from) return cregbefore (to, from, p, dguard, dstart);
	if (!prevskips (p) || cregok (after (p), from)) { /* make sure ok */
	    if (dguard != NULL) return 0; /* right reg num, wrong reg val */
	    if (p->Pop == P_MOVE && (p->Ptype &~ PTF_SKIPPED) == PTA_REGIS &&
		to == p->Pr2) {		/* old failed changereg? */
		p->Pop = P_NOP;		/* yes, drop it */
		if (p->Ptype & PTF_SKIPPED) unskip (before (p)); /* and prv skip */
	    } else p->Preg = to;	/* otherwise just make change */
	    return 1;			/* and return winnitude */
	}				/* otherwise treat as PRC_RCHG */
    case PRC_RCHG:
	if (p->Ptype == PTA_REGIS && p->Preg == from && p->Pr2 == to &&
	    dguard == NULL) switch (p->Pop) {
	case P_ADD: case P_IMUL: case P_IOR: case P_AND: case P_XOR:
	case P_FADR: case P_FMPR:

	    /*
	    ** code0, when it sees
	    ** 	    OP1 R,x
	    ** 	    OP2 R,S
	    ** for some commutative op2, turns it into
	    ** 	    OP1 R,x
	    ** 	    OP2 S,R
	    ** 	    P_MOVE R,S
	    ** in the hope that OP2 can fold into OP1.  We come here
	    ** when that has not happened and we are trying not to
	    ** emit the P_MOVE - if that is the case we simply switch
	    ** the two registers in OP2.
	    */

	    p->Preg = to;
	    p->Pr2 = from;
	    return 1;
	default:
	   ;  /* do nothing */
	}

    case PRC_RSAME:
    case PRC_RCHG_DSAME:
	if (p->Preg == to) return 0;	/* conflict, lose */
	if (p->Preg != from) return cregbefore (to, from, p, dguard, dstart);
	if (!cregbefore (to, from, p, dguard, dstart))
	    return dguard == NULL? craddhack (to, from, p) : 0;
	p->Preg = to;			/* changed up to here so change here */
	return 1;			/* and pass success back up */

    case PRC_DCHG_RSAME:		/* P_IDIV or similar instr */
#if 0
	This code loses for the case where an "IDIVI from,x" exists, and
to+1 (ie the new remainder-clobbered register) happens to be a register
that contains a value used farther on in the code buffer.  In this lossage
case, the register had been freed, but subexpression optimization had
found it still contained a useful value, and thus re-used that value.
Thus bug is demonstrated by the file BUGDIV.C.
Until this all gets figured out, simplest to avoid messing with IDIV
completely.  Sigh.  --KLH

	if (dguard == p) {		/* already been here once? */
	    if (p->Preg != from) to = to - 1; /* yes, change right reg */
	    if (!cregbefore (to, p->Preg, p, NULL, before (p))) return 0;
	    p->Preg = to;		/* done change before and here */
	    return 1;			/* so return success */
	}
	if (p->Preg == to || p->Preg == to - 1) return 0; /* blocked */
	if (dguard != NULL && (p->Preg == from || p->Preg == from - 1))
	    return 0;			/* can't deal with two at once */
	if (p->Preg == from) {		/* first half of double chg */
	    if (to >= R_MAXREG || !rfree (from + 1)) return 0; /* check safe */
	    return creg (to + 1, from + 1, dstart, p, NULL); /* recurse */
	}
	if (p->Preg == from - 1) {	/* same but with other reg */
	    if (to <= 1 || !rfree (from - 1)) return 0;	/* check safe */
	    return creg (to - 1, from - 1, dstart, p, NULL); /* recurse */
	}
	return cregbefore (to, from, p, dguard, dstart); /* normal, continue */
#endif

    case PRC_DSAME:			/* can't deal with doublewords */
    case PRC_DSET:			/* so if it uses any of our regs */
    case PRC_DSET_RSAME:		/* then we can't do anything. */
    case PRC_DCHG:			/* otherwise we can ignore the op. */
	if (p->Preg == to || p->Preg == to - 1 || /* blocked */
	    p->Preg == from || p->Preg == from - 1) return 0; /* or bad op */
	return cregbefore (to, from, p, dguard, dstart); /* normal, continue */

    default:
	int_error("creg: bad PRC_ val");
					/* Drop through */

    case PRC_UNKNOWN:			/* Unknown changes (PUSHJ) */
	return 0;			/* give it up */
    }
}

/*
** Make sure changereg is final for skipped over op
**
** Called by changereg() when we have some op that is PRC_RSET but
** which can be skipped over.  If the control flow leading to the
** following op is never going to escape to the end of the current
** peephole buffer contents, or if the following op also sets the
** same register (and thus will be changed by the instance of
** changereg() which called the one that is calling us) we are safe.
** KLH: We must also test to see whether the "following op" references
** the same register as a mem operand, because if so then its value
** depends on the instruction BEFORE the current one, and cregok() must
** fail in order to force creg() to keep looking back.
**
** Arguments are the op after the one that was skipped over, and
** the register to be changed from.
*/

static int
cregok (p, r)
PCODE *p;
{
    if (p == NULL) return 0;
    if (rchange (p->Pop) == PRC_RSET
	&& p->Preg == r
	&& !rinaddr(p, r)) return 1;
    return dropsout (p);
}

/*
** Change register retroactively before op.
**