[PATCH](ping) Fix PR15911, VRP for && and ||
Richard Guenther
rguenther@suse.de
Sun Oct 22 15:32:00 GMT 2006
This patch teaches VRP about && and || expressions in conditionals.
See also http://gcc.gnu.org/ml/gcc-patches/2006-05/msg00030.html.
Re-bootstrapped and tested on x86_64-unknown-linux-gnu.
Ok for mainline?
Thanks,
Richard.
:ADDPATCH middle-end:
2006-04-25 Jeff Law <law@redhat.com>
Richard Guenther <rguenther@suse.de>
PR tree-optimization/15911
* tree-vrp.c (extract_code_and_val_from_cond): New function.
(register_edge_assert_for_1): Likewise.
(register_edge_assert_for): Handle &&/&/||/| in conditionals.
(find_conditional_asserts): Adjust for new function signature.
(find_assert_locations): Likewise.
Index: tree-vrp.c
===================================================================
*** tree-vrp.c (revision 113251)
--- tree-vrp.c (working copy)
*************** register_new_assert_for (tree name,
*** 2680,2806 ****
bitmap_set_bit (need_assert_for, SSA_NAME_VERSION (name));
}
! /* Try to register an edge assertion for SSA name NAME on edge E for
! the conditional jump pointed to by SI. Return true if an assertion
! for NAME could be registered. */
static bool
! register_edge_assert_for (tree name, edge e, block_stmt_iterator si)
{
- tree val, stmt;
enum tree_code comp_code;
! stmt = bsi_stmt (si);
/* Do not attempt to infer anything in names that flow through
abnormal edges. */
if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name))
return false;
! /* If NAME was not found in the sub-graph reachable from E, then
! there's nothing to do. */
! if (!TEST_BIT (found_in_subgraph, SSA_NAME_VERSION (name)))
return false;
! /* We found a use of NAME in the sub-graph rooted at E->DEST.
! Register an assertion for NAME according to the value that NAME
! takes on edge E. */
! if (TREE_CODE (stmt) == COND_EXPR)
! {
! /* If BB ends in a COND_EXPR then NAME then we should insert
! the original predicate on EDGE_TRUE_VALUE and the
! opposite predicate on EDGE_FALSE_VALUE. */
! tree cond = COND_EXPR_COND (stmt);
! bool is_else_edge = (e->flags & EDGE_FALSE_VALUE) != 0;
!
! /* Predicates may be a single SSA name or NAME OP VAL. */
! if (cond == name)
! {
! /* If the predicate is a name, it must be NAME, in which
! case we create the predicate NAME == true or
! NAME == false accordingly. */
! comp_code = EQ_EXPR;
! val = (is_else_edge) ? boolean_false_node : boolean_true_node;
! }
! else
! {
! /* Otherwise, we have a comparison of the form NAME COMP VAL
! or VAL COMP NAME. */
! if (name == TREE_OPERAND (cond, 1))
! {
! /* If the predicate is of the form VAL COMP NAME, flip
! COMP around because we need to register NAME as the
! first operand in the predicate. */
! comp_code = swap_tree_comparison (TREE_CODE (cond));
! val = TREE_OPERAND (cond, 0);
! }
! else
! {
! /* The comparison is of the form NAME COMP VAL, so the
! comparison code remains unchanged. */
! comp_code = TREE_CODE (cond);
! val = TREE_OPERAND (cond, 1);
! }
! /* If we are inserting the assertion on the ELSE edge, we
! need to invert the sign comparison. */
! if (is_else_edge)
! comp_code = invert_tree_comparison (comp_code, 0);
!
! /* Do not register always-false predicates. FIXME, this
! works around a limitation in fold() when dealing with
! enumerations. Given 'enum { N1, N2 } x;', fold will not
! fold 'if (x > N2)' to 'if (0)'. */
! if ((comp_code == GT_EXPR || comp_code == LT_EXPR)
! && (INTEGRAL_TYPE_P (TREE_TYPE (val))
! || SCALAR_FLOAT_TYPE_P (TREE_TYPE (val))))
! {
! tree min = TYPE_MIN_VALUE (TREE_TYPE (val));
! tree max = TYPE_MAX_VALUE (TREE_TYPE (val));
! if (comp_code == GT_EXPR && compare_values (val, max) == 0)
! return false;
! if (comp_code == LT_EXPR && compare_values (val, min) == 0)
! return false;
! }
}
}
! else
{
! /* FIXME. Handle SWITCH_EXPR. */
! gcc_unreachable ();
}
! register_new_assert_for (name, comp_code, val, NULL, e, si);
! return true;
}
static bool find_assert_locations (basic_block bb);
/* Determine whether the outgoing edges of BB should receive an
! ASSERT_EXPR for each of the operands of BB's last statement. The
! last statement of BB must be a COND_EXPR or a SWITCH_EXPR.
If any of the sub-graphs rooted at BB have an interesting use of
the predicate operands, an assert location node is added to the
list of assertions for the corresponding operands. */
static bool
! find_conditional_asserts (basic_block bb)
{
bool need_assert;
! block_stmt_iterator last_si;
! tree op, last;
edge_iterator ei;
edge e;
ssa_op_iter iter;
need_assert = false;
! last_si = bsi_last (bb);
! last = bsi_stmt (last_si);
/* Look for uses of the operands in each of the sub-graphs
rooted at BB. We need to check each of the outgoing edges
--- 2680,2968 ----
bitmap_set_bit (need_assert_for, SSA_NAME_VERSION (name));
}
+ /* COND is a predicate which uses NAME. Extract a suitable test code
+ and value and store them into *CODE_P and *VAL_P so the predicate
+ is normalized to NAME *CODE_P *VAL_P.
! If no extraction was possible, return FALSE, otherwise return TRUE.
!
! If INVERT is true, then we invert the result stored into *CODE_P. */
static bool
! extract_code_and_val_from_cond (tree name, tree cond, bool invert,
! enum tree_code *code_p, tree *val_p)
{
enum tree_code comp_code;
+ tree val;
+
+ /* Predicates may be a single SSA name or NAME OP VAL. */
+ if (cond == name)
+ {
+ /* If the predicate is a name, it must be NAME, in which
+ case we create the predicate NAME == true or
+ NAME == false accordingly. */
+ comp_code = EQ_EXPR;
+ val = invert ? boolean_false_node : boolean_true_node;
+ }
+ else
+ {
+ /* Otherwise, we have a comparison of the form NAME COMP VAL
+ or VAL COMP NAME. */
+ if (name == TREE_OPERAND (cond, 1))
+ {
+ /* If the predicate is of the form VAL COMP NAME, flip
+ COMP around because we need to register NAME as the
+ first operand in the predicate. */
+ comp_code = swap_tree_comparison (TREE_CODE (cond));
+ val = TREE_OPERAND (cond, 0);
+ }
+ else
+ {
+ /* The comparison is of the form NAME COMP VAL, so the
+ comparison code remains unchanged. */
+ comp_code = TREE_CODE (cond);
+ val = TREE_OPERAND (cond, 1);
+ }
+
+ /* Invert the comparison code as necessary. */
+ if (invert)
+ comp_code = invert_tree_comparison (comp_code, 0);
+
+ /* We cannot handle float types at all and will ICE in
+ various ways down from compare_values. */
+ if (SCALAR_FLOAT_TYPE_P (TREE_TYPE (val)))
+ return false;
+
+ /* Do not register always-false predicates.
+ FIXME: this works around a limitation in fold() when dealing with
+ enumerations. Given 'enum { N1, N2 } x;', fold will not
+ fold 'if (x > N2)' to 'if (0)'. */
+ if ((comp_code == GT_EXPR || comp_code == LT_EXPR)
+ && INTEGRAL_TYPE_P (TREE_TYPE (val)))
+ {
+ tree min = TYPE_MIN_VALUE (TREE_TYPE (val));
+ tree max = TYPE_MAX_VALUE (TREE_TYPE (val));
+
+ if (comp_code == GT_EXPR
+ && (!max
+ || compare_values (val, max) == 0))
+ return false;
+
+ if (comp_code == LT_EXPR
+ && (!min
+ || compare_values (val, min) == 0))
+ return false;
+ }
+ }
+ *code_p = comp_code;
+ *val_p = val;
+ return true;
+ }
! /* 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.
!
! If CODE is EQ_EXPR, then we want to register OP is zero (false),
! if CODE is NE_EXPR, then we want to register OP is nonzero (true). */
!
! static bool
! register_edge_assert_for_1 (tree op, enum tree_code code,
! edge e, block_stmt_iterator bsi)
! {
! bool invert, retval = false;
! tree op_def, rhs, val;
!
! /* We only care about SSA_NAMEs. */
! if (TREE_CODE (op) != SSA_NAME)
! return false;
!
! /* We know that OP will have a zero or nonzero value. If OP is used
! more than once go ahead and register an assert for OP.
!
! The FOUND_IN_SUBGRAPH support is not helpful in this situation as
! it will always be set for OP (because OP is used in a COND_EXPR in
! the subgraph). */
! 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;
! }
!
! /* Now look at how OP is set. If it's set from a comparison,
! a truth operation or some bit operations, then we may be able
! to register information about the operands of that assignment. */
! op_def = SSA_NAME_DEF_STMT (op);
! if (TREE_CODE (op_def) != MODIFY_EXPR)
! return retval;
!
! invert = (code == EQ_EXPR ? true : false);
! rhs = TREE_OPERAND (op_def, 1);
!
! if (COMPARISON_CLASS_P (rhs))
! {
! 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
! || TREE_CODE (rhs) == BIT_AND_EXPR))
! || (code == EQ_EXPR
! && (TREE_CODE (rhs) == TRUTH_OR_EXPR
! || TREE_CODE (rhs) == BIT_IOR_EXPR)))
! {
! /* Recurse on each operand. */
! retval |= register_edge_assert_for_1 (TREE_OPERAND (rhs, 0),
! code, e, bsi);
! retval |= register_edge_assert_for_1 (TREE_OPERAND (rhs, 1),
! code, e, bsi);
! }
! else if (TREE_CODE (rhs) == TRUTH_NOT_EXPR)
! {
! invert = !invert;
! /* Recurse, flipping the tense of INVERT. */
! retval |= register_edge_assert_for_1 (TREE_OPERAND (rhs, 0),
! invert, e, bsi);
! }
! else if (TREE_CODE (rhs) == SSA_NAME)
! {
! /* Recurse through the copy, the tense of INVERT remains
! unchanged. */
! retval |= register_edge_assert_for_1 (rhs, code, e, bsi);
! }
! else if (TREE_CODE (rhs) == NOP_EXPR
! || TREE_CODE (rhs) == CONVERT_EXPR
! || TREE_CODE (rhs) == VIEW_CONVERT_EXPR
! || TREE_CODE (rhs) == NON_LVALUE_EXPR)
! {
! /* Recurse through the type conversion, the tense of INVERT
! remains unchanged. */
! retval |= register_edge_assert_for_1 (TREE_OPERAND (rhs, 0),
! code, e, bsi);
! }
!
! return retval;
! }
!
! /* 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 SI.
! Return true if an assertion for NAME could be registered. */
!
! static bool
! register_edge_assert_for (tree name, edge e, block_stmt_iterator si, tree cond)
! {
! tree val;
! enum tree_code comp_code;
! bool retval = false;
! bool is_else_edge = (e->flags & EDGE_FALSE_VALUE) != 0;
/* Do not attempt to infer anything in names that flow through
abnormal edges. */
if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name))
return false;
! if (!extract_code_and_val_from_cond (name, cond, is_else_edge,
! &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
! for SSA_NAMEs which flow into COND. */
! /* In the case of NAME == 1 or NAME != 0, for TRUTH_AND_EXPR defining
! statement of NAME we can assert both operands of the TRUTH_AND_EXPR
! have non-zero value. */
! if (((comp_code == EQ_EXPR && integer_onep (val))
! || (comp_code == NE_EXPR && integer_zerop (val))))
! {
! tree def_stmt = SSA_NAME_DEF_STMT (name);
! if (TREE_CODE (def_stmt) == MODIFY_EXPR
! && (TREE_CODE (TREE_OPERAND (def_stmt, 1)) == TRUTH_AND_EXPR
! || TREE_CODE (TREE_OPERAND (def_stmt, 1)) == BIT_AND_EXPR))
! {
! tree op0 = TREE_OPERAND (TREE_OPERAND (def_stmt, 1), 0);
! tree op1 = TREE_OPERAND (TREE_OPERAND (def_stmt, 1), 1);
! retval |= register_edge_assert_for_1 (op0, NE_EXPR, e, si);
! retval |= register_edge_assert_for_1 (op1, NE_EXPR, e, si);
}
}
!
! /* In the case of NAME == 0 or NAME != 1, for TRUTH_OR_EXPR defining
! statement of NAME we can assert both operands of the TRUTH_OR_EXPR
! have zero value. */
! if (((comp_code == EQ_EXPR && integer_zerop (val))
! || (comp_code == NE_EXPR && integer_onep (val))))
{
! tree def_stmt = SSA_NAME_DEF_STMT (name);
!
! if (TREE_CODE (def_stmt) == MODIFY_EXPR
! && (TREE_CODE (TREE_OPERAND (def_stmt, 1)) == TRUTH_OR_EXPR
! || TREE_CODE (TREE_OPERAND (def_stmt, 1)) == BIT_IOR_EXPR))
! {
! tree op0 = TREE_OPERAND (TREE_OPERAND (def_stmt, 1), 0);
! tree op1 = TREE_OPERAND (TREE_OPERAND (def_stmt, 1), 1);
! retval |= register_edge_assert_for_1 (op0, EQ_EXPR, e, si);
! retval |= register_edge_assert_for_1 (op1, EQ_EXPR, e, si);
! }
}
! return retval;
}
static bool find_assert_locations (basic_block bb);
/* Determine whether the outgoing edges of BB should receive an
! ASSERT_EXPR for each of the operands of BB's LAST statement.
! The last statement of BB must be a COND_EXPR or a SWITCH_EXPR.
If any of the sub-graphs rooted at BB have an interesting use of
the predicate operands, an assert location node is added to the
list of assertions for the corresponding operands. */
static bool
! find_conditional_asserts (basic_block bb, tree last)
{
bool need_assert;
! block_stmt_iterator bsi;
! tree op;
edge_iterator ei;
edge e;
ssa_op_iter iter;
need_assert = false;
! bsi = bsi_for_stmt (last);
/* Look for uses of the operands in each of the sub-graphs
rooted at BB. We need to check each of the outgoing edges
*************** find_conditional_asserts (basic_block bb
*** 2844,2850 ****
/* Register the necessary assertions for each operand in the
conditional predicate. */
FOR_EACH_SSA_TREE_OPERAND (op, last, iter, SSA_OP_USE)
! need_assert |= register_edge_assert_for (op, e, last_si);
}
/* Finally, indicate that we have found the operands in the
--- 3006,3013 ----
/* Register the necessary assertions for each operand in the
conditional predicate. */
FOR_EACH_SSA_TREE_OPERAND (op, last, iter, SSA_OP_USE)
! need_assert |= register_edge_assert_for (op, e, bsi,
! COND_EXPR_COND (last));
}
/* Finally, indicate that we have found the operands in the
*************** find_assert_locations (basic_block bb)
*** 3034,3040 ****
&& TREE_CODE (last) == COND_EXPR
&& !fp_predicate (COND_EXPR_COND (last))
&& !ZERO_SSA_OPERANDS (last, SSA_OP_USE))
! need_assert |= find_conditional_asserts (bb);
/* Recurse into the dominator children of BB. */
for (son = first_dom_son (CDI_DOMINATORS, bb);
--- 3197,3203 ----
&& TREE_CODE (last) == COND_EXPR
&& !fp_predicate (COND_EXPR_COND (last))
&& !ZERO_SSA_OPERANDS (last, SSA_OP_USE))
! need_assert |= find_conditional_asserts (bb, last);
/* Recurse into the dominator children of BB. */
for (son = first_dom_son (CDI_DOMINATORS, bb);
Index: gcc/testsuite/gcc.dg/tree-ssa/vrp29.c
===================================================================
*** gcc/testsuite/gcc.dg/tree-ssa/vrp29.c (revision 0)
--- gcc/testsuite/gcc.dg/tree-ssa/vrp29.c (revision 0)
***************
*** 0 ****
--- 1,30 ----
+ /* { dg-do link } */
+ /* { dg-options "-O2" } */
+
+ extern int link_error (int);
+
+ int tst2 (int x, int y)
+ {
+ /* VRP should be able to extract range information for
+ x and y out of this TRUTH_AND_EXPR. */
+ if ((x > 5555) && (y < 6666))
+ {
+ if (x > 5555)
+ if (y < 6666)
+ return 1111;
+ else
+ return link_error (2222);
+ else
+ if (y < 6666)
+ return link_error (3333);
+ else
+ return link_error (4444);
+ }
+ else
+ return 0;
+ }
+
+ int main()
+ {
+ return 0;
+ }
Index: gcc/testsuite/gcc.dg/tree-ssa/vrp30.c
===================================================================
*** gcc/testsuite/gcc.dg/tree-ssa/vrp30.c (revision 0)
--- gcc/testsuite/gcc.dg/tree-ssa/vrp30.c (revision 0)
***************
*** 0 ****
--- 1,36 ----
+ /* { dg-do link } */
+ /* { dg-options "-O2" } */
+
+ extern int link_error (int);
+
+ int tst2 (int x, int y)
+ {
+ /* VRP should be able to extract range information for
+ x and y out of this TRUTH_OR_EXPR. */
+ if ((x > 5555) || (y < 6666))
+ {
+ if (x <= 5555)
+ {
+ if (y < 6666)
+ return 1111;
+ else
+ return link_error (2222);
+ }
+ if (y >= 6666)
+ {
+ if (x > 5555)
+ return 1111;
+ else
+ return link_error (3333);
+ }
+ }
+ else
+ if (x <= 5555 && y >= 6666)
+ link_error (4444);
+ return 0;
+ }
+
+ int main()
+ {
+ return 0;
+ }
More information about the Gcc-patches
mailing list