ccopt.c

KCC , a good c compiler, write by Ken Harrenstien

/*	CCOPT.C - Peephole Optimizer - miscellaneous optimizations
**
**	(c) Copyright Ken Harrenstien 1989
**		All changes after v.328, 3-Feb-1989
**	(c) Copyright Ken Harrenstien, SRI International 1985, 1986
**		All changes after v.218, 8-Aug-1985
**
**	Original version (C) 1981  K. Chen
*/
/*
** This collects the peephole optimizations that have not been
** classified into other files, and which are not still integrated
** with generation of code into the peephole buffer (in cccode) or
** emission of it from there into the assembly language output file
** (in ccout).
**
** Other modules containing peephole optimization routines include:
**    cccreg - propagation of P_MOVE R,S back through peephole buffer
**    cccse  - finding registers already containing calculated value
**    ccjskp - rearrangement of jump and skip instructions
*/

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

/* Imported functions */
extern int adjboffset(INT, INT *, int);			/* from CCOUT */
extern PCODE *before(PCODE *), *after(PCODE *);		/* CCCODE */
extern void fixprev(void);				/* CCCODE */
extern void dropinstr(PCODE *);
extern void code00(int, int, int), codr1(int, int, INT),
	codebp(int, int, INT, int, SYMBOL *, INT),
	codr10(int, int, SYMBOL *, INT, INT);
extern PCODE *chkmref(PCODE *, PCODE *, INT *);		/* CCCODE */
extern int rincode(PCODE *, int), rinreg(PCODE *, int),
	rinaddr(PCODE *, int),	rrchg(PCODE *, int);	/* CCCREG */
extern int sameaddr(PCODE *, PCODE *, INT), alias(PCODE *, PCODE *, INT);
extern void foldidx(PCODE *), swappseudo(PCODE *, PCODE *);
extern int  foldrcse(int, PCODE *);
extern void foldmove(PCODE *), inskip(PCODE *);
extern int dropsout(PCODE *), immedop(int), pushneg(int, PCODE *);
extern int rruse(PCODE *, int), rfree (int);
extern int rbinreg (PCODE *), rbinaddr (PCODE *), rbincode (PCODE *); /* CCCREG */

/* Exported functions */
PCODE *findrset(PCODE *, int);	/* CCCODE (4 usage), CCOPT (5) */
int localbyte(PCODE *, PCODE *);/* CCCODE (1) */
void foldbp(PCODE *);		/* CCCODE (1) */
void foldbyte(PCODE *);		/* CCCODE (2) */
int findconst(PCODE *);		/* CCCODE (3) */
void foldplus(PCODE *);		/* CCCODE (5), CCOPT (11) */
void foldadjbp(PCODE *);	/* CCCODE (2) */
void foldboth(void);		/* CCCODE (2) */
INT foldstack(INT);		/* CCCODE (1) */
INT hackstack(SYMBOL *);	/* CCCODE (1) */
int unsetz(PCODE *);		/*  CCJSKP (3), CCOPT (4) */
void killstack(void);		/*  CCGEN1 (1) */
void optlsh(PCODE *);		/* CCCODE (1) */

/* Internal functions */
static INT makepop(PCODE *), adjstack(INT, PCODE *);
static void foldinc(PCODE *);
static int snglop(int);
static PCODE *findmove(PCODE *, PCODE *);
#if 0
static int snglop();
static PCODE *findmove();
static INT makepop(), adjstack();
static void foldinc();
#endif

/* LOCALBYTE(p, np) - Optimize usage of local byte pointer.
**	P points to either an IOR S, or ADJBP S,.
**	NP points to a succeeding instr, either a LDB R,S or DPB R,S.
**
**	There may be several instructions in between.  We know however
** that S is not used or referenced in between.
**
**	The byte pointer will not be saved, so it is
** safe to make it a literal local-format BP.  The return value
** is 1 if the op could be folded into the previous instructions,
** and 0 otherwise.
**	This is only called from one place, in CCCODE.
*/

int
localbyte(p, np)
PCODE *p, *np;
{
    int op = np->Pop;
    int r = np->Preg;
    int s = np->Pr2;
    INT b;
    int i;
    PCODE *q;

    if (p
	&& p->Pop == P_IOR
	&& p->Ptype == PTA_PCONST /* && !prevskips(p) */
	&& p->Preg == s
	&& p->Pptr == NULL)
	{
	/*
	** fold:  p->	IOR S,[<pconst>]
	**		...
	**        np->	DPB  R,S
	**
	** into:  np->	DPB  R,[ppss00,,(S)]
	**
	** and perhaps fold further with previous ops...
	*/
	b = TGSIZ_WORD - p->Pbsize * (p->Poffset+1);	/* P field */
	b = ((b&077)<<6) | (p->Pbsize & 077);		/* add S field */
	b <<= 6;					/* shift into place */

	dropinstr(p);			/* drop the IOR from peephole buffer */
	dropinstr(np);			/* Drop the LDB/DPB too */
	codebp(op, r, b, s, (SYMBOL *)NULL, 0);	/* make new op */
	return 1;				/* folded, say so */
	}
    else if (p->Pop == P_ADJBP		/* Check for ADJBP S,I */
		&& p->Ptype == PTA_REGIS
		&& p->Preg != p->Pr2		/* Avoid ADJBP S,S */
		&& (q = findrset(before(p), p->Pr2)) != NULL
		&& q->Pop == P_IOR	/* Check for IOR I,[<pconst>] */
		&& q->Ptype == PTA_PCONST
		&& q->Pptr == NULL)
	{
	PCODE *rp;
	i = p->Pr2;		/* Pick up I holding wordptr index */

	/* Must verify that I is not used anywhere between the LDB and
	** the IOR, except for the ADJBP itself.
	*/
	for (rp = before(np); rp && rp != q; rp = before(rp))
	    if (rincode(rp, i))			/* Halt if ref seen */
		if (rp != p)
		    break;		/* unless it's the ADJBP */
	if (rp != q)
	    return 0;		/* Ref seen or something, forget it. */
	
	/*
	** fold:
	** q->	IOR I,[<pconst>]
	**		...
	** p->	ADJBP S,I
	**		...
	** np->	LDB/DPB R,S
	**
	** into: P_ADJBP S,[ppss00,,(I)]
	**	 P_DPB R,S
	*/

	b = TGSIZ_WORD - q->Pbsize * (q->Poffset+1);	/* P field */
	b = ((b&077)<<6) | (q->Pbsize & 077);	/* add S field */
	b <<= 6;				/* shift into place */

	dropinstr(q);		/* drop IOR */
	dropinstr(p);		/* and drop ADJBP */
	dropinstr(np);		/* and the LDB/DPB */
	codebp(P_ADJBP, s, b, i, (SYMBOL *)NULL, 0);	/* Make new ADJBP */
	code00(op, r, s);	/* and new LDB/DPB */
	return 1;
	}
    return 0;
}

/* FOLDBP(p) - Optimize a byte pointer operand.
**	Called with p pointing to a instr with a PTA_BYTEPOINT operand,
** and if it uses an index register tries to improve things.
**	May drop a previous instr if its action on the index reg can
** be folded into the byte pointer, either by changing the offset or
** using indirection.
*/
void
foldbp(p)
PCODE *p;
{
    PCODE *q;
    INT soff;

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

/* Look for a previous instruction that sets the index register */
    if (!p->Pindex || (q = findrset(before(p), p->Pindex)) == 0)
	return;			/* No index reg or can't find an instr */

    switch (q->Pop)		/* Found one, examine it */
	{
	case P_ADD:
	    if (q->Ptype == PTV_IMMED)
		{
		p->Poffset += q->Pvalue;	/* this BP has an offset */
		dropinstr(q);			/* drop the ADDI */
		}
	    break;

	case P_SUB:
	    if (q->Ptype == PTV_IMMED)
		{
		p->Poffset -= q->Pvalue;	/* this BP has an offset */
		dropinstr(q);			/* drop the SUBI */
		}
	    break;

	case P_MOVE:	/* MOVE or MOVEI */
	    if (p->Pptr != NULL)
		break;	/* don't double up symbol */
	    if (chkmref(q, p, &soff))	/* Verify OK to steal addr */
		break;
	    if (q->Ptype == PTA_MINDEXED)
		{
	    /* See if can use indirection */
		if (  soff			/* Cannot use offset */
		  || p->Poffset != 0	/* of any kind */
		  || p->Pop == P_ADJBP	/* Cannot adj an indirect BP */
		  || p->Pop == P_IBP	/* Cannot bump it either */
		  || p->Pop == P_ILDB
		  || p->Pop == P_IDPB)
		    break;
		p->Ptype |= PTF_IND;	/* Indirect OK, set @ bit! */
		}
	    else if (q->Ptype != PTV_IINDEXED)
		break;
	    p->Pptr = q->Pptr;			/* new addr symbol */
	    p->Pindex = q->Pindex;			/* index */
	    p->Poffset += q->Poffset - soff;	/* and offset */
	    dropinstr(q);			/* drop the move */
	    break;
	}
}

/* FOLDBYTE(p) - Optimize LDB/DPB instructions.
**	Called with p pointing to a LDB or DPB.
**	First checks to see if a halfword instruction can replace it, then
**	just invokes cse to combine with a previous IBP if any.
*/
void
foldbyte(p)
PCODE *p;
{
    int op;

    switch (op = p->Pop)		/* No POF_ flags shd be set */
	{
	case P_LDB:
	case P_DPB:
	    switch (p->Ptype & PTF_ADRMODE)	/* OK if instr skipped */
		{
		case PTA_BYTEPOINT:
		    switch ((int) p->Pbsize)
			{
		/* fold:
		**	LDB R,[2200,,x]	=>	HRRZ R,x
		**	DPB R,[2200,,x] =>	HRRM R,x
		**	LDB R,[222200,,x] =>	HLRZ R,x
		**	DPB R,[222200,,x] =>	HLRM R,x
		*/
			case 02200:	/* Right half? */
			    op = (op == P_LDB) ? P_HRRZ : P_HRRM;
			    break;
			case 0222200L:	/* Left half? */
			    op = (op == P_LDB) ? P_HLRZ : P_HRLM;
			    break;
			}
		case PTA_PCONST:
		    if (p->Pbsize == TGSIZ_HALFWD)
			{
		    /* Fold LDB/DPB R,[<pconst>] into halfword instruction */
			p->Pindex = 0;		/* Never any index */
			if (p->Poffset & 01)	/* Right half? */
			    op = (op == P_LDB) ? P_HRRZ : P_HRRM;
			else
			    op = (op == P_LDB)? P_HLRZ : P_HRLM;
			p->Poffset /= 2;		/* Make word offset */
			}
		    break;
		}
	    if (op != p->Pop)
		{
		p->Ptype &= ~PTF_ADRMODE;
		p->Ptype |= PTA_MINDEXED;
		p->Pop = op;
		}
	    break;
	}

    /* Whether instr was an optimized byte op or not, always
    ** invoke foldmove.  This can combine IBP + LDB => ILDB.
    */
    foldmove(p);
}

/* FOLDADJBP(p) - Optimize P_ADJBP instruction.
**
**    takes an P_ADJBP instruction in the peephole buffer,
**    and tries to fold it out (e.g. by turning it into an P_ADDI).
*/

void
foldadjbp(p)
PCODE *p;
{
    PCODE *q, *n;
    int a, r, s;
    INT boff, woff, bsiz;

    /* Make sure we're looking at an unskipped P_ADJBP */
    if (p->Pop != P_ADJBP || prevskips(p))
	{
	foldmove(p);			/* just run cse */
	return;
	}

    /*
    ** Find the instruction that sets R.
    */
    if (rinaddr(p, p->Preg))	/* Make sure R not otherwise used in ADJBP! */
	return;

    if ((n = findrset(before(p), p->Preg)) == NULL)
	{
	foldmove(p);		/* Nothing to fold into, try cse */
	return;
	}

    /*
    ** Found it, now see what kind of op we have.
    **
    ** If it is a SETZ, we simply turn the ADJBP into a MOVE.
    ** If it is a MOVNI or SETO or SUBI, we turn it into a MOVEI or ADDI.
    ** Otherwise, if it is not a MOVEI or ADDI we give up.
    */
    switch (n->Pop)			/* make sure we can hack it */
	{
	case P_SETZ:
	    n->Pop = P_NOP;
	case P_SETZ+POF_BOTH:
	    n->Preg = R_SCRREG;		/* take out reg if not whole op */
	    p->Pop = P_MOVE;		/* change null ADJBP into MOVE */
	    foldmove(p);			/* try further optimizations */
	    return;				/* all done */

	case P_MOVN:
	case P_SUB:
	case P_SETO:
	case P_MOVE:
	case P_ADD:
	    if (unsetz (n) && n->Ptype == PTV_IMMED)
		break;
	default:
	    foldmove(p);
	    return;
	}

    /* Now if instr is an ADJBP R,S (register-register) then we may be
    ** able to do further optimizations depending on how S is set.
    */
    q = NULL;			/* Initialize, no byte-pointer construction */
    if (p->Ptype == PTA_REGIS			/* If ADJBP R,S then */
	&& ((q = findrset(before(p), p->Pr2)) != NULL)	/* find instr that sets S */
	&& q->Pop == P_MOVE
#if SYS_CSI
	/* SSR 9718, 9719   AVOID the following
	 *   folds	MOVE 1,0(2) MOVEI 2,1 ADJBP 2,1 
	 *   into		    MOVEI 2,1 ADJBP 2,0(2)
         */
	&& p->Preg != q->Pindex
#endif
	)			/* Check for simple setup */

	/* Change MOVE S,x  /.../  ADJBP R,S   into   ADJBP R,x
	** Note that x may be a pointer constant, which allows following
	** optimization to win big.
	*/
	{
	r = p->Preg;		/* Save R */
	*p = *q;		/* Copy the MOVE instruction onto ADJBP */
	p->Pop = P_ADJBP;	/* Make it an ADJBP again */
	p->Preg = r;		/* with proper register */
	q->Pop = P_NOP;		/* and flush old MOVE instruction */
	q = NULL;		/* Say no byte-pointer construct instr */
	}

    /* Check for ADJBP R,[pconst].
    ** We can simply fiddle with the pointer-constant parameters to
    ** accomplish the effect of the ADDI/MOVEI that n points to.
    ** If it was a MOVEI (thus completely determining the new pointer)
    ** then the ADJBP can be flushed and replaced with a MOVE!
    */
    if (p->Ptype == PTA_PCONST)
	{
	p->Poffset += n->Pvalue;	/* Add together the byte offsets */
	if (n->Pop == P_MOVE)		/* Was R set by a MOVEI? */
	    p->Pop = P_MOVE;		/* Yes, turn ADJBP R,x into MOVE R,x */
	n->Pop = P_NOP;			/* Now flush the ADDI or MOVEI */
	return;				/* Win, win! */
	}

    /* Now see if there is a byte-pointer construction instruction
    ** before an ADJBP R,S in which case we may also be able to flush
    ** the ADJBP (and a MOVEI if that is what sets R) by changing the
    ** way the pointer is constructed.
    */
    if (q && q->Pop == P_IOR		/* Check for IOR S,[pconst] */
	&& q->Ptype == PTA_PCONST
	&& q->Pptr == NULL)		/* Better not have any symbol! */

	/* If found a byte-pointer construction:
	**
	** fold: n-> MOVEI/ADDI  R,n
	**		...
	**	 q-> IOR S,[pconst + byteoffset]
	**		...
	**	 p-> ADJBP  R,S
	**
	** into:  ADDI   S,i		(can flush if i == 0)
	**        IOR    S,[pconst + new byteoffset]
	**        MOVE/ADJBP   R,S	(MOVE if n was MOVEI; else ADJBP)
	*/
	{
	bsiz = q->Pbsize;			/* Save bytesize */
	boff = adjboffset(n->Pvalue+q->Poffset,	/* Get sum of byte offsets */
			&woff,			/* and set woff/boff */
			(int) (TGSIZ_WORD/bsiz));

	a = n->Pop;		/* Remember the op that set R */
	r = p->Preg;		/* Remember regs of P_ADJBP for later */
	s = p->Pr2;

	/* Flush old instructions */
	n->Pop = P_NOP;		/* Flush MOVEI/ADDI */
	q->Pop = P_NOP;		/* Flush IOR */
	p->Pop = P_NOP;		/* Flush ADJBP */
	fixprev();

	/* Make new instructions */
	if (woff)
	    codr1(P_ADD, s, woff);		/* New ADDI */
	codr10(P_IOR, s, (SYMBOL *)NULL, bsiz, boff);	/* New IOR */
	code00((a==P_MOVE ? P_MOVE : P_ADJBP), r, s);	/* New MOVE or ADJBP */
	return;
	}

#if 0
    /* That lost.  Last possibility to check for is simply adding 1 to the
    ** pointer, which can be done with a simple IBP.
    */
    if (n->Pop == P_MOVE && n->Pvalue == 1)
	{
	n->Pop = P_NOP;			/* change P_MOVEI R,1 + P_ADJBP R,x */