Richard Guenther - [PATCH] Make VRP recognize range tests (unsigned)a + CST <= CST2 (original) (raw)

This is the mail archive of the gcc-patches@gcc.gnu.orgmailing list for the GCC project.

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

This patch makes VRP recognize range and anti-range tests. It does so by allowing more flexible ASSERT_EXPRs (which is neccessary for the anti-range case) like

ASSERT_EXPR <a_1, (unsigned)a_1 + 5 > 13>

and derive ranges and anti-ranges from such directly.

This transformation triggers quite a few times during a C only gcc bootstrap (around 30000 times) due to tree code and tree code class checks.

Bootstrapped and tested on x86_64-unknown-linux-gnu for all languages including Ada.

Ok for mainline?

Thanks, Richard.

2007-01-20 Richard Guenther rguenther@suse.de

* 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/vrp33.c: New testcase.
* gcc.dg/tree-ssa/vrp34.c: Likewise.
* gcc.dg/tree-ssa/vrp35.c: Likewise.

Index: gcc/tree-vrp.c

*** gcc.orig/tree-vrp.c 2007-02-05 15:31:43.000000000 +0100 --- gcc/tree-vrp.c 2007-02-06 11:30:55.000000000 +0100 *************** struct assert_locus_d *** 69,74 **** --- 69,77 ---- /* 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 (tree arg) *** 141,146 **** --- 144,161 ---- }

+ / 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 *** 189,194 **** --- 204,249 ---- }

+ / 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 *************** set_value_range_to_null (value_range_t * *** 226,243 **** }

- / Set value range VR to VR_VARYING. */

--- 281,286 ---- *************** extract_range_from_assert (value_range_t *** 799,818 **** 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)); }
type = TREE_TYPE (limit); --- 842,865 ---- 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); }
type = TREE_TYPE (limit); *************** extract_range_from_assert (value_range_t *** 855,862 **** 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;
--- 902,941 ---- 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) *** 2663,2671 ****

/ 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 --- 2742,2750 ----

/ 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) *** 2674,2680 **** must not be NULL. /
static void ! register_new_assert_for (tree name, enum tree_code comp_code, tree val, basic_block bb, --- 2753,2759 ---- 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, *** 2728,2734 **** { 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 --- 2807,2815 ---- { 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, *** 2775,2780 **** --- 2856,2862 ---- 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 *** 2863,2868 **** --- 2945,3042 ---- 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 + #if 0 + && TREE_CODE (TYPE_MIN_VALUE (TREE_TYPE (name2))) == INTEGER_CST + && TREE_CODE (TYPE_MAX_VALUE (TREE_TYPE (name2))) == INTEGER_CST + #endif + && 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 *** 2890,2896 **** 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; }
--- 3064,3070 ---- 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 *** 2909,2934 **** 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 --- 3083,3092 ---- 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 *** 2989,3001 **** &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 --- 3147,3155 ---- &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) *** 3276,3282 **** conversion. */ if (! has_single_use (t)) { ! register_new_assert_for (t, comp_code, value, bb, NULL, si); need_assert = true; } --- 3430,3436 ---- 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) *** 3288,3294 **** 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; } } --- 3442,3449 ---- 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 *** 3328,3334 **** 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) --- 3483,3489 ---- 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/vrp34.c

*** /dev/null 1970-01-01 00:00:00.000000000 +0000 --- gcc/testsuite/gcc.dg/tree-ssa/vrp34.c 2007-02-06 10:39:58.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/vrp33.c

*** /dev/null 1970-01-01 00:00:00.000000000 +0000 --- gcc/testsuite/gcc.dg/tree-ssa/vrp33.c 2007-02-06 10:39:58.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/vrp35.c

*** /dev/null 1970-01-01 00:00:00.000000000 +0000 --- gcc/testsuite/gcc.dg/tree-ssa/vrp35.c 2007-02-06 10:39:58.000000000 +0100

*** 0 **** --- 1,12 ----

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]