On Fri, 2 Dec 2016, Richard Biener wrote:
>
> The following refactors range extraction from edges and makes EVRP
> able to merge such edge based ranges for the case of multiple
> predecessors. This allows it to catch anti-ranges from
> if (a < 4 || a > 8) if that is not re-written to a single test like
> when using gotos.
>
> I don't expect this to catch very much in practice but the refactoring
> means we can incorporate the tricks from register_edge_assert_for
> more easily (we "simply" have to use extract_ranges_from_edge as the
> one-and-true kind-of interface).
Like the following, preliminary testing shows
FAIL: gcc.dg/tree-ssa/pr49039.c scan-tree-dump vrp1 "Folding predicate
minv_[0-9]* == 5 to 0"
FAIL: gcc.dg/tree-ssa/pr49039.c scan-tree-dump vrp1 "Folding predicate
minv_[0-9]* == 6 to 0"
FAIL: gcc.dg/tree-ssa/pr49039.c scan-tree-dump vrp1 "Folding predicate
maxv_[0-9]* == 5 to 0"
FAIL: gcc.dg/tree-ssa/pr49039.c scan-tree-dump vrp1 "Folding predicate
maxv_[0-9]* == 6 to 0"
FAIL: gcc.dg/tree-ssa/vrp35.c scan-tree-dump vrp1 "Removing dead stmt
[^\r\n]* = j_.* == 10"
FAIL: gcc.dg/tree-ssa/vrp36.c scan-tree-dump vrp1 "Removing dead stmt
[^\r\n]* = i_.* == 1"
so more things are done by EVRP. More testing next week because
I expected more VRP testcase fallout. But as expected this allows
for the single-test if (a < 4 || a > 8) variant.
Richard.
2016-12-02 Richard Biener <rguent...@suse.de>
* tree-vrp.c (assert_info): New struct.
(add_assert_info): New helper.
(register_edge_assert_for_2): Refactor to add asserts to a vector
of assert_info.
(register_edge_assert_for_1): Likewise.
(register_edge_assert_for): Likewise.
(finish_register_edge_assert_for): New helper actually registering
asserts where live on edge.
(find_conditional_asserts): Adjust.
(find_switch_asserts): Likewise.
(evrp_dom_walker::try_find_new_range): Generalize.
(evrp_dom_walker::extract_ranges_from_edge): Use
register_edge_assert_for.
(evrp_dom_walker::before_dom_children): Adjust.
diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
index 592d3b0..62d0e9d 100644
--- a/gcc/tree-vrp.c
+++ b/gcc/tree-vrp.c
@@ -89,6 +89,21 @@ static tree vrp_evaluate_conditional_warnv_with_ops (enum
tree_code,
tree, tree, bool, bool *,
bool *);
+struct assert_info
+{
+ /* Predicate code for the ASSERT_EXPR. Must be COMPARISON_CLASS_P. */
+ enum tree_code comp_code;
+
+ /* Name to register the assert for. */
+ tree name;
+
+ /* Value being compared against. */
+ tree val;
+
+ /* Expression to compare. */
+ tree expr;
+};
+
/* Location information for ASSERT_EXPRs. Each instance of this
structure describes an ASSERT_EXPR for an SSA name. Since a single
SSA name may have more than one assertion associated with it, these
@@ -4956,6 +4971,19 @@ debug_all_asserts (void)
dump_all_asserts (stderr);
}
+/* Push the assert info for NAME, EXPR, COMP_CODE and VAL to ASSERTS. */
+
+static void
+add_assert_info (vec<assert_info> &asserts,
+ tree name, tree expr, enum tree_code comp_code, tree val)
+{
+ assert_info info;
+ info.comp_code = comp_code;
+ info.name = name;
+ info.val = val;
+ info.expr = expr;
+ asserts.safe_push (info);
+}
/* If NAME doesn't have an ASSERT_EXPR registered for asserting
'EXPR COMP_CODE VAL' at a location that dominates block BB or
@@ -5172,9 +5200,10 @@ masked_increment (const wide_int &val_in, const wide_int
&mask,
Invert the condition COND if INVERT is true. */
static void
-register_edge_assert_for_2 (tree name, edge e, gimple_stmt_iterator bsi,
+register_edge_assert_for_2 (tree name, edge e,
enum tree_code cond_code,
- tree cond_op0, tree cond_op1, bool invert)
+ tree cond_op0, tree cond_op1, bool invert,
+ vec<assert_info> &asserts)
{
tree val;
enum tree_code comp_code;
@@ -5185,10 +5214,8 @@ register_edge_assert_for_2 (tree name, edge e,
gimple_stmt_iterator bsi,
invert, &comp_code, &val))
return;
- /* Only register an ASSERT_EXPR if NAME was found in the sub-graph
- reachable from E. */
- if (live_on_edge (e, name))
- register_new_assert_for (name, name, comp_code, val, NULL, e, bsi);
+ /* Queue the assert. */
+ add_assert_info (asserts, name, name, comp_code, val);
/* In the case of NAME <= CST and NAME being defined as
NAME = (unsigned) NAME2 + CST2 we can assert NAME2 >= -CST2
@@ -5228,8 +5255,7 @@ register_edge_assert_for_2 (tree name, edge e,
gimple_stmt_iterator bsi,
&& TREE_CODE (name3) == SSA_NAME
&& (cst2 == NULL_TREE
|| TREE_CODE (cst2) == INTEGER_CST)
- && INTEGRAL_TYPE_P (TREE_TYPE (name3))
- && live_on_edge (e, name3))
+ && INTEGRAL_TYPE_P (TREE_TYPE (name3)))
{
tree tmp;
@@ -5247,15 +5273,14 @@ register_edge_assert_for_2 (tree name, edge e,
gimple_stmt_iterator bsi,
fprintf (dump_file, "\n");
}
- register_new_assert_for (name3, tmp, comp_code, val, NULL, e, bsi);
+ add_assert_info (asserts, name3, tmp, comp_code, val);
}
/* If name2 is used later, create an ASSERT_EXPR for it. */
if (name2 != NULL_TREE
&& TREE_CODE (name2) == SSA_NAME
&& TREE_CODE (cst2) == INTEGER_CST
- && INTEGRAL_TYPE_P (TREE_TYPE (name2))
- && live_on_edge (e, name2))
+ && INTEGRAL_TYPE_P (TREE_TYPE (name2)))
{
tree tmp;
@@ -5275,7 +5300,7 @@ register_edge_assert_for_2 (tree name, edge e,
gimple_stmt_iterator bsi,
fprintf (dump_file, "\n");
}
- register_new_assert_for (name2, tmp, comp_code, val, NULL, e, bsi);
+ add_assert_info (asserts, name2, tmp, comp_code, val);
}
}
@@ -5301,8 +5326,7 @@ register_edge_assert_for_2 (tree name, edge e,
gimple_stmt_iterator bsi,
continue;
tree name2 = gimple_assign_lhs (use_stmt);
- if (TREE_CODE (name2) != SSA_NAME
- || !live_on_edge (e, name2))
+ if (TREE_CODE (name2) != SSA_NAME)
continue;
enum tree_code code = gimple_assign_rhs_code (use_stmt);
@@ -5330,8 +5354,7 @@ register_edge_assert_for_2 (tree name, edge e,
gimple_stmt_iterator bsi,
if (TREE_OVERFLOW_P (cst))
cst = drop_tree_overflow (cst);
- register_new_assert_for (name2, name2, comp_code, cst,
- NULL, e, bsi);
+ add_assert_info (asserts, name2, name2, comp_code, cst);
}
}
@@ -5357,15 +5380,14 @@ register_edge_assert_for_2 (tree name, edge e,
gimple_stmt_iterator bsi,
tree op0 = gimple_assign_rhs1 (def_stmt);
tree op1 = gimple_assign_rhs2 (def_stmt);
if (TREE_CODE (op0) == SSA_NAME
- && TREE_CODE (op1) == INTEGER_CST
- && live_on_edge (e, op0))
+ && TREE_CODE (op1) == INTEGER_CST)
{
enum tree_code reverse_op = (rhs_code == PLUS_EXPR
? MINUS_EXPR : PLUS_EXPR);
op1 = int_const_binop (reverse_op, val, op1);
if (TREE_OVERFLOW (op1))
op1 = drop_tree_overflow (op1);
- register_new_assert_for (op0, op0, comp_code, op1, NULL, e, bsi);
+ add_assert_info (asserts, op0, op0, comp_code, op1);
}
}
@@ -5383,8 +5405,7 @@ register_edge_assert_for_2 (tree name, edge e,
gimple_stmt_iterator bsi,
&& prec == TYPE_PRECISION (TREE_TYPE (name2))
&& (comp_code == LE_EXPR || comp_code == GT_EXPR
|| !tree_int_cst_equal (val,
- TYPE_MIN_VALUE (TREE_TYPE (val))))
- && live_on_edge (e, name2))
+ TYPE_MIN_VALUE (TREE_TYPE (val)))))
{
tree tmp, cst;
enum tree_code new_comp_code = comp_code;
@@ -5411,8 +5432,7 @@ register_edge_assert_for_2 (tree name, edge e,
gimple_stmt_iterator bsi,
fprintf (dump_file, "\n");
}
- register_new_assert_for (name2, tmp, new_comp_code, cst, NULL,
- e, bsi);
+ add_assert_info (asserts, name2, tmp, new_comp_code, cst);
}
}
@@ -5428,8 +5448,7 @@ register_edge_assert_for_2 (tree name, edge e,
gimple_stmt_iterator bsi,
&& tree_fits_uhwi_p (cst2)
&& INTEGRAL_TYPE_P (TREE_TYPE (name2))
&& IN_RANGE (tree_to_uhwi (cst2), 1, prec - 1)
- && prec == GET_MODE_PRECISION (TYPE_MODE (TREE_TYPE (val)))
- && live_on_edge (e, name2))
+ && prec == GET_MODE_PRECISION (TYPE_MODE (TREE_TYPE (val))))
{
mask = wi::mask (tree_to_uhwi (cst2), false, prec);
val2 = fold_binary (LSHIFT_EXPR, TREE_TYPE (val), val, cst2);
@@ -5487,8 +5506,7 @@ register_edge_assert_for_2 (tree name, edge e,
gimple_stmt_iterator bsi,
fprintf (dump_file, "\n");
}
- register_new_assert_for (name2, tmp, new_comp_code, new_val,
- NULL, e, bsi);
+ add_assert_info (asserts, name2, tmp, new_comp_code, new_val);
}
}
@@ -5533,12 +5551,10 @@ register_edge_assert_for_2 (tree name, edge e,
gimple_stmt_iterator bsi,
if (!CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt2))
|| !INTEGRAL_TYPE_P (TREE_TYPE (names[1]))
|| (TYPE_PRECISION (TREE_TYPE (name2))
- != TYPE_PRECISION (TREE_TYPE (names[1])))
- || !live_on_edge (e, names[1]))
+ != TYPE_PRECISION (TREE_TYPE (names[1]))))
names[1] = NULL_TREE;
}
- if (live_on_edge (e, name2))
- names[0] = name2;
+ names[0] = name2;
}
}
if (names[0] || names[1])
@@ -5729,8 +5745,7 @@ register_edge_assert_for_2 (tree name, edge e,
gimple_stmt_iterator bsi,
fprintf (dump_file, "\n");
}
- register_new_assert_for (names[i], tmp, LE_EXPR,
- new_val, NULL, e, bsi);
+ add_assert_info (asserts, names[i], tmp, LE_EXPR, new_val);
}
}
}
@@ -5746,7 +5761,7 @@ register_edge_assert_for_2 (tree name, edge e,
gimple_stmt_iterator bsi,
static void
register_edge_assert_for_1 (tree op, enum tree_code code,
- edge e, gimple_stmt_iterator bsi)
+ edge e, vec<assert_info> &asserts)
{
gimple *op_def;
tree val;
@@ -5756,13 +5771,9 @@ register_edge_assert_for_1 (tree op, enum tree_code code,
if (TREE_CODE (op) != SSA_NAME)
return;
- /* 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. */
- if (live_on_edge (e, op))
- {
- val = build_int_cst (TREE_TYPE (op), 0);
- register_new_assert_for (op, op, code, val, NULL, e, bsi);
- }
+ /* We know that OP will have a zero or nonzero value. */
+ val = build_int_cst (TREE_TYPE (op), 0);
+ add_assert_info (asserts, op, op, code, val);
/* 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
@@ -5780,9 +5791,9 @@ register_edge_assert_for_1 (tree op, enum tree_code code,
tree op1 = gimple_assign_rhs2 (op_def);
if (TREE_CODE (op0) == SSA_NAME)
- register_edge_assert_for_2 (op0, e, bsi, rhs_code, op0, op1, invert);
+ register_edge_assert_for_2 (op0, e, rhs_code, op0, op1, invert,
asserts);
if (TREE_CODE (op1) == SSA_NAME)
- register_edge_assert_for_2 (op1, e, bsi, rhs_code, op0, op1, invert);
+ register_edge_assert_for_2 (op1, e, rhs_code, op0, op1, invert,
asserts);
}
else if ((code == NE_EXPR
&& gimple_assign_rhs_code (op_def) == BIT_AND_EXPR)
@@ -5794,22 +5805,22 @@ register_edge_assert_for_1 (tree op, enum tree_code
code,
tree op1 = gimple_assign_rhs2 (op_def);
if (TREE_CODE (op0) == SSA_NAME
&& has_single_use (op0))
- register_edge_assert_for_1 (op0, code, e, bsi);
+ register_edge_assert_for_1 (op0, code, e, asserts);
if (TREE_CODE (op1) == SSA_NAME
&& has_single_use (op1))
- register_edge_assert_for_1 (op1, code, e, bsi);
+ register_edge_assert_for_1 (op1, code, e, asserts);
}
else if (gimple_assign_rhs_code (op_def) == BIT_NOT_EXPR
&& TYPE_PRECISION (TREE_TYPE (gimple_assign_lhs (op_def))) == 1)
{
/* Recurse, flipping CODE. */
code = invert_tree_comparison (code, false);
- register_edge_assert_for_1 (gimple_assign_rhs1 (op_def), code, e, bsi);
+ register_edge_assert_for_1 (gimple_assign_rhs1 (op_def), code, e,
asserts);
}
else if (gimple_assign_rhs_code (op_def) == SSA_NAME)
{
/* Recurse through the copy. */
- register_edge_assert_for_1 (gimple_assign_rhs1 (op_def), code, e, bsi);
+ register_edge_assert_for_1 (gimple_assign_rhs1 (op_def), code, e,
asserts);
}
else if (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (op_def)))
{
@@ -5819,7 +5830,7 @@ register_edge_assert_for_1 (tree op, enum tree_code code,
if (INTEGRAL_TYPE_P (TREE_TYPE (rhs))
&& (TYPE_PRECISION (TREE_TYPE (rhs))
<= TYPE_PRECISION (TREE_TYPE (op))))
- register_edge_assert_for_1 (rhs, code, e, bsi);
+ register_edge_assert_for_1 (rhs, code, e, asserts);
}
}
@@ -5828,9 +5839,9 @@ register_edge_assert_for_1 (tree op, enum tree_code code,
SI. */
static void
-register_edge_assert_for (tree name, edge e, gimple_stmt_iterator si,
+register_edge_assert_for (tree name, edge e,
enum tree_code cond_code, tree cond_op0,
- tree cond_op1)
+ tree cond_op1, vec<assert_info> &asserts)
{
tree val;
enum tree_code comp_code;
@@ -5848,8 +5859,8 @@ register_edge_assert_for (tree name, edge e,
gimple_stmt_iterator si,
return;
/* Register ASSERT_EXPRs for name. */
- register_edge_assert_for_2 (name, e, si, cond_code, cond_op0,
- cond_op1, is_else_edge);
+ register_edge_assert_for_2 (name, e, cond_code, cond_op0,
+ cond_op1, is_else_edge, asserts);
/* If COND is effectively an equality test of an SSA_NAME against
@@ -5869,8 +5880,8 @@ register_edge_assert_for (tree name, edge e,
gimple_stmt_iterator si,
{
tree op0 = gimple_assign_rhs1 (def_stmt);
tree op1 = gimple_assign_rhs2 (def_stmt);
- register_edge_assert_for_1 (op0, NE_EXPR, e, si);
- register_edge_assert_for_1 (op1, NE_EXPR, e, si);
+ register_edge_assert_for_1 (op0, NE_EXPR, e, asserts);
+ register_edge_assert_for_1 (op1, NE_EXPR, e, asserts);
}
}
@@ -5891,12 +5902,28 @@ register_edge_assert_for (tree name, edge e,
gimple_stmt_iterator si,
{
tree op0 = gimple_assign_rhs1 (def_stmt);
tree op1 = gimple_assign_rhs2 (def_stmt);
- register_edge_assert_for_1 (op0, EQ_EXPR, e, si);
- register_edge_assert_for_1 (op1, EQ_EXPR, e, si);
+ register_edge_assert_for_1 (op0, EQ_EXPR, e, asserts);
+ register_edge_assert_for_1 (op1, EQ_EXPR, e, asserts);
}
}
}
+/* Finish found ASSERTS for E and register them at GSI. */
+
+static void
+finish_register_edge_assert_for (edge e, gimple_stmt_iterator gsi,
+ vec<assert_info> &asserts)
+{
+ for (unsigned i = 0; i < asserts.length (); ++i)
+ /* Only register an ASSERT_EXPR if NAME was found in the sub-graph
+ reachable from E. */
+ if (live_on_edge (e, asserts[i].name))
+ register_new_assert_for (asserts[i].name, asserts[i].expr,
+ asserts[i].comp_code, asserts[i].val,
+ NULL, e, gsi);
+}
+
+
/* Determine whether the outgoing edges of BB should receive an
ASSERT_EXPR for each of the operands of BB's LAST statement.
@@ -5928,11 +5955,13 @@ find_conditional_asserts (basic_block bb, gcond *last)
/* Register the necessary assertions for each operand in the
conditional predicate. */
+ auto_vec<assert_info, 8> asserts;
FOR_EACH_SSA_TREE_OPERAND (op, last, iter, SSA_OP_USE)
- register_edge_assert_for (op, e, bsi,
+ register_edge_assert_for (op, e,
gimple_cond_code (last),
gimple_cond_lhs (last),
- gimple_cond_rhs (last));
+ gimple_cond_rhs (last), asserts);
+ finish_register_edge_assert_for (e, bsi, asserts);
}
}
@@ -6044,12 +6073,16 @@ find_switch_asserts (basic_block bb, gswitch *last)
/* Register the necessary assertions for the operand in the
SWITCH_EXPR. */
- register_edge_assert_for (op, e, bsi,
+ auto_vec<assert_info, 8> asserts;
+ register_edge_assert_for (op, e,
max ? GE_EXPR : EQ_EXPR,
- op, fold_convert (TREE_TYPE (op), min));
+ op, fold_convert (TREE_TYPE (op), min),
+ asserts);
if (max)
- register_edge_assert_for (op, e, bsi, LE_EXPR, op,
- fold_convert (TREE_TYPE (op), max));
+ register_edge_assert_for (op, e, LE_EXPR, op,
+ fold_convert (TREE_TYPE (op), max),
+ asserts);
+ finish_register_edge_assert_for (e, bsi, asserts);
}
XDELETEVEC (ci);
@@ -6089,8 +6122,11 @@ find_switch_asserts (basic_block bb, gswitch *last)
if (max == NULL_TREE)
{
/* Register the assertion OP != MIN. */
+ auto_vec<assert_info, 8> asserts;
min = fold_convert (TREE_TYPE (op), min);
- register_edge_assert_for (op, default_edge, bsi, NE_EXPR, op, min);
+ register_edge_assert_for (op, default_edge, NE_EXPR, op, min,
+ asserts);
+ finish_register_edge_assert_for (default_edge, bsi, asserts);
}
else
{
@@ -10699,7 +10735,7 @@ public:
virtual void after_dom_children (basic_block);
void push_value_range (tree var, value_range *vr);
value_range *pop_value_range (tree var);
- value_range *try_find_new_range (tree op, tree_code code, tree limit);
+ value_range *try_find_new_range (tree, tree op, tree_code code, tree limit);
void extract_ranges_from_edge (edge, vec<std::pair <tree, value_range*> > &);
/* Cond_stack holds the old VR. */
@@ -10709,19 +10745,18 @@ public:
auto_vec<gimple *> stmts_to_remove;
};
-/* Find new range for OP such that (OP CODE LIMIT) is true. */
+/* Find new range for NAME such that (OP CODE LIMIT) is true. */
value_range *
-evrp_dom_walker::try_find_new_range (tree op, tree_code code, tree limit)
+evrp_dom_walker::try_find_new_range (tree name,
+ tree op, tree_code code, tree limit)
{
value_range vr = VR_INITIALIZER;
- value_range *old_vr = get_value_range (op);
+ value_range *old_vr = get_value_range (name);
/* Discover VR when condition is true. */
- extract_range_for_var_from_comparison_expr (op, code, op,
+ extract_range_for_var_from_comparison_expr (name, code, op,
limit, &vr);
- if (old_vr->type == VR_RANGE || old_vr->type == VR_ANTI_RANGE)
- vrp_intersect_ranges (&vr, old_vr);
/* If we found any usable VR, set the VR to ssa_name and create a
PUSH old value in the stack with the old VR. */
if (vr.type == VR_RANGE || vr.type == VR_ANTI_RANGE)
@@ -10761,36 +10796,24 @@ evrp_dom_walker::extract_ranges_from_edge (edge e,
/* Entering a new scope. Try to see if we can find a VR
here. */
tree op1 = gimple_cond_rhs (stmt);
- tree_code code = gimple_cond_code (stmt);
-
if (TREE_OVERFLOW_P (op1))
op1 = drop_tree_overflow (op1);
+ tree_code code = gimple_cond_code (stmt);
- /* If condition is false, invert the cond. */
- if (e->flags & EDGE_FALSE_VALUE)
- code = invert_tree_comparison (gimple_cond_code (stmt),
- HONOR_NANS (op0));
- /* Add VR when (OP0 CODE OP1) condition is true. */
- value_range *op0_range = try_find_new_range (op0, code, op1);
-
- /* Register ranges for y in x < y where
- y might have ranges that are useful. */
- tree limit;
- tree_code new_code;
- if (TREE_CODE (op1) == SSA_NAME
- && extract_code_and_val_from_cond_with_ops (op1, code,
- op0, op1,
- false,
- &new_code, &limit))
+ auto_vec<assert_info, 8> asserts;
+ register_edge_assert_for (op0, e, code, op0, op1, asserts);
+ if (TREE_CODE (op1) == SSA_NAME)
+ register_edge_assert_for (op1, e, code, op0, op1, asserts);
+
+ for (unsigned i = 0; i < asserts.length (); ++i)
{
- /* Add VR when (OP1 NEW_CODE LIMIT) condition is true. */
- value_range *op1_range = try_find_new_range (op1, new_code, limit);
- if (op1_range)
- v.safe_push (std::make_pair (op1, op1_range));
+ value_range *vr = try_find_new_range (asserts[i].name,
+ asserts[i].expr,
+ asserts[i].comp_code,
+ asserts[i].val);
+ if (vr)
+ v.safe_push (std::make_pair (asserts[i].name, vr));
}
-
- if (op0_range)
- v.safe_push (std::make_pair (op0, op0_range));
}
}
@@ -11058,13 +11081,13 @@ evrp_dom_walker::before_dom_children (basic_block bb)
/* Add VR when (T COMP_CODE value) condition is
true. */
value_range *op_range
- = try_find_new_range (t, comp_code, value);
+ = try_find_new_range (t, t, comp_code, value);
if (op_range)
push_value_range (t, op_range);
}
}
/* Add VR when (OP COMP_CODE value) condition is true. */
- value_range *op_range = try_find_new_range (op,
+ value_range *op_range = try_find_new_range (op, op,
comp_code, value);
if (op_range)
push_value_range (op, op_range);
