[PATCH] backwards threader: handle SSA names occurring in abnormal PHIs
Aldy Hernandez <[email protected]>
| Newsgroups | gmane.comp.gcc.patches |
|---|---|
| Message-ID | <[email protected]> |
[Andrew: are you OK with the changes to gimple_range_ssa_names and
gimple_range_ssa_p, or would you prefer it to be solved a different
way?]
[Richi/Jeff, are you OK with this, since you've done work in this area?]
The backward threader refuses to look at any SSA name occurring in an
abnormal PHI, but DOM's threader does, at least for PHIs where the
path taken does not include an abnormal edge. For example:
x_5(ab) = PHI <45(5), y_8(ab)>
...
if (x_5 == 45)
If we're threading a path coming in from BB5, it's perfectly valid to
thread this path, even if x_5 itself is AB.
This patch adds the functionality to the path solver, and also enables
threading computed gotos whose destination occurs in an abnormal PHI,
which happens when the goto block is itself one of the goto's targets.
I'm adding an abnormal_ok flag to gimple_range_ssa_p and
gimple_range_ssa_names, defaulting to false, so path discovery and the
solver track names occurring in abnormal PHIs like any other.
The flag lives in gimple_range_ssa_p rather than in a path solver
local predicate because operand collection must agree with the
predicate: gimple_range_ssa_names walks a statement's operands via the
range-op handler and filters them with gimple_range_ssa_p. A
path-local version would have to duplicate all this. I tried it both
ways, and the path solver local predicate was fugly.
gcc/ChangeLog:
PR tree-optimization/126103
* gimple-range-fold.h (gimple_range_ssa_p): Add abnormal_ok
argument.
* gimple-range-op.h (gimple_range_ssa_names): Same.
* gimple-range-op.cc (gimple_range_ssa_names): Same.
* gimple-range-path.cc (path_range_query::get_cache): Allow
names occurring in abnormal PHIs.
(path_range_query::ssa_range_in_phi): Assert the incoming path
edge is not abnormal.
(path_range_query::compute_exit_dependencies): Allow names
occurring in abnormal PHIs.
(path_range_query::maybe_register_phi_relation): Comment.
* tree-ssa-threadbackward.cc (back_threader::find_paths_to_names):
Follow abnormal PHIs and names occurring in abnormal PHIs.
(back_threader::maybe_thread_block): Allow names occurring in
abnormal PHIs.
gcc/testsuite/ChangeLog:
PR tree-optimization/126103
* gcc.dg/tree-ssa/ssa-thread-abnormal-phi-1.c: New test.
* gcc.dg/tree-ssa/ssa-thread-abnormal-phi-2.c: New test.
* gcc.dg/tree-ssa/backthread-computed-goto-2.c: New test.
---
gcc/gimple-range-fold.h | 6 ++-
gcc/gimple-range-op.cc | 16 ++++---
gcc/gimple-range-op.h | 3 +-
gcc/gimple-range-path.cc | 11 ++++-
.../tree-ssa/backthread-computed-goto-2.c | 22 +++++++++
.../tree-ssa/ssa-thread-abnormal-phi-1.c | 46 +++++++++++++++++++
.../tree-ssa/ssa-thread-abnormal-phi-2.c | 45 ++++++++++++++++++
gcc/tree-ssa-threadbackward.cc | 11 ++---
8 files changed, 141 insertions(+), 19 deletions(-)
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/backthread-computed-goto-2.c
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-abnormal-phi-1.c
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-abnormal-phi-2.c
diff --git a/gcc/gimple-range-fold.h b/gcc/gimple-range-fold.h
index b11c179d173..13d7d56288e 100644
--- a/gcc/gimple-range-fold.h
+++ b/gcc/gimple-range-fold.h
@@ -84,13 +84,15 @@ gimple_range_type (const gimple *s)
}
// Return EXP if it is an SSA_NAME with a type supported by gimple ranges.
+// If ABNORMAL_OK, also accept SSA names occurring in abnormal PHIs,
+// which only the path solver can handle currently.
inline tree
-gimple_range_ssa_p (tree exp)
+gimple_range_ssa_p (tree exp, bool abnormal_ok = false)
{
if (exp && TREE_CODE (exp) == SSA_NAME &&
!SSA_NAME_IS_VIRTUAL_OPERAND (exp) &&
- !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (exp) &&
+ (abnormal_ok || !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (exp)) &&
value_range::supports_type_p (TREE_TYPE (exp)))
return exp;
return NULL_TREE;
diff --git a/gcc/gimple-range-op.cc b/gcc/gimple-range-op.cc
index 63eccc3fb9f..64db73bd912 100644
--- a/gcc/gimple-range-op.cc
+++ b/gcc/gimple-range-op.cc
@@ -48,10 +48,12 @@ along with GCC; see the file COPYING3. If not see
// Given stmt S, fill VEC, up to VEC_SIZE elements, with relevant ssa-names
// on the statement. For efficiency, it is an error to not pass in enough
-// elements for the vector. Return the number of ssa-names.
+// elements for the vector. Return the number of ssa-names. If
+// ABNORMAL_OK, also include SSA names occurring in abnormal PHIs.
unsigned
-gimple_range_ssa_names (tree *vec, unsigned vec_size, gimple *stmt)
+gimple_range_ssa_names (tree *vec, unsigned vec_size, gimple *stmt,
+ bool abnormal_ok)
{
tree ssa;
int count = 0;
@@ -60,9 +62,9 @@ gimple_range_ssa_names (tree *vec, unsigned vec_size, gimple *stmt)
if (handler)
{
gcc_checking_assert (vec_size >= 2);
- if ((ssa = gimple_range_ssa_p (handler.operand1 ())))
+ if ((ssa = gimple_range_ssa_p (handler.operand1 (), abnormal_ok)))
vec[count++] = ssa;
- if ((ssa = gimple_range_ssa_p (handler.operand2 ())))
+ if ((ssa = gimple_range_ssa_p (handler.operand2 (), abnormal_ok)))
vec[count++] = ssa;
}
else if (is_a<gassign *> (stmt)
@@ -70,11 +72,11 @@ gimple_range_ssa_names (tree *vec, unsigned vec_size, gimple *stmt)
{
gcc_checking_assert (vec_size >= 3);
gassign *st = as_a<gassign *> (stmt);
- if ((ssa = gimple_range_ssa_p (gimple_assign_rhs1 (st))))
+ if ((ssa = gimple_range_ssa_p (gimple_assign_rhs1 (st), abnormal_ok)))
vec[count++] = ssa;
- if ((ssa = gimple_range_ssa_p (gimple_assign_rhs2 (st))))
+ if ((ssa = gimple_range_ssa_p (gimple_assign_rhs2 (st), abnormal_ok)))
vec[count++] = ssa;
- if ((ssa = gimple_range_ssa_p (gimple_assign_rhs3 (st))))
+ if ((ssa = gimple_range_ssa_p (gimple_assign_rhs3 (st), abnormal_ok)))
vec[count++] = ssa;
}
return count;
diff --git a/gcc/gimple-range-op.h b/gcc/gimple-range-op.h
index 51da0ddebea..0425e122acf 100644
--- a/gcc/gimple-range-op.h
+++ b/gcc/gimple-range-op.h
@@ -52,6 +52,7 @@ private:
// on the statement. For efficiency, it is an error to not pass in enough
// elements for the vector. Return the number of ssa-names.
-unsigned gimple_range_ssa_names (tree *vec, unsigned vec_size, gimple *stmt);
+unsigned gimple_range_ssa_names (tree *vec, unsigned vec_size, gimple *stmt,
+ bool abnormal_ok = false);
#endif // GCC_GIMPLE_RANGE_OP_H
diff --git a/gcc/gimple-range-path.cc b/gcc/gimple-range-path.cc
index 8a89da3dda3..4e62b25ffb2 100644
--- a/gcc/gimple-range-path.cc
+++ b/gcc/gimple-range-path.cc
@@ -81,7 +81,7 @@ path_range_query::exit_dependency_p (tree name)
inline bool
path_range_query::get_cache (vrange &r, tree name)
{
- if (!gimple_range_ssa_p (name))
+ if (!gimple_range_ssa_p (name, /*abnormal_ok=*/true))
return get_global_range_query ()->range_of_expr (r, name);
return m_cache.get_range (r, name);
@@ -256,6 +256,10 @@ path_range_query::ssa_range_in_phi (vrange &r, gphi *phi)
basic_block bb = gimple_bb (phi);
basic_block prev = prev_bb ();
edge e_in = find_edge (prev, bb);
+ // The incoming edge the path supplies is never abnormal, so the
+ // argument on it is a valid value for the PHI result even when the
+ // result occurs in an abnormal PHI.
+ gcc_checking_assert (!(e_in->flags & EDGE_ABNORMAL));
tree arg = PHI_ARG_DEF_FROM_EDGE (phi, e_in);
// Avoid using the cache for ARGs defined in this block, as
// that could create an ordering problem.
@@ -526,7 +530,8 @@ path_range_query::compute_exit_dependencies (bitmap dependencies)
else if (gassign *ass = dyn_cast <gassign *> (def_stmt))
{
tree ssa[3];
- unsigned count = gimple_range_ssa_names (ssa, 3, ass);
+ unsigned count = gimple_range_ssa_names (ssa, 3, ass,
+ /*abnormal_ok=*/true);
for (unsigned j = 0; j < count; ++j)
if (add_to_exit_dependencies (ssa[j], dependencies))
worklist.safe_push (ssa[j]);
@@ -691,6 +696,8 @@ path_range_query::maybe_register_phi_relation (gphi *phi, edge e)
{
tree arg = gimple_phi_arg_def (phi, e->dest_idx);
+ // Deliberately not abnormal_ok: keep names occurring in abnormal
+ // PHIs out of the relation oracle.
if (!gimple_range_ssa_p (arg))
return;
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/backthread-computed-goto-2.c b/gcc/testsuite/gcc.dg/tree-ssa/backthread-computed-goto-2.c
new file mode 100644
index 00000000000..86d0f688210
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/backthread-computed-goto-2.c
@@ -0,0 +1,22 @@
+/* PR tree-optimization/126103 */
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdisable-tree-ethread -fdump-tree-threadfull1-details" } */
+
+int g;
+
+void
+h (int a)
+{
+ void *q;
+ if (a)
+ q = &&L0;
+ else
+ q = &&L2;
+L2:
+ g++;
+ goto *q;
+L0:
+ return;
+}
+
+/* { dg-final { scan-tree-dump-times "Registering jump thread" 2 "threadfull1" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-abnormal-phi-1.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-abnormal-phi-1.c
new file mode 100644
index 00000000000..7fe315fdea8
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-abnormal-phi-1.c
@@ -0,0 +1,46 @@
+/* PR tree-optimization/126103 */
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdisable-tree-ethread -fdump-tree-threadfull1-details" } */
+
+/* The conditional at "join" tests the result of an abnormal PHI:
+ t = PHI <k(ab), 0, 0>. Both normal predecessors feed constant 0,
+ so the backward threader must thread them past the conditional;
+ the abnormal predecessor keeps the original block. The two normal
+ predecessors of the computed goto also know its destination, so
+ they are threaded as well. */
+
+void foo (void);
+void bar (void);
+
+void
+f (int k)
+{
+ void *p = (k & 1) ? &&yes : &&join;
+ int t;
+
+ if (k > 0)
+ {
+ t = k;
+ goto *p;
+ }
+
+ if (k < -5)
+ {
+ foo ();
+ t = 0;
+ }
+ else
+ {
+ bar ();
+ t = 0;
+ }
+
+join:
+ if (t != 0)
+ {
+yes:
+ foo ();
+ }
+}
+
+/* { dg-final { scan-tree-dump-times "Registering jump thread" 4 "threadfull1" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-abnormal-phi-2.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-abnormal-phi-2.c
new file mode 100644
index 00000000000..8f74084ee2c
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-abnormal-phi-2.c
@@ -0,0 +1,45 @@
+/* PR tree-optimization/126103 */
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdisable-tree-ethread -fdump-tree-threadfull1-details" } */
+
+/* Like ssa-thread-abnormal-phi-1.c, but the conditional tests a value
+ derived from the abnormal PHI. */
+
+void foo (void);
+void bar (void);
+int g;
+
+void
+f (int k)
+{
+ void *p = (k & 1) ? &&yes : &&join;
+ int t;
+
+ if (k > 0)
+ {
+ t = k;
+ goto *p;
+ }
+
+ if (k < -5)
+ {
+ foo ();
+ t = 1;
+ }
+ else
+ {
+ bar ();
+ t = 0;
+ }
+
+join:
+ if (g)
+ bar ();
+ if ((t & 2) == 0)
+ {
+yes:
+ foo ();
+ }
+}
+
+/* { dg-final { scan-tree-dump-times "Registering jump thread" 6 "threadfull1" } } */
diff --git a/gcc/tree-ssa-threadbackward.cc b/gcc/tree-ssa-threadbackward.cc
index 77726ba66cd..dd33ccfd23b 100644
--- a/gcc/tree-ssa-threadbackward.cc
+++ b/gcc/tree-ssa-threadbackward.cc
@@ -450,17 +450,14 @@ back_threader::find_paths_to_names (basic_block bb, bitmap interesting,
}
/* Local PHIs participate in renaming below. */
if (gphi *phi = dyn_cast<gphi *> (def_stmt))
- {
- tree res = gimple_phi_result (phi);
- if (!SSA_NAME_OCCURS_IN_ABNORMAL_PHI (res))
- interesting_phis.safe_push (phi);
- }
+ interesting_phis.safe_push (phi);
/* For other local defs process their uses, amending
imports on the way. */
else
{
tree ssa[3];
- unsigned lim = gimple_range_ssa_names (ssa, 3, def_stmt);
+ unsigned lim = gimple_range_ssa_names (ssa, 3, def_stmt,
+ /*abnormal_ok=*/true);
for (unsigned j = 0; j < lim; ++j)
{
tree rhs = ssa[j];
@@ -564,7 +561,7 @@ back_threader::maybe_thread_block (basic_block bb)
tree name;
FOR_EACH_SSA_TREE_OPERAND (name, stmt, iter, SSA_OP_USE)
{
- if (!gimple_range_ssa_p (name))
+ if (!gimple_range_ssa_p (name, /*abnormal_ok=*/true))
return;
bitmap_set_bit (m_imports, SSA_NAME_VERSION (name));
}
--
2.47.3