ccopt.c

KCC , a good c compiler, write by Ken Harrenstien

	** a MOVEM R,-n(P).
	**	 A PUSH of anything else would
	** take 2 instructions to replace the PUSH if the stack pointer
	** was different, so it does us no good to continue looking back.
	*/
	if (p->Preg != R_SP || prevskips(p))	/* Fail if skipped */
	    return n;				/* or not a stack instr */
	if (n < 0 && p == previous)	/* If stk being flushed & last instr */
	    {
	    dropinstr(p);		/* can just flush the PUSH! */
	    ++n;			/* Account for flushed instr */
	    p = previous;		/* Get new previous, restart loop */
	    break;
	    }
	if (((p->Ptype == PTV_IMMED && p->Pvalue >= -1 && p->Pvalue <= 0)
	     || p->Ptype == PTA_REGIS))
	    {
	    maxfold = 0;	/* This referenced top of stack */
	    p = before(p);
	    break;		/* Continue looking back */
	    }
	return n;

    case P_POP:
	/* OK to look past a POP if it is a POP P,R
	** since adjstack() can replace that with MOVE R,-n(P) if the
	** stack pointer is changed.
	** Otherwise, as for PUSH, we stop since it would take 2 instrs
	** (a MOVE and MOVEM) to replace the POP; settle for what we have
	** now.
	*/
	if ( p->Preg == R_SP		/* Must be POP 17, */
	  && p->Ptype == PTA_REGIS	/* and a POP 17,R */
	  /* && !prevskips(p) */  )	/* and not skipped over */
	    {
	    maxfold = 0;		/* This is a ref to top of stack */
	    p = before(p);		/* continue looking back */
	    break;
	    }
	return n;

#if 0	/* Should never have positive index to stack like this! */
    case P_MOVEM:
	if (p->Ptype == PTA_MINDEXED
	    && p->Pindex == R_SP
	    && p->Poffset == 1 && n > 0 && !prevskips (p))
	    {

	    /*
	    ** fold:  P_MOVEM R,1(17)
	    ** into:  P_PUSH  17,R
	    */
	    p->Ptype = PTA_REGIS;
	    p->Pr2 = p->Preg;
	    p->Preg = R_SP;
	    p->Pop = P_PUSH;
	    n += adjstack(-1, p);
	    n--;
	    p = previous;
	    maxfold = (stackrefs? 0 : 1000000); /* start again */
	    break;
	    }
	/* Can't fold, check for stack ref */
	if (( (p->Ptype & PTF_ADRMODE) == PTA_MINDEXED
	    ||(p->Ptype & PTF_ADRMODE) == PTA_BYTEPOINT)
	  && p->Pindex == R_SP
	  && p->Poffset > - maxfold)
	    maxfold = - p->Poffset;
	p = before(p);
	break;
#endif

    case P_MOVE:
	if ( p->Ptype == PTA_MINDEXED /* && !prevskips(p) */
	  && p->Pindex == R_SP
	  && p->Poffset == 0		/* MOVE R,0(17) */
	  && n < 0			/* Want stuff popped off */
	  && (maxfold > 0		/* No other ref to top of stack */
	    || p == previous))	/*   or no other instrs in between */
	    /*
	    ** fold:  P_MOVE  R,0(17)
	    ** into:  P_POP   17,R
	    */
	    {
	    n += makepop(p);		/* turn into P_POP */
	    p = previous;
	    maxfold = (stackrefs ? 0 : 1000000L);	/* Start again */
	    break;
	    }
	/* Can't fold, drop thru to normal check for stack ref */
    case P_MOVEM:

    case P_ADD:
    case P_SUB:
    case P_IMUL:
    case P_IDIV:
    case P_UIDIV:
    case P_FADR:
    case P_FSBR:
    case P_FDVR:
    case P_FMPR:
    case P_AND:
    case P_IOR:
    case P_XOR:
    case P_CAI:
    case P_MOVN:
    case P_SETCM:
    case P_SETZ:
    case P_CAM:
    case P_SETO:
    case P_AOS:
    case P_SOS:
    case P_LSH:
    case P_ADJBP:
    case P_SUBBP:
    case P_IBP:
    case P_ILDB:
    case P_IDPB:
    case P_LDB:
    case P_DPB:
    case P_HLRZ:
    case P_HRLM:
    case P_HRRZ:
    case P_HRRM:
    case P_TDC:
    case P_TDN:
    case P_TDO:
    case P_TDZ:
    case P_TLC:
    case P_TLN:
    case P_TLO:
    case P_TLZ:
    case P_TRC:
    case P_TRO:
    case P_TRN:
    case P_TRZ:
    case P_SKIP:
    case P_SMOVE:
	/* If instr is one we understand, can check it for stack ref */
	if (rinreg(p, R_SP))		/* If used as OP 17,x */
	    return n;			/* then always give up. */
	if (rinaddr(p, R_SP))		/* If used in address, */
	    /* it better be as an index reg, or we can't handle it. */
	    {
	    if ( ((p->Ptype & PTF_ADRMODE) != PTA_MINDEXED
		&&(p->Ptype & PTF_ADRMODE) != PTA_BYTEPOINT)
	      || p->Pindex != R_SP)
		return n;		/* Can't grok this address ref */
	    /* Indexing through stack ptr, can handle it! */
	    if (p->Poffset > -maxfold)	/* See if ref is higher on stk */
		maxfold = - p->Poffset;	/* Yes, remember as highest so far */
	    }
	p = before(p);
	break;

    default:
	/* Instr we don't understand, don't try to optimize back over it */
	return n;
}
return n;
    }

/* MAKEPOP(p) - Turn P_MOVE instruction into P_POP
**
**	This is only called by foldstack().
**	This is the only place in KCC where a P_POP pseudo-code instruction
** is generated.
**
** This turns the given MOVE R,0(17) into POP 17,R and fixes up
** the surrounding instructions.  It returns the result of
** adjstack() + 1 (for the new extra pop).
*/

static INT
makepop(p)
PCODE *p;
    {
    PCODE *q, *b;


    /* First make the pop */
    p->Pop = P_POP;
    p->Ptype = PTA_REGIS;
    p->Pr2 = p->Preg;	/* Copy R into 2nd reg */
    p->Preg = R_SP;

    /* Now see if we can further fold it.
    ** Attempt to turn:		into:
    **	p->	POP P,R		--
    **	q->	MOVEM R,X	POP P,X
    */
    if (p->Pr2 != R_RETVAL
      && (q = after(p)) != NULL
      && q->Pop == P_MOVEM
      && q->Preg == p->Pr2
      && !rinaddr(q, p->Pr2))
	{		/* Ensure R not used in X */
	/* Have a MOVEM R,X -- scan forward to ensure that the value of R
	** isn't needed by any following instructions.
	*/
	    for (b = q; (b = after(b)) != NULL; )
		if (rincode(b, p->Pr2))	/* Found an instr that hacks R? */
		    {
		    if (rruse(b, p->Pr2))	/* Yep, see if it uses val in R */
			q = NULL;		/* Yes, must leave it alone */
		    break;
		    }
	    if (q)			/* OK to go ahead? */
		{
		q->Pop = P_POP;		/* Yes, make P_POP */
		q->Preg = p->Preg;		/* from stack reg */
		p->Pop = P_NOP;		/* drop register P_POP */
		p = q;			/* Start adjust from this instr */
		}
}

return adjstack(1, p) + 1;
    }

/* ADJSTACK(n, p) - Fix up old ops after stack change shifts.
**
**	The section of the buffer from P (exclusive) to the end
** ("previous") has all references to the stack adjusted as if an
** ADJSP 17,N at P had vanished.  Thus the effect on the instructions
** is as if the stack pointer had changed by -N from what it used to be.
**
** This is an auxiliary routine used by foldstack() (and its auxiliary
** makepop(); these are the only 2 routines which call it.
**
** The section of the buffer changed is assumed to be safe, i.e. checked
** over by foldstack().
** It returns the net change to the stack offset as a result of
** turning PUSH/POP instructions into ones which don't change the stack
** pointer.
*/

static INT
adjstack(n, p)
INT n;
PCODE *p;
    {
    PCODE *q;
    INT c = 0;				/* how much we changed it */

    /* Loop back until we hit the changed op, and then return. */
    for (q = previous; q != p; q = before(q))
	{
	    switch (q->Ptype & PTF_ADRMODE)
		{

		case PTA_MINDEXED:
		case PTA_BYTEPOINT:		/* If an indexed instruction */
		    if (q->Pindex == R_SP)	/* uses the stack ptr as index */
			q->Poffset += n;	/* then need to adjust it. */
		    break;

		case PTA_REGIS:		/* POP/PUSH P,R turns into MOVE/M R,-n(P) */
		    if (q->Preg == R_SP)
			switch (q->Pop)
			    {
			    case P_POP:
				c += adjstack(-1, q);
				q->Pop = P_MOVE;
				q->Preg = (char) (q->Pr2); // FW KCC-NT
				q->Ptype = PTA_MINDEXED;
				q->Pptr = NULL;
				q->Pindex = R_SP;
				q->Poffset = n;
				c--;
				break;
			    case P_PUSH:
				c += adjstack(1, q);
				q->Pop = P_MOVEM;
				q->Preg = (char) (q->Pr2); // FW KCC-NT
				q->Ptype = PTA_MINDEXED;
				q->Pptr = NULL;
				q->Pindex = R_SP;
				q->Poffset = n + 1;
				c++;
				break;
			    }			/* end case PTA_REGIS: switch(q->Pop) */

		case PTA_RCONST:	/* PUSH P,[0/-1] becomes SETZB/OB 16,-n(P) */
		    if (q->Pop == P_PUSH)
			{
			c += adjstack(1, q);
			q->Pop = (q->Pvalue == 0)? P_SETZ+POF_BOTH : P_SETO+POF_BOTH;
			q->Preg = R_SCRREG;	/* have to have some reg here */
			q->Ptype = PTA_MINDEXED;
			q->Pptr = NULL;
			q->Pindex = R_SP;
			q->Poffset = n + 1;
			c++;
			break;
			}
		}				/* end switch(q->Ptype) */
}

return c;
    }

/* HACKSTACK(label) - Pull beginning-of-routine P_ADJSP across label
**
** Often some code will start out with  if (cond) return;
** if there are local variables in the routine they will be made
** and unmade unnecessarily while the condition is checked.
** Here we attempt to fix that up by pulling the P_ADJSP for the
** local variables across the  if  and  return.
** This also works for some cases where there is a JRST instead of a POPJ.
**
** Our argument is the label we are about to emit;
** the return value is the P_ADJSP that must be done
** after the label is (or is not) emitted.
*/
#if 0	/* COMMENT */
	The algorithm used here is a little non-obvious and needs some
words of explanation.
	Basically, we are looking backwards from our current location
(marked by "label") to see if we can find an ADJSP with a positive
value N.  If we find one, we see if it can be flushed entirely or not;
only flushing it partially is no good, since the instruction takes
just as much time regardless of N.
	To see whether it can be flushed, we have to know two
things:
FIRST, does the stack size change between the ADJSP and our label?  If
new cells are added in some way (PUSH is the only way, as an ADJSP
would have been caught) then they must have been flushed off before
reaching our label.  We check this by making sure the current stack
offset ("spos") after the ADJSP is the same as that of the stack
offset at our label ("stackoffset").  Only if they are the same is it
safe to move this ADJSP to our label.

 SECOND, are any of the N stack cells the ADJSP creates referenced
between there and our label?  As we go back, we check each instruction
for a stack reference;
but since we don't know beforehand how large N
is, we cannot easily know which references are significant.  We only
know two things: (1) Refs with a negative overall stack offset are to
the function arguments and thus are okay, and (2) Refs with a positive
offset higher than "stackoffset" refer to places above N which are
temporary (created by PUSH, removed by POP or ADJSP) and will not
exist by the time we are at our label, and thus are also OK.
	To keep track of positive-offset references the same or lower
than "stackoffset", we keep a count "nrefs" of such references, and a
variable "ceiling" which remembers the offset of the largest such
reference seen.  It is important to remember that "ceiling" is NOT the
largest positive-offset reference;
it is only the largest one that is
at or below "stackoffset".

	Thus, when we find the positive ADJSP, first we check "nrefs";
if
there were no qualifying references, we are safe.  But otherwise the N
tells us where the N cells started;
if our "ceiling" is below this start,
then none of those cells were referenced and we are also safe.  If on the
other hand the "ceiling" is above the start of the N cells, then it marks
a reference to one of the N cells and we dare not touch the ADJSP.

	Note that if the global "stackrefs" is set, there is at least one
automatic variable address somewhere in the function, which prevents us from
ever flushing a positive ADJSP.  At least not without even hairier checking
to ensure that no such address is generated within the range of instructions
between the ADJSP and the label.  For the time being, we try to do
    this
    hairy checking, assuming that only three kinds of instructions can possibly
    generate such addresses: MOVEI, MOVE [bp], and ADJBP [bp].

#endif

    INT
    hackstack (lab)
    SYMBOL *lab;
    {
    INT spos;			/* Current stack offset */
    INT ceiling = (-1);		/* Largest "affected" stack offset ref */
    INT nrefs;			/* # of such stack references seen */
    PCODE *lastadj, *p;
    INT newtop, adjres;

#if 0	/* We try to check for generated addrs... */
    if (stackrefs)
	return 0;		/* Too risky */
#endif
    if (isskip(previous->Pop))
	return 0;

    spos = stackoffset;			/* Set current stack offset */
    nrefs = 0;				/* No refs yet */
    lastadj = NULL;			/* haven't found an ADJSP yet */

    for (p = previous; p != NULL; p = before (p))
	switch (p->Pop & POF_OPCODE)
{

    case P_JRST:
    case P_JUMP:		/* A jump to someplace */
    case P_AOJ:
    case P_SOJ:		/* had better be to our label */
	if (p->Pptr == NULL)
	    return 0;	/* Make sure it has a label */
	if (p->Pptr->Sclass == SC_ILABEL)	/* If it's an internal lab, */
	    {
	    if (p->Pptr != lab)		/* and not to our label, */
		return 0;		/* then must fail, can't track code */
	    if (spos != stackoffset)	/* To our label.  Offset gotta match */
		return 0;		/*  Ugh.  Probably an error. */
	    continue;			/* OK, can continue. */
	    }
	/* Jump to an external label.  This is assumed to be a tail
	** recursion optimization (where a PUSHJ + POPJ is replaced by a
	** JRST), and so we interpret the jump like a POPJ by dropping
	** through.
	*/

    case P_POPJ:		/* Handle POPJ (also fall thru from above) */
	spos = 0;		/* stack can't exist here */
	lastadj = NULL;		/* so don't remember ADJSP after */
	continue;

    case P_PUSH:
	/* PUSH of something onto the stack must check two things:
	**	the address pushed into (top of stack), and
	**	the address pushed from (address ref).
	** We do the top of stack first.  This involves two checks of its own;
	**	First we make sure the object pushed is later removed (by
	**	seeing whether the current stack offset is smaller than the
	**	original one farther down in the code).
#if 0
	**	Second we do an address ref check similar to that done for
	**	memory operands, except that Poffset is known to be 0.
#endif
	**
	*/
	if (p->Preg == R_SP)		/* If pushing onto stack, check it */
	    {
	    if (spos < stackoffset)	/* If putting stuff on stack that */
		return 0;		/* isn't removed later, give up. */
#if 0
	    if (nrefs++ == 0
	      || spos < ceiling)	/* Update lowest cell reffed */
		{
		ceiling = spos;
		if (ceiling <= 1)	/* If 1st cell or worse, */
		    return 0;		/* quit. */
		}
#endif
	    spos--;	/* See comment below */
	    }
	/* PUSH of something onto the stack must bump down the stack offset
	** prior to checking address ref, as when the instr is executed
	** the address is computed before the stack is bumped.  But our