cccse.c

KCC , a good c compiler, write by Ken Harrenstien

/*	CCCSE.C - Peephole Optimizer - fold common subexpressions
**
**	(c) Copyright Ken Harrenstien 1989
**		All changes after v.136, 31-Mar-1988
**	(c) Copyright Ken Harrenstien, SRI International 1985, 1986
**		All changes after v.97, 8-Aug-1985
**
** Original version by David Eppstein / Stanford University / 30-Jul-84
*/

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

/* Exported functions */
void foldmove(PCODE *p), foldidx(PCODE *p), folddiv(VREG *vr);
int foldrcse(int r, PCODE *p);
int sameaddr(PCODE *p, PCODE *q, INT stkoffset), 
    alias(PCODE *p, PCODE *q, INT soff);	/* for CCOPT */

/* Imported functions */
extern PCODE *before(PCODE *), *after(PCODE *);
extern void code00(int, int, int), fixprev(void);
extern int dropsout(PCODE *);
extern int rfree (int);
extern int vrreal (VREG *);

/* Internal functions */
static int findcse(int, PCODE *, int);
static void flushreg(int), flushtarget(int);
static int chgpush(PCODE *), stktop(PCODE *), 
	   safematch(PCODE *, int), match(PCODE *, int);
static int flushalias(PCODE *);
static int cseinit(int, PCODE *, int);
#if 0
static int findcse();
static void flushreg(), flushtarget();
static int chgpush(), stktop(), safematch(), match();
static int flushalias();
static int cseinit();
#endif

#define	MAXCSE	10			/* how many ops we will look at */

static PCODE *target[MAXCSE];		/* target op pointers for subexpr */
static INT
    stkoffset;		/* offset in stk from target */

static int
    maxcse,		/* how many ops in subexpr (# ptrs in target[]) */
    maxflush,		/* how far to flush ops */
    jumped,		/* Flag: found a jump, can't fold P_ILDB */
    ismod[MAXCSE],	/* P_IDIV used as mod rather than div */
    regret[NREGS],	/* What reg to return if we match */
    matchedto[NREGS],	/* Register match machines
			** Contains index into target[].  -1 if none.
			*/
    isindex[NREGS];	/* Contains index into target[].  -1 if reg never
			** used as an index reg, else "earliest each
			** reg is used as index".
			*/
    /*
    ** Isindex contains the earliest each register is used
    ** as an index.  If an opcode changes that register
    ** we must flush matches for all registers not that far.
    **
    ** Maxflush contains the latest use of the register we are
    ** matching in another op.  It controls how far back we can
    ** go in dropping the opcodes making the redundant expression.
    **
    ** Jumped is true if we have stepped back over some conditional
    ** jump instruction.  If this is the case then we can't fold
    ** P_IBP + P_LDB into P_ILDB.
    */
#if 0
	/* Overview of how findcse works (from David Eppstein) */
      - In the first loop it goes back through the peephole buffer and
	builds up a list of instructions that taken together calculate
	the value in the target register (the one given it as an
	argument).  In this case the list will just be the LDB.

      - For each other register that can hold a computed value, in
	parallel and with the state of each parallel computation held
	in what is called in the comments a register match machine,
	it goes back through the peephole buffer and sees if the
	instructions which calculate the value in that other register
	match the built up list of instructions.  This is the big loop.

      - If we ever get such a match, then the built up list of
	instructions for the target register value is not necessary,
	because we can instead copy the value in the matching register
	and it will be the same.  This is the common subexpr elimination.
	The redundant instructions will be removed from the buffer and
	the register containing the result will be the return value.
	The caller might emit a MOVE or might just use that register.

      - If all machines don't match, i.e. they find an instruction
	which is part of how the value in their result registers was
	calculated but which isn't part of how the target value was
	calculated, then we know that the target value is not a common
	subexpression so we have to keep its calculation (and return
	zero to show that we are still using the old register).

      - If we get to the beginning of the peephole buffer without any
	machine matching then again there is no common subexpression.

Building the target calculation instruction list (the first loop) should
be pretty straightforward.  The second and longer loop is where the
match machines go about their work.  Actually what happens is that we
look at each instruction and there will usually be only one register
changed, so only one match machine needs to be activated.  If the
instruction changing the register is the same as the one the machine
expects then the machine advances to the next instruction in the list;
if it doesn't match the machine aborts.  Most of the state of each
machine can be found in matchedto[], which says which instruction it
wants to see next or whether it's aborted.

One complication is that we have to tell whether a register used as an
index was not changed between the machine's calculation's use of it
and the target calculation's use.  This information is kept in isindex[].
Isindex[reg] is the pointer to the earliest use of that register in
the target calculation; if any machines are not yet that far back when
we see an instruction changing that reg then all those machines are aborted.
There is a possible bug here if the same register is used twice as an
index in the target calculation, with a change to it in between the
two uses; if this situation happens the first loop that builds the
target calculation instruction list should abort because the second
loop can't handle this, but I don't know whether it currently does.
Something that probably hasn't come up but might be made to with
sufficiently tricky code.  You should check this anyway (not that it
is related to your current bug).

Another complication is that, because of IDIVI, the register that a
machine wakes up on is not always the same as the one it uses as the
common subexpression value after a successful match.  There is another
array that keeps track of this information (I forget the name).

Yet another complication is to take care of instructions that can be
skipped over.  There is a SKIPPED field in the address mode type of
each instruction which the code should be looking at (I am pretty sure
it does but it's been a while).

The minor function of findcse was that it turned out to be convenient
to put ILDB folding there.  LDB folding only happens when there is a
single LDB (or DPB) as the target calculation.  If we find a matching
LDB first, this is just a common subexpression like any other.  But if
we find an IBP, then we want to turn both instructions into an ILDB.
Currently there is one thing which inhibits this, the jumped flag.  If
we move back across a jump out of the peephole buffer, this is not a
problem for common subexpressions but you don't want to pull the IBP
across the jump because then it won't happen if the jump gets taken.

#endif

/*
** Fold common subs into changereg
** Can't handle P_IDIV because looks at op to determine reg
*/

void
foldmove(p)
PCODE *p;
{
    int r = p->Preg, s, op = p->Pop;
    if (p->Pop == P_IDIV || p->Pop == P_UIDIV) return;
    if ((s = findcse(r, p, 0)) != 0)
    {   if (op == P_HRRZ  ||  op == P_HLRZ)
	    code00(P_HRRZ, r, s);
        else
	    code00(P_MOVE, r, s);
    }
}

/*
** Ditto for P_IDIV, needs register argument to tell what to fold.
** We take the register as a vreg for caller's convenience, but it must
** be an active register.
*/

void
folddiv(vr)
VREG *vr;
{
    int r = vrreal(vr), s;
    if ((s = findcse(r, previous, 0)) != 0)
	code00(P_MOVE, r, s);
}

#if 0
/*
** Return result of folding out common sub
** Used for folding cse's out of index registers
*/

int
foldcse(r, p)
int r;
PCODE *p;
{
    int s;

    if (s = findcse(r, p, 1))	/* look for match */
	return s;		/* success, return folded reg */
    return r;			/* failure, return old one */
}
#endif

/* FOLDIDX - Assumes given instruction uses an index reg.
**	Attempts to find a CSE reg with the same value, and if so
**	flushes the index reg calculation and changes the index reference
**	to use the existing reg.
**	Doesn't pay attention to whether phys regs are still assigned to
**	virtual regs (assumes that index reg, once used, isn't needed again).
*/
void
foldidx(p)
PCODE *p;
{
    int s;

#if SYS_CSI			/* Reg linkage */
    if (Register_Nopreserve(p->Pindex))	/* avoid faulty opts */
#endif
        if ((s = findcse(p->Pindex, before(p), 1)) != 0) /* Look for match to index */
	    p->Pindex = s;		/* Won, set new index reg */
}

/* FOLDRCSE - Folds a CSE paying no attention to whether phys regs are
**	still assigned to virtual regs or not.
**	Returns phys register # containing value, or 0 if no folding done.
*/
int
foldrcse(r, p)
PCODE *p;
{
    return findcse(r, p, 1);
}

/* CSEINIT - auxiliary for FINDCSE to set things up
*/
static int
cseinit(r, p, safedouble)
PCODE *p;
{
    PCODE *q;
    int i;

    /*
    ** Do some preliminary initialization of variables.
    **
    */

    for (i = 0; i < NREGS; i++) isindex[i] = -1;
    maxflush = -1;			/* can't flush anything yet */
    jumped = 0;				/* haven't stepped over a jump */

    /*
    ** We search through the peephole buffer twice; once
    ** to discover the expression we want to match, and
    ** once to match it.  We do the former now.
    */

    maxcse = 0;				/* start at top of cse list */
    q = p;				/* and top of code */
    while (1) {				/* until we break out */
	if (q == NULL) return 0;	/* if had to stop, give up */

	/*
	** Look at the opcode of each instruction as we go back,
	** to make sure it is one we understand.  If the register
	** is the one we are folding, remember the op and if it
	** determined completely the register, stop there.
	**
	** We also stop for P_DPB, so we can fold P_IBP+P_DPB into P_IDPB.
	** (NO LONGER DONE -- DPB is a mem change! -- KLH)
	*/

	switch (q->Pop) {
	case P_FADR:	case P_FSBR:	case P_FMPR:	case P_FDVR:
	case P_ADD:	case P_IMUL:	case P_SUB:	case P_AND:
	case P_IOR:	case P_XOR:	case P_ADJBP:	case P_LSH:
	case P_IDIV:	case P_UIDIV:
	    i = 0;			/* not final */
	    break;			/* go handle */

	case P_MOVE:	case P_LDB:
	case P_MOVN:	case P_SETCM:	case P_SETO:	case P_SETZ:
	case P_HRRZ:	case P_HLRZ:	case P_HRRE:	case P_HLRE:
	case P_FIX:	case P_FLTR:
	    i = 1;			/* this will be the last */
	    break;			/* go handle */

	default:
	    return 0;			/* unknown op, give up */
	}

	/*
	** If we got this far we approve of the opcode.  Variable
	** i contains 1 if this will be the last op to examine.
	** It must be maintained for many lines until used.
	** We take this opportunity to set maxflush.
	*/

	if ((q->Pop & POF_BOTH)		/* don't go past mem change */
	  || (popflg[q->Pop&POF_OPCODE]&PF_MEMCHG))
		return 0;

	if ((q->Pop == P_IDIV || q->Pop == P_UIDIV) && q->Preg == r - 1) {
	    r--;			/* division used for modulus */
	    ismod[maxcse] = 1;		/* change target reg and remember so */
	} else ismod[maxcse] = 0;	/* otherwise don't remember as mod */

	if (maxflush < 0 && q->Preg != r) switch (q->Ptype & PTF_ADRMODE) {
	case PTA_BYTEPOINT:
	case PTA_MINDEXED:
	    if (q->Pindex == r) maxflush = maxcse;
	    break;
	case PTA_REGIS:
	    if (q->Pr2 == r) maxflush = maxcse;
	default:
	    ;	/* do nothing */
	}

	/*
	** If the register of the opcode is not what we are looking for,
	** the op is irrelevant and we can now safely ignore it.
	*/

	if (q->Preg != r) {		/* irrelevant op? */
	    q = before (q);		/* yes, skip over */
	    continue;			/* and try for more */
	}

	/*
	** Now we must make sure the pseudo-op type is acceptible.
	** For instance, we can not accept PTA_REGIS operations.
	** We also take this opportunity to note index registers needed.
	**
	** Note we don't mask out PTF_SKIPPED or POF_BOTH before switching.
	*/

	switch (q->Ptype) {
	case PTA_REGIS: