/************************************************************************/
/*                                                                      */
/* Copyright (c) 1988 -                                                 */
/*     The Rector and Visitors of the University of Virginia            */
/*                                                                      */
/* This code may not be distributed further without permission          */
/*      from the University of Virginia.                                */
/* This code is distributed WITHOUT ANY WARRANTY.  No claims are        */
/*      made as to whether it serves any particular purpose or even     */
/*      works at all.                                                   */
/*                                                                      */
/************************************************************************/

#include "types.h"
#include "tword.h"
#include "scan.h"
#include "node.h"

# define LCON(p) (p->nd.in.left->nd_op == ND_ICON)
# define RCON(p) (p->nd.in.right->nd_op == ND_ICON)
# define LO(p) p->nd.in.left->nd_op
# define RO(p) p->nd.in.right->nd_op
# define RTY(p) p->nd.in.right->nd_type
# define RVI(p) p->nd.in.right->nd.tn.ival
# define RVR(p) p->nd.in.right->nd.tn.rval

/*
 * nd_zapright converts tree (e1 op e2) to (e1).
 */

NODE *
nd_zapright(p)
	register NODE *p;
{
	register NODE *l, *r;
	(l = p->nd.in.left)->nd_type = p->nd_type;
	p->nd_op = ND_FREE;
	if (r = p->nd.in.right)
		r->nd_op = ND_FREE;
	return(l);
}

/*
 * nd_local optimizes ND_PCONV nodes.  This version assumes that the target
 * machine requires no action to convert pointers and simply eliminates
 * the node.
 */

NODE *
nd_local(p)
	register NODE *p;
{
	p->nd_op = ND_FREE;
	return(p->nd.in.left);
}

/*
 * nd_optim1 removes extraneous ND_PCONV nodes and reshapes the tree to
 * "bubble" constants together for folding.
 */

NODE *
nd_optim1(p)
	register NODE *p;
{
	register int o;
	register NODE *sp;

	/* skip leaf nodes */

	o = p->nd_op;
	if (ND_LEAF(o))
		return(p);

	/* do operands first */

	p->nd.in.left = nd_optim1(p->nd.in.left);
	if (p->nd.in.right)
		p->nd.in.right = nd_optim1(p->nd.in.right);

	/*
	 * convert (c1 op c2) to (c3) where c1 and c2 are constants and
	 * c3 == c1 op c2
	 */

	if (LCON(p) && p->nd.in.right && RCON(p) &&
		nd_conval(o, p->nd.in.left, p->nd.in.right))
	{
		return(nd_zapright(p));
	}

again:

	switch(o) {

	case ND_PCONV:
		return (nd_local(p));

	case SY_MINUS:
	
		/* convert (e - c) to (e + (-c)) */

		if(RCON(p)) {
			if (RTY(p) == TW_DOUBLE)
				RVR(p) = -RVR(p);
			else
				RVI(p) = -RVI(p);
			o = p->nd_op = SY_PLUS;
			goto again;
		}
		break;

	case SY_DIV: case SY_SLASH:

		/* convert (e / c) to (e * (1.0 / c)) */

		if (RCON(p) && RTY(p) == TW_DOUBLE) {
			RVR(p) = 1.0 / RVR(p);
			o = p->nd_op = SY_STAR;
			goto again;
		}
		break;

	case SY_STAR: case SY_PLUS:		/* commutative operators */

		/*  convert (e1 op (e2 op e3)) to ((e1 op e2) op e3) */

		if (RO(p) == o) {
			NODE *e1, *e2, *e3;
			e1 = p->nd.in.left;
			sp = p->nd.in.right;
			e2 = sp->nd.in.left;
			e3 = sp->nd.in.right;

			/* put together again */

			p->nd.in.left = sp;
			sp->nd.in.left = e1;
			sp->nd.in.right = e2;
			sp->nd_type = p->nd_type;
			p->nd.in.right = e3;
			p = nd_optim1(p);
		}

	 	/* convert ((e op c1) op c2) to (e op c3)  where c3 = c1 op c2 */
		
		if (RCON(p) && LO(p) == o && RCON(p->nd.in.left) &&
			nd_conval(o, p->nd.in.right, p->nd.in.left->nd.in.right))
		{
			RO(p->nd.in.left) = ND_FREE;
			LO(p) = ND_FREE;
			p->nd.in.left = p->nd.in.left->nd.in.left;
		}

		/*
		 * convert ((e1 op c) op e2) to ((e1 op e2) op c)
		 * this "bubbles up" the constant for possible folding later.
		 */

		if (LO(p) == o && RCON(p->nd.in.left)) {
			sp = p->nd.in.right;
			p->nd.in.right = p->nd.in.left->nd.in.right;
			p->nd.in.left->nd.in.right = sp;
		}
		break;

	}
	return(p);
}

/*
 * nd_optim2 eliminates addition/subtraction of zero, multiplication
 * by 1, replaces multiplication by powers of 2 with shifts.
 */

NODE *
nd_optim2(p)
	register NODE *p;
{
	register int i, o;

	/* skip leaf nodes */

	o = p->nd_op;
	if (ND_LEAF(o))
		return(p);
	
	/* do operands first */

	p->nd.in.left = nd_optim2(p->nd.in.left);
	if (p->nd.in.right)
		p->nd.in.right = nd_optim2(p->nd.in.right);

	switch(o) {

	case SY_PLUS:
	case SY_MINUS:
		if (RCON(p) && RTY(p) != TW_DOUBLE && RVI(p) == 0)
			return(nd_zapright(p));
		break;

	case SY_STAR:
		if (RCON(p) && RTY(p) != TW_DOUBLE &&
			(i = nd_ispow2(RVI(p))) >= 0)
		{
			if (i == 0)		/* multiplication by 1 */
				return(nd_zapright(p));
			p->nd_op = ND_LSHIFT;
			RTY(p) = TW_INT;
			RVI(p) = i;
		}
		break;

	}
	return(p);
}

/*
 * nd_ispow2(c) returns i such that 2^i == c, otherwise returns -1;
 */

int
nd_ispow2( c )
	register int c;
{
	register i;
	if (c <= 0 || c & (c-1))
		return(-1);
	for( i=0; c>1; ++i)
		c >>= 1;
	return(i);
}
