The code that threads incoming paths to a PHI is duplicating what we
do generically in find_paths_to_names. This shortcoming is actually
one of the reasons we aren't threading all possible paths into a PHI.
For example, we give up after finding one threadable path, but some
PHIs have multiple threadable paths:
// x_5 = PHI <10(4), 20(5), ...>
// if (x_5 > 5)
Addressing this not only fixes the oversight, but simplifies the
PHI handling code, since we can consider the PHI fully resolved upon
return.
Interestingly, for ssa-thread-12.c the main thread everything was
hinging on was unreachable. With this patch, we call
maybe_register_path() earlier. In doing so, the solver realizes
that any path starting with 4->8 is unreachable and can be avoided.
This caused the cascade of threadable paths that depended on this
to no longer happen. Since threadable paths in thread[34] was the only
thing this test was testing, there's no longer anything to test. Neat!
Tested on x86-64 Linux.
OK for trunk?
gcc/ChangeLog:
* tree-ssa-threadbackward.c (back_threader::resolve_phi):
Attempt to resolve all incoming paths to a PHI.
(back_threader::resolve_def): Always return true for PHIs.
gcc/testsuite/ChangeLog:
* gcc.dg/tree-ssa/pr21090.c: Adjust for threading.
* gcc.dg/tree-ssa/ssa-thread-12.c: Removed.
---
gcc/testsuite/gcc.dg/tree-ssa/pr21090.c | 2 +-
gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-12.c | 73 -------------------
gcc/tree-ssa-threadbackward.c | 70 +++++-------------
3 files changed, 21 insertions(+), 124 deletions(-)
delete mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-12.c
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr21090.c
b/gcc/testsuite/gcc.dg/tree-ssa/pr21090.c
index 3909adb72d4..92a87688601 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/pr21090.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr21090.c
@@ -1,5 +1,5 @@
/* { dg-do compile } */
-/* { dg-options "-O2 -fdisable-tree-evrp -fdump-tree-vrp1
-fdelete-null-pointer-checks" } */
+/* { dg-options "-O2 -fno-thread-jumps -fdisable-tree-evrp -fdump-tree-vrp1
-fdelete-null-pointer-checks" } */
int g, h;
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-12.c
b/gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-12.c
deleted file mode 100644
index 08c0b8d3bcc..00000000000
--- a/gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-12.c
+++ /dev/null
@@ -1,73 +0,0 @@
-/* { dg-do compile } */
-/* { dg-options "-O2 -fdump-tree-thread3-details -fdump-tree-thread4-details
-fno-finite-loops --param early-inlining-insns=14 -fno-inline-functions" } */
-/* { dg-final { scan-tree-dump "Registering jump thread" "thread3" } } */
-/* { dg-final { scan-tree-dump "Registering jump thread" "thread4" } } */
-
-typedef struct bitmap_head_def *bitmap;
-typedef const struct bitmap_head_def *const_bitmap;
-typedef struct VEC_int_base
-{
-}
-VEC_int_base;
-typedef struct VEC_int_heap
-{
- VEC_int_base base;
-}
-VEC_int_heap;
-typedef unsigned long BITMAP_WORD;
-typedef struct bitmap_element_def
-{
- struct bitmap_element_def *next;
- unsigned int indx;
-}
-bitmap_element;
-typedef struct bitmap_head_def
-{
-}
-bitmap_head;
-typedef struct
-{
- bitmap_element *elt1;
- bitmap_element *elt2;
- BITMAP_WORD bits;
-}
-bitmap_iterator;
-static __inline__ void
-bmp_iter_and_compl_init (bitmap_iterator * bi, const_bitmap map1,
- const_bitmap map2, unsigned start_bit,
- unsigned *bit_no)
-{
-}
-
-static __inline__ void
-bmp_iter_next (bitmap_iterator * bi, unsigned *bit_no)
-{
-}
-
-static __inline__ unsigned char
-bmp_iter_and_compl (bitmap_iterator * bi, unsigned *bit_no)
-{
- if (bi->bits)
- {
- while (bi->elt2 && bi->elt2->indx < bi->elt1->indx)
- bi->elt2 = bi->elt2->next;
- }
-}
-
-extern int VEC_int_base_length (VEC_int_base *);
-bitmap
-compute_idf (bitmap def_blocks, bitmap_head * dfs)
-{
- bitmap_iterator bi;
- unsigned bb_index, i;
- VEC_int_heap *work_stack;
- bitmap phi_insertion_points;
- while ((VEC_int_base_length (((work_stack) ? &(work_stack)->base : 0))) > 0)
- {
- for (bmp_iter_and_compl_init
- (&(bi), (&dfs[bb_index]), (phi_insertion_points), (0), &(i));
- bmp_iter_and_compl (&(bi), &(i)); bmp_iter_next (&(bi), &(i)))
- {
- }
- }
-}
diff --git a/gcc/tree-ssa-threadbackward.c b/gcc/tree-ssa-threadbackward.c
index edb396b3d6f..a6b9893abbd 100644
--- a/gcc/tree-ssa-threadbackward.c
+++ b/gcc/tree-ssa-threadbackward.c
@@ -83,7 +83,7 @@ private:
edge maybe_register_path ();
bool find_paths_to_names (basic_block bb, bitmap imports);
bool resolve_def (tree name, bitmap interesting, vec<tree> &worklist);
- bool resolve_phi (gphi *phi, bitmap imports);
+ void resolve_phi (gphi *phi, bitmap imports);
edge find_taken_edge (const vec<basic_block> &path);
edge find_taken_edge_cond (const vec<basic_block> &path, gcond *);
edge find_taken_edge_switch (const vec<basic_block> &path, gswitch *);
@@ -243,17 +243,14 @@ populate_worklist (vec<tree> &worklist, bitmap bits)
}
}
-// If taking any of the incoming edges to a PHI causes the final
-// conditional of the current path to be constant, register the
-// path(s), and return TRUE.
+// Find jump threading paths that go through a PHI.
-bool
+void
back_threader::resolve_phi (gphi *phi, bitmap interesting)
{
if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_phi_result (phi)))
- return true;
+ return;
- bool done = false;
for (size_t i = 0; i < gimple_phi_num_args (phi); ++i)
{
edge e = gimple_phi_arg_edge (phi, i);
@@ -275,53 +272,24 @@ back_threader::resolve_phi (gphi *phi, bitmap interesting)
continue;
}
- // FIXME: We currently stop looking if we find a threadable path
- // through a PHI. This is pessimistic, as there can be multiple
- // paths that can resolve the path. For example:
- //
- // x_5 = PHI <10(4), 20(5), ...>
- // if (x_5 > 5)
-
tree arg = gimple_phi_arg_def (phi, i);
- if (TREE_CODE (arg) == SSA_NAME)
- {
- unsigned v = SSA_NAME_VERSION (arg);
-
- // Avoid loops as in: x_5 = PHI <x_5(2), ...>.
- if (bitmap_bit_p (interesting, v))
- continue;
+ unsigned v = 0;
+ if (TREE_CODE (arg) == SSA_NAME
+ && !bitmap_bit_p (interesting, SSA_NAME_VERSION (arg)))
+ {
+ // Record that ARG is interesting when searching down this path.
+ v = SSA_NAME_VERSION (arg);
+ gcc_checking_assert (v != 0);
bitmap_set_bit (interesting, v);
bitmap_set_bit (m_imports, v);
+ }
- // When resolving unknowns, see if the incoming SSA can be
- // resolved on entry without having to keep looking back.
- bool keep_looking = true;
- if (m_resolve)
- {
- m_path.safe_push (e->src);
- if (maybe_register_path ())
- {
- keep_looking = false;
- m_visited_bbs.add (e->src);
- }
- m_path.pop ();
- }
- if (keep_looking)
- done |= find_paths_to_names (e->src, interesting);
+ find_paths_to_names (e->src, interesting);
- bitmap_clear_bit (interesting, v);
- }
- else if (TREE_CODE (arg) == INTEGER_CST)
- {
- m_path.safe_push (e->src);
- edge taken_edge = maybe_register_path ();
- if (taken_edge && taken_edge != UNREACHABLE_EDGE)
- done = true;
- m_path.pop ();
- }
+ if (v)
+ bitmap_clear_bit (interesting, v);
}
- return done;
}
// If the definition of NAME causes the final conditional of the
@@ -333,9 +301,11 @@ back_threader::resolve_def (tree name, bitmap interesting,
vec<tree> &worklist)
gimple *def_stmt = SSA_NAME_DEF_STMT (name);
// Handle PHIs.
- if (is_a<gphi *> (def_stmt)
- && resolve_phi (as_a<gphi *> (def_stmt), interesting))
- return true;
+ if (is_a<gphi *> (def_stmt))
+ {
+ resolve_phi (as_a<gphi *> (def_stmt), interesting);
+ return true;
+ }
// Defer copies of SSAs by adding the source to the worklist.
if (gimple_assign_single_p (def_stmt)
--
2.31.1
