[patch] tree.c: Fix latent bugs in upper_bound_in_type and lower_bound_in_type.
Kazu Hirata
kazu@codesourcery.com
Fri Jul 8 14:01:00 GMT 2005
Hi,
Attached is a patch to fix latent bugs in upper_bound_in_type and
lower_bound_in_type that I discovered while working on PR 20139.
upper_bound_in_type and lower_bound_in_type calculate ranges of a
value of type INNER cast to type OUTER. For example, if we are
casting a 16-bit signed short to 32-bit unsigned int, the lower bound
of a resulting value would be 0. The upper bound would be 2^^32-1.
The problem with these two functions is that they do not handle all
cases correctly. The upper and lower bounds depend on several
factors.
- Do we have a widening cast?
- Is the outer type unsigned?
- Is the inner type unsigned?
- What are the precisions of the inner and outer types?
I worked out all the possibilities. Here is the table for
lower_bound_in_type.
widening? outer uns? inner uns? lower bound
-----------------------------------------------------------------
no no no -2^(OP-1) <- used to be -2^(IP-1)
no no yes -2^(OP-1) <- used to be -2^(IP-1)
no yes no 0
no yes yes 0
yes no no -2^(IP-1)
yes no yes 0
yes yes no 0
yes yes yes 0
where
widening?: (TREE_PRECISION (outer) > TREE_PRECISION (inner))
outer uns?: TREE_UNSIGNED (outer)
inner uns?: TREE_UNSIGNED (inner)
IP: TREE_PRECISION (inner)
PP: TREE_PRECISION (outer)
Similarly, for upper_bound_in_type.
widening? outer uns? inner uns? upper bound
-----------------------------------------------------------------
no no no 2^(OP-1)-1 <- used to be 2^(IP-1)
no no yes 2^(OP-1)-1 <- used to be 2^IP-1
no yes no 2^OP-1
no yes yes 2^OP-1
yes no no 2^(IP-1)-1
yes no yes 2^IP-1
yes yes no 2^OP-1 <- used to be 2^IP-1
yes yes yes 2^IP-1
For lower bound, I used a sequence of several "if" statements. For
upper bound, I implemented the table directly. A sequence of "if"
statements for the upper bound case would be too messy.
Unfortunately, I don't have any testcase that goes with this patch. I
couldn't trigger any of these with fold_widened_comparison. However,
once I check in a patch for PR 20139, the "yes yes no" case in
upper_bound_in_type will be important so that
gcc.c-torture/execute/pr21331.c won't regress, which is how I found
these latent bugs.
Tested on x86_64-pc-linux-gnu. OK to apply?
Kazu Hirata
2005-07-08 Kazu Hirata <kazu@codesourcery.com>
PR tree-optimization/22360
* tree.c (upper_bound_in_type): Fix calculations for casting
to a non-wider signed type and casting a signed value to a
wider unsigned type.
(lower_bound_in_type): Fix calculations for casting to a
non-wider signed type.
Index: tree.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree.c,v
retrieving revision 1.494
diff -c -d -p -r1.494 tree.c
*** tree.c 5 Jul 2005 17:50:08 -0000 1.494
--- tree.c 8 Jul 2005 04:44:22 -0000
*************** tree
*** 6417,6459 ****
upper_bound_in_type (tree outer, tree inner)
{
unsigned HOST_WIDE_INT lo, hi;
! unsigned bits = TYPE_PRECISION (inner);
! if (TYPE_UNSIGNED (outer) || TYPE_UNSIGNED (inner))
{
! /* Zero extending in these cases. */
! if (bits <= HOST_BITS_PER_WIDE_INT)
! {
! hi = 0;
! lo = (~(unsigned HOST_WIDE_INT) 0)
! >> (HOST_BITS_PER_WIDE_INT - bits);
! }
! else
! {
! hi = (~(unsigned HOST_WIDE_INT) 0)
! >> (2 * HOST_BITS_PER_WIDE_INT - bits);
! lo = ~(unsigned HOST_WIDE_INT) 0;
! }
}
else
{
! /* Sign extending in these cases. */
! if (bits <= HOST_BITS_PER_WIDE_INT)
! {
! hi = 0;
! lo = (~(unsigned HOST_WIDE_INT) 0)
! >> (HOST_BITS_PER_WIDE_INT - bits) >> 1;
! }
! else
! {
! hi = (~(unsigned HOST_WIDE_INT) 0)
! >> (2 * HOST_BITS_PER_WIDE_INT - bits) >> 1;
! lo = ~(unsigned HOST_WIDE_INT) 0;
! }
}
! return fold_convert (outer,
! build_int_cst_wide (inner, lo, hi));
}
/* Returns the smallest value obtainable by casting something in INNER type to
--- 6417,6480 ----
upper_bound_in_type (tree outer, tree inner)
{
unsigned HOST_WIDE_INT lo, hi;
! unsigned int det = 0;
! unsigned oprec = TYPE_PRECISION (outer);
! unsigned iprec = TYPE_PRECISION (inner);
! unsigned prec;
! /* Compute a unique number for every combination. */
! det |= (oprec > iprec) ? 4 : 0;
! det |= TYPE_UNSIGNED (outer) ? 2 : 0;
! det |= TYPE_UNSIGNED (inner) ? 1 : 0;
!
! /* Determine the exponent to use. */
! switch (det)
{
! case 0:
! case 1:
! /* oprec <= iprec, outer: signed, inner: don't care. */
! prec = oprec - 1;
! break;
! case 2:
! case 3:
! /* oprec <= iprec, outer: unsigned, inner: don't care. */
! prec = oprec;
! break;
! case 4:
! /* oprec > iprec, outer: signed, inner: signed. */
! prec = iprec - 1;
! break;
! case 5:
! /* oprec > iprec, outer: signed, inner: unsigned. */
! prec = iprec;
! break;
! case 6:
! /* oprec > iprec, outer: unsigned, inner: signed. */
! prec = oprec;
! break;
! case 7:
! /* oprec > iprec, outer: unsigned, inner: unsigned. */
! prec = iprec;
! break;
! default:
! gcc_unreachable ();
! }
!
! /* Compute 2^^prec - 1. */
! if (prec <= HOST_BITS_PER_WIDE_INT)
! {
! hi = 0;
! lo = ((~(unsigned HOST_WIDE_INT) 0)
! >> (HOST_BITS_PER_WIDE_INT - prec));
}
else
{
! hi = ((~(unsigned HOST_WIDE_INT) 0)
! >> (2 * HOST_BITS_PER_WIDE_INT - prec));
! lo = ~(unsigned HOST_WIDE_INT) 0;
}
! return build_int_cst_wide (outer, lo, hi);
}
/* Returns the smallest value obtainable by casting something in INNER type to
*************** tree
*** 6463,6485 ****
lower_bound_in_type (tree outer, tree inner)
{
unsigned HOST_WIDE_INT lo, hi;
! unsigned bits = TYPE_PRECISION (inner);
! if (TYPE_UNSIGNED (outer) || TYPE_UNSIGNED (inner))
lo = hi = 0;
- else if (bits <= HOST_BITS_PER_WIDE_INT)
- {
- hi = ~(unsigned HOST_WIDE_INT) 0;
- lo = (~(unsigned HOST_WIDE_INT) 0) << (bits - 1);
- }
else
{
! hi = (~(unsigned HOST_WIDE_INT) 0) << (bits - HOST_BITS_PER_WIDE_INT - 1);
! lo = 0;
}
! return fold_convert (outer,
! build_int_cst_wide (inner, lo, hi));
}
/* Return nonzero if two operands that are suitable for PHI nodes are
--- 6484,6522 ----
lower_bound_in_type (tree outer, tree inner)
{
unsigned HOST_WIDE_INT lo, hi;
! unsigned oprec = TYPE_PRECISION (outer);
! unsigned iprec = TYPE_PRECISION (inner);
! /* If OUTER type is unsigned, we can definitely cast 0 to OUTER type
! and obtain 0. */
! if (TYPE_UNSIGNED (outer)
! /* If we are widening something of an unsigned type, OUTER type
! contains all values of INNER type. In particular, both INNER
! and OUTER types have zero in common. */
! || (oprec > iprec && TYPE_UNSIGNED (inner)))
lo = hi = 0;
else
{
! /* If we are widening a signed type to another signed type, we
! want to obtain -2^^(iprec-1). If we are keeping the
! precision or narrowing to a signed type, we want to obtain
! -2^(oprec-1). */
! unsigned prec = oprec > iprec ? iprec : oprec;
!
! if (prec <= HOST_BITS_PER_WIDE_INT)
! {
! hi = ~(unsigned HOST_WIDE_INT) 0;
! lo = (~(unsigned HOST_WIDE_INT) 0) << (prec - 1);
! }
! else
! {
! hi = ((~(unsigned HOST_WIDE_INT) 0)
! << (prec - HOST_BITS_PER_WIDE_INT - 1));
! lo = 0;
! }
}
! return build_int_cst_wide (outer, lo, hi);
}
/* Return nonzero if two operands that are suitable for PHI nodes are
More information about the Gcc-patches
mailing list