gnu1987/gnu1988/gcc-0.9/fold-const.c

/*@@ Fix lossage on folding division of big integers.  */

/*@@ This file should be rewritten to use an arbitary precision
  @@ representation for "struct tree_int_cst" and "struct tree_real_cst".
  @@ Perhaps the routines could also be used for bc/dc, and made a lib.
  @@ The routines that translate from the ap rep should
  @@ warn if precision et. al. is lost.
  @@ This would also make life easier when this technology is used
  @@ for cross-compilers.  */

/* Fold a constant sub-tree into a single node for C-compiler
   Copyright (C) 1987 Free Software Foundation, Inc.

This file is part of GNU CC.

GNU CC is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY.  No author or distributor
accepts responsibility to anyone for the consequences of using it
or for whether it serves any particular purpose or works at all,
unless he says so in writing.  Refer to the GNU CC General Public
License for full details.

Everyone is granted permission to copy, modify and redistribute
GNU CC, but only under the conditions described in the
GNU CC General Public License.   A copy of this license is
supposed to have been given to you along with GNU CC so you
can know your rights and responsibilities.  It should be in a
file named COPYING.  Among other things, the copyright notice
and this notice must be preserved on all copies.  */


/* There are only two entry points in this file:
   fold and combine.

   fold takes a tree as argument and returns a simplified tree.

   combine takes a tree code for an arithmetic operation
   and two operands that are trees for constant values
   and returns the result of the specified operation on those values,
   also as a tree.  */
   
#include <stdio.h>
#include "config.h"
#include "tree.h"

static void lshift_double ();
static void rshift_double ();
static void lrotate_double ();
static void rrotate_double ();

/* To do constant folding on INTEGER_CST nodes requires 64-bit arithmetic.
   We do that by representing the 64-bit integer as 8 shorts,
   with only 8 bits stored in each short, as a positive number.  */

/* Unpack a 64-bit integer into 8 shorts.
   LOW and HI are the integer, as two `int' pieces.
   SHORTS points to the array of shorts.  */

static void
encode (shorts, low, hi)
     short *shorts;
     int low, hi;
{
  shorts[0] = low & 0xff;
  shorts[1] = (low >> 8) & 0xff;
  shorts[2] = (low >> 16) & 0xff;
  shorts[3] = (low >> 24) & 0xff;
  shorts[4] = hi & 0xff;
  shorts[5] = (hi >> 8) & 0xff;
  shorts[6] = (hi >> 16) & 0xff;
  shorts[7] = (hi >> 24) & 0xff;
}

/* Pack an array of 8 shorts into a 64-bit integer.
   SHORTS points to the array of shorts.
   The integer is stored into *LOW and *HI as two `int' pieces.  */

static void
decode (shorts, low, hi)
     short *shorts;
     int *low, *hi;
{
  *low = (shorts[3] << 24) | (shorts[2] << 16) | (shorts[1] << 8) | shorts[0];
  *hi = (shorts[7] << 24) | (shorts[6] << 16) | (shorts[5] << 8) | shorts[4];
}

/* Zero out any bits in an unsigned integer that are supposed to be zero
   because they are beyond the precision of the integer's data type.  */

static void
truncate_unsigned (x)
     tree x;
{
  register int prec = TYPE_PRECISION (TREE_TYPE (x));

  if (TREE_CODE (TREE_TYPE (x)) == POINTER_TYPE)
    TREE_INT_CST_HIGH (x) = 0;
  else if (prec > HOST_BITS_PER_INT)
    {
      TREE_INT_CST_HIGH (x)
	&= ~((-1) << (prec - HOST_BITS_PER_INT));
    }
  else
    {
      TREE_INT_CST_HIGH (x) = 0;
      TREE_INT_CST_LOW (x)
	&= ~((-1) << prec);
    }
}

/* Add two 64-bit integers with 64-bit result.
   Each argument is given as two `int' pieces.
   One argument is L1 and H1; the other, L2 and H2.
   The value is stored as two `int' pieces in *LV and *HV.
   We use the 8-shorts representation internally.  */

static void
add_double (l1, h1, l2, h2, lv, hv)
     int l1, h1, l2, h2;
     int *lv, *hv;
{
  short arg1[8];
  short arg2[8];
  register int carry = 0;
  register int i;

  encode (arg1, l1, h1);
  encode (arg2, l2, h2);

  for (i = 0; i < 8; i++)
    {
      carry += arg1[i] + arg2[i];
      arg1[i] = carry & 0xff;
      carry >>= 8;
    }

  decode (arg1, lv, hv);
}

/* Negate a 64-bit integers with 64-bit result.
   The argument is given as two `int' pieces in L1 and H1.
   The value is stored as two `int' pieces in *LV and *HV.
   We use the 8-shorts representation internally.  */

static void
neg_double (l1, h1, lv, hv)
     int l1, h1;
     int *lv, *hv;
{
  if (l1 == 0)
    {
      *lv = 0;
      *hv = - h1;
    }
  else
    {
      *lv = - l1;
      *hv = ~ h1;
    }
}

/* Multiply two 64-bit integers with 64-bit result.
   Each argument is given as two `int' pieces.
   One argument is L1 and H1; the other, L2 and H2.
   The value is stored as two `int' pieces in *LV and *HV.
   We use the 8-shorts representation internally.  */

static void
mul_double (l1, h1, l2, h2, lv, hv)
     int l1, h1, l2, h2;
     int *lv, *hv;
{
  short arg1[8];
  short arg2[8];
  short prod[16];
  register int carry = 0;
  register int i, j, k;

  encode (arg1, l1, h1);
  encode (arg2, l2, h2);

  bzero (prod, sizeof prod);

  for (i = 0; i < 8; i++)
    for (j = 0; j < 8; j++)
      {
	k = i + j;
	carry = arg1[i] * arg2[j];
	while (carry)
	  {
	    carry += prod[k];
	    prod[k] = carry & 0xff;
	    carry >>= 8;
	    k++;
	  }
      }

  decode (prod, lv, hv);	/* @@decode ignores prod[8] -> prod[15] */
}

/* Shift the 64-bit integer in L1, H1 left by COUNT places
   keeping only PREC bits of result.
   Shift right if COUNT is negative.
   ARITH nonzero specifies arithmetic shifting; otherwise use logical shift.
   Store the value as two `int' pieces in *LV and *HV.  */

static void
lshift_double (l1, h1, count, prec, lv, hv, arith)
     int l1, h1, count, prec;
     int *lv, *hv;
     int arith;
{
  short arg1[8];
  register int i;
  register int carry = 0;

  if (count < 0)
    {
      rshift_double (l1, h1, - count, prec, lv, hv, arith);
      return;
    }

  encode (arg1, l1, h1);
  count &= (1 << prec) - 1;

  while (count > 0)
    {
      for (i = 0; i < 8; i++)
	{
	  carry += arg1[i] << 1;
	  arg1[i] = carry & 0xff;
	  carry >>= 8;
	}
      count--;
    }

  decode (arg1, lv, hv);
}

/* Shift the 64-bit integer in L1, H1 right by COUNT places
   keeping only PREC bits of result.  COUNT must be positive.
   ARITH nonzero specifies arithmetic shifting; otherwise use logical shift.
   Store the value as two `int' pieces in *LV and *HV.  */

static void
rshift_double (l1, h1, count, prec, lv, hv, arith)
     int l1, h1, count, prec;
     int *lv, *hv;
     int arith;
{
  short arg1[8];
  register int i;
  register int carry;

  encode (arg1, l1, h1);
  count &= (1 << prec) - 1;

  carry = arith && arg1[7] >> 7;
  while (count > 0)
    {
      for (i = 7; i >= 0; i--)
	{
	  carry <<= 8;
	  carry += arg1[i];
	  arg1[i] = (carry >> 1) & 0xff;
	}
      count--;
    }

  decode (arg1, lv, hv);
}

/* Rotate the 64-bit integer in L1, H1 left by COUNT places
   keeping only PREC bits of result.
   Rotate right if COUNT is negative.
   Store the value as two `int' pieces in *LV and *HV.  */

static void
lrotate_double (l1, h1, count, prec, lv, hv)
     int l1, h1, count, prec;
     int *lv, *hv;
{
  short arg1[8];
  register int i;
  register int carry;

  if (count < 0)
    {
      rrotate_double (l1, h1, - count, prec, lv, hv);
      return;
    }

  encode (arg1, l1, h1);
  count &= (1 << prec) - 1;

  carry = arg1[7] >> 7;
  while (count > 0)
    {
      for (i = 0; i < 8; i++)
	{
	  carry += arg1[i] << 1;
	  arg1[i] = carry & 0xff;
	  carry >>= 8;
	}
      count--;
    }

  decode (arg1, lv, hv);
}

/* ROtate the 64-bit integer in L1, H1 left by COUNT places
   keeping only PREC bits of result.  COUNT must be positive.
   Store the value as two `int' pieces in *LV and *HV.  */

static void
rrotate_double (l1, h1, count, prec, lv, hv)
     int l1, h1, count, prec;
     int *lv, *hv;
{
  short arg1[8];
  register int i;
  register int carry;

  encode (arg1, l1, h1);
  count &= (1 << prec) - 1;

  carry = arg1[0] & 1;
  while (count > 0)
    {
      for (i = 7; i >= 0; i--)
	{
	  carry <<= 8;
	  carry += arg1[i];
	  arg1[i] = (carry >> 1) & 0xff;
	}
      count--;
    }

  decode (arg1, lv, hv);
}

/* Divide 64 bit integer LNUM, HNUM by 64 bit integer LDEN, HDEN
   for a quotient (stored in *LQUO, *HQUO) and remainder (in *LREM, *HREM).
   CODE is a tree code for a kind of division, one of
   TRUNC_DIV_EXPR, FLOOR_DIV_EXPR, CEIL_DIV_EXPR and ROUND_DIV_EXPR.
   It controls how the quotient is rounded to a integer.
   UNS nonzero says do unsigned division.  */

static void
div_and_round_double (code, uns,
		      lnum, hnum, lden, hden, lquo, hquo, lrem, hrem)
     enum tree_code code;
     int uns;
     int lnum, hnum;		/* num == numerator == dividend */
     int lden, hden;		/* den == denominator == divisor */
     int *lquo, *hquo, *lrem, *hrem;
{
  int quo_neg = 0;
  short num[9], den[8], quo[8];	/* extra element for scaling.  */
  register int i, j, work;
  register int carry = 0;

  if ((hden == 0) && (lden == 0)) {
    *hquo = *lquo = *hrem = *lrem = 0;
    yyerror
      ("divide by 0 in constant folding - quotient and remainder set to 0.");
    return;
  }

  /* calculate quotient sign and convert operands to unsigned.  */
  if (!uns) 
    {
      if (hden < 0) 
	{
	  quo_neg = ~ quo_neg;
	  neg_double (lden, hden, &lden, &hden);
	}
      if (hnum < 0)
	{
	  quo_neg = ~ quo_neg;
	  neg_double (lnum, hnum, &lnum, &hnum);
	}
    }

  if (hnum == 0 && hden == 0)
    {				/* single precision */
      *hquo = *hrem = 0;
      *lquo = lnum / lden;	/* rounds toward zero since positive args */
      goto finish_up;
    }

  if (hnum == 0)
    {				/* trivial case: dividend < divisor */
      /* hden != 0 already checked.  */
      *hquo = *lquo = 0;
      *hrem = hnum;
      *lrem = lnum;
      goto finish_up;
    }

  bzero (quo, sizeof quo);

  bzero (num, sizeof num);	/* to zero 9th element */
  bzero (den, sizeof den);

  encode (num, lnum, hnum); 
  encode (den, lden, hden);

  if (hden == 0)
    {				/* simpler algorithm */
      /* hnum != 0 already checked.  */
      for (i = 7; i >= 0; i--)
	{
	  work = num[i] + (carry << 8);
	  quo[i] = work / lden;
	  carry = work % lden;
	}
    }
  else {			/* full double precision,
				   with thanks to Don Knuth's
				   "Semi-Numericial Algorithms".  */
#define BASE 256
    int quo_est, scale, num_hi_sig, den_hi_sig, quo_hi_sig;

    /* Find the highest non-zero divisor digit.  */
    for (i = 7; ; i--)
      if (den[i] != 0) {
	den_hi_sig = i;
	break;
      }
    for (i = 7; ; i--)
      if (num[i] != 0) {
	num_hi_sig = i;
	break;
      }
    quo_hi_sig = num_hi_sig - den_hi_sig + 1;

    /* Insure that the first digit of the divisor is at least BASE/2.
       This is required by the quotient digit estimation algorithm.  */

    scale = BASE / (den[den_hi_sig] + 1);
    if (scale > 1) {		/* scale divisor and dividend */
      carry = 0;
      for (i = 0; i <= 8; i++) {
	work = (num[i] * scale) + carry;
	num[i] = work & 0xff;
	carry = work >> 8;
	if (num[i] != 0) num_hi_sig = i;
      }
      carry = 0;
      for (i = 0; i <= 7; i++) {
	work = (den[i] * scale) + carry;
	den[i] = work & 0xff;
	carry = work >> 8;
	if (den[i] != 0) den_hi_sig = i;
      }
    }

    /* Main loop */
    for (i = quo_hi_sig; i > 0; i--) {
      /* quess the next quotient digit, quo_est, by dividing the first
	 two remaining dividend digits by the high order quotient digit.
	 quo_est is never low and is at most 2 high.  */

      int num_hi;		/* index of highest remaining dividend digit */

      num_hi = i + den_hi_sig;

      work = (num[num_hi] * BASE) + (num_hi ? 0 : num[num_hi - 1]);
      if (num[num_hi] != den[den_hi_sig]) {
	quo_est = work / den[den_hi_sig];
      }
      else {
	quo_est = BASE - 1;
      }

      /* refine quo_est so it's usually correct, and at most one high.   */
      while ((den[den_hi_sig - 1] * quo_est)
	     > (((work - (quo_est * den[den_hi_sig])) * BASE)
		 + ((num_hi - 1) ? 0 : num[num_hi - 2]))) {
	quo_est--;
      }

      /* try quo_est as the quotient digit, by multiplying the
         divisor by quo_est and subtracting from the remaining dividend.  */

      carry = 0;

      for (j = 0; j <= den_hi_sig; j++) {
	int digit;

	work = num[i + j] - (quo_est * den[j]) + carry;
	digit = work & 0xff;
	carry = work >> 8;
	if (digit < 0) {
	  digit += BASE;
	  carry--;
	}
	num[i + j] = digit;
      }

      /* if quo_est was high by one, then num[i] went negative and
	 we need to correct things.  */

      if (num[num_hi] < 0) {
	quo_est--;
	carry = 0;		/* add divisor back in */
	for (j = 0; j <= den_hi_sig; j++) {
	  work = num[i + j] + den[j] + carry;
	  if (work > BASE) {
	    work -= BASE;
	    carry = 1;
	  }
	  else {
	    carry = 0;
	  }
	  num[i + j] = work;
	}
	num [num_hi] += carry;
      }

      /* store the quotient digit.  */
      quo[i - 1] = quo_est;
    }
  }

  decode (quo, lquo, hquo);

 finish_up:
  /* if result is negative, make it so.  */
  if (quo_neg)
    neg_double (*lquo, *hquo, lquo, hquo);

  /* compute trial remainder:  rem = num - (quo * den)  */
  mul_double (*lquo, *hquo, lden, hden, lrem, hrem);
  neg_double (*lrem, *hrem, lrem, hrem);
  add_double (lnum, hnum, *lrem, *hrem, lrem, hrem);

  switch (code)
    {
    case TRUNC_DIV_EXPR:
    case TRUNC_MOD_EXPR:	/* round toward zero */
      return;

    case FLOOR_DIV_EXPR:
    case FLOOR_MOD_EXPR:	/* round toward negative infinity */
      if (quo_neg && (*lrem != 0 || *hrem != 0))   /* quo < 0 && rem != 0 */
	{
	  /* quo = quo - 1;  */
	  add_double (*lquo, *hquo, -1, -1, lquo, hquo);
	}
      else return;
      break;

    case CEIL_DIV_EXPR:
    case CEIL_MOD_EXPR:		/* round toward positive infinity */
      if ((uns || !quo_neg) && *lquo != 0 && *quo != 0 /* quo > 0 */
	  && (*lrem != 0 || *hrem != 0))	       /* && rem != 0 */
	{
	  add_double (*lquo, *hquo, 1, 0, lquo, hquo);
	}
      else return;
      break;
    
    case ROUND_DIV_EXPR:
    case ROUND_MOD_EXPR:	/* round to closest integer */
      {
	int labs_rem = *lrem, habs_rem = *hrem;
	int labs_den = lden, habs_den = hden, ltwice, htwice;

	/* get absolute values */
	if (*hrem < 0) neg_double(*lrem, *hrem, &labs_rem, &habs_rem);
	if (hden < 0) neg_double(lden, hden, &labs_den, &habs_den);

	/* if (2 * abs (lrem) >= abs (lden)) */
	mul_double(2, 0, labs_rem, habs_rem, &ltwice, &htwice);
	if (((unsigned) habs_den < (unsigned) htwice)
	    || (((unsigned) habs_den == (unsigned) htwice)
		&& ((unsigned) labs_den < (unsigned) ltwice)))
	  {
	    if (*hquo < 0)
	      /* quo = quo - 1;  */
	      add_double (*lquo, *hquo, -1, -1, lquo, hquo);
	    else
	      /* quo = quo + 1; */
	      add_double (*lquo, *hquo, 1, 0, lquo, hquo);
	  }
	else return;
      }
      break;

    default:
      abort ();
    }

  /* compute true remainder:  rem = num - (quo * den)  */
  mul_double (*lquo, *hquo, lden, hden, lrem, hrem);
  neg_double (&lrem, &hrem, lrem, hrem);
  add_double (lnum, hnum, &lrem, &hrem, lrem, hrem);
}

/* Split a tree IN into a constant and a variable part
   that could be combined with CODE to make IN.
   CODE must be a commutative arithmetic operation.
   Store the constant part into *CONP and the variable in &VARP.
   Return 1 if this was done; zero means the tree IN did not decompose
   this way.

   If CODE is PLUS_EXPR we also split trees that use MINUS_EXPR.
   Therefore, we must tell the caller whether the variable part
   was subtracted.  We do this by storing 1 or -1 into *VARSIGNP.
   The value stored is the coefficient for the variable term.
   The constant term we return should always be added;
   we negate it if necessary.  */

static int
split_tree (in, code, varp, conp, varsignp)
     tree in;
     enum tree_code code;
     tree *varp, *conp;
     int *varsignp;
{
  register tree outtype = TREE_TYPE (in);
  *varp = 0;
  *conp = 0;

  if (TREE_CODE (in) == NOP_EXPR)
    in = TREE_OPERAND (in, 0);

  if (TREE_CODE (in) == code
      || (TREE_CODE (TREE_TYPE (in)) != REAL_TYPE
	  /* We can associate addition and subtraction together
	     (even though the C standard doesn't say so)
	     for integers because the value is not affected.
	     For reals, the value might be affected, so we can't.  */
	  &&
	  ((code == PLUS_EXPR && TREE_CODE (in) == MINUS_EXPR)
	   || (code == MINUS_EXPR && TREE_CODE (in) == PLUS_EXPR))))
    {
      if (TREE_LITERAL (TREE_OPERAND (in, 0)))
	{
	  *conp = TREE_OPERAND (in, 0);
	  *varp = TREE_OPERAND (in, 1);
	  if (TREE_TYPE (*varp) != outtype)
	    *varp = convert (outtype, *varp);
	  *varsignp = (TREE_CODE (in) == MINUS_EXPR) ? -1 : 1;
	  return 1;
	}
      if (TREE_LITERAL (TREE_OPERAND (in, 1)))
	{
	  *conp = TREE_OPERAND (in, 1);
	  *varp = TREE_OPERAND (in, 0);
	  *varsignp = 1;
	  if (TREE_TYPE (*varp) != outtype)
	    *varp = convert (outtype, *varp);
	  if (TREE_CODE (in) == MINUS_EXPR)
	    *conp = combine (MINUS_EXPR, integer_zero_node, *conp);
	  return 1;
	}
    }
  return 0;
}

/* Combine two constants NUM and ARG2 under operation CODE
   to produce a new constant.
   We assume ARG1 and ARG2 have the same data type,
   or at least are the same kind of constant and the same machine mode.  */

tree
combine (code, arg1, arg2)
     enum tree_code code;
     register tree arg1, arg2;
{
  if (TREE_CODE (arg1) == INTEGER_CST)
    {
      register int int1l = TREE_INT_CST_LOW (arg1);
      register int int1h = TREE_INT_CST_HIGH (arg1);
      int int2l = TREE_INT_CST_LOW (arg2);
      int int2h = TREE_INT_CST_HIGH (arg2);
      int low, hi;
      int garbage;
      register tree t;
      int uns = type_unsigned_p (TREE_TYPE (arg1));

      switch (code)
	{
	case BIT_IOR_EXPR:
	  t = build_int_2 (int1l | int2l, int1h | int2h);
	  break;

	case BIT_XOR_EXPR:
	  t = build_int_2 (int1l ^ int2l, int1h ^ int2h);
	  break;

	case BIT_AND_EXPR:
	  t = build_int_2 (int1l & int2l, int1h & int2h);
	  break;

	case BIT_ANDTC_EXPR:
	  t = build_int_2 (int1l & ~int2l, int1h & ~int2h);
	  break;

	case RSHIFT_EXPR:
	  int2l = - int2l;
	case LSHIFT_EXPR:
	  lshift_double (int1l, int1h, int2l,
			 TYPE_PRECISION (TREE_TYPE (arg1)),
			 &low, &hi,
			 !uns);
	  t = build_int_2 (low, hi);
	  break;

	case RROTATE_EXPR:
	  int2l = - int2l;
	case LROTATE_EXPR:
	  lrotate_double (int1l, int1h, int2l,
			  TYPE_PRECISION (TREE_TYPE (arg1)),
			  &low, &hi);
	  t = build_int_2 (low, hi);
	  break;

	case PLUS_EXPR:
	  add_double (int1l, int1h, int2l, int2h, &low, &hi);
	  t = build_int_2 (low, hi);
	  break;

	case MINUS_EXPR:
	  neg_double (int2l, int2h, &int2l, &int2h);
	  add_double (int1l, int1h, int2l, int2h, &low, &hi);
	  t = build_int_2 (low, hi);
	  break;

	case MULT_EXPR:
	  mul_double (int1l, int1h, int2l, int2h, &low, &hi);
	  t = build_int_2 (low, hi);
	  break;

	case TRUNC_DIV_EXPR: case ROUND_DIV_EXPR: 
	case FLOOR_DIV_EXPR: case CEIL_DIV_EXPR:
	  div_and_round_double (code, uns, int1l, int1h, int2l, int2h,
				&low, &hi, &garbage, &garbage);
	  t = build_int_2 (low, hi);
	  break;

	case TRUNC_MOD_EXPR: case ROUND_MOD_EXPR: 
	case FLOOR_MOD_EXPR: case CEIL_MOD_EXPR:
	  div_and_round_double (code, uns, int1l, int1h, int2l, int2h,
				&garbage, &garbage, &low, &hi);
	  t = build_int_2 (low, hi);
	  break;

	case MIN_EXPR:
	case MAX_EXPR:
	  if (uns)
	    {
	      low = (((unsigned) int1h < (unsigned) int2h)
		     || (((unsigned) int1h == (unsigned) int2h)
			 && ((unsigned) int1l < (unsigned) int2l)));
	    }
	  else
	    {
	      low = ((int1h < int2h)
		     || ((int1h == int2h)
			 && ((unsigned) int1l < (unsigned) int2l)));
	    }
	  if (low == (code == MIN_EXPR))
	    t = build_int_2 (int1l, int1h);
	  else
	    t = build_int_2 (int2l, int2h);
	  break;

	default:
	  abort ();
	}
      TREE_TYPE (t) = TREE_TYPE (arg1);
      if (uns)
	truncate_unsigned (t);
      return t;
    }
  if (TREE_CODE (arg1) == REAL_CST)
    {
      register double d1 = TREE_REAL_CST (arg1);
      register double d2 = TREE_REAL_CST (arg2);
      register tree t;

      switch (code)
	{
	case PLUS_EXPR:
	  t = build_real (d1 + d2);
	  break;

	case MINUS_EXPR:
	  t = build_real (d1 - d2);
	  break;

	case MULT_EXPR:
	  t = build_real (d1 * d2);
	  break;

	case RDIV_EXPR:
	  if (d2 == 0)
	    return 0;

	  t = build_real (d1 / d2);
	  break;

	case MIN_EXPR:
	  if (d1 < d2)
	    t = build_real (d1);
	  t = build_real (d2);
	  break;

	case MAX_EXPR:
	  if (d1 > d2)
	    t = build_real (d1);
	  t = build_real (d2);
	  break;

	default:
	  abort ();
	}
      TREE_TYPE (t) = TREE_TYPE (arg1);
      return t;
    }
  if (TREE_CODE (arg1) == COMPLEX_CST)
    {
      register tree r1 = TREE_REALPART (arg1);
      register tree i1 = TREE_IMAGPART (arg1);
      register tree r2 = TREE_REALPART (arg2);
      register tree i2 = TREE_IMAGPART (arg2);
      register tree t;

      switch (code)
	{
	case PLUS_EXPR:
	  t = build_complex (combine (PLUS_EXPR, r1, r2),
			     combine (PLUS_EXPR, i1, i2));
	  break;

	case MINUS_EXPR:
	  t = build_complex (combine (MINUS_EXPR, r1, r2),
			     combine (MINUS_EXPR, i1, i2));
	  break;

	case MULT_EXPR:
	  t = build_complex (combine (MINUS_EXPR,
				      combine (MULT_EXPR, r1, r2),
				      combine (MULT_EXPR, i1, i2)),
			     combine (PLUS_EXPR,
				      combine (MULT_EXPR, r1, i2),
				      combine (MULT_EXPR, i1, r2)));
	  break;

	case RDIV_EXPR:
	  {
	    register tree magsquared
	      = combine (PLUS_EXPR,
			 combine (MULT_EXPR, r2, r2),
			 combine (MULT_EXPR, i2, i2));
	    t = build_complex (combine (RDIV_EXPR,
					combine (PLUS_EXPR,
						 combine (MULT_EXPR, r1, r2),
						 combine (MULT_EXPR, i1, i2)),
					magsquared),
			       combine (RDIV_EXPR,
					combine (MINUS_EXPR,
						 combine (MULT_EXPR, i1, r2),
						 combine (MULT_EXPR, r1, i2)),
					magsquared));
	  }
	  break;

	default:
	  abort ();
	}
      TREE_TYPE (t) = TREE_TYPE (arg1);
      return t;
    }
  return 0;
}

/* Given T, a tree representing type conversion of a constant,
   return a constant tree representing the result of conversion.  */

static tree
fold_convert (t)
     register tree t;
{
  register tree arg1 = TREE_OPERAND (t, 0);
  register tree type = TREE_TYPE (t);

  if (TREE_CODE (type) == POINTER_TYPE
      || TREE_CODE (type) == INTEGER_TYPE
      || TREE_CODE (type) == ENUMERAL_TYPE)
    {
      if (TREE_CODE (arg1) == INTEGER_CST)
	{
	  /* Given an integer constant, make new constant with new type,
	     appropriately sign-extended or truncated.  */
	  register int inprec;
	  register int outprec;

	  if (TREE_CODE (TREE_TYPE (arg1)) == POINTER_TYPE)
	    inprec = BITS_PER_WORD;
	  else
	    inprec = TYPE_PRECISION (TREE_TYPE (arg1));
	  if (TREE_CODE (type) == POINTER_TYPE)
	    outprec = BITS_PER_WORD;
	  else
	    outprec = TYPE_PRECISION (type);

	  t = build_int_2 (TREE_INT_CST_LOW (arg1),
			   TREE_INT_CST_HIGH (arg1));
	  TREE_TYPE (t) = type;
	  /* First zero out all bits not in the new type.  */
	  truncate_unsigned (t);

	  /* If desired type is signed, sign extend.  */
	  if (!type_unsigned_p (type)
	      && (outprec > HOST_BITS_PER_INT
		  ? TREE_INT_CST_HIGH (t)
		  & (1 << (outprec - HOST_BITS_PER_INT - 1))
		  : TREE_INT_CST_LOW (t) & (1 << (outprec - 1))))
	    {
	      /* Value is negative:
		 set to 1 all the undesired bits.  */
	      if (outprec > HOST_BITS_PER_INT)
		{
		  TREE_INT_CST_HIGH (t)
		    |= ((-1) << (outprec - HOST_BITS_PER_INT));
		}
	      else
		{
		  TREE_INT_CST_HIGH (t) = -1;
		  TREE_INT_CST_LOW (t)
		    |= ((-1) << outprec);
		}
	    }
	}
      else if (TREE_CODE (arg1) == REAL_CST)
	t = build_int_2 ((int) TREE_REAL_CST (arg1),
			 (int) (TREE_REAL_CST (arg1) / 0x10000 / 0x10000));
    }
  else if (TREE_CODE (type) == REAL_TYPE)
    {
      if (TREE_CODE (arg1) == INTEGER_CST)
	t = build_real_from_int_cst (arg1);
      else if (TREE_CODE (arg1) == REAL_CST)
	t = build_real (TREE_REAL_CST (arg1));
    }
  TREE_TYPE (t) = type;
  TREE_LITERAL (t) = 1;
  return t;
}

/* Perform constant folding and related simplification of EXPR.
   The related simplifications include x*1 => x, x*0 => 0, etc.,
   and application of the associative law.
   NOP_EXPR conversions may be removed freely (as long as we
   are careful not to change the C type of the overall expression)
   We cannot simplify through a CONVERT_EXPR, FIX_EXPR or FLOAT_EXPR,
   but we can constant-fold them if they have constant operands.  */

tree
fold (expr) 
     tree expr;
{
  register tree t = expr;
  register tree arg0, arg1;
  register enum tree_code code = TREE_CODE (t);
  register int kind;

  /* WINS will be nonzero when the switch is done
     if all operands are constant.

     LOSES will be nonzero when the switch is done
     if any operand is volatile.
     This inhibits optimizations such as  (foo () * 0) => 0.
     But identity-element optimizations such as
     (foo () * 1) => (foo ()) can be done even if LOSES is set.  */

  int wins = 1;
  int loses = 0;

  /* Return right away if already constant.  */
  if (TREE_LITERAL (t))
    {
      if (code == CONST_DECL)
	return DECL_INITIAL (t);
      return t;
    }
  
  kind = *tree_code_type[(int) code];
  if (kind == 'e' || kind == 'r')
    {
      register int len = tree_code_length[(int) code];
      register int i;
      for (i = 0; i < len; i++)
	{
	  if (TREE_CODE (TREE_OPERAND (t, i)) != INTEGER_CST
	      && TREE_CODE (TREE_OPERAND (t, i)) != REAL_CST)
	    /* Note that TREE_LITERAL isn't enough:
	       static var addresses are constant but we can't
	       do arithmetic on them.  */
	    wins = 0;
	  if (TREE_VOLATILE (TREE_OPERAND (t, i)))
	    loses = 1;
	}
      arg0 = TREE_OPERAND (t, 0);
      if (len > 1)
	arg1 = TREE_OPERAND (t, 1);
    }

  /* Now WINS and LOSES are set as described above,
     ARG0 is the first operand of EXPR,
     and ARG1 is the second operand (if it has more than one operand).  */

  switch (code)
    {
    case INTEGER_CST:
    case REAL_CST:
    case STRING_CST:
    case COMPLEX_CST:
    case CONSTRUCTOR:
      return t;

    case CONST_DECL:
      return fold (DECL_INITIAL (t));

    case NOP_EXPR:
    case FLOAT_EXPR:
    case CONVERT_EXPR:
    case FIX_ROUND_EXPR:
      if (!wins)
	{
	  TREE_LITERAL (t) = TREE_LITERAL (arg0);
	  return t;
	}
      return fold_convert (t);

    case RANGE_EXPR:
      TREE_LITERAL (t) = wins;
      return t;

    case NEGATE_EXPR:
      if (wins)
	{
	  if (TREE_CODE (arg0) == INTEGER_CST)
	    {
	      if (TREE_INT_CST_LOW (arg0) == 0)
		t = build_int_2 (0, - TREE_INT_CST_HIGH (arg0));
	      else
		t = build_int_2 (- TREE_INT_CST_LOW (arg0),
				 ~ TREE_INT_CST_HIGH (arg0));
	      if (type_unsigned_p (TREE_TYPE (expr)))
		truncate_unsigned (t);
	    }
	  else if (TREE_CODE (arg0) == REAL_CST)
	    t = build_real (- TREE_REAL_CST (arg0));
	  else if (TREE_CODE (arg0) == COMPLEX_CST)
	    t = build_complex (fold (build1 (NEGATE_EXPR, arg0)),
			       fold (build1 (NEGATE_EXPR, arg1)));
	  TREE_TYPE (t) = TREE_TYPE (expr);
	}
      return t;

    case ABS_EXPR:
      if (wins)
	{
	  if (TREE_CODE (arg0) == INTEGER_CST)
	    {
	      if (! type_unsigned_p (TREE_TYPE (expr))
		  || TREE_INT_CST_HIGH (arg0) < 0)
		{
		  if (TREE_INT_CST_LOW (arg0) == 0)
		    t = build_int_2 (0, - TREE_INT_CST_HIGH (arg0));
		  else
		    t = build_int_2 (- TREE_INT_CST_LOW (arg0),
				     ~ TREE_INT_CST_HIGH (arg0));
		}
	    }
	  else if (TREE_CODE (arg0) == REAL_CST)
	    {
	      if (TREE_REAL_CST (arg0) < 0)
		t = build_real (- TREE_REAL_CST (arg0));
	    }
	  TREE_TYPE (t) = TREE_TYPE (expr);
	}
      return t;

    case BIT_NOT_EXPR:
      if (wins)
	{
	  if (TREE_CODE (arg0) == INTEGER_CST)
	    t = build_int_2 (~ TREE_INT_CST_LOW (arg0),
			     ~ TREE_INT_CST_HIGH (arg0));
	  TREE_TYPE (t) = TREE_TYPE (expr);
	  if (type_unsigned_p (TREE_TYPE (t)))
	    truncate_unsigned (t);
	}
      return t;

    case PLUS_EXPR:
      if (integer_zerop (arg0))
	return arg1;
      if (integer_zerop (arg1))
	return arg0;
    associate:
      /* The varsign == -1 cases happen only for addition and subtraction.
	 It says that the arg that was split was really CON minus VAR.
	 The rest of the code applies to all associative operations.  */
      if (!wins)
	{
	  tree var, con, tem;
	  int varsign;
	  if (split_tree (arg0, code, &var, &con, &varsign))
	    {
	      if (varsign == -1)
		{
		  TREE_SET_CODE (t, MINUS_EXPR);
		  TREE_OPERAND (t, 1) = var;
		  tem = build2 (code, con, arg1);
		  TREE_TYPE (tem) = TREE_TYPE (t);
		  TREE_OPERAND (t, 0) = fold (tem);
		}
	      else
		{
		  tem = build2 (code, arg1, con);
		  TREE_TYPE (tem) = TREE_TYPE (t);
		  TREE_OPERAND (t, 1) = fold (tem);
		  TREE_OPERAND (t, 0) = var;
		}
	      return t;
	    }
	}
      else if (!wins)
	{
	  tree var, con, tem;
	  int varsign;
	  if (split_tree (arg1, code, &var, &con, &varsign))
	    {
	      if (varsign == -1)
		TREE_SET_CODE (t,
			       (code == PLUS_EXPR ? MINUS_EXPR : PLUS_EXPR));
	      tem = build2 (code, arg0, con);
	      TREE_TYPE (tem) = TREE_TYPE (t);
	      TREE_OPERAND (t, 0) = fold (tem);
	      TREE_OPERAND (t, 1) = var;
	      return t;
	    }
	}
    binary:
      {
	register tree t1 = NULL_TREE;
	if (wins)
	  t1 = combine (code, arg0, arg1);
	if (t1 != NULL_TREE) return t1;
	return t;
      }

    case MINUS_EXPR:
      if (integer_zerop (arg0))
	{
	  t = build1 (NEGATE_EXPR, arg1);
	  TREE_TYPE (t) = TREE_TYPE (expr);
	  return t;
	}
      if (integer_zerop (arg1))
	return arg0;
      /* Can't associate subtraction on floats in C.  */
      if (TREE_CODE (TREE_TYPE (expr)) == REAL_TYPE)
	goto binary;
      goto associate;

    case MULT_EXPR:
      if (!loses && integer_zerop (arg0))
	return arg0;
      if (!loses && integer_zerop (arg1))
	return arg1;
      if (integer_onep (arg0))
	return arg1;
      if (integer_onep (arg1))
	return arg0;
      goto associate;

    case BIT_IOR_EXPR:
      if (!loses && integer_all_onesp (arg0))
	return arg0;
      if (!loses && integer_all_onesp (arg1))
	return arg1;
    case BIT_XOR_EXPR:
      if (integer_zerop (arg0))
	return arg1;
      if (integer_zerop (arg1))
	return arg0;
      goto associate;

    case BIT_AND_EXPR:
      if (integer_all_onesp (arg0))
	return arg1;
      if (integer_all_onesp (arg1))
	return arg0;
      if (!loses && integer_zerop (arg0))
	return arg0;
      if (!loses && integer_zerop (arg1))
	return arg1;
      goto associate;

    case BIT_ANDTC_EXPR:
      if (integer_all_onesp (arg0))
	return arg1;
      if (integer_zerop (arg1))
	return arg0;
      if (!loses && integer_zerop (arg0))
	return arg0;
      if (!loses && integer_all_onesp (arg1))
	return combine (code, arg1, arg1);
      goto binary;

    case TRUNC_DIV_EXPR:
    case ROUND_DIV_EXPR:
    case FLOOR_DIV_EXPR:
    case CEIL_DIV_EXPR:
    case RDIV_EXPR:
      if (integer_onep (arg1))
	return arg0;
      goto binary;

    case CEIL_MOD_EXPR:
    case FLOOR_MOD_EXPR:
    case ROUND_MOD_EXPR:
    case TRUNC_MOD_EXPR:
      if (!loses && integer_onep (arg1))
	return combine (code, arg1, arg1);
      goto binary;

    case LSHIFT_EXPR:
    case RSHIFT_EXPR:
    case LROTATE_EXPR:
    case RROTATE_EXPR:
      if (integer_zerop (arg1))
	return arg0;
      goto binary;

    case MIN_EXPR: case MAX_EXPR:
      goto associate;

    case EQ_EXPR:
    case NE_EXPR:
      /* Compute a result for EQ, or return if cannot do so.  */
      if (TREE_CODE (arg0) == INTEGER_CST
	  && TREE_CODE (arg1) == INTEGER_CST)
	{
	  t = build_int_2
	    (TREE_INT_CST_LOW (arg0) == TREE_INT_CST_LOW (arg1)
	     && TREE_INT_CST_HIGH (arg0) == TREE_INT_CST_HIGH (arg1),
	     0);
	}
      else if (TREE_CODE (arg0) == REAL_CST
	       && TREE_CODE (arg1) == REAL_CST) {
	t = build_int_2 (TREE_REAL_CST (arg0) == TREE_REAL_CST (arg1),
			 0);
      }
      else
	return t;
      /* If we wanted NE_EXPR, invert the result.  */
      if (code == NE_EXPR)
	TREE_INT_CST_LOW (t) ^= 1;
      TREE_TYPE (t) = TREE_TYPE (expr);
      return t;

    case LT_EXPR:
    case GT_EXPR:
    case LE_EXPR:
    case GE_EXPR:
      /* To compute GT, swap the arguments and do LT.
	 To compute GE, do LT and invert the result.
	 To compute LE, swap the arguments, do LT and invert the result.  */
      if (code == LE_EXPR || code == GT_EXPR) {
	register tree temp = arg0;
	arg0 = arg1;
	arg1 = temp;
      }
      /* Compute a result for LT, or return if cannot do so.  */
      if (TREE_CODE (arg0) == INTEGER_CST
	  && TREE_CODE (arg1) == INTEGER_CST) {
	t = build_int_2 ((type_unsigned_p (TREE_TYPE (arg0))
			  ? INT_CST_LT_UNSIGNED (arg0, arg1)
			  : INT_CST_LT (arg0, arg1)),
			 0);
      }
      else if (TREE_CODE (arg0) == REAL_CST
	       && TREE_CODE (arg1) == REAL_CST) {
	  t = build_int_2 (TREE_REAL_CST (arg0) < TREE_REAL_CST (arg1), 0);
	}
      else
	return t;

      /* If we wanted ...-or-equal, invert the result.  */
      if (code == GE_EXPR || code == LE_EXPR)
	TREE_INT_CST_LOW (t) ^= 1;
      TREE_TYPE (t) = TREE_TYPE (expr);
      return t;

    COND_EXPR:
      if (TREE_LITERAL (arg0))
	return TREE_OPERAND (expr, (integer_zerop (arg0) ? 2 : 1));
      return t;

    default:
      return t;
    } /* switch (code) */
}