[PATCH][PING] Teach VRP about range checks
Richard Guenther
rguenther@suse.de
Fri Mar 28 13:04:00 GMT 2008
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)
More information about the Gcc-patches
mailing list