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 <rguent...@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))
{
