* [PATCH] EVRP edge info refactoring and simple improvement
@ 2016-12-02 12:12 Richard Biener
2016-12-02 13:25 ` Richard Biener
0 siblings, 1 reply; 3+ messages in thread
From: Richard Biener @ 2016-12-02 12:12 UTC (permalink / raw)
To: gcc-patches
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).
Motivated by Martin Sebors work on b_o_s and the appearant inability
of EVRP to do anything useful for him.
Bootstrap & regtest running on x86_64-unknown-linux-gnu.
Richard.
2016-12-02 Richard Biener <rguenther@suse.de>
* tree-vrp.c (evrp_dom_walker::extract_ranges_from_edge): New method
split out from evrp_dom_walker::before_dom_children.
(evrp_dom_walker::before_dom_children): Use it and implement merging
of edge range info from multiple predecessors.
* gcc.dg/tree-ssa/evrp7.c: New testcase.
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/evrp7.c b/gcc/testsuite/gcc.dg/tree-ssa/evrp7.c
new file mode 100644
index 0000000..c28347d
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/evrp7.c
@@ -0,0 +1,31 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fgimple -fdump-tree-evrp" } */
+
+void __GIMPLE (startwith("evrp"))
+f (unsigned int a)
+{
+ if (a < 4U)
+ goto x;
+ else
+ goto bb_3;
+
+bb_3:
+ if (a > 8U)
+ goto x;
+ else
+ goto bb_4;
+
+x:
+ if (a == 5U)
+ goto bb_5;
+ else
+ goto bb_4;
+
+bb_5:
+ __builtin_abort ();
+
+bb_4:
+ return;
+}
+
+/* { dg-final { scan-tree-dump-times "evrp" 0 "if" } } */
diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
index 600634d..592d3b0 100644
--- a/gcc/tree-vrp.c
+++ b/gcc/tree-vrp.c
@@ -10700,6 +10700,7 @@ public:
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);
+ void extract_ranges_from_edge (edge, vec<std::pair <tree, value_range*> > &);
/* Cond_stack holds the old VR. */
auto_vec<std::pair <tree, value_range*> > stack;
@@ -10736,13 +10737,69 @@ evrp_dom_walker::try_find_new_range (tree op, tree_code code, tree limit)
return NULL;
}
+/* Extract ranges on E and store them into V. */
+
+void
+evrp_dom_walker::extract_ranges_from_edge (edge e,
+ vec<std::pair
+ <tree, value_range*> > & v)
+{
+ gimple *stmt = last_stmt (e->src);
+ tree op0;
+ if (stmt
+ && gimple_code (stmt) == GIMPLE_COND
+ && (op0 = gimple_cond_lhs (stmt))
+ && TREE_CODE (op0) == SSA_NAME
+ && (INTEGRAL_TYPE_P (TREE_TYPE (gimple_cond_lhs (stmt)))
+ || POINTER_TYPE_P (TREE_TYPE (gimple_cond_lhs (stmt)))))
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "Visiting controlling predicate ");
+ print_gimple_stmt (dump_file, stmt, 0, 0);
+ }
+ /* 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);
+
+ /* 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))
+ {
+ /* 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));
+ }
+
+ if (op0_range)
+ v.safe_push (std::make_pair (op0, op0_range));
+ }
+}
+
/* See if there is any new scope is entered with new VR and set that VR to
ssa_name before visiting the statements in the scope. */
edge
evrp_dom_walker::before_dom_children (basic_block bb)
{
- tree op0 = NULL_TREE;
edge_iterator ei;
edge e;
@@ -10768,53 +10825,10 @@ evrp_dom_walker::before_dom_children (basic_block bb)
}
if (pred_e)
{
- gimple *stmt = last_stmt (pred_e->src);
- if (stmt
- && gimple_code (stmt) == GIMPLE_COND
- && (op0 = gimple_cond_lhs (stmt))
- && TREE_CODE (op0) == SSA_NAME
- && (INTEGRAL_TYPE_P (TREE_TYPE (gimple_cond_lhs (stmt)))
- || POINTER_TYPE_P (TREE_TYPE (gimple_cond_lhs (stmt)))))
- {
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file, "Visiting controlling predicate ");
- print_gimple_stmt (dump_file, stmt, 0, 0);
- }
- /* 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);
-
- /* If condition is false, invert the cond. */
- if (pred_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))
- {
- /* 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)
- push_value_range (op1, op1_range);
- }
-
- if (op0_range)
- push_value_range (op0, op0_range);
- }
+ auto_vec<std::pair<tree, value_range *>, 2> ranges;
+ extract_ranges_from_edge (pred_e, ranges);
+ for (unsigned i = 0; i < ranges.length (); ++i)
+ push_value_range (ranges[i].first, ranges[i].second);
}
/* Visit PHI stmts and discover any new VRs possible. */
@@ -10827,6 +10841,71 @@ evrp_dom_walker::before_dom_children (basic_block bb)
break;
}
+ /* If we have multiple predecessors try merging range info from them. */
+ edge first = NULL;
+ if (! pred_e
+ && ! has_unvisited_preds)
+ FOR_EACH_EDGE (e, ei, bb->preds)
+ if ((e->flags & EDGE_EXECUTABLE)
+ && ! dominated_by_p (CDI_DOMINATORS, e->dest, e->src))
+ {
+ first = e;
+ break;
+ }
+ if (first)
+ {
+ auto_vec<std::pair<tree, value_range *>, 2> ranges;
+ extract_ranges_from_edge (first, ranges);
+ if (! ranges.is_empty ())
+ {
+ FOR_EACH_EDGE (e, ei, bb->preds)
+ {
+ if (! (e->flags & EDGE_EXECUTABLE)
+ || e == first)
+ continue;
+ bool can_use_lattice_for_edge
+ = dominated_by_p (CDI_DOMINATORS, e->dest, e->src);
+ auto_vec<std::pair<tree, value_range *>, 2> e_ranges;
+ extract_ranges_from_edge (e, e_ranges);
+ /* ??? Sort the range vectors once we may get more than two
+ ranges and remove the quadratic seach below. */
+ for (unsigned i = 0; i < ranges.length ();)
+ {
+ tree name = ranges[i].first;
+ bool found = false;
+ for (unsigned j = 0; j < e_ranges.length (); ++j)
+ {
+ if (e_ranges[j].first == name)
+ {
+ found = true;
+ vrp_meet (ranges[i].second, e_ranges[j].second);
+ }
+ }
+ if (! found
+ && can_use_lattice_for_edge)
+ {
+ found = true;
+ vrp_meet (ranges[i].second, get_value_range (name));
+ }
+ if (! found
+ || ranges[i].second->type == VR_VARYING)
+ {
+ vrp_value_range_pool.remove (ranges[i].second);
+ ranges.unordered_remove (i);
+ continue;
+ }
+ ++i;
+ }
+ for (unsigned i = 0; i < e_ranges.length (); ++i)
+ vrp_value_range_pool.remove (e_ranges[i].second);
+ if (ranges.is_empty ())
+ break;
+ }
+ for (unsigned i = 0; i < ranges.length (); ++i)
+ push_value_range (ranges[i].first, ranges[i].second);
+ }
+ }
+
for (gphi_iterator gpi = gsi_start_phis (bb);
!gsi_end_p (gpi); gsi_next (&gpi))
{
^ permalink raw reply [flat|nested] 3+ messages in thread
* Re: [PATCH] EVRP edge info refactoring and simple improvement
2016-12-02 12:12 [PATCH] EVRP edge info refactoring and simple improvement Richard Biener
@ 2016-12-02 13:25 ` Richard Biener
2016-12-02 13:44 ` Richard Biener
0 siblings, 1 reply; 3+ messages in thread
From: Richard Biener @ 2016-12-02 13:25 UTC (permalink / raw)
To: gcc-patches
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 <rguenther@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);
^ permalink raw reply [flat|nested] 3+ messages in thread
* Re: [PATCH] EVRP edge info refactoring and simple improvement
2016-12-02 13:25 ` Richard Biener
@ 2016-12-02 13:44 ` Richard Biener
0 siblings, 0 replies; 3+ messages in thread
From: Richard Biener @ 2016-12-02 13:44 UTC (permalink / raw)
To: gcc-patches
On Fri, 2 Dec 2016, Richard Biener wrote:
> 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.
It also allows to optimize
void f (unsigned a)
{
if (a < 4 || a > 8)
goto x;
if (a > 5 && a < 9)
goto x;
return;
x:
if (a == 5)
__builtin_abort ();
}
which VRP does not handle, only reassoc can do this (implementing
folds simplifications, so writing (a < 4 || a > 8 || (a > 5 && a < 9))
simplifies this in fold already.
Richard.
> Richard.
>
> 2016-12-02 Richard Biener <rguenther@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);
>
--
Richard Biener <rguenther@suse.de>
SUSE LINUX GmbH, GF: Felix Imendoerffer, Jane Smithard, Graham Norton, HRB 21284 (AG Nuernberg)
^ permalink raw reply [flat|nested] 3+ messages in thread
end of thread, other threads:[~2016-12-02 13:44 UTC | newest]
Thread overview: 3+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2016-12-02 12:12 [PATCH] EVRP edge info refactoring and simple improvement Richard Biener
2016-12-02 13:25 ` Richard Biener
2016-12-02 13:44 ` Richard Biener
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).