[PATCH] PR 168: More tree_expr_nonnegative_p improvements
Roger Sayle
roger@eyesopen.com
Thu Jun 12 18:22:00 GMT 2003
Many thanks to Joseph Myers for bringing it to my attention that
the long-standing PR middle-end/168 is caused by a defficiency of
GCC's tree_expr_nonnegative_p. This patch contains several small
improvements to tree_expr_nonnegative_p, which include recognizing
that floating point conversions and the ceil and floor builtins are
always sign preserving, that a zero extension is always non-negative,
and that sign extension of a non-negative operand is non-negative.
Additionally, to actually fix PR middle-end/168, it now knows that
zero_extend(x) + zero_extend(y) and zero_extend(x) * zero_extend(y)
are unsigned, iff the result isn't wide enough to overflow into the
sign bit of the result, using x+y is atmost max(bits(x),bits(y))+1
wide, and x*y is atmost bits(x)+bits(y) wide.
The following patch has been tested on i686-pc-linux-gnu with a full
"make bootstrap", all languages except treelang, and regression tested
with a top-level "make -k check" with no new failures.
Ok for mainline?
2003-06-12 Roger Sayle <roger@eyesopen.com>
PR middle-end/168
* fold-const.c (tree_expr_nonnegative_p): Handle addition
and multiplication of zero extensions, floating point division,
and integer<->fp, fp<->fp and zero extension conversions.
The built-in ceil and floor functions preserve signedness.
* gcc.dg/20030612-1.c: New test case.
Index: fold-const.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/fold-const.c,v
retrieving revision 1.260
diff -c -3 -p -r1.260 fold-const.c
*** fold-const.c 12 Jun 2003 12:52:59 -0000 1.260
--- fold-const.c 12 Jun 2003 14:38:31 -0000
*************** tree_expr_nonnegative_p (t)
*** 8022,8030 ****
return ! REAL_VALUE_NEGATIVE (TREE_REAL_CST (t));
case PLUS_EXPR:
! return FLOAT_TYPE_P (TREE_TYPE (t))
! && tree_expr_nonnegative_p (TREE_OPERAND (t, 0))
! && tree_expr_nonnegative_p (TREE_OPERAND (t, 1));
case MULT_EXPR:
if (FLOAT_TYPE_P (TREE_TYPE (t)))
--- 8022,8048 ----
return ! REAL_VALUE_NEGATIVE (TREE_REAL_CST (t));
case PLUS_EXPR:
! if (FLOAT_TYPE_P (TREE_TYPE (t)))
! return tree_expr_nonnegative_p (TREE_OPERAND (t, 0))
! && tree_expr_nonnegative_p (TREE_OPERAND (t, 1));
!
! /* zero_extend(x) + zero_extend(y) is non-negative is x and y are
! both unsigned and at atleast 2 bits shorter than the result. */
! if (TREE_CODE (TREE_TYPE (t)) == INTEGER_TYPE
! && TREE_CODE (TREE_OPERAND (t, 0)) == NOP_EXPR
! && TREE_CODE (TREE_OPERAND (t, 1)) == NOP_EXPR)
! {
! tree inner1 = TREE_TYPE (TREE_OPERAND (TREE_OPERAND (t, 0), 0));
! tree inner2 = TREE_TYPE (TREE_OPERAND (TREE_OPERAND (t, 1), 0));
! if (TREE_CODE (inner1) == INTEGER_TYPE && TREE_UNSIGNED (inner1)
! && TREE_CODE (inner2) == INTEGER_TYPE && TREE_UNSIGNED (inner2))
! {
! unsigned int prec = MAX (TYPE_PRECISION (inner1),
! TYPE_PRECISION (inner2)) + 1;
! return prec < TYPE_PRECISION (TREE_TYPE (t));
! }
! }
! break;
case MULT_EXPR:
if (FLOAT_TYPE_P (TREE_TYPE (t)))
*************** tree_expr_nonnegative_p (t)
*** 8035,8040 ****
--- 8053,8072 ----
return tree_expr_nonnegative_p (TREE_OPERAND (t, 0))
&& tree_expr_nonnegative_p (TREE_OPERAND (t, 1));
}
+
+ /* zero_extend(x) * zero_extend(y) is non-negative is x and y are
+ both unsigned and their total bits is shorter than the result. */
+ if (TREE_CODE (TREE_TYPE (t)) == INTEGER_TYPE
+ && TREE_CODE (TREE_OPERAND (t, 0)) == NOP_EXPR
+ && TREE_CODE (TREE_OPERAND (t, 1)) == NOP_EXPR)
+ {
+ tree inner1 = TREE_TYPE (TREE_OPERAND (TREE_OPERAND (t, 0), 0));
+ tree inner2 = TREE_TYPE (TREE_OPERAND (TREE_OPERAND (t, 1), 0));
+ if (TREE_CODE (inner1) == INTEGER_TYPE && TREE_UNSIGNED (inner1)
+ && TREE_CODE (inner2) == INTEGER_TYPE && TREE_UNSIGNED (inner2))
+ return TYPE_PRECISION (inner1) + TYPE_PRECISION (inner2)
+ < TYPE_PRECISION (TREE_TYPE (t));
+ }
return 0;
case TRUNC_DIV_EXPR:
*************** tree_expr_nonnegative_p (t)
*** 8042,8053 ****
case FLOOR_DIV_EXPR:
case ROUND_DIV_EXPR:
return tree_expr_nonnegative_p (TREE_OPERAND (t, 0))
! && tree_expr_nonnegative_p (TREE_OPERAND (t, 1));
case TRUNC_MOD_EXPR:
case CEIL_MOD_EXPR:
case FLOOR_MOD_EXPR:
case ROUND_MOD_EXPR:
return tree_expr_nonnegative_p (TREE_OPERAND (t, 0));
case COND_EXPR:
return tree_expr_nonnegative_p (TREE_OPERAND (t, 1))
&& tree_expr_nonnegative_p (TREE_OPERAND (t, 2));
--- 8074,8118 ----
case FLOOR_DIV_EXPR:
case ROUND_DIV_EXPR:
return tree_expr_nonnegative_p (TREE_OPERAND (t, 0))
! && tree_expr_nonnegative_p (TREE_OPERAND (t, 1));
!
case TRUNC_MOD_EXPR:
case CEIL_MOD_EXPR:
case FLOOR_MOD_EXPR:
case ROUND_MOD_EXPR:
return tree_expr_nonnegative_p (TREE_OPERAND (t, 0));
+
+ case RDIV_EXPR:
+ return tree_expr_nonnegative_p (TREE_OPERAND (t, 0))
+ && tree_expr_nonnegative_p (TREE_OPERAND (t, 1));
+
+ case NOP_EXPR:
+ {
+ tree inner_type = TREE_TYPE (TREE_OPERAND (t, 0));
+ tree outer_type = TREE_TYPE (t);
+
+ if (TREE_CODE (outer_type) == REAL_TYPE)
+ {
+ if (TREE_CODE (inner_type) == REAL_TYPE)
+ return tree_expr_nonnegative_p (TREE_OPERAND (t, 0));
+ if (TREE_CODE (inner_type) == INTEGER_TYPE)
+ {
+ if (TREE_UNSIGNED (inner_type))
+ return 1;
+ return tree_expr_nonnegative_p (TREE_OPERAND (t, 0));
+ }
+ }
+ else if (TREE_CODE (outer_type) == INTEGER_TYPE)
+ {
+ if (TREE_CODE (inner_type) == REAL_TYPE)
+ return tree_expr_nonnegative_p (TREE_OPERAND (t,0));
+ if (TREE_CODE (inner_type) == INTEGER_TYPE)
+ return TYPE_PRECISION (inner_type) < TYPE_PRECISION (outer_type)
+ && TREE_UNSIGNED (inner_type);
+ }
+ }
+ break;
+
case COND_EXPR:
return tree_expr_nonnegative_p (TREE_OPERAND (t, 1))
&& tree_expr_nonnegative_p (TREE_OPERAND (t, 2));
*************** tree_expr_nonnegative_p (t)
*** 8097,8102 ****
--- 8162,8173 ----
case BUILT_IN_ATAN:
case BUILT_IN_ATANF:
case BUILT_IN_ATANL:
+ case BUILT_IN_CEIL:
+ case BUILT_IN_CEILF:
+ case BUILT_IN_CEILL:
+ case BUILT_IN_FLOOR:
+ case BUILT_IN_FLOORF:
+ case BUILT_IN_FLOORL:
return tree_expr_nonnegative_p (TREE_VALUE (arglist));
case BUILT_IN_POW:
*************** tree_expr_nonnegative_p (t)
*** 8115,8124 ****
if (truth_value_p (TREE_CODE (t)))
/* Truth values evaluate to 0 or 1, which is nonnegative. */
return 1;
- else
- /* We don't know sign of `t', so be conservative and return false. */
- return 0;
}
}
/* Return true if `r' is known to be non-negative.
--- 8186,8195 ----
if (truth_value_p (TREE_CODE (t)))
/* Truth values evaluate to 0 or 1, which is nonnegative. */
return 1;
}
+
+ /* We don't know sign of `t', so be conservative and return false. */
+ return 0;
}
/* Return true if `r' is known to be non-negative.
/* Derived from PR middle-end/168. */
/* { dg-do compile } */
/* { dg-options "-W" } */
extern void foo ();
unsigned char uc;
unsigned short int usi;
unsigned int ui;
void bar()
{
if (uc + usi >= ui) /* { dg-bogus "between signed and unsigned" } */
foo ();
if (uc * usi >= ui) /* { dg-bogus "between signed and unsigned" } */
foo ();
}
Roger
--
Roger Sayle, E-mail: roger@eyesopen.com
OpenEye Scientific Software, WWW: http://www.eyesopen.com/
Suite 1107, 3600 Cerrillos Road, Tel: (+1) 505-473-7385
Santa Fe, New Mexico, 87507. Fax: (+1) 505-473-0833
More information about the Gcc-patches
mailing list