On 10/18/21 12:52 AM, Jeff Law wrote:
On 10/8/2021 9:12 AM, Aldy Hernandez via Gcc-patches wrote:
The following patch converts the strlen pass from evrp to ranger,
leaving DOM as the last remaining user.
So is there any reason why we can't convert DOM as well? DOM's use of
EVRP is pretty limited. You've mentioned FP bits before, but my
recollection is those are not part of the EVRP analysis DOM uses. Hell,
give me a little guidance and I'll do the work...
Not only will I take you up on that offer, but I can provide 90% of the
work. Here be dragons, though (well, for me, maybe not for you ;-)).
DOM is actually an evrp pass at -O1 in disguise. The reason it really
is a covert evrp pass is because:
a) It calls extract_range_from_stmt on each statement.
b) It folds conditionals with simplify_using_ranges.
c) But most importantly, it exports discovered ranges when it's done
(evrp_range_analyzer(true)).
If you look at the evrp pass, you'll notice that that's basically what
it does, albeit with the substitute and fold engine, which also calls
gimple fold plus other goodies.
But I could argue that we've made DOM into an evrp pass without
noticing. The last item (c) is particularly invasive because these
exported ranges show up in other passes unexpectedly. For instance, I
saw an RTL pass at -O1 miss an optimization because it was dependent on
some global range being set. IMO, DOM should not export global ranges
it discovered during its walk (do one thing and do it well), but I leave
it to you experts to pontificate.
The attached patch is rather trivial. It's mostly deleting state. It
seems DOM spends a lot of time massaging the IL so that it can fold
conditionals or thread paths. None of this is needed, because the
ranger can do all of this. Well, except floats, but...
...You'll notice that converting to the threader is an exercise in code
deletion. Basically, inherit from the hybrid threader while still using
the copies/avail_exprs business. This has the added benefit of keeping
our float threading capabilities intact, while pulling in all the hybrid
threader goodness.
Over the past year or so, I've been cleaning up evrp clients to use the
common range_query API. This makes this conversion easier, as it mostly
involves replacing evrp_range_analyzer with the ranger and removing the
state pushing/popping business.
That's the good news. The bad news is that DOM changes the IL as it
goes and the patch doesn't bootstrap. Andrew insists that we should
work even with DOM's changing IL, but last time we played this dance
with the substitute_and_fold engine, there were some tweaks needed to
the ranger. Could be this, but I haven't investigated. It could also
be that the failures I was seeing were just DOM things that were no
longer needed (shuffling the IL to simplify things for evrp).
This just needs a little shepherding from a DOM expert ;-). If you get
it to bootstrap, I could take care of the tests, performance, and making
sure we're getting the same number of threads etc.
No additional cleanups have been done. For example, the strlen pass
still has uses of VR_ANTI_RANGE, and the sprintf still passes around
pairs of integers instead of using a proper range. Fixing this
could further improve these passes.
As a further enhancement, if the relevant maintainers deem useful,
the domwalk could be removed from strlen. That is, unless the pass
needs it for something else.
The dom walk was strictly for the benefit of EVRP when it was added. So
I think it can get zapped once the pass is converted.
Jakub mentioned a while ago, that the strlen pass itself needs DOM, so
perhaps this needs to stay.
Aldy
>From d0cb66e21abfccb738faabe2910b5000823f3030 Mon Sep 17 00:00:00 2001
From: Aldy Hernandez <al...@redhat.com>
Date: Wed, 29 Sep 2021 20:50:41 +0200
Subject: [PATCH] Convert DOM to ranger.
---
gcc/testsuite/gcc.dg/graphite/pr69728.c | 4 +-
gcc/testsuite/gcc.dg/sancov/cmp0.c | 2 +-
.../gcc.dg/tree-ssa/ssa-dom-branch-1.c | 7 +-
gcc/testsuite/gcc.dg/vect/bb-slp-pr81635-2.c | 6 +-
gcc/testsuite/gcc.dg/vect/bb-slp-pr81635-4.c | 24 +++-
gcc/tree-ssa-dom.c | 132 ++++--------------
gcc/tree-ssa-threadedge.c | 67 +--------
gcc/tree-ssa-threadedge.h | 5 +-
8 files changed, 72 insertions(+), 175 deletions(-)
diff --git a/gcc/testsuite/gcc.dg/graphite/pr69728.c b/gcc/testsuite/gcc.dg/graphite/pr69728.c
index 69e28318aaf..e8cd7bec0a1 100644
--- a/gcc/testsuite/gcc.dg/graphite/pr69728.c
+++ b/gcc/testsuite/gcc.dg/graphite/pr69728.c
@@ -24,6 +24,4 @@ fn1 ()
run into scheduling issues before here, not being able to handle
empty domains. */
-/* XFAILed by fix for PR86865. */
-
-/* { dg-final { scan-tree-dump "loop nest optimized" "graphite" { xfail *-*-* } } } */
+/* { dg-final { scan-tree-dump "loop nest optimized" "graphite" } } */
diff --git a/gcc/testsuite/gcc.dg/sancov/cmp0.c b/gcc/testsuite/gcc.dg/sancov/cmp0.c
index 8bbf06e9466..9fd7f5cccc8 100644
--- a/gcc/testsuite/gcc.dg/sancov/cmp0.c
+++ b/gcc/testsuite/gcc.dg/sancov/cmp0.c
@@ -1,6 +1,6 @@
/* Basic test on number of inserted callbacks. */
/* { dg-do compile } */
-/* { dg-options "-fsanitize-coverage=trace-cmp -fdump-tree-optimized" } */
+/* { dg-options "-fsanitize-coverage=trace-cmp -fdump-tree-optimized -fno-thread-jumps" } */
/* { dg-skip-if "different type layout" { avr-*-* } } */
#if __SIZEOF_INT__ < 4
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-branch-1.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-branch-1.c
index fae5bdef818..c71e0d0a63f 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-branch-1.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-branch-1.c
@@ -19,10 +19,9 @@ try_combine (rtx i1, rtx newpat)
else if (i1 && foo ());
}
-/* There should be four tests against i1. One from the hash table
- dumps, one from the EVRP analyzer one from EVRP evaluation and one
- in the code itself. */
-/* { dg-final { scan-tree-dump-times "if .i1_" 4 "dom2"} } */
+/* There should be 3 tests against i1. Two from DOM analyzing things
+ and one from the code itself. */
+/* { dg-final { scan-tree-dump-times "if .i1_" 3 "dom2"} } */
/* There should be no actual jump threads realized by DOM. The
legitimize jump threads are handled in VRP and those discovered
diff --git a/gcc/testsuite/gcc.dg/vect/bb-slp-pr81635-2.c b/gcc/testsuite/gcc.dg/vect/bb-slp-pr81635-2.c
index 6b213d4da28..f5996219780 100644
--- a/gcc/testsuite/gcc.dg/vect/bb-slp-pr81635-2.c
+++ b/gcc/testsuite/gcc.dg/vect/bb-slp-pr81635-2.c
@@ -1,7 +1,11 @@
/* { dg-do compile } */
-/* { dg-additional-options "-fno-tree-loop-vectorize" } */
+/* { dg-additional-options "-fno-tree-loop-vectorize -fno-tree-dominator-opts" } */
/* { dg-require-effective-target lp64 } */
+/* See note in bb-slp-pr81635-4.c. A ranger based DOM causes many
+ more SSA names to be exported which causes slp1 to vectorize
+ more. */
+
double p[1000];
double q[1000];
diff --git a/gcc/testsuite/gcc.dg/vect/bb-slp-pr81635-4.c b/gcc/testsuite/gcc.dg/vect/bb-slp-pr81635-4.c
index 599f718ecdc..f3704a30cbe 100644
--- a/gcc/testsuite/gcc.dg/vect/bb-slp-pr81635-4.c
+++ b/gcc/testsuite/gcc.dg/vect/bb-slp-pr81635-4.c
@@ -1,7 +1,29 @@
/* { dg-do compile } */
-/* { dg-additional-options "-fno-tree-loop-vectorize" } */
+/* { dg-additional-options "-fno-tree-loop-vectorize -fno-tree-dominator-opts" } */
/* { dg-require-effective-target lp64 } */
+/* A ranger based DOM causes many more SSA names to be exported:
+
+ +Exported global range table:
+ +============================
+ +_1 : long unsigned int [0, 4294967294]
+ +_2 : long unsigned int [0, 34359738352]
+ +_7 : unsigned int [1, +INF]
+ +_8 : long unsigned int [1, 4294967295]
+ +_9 : long unsigned int [8, 34359738360]
+ +_10 : double * [1B, +INF]
+ +_12 : double * [1B, +INF]
+ +i_28 : unsigned int [0, 4294967294]
+
+ This causes slp1 to vectorize more things:
+ + vector(2) double * vectp.8;
+ + vector(2) double vect_a_22.7;
+ + vector(2) double vect__6.6;
+ + double * vectp.5;
+ + vector(2) double * vectp.4;
+
+ Disabling DOM to avoid disturbing this test. */
+
void
f1 (double *p, double *q, unsigned int n)
{
diff --git a/gcc/tree-ssa-dom.c b/gcc/tree-ssa-dom.c
index a8a5b34f725..234252cec34 100644
--- a/gcc/tree-ssa-dom.c
+++ b/gcc/tree-ssa-dom.c
@@ -48,7 +48,8 @@ along with GCC; see the file COPYING3. If not see
#include "alloc-pool.h"
#include "tree-vrp.h"
#include "vr-values.h"
-#include "gimple-ssa-evrp-analyze.h"
+#include "gimple-range.h"
+#include "gimple-range-path.h"
#include "alias.h"
/* This file implements optimizations on the dominator tree. */
@@ -588,134 +589,60 @@ record_edge_info (basic_block bb)
class dom_jt_state : public jt_state
{
public:
- dom_jt_state (const_and_copies *copies, avail_exprs_stack *avails,
- evrp_range_analyzer *evrp)
- : m_copies (copies), m_avails (avails), m_evrp (evrp)
+ dom_jt_state (const_and_copies *copies, avail_exprs_stack *avails)
+ : m_copies (copies), m_avails (avails)
{
}
void push (edge e) override
{
m_copies->push_marker ();
m_avails->push_marker ();
- m_evrp->push_marker ();
jt_state::push (e);
}
void pop () override
{
m_copies->pop_to_marker ();
m_avails->pop_to_marker ();
- m_evrp->pop_to_marker ();
jt_state::pop ();
}
void register_equivs_edge (edge e) override
{
record_temporary_equivalences (e, m_copies, m_avails);
}
- void record_ranges_from_stmt (gimple *stmt, bool temporary) override
+ void register_equiv (tree dest, tree src, bool) override
{
- m_evrp->record_ranges_from_stmt (stmt, temporary);
+ m_copies->record_const_or_copy (dest, src);
}
- void register_equiv (tree dest, tree src, bool update) override;
private:
const_and_copies *m_copies;
avail_exprs_stack *m_avails;
- evrp_range_analyzer *m_evrp;
};
-void
-dom_jt_state::register_equiv (tree dest, tree src, bool update)
-{
- m_copies->record_const_or_copy (dest, src);
-
- /* If requested, update the value range associated with DST, using
- the range from SRC. */
- if (update)
- {
- /* Get new VR we can pass to push_value_range. */
- value_range_equiv *new_vr = m_evrp->allocate_value_range_equiv ();
- new (new_vr) value_range_equiv ();
-
- /* There are three cases to consider:
-
- First if SRC is an SSA_NAME, then we can copy the value range
- from SRC into NEW_VR.
-
- Second if SRC is an INTEGER_CST, then we can just set NEW_VR
- to a singleton range. Note that even if SRC is a constant we
- need to set a suitable output range so that VR_UNDEFINED
- ranges do not leak through.
-
- Otherwise set NEW_VR to varying. This may be overly
- conservative. */
- if (TREE_CODE (src) == SSA_NAME)
- new_vr->deep_copy (m_evrp->get_value_range (src));
- else if (TREE_CODE (src) == INTEGER_CST)
- new_vr->set (src);
- else
- new_vr->set_varying (TREE_TYPE (src));
-
- /* This is a temporary range for DST, so push it. */
- m_evrp->push_value_range (dest, new_vr);
- }
-}
-
-class dom_jt_simplifier : public jt_simplifier
+class dom_jt_simplifier : public hybrid_jt_simplifier
{
public:
- dom_jt_simplifier (vr_values *v, avail_exprs_stack *avails)
- : m_vr_values (v), m_avails (avails) { }
+ dom_jt_simplifier (avail_exprs_stack *avails,
+ gimple_ranger *ranger,
+ path_range_query *query)
+ : hybrid_jt_simplifier (ranger, query), m_avails (avails)
+ {
+ }
private:
tree simplify (gimple *, gimple *, basic_block, jt_state *) override;
- vr_values *m_vr_values;
avail_exprs_stack *m_avails;
};
tree
dom_jt_simplifier::simplify (gimple *stmt, gimple *within_stmt,
- basic_block, jt_state *)
+ basic_block bb, jt_state *state)
{
/* First see if the conditional is in the hash table. */
tree cached_lhs = m_avails->lookup_avail_expr (stmt, false, true);
if (cached_lhs)
return cached_lhs;
- if (gcond *cond_stmt = dyn_cast <gcond *> (stmt))
- {
- simplify_using_ranges simplifier (m_vr_values);
- return simplifier.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;
-
- const value_range_equiv *vr = m_vr_values->get_value_range (op);
- return find_case_label_range (switch_stmt, vr);
- }
- 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_equiv new_vr;
- m_vr_values->extract_range_from_stmt (stmt, &dummy_e, &dummy_tree,
- &new_vr);
- tree singleton;
- if (new_vr.singleton_p (&singleton))
- return singleton;
- }
- }
- return NULL;
+ return hybrid_jt_simplifier::simplify (stmt, within_stmt, bb, state);
}
class dom_opt_dom_walker : public dom_walker
@@ -724,12 +651,12 @@ public:
dom_opt_dom_walker (cdi_direction direction,
jump_threader *threader,
jt_state *state,
- evrp_range_analyzer *analyzer,
+ gimple_ranger *ranger,
const_and_copies *const_and_copies,
avail_exprs_stack *avail_exprs_stack)
: dom_walker (direction, REACHABLE_BLOCKS)
{
- m_evrp_range_analyzer = analyzer;
+ m_ranger = ranger;
m_state = state;
m_dummy_cond = gimple_build_cond (NE_EXPR, integer_zero_node,
integer_zero_node, NULL, NULL);
@@ -760,7 +687,7 @@ private:
void test_for_singularity (gimple *, avail_exprs_stack *);
jump_threader *m_threader;
- evrp_range_analyzer *m_evrp_range_analyzer;
+ gimple_ranger *m_ranger;
jt_state *m_state;
};
@@ -857,18 +784,22 @@ pass_dominator::execute (function *fun)
record_edge_info (bb);
/* Recursively walk the dominator tree optimizing statements. */
- evrp_range_analyzer analyzer (true);
- dom_jt_simplifier simplifier (&analyzer, avail_exprs_stack);
- dom_jt_state state (const_and_copies, avail_exprs_stack, &analyzer);
+ gimple_ranger *ranger = enable_ranger (fun);
+ path_range_query path_query (*ranger, /*resolve=*/true);
+ dom_jt_simplifier simplifier (avail_exprs_stack, ranger, &path_query);
+ dom_jt_state state (const_and_copies, avail_exprs_stack);
jump_threader threader (&simplifier, &state);
dom_opt_dom_walker walker (CDI_DOMINATORS,
&threader,
&state,
- &analyzer,
+ ranger,
const_and_copies,
avail_exprs_stack);
walker.walk (fun->cfg->x_entry_block_ptr);
+ ranger->export_global_ranges ();
+ disable_ranger (fun);
+
/* Look for blocks where we cleared EDGE_EXECUTABLE on an outgoing
edge. When found, remove jump threads which contain any outgoing
edge from the affected block. */
@@ -1494,8 +1425,6 @@ 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);
- m_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 ();
@@ -1531,7 +1460,9 @@ dom_opt_dom_walker::before_dom_children (basic_block bb)
continue;
}
- m_state->record_ranges_from_stmt (gsi_stmt (gsi), false);
+ int_range<2> r;
+ gimple *stmt = gsi_stmt (gsi);
+ m_ranger->range_of_stmt (r, stmt);
bool removed_p = false;
taken_edge = this->optimize_stmt (bb, &gsi, &removed_p);
if (!removed_p)
@@ -1579,7 +1510,6 @@ dom_opt_dom_walker::after_dom_children (basic_block bb)
m_threader->thread_outgoing_edges (bb);
m_avail_exprs_stack->pop_to_marker ();
m_const_and_copies->pop_to_marker ();
- m_evrp_range_analyzer->leave (bb);
}
/* Search for redundant computations in STMT. If any are found, then
@@ -2110,7 +2040,7 @@ dom_opt_dom_walker::optimize_stmt (basic_block bb, gimple_stmt_iterator *si,
opt_stats.num_stmts++;
/* Const/copy propagate into USES, VUSES and the RHS of VDEFs. */
- cprop_into_stmt (stmt, m_evrp_range_analyzer);
+ cprop_into_stmt (stmt, m_ranger);
/* If the statement has been modified with constant replacements,
fold its RHS before checking for redundant computations. */
@@ -2208,7 +2138,7 @@ dom_opt_dom_walker::optimize_stmt (basic_block bb, gimple_stmt_iterator *si,
SSA_NAMES. */
update_stmt_if_modified (stmt);
edge taken_edge = NULL;
- simplify_using_ranges simpl (m_evrp_range_analyzer);
+ simplify_using_ranges simpl (m_ranger);
simpl.vrp_visit_cond_stmt (as_a <gcond *> (stmt), &taken_edge);
if (taken_edge)
{
diff --git a/gcc/tree-ssa-threadedge.c b/gcc/tree-ssa-threadedge.c
index a63a9764ff8..3ffb7ceb1fa 100644
--- a/gcc/tree-ssa-threadedge.c
+++ b/gcc/tree-ssa-threadedge.c
@@ -324,7 +324,7 @@ jump_threader::record_temporary_equivalences_from_stmts_at_dest (edge e)
continue;
}
- m_state->register_equivs_stmt (stmt, e->src, m_simplifier);
+ m_state->register_equivs_stmt (stmt);
}
return stmt;
}
@@ -1326,72 +1326,17 @@ jt_state::register_equivs_edge (edge)
}
void
-jt_state::register_equivs_stmt (gimple *stmt, basic_block bb,
- jt_simplifier *simplifier)
+jt_state::register_equivs_stmt (gimple *stmt)
{
- /* At this point we have a statement which assigns an RHS to an
- SSA_VAR on the LHS. We want to try and simplify this statement
- to expose more context sensitive equivalences which in turn may
- allow us to simplify the condition at the end of the loop.
-
- Handle simple copy operations as well as implied copies from
- ASSERT_EXPRs. */
+ /* Try and simplify this statement to expose more context sensitive
+ equivalences which in turn may allow us to simplify the condition
+ at the end of the loop. */
tree cached_lhs = NULL;
if (gimple_assign_single_p (stmt)
&& TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME)
cached_lhs = gimple_assign_rhs1 (stmt);
- else if (gimple_assign_single_p (stmt)
- && TREE_CODE (gimple_assign_rhs1 (stmt)) == ASSERT_EXPR)
- cached_lhs = TREE_OPERAND (gimple_assign_rhs1 (stmt), 0);
else
- {
- /* A statement that is not a trivial copy or ASSERT_EXPR.
- Try to fold the new expression. Inserting the
- expression into the hash table is unlikely to help. */
- /* ??? The DOM callback below can be changed to setting
- the mprts_hook around the call to thread_across_edge,
- avoiding the use substitution. The VRP hook should be
- changed to properly valueize operands itself using
- SSA_NAME_VALUE in addition to its own lattice. */
- cached_lhs = gimple_fold_stmt_to_constant_1 (stmt,
- threadedge_valueize);
- if (NUM_SSA_OPERANDS (stmt, SSA_OP_ALL_USES) != 0
- && (!cached_lhs
- || (TREE_CODE (cached_lhs) != SSA_NAME
- && !is_gimple_min_invariant (cached_lhs))))
- {
- /* We're going to temporarily copy propagate the operands
- and see if that allows us to simplify this statement. */
- tree *copy;
- ssa_op_iter iter;
- use_operand_p use_p;
- unsigned int num, i = 0;
-
- num = NUM_SSA_OPERANDS (stmt, SSA_OP_ALL_USES);
- copy = XALLOCAVEC (tree, num);
-
- /* Make a copy of the uses & vuses into USES_COPY, then cprop into
- the operands. */
- FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
- {
- tree tmp = NULL;
- tree use = USE_FROM_PTR (use_p);
-
- copy[i++] = use;
- if (TREE_CODE (use) == SSA_NAME)
- tmp = SSA_NAME_VALUE (use);
- if (tmp)
- SET_USE (use_p, tmp);
- }
-
- cached_lhs = simplifier->simplify (stmt, stmt, bb, this);
-
- /* Restore the statement's original uses/defs. */
- i = 0;
- FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
- SET_USE (use_p, copy[i++]);
- }
- }
+ cached_lhs = gimple_fold_stmt_to_constant_1 (stmt, threadedge_valueize);
/* Record the context sensitive equivalence if we were able
to simplify this statement. */
diff --git a/gcc/tree-ssa-threadedge.h b/gcc/tree-ssa-threadedge.h
index c46a5c6c489..8782145ae53 100644
--- a/gcc/tree-ssa-threadedge.h
+++ b/gcc/tree-ssa-threadedge.h
@@ -31,8 +31,7 @@ public:
virtual void pop ();
virtual void register_equiv (tree dest, tree src, bool update_range);
virtual void register_equivs_edge (edge e);
- virtual void register_equivs_stmt (gimple *, basic_block,
- class jt_simplifier *);
+ virtual void register_equivs_stmt (gimple *);
virtual void record_ranges_from_stmt (gimple *stmt, bool temporary);
void get_path (vec<basic_block> &);
void append_path (basic_block);
@@ -56,7 +55,7 @@ public:
class hybrid_jt_state : public jt_state
{
private:
- void register_equivs_stmt (gimple *, basic_block, jt_simplifier *) override
+ void register_equivs_stmt (gimple *) override
{
// Ranger has no need to simplify anything.
}
--
2.31.1
