And a WIP. I can justify continuing work on this during stage3 for
pr78496. But I thought it was worth giving folks a looksie.
The goal here is to make tree-vrp's threading obsolete and remove it and
at the same time pick up all the missed jump threads in pr78496.
Essentially this patch embeds the evrp analysis into DOM and adds some
simplification code to use the results of the evrp analysis within jump
threading.
This bootstraps, but doesn't quite pass regression testing. There's a
few tests that need adjustment. There's also two failing tests which I
think are a manifestation of a latent bug in the EVRP bits I've been
worried about since I started looking at the code.
It does find *all* the missing threads in pr78496. I'm still evaluating
the impact of dropping tree-vrp.c's jump threading, but it looks promising.
There's two patches I'm not posting at this time. First is the range
analyzer embedded in the sprintf warning pass to avoid a false positive
reported to gcc-bugs a while back. I'm pretty sure it tickles the same
latent bug I mentioned above with the range analyzer embedded in DOM.
It also needs minor fixes to deal with being called when the optimizer
is not on. Given the false positive posted to gcc-bugs and the tiny
size of the patch I can justify wrapping that up early in stage3.
The second patch I'm not posting rips jump threading out of tree-vrp.c
It's just too rough in its current state. I'm sure there's a bug that
says GCC has gotten slower than I can use to justify pushing on this
early in stage3 as well.
I'm calling it a night from my virtual office in Hawaii.
Jeff
* gimple-ssa-evrp-analyze.h (class evrp_range_analyzer): Add new
private member, use_scev to control use of SCEV.
* gimple-ssa-evrp-analyze.c
(evrp_range_analyzer::evrp_range_analyzer): Initialize use_scev
from argument. Pass it along to vr_values ctor as well.
(evrp_range_analyzer::record_ranges_from_phis): Only call
SCEV routines if use_scev is true.
* gimple-ssa-evrp.c (evrp_dom_walker): Pass use_scev along to
evrp_range_analyzer ctor.
* tree-vrp.c (vrp_prop::vrp_prop): Accept along use_scev to to
vr_values ctor.
(execute_vrp): Add new argument to vrp_prop::vrp_prop.
* vr-values.h (class vr_values): New data member use_scev.
* vr-values.c (vr_values::vr_values): Accept and initialize use_scev.
(vr_values::extract_range_from_phi_node): Only call SCEV routines
if use_scev is true.
* tree-ssa-dom.c: Include alloc-pool.h, tree-vrp.h, vr-values.h
and gimple-ssa-evrp-analyze.h.
(dom_opt_dom_walker class): Add evrp_range_analyzer member and
initialize it.
(simplify_stmt_for_jump_threading): Copy a blob of code from
tree-vrp.c to use ranges to simplify statements.
(dom_opt_dom_walker::before_dom_children): Call
evrp_range_analyzer::{enter,record_ranges_from_stmt} methods.
(dom_opt_dom_walker::after_dom_children): Similarly for
evrp_range_analyzer::leave.
diff --git a/gcc/gimple-ssa-evrp-analyze.c b/gcc/gimple-ssa-evrp-analyze.c
index 5702a5e..0fd5a01 100644
--- a/gcc/gimple-ssa-evrp-analyze.c
+++ b/gcc/gimple-ssa-evrp-analyze.c
@@ -42,7 +42,8 @@ along with GCC; see the file COPYING3. If not see
#include "vr-values.h"
#include "gimple-ssa-evrp-analyze.h"
-evrp_range_analyzer::evrp_range_analyzer () : stack (10)
+evrp_range_analyzer::evrp_range_analyzer (bool use_scev_)
+ : use_scev (use_scev_), stack (10)
{
edge e;
edge_iterator ei;
@@ -53,7 +54,7 @@ evrp_range_analyzer::evrp_range_analyzer () : stack (10)
FOR_EACH_EDGE (e, ei, bb->preds)
e->flags |= EDGE_EXECUTABLE;
}
- vr_values = new class vr_values;
+ vr_values = new class vr_values (use_scev);
}
void
@@ -178,7 +179,8 @@ evrp_range_analyzer::record_ranges_from_phis (basic_block
bb)
to use VARYING for them. But we can still resort to
SCEV for loop header PHIs. */
struct loop *l;
- if (interesting
+ if (use_scev
+ && interesting
&& (l = loop_containing_stmt (phi))
&& l->header == gimple_bb (phi))
vr_values->adjust_range_with_scev (&vr_result, l, phi, lhs);
diff --git a/gcc/gimple-ssa-evrp-analyze.h b/gcc/gimple-ssa-evrp-analyze.h
index b60bba8..c327836 100644
--- a/gcc/gimple-ssa-evrp-analyze.h
+++ b/gcc/gimple-ssa-evrp-analyze.h
@@ -23,7 +23,7 @@ along with GCC; see the file COPYING3. If not see
class evrp_range_analyzer
{
public:
- evrp_range_analyzer (void);
+ evrp_range_analyzer (bool);
~evrp_range_analyzer (void)
{
if (vr_values)
@@ -70,6 +70,9 @@ class evrp_range_analyzer
void record_ranges_from_incoming_edge (basic_block);
void record_ranges_from_phis (basic_block);
+ /* Whether or not to use SCEV to refine ranges. */
+ bool use_scev;
+
/* STACK holds the old VR. */
auto_vec<std::pair <tree, value_range*> > stack;
};
diff --git a/gcc/gimple-ssa-evrp.c b/gcc/gimple-ssa-evrp.c
index 30d0689..f9a014d 100644
--- a/gcc/gimple-ssa-evrp.c
+++ b/gcc/gimple-ssa-evrp.c
@@ -69,6 +69,7 @@ class evrp_dom_walker : public dom_walker
public:
evrp_dom_walker ()
: dom_walker (CDI_DOMINATORS),
+ evrp_range_analyzer (true),
evrp_folder (evrp_range_analyzer.get_vr_values (false))
{
need_eh_cleanup = BITMAP_ALLOC (NULL);
diff --git a/gcc/tree-ssa-dom.c b/gcc/tree-ssa-dom.c
index eb85b4a..d7f2095 100644
--- a/gcc/tree-ssa-dom.c
+++ b/gcc/tree-ssa-dom.c
@@ -46,6 +46,10 @@ along with GCC; see the file COPYING3. If not see
#include "gimplify.h"
#include "tree-cfgcleanup.h"
#include "dbgcnt.h"
+#include "alloc-pool.h"
+#include "tree-vrp.h"
+#include "vr-values.h"
+#include "gimple-ssa-evrp-analyze.h"
/* This file implements optimizations on the dominator tree. */
@@ -573,6 +577,7 @@ public:
: dom_walker (direction, true),
m_const_and_copies (const_and_copies),
m_avail_exprs_stack (avail_exprs_stack),
+ evrp_range_analyzer (false),
m_dummy_cond (dummy_cond) { }
virtual edge before_dom_children (basic_block);
@@ -584,6 +589,9 @@ private:
class const_and_copies *m_const_and_copies;
class avail_exprs_stack *m_avail_exprs_stack;
+ /* And VRP data. */
+ class evrp_range_analyzer evrp_range_analyzer;
+
/* Dummy condition to avoid creating lots of throw away statements. */
gcond *m_dummy_cond;
@@ -835,6 +843,8 @@ make_pass_dominator (gcc::context *ctxt)
return new pass_dominator (ctxt);
}
+/* A hack. */
+static class vr_values *x_vr_values;
/* A trivial wrapper so that we can present the generic jump
threading code with a simple API for simplifying statements. */
@@ -844,7 +854,91 @@ simplify_stmt_for_jump_threading (gimple *stmt,
class avail_exprs_stack *avail_exprs_stack,
basic_block bb ATTRIBUTE_UNUSED)
{
- return avail_exprs_stack->lookup_avail_expr (stmt, false, true);
+ tree cached_lhs = avail_exprs_stack->lookup_avail_expr (stmt, false, true);
+ if (cached_lhs && is_gimple_min_invariant (cached_lhs))
+ return cached_lhs;
+
+ /* */
+ vr_values *vr_values = x_vr_values;
+ if (gcond *cond_stmt = dyn_cast <gcond *> (stmt))
+ {
+ return vr_values->vrp_evaluate_conditional (gimple_cond_code (cond_stmt),
+ gimple_cond_lhs (cond_stmt),
+ gimple_cond_rhs (cond_stmt),
+ within_stmt);
+ }
+
+ if (gswitch *switch_stmt = dyn_cast <gswitch *> (stmt))
+ {
+ tree op = gimple_switch_index (switch_stmt);
+ if (TREE_CODE (op) != SSA_NAME)
+ return NULL_TREE;
+
+ value_range *vr = vr_values->get_value_range (op);
+ if ((vr->type != VR_RANGE && vr->type != VR_ANTI_RANGE)
+ || symbolic_range_p (vr))
+ return NULL_TREE;
+
+ if (vr->type == VR_RANGE)
+ {
+ size_t i, j;
+
+ find_case_label_range (switch_stmt, vr->min, vr->max, &i, &j);
+
+ if (i == j)
+ {
+ tree label = gimple_switch_label (switch_stmt, i);
+
+ if (CASE_HIGH (label) != NULL_TREE
+ ? (tree_int_cst_compare (CASE_LOW (label), vr->min) <= 0
+ && tree_int_cst_compare (CASE_HIGH (label), vr->max) >= 0)
+ : (tree_int_cst_equal (CASE_LOW (label), vr->min)
+ && tree_int_cst_equal (vr->min, vr->max)))
+ return label;
+
+ if (i > j)
+ return gimple_switch_label (switch_stmt, 0);
+ }
+ }
+
+ if (vr->type == VR_ANTI_RANGE)
+ {
+ unsigned n = gimple_switch_num_labels (switch_stmt);
+ tree min_label = gimple_switch_label (switch_stmt, 1);
+ tree max_label = gimple_switch_label (switch_stmt, n - 1);
+
+ /* The default label will be taken only if the anti-range of the
+ operand is entirely outside the bounds of all the (non-default)
+ case labels. */
+ if (tree_int_cst_compare (vr->min, CASE_LOW (min_label)) <= 0
+ && (CASE_HIGH (max_label) != NULL_TREE
+ ? tree_int_cst_compare (vr->max, CASE_HIGH (max_label)) >= 0
+ : tree_int_cst_compare (vr->max, CASE_LOW (max_label)) >=
0))
+ return gimple_switch_label (switch_stmt, 0);
+ }
+
+ return NULL_TREE;
+ }
+
+ if (gassign *assign_stmt = dyn_cast <gassign *> (stmt))
+ {
+ tree lhs = gimple_assign_lhs (assign_stmt);
+ if (TREE_CODE (lhs) == SSA_NAME
+ && (INTEGRAL_TYPE_P (TREE_TYPE (lhs))
+ || POINTER_TYPE_P (TREE_TYPE (lhs)))
+ && stmt_interesting_for_vrp (stmt))
+ {
+ edge dummy_e;
+ tree dummy_tree;
+ value_range new_vr = VR_INITIALIZER;
+ vr_values->extract_range_from_stmt (stmt, &dummy_e,
+ &dummy_tree, &new_vr);
+ if (range_int_cst_singleton_p (&new_vr))
+ return new_vr.min;
+ }
+ }
+ return NULL;
+
}
/* Valueize hook for gimple_fold_stmt_to_constant_1. */
@@ -1299,6 +1393,8 @@ dom_opt_dom_walker::before_dom_children (basic_block bb)
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "\n\nOptimizing block #%d\n\n", bb->index);
+ evrp_range_analyzer.enter (bb);
+
/* Push a marker on the stacks of local information so that we know how
far to unwind when we finalize this block. */
m_avail_exprs_stack->push_marker ();
@@ -1321,7 +1417,10 @@ dom_opt_dom_walker::before_dom_children (basic_block bb)
edge taken_edge = NULL;
for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
- taken_edge = this->optimize_stmt (bb, gsi);
+ {
+ evrp_range_analyzer.record_ranges_from_stmt (gsi_stmt (gsi));
+ taken_edge = this->optimize_stmt (bb, gsi);
+ }
/* Now prepare to process dominated blocks. */
record_edge_info (bb);
@@ -1339,13 +1438,16 @@ dom_opt_dom_walker::before_dom_children (basic_block bb)
void
dom_opt_dom_walker::after_dom_children (basic_block bb)
{
+ x_vr_values = evrp_range_analyzer.get_vr_values (false);
thread_outgoing_edges (bb, m_dummy_cond, m_const_and_copies,
m_avail_exprs_stack,
simplify_stmt_for_jump_threading);
+ x_vr_values = NULL;
/* These remove expressions local to BB from the tables. */
m_avail_exprs_stack->pop_to_marker ();
m_const_and_copies->pop_to_marker ();
+ evrp_range_analyzer.leave (bb);
}
/* Search for redundant computations in STMT. If any are found, then
diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
index 838822d..46be749 100644
--- a/gcc/tree-vrp.c
+++ b/gcc/tree-vrp.c
@@ -4737,6 +4737,7 @@ insert_range_assertions (void)
class vrp_prop : public ssa_propagation_engine
{
public:
+ vrp_prop (bool use_scev_) : vr_values (use_scev_) { }
enum ssa_prop_result visit_stmt (gimple *, edge *, tree *) FINAL OVERRIDE;
enum ssa_prop_result visit_phi (gphi *) FINAL OVERRIDE;
@@ -6862,7 +6863,7 @@ execute_vrp (bool warn_array_bounds_p)
/* For visiting PHI nodes we need EDGE_DFS_BACK computed. */
mark_dfs_back_edges ();
- class vrp_prop vrp_prop;
+ class vrp_prop vrp_prop (true);
vrp_prop.vrp_initialize ();
vrp_prop.ssa_propagate ();
vrp_prop.vrp_finalize (warn_array_bounds_p);
diff --git a/gcc/vr-values.c b/gcc/vr-values.c
index 3e760a3..a0e68fb 100644
--- a/gcc/vr-values.c
+++ b/gcc/vr-values.c
@@ -1888,7 +1888,8 @@ vr_values::dump_all_value_ranges (FILE *file)
/* Initialize VRP lattice. */
-vr_values::vr_values () : vrp_value_range_pool ("Tree VRP value ranges")
+vr_values::vr_values (bool use_scev_)
+ : vrp_value_range_pool ("Tree VRP value ranges"), use_scev (use_scev_)
{
values_propagated = false;
num_vr_values = num_ssa_names;
@@ -2916,7 +2917,8 @@ scev_check:
scev_check can be reached from two paths, one is a fall through from above
"varying" label, the other is direct goto from code block which tries to
avoid infinite simulation. */
- if ((l = loop_containing_stmt (phi))
+ if (use_scev
+ && (l = loop_containing_stmt (phi))
&& l->header == gimple_bb (phi))
adjust_range_with_scev (vr_result, l, phi, lhs);
diff --git a/gcc/vr-values.h b/gcc/vr-values.h
index 124ee6f..816bdc0 100644
--- a/gcc/vr-values.h
+++ b/gcc/vr-values.h
@@ -37,7 +37,7 @@ along with GCC; see the file COPYING3. If not see
class vr_values
{
public:
- vr_values (void);
+ vr_values (bool);
~vr_values (void);
value_range *get_value_range (const_tree);
@@ -109,6 +109,9 @@ class vr_values
/* Allocation pools for value_range objects. */
object_allocator<value_range> vrp_value_range_pool;
+ /* Whether or not to use SCEV to refine ranges. */
+ bool use_scev;
+
/* This probably belongs in the lattice rather than in here. */
bool values_propagated;
