* [PATCH][PING] Teach VRP about range checks
@ 2008-03-20 15:32 Richard Guenther
2008-03-28 4:15 ` Diego Novillo
0 siblings, 1 reply; 6+ messages in thread
From: Richard Guenther @ 2008-03-20 15:32 UTC (permalink / raw)
To: gcc-patches; +Cc: dnovillo
This (old) patch teaches VRP about (anti-)range checks written like
(unsigned)a + CST cmp CST which are the canonical form of
(a < 5) || (a > 10) and (a > 5) && (a < 10) and produced for example
by fold (if not by a human).
The previous posting of this patch was a year ago
http://gcc.gnu.org/ml/gcc-patches/2007-02/msg00489.html
and Diego had some complaints about the added complexity but the
thread died down without any conclusion.
Still recognizing (anti-)range checks in VRP seems like a natural
thing to do and so I am pushing this patch (and shortly some followups)
again. It is badly needed to be able to optimize range checks as
emitted for example by the Ada frontend.
The only change compared to the previous posting is that we have
to deal with the funny overflow infinities that VRP got, where
in the Ada case (I recognized this while building the RTS) we
are now able to extract ~[min,max] ranges for integer subtypes
(that is, a value is outside of the range of valid values), but
the verification code barfs on that. This is fixed by for
sub-types using the underlying type to determine what is min/max
and for not handling subtypes in the special overflow code (no
arithmetic is ever performed on these types). In fact the
rule that ~[min,max] isn't a useful range is not true for
subtypes. This part is in the separate first patch.
Bootstrapped and tested on x86_64-unknown-linux-gnu, ok for mainline?
Measurements with the statistics patch infrastructure show that
with this patch for a make all-gcc in gcc/ we do 194 more
transformations from vrp (Copies propagated, Constants propagated,
Predicates folded, jump threaded).
Thanks,
Richard.
2008-03-20 Richard Guenther <rguenther@suse.de>
* tree-vrp.c (needs_overflow_infinity): Integer sub-types
do not need overflow infinities.
(vrp_val_is_max): The extreme values of integer sub-types
are those of the base type.
(vrp_val_is_min): Likewise.
Index: trunk/gcc/tree-vrp.c
===================================================================
*** trunk.orig/gcc/tree-vrp.c 2008-03-20 14:11:42.000000000 +0100
--- trunk/gcc/tree-vrp.c 2008-03-20 14:25:52.000000000 +0100
*************** static int *vr_phi_edge_counts;
*** 112,118 ****
static inline bool
needs_overflow_infinity (const_tree type)
{
! return INTEGRAL_TYPE_P (type) && !TYPE_OVERFLOW_WRAPS (type);
}
/* Return whether TYPE can support our overflow infinity
--- 112,122 ----
static inline bool
needs_overflow_infinity (const_tree type)
{
! return (INTEGRAL_TYPE_P (type)
! && !TYPE_OVERFLOW_WRAPS (type)
! /* Integer sub-types never overflow as they are never
! operands of arithmetic operators. */
! && !(TREE_TYPE (type) && TREE_TYPE (type) != type));
}
/* Return whether TYPE can support our overflow infinity
*************** avoid_overflow_infinity (tree val)
*** 234,240 ****
static inline bool
vrp_val_is_max (const_tree val)
{
! tree type_max = TYPE_MAX_VALUE (TREE_TYPE (val));
return (val == type_max
|| (type_max != NULL_TREE
--- 238,249 ----
static inline bool
vrp_val_is_max (const_tree val)
{
! tree type_max, type = TREE_TYPE (val);
!
! /* For integer sub-types the values for the base type are relevant. */
! if (TREE_TYPE (type))
! type = TREE_TYPE (type);
! type_max = TYPE_MAX_VALUE (type);
return (val == type_max
|| (type_max != NULL_TREE
*************** vrp_val_is_max (const_tree val)
*** 247,253 ****
static inline bool
vrp_val_is_min (const_tree val)
{
! tree type_min = TYPE_MIN_VALUE (TREE_TYPE (val));
return (val == type_min
|| (type_min != NULL_TREE
--- 256,267 ----
static inline bool
vrp_val_is_min (const_tree val)
{
! tree type_min, type = TREE_TYPE (val);
!
! /* For integer sub-types the values for the base type are relevant. */
! if (TREE_TYPE (type))
! type = TREE_TYPE (type);
! type_min = TYPE_MIN_VALUE (type);
return (val == type_min
|| (type_min != NULL_TREE
2008-03-20 Richard Guenther <rguenther@suse.de>
PR tree-optimization/30317
PR tree-optimization/30911
PR tree-optimization/34793
* tree-vrp.c (set_value_range_auto): New function.
(struct assert_locus_d): New member EXPR.
(register_new_assert_for): Add EXPR parameter to support
ASSERT_EXPR <name, expr OP limit>.
(register_edge_assert_for_1): Adjust callers.
(find_assert_locations): Likewise.
(process_assert_insertions_for): Build condition from
expression.
(extract_range_from_assert): Handle ASSERT_EXPRs
of the form ASSERT_EXPR <name, expr OP limit>.
(register_edge_assert_for_2): New helper registering
asserts for comparisons. Recognize range tests of the form
(unsigned)i - CST1 OP CST2.
(register_edge_assert_for_1): Use it.
(register_edge_assert_for): Likewise.
* gcc.dg/tree-ssa/vrp35.c: New testcase.
* gcc.dg/tree-ssa/vrp36.c: Likewise.
* gcc.dg/tree-ssa/vrp37.c: Likewise.
Index: gcc/tree-vrp.c
===================================================================
*** gcc/tree-vrp.c.orig 2008-03-19 14:48:15.000000000 +0100
--- gcc/tree-vrp.c 2008-03-20 13:31:12.000000000 +0100
*************** struct assert_locus_d
*** 71,76 ****
--- 71,79 ----
/* Value being compared against. */
tree val;
+ /* Expression to compare. */
+ tree expr;
+
/* Next node in the linked list. */
struct assert_locus_d *next;
};
*************** nonnull_arg_p (const_tree arg)
*** 300,305 ****
--- 303,320 ----
}
+ /* Set value range VR to VR_VARYING. */
+
+ static inline void
+ set_value_range_to_varying (value_range_t *vr)
+ {
+ vr->type = VR_VARYING;
+ vr->min = vr->max = NULL_TREE;
+ if (vr->equiv)
+ bitmap_clear (vr->equiv);
+ }
+
+
/* Set value range VR to {T, MIN, MAX, EQUIV}. */
static void
*************** set_value_range (value_range_t *vr, enum
*** 352,375 ****
}
! /* Copy value range FROM into value range TO. */
! static inline void
! copy_value_range (value_range_t *to, value_range_t *from)
{
! set_value_range (to, from->type, from->min, from->max, from->equiv);
! }
! /* Set value range VR to VR_VARYING. */
static inline void
! set_value_range_to_varying (value_range_t *vr)
{
! vr->type = VR_VARYING;
! vr->min = vr->max = NULL_TREE;
! if (vr->equiv)
! bitmap_clear (vr->equiv);
}
/* Set value range VR to a single value. This function is only called
--- 367,418 ----
}
! /* Set value range VR to {T, MIN, MAX, EQUIV}. Adjust T, MIN and MAX
! treating [MAX, MIN] as anti-range and ~[MAX, MIN] as range when
! possible. Fall back to varying in corner cases. */
! static void
! set_value_range_auto (value_range_t *vr, enum value_range_type t, tree min,
! tree max, bitmap equiv)
{
! tree one, tmp;
+ if ((t != VR_RANGE
+ && t != VR_ANTI_RANGE)
+ || TREE_CODE (min) != INTEGER_CST
+ || TREE_CODE (max) != INTEGER_CST
+ || !tree_int_cst_lt (max, min))
+ {
+ set_value_range (vr, t, min, max, equiv);
+ return;
+ }
! /* Wrong order for min and max, to swap them and the VR type we need
! to adjust them. */
! one = build_int_cst (TREE_TYPE (min), 1);
! tmp = int_const_binop (PLUS_EXPR, max, one, 0);
! max = int_const_binop (MINUS_EXPR, min, one, 0);
! min = tmp;
!
! /* There's one corner case, if we had [C+1, C] before we now have
! that again. But this represents an empty value range, so drop
! to varying in this case. */
! if (tree_int_cst_lt (max, min))
! {
! set_value_range_to_varying (vr);
! return;
! }
!
! t = t == VR_RANGE ? VR_ANTI_RANGE : VR_RANGE;
! set_value_range (vr, t, min, max, equiv);
! }
!
! /* Copy value range FROM into value range TO. */
static inline void
! copy_value_range (value_range_t *to, value_range_t *from)
{
! set_value_range (to, from->type, from->min, from->max, from->equiv);
}
/* Set value range VR to a single value. This function is only called
*************** extract_range_from_assert (value_range_t
*** 1101,1120 ****
gcc_assert (COMPARISON_CLASS_P (cond));
/* Find VAR in the ASSERT_EXPR conditional. */
! if (var == TREE_OPERAND (cond, 0))
{
/* If the predicate is of the form VAR COMP LIMIT, then we just
take LIMIT from the RHS and use the same comparison code. */
- limit = TREE_OPERAND (cond, 1);
cond_code = TREE_CODE (cond);
}
else
{
/* If the predicate is of the form LIMIT COMP VAR, then we need
to flip around the comparison code to create the proper range
for VAR. */
- limit = TREE_OPERAND (cond, 0);
cond_code = swap_tree_comparison (TREE_CODE (cond));
}
limit = avoid_overflow_infinity (limit);
--- 1144,1167 ----
gcc_assert (COMPARISON_CLASS_P (cond));
/* Find VAR in the ASSERT_EXPR conditional. */
! if (var == TREE_OPERAND (cond, 0)
! || TREE_CODE (TREE_OPERAND (cond, 0)) == PLUS_EXPR
! || TREE_CODE (TREE_OPERAND (cond, 0)) == NOP_EXPR)
{
/* If the predicate is of the form VAR COMP LIMIT, then we just
take LIMIT from the RHS and use the same comparison code. */
cond_code = TREE_CODE (cond);
+ limit = TREE_OPERAND (cond, 1);
+ cond = TREE_OPERAND (cond, 0);
}
else
{
/* If the predicate is of the form LIMIT COMP VAR, then we need
to flip around the comparison code to create the proper range
for VAR. */
cond_code = swap_tree_comparison (TREE_CODE (cond));
+ limit = TREE_OPERAND (cond, 0);
+ cond = TREE_OPERAND (cond, 1);
}
limit = avoid_overflow_infinity (limit);
*************** extract_range_from_assert (value_range_t
*** 1158,1165 ****
instance, ASSERT_EXPR <x_2, x_2 <= b_4>. If b_4 is ~[2, 10],
then b_4 takes on the ranges [-INF, 1] and [11, +INF]. There is
no single range for x_2 that could describe LE_EXPR, so we might
! as well build the range [b_4, +INF] for it. */
! if (cond_code == EQ_EXPR)
{
enum value_range_type range_type;
--- 1205,1244 ----
instance, ASSERT_EXPR <x_2, x_2 <= b_4>. If b_4 is ~[2, 10],
then b_4 takes on the ranges [-INF, 1] and [11, +INF]. There is
no single range for x_2 that could describe LE_EXPR, so we might
! as well build the range [b_4, +INF] for it.
! One special case we handle is extracting a range from a
! range test encoded as (unsigned)var + CST <= limit. */
! if (TREE_CODE (cond) == NOP_EXPR
! || TREE_CODE (cond) == PLUS_EXPR)
! {
! tree cst2 = NULL_TREE;
!
! if (TREE_CODE (cond) == PLUS_EXPR)
! {
! min = TREE_OPERAND (cond, 1);
! cst2 = fold_build1 (NEGATE_EXPR, TREE_TYPE (min), min);
! min = fold_convert (TREE_TYPE (var), cst2);
! cond = TREE_OPERAND (cond, 0);
! }
! else
! min = build_int_cst (TREE_TYPE (var), 0);
!
! if (cst2 != NULL_TREE)
! max = int_const_binop (PLUS_EXPR, limit, min, 0);
! else
! max = limit;
! max = fold_convert (TREE_TYPE (var), max);
!
! /* We can transform a max, min range to an anti-range or
! vice-versa. Use set_value_range_auto which does this for us. */
! if (cond_code == LE_EXPR)
! set_value_range_auto (vr_p, VR_RANGE, min, max, vr_p->equiv);
! else if (cond_code == GT_EXPR)
! set_value_range_auto (vr_p, VR_ANTI_RANGE, min, max, vr_p->equiv);
! else
! gcc_unreachable ();
! }
! else if (cond_code == EQ_EXPR)
{
enum value_range_type range_type;
*************** debug_all_asserts (void)
*** 3387,3395 ****
/* If NAME doesn't have an ASSERT_EXPR registered for asserting
! 'NAME COMP_CODE VAL' at a location that dominates block BB or
E->DEST, then register this location as a possible insertion point
! for ASSERT_EXPR <NAME, NAME COMP_CODE VAL>.
BB, E and SI provide the exact insertion point for the new
ASSERT_EXPR. If BB is NULL, then the ASSERT_EXPR is to be inserted
--- 3466,3474 ----
/* If NAME doesn't have an ASSERT_EXPR registered for asserting
! 'EXPR COMP_CODE VAL' at a location that dominates block BB or
E->DEST, then register this location as a possible insertion point
! for ASSERT_EXPR <NAME, EXPR COMP_CODE VAL>.
BB, E and SI provide the exact insertion point for the new
ASSERT_EXPR. If BB is NULL, then the ASSERT_EXPR is to be inserted
*************** debug_all_asserts (void)
*** 3398,3404 ****
must not be NULL. */
static void
! register_new_assert_for (tree name,
enum tree_code comp_code,
tree val,
basic_block bb,
--- 3477,3483 ----
must not be NULL. */
static void
! register_new_assert_for (tree name, tree expr,
enum tree_code comp_code,
tree val,
basic_block bb,
*************** register_new_assert_for (tree name,
*** 3452,3458 ****
{
if (loc->comp_code == comp_code
&& (loc->val == val
! || operand_equal_p (loc->val, val, 0)))
{
/* If the assertion NAME COMP_CODE VAL has already been
registered at a basic block that dominates DEST_BB, then
--- 3531,3539 ----
{
if (loc->comp_code == comp_code
&& (loc->val == val
! || operand_equal_p (loc->val, val, 0))
! && (loc->expr == expr
! || operand_equal_p (loc->expr, expr, 0)))
{
/* If the assertion NAME COMP_CODE VAL has already been
registered at a basic block that dominates DEST_BB, then
*************** register_new_assert_for (tree name,
*** 3499,3504 ****
--- 3580,3586 ----
n->si = si;
n->comp_code = comp_code;
n->val = val;
+ n->expr = expr;
n->next = NULL;
if (last_loc)
*************** extract_code_and_val_from_cond (tree nam
*** 3587,3592 ****
--- 3669,3762 ----
return true;
}
+ /* Try to register an edge assertion for SSA name NAME on edge E for
+ the condition COND contributing to the conditional jump pointed to by BSI.
+ Invert the condition COND if INVERT is true.
+ Return true if an assertion for NAME could be registered. */
+
+ static bool
+ register_edge_assert_for_2 (tree name, edge e, block_stmt_iterator bsi,
+ tree cond, bool invert)
+ {
+ tree val;
+ enum tree_code comp_code;
+ bool retval = false;
+
+ if (!extract_code_and_val_from_cond (name, cond, invert, &comp_code, &val))
+ return false;
+
+ /* Only register an ASSERT_EXPR if NAME was found in the sub-graph
+ reachable from E. */
+ if (TEST_BIT (found_in_subgraph, SSA_NAME_VERSION (name))
+ && !has_single_use (name))
+ {
+ register_new_assert_for (name, name, comp_code, val, NULL, e, bsi);
+ retval = true;
+ }
+
+ /* In the case of NAME <= CST and NAME being defined as
+ NAME = (unsigned) NAME2 + CST2 we can assert NAME2 >= -CST2
+ and NAME2 <= CST - CST2. We can do the same for NAME > CST.
+ This catches range and anti-range tests. */
+ if ((comp_code == LE_EXPR
+ || comp_code == GT_EXPR)
+ && TREE_CODE (val) == INTEGER_CST
+ && TYPE_UNSIGNED (TREE_TYPE (val)))
+ {
+ tree def_stmt = SSA_NAME_DEF_STMT (name);
+ tree cst2 = NULL_TREE, name2 = NULL_TREE;
+
+ /* Extract CST2 from the (optional) addition. */
+ if (TREE_CODE (def_stmt) == GIMPLE_MODIFY_STMT
+ && TREE_CODE (GIMPLE_STMT_OPERAND (def_stmt, 1)) == PLUS_EXPR)
+ {
+ name2 = TREE_OPERAND (GIMPLE_STMT_OPERAND (def_stmt, 1), 0);
+ cst2 = TREE_OPERAND (GIMPLE_STMT_OPERAND (def_stmt, 1), 1);
+ if (TREE_CODE (name2) == SSA_NAME
+ && TREE_CODE (cst2) == INTEGER_CST)
+ def_stmt = SSA_NAME_DEF_STMT (name2);
+ }
+
+ /* Extract NAME2 from the (optional) cast. */
+ if (TREE_CODE (def_stmt) == GIMPLE_MODIFY_STMT
+ && TREE_CODE (GIMPLE_STMT_OPERAND (def_stmt, 1)) == NOP_EXPR)
+ name2 = TREE_OPERAND (GIMPLE_STMT_OPERAND (def_stmt, 1), 0);
+
+ if (name2 != NULL_TREE
+ && TREE_CODE (name2) == SSA_NAME
+ && (cst2 == NULL_TREE
+ || TREE_CODE (cst2) == INTEGER_CST)
+ && TREE_CODE (TREE_TYPE (name2)) == INTEGER_TYPE
+ && TEST_BIT (found_in_subgraph, SSA_NAME_VERSION (name2))
+ && !has_single_use (name2))
+ {
+ tree tmp;
+
+ /* Build an expression for the range test. */
+ tmp = name2;
+ if (TREE_TYPE (name) != TREE_TYPE (name2))
+ tmp = build1 (NOP_EXPR, TREE_TYPE (name), tmp);
+ if (cst2 != NULL_TREE)
+ tmp = build2 (PLUS_EXPR, TREE_TYPE (name), tmp, cst2);
+
+ if (dump_file)
+ {
+ fprintf (dump_file, "Adding assert for ");
+ print_generic_expr (dump_file, name2, 0);
+ fprintf (dump_file, " from ");
+ print_generic_expr (dump_file, tmp, 0);
+ fprintf (dump_file, "\n");
+ }
+
+ register_new_assert_for (name2, tmp, comp_code, val, NULL, e, bsi);
+
+ retval = true;
+ }
+ }
+
+ return retval;
+ }
+
/* OP is an operand of a truth value expression which is known to have
a particular value. Register any asserts for OP and for any
operands in OP's defining statement.
*************** register_edge_assert_for_1 (tree op, enu
*** 3614,3620 ****
if (!has_single_use (op))
{
val = build_int_cst (TREE_TYPE (op), 0);
! register_new_assert_for (op, code, val, NULL, e, bsi);
retval = true;
}
--- 3784,3790 ----
if (!has_single_use (op))
{
val = build_int_cst (TREE_TYPE (op), 0);
! register_new_assert_for (op, op, code, val, NULL, e, bsi);
retval = true;
}
*************** register_edge_assert_for_1 (tree op, enu
*** 3633,3658 ****
tree op0 = TREE_OPERAND (rhs, 0);
tree op1 = TREE_OPERAND (rhs, 1);
! /* Conditionally register an assert for each SSA_NAME in the
! comparison. */
! if (TREE_CODE (op0) == SSA_NAME
! && !has_single_use (op0)
! && extract_code_and_val_from_cond (op0, rhs,
! invert, &code, &val))
! {
! register_new_assert_for (op0, code, val, NULL, e, bsi);
! retval = true;
! }
!
! /* Similarly for the second operand of the comparison. */
! if (TREE_CODE (op1) == SSA_NAME
! && !has_single_use (op1)
! && extract_code_and_val_from_cond (op1, rhs,
! invert, &code, &val))
! {
! register_new_assert_for (op1, code, val, NULL, e, bsi);
! retval = true;
! }
}
else if ((code == NE_EXPR
&& (TREE_CODE (rhs) == TRUTH_AND_EXPR
--- 3803,3812 ----
tree op0 = TREE_OPERAND (rhs, 0);
tree op1 = TREE_OPERAND (rhs, 1);
! if (TREE_CODE (op0) == SSA_NAME)
! retval |= register_edge_assert_for_2 (op0, e, bsi, rhs, invert);
! if (TREE_CODE (op1) == SSA_NAME)
! retval |= register_edge_assert_for_2 (op1, e, bsi, rhs, invert);
}
else if ((code == NE_EXPR
&& (TREE_CODE (rhs) == TRUTH_AND_EXPR
*************** register_edge_assert_for (tree name, edg
*** 3712,3724 ****
&comp_code, &val))
return false;
! /* Only register an ASSERT_EXPR if NAME was found in the sub-graph
! reachable from E. */
! if (TEST_BIT (found_in_subgraph, SSA_NAME_VERSION (name)))
! {
! register_new_assert_for (name, comp_code, val, NULL, e, si);
! retval = true;
! }
/* If COND is effectively an equality test of an SSA_NAME against
the value zero or one, then we may be able to assert values
--- 3866,3874 ----
&comp_code, &val))
return false;
! /* Register ASSERT_EXPRs for name. */
! retval |= register_edge_assert_for_2 (name, e, si, cond, is_else_edge);
!
/* If COND is effectively an equality test of an SSA_NAME against
the value zero or one, then we may be able to assert values
*************** find_assert_locations (basic_block bb)
*** 4125,4131 ****
conversion. */
if (! has_single_use (t))
{
! register_new_assert_for (t, comp_code, value,
bb, NULL, si);
need_assert = true;
}
--- 4275,4281 ----
conversion. */
if (! has_single_use (t))
{
! register_new_assert_for (t, t, comp_code, value,
bb, NULL, si);
need_assert = true;
}
*************** find_assert_locations (basic_block bb)
*** 4137,4143 ****
ASSERT_EXPR would do nothing but increase compile time. */
if (!has_single_use (op))
{
! register_new_assert_for (op, comp_code, value, bb, NULL, si);
need_assert = true;
}
}
--- 4287,4294 ----
ASSERT_EXPR would do nothing but increase compile time. */
if (!has_single_use (op))
{
! register_new_assert_for (op, op, comp_code, value,
! bb, NULL, si);
need_assert = true;
}
}
*************** process_assert_insertions_for (tree name
*** 4182,4188 ****
edge_iterator ei;
edge e;
! cond = build2 (loc->comp_code, boolean_type_node, name, loc->val);
assert_expr = build_assert_expr_for (cond, name);
if (loc->e)
--- 4333,4339 ----
edge_iterator ei;
edge e;
! cond = build2 (loc->comp_code, boolean_type_node, loc->expr, loc->val);
assert_expr = build_assert_expr_for (cond, name);
if (loc->e)
Index: gcc/testsuite/gcc.dg/tree-ssa/vrp36.c
===================================================================
*** /dev/null 1970-01-01 00:00:00.000000000 +0000
--- gcc/testsuite/gcc.dg/tree-ssa/vrp36.c 2008-03-20 13:12:15.000000000 +0100
***************
*** 0 ****
--- 1,12 ----
+ /* { dg-do compile } */
+ /* { dg-options "-O2 -fdump-tree-vrp1" } */
+
+ int foo(int i)
+ {
+ if (i < 0 || i >= 5)
+ return i == 1;
+ return 1;
+ }
+
+ /* { dg-final { scan-tree-dump "Folding predicate i_.* == 1 to 0" "vrp1" } } */
+ /* { dg-final { cleanup-tree-dump "vrp1" } } */
Index: gcc/testsuite/gcc.dg/tree-ssa/vrp35.c
===================================================================
*** /dev/null 1970-01-01 00:00:00.000000000 +0000
--- gcc/testsuite/gcc.dg/tree-ssa/vrp35.c 2008-03-20 13:12:15.000000000 +0100
***************
*** 0 ****
--- 1,15 ----
+ /* { dg-do compile } */
+ /* { dg-options "-O2 -fdump-tree-vrp1" } */
+
+ int test1(int i, int k)
+ {
+ if (i > 0 && i <= 5 && k >= 10 && k < 42)
+ {
+ int j = i + 1 + k;
+ return j == 10;
+ }
+ return 1;
+ }
+
+ /* { dg-final { scan-tree-dump "Folding predicate j_.* == 10 to 0" "vrp1" } } */
+ /* { dg-final { cleanup-tree-dump "vrp1" } } */
Index: gcc/testsuite/gcc.dg/tree-ssa/vrp37.c
===================================================================
*** /dev/null 1970-01-01 00:00:00.000000000 +0000
--- gcc/testsuite/gcc.dg/tree-ssa/vrp37.c 2008-03-20 13:12:15.000000000 +0100
***************
*** 0 ****
--- 1,12 ----
+ /* { dg-do compile } */
+ /* { dg-options "-O2" } */
+
+ unsigned char x;
+ int foo(void)
+ {
+ unsigned long long i = x;
+ i = i + 0x80000000;
+ if (i > 0xffffffff)
+ return x;
+ return 0;
+ }
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [PATCH][PING] Teach VRP about range checks
2008-03-20 15:32 [PATCH][PING] Teach VRP about range checks Richard Guenther
@ 2008-03-28 4:15 ` Diego Novillo
2008-03-28 13:04 ` Richard Guenther
0 siblings, 1 reply; 6+ messages in thread
From: Diego Novillo @ 2008-03-28 4:15 UTC (permalink / raw)
To: Richard Guenther; +Cc: gcc-patches
On Thu, Mar 20, 2008 at 10:50, Richard Guenther <rguenther@suse.de> wrote:
> and Diego had some complaints about the added complexity but the
> thread died down without any conclusion.
I withdraw those complaints. There is added complexity, but you
make a good case that it's worth the extra effort. Do we get any
compile time hits because of the added cases?
> PR tree-optimization/30317
> PR tree-optimization/30911
> PR tree-optimization/34793
> * tree-vrp.c (set_value_range_auto): New function.
> (struct assert_locus_d): New member EXPR.
> (register_new_assert_for): Add EXPR parameter to support
> ASSERT_EXPR <name, expr OP limit>.
> (register_edge_assert_for_1): Adjust callers.
> (find_assert_locations): Likewise.
> (process_assert_insertions_for): Build condition from
> expression.
> (extract_range_from_assert): Handle ASSERT_EXPRs
> of the form ASSERT_EXPR <name, expr OP limit>.
> (register_edge_assert_for_2): New helper registering
> asserts for comparisons. Recognize range tests of the form
> (unsigned)i - CST1 OP CST2.
> (register_edge_assert_for_1): Use it.
> (register_edge_assert_for): Likewise.
>
> * gcc.dg/tree-ssa/vrp35.c: New testcase.
> * gcc.dg/tree-ssa/vrp36.c: Likewise.
> * gcc.dg/tree-ssa/vrp37.c: Likewise.
OK, with:
> --- 367,418 ----
> }
>
>
> ! /* Set value range VR to {T, MIN, MAX, EQUIV}. Adjust T, MIN and MAX
> ! treating [MAX, MIN] as anti-range and ~[MAX, MIN] as range when
Mentioning a range [MAX, MIN] is confusing here. Add a
description of why this function exists to set ranges for
expressions of the form var + CST <= limit.
> ! possible. Fall back to varying in corner cases. */
>
> ! static void
> ! set_value_range_auto (value_range_t *vr, enum value_range_type t, tree min,
> ! tree max, bitmap equiv)
> {
> ! tree one, tmp;
>
> + if ((t != VR_RANGE
> + && t != VR_ANTI_RANGE)
> + || TREE_CODE (min) != INTEGER_CST
> + || TREE_CODE (max) != INTEGER_CST
> + || !tree_int_cst_lt (max, min))
> + {
/* If MIN <= MAX already, just set the range. */
> + set_value_range (vr, t, min, max, equiv);
> + return;
> + }
Also, could you edit tree.def and add the additional cases
supported by ASSERT_EXPR?
Thanks. Diego.
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [PATCH][PING] Teach VRP about range checks
2008-03-28 4:15 ` Diego Novillo
@ 2008-03-28 13:04 ` Richard Guenther
2008-03-28 13:22 ` Duncan Sands
2008-04-01 13:52 ` H.J. Lu
0 siblings, 2 replies; 6+ messages in thread
From: Richard Guenther @ 2008-03-28 13:04 UTC (permalink / raw)
To: Diego Novillo; +Cc: gcc-patches
On Thu, 27 Mar 2008, Diego Novillo wrote:
> On Thu, Mar 20, 2008 at 10:50, Richard Guenther <rguenther@suse.de> wrote:
>
> > and Diego had some complaints about the added complexity but the
> > thread died down without any conclusion.
>
> I withdraw those complaints. There is added complexity, but you
> make a good case that it's worth the extra effort. Do we get any
> compile time hits because of the added cases?
No measurable at least. I remember testing cc1files build and the
usual set of "C++" benchmarks (http://www.suse.de/~gcctest/c++bench/)
> OK, with:
>
> > --- 367,418 ----
> > }
> >
> >
> > ! /* Set value range VR to {T, MIN, MAX, EQUIV}. Adjust T, MIN and MAX
> > ! treating [MAX, MIN] as anti-range and ~[MAX, MIN] as range when
>
> Mentioning a range [MAX, MIN] is confusing here. Add a
> description of why this function exists to set ranges for
> expressions of the form var + CST <= limit.
I renamed the function to set_and_canonicalize_value_range and adjusted
the docs as follows:
! /* Set value range VR to the canonical form of {T, MIN, MAX, EQUIV}.
! This means adjusting T, MIN and MAX representing the case of a
! wrapping range with MAX < MIN covering [MIN, type_max] U [type_min,
MAX]
! as anti-rage ~[MAX+1, MIN-1]. Likewise for wrapping anti-ranges.
! In corner cases where MAX+1 or MIN-1 wraps this will fall back
! to varying.
! This routine exists to ease canonicalization in the case where we
! extract ranges from var + CST op limit. */
! static void
! set_and_canonicalize_value_range (value_range_t *vr, enum
value_range_type t,
! tree min, tree max, bitmap equiv)
> Also, could you edit tree.def and add the additional cases
> supported by ASSERT_EXPR?
Sure.
Installed after re-bootstrapping and testing on x86_64-unknown-linux-gnu
as follows.
Richard.
2008-03-28 Richard Guenther <rguenther@suse.de>
PR tree-optimization/30317
PR tree-optimization/30911
PR tree-optimization/34793
* tree-vrp.c (set_and_canonicalize_value_range): New function.
(struct assert_locus_d): New member EXPR.
(register_new_assert_for): Add EXPR parameter to support
ASSERT_EXPR <name, expr OP limit>.
(register_edge_assert_for_1): Adjust callers.
(find_assert_locations): Likewise.
(process_assert_insertions_for): Build condition from
expression.
(extract_range_from_assert): Handle ASSERT_EXPRs
of the form ASSERT_EXPR <name, expr OP limit>.
(register_edge_assert_for_2): New helper registering
asserts for comparisons. Recognize range tests of the form
(unsigned)i - CST1 OP CST2.
(register_edge_assert_for_1): Use it.
(register_edge_assert_for): Likewise.
* tree.def (ASSERT_EXPR): Document extra allowed conditional
expressions.
* gcc.dg/tree-ssa/vrp35.c: New testcase.
* gcc.dg/tree-ssa/vrp36.c: Likewise.
* gcc.dg/tree-ssa/vrp37.c: Likewise.
Index: gcc/tree-vrp.c
===================================================================
*** gcc/tree-vrp.c.orig 2008-03-28 11:33:19.000000000 +0100
--- gcc/tree-vrp.c 2008-03-28 11:48:44.000000000 +0100
*************** struct assert_locus_d
*** 71,76 ****
--- 71,79 ----
/* Value being compared against. */
tree val;
+ /* Expression to compare. */
+ tree expr;
+
/* Next node in the linked list. */
struct assert_locus_d *next;
};
*************** nonnull_arg_p (const_tree arg)
*** 314,319 ****
--- 317,334 ----
}
+ /* Set value range VR to VR_VARYING. */
+
+ static inline void
+ set_value_range_to_varying (value_range_t *vr)
+ {
+ vr->type = VR_VARYING;
+ vr->min = vr->max = NULL_TREE;
+ if (vr->equiv)
+ bitmap_clear (vr->equiv);
+ }
+
+
/* Set value range VR to {T, MIN, MAX, EQUIV}. */
static void
*************** set_value_range (value_range_t *vr, enum
*** 366,389 ****
}
! /* Copy value range FROM into value range TO. */
! static inline void
! copy_value_range (value_range_t *to, value_range_t *from)
{
! set_value_range (to, from->type, from->min, from->max, from->equiv);
! }
! /* Set value range VR to VR_VARYING. */
static inline void
! set_value_range_to_varying (value_range_t *vr)
{
! vr->type = VR_VARYING;
! vr->min = vr->max = NULL_TREE;
! if (vr->equiv)
! bitmap_clear (vr->equiv);
}
/* Set value range VR to a single value. This function is only called
--- 381,437 ----
}
! /* Set value range VR to the canonical form of {T, MIN, MAX, EQUIV}.
! This means adjusting T, MIN and MAX representing the case of a
! wrapping range with MAX < MIN covering [MIN, type_max] U [type_min, MAX]
! as anti-rage ~[MAX+1, MIN-1]. Likewise for wrapping anti-ranges.
! In corner cases where MAX+1 or MIN-1 wraps this will fall back
! to varying.
! This routine exists to ease canonicalization in the case where we
! extract ranges from var + CST op limit. */
! static void
! set_and_canonicalize_value_range (value_range_t *vr, enum value_range_type t,
! tree min, tree max, bitmap equiv)
{
! tree one, tmp;
+ if ((t != VR_RANGE
+ && t != VR_ANTI_RANGE)
+ || TREE_CODE (min) != INTEGER_CST
+ || TREE_CODE (max) != INTEGER_CST
+ || !tree_int_cst_lt (max, min))
+ {
+ set_value_range (vr, t, min, max, equiv);
+ return;
+ }
! /* Wrong order for min and max, to swap them and the VR type we need
! to adjust them. */
! one = build_int_cst (TREE_TYPE (min), 1);
! tmp = int_const_binop (PLUS_EXPR, max, one, 0);
! max = int_const_binop (MINUS_EXPR, min, one, 0);
! min = tmp;
!
! /* There's one corner case, if we had [C+1, C] before we now have
! that again. But this represents an empty value range, so drop
! to varying in this case. */
! if (tree_int_cst_lt (max, min))
! {
! set_value_range_to_varying (vr);
! return;
! }
!
! t = t == VR_RANGE ? VR_ANTI_RANGE : VR_RANGE;
! set_value_range (vr, t, min, max, equiv);
! }
!
! /* Copy value range FROM into value range TO. */
static inline void
! copy_value_range (value_range_t *to, value_range_t *from)
{
! set_value_range (to, from->type, from->min, from->max, from->equiv);
}
/* Set value range VR to a single value. This function is only called
*************** extract_range_from_assert (value_range_t
*** 1116,1135 ****
gcc_assert (COMPARISON_CLASS_P (cond));
/* Find VAR in the ASSERT_EXPR conditional. */
! if (var == TREE_OPERAND (cond, 0))
{
/* If the predicate is of the form VAR COMP LIMIT, then we just
take LIMIT from the RHS and use the same comparison code. */
- limit = TREE_OPERAND (cond, 1);
cond_code = TREE_CODE (cond);
}
else
{
/* If the predicate is of the form LIMIT COMP VAR, then we need
to flip around the comparison code to create the proper range
for VAR. */
- limit = TREE_OPERAND (cond, 0);
cond_code = swap_tree_comparison (TREE_CODE (cond));
}
limit = avoid_overflow_infinity (limit);
--- 1164,1187 ----
gcc_assert (COMPARISON_CLASS_P (cond));
/* Find VAR in the ASSERT_EXPR conditional. */
! if (var == TREE_OPERAND (cond, 0)
! || TREE_CODE (TREE_OPERAND (cond, 0)) == PLUS_EXPR
! || TREE_CODE (TREE_OPERAND (cond, 0)) == NOP_EXPR)
{
/* If the predicate is of the form VAR COMP LIMIT, then we just
take LIMIT from the RHS and use the same comparison code. */
cond_code = TREE_CODE (cond);
+ limit = TREE_OPERAND (cond, 1);
+ cond = TREE_OPERAND (cond, 0);
}
else
{
/* If the predicate is of the form LIMIT COMP VAR, then we need
to flip around the comparison code to create the proper range
for VAR. */
cond_code = swap_tree_comparison (TREE_CODE (cond));
+ limit = TREE_OPERAND (cond, 0);
+ cond = TREE_OPERAND (cond, 1);
}
limit = avoid_overflow_infinity (limit);
*************** extract_range_from_assert (value_range_t
*** 1173,1180 ****
instance, ASSERT_EXPR <x_2, x_2 <= b_4>. If b_4 is ~[2, 10],
then b_4 takes on the ranges [-INF, 1] and [11, +INF]. There is
no single range for x_2 that could describe LE_EXPR, so we might
! as well build the range [b_4, +INF] for it. */
! if (cond_code == EQ_EXPR)
{
enum value_range_type range_type;
--- 1225,1267 ----
instance, ASSERT_EXPR <x_2, x_2 <= b_4>. If b_4 is ~[2, 10],
then b_4 takes on the ranges [-INF, 1] and [11, +INF]. There is
no single range for x_2 that could describe LE_EXPR, so we might
! as well build the range [b_4, +INF] for it.
! One special case we handle is extracting a range from a
! range test encoded as (unsigned)var + CST <= limit. */
! if (TREE_CODE (cond) == NOP_EXPR
! || TREE_CODE (cond) == PLUS_EXPR)
! {
! tree cst2 = NULL_TREE;
!
! if (TREE_CODE (cond) == PLUS_EXPR)
! {
! min = TREE_OPERAND (cond, 1);
! cst2 = fold_build1 (NEGATE_EXPR, TREE_TYPE (min), min);
! min = fold_convert (TREE_TYPE (var), cst2);
! cond = TREE_OPERAND (cond, 0);
! }
! else
! min = build_int_cst (TREE_TYPE (var), 0);
!
! if (cst2 != NULL_TREE)
! max = int_const_binop (PLUS_EXPR, limit, min, 0);
! else
! max = limit;
! max = fold_convert (TREE_TYPE (var), max);
!
! /* We can transform a max, min range to an anti-range or
! vice-versa. Use set_and_canonicalize_value_range which does
! this for us. */
! if (cond_code == LE_EXPR)
! set_and_canonicalize_value_range (vr_p, VR_RANGE,
! min, max, vr_p->equiv);
! else if (cond_code == GT_EXPR)
! set_and_canonicalize_value_range (vr_p, VR_ANTI_RANGE,
! min, max, vr_p->equiv);
! else
! gcc_unreachable ();
! }
! else if (cond_code == EQ_EXPR)
{
enum value_range_type range_type;
*************** debug_all_asserts (void)
*** 3402,3410 ****
/* If NAME doesn't have an ASSERT_EXPR registered for asserting
! 'NAME COMP_CODE VAL' at a location that dominates block BB or
E->DEST, then register this location as a possible insertion point
! for ASSERT_EXPR <NAME, NAME COMP_CODE VAL>.
BB, E and SI provide the exact insertion point for the new
ASSERT_EXPR. If BB is NULL, then the ASSERT_EXPR is to be inserted
--- 3489,3497 ----
/* If NAME doesn't have an ASSERT_EXPR registered for asserting
! 'EXPR COMP_CODE VAL' at a location that dominates block BB or
E->DEST, then register this location as a possible insertion point
! for ASSERT_EXPR <NAME, EXPR COMP_CODE VAL>.
BB, E and SI provide the exact insertion point for the new
ASSERT_EXPR. If BB is NULL, then the ASSERT_EXPR is to be inserted
*************** debug_all_asserts (void)
*** 3413,3419 ****
must not be NULL. */
static void
! register_new_assert_for (tree name,
enum tree_code comp_code,
tree val,
basic_block bb,
--- 3500,3506 ----
must not be NULL. */
static void
! register_new_assert_for (tree name, tree expr,
enum tree_code comp_code,
tree val,
basic_block bb,
*************** register_new_assert_for (tree name,
*** 3467,3473 ****
{
if (loc->comp_code == comp_code
&& (loc->val == val
! || operand_equal_p (loc->val, val, 0)))
{
/* If the assertion NAME COMP_CODE VAL has already been
registered at a basic block that dominates DEST_BB, then
--- 3554,3562 ----
{
if (loc->comp_code == comp_code
&& (loc->val == val
! || operand_equal_p (loc->val, val, 0))
! && (loc->expr == expr
! || operand_equal_p (loc->expr, expr, 0)))
{
/* If the assertion NAME COMP_CODE VAL has already been
registered at a basic block that dominates DEST_BB, then
*************** register_new_assert_for (tree name,
*** 3514,3519 ****
--- 3603,3609 ----
n->si = si;
n->comp_code = comp_code;
n->val = val;
+ n->expr = expr;
n->next = NULL;
if (last_loc)
*************** extract_code_and_val_from_cond (tree nam
*** 3602,3607 ****
--- 3692,3785 ----
return true;
}
+ /* Try to register an edge assertion for SSA name NAME on edge E for
+ the condition COND contributing to the conditional jump pointed to by BSI.
+ Invert the condition COND if INVERT is true.
+ Return true if an assertion for NAME could be registered. */
+
+ static bool
+ register_edge_assert_for_2 (tree name, edge e, block_stmt_iterator bsi,
+ tree cond, bool invert)
+ {
+ tree val;
+ enum tree_code comp_code;
+ bool retval = false;
+
+ if (!extract_code_and_val_from_cond (name, cond, invert, &comp_code, &val))
+ return false;
+
+ /* Only register an ASSERT_EXPR if NAME was found in the sub-graph
+ reachable from E. */
+ if (TEST_BIT (found_in_subgraph, SSA_NAME_VERSION (name))
+ && !has_single_use (name))
+ {
+ register_new_assert_for (name, name, comp_code, val, NULL, e, bsi);
+ retval = true;
+ }
+
+ /* In the case of NAME <= CST and NAME being defined as
+ NAME = (unsigned) NAME2 + CST2 we can assert NAME2 >= -CST2
+ and NAME2 <= CST - CST2. We can do the same for NAME > CST.
+ This catches range and anti-range tests. */
+ if ((comp_code == LE_EXPR
+ || comp_code == GT_EXPR)
+ && TREE_CODE (val) == INTEGER_CST
+ && TYPE_UNSIGNED (TREE_TYPE (val)))
+ {
+ tree def_stmt = SSA_NAME_DEF_STMT (name);
+ tree cst2 = NULL_TREE, name2 = NULL_TREE;
+
+ /* Extract CST2 from the (optional) addition. */
+ if (TREE_CODE (def_stmt) == GIMPLE_MODIFY_STMT
+ && TREE_CODE (GIMPLE_STMT_OPERAND (def_stmt, 1)) == PLUS_EXPR)
+ {
+ name2 = TREE_OPERAND (GIMPLE_STMT_OPERAND (def_stmt, 1), 0);
+ cst2 = TREE_OPERAND (GIMPLE_STMT_OPERAND (def_stmt, 1), 1);
+ if (TREE_CODE (name2) == SSA_NAME
+ && TREE_CODE (cst2) == INTEGER_CST)
+ def_stmt = SSA_NAME_DEF_STMT (name2);
+ }
+
+ /* Extract NAME2 from the (optional) cast. */
+ if (TREE_CODE (def_stmt) == GIMPLE_MODIFY_STMT
+ && TREE_CODE (GIMPLE_STMT_OPERAND (def_stmt, 1)) == NOP_EXPR)
+ name2 = TREE_OPERAND (GIMPLE_STMT_OPERAND (def_stmt, 1), 0);
+
+ if (name2 != NULL_TREE
+ && TREE_CODE (name2) == SSA_NAME
+ && (cst2 == NULL_TREE
+ || TREE_CODE (cst2) == INTEGER_CST)
+ && TREE_CODE (TREE_TYPE (name2)) == INTEGER_TYPE
+ && TEST_BIT (found_in_subgraph, SSA_NAME_VERSION (name2))
+ && !has_single_use (name2))
+ {
+ tree tmp;
+
+ /* Build an expression for the range test. */
+ tmp = name2;
+ if (TREE_TYPE (name) != TREE_TYPE (name2))
+ tmp = build1 (NOP_EXPR, TREE_TYPE (name), tmp);
+ if (cst2 != NULL_TREE)
+ tmp = build2 (PLUS_EXPR, TREE_TYPE (name), tmp, cst2);
+
+ if (dump_file)
+ {
+ fprintf (dump_file, "Adding assert for ");
+ print_generic_expr (dump_file, name2, 0);
+ fprintf (dump_file, " from ");
+ print_generic_expr (dump_file, tmp, 0);
+ fprintf (dump_file, "\n");
+ }
+
+ register_new_assert_for (name2, tmp, comp_code, val, NULL, e, bsi);
+
+ retval = true;
+ }
+ }
+
+ return retval;
+ }
+
/* OP is an operand of a truth value expression which is known to have
a particular value. Register any asserts for OP and for any
operands in OP's defining statement.
*************** register_edge_assert_for_1 (tree op, enu
*** 3629,3635 ****
if (!has_single_use (op))
{
val = build_int_cst (TREE_TYPE (op), 0);
! register_new_assert_for (op, code, val, NULL, e, bsi);
retval = true;
}
--- 3807,3813 ----
if (!has_single_use (op))
{
val = build_int_cst (TREE_TYPE (op), 0);
! register_new_assert_for (op, op, code, val, NULL, e, bsi);
retval = true;
}
*************** register_edge_assert_for_1 (tree op, enu
*** 3648,3673 ****
tree op0 = TREE_OPERAND (rhs, 0);
tree op1 = TREE_OPERAND (rhs, 1);
! /* Conditionally register an assert for each SSA_NAME in the
! comparison. */
! if (TREE_CODE (op0) == SSA_NAME
! && !has_single_use (op0)
! && extract_code_and_val_from_cond (op0, rhs,
! invert, &code, &val))
! {
! register_new_assert_for (op0, code, val, NULL, e, bsi);
! retval = true;
! }
!
! /* Similarly for the second operand of the comparison. */
! if (TREE_CODE (op1) == SSA_NAME
! && !has_single_use (op1)
! && extract_code_and_val_from_cond (op1, rhs,
! invert, &code, &val))
! {
! register_new_assert_for (op1, code, val, NULL, e, bsi);
! retval = true;
! }
}
else if ((code == NE_EXPR
&& (TREE_CODE (rhs) == TRUTH_AND_EXPR
--- 3826,3835 ----
tree op0 = TREE_OPERAND (rhs, 0);
tree op1 = TREE_OPERAND (rhs, 1);
! if (TREE_CODE (op0) == SSA_NAME)
! retval |= register_edge_assert_for_2 (op0, e, bsi, rhs, invert);
! if (TREE_CODE (op1) == SSA_NAME)
! retval |= register_edge_assert_for_2 (op1, e, bsi, rhs, invert);
}
else if ((code == NE_EXPR
&& (TREE_CODE (rhs) == TRUTH_AND_EXPR
*************** register_edge_assert_for (tree name, edg
*** 3727,3739 ****
&comp_code, &val))
return false;
! /* Only register an ASSERT_EXPR if NAME was found in the sub-graph
! reachable from E. */
! if (TEST_BIT (found_in_subgraph, SSA_NAME_VERSION (name)))
! {
! register_new_assert_for (name, comp_code, val, NULL, e, si);
! retval = true;
! }
/* If COND is effectively an equality test of an SSA_NAME against
the value zero or one, then we may be able to assert values
--- 3889,3897 ----
&comp_code, &val))
return false;
! /* Register ASSERT_EXPRs for name. */
! retval |= register_edge_assert_for_2 (name, e, si, cond, is_else_edge);
!
/* If COND is effectively an equality test of an SSA_NAME against
the value zero or one, then we may be able to assert values
*************** find_assert_locations (basic_block bb)
*** 4140,4146 ****
conversion. */
if (! has_single_use (t))
{
! register_new_assert_for (t, comp_code, value,
bb, NULL, si);
need_assert = true;
}
--- 4298,4304 ----
conversion. */
if (! has_single_use (t))
{
! register_new_assert_for (t, t, comp_code, value,
bb, NULL, si);
need_assert = true;
}
*************** find_assert_locations (basic_block bb)
*** 4152,4158 ****
ASSERT_EXPR would do nothing but increase compile time. */
if (!has_single_use (op))
{
! register_new_assert_for (op, comp_code, value, bb, NULL, si);
need_assert = true;
}
}
--- 4310,4317 ----
ASSERT_EXPR would do nothing but increase compile time. */
if (!has_single_use (op))
{
! register_new_assert_for (op, op, comp_code, value,
! bb, NULL, si);
need_assert = true;
}
}
*************** process_assert_insertions_for (tree name
*** 4197,4203 ****
edge_iterator ei;
edge e;
! cond = build2 (loc->comp_code, boolean_type_node, name, loc->val);
assert_expr = build_assert_expr_for (cond, name);
if (loc->e)
--- 4356,4362 ----
edge_iterator ei;
edge e;
! cond = build2 (loc->comp_code, boolean_type_node, loc->expr, loc->val);
assert_expr = build_assert_expr_for (cond, name);
if (loc->e)
Index: gcc/testsuite/gcc.dg/tree-ssa/vrp36.c
===================================================================
*** /dev/null 1970-01-01 00:00:00.000000000 +0000
--- gcc/testsuite/gcc.dg/tree-ssa/vrp36.c 2008-03-28 11:33:25.000000000 +0100
***************
*** 0 ****
--- 1,12 ----
+ /* { dg-do compile } */
+ /* { dg-options "-O2 -fdump-tree-vrp1" } */
+
+ int foo(int i)
+ {
+ if (i < 0 || i >= 5)
+ return i == 1;
+ return 1;
+ }
+
+ /* { dg-final { scan-tree-dump "Folding predicate i_.* == 1 to 0" "vrp1" } } */
+ /* { dg-final { cleanup-tree-dump "vrp1" } } */
Index: gcc/testsuite/gcc.dg/tree-ssa/vrp35.c
===================================================================
*** /dev/null 1970-01-01 00:00:00.000000000 +0000
--- gcc/testsuite/gcc.dg/tree-ssa/vrp35.c 2008-03-28 11:33:25.000000000 +0100
***************
*** 0 ****
--- 1,15 ----
+ /* { dg-do compile } */
+ /* { dg-options "-O2 -fdump-tree-vrp1" } */
+
+ int test1(int i, int k)
+ {
+ if (i > 0 && i <= 5 && k >= 10 && k < 42)
+ {
+ int j = i + 1 + k;
+ return j == 10;
+ }
+ return 1;
+ }
+
+ /* { dg-final { scan-tree-dump "Folding predicate j_.* == 10 to 0" "vrp1" } } */
+ /* { dg-final { cleanup-tree-dump "vrp1" } } */
Index: gcc/testsuite/gcc.dg/tree-ssa/vrp37.c
===================================================================
*** /dev/null 1970-01-01 00:00:00.000000000 +0000
--- gcc/testsuite/gcc.dg/tree-ssa/vrp37.c 2008-03-28 11:33:25.000000000 +0100
***************
*** 0 ****
--- 1,12 ----
+ /* { dg-do compile } */
+ /* { dg-options "-O2" } */
+
+ unsigned char x;
+ int foo(void)
+ {
+ unsigned long long i = x;
+ i = i + 0x80000000;
+ if (i > 0xffffffff)
+ return x;
+ return 0;
+ }
Index: gcc/tree.def
===================================================================
*** gcc/tree.def.orig 2008-03-18 17:08:06.000000000 +0100
--- gcc/tree.def 2008-03-28 11:47:29.000000000 +0100
*************** DEFTREECODE (VALUE_HANDLE, "value_handle
*** 937,944 ****
two things:
1- X is a copy of Y.
! 2- EXPR is a GIMPLE conditional expression (as defined by
! is_gimple_condexpr) and is known to be true.
The type of the expression is the same as Y. */
DEFTREECODE (ASSERT_EXPR, "assert_expr", tcc_expression, 2)
--- 937,949 ----
two things:
1- X is a copy of Y.
! 2- EXPR is a conditional expression and is known to be true.
!
! Valid and to be expected forms of conditional expressions are
! valid GIMPLE condidional expressions (as defined by is_gimple_condexpr)
! and conditional expressions with the first operand being a
! PLUS_EXPR with a variable possibly wrapped in a NOP_EXPR first
! operand and an integer constant second operand.
The type of the expression is the same as Y. */
DEFTREECODE (ASSERT_EXPR, "assert_expr", tcc_expression, 2)
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [PATCH][PING] Teach VRP about range checks
2008-03-28 13:04 ` Richard Guenther
@ 2008-03-28 13:22 ` Duncan Sands
2008-03-28 13:25 ` Richard Guenther
2008-04-01 13:52 ` H.J. Lu
1 sibling, 1 reply; 6+ messages in thread
From: Duncan Sands @ 2008-03-28 13:22 UTC (permalink / raw)
To: gcc-patches; +Cc: Richard Guenther, Diego Novillo
Hi Richard, is VRP now making deductions based on
TYPE_MIN_VALUE/TYPE_MAX_VALUE? The reason I ask is
that attempts to do this in the past caused problems,
because fold liked to perform transformations that
created values outside the type range (it should do
the transform in the base type rather than the type).
If you have fixed all this that would be great news!
Best wishes,
Duncan.
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [PATCH][PING] Teach VRP about range checks
2008-03-28 13:22 ` Duncan Sands
@ 2008-03-28 13:25 ` Richard Guenther
0 siblings, 0 replies; 6+ messages in thread
From: Richard Guenther @ 2008-03-28 13:25 UTC (permalink / raw)
To: Duncan Sands; +Cc: gcc-patches, Diego Novillo
On Fri, 28 Mar 2008, Duncan Sands wrote:
> Hi Richard, is VRP now making deductions based on
> TYPE_MIN_VALUE/TYPE_MAX_VALUE? The reason I ask is
> that attempts to do this in the past caused problems,
> because fold liked to perform transformations that
> created values outside the type range (it should do
> the transform in the base type rather than the type).
> If you have fixed all this that would be great news!
No it doesn't. What it does now is recognize the
if ((unsigned)i + 5 < 10)
and similar style range checks that fold produces from
if (i < 5 || i > 10)
and
if (i > 5 && i < 10)
Dependent on how the Ada FE emits range checks this will
help derive ranges from these checks.
I have to re-evaluate the testcases in the Ada and Fortran
range-check PRs to see what is left to make VRP optimize
these where possible.
But first I have a bunch of switch stmt optimization patches
for VRP.
Thanks,
Richard.
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [PATCH][PING] Teach VRP about range checks
2008-03-28 13:04 ` Richard Guenther
2008-03-28 13:22 ` Duncan Sands
@ 2008-04-01 13:52 ` H.J. Lu
1 sibling, 0 replies; 6+ messages in thread
From: H.J. Lu @ 2008-04-01 13:52 UTC (permalink / raw)
To: Richard Guenther; +Cc: Diego Novillo, gcc-patches
Hi,
This patch breaks 447.dealII in SPEC CPU 2006:
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=35787
H.J.
On Fri, Mar 28, 2008 at 5:20 AM, Richard Guenther <rguenther@suse.de> wrote:
>
> 2008-03-28 Richard Guenther <rguenther@suse.de>
>
>
> PR tree-optimization/30317
> PR tree-optimization/30911
> PR tree-optimization/34793
> * tree-vrp.c (set_and_canonicalize_value_range): New function.
>
> (struct assert_locus_d): New member EXPR.
> (register_new_assert_for): Add EXPR parameter to support
> ASSERT_EXPR <name, expr OP limit>.
> (register_edge_assert_for_1): Adjust callers.
> (find_assert_locations): Likewise.
> (process_assert_insertions_for): Build condition from
> expression.
> (extract_range_from_assert): Handle ASSERT_EXPRs
> of the form ASSERT_EXPR <name, expr OP limit>.
> (register_edge_assert_for_2): New helper registering
> asserts for comparisons. Recognize range tests of the form
> (unsigned)i - CST1 OP CST2.
> (register_edge_assert_for_1): Use it.
> (register_edge_assert_for): Likewise.
> * tree.def (ASSERT_EXPR): Document extra allowed conditional
> expressions.
>
>
> * gcc.dg/tree-ssa/vrp35.c: New testcase.
> * gcc.dg/tree-ssa/vrp36.c: Likewise.
> * gcc.dg/tree-ssa/vrp37.c: Likewise.
>
>
>
^ permalink raw reply [flat|nested] 6+ messages in thread
end of thread, other threads:[~2008-04-01 13:52 UTC | newest]
Thread overview: 6+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2008-03-20 15:32 [PATCH][PING] Teach VRP about range checks Richard Guenther
2008-03-28 4:15 ` Diego Novillo
2008-03-28 13:04 ` Richard Guenther
2008-03-28 13:22 ` Duncan Sands
2008-03-28 13:25 ` Richard Guenther
2008-04-01 13:52 ` H.J. Lu
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).