cceval.c

KCC , a good c compiler, write by Ken Harrenstien

(1) Explicit top-level cast operation, specified by user.
	Expressions starting with a N_CAST of CAST_VOID.
(2) Flag set in top-level node by evaldiscard().
	If the NF_DISCARD flag is set, the result of that expression
	is to be thrown away.
(3) Implied by statement context, as per [H&S2 7.13]:
	An expression statement.
	The first operand of a comma expression.
	The initialization and incrementation expressions in a "for" statement.

In practice more than one method is used; for example the parser
checks the statement context cases and ensures that NF_DISCARD is set
for those expressions.  The code generator does a similar
context-dependent setting as a backup.

#endif

/* EVALDISCARD - Used by CCSTMT parsing.
**	Sets flag for given expression to indicate value can be discarded,
** and propagates this flag downwards as far as possible,
** and attempts to reduce expression as much as possible, so as to
** avoid generating any code.
**
** Note: this function returns NULL if the expression was completely flushed.
**
**	A warning is printed only if two conditions hold:
** (1) the expression's type was not "void".  (If it was, then the programmer
**	has coded properly, perhaps with an explicit (void) cast.)
** (2) the top-level operator node is changed, OR the discard count has
**	been bumped.  If not then this top-level operator or its operands
**	had a side effect and thus was preserved.
**
** The sequential (,), conditional (?:), and binary logical (&&,||) operators
** are a little tricky; it is possible for these to have some of their
** sub-expressions discarded without affecting the top-level node.
** This is why the "discnt" variable exists, for an unambiguous indication
** that something was discarded.
**
** Yet another fuzzy situation exists for the cast operator, which can
** exist either due to an explicit user cast or an implicit type coercion.
** We have three choices when discarding a cast operator:
**	(1) always complain
**	(2) never complain
**	(3) complain if discarding an explicit cast; don't if discarding an
**		implicit cast.
** We implement (3) by using the NF_USERCAST flag to distinguish explicit
** from implicit casts, and only bumping the discard count for explicit
** casts.  Both are thrown away, however, which means that even an implicit
** cast will generate a warning if was the top-level node given to
** evaldiscard().  This should never happen, though, as there is no context
** in C for which a top-level implicit coercion is necessary.
*/

static int discnt;	/* Count of internal discards (see above comment) */

NODE *
evaldiscard(NODE *n)
{
    NODE *dn;

    if (!n) return n;			/* Check for NULL */
    if (n->Ntype == voidtype)		/* If type is explicitly void, */
	return edisc(n);		/* never give warning message. */

    /* Must check for discards... */
    discnt = 0;			/* Reset internal flush count */
    dn = edisc(n);		/* Run it through, see what we get */
    if (dn != n || discnt)	/* If anything munged, then barf. */
	note("Discarding %s without side effects",
		    dn	? "operator"	/* If still stuff, assume just oper */
			: "expression");	/* else flushed whole expr */
    
    return dn;			/* Note this may or may not be NULL. */
}


/* ESEQDISC - Auxiliary for evalb1op and evalasop, to take care of
**	flushing the non-constant parts of an expression.
** The left and right args should be put into a "(l, r)" sequential
** expression, if the left arg has a side-effect that prevents it
** from being completely flushed.
**	edisc() is called directly to avoid provoking warning messages.
*/
static NODE *
eseqdisc(NODE *l, NODE *r)
{
    if ((l = edisc(l)) == NULL)	/* If can completely flush left arg, */
	return r;		/* just return right arg. */
    return ndef(N_EXPRLIST, r->Ntype, 0, l, r);
}

/* EDISC - Evaluate node, discarding anything that doesn't have
**	side effects.  This is very similar to sideffp() in CCEVAL!
**
** Note that exprs which can be lvalues must be checked for the "volatile"
** type qualifier, which counts as a side-effect.  See comments in sideffp().
*/
static NODE *
edisc(NODE *n)
{
    NODE *ln, *rn;
    int savcnt;

    if (n == NULL) return n;
    n->Nflag |= NF_DISCARD;		/* Set flag for this node */

    switch(tok[n->Nop].tktype) {
	case TKTY_RWOP:		/* Reserved-word Op, similar to primary */
	    switch (n->Nop) {
		case Q_ASM:		/* asm() has side effects! */
		    return n;
	    }
	    return n;			/* Assume new ops have side effs too */

	case TKTY_PRIMARY:	/* Primary expression */
	    switch (n->Nop) {
		case N_FNCALL:			/* Funct call has side effs! */
		    return n;
		case Q_DOT:			/* May be lvalue, find out */
		    if (!(n->Nflag & NF_LVALUE))
			return edisc(n->Nleft);
		case Q_MEMBER:			/* Always an lvalue */
		    if (tisanyvolat(n->Ntype))
			return n;		/* Volatile, leave alone! */
		    ++discnt;
		    return edisc(n->Nleft);
		case Q_IDENT:
		    if (tisanyvolat(n->Ntype))
			return n;		/* Volatile, leave alone! */
		    break;
	    }
	    ++discnt;
	    return NULL;	/* All other primary exprs have no side-eff */

	case TKTY_UNOP:		/* Unary operator - check single operand */
	    switch (n->Nop) {
		case N_POSTINC: case N_PREINC:
		case N_POSTDEC: case N_PREDEC:
		    return n;		/* These four have side effects! */
		case N_CAST:		/* Cast is a bit special */
		    if ((n->Nflag & NF_USERCAST)==0)	/* If implicit cast, */
			return edisc(n->Nleft);		/* flush quietly, */
							/* without ++discnt! */
		    if (n->Ntype == voidtype) {	/* If explicit cast to void, */
			savcnt = discnt;	/* flush the rest quietly! */
			n = edisc(n->Nleft);
			discnt = savcnt;
			return n;
		    }
		    /* else drop thru to flush non-quietly! */
		    break;

		case N_PTR:			/* Always lvalue, so check */
		    if (tisvolatile(n->Ntype))	/* Check, note type will  */
			return n;		/* never be struct/union */
		    break;		/* so needn't use tisanyvolat */

		case N_ADDR:		/* Special checks to bypass qualifs */
		    switch (n->Nleft->Nop) {
			case Q_IDENT: ++discnt;	/* OK to just flush this */
				return NULL;
			case Q_DOT:
			case Q_MEMBER:
			case N_PTR:
			    ++discnt;
			    return edisc(n->Nleft->Nleft);
		    }
		    break;
	    }
	    /* Drop through to flush unary operator */

	case TKTY_BOOLUN:	/* Unary boolean operator (only '!') */
	    ++discnt;		/* Say something flushed */
	    return edisc(n->Nleft);

	case TKTY_BOOLOP:	/* Binary boolean or logical operator */
	    if (n->Nop == Q_LAND || n->Nop == Q_LOR) {
		/* Binary logical op, right-hand operand may or may not be
		** evaluated.  If it has no side effect we can flush it
		** and check the left-hand operand, but if it does then
		** we have to leave the left-hand operand alone.
		*/
		if ((n->Nright = edisc(n->Nright)) != NULL)/* Check 2nd val */
		    return n;			/* Can't flush it */
		++discnt;			/* Aha, note flushed and */
		return edisc(n->Nleft);		/* can now check 1st val */
	    }
	    /* Not a logical boolean operator, drop thru to treat
	    ** like binary operator
	    */
	case TKTY_BINOP:	/* Binary operator - check both operands */
	    ++discnt;			/* Will always flush something. */
	    ln = edisc(n->Nleft);
	    rn = edisc(n->Nright);
	    if (!rn) return ln;
	    if (!ln) return rn;
	    /* Still have both operands, set up to execute in sequence
	    ** by converting into a comma expression (ln,rn).
	    ** Do left first, then right, just for consistency.
	    ** Note flags already have NF_DISCARD set in them.
	    */
	    return ndef(N_EXPRLIST, rn->Ntype, rn->Nflag,
			ndef(N_EXPRLIST, ln->Ntype, ln->Nflag,
				(NODE *)NULL, ln),
			rn);

	case TKTY_ASOP:		/* Binary assignment operator */
	    break;		/* Always a side-effect operation */

	case TKTY_TERNARY:	/* Ternary operator (only '?') - check 3 ops */
	    /* First check each of the 2 possible values.
	    ** Note either may be replaced by NULL or have their types
	    ** changed so they no longer match the overall result type!
	    ** The gternary() code in CCGEN2 needs to be aware of this.
	    */
	    savcnt = discnt;			/* Remember count */
	    ln = edisc(n->Nright->Nleft);
	    rn = edisc(n->Nright->Nright);
	    if (!ln && !rn) {			/* If both values went away */
		++discnt;
		return edisc(n->Nleft);		/* Then hack condition only! */
	    }
	    /* In an attempt to avoid complaining about cases such
	    ** as (cond ? foo() : 0) which occur in macros, we check to
	    ** see whether a discard was due to the complete flushage of
	    ** a single primary value.  In this case one pointer will have been
	    ** changed to NULL (make sure it wasn't already NULL!) and the
	    ** count of discards will be only 1 greater.  If so, undo the
	    ** count so we don't complain if that was the only problem.
	    */
	    if ((!ln && n->Nright->Nleft)	/* Left changed, now NULL? */
	     || (!rn && n->Nright->Nright))	/* or right? */
		if (discnt == savcnt+1)		/* Yes, flushed just one?*/
		    --discnt;			/* If so, ignore that flush */

	    n->Nright->Nleft  = ln;
	    n->Nright->Nright = rn;
	    break;		/* Still have side effects */

	case TKTY_SEQ:		/* Sequential evaluation operator (only ',') */
	    if ((n->Nright = edisc(n->Nright)) == NULL) { /* If zap top, */
		++discnt;
		return edisc(n->Nleft);			/* flush it. */
	    }

	    /* Keep but check the rest.  Actually it shouldn't be necessary
	    ** to check the rest, as the parser does this when it builds
	    ** the sequential expression.  But it doesn't hurt to do it again
	    ** (someday something else might build those expressions too).
	    */
	    n->Ntype = n->Nright->Ntype;	/* Update overall type */
	    n->Nleft = edisc(n->Nleft);		/* Do rest. */
	    break;

	default:
	    int_warn("edisc: non-expr %N", n);
	    break;
    }
    return n;
}

/* SIDEFFP - Returns TRUE if expression has side effects.
**	Has to trace entire expression tree, so needs to know about
** structure of parse trees.
**
**	Any read reference to a "volatile"-qualified object is also considered
** a side effect!  Read refs can only happen with lvalues, and lvalues are
** only produced by:
**	Q_IDENT (identifier)
**	N_PTR (*)
**	Q_DOT (.)
**	Q_MEMBER (->)
** Note that N_ADDR (&) is a special case because even though it takes an
** lvalue as its operand, the object is not actually referenced.  To avoid
** spuriously flagging these cases, we have to handle N_ADDR by checking
** its operand for the lvalue objects and bypassing the first level.
*/
int
sideffp(n)
NODE *n;
{
    extern char *nopname[];

    switch(tok[n->Nop].tktype) {
	case TKTY_RWOP:		/* Similar to primary expression */
	    if (n->Nop == Q_ASM)	/* asm() code has side-eff */ 
	        return 1;
	    return 1;		/* Use safe default in case of new built-ins */

	case TKTY_PRIMARY:	/* Primary expression */
	    switch (n->Nop) {
		case N_FNCALL:	return 1;	/* Function call has side-eff*/
		case Q_DOT:			/* May be lvalue, find out */
		    if (!(n->Nflag & NF_LVALUE))
			return sideffp(n->Nleft);
		case Q_MEMBER:			/* Always an lvalue */
		    if (tisanyvolat(n->Ntype))
			return 1;
		    return sideffp(n->Nleft);	/* Check these out */
		case Q_IDENT:			/* Ident is always lvalue */
		    return tisanyvolat(n->Ntype);
	    }
	    return 0;			/* Other primaries have no side-eff */

	case TKTY_UNOP:		/* Unary operator - check single operand */
	    switch (n->Nop) {
		case N_POSTINC: case N_POSTDEC:
		case N_PREINC: case N_PREDEC:
		    return 1;
		case N_PTR:			/* Always lvalue, so check */
		    if (tisvolatile(n->Ntype))	/* Check, note type will  */
			return 1;		/* never be struct/union */
		    break;		/* so needn't use tisanyvolat */

		case N_ADDR:		/* Special checking!! */
		    switch (n->Nleft->Nop) {
			case Q_IDENT: return 0;
			case Q_DOT:
			case Q_MEMBER:
			case N_PTR:
			    return sideffp(n->Nleft->Nleft);
		    }
		    break;
	    }
	    return sideffp(n->Nleft);

	case TKTY_BOOLUN:	/* Unary boolean operator (only '!') */
	    return sideffp(n->Nleft);

	case TKTY_BINOP:	/* Binary operator - check both operands */
	case TKTY_BOOLOP:	/* Binary boolean operator - ditto */
	    return (sideffp(n->Nright) || sideffp(n->Nleft));

	case TKTY_ASOP:		/* Binary assignment operator */
	    return 1;		/* Always a side-effect operation */

	case TKTY_TERNARY:	/* Ternary operator (only '?') - check 3 ops */
	    if (sideffp(n->Nleft)) return 1;	/* Check condition */
	    n = n->Nright;	/* Then set up to check the 2 outcomes */
	    return ((n->Nright && sideffp(n->Nright))
		|| (n->Nleft && sideffp(n->Nleft)));
	
	case TKTY_SEQ:		/* Sequential evaluation operator (only ',') */
	    do if (sideffp(n->Nright)) return 1;
	    while ((n = n->Nleft) != NULL) ;
	    return 0;		/* Nothing had a side effect, so return zero */

	default:
	    int_warn("sideffp: bad op %N", n);
	    return 1;			/* Play it safe */
    }
}

/* ISTRUE - evalute boolean expression as far as we can.
**	Used only by gfor(), to see whether the loop test
**	can be omitted the first time through, and thus moved to the
**	end of the loop.
** The main difference from evalexpr() is that the expression is known
** to be of scalar type, and we also have an expression ("bindings") which
** constitutes the initial expression.  Q_IDENTs encountered during the
** evaluation are looked up in the binding expr to see if they can be resolved,
** and thus produce a constant the first time the loop test is checked.
*/
static int unset;		/* whether an unbound var was found */

INT
istrue(NODE *test, NODE *bindings)
{
    unset = 0;
    return value(test, bindings) && !unset;
}

/* ---------------------------------------- */
/*      recursive expression evaluator      */
/* ---------------------------------------- */

static long
value(NODE *test, NODE *bindings)
{
    if (test == NULL) return 0;
    switch (test->Nop) {
    case N_ICONST:
	return test->Niconst;

    case Q_IDENT:
	test = lookup(test->Nid, bindings); /* find variable assignment */
	if (test == NULL) break;	/* none found, give up.  Otherwise, */
	return value(test, (NODE *)NULL); /* re-eval hoping no vars */

    case Q_LAND:
	return value(test->Nleft, bindings) && value(test->Nright, bindings);
    case Q_LOR:
	return value(test->Nleft, bindings) || value(test->Nright, bindings);
    case Q_NOT:
	return !value(test->Nleft, bindings);

    case Q_EQUAL:
	return value(test->Nleft, bindings) == value(test->Nright, bindings);
    case Q_LESS:
	return value(test->Nleft, bindings) < value(test->Nright, bindings);
    case Q_GREAT:
	return value(test->Nleft, bindings) > value(test->Nright, bindings);
    case Q_NEQ:
	return value(test->Nleft, bindings) != value(test->Nright, bindings);
    case Q_LEQ:
	return value(test->Nleft, bindings) <= value(test->Nright, bindings);
    case Q_GEQ:
	return value(test->Nleft, bindings) >= value(test->Nright, bindings);

    case Q_PLUS:
	return value(test->Nleft, bindings) + value(test->Nright, bindings);
    case Q_MINUS:
	return value(test->Nleft, bindings) - value(test->Nright, bindings);
    case Q_MPLY:
	return value(test->Nleft, bindings) * value(test->Nright, bindings);
    case Q_DIV:
	return value(test->Nleft, bindings) / value(test->Nright, bindings);
    case Q_MOD:
	return value(test->Nleft, bindings) % value(test->Nright, bindings);
    }

    /* here when unrecognized node or unbound var, remember bad expr */
    unset = 1;				/* tell caller we lost */
    return 0;				/* and pick arbitrary val to return */
}

/* ------------------------------------------------ */
/*      find an assignment to a given variable      */
/* ------------------------------------------------ */

static NODE *
lookup(SYMBOL *var, NODE *bindings)
{
    NODE *result;

    if (bindings == NULL) return NULL;
    switch (bindings->Nop) {
    case N_EXPRLIST:
	result = lookup(var, bindings->Nright);
	if (result != NULL) return result;
	else return lookup(var, bindings->Nleft);
    case Q_ASGN:
	if (bindings->Nleft->Nop == Q_IDENT && bindings->Nleft->Nid == var)
	    return bindings->Nright;
	else return NULL;
    default:
	return NULL;
    }
}