fold-const.c

早期freebsd实现

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

This file is part of GNU CC.

GNU CC is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2, or (at your option)
any later version.

GNU CC is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with GNU CC; see the file COPYING.  If not, write to
the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.  */

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

/*@@ This file should be rewritten to use an arbitrary 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.  */


/* The entry points in this file are fold, size_int and size_binop.

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

   size_binop takes a tree code for an arithmetic operation
   and two operands that are trees, and produces a tree for the
   result, assuming the type comes from `sizetype'.

   size_int takes an integer value, and creates a tree constant
   with type from `sizetype'.  */
   
#include <stdio.h>
#include <setjmp.h>
#include "config.h"
#include "flags.h"
#include "tree.h"

/* Handle floating overflow for `const_binop'.  */
static jmp_buf float_error;

int lshift_double ();
void rshift_double ();
void lrotate_double ();
void rrotate_double ();
static tree const_binop ();

#ifndef BRANCH_COST
#define BRANCH_COST 1
#endif

/* Yield nonzero if a signed left shift of A by B bits overflows.  */
#define left_shift_overflows(a, b)  ((a)  !=  ((a) << (b)) >> (b))

/* Yield nonzero if A and B have the same sign.  */
#define same_sign(a, b) ((a) ^ (b) >= 0)

/* Suppose A1 + B1 = SUM1, using 2's complement arithmetic ignoring overflow.
   Suppose A, B and SUM have the same respective signs as A1, B1, and SUM1.
   Then this yields nonzero if overflow occurred during the addition.
   Overflow occurs if A and B have the same sign, but A and SUM differ in sign.
   Use `^' to test whether signs differ, and `< 0' to isolate the sign.  */
#define overflow_sum_sign(a, b, sum) ((~((a) ^ (b)) & ((a) ^ (sum))) < 0)

/* To do constant folding on INTEGER_CST nodes requires two-word arithmetic.
   We do that by representing the two-word integer as MAX_SHORTS shorts,
   with only 8 bits stored in each short, as a positive number.  */

/* Unpack a two-word integer into MAX_SHORTS shorts.
   LOW and HI are the integer, as two `HOST_WIDE_INT' pieces.
   SHORTS points to the array of shorts.  */

static void
encode (shorts, low, hi)
     short *shorts;
     HOST_WIDE_INT low, hi;
{
  register int i;

  for (i = 0; i < MAX_SHORTS / 2; i++)
    {
      shorts[i] = (low >> (i * 8)) & 0xff;
      shorts[i + MAX_SHORTS / 2] = (hi >> (i * 8) & 0xff);
    }
}

/* Pack an array of MAX_SHORTS shorts into a two-word integer.
   SHORTS points to the array of shorts.
   The integer is stored into *LOW and *HI as two `HOST_WIDE_INT' pieces.  */

static void
decode (shorts, low, hi)
     short *shorts;
     HOST_WIDE_INT *low, *hi;
{
  register int i;
  HOST_WIDE_INT lv = 0, hv = 0;

  for (i = 0; i < MAX_SHORTS / 2; i++)
    {
      lv |= (HOST_WIDE_INT) shorts[i] << (i * 8);
      hv |= (HOST_WIDE_INT) shorts[i + MAX_SHORTS / 2] << (i * 8);
    }

  *low = lv, *hi = hv;
}

/* Make the integer constant T valid for its type
   by setting to 0 or 1 all the bits in the constant
   that don't belong in the type.  */

static void
force_fit_type (t)
     tree t;
{
  register int prec = TYPE_PRECISION (TREE_TYPE (t));

  if (TREE_CODE (TREE_TYPE (t)) == POINTER_TYPE)
    prec = POINTER_SIZE;

  /* First clear all bits that are beyond the type's precision.  */

  if (prec == 2 * HOST_BITS_PER_WIDE_INT)
    ;
  else if (prec > HOST_BITS_PER_WIDE_INT)
    {
      TREE_INT_CST_HIGH (t)
	&= ~((HOST_WIDE_INT) (-1) << (prec - HOST_BITS_PER_WIDE_INT));
    }
  else
    {
      TREE_INT_CST_HIGH (t) = 0;
      if (prec < HOST_BITS_PER_WIDE_INT)
	TREE_INT_CST_LOW (t) &= ~((HOST_WIDE_INT) (-1) << prec);
    }

  /* If it's a signed type and value's sign bit is set, extend the sign.  */

  if (! TREE_UNSIGNED (TREE_TYPE (t))
      && prec != 2 * HOST_BITS_PER_WIDE_INT
      && (prec > HOST_BITS_PER_WIDE_INT
	  ? (TREE_INT_CST_HIGH (t)
	     & ((HOST_WIDE_INT) 1 << (prec - HOST_BITS_PER_WIDE_INT - 1)))
	  : TREE_INT_CST_LOW (t) & ((HOST_WIDE_INT) 1 << (prec - 1))))
    {
      /* Value is negative:
	 set to 1 all the bits that are outside this type's precision.  */
      if (prec > HOST_BITS_PER_WIDE_INT)
	{
	  TREE_INT_CST_HIGH (t)
	    |= ((HOST_WIDE_INT) (-1) << (prec - HOST_BITS_PER_WIDE_INT));
	}
      else
	{
	  TREE_INT_CST_HIGH (t) = -1;
	  if (prec < HOST_BITS_PER_WIDE_INT)
	    TREE_INT_CST_LOW (t) |= ((HOST_WIDE_INT) (-1) << prec);
	}
    }
}

/* Add two doubleword integers with doubleword result.
   Each argument is given as two `HOST_WIDE_INT' pieces.
   One argument is L1 and H1; the other, L2 and H2.
   The value is stored as two `HOST_WIDE_INT' pieces in *LV and *HV.
   We use the 8-shorts representation internally.  */

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

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

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

  decode (arg1, lv, hv);
  return overflow_sum_sign (h1, h2, *hv);
}

/* Negate a doubleword integer with doubleword result.
   Return nonzero if the operation overflows, assuming it's signed.
   The argument is given as two `HOST_WIDE_INT' pieces in L1 and H1.
   The value is stored as two `HOST_WIDE_INT' pieces in *LV and *HV.
   We use the 8-shorts representation internally.  */

int
neg_double (l1, h1, lv, hv)
     HOST_WIDE_INT l1, h1;
     HOST_WIDE_INT *lv, *hv;
{
  if (l1 == 0)
    {
      *lv = 0;
      *hv = - h1;
      return same_sign (h1, *hv);
    }
  else
    {
      *lv = - l1;
      *hv = ~ h1;
      return 0;
    }
}

/* Multiply two doubleword integers with doubleword result.
   Return nonzero if the operation overflows, assuming it's signed.
   Each argument is given as two `HOST_WIDE_INT' pieces.
   One argument is L1 and H1; the other, L2 and H2.
   The value is stored as two `HOST_WIDE_INT' pieces in *LV and *HV.
   We use the 8-shorts representation internally.  */

int
mul_double (l1, h1, l2, h2, lv, hv)
     HOST_WIDE_INT l1, h1, l2, h2;
     HOST_WIDE_INT *lv, *hv;
{
  short arg1[MAX_SHORTS];
  short arg2[MAX_SHORTS];
  short prod[MAX_SHORTS * 2];
  register int carry = 0;
  register int i, j, k;
  HOST_WIDE_INT toplow, tophigh, neglow, neghigh;

  /* These cases are used extensively, arising from pointer combinations.  */
  if (h2 == 0)
    {
      if (l2 == 2)
	{
	  int overflow = left_shift_overflows (h1, 1);
	  unsigned HOST_WIDE_INT temp = l1 + l1;
	  *hv = (h1 << 1) + (temp < l1);
	  *lv = temp;
	  return overflow;
	}
      if (l2 == 4)
	{
	  int overflow = left_shift_overflows (h1, 2);
	  unsigned HOST_WIDE_INT temp = l1 + l1;
	  h1 = (h1 << 2) + ((temp < l1) << 1);
	  l1 = temp;
	  temp += temp;
	  h1 += (temp < l1);
	  *lv = temp;
	  *hv = h1;
	  return overflow;
	}
      if (l2 == 8)
	{
	  int overflow = left_shift_overflows (h1, 3);
	  unsigned HOST_WIDE_INT temp = l1 + l1;
	  h1 = (h1 << 3) + ((temp < l1) << 2);
	  l1 = temp;
	  temp += temp;
	  h1 += (temp < l1) << 1;
	  l1 = temp;
	  temp += temp;
	  h1 += (temp < l1);
	  *lv = temp;
	  *hv = h1;
	  return overflow;
	}
    }

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

  bzero (prod, sizeof prod);

  for (i = 0; i < MAX_SHORTS; i++)
    for (j = 0; j < MAX_SHORTS; 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);	/* This ignores
				   prod[MAX_SHORTS] -> prod[MAX_SHORTS*2-1] */

  /* Check for overflow by calculating the top half of the answer in full;
     it should agree with the low half's sign bit.  */
  decode (prod+MAX_SHORTS, &toplow, &tophigh);
  if (h1 < 0)
    {
      neg_double (l2, h2, &neglow, &neghigh);
      add_double (neglow, neghigh, toplow, tophigh, &toplow, &tophigh);
    }
  if (h2 < 0)
    {
      neg_double (l1, h1, &neglow, &neghigh);
      add_double (neglow, neghigh, toplow, tophigh, &toplow, &tophigh);
    }
  return (*hv < 0 ? ~(toplow & tophigh) : toplow | tophigh) != 0;
}

/* Shift the doubleword 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.
   Return nonzero if the arithmetic shift overflows, assuming it's signed.
   Store the value as two `HOST_WIDE_INT' pieces in *LV and *HV.  */

int
lshift_double (l1, h1, count, prec, lv, hv, arith)
     HOST_WIDE_INT l1, h1;
     int count, prec;
     HOST_WIDE_INT *lv, *hv;
     int arith;
{
  short arg1[MAX_SHORTS];
  register int i;
  register int carry, overflow;

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

  encode (arg1, l1, h1);

  if (count > prec)
    count = prec;

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

  decode (arg1, lv, hv);
  return overflow;
}

/* Shift the doubleword 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 `HOST_WIDE_INT' pieces in *LV and *HV.  */

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

  encode (arg1, l1, h1);

  if (count > prec)
    count = prec;

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

  decode (arg1, lv, hv);
}

/* Rotate the doubldword 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 `HOST_WIDE_INT' pieces in *LV and *HV.  */

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

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

  encode (arg1, l1, h1);

  if (count > prec)
    count = prec;

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

  decode (arg1, lv, hv);
}

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

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

  encode (arg1, l1, h1);

  if (count > prec)
    count = prec;

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

  decode (arg1, lv, hv);
}

/* Divide doubleword integer LNUM, HNUM by doubleword integer LDEN, HDEN