The following allows the backward thread through a loop header
to exit, allowing it to fully peel a not iterating loop on a
threading path. The backward thread copier cannot handle copying
loops, but this special case is OK and is also handled by the
forward threader. We have to take care to not randomly peel
loops though, not even after loop opts, so this patch adds
appropriate measures and a testcase.
Bootstrapped and tested on x86_64-unknown-linux-gnu, pushed.
PR tree-optimization/126887
* tree-ssa-threadbackward.cc (back_threader::find_paths_to_names):
Allow to search past a loop header in case we are threading a
loop exit test.
* tree-ssa-threadupdate.cc
(back_jt_path_registry::duplicate_thread_path): Properly
detect when a entered subloop is dissolved by threading,
but avoid creating new entries into the original loop.
(jt_path_registry::cancel_invalid_paths): Do not allow
peeling loops.
* gcc.dg/tree-ssa/ssa-thread-23.c: New testcase.
* gcc.dg/tree-ssa/ssa-thread-24.c: Likewise.
---
gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-23.c | 19 +++++++++++++++++++
gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-24.c | 19 +++++++++++++++++++
gcc/tree-ssa-threadbackward.cc | 14 ++++++--------
gcc/tree-ssa-threadupdate.cc | 18 ++++++++++++++++--
4 files changed, 60 insertions(+), 10 deletions(-)
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-23.c
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-24.c
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-23.c
b/gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-23.c
new file mode 100644
index 00000000000..a7896e4e57c
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-23.c
@@ -0,0 +1,19 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+
+volatile unsigned sink;
+
+void
+f (int flag, unsigned n)
+{
+ unsigned i = 0;
+ do
+ {
+ sink = i;
+ i += 1;
+ }
+ while (i != 128);
+}
+
+/* We should not peel this loop. */
+/* { dg-final { scan-tree-dump-times "sink" 1 "optimized" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-24.c
b/gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-24.c
new file mode 100644
index 00000000000..dae43512a17
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-24.c
@@ -0,0 +1,19 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 --param dom-jump-threading=0 -fdump-tree-thread2-stats" }
*/
+volatile unsigned sink;
+
+void
+f (int flag, unsigned n)
+{
+ unsigned i = flag ? 0 : n;
+ do
+ {
+ sink = i;
+ i += 4;
+ }
+ while (i != 4);
+}
+
+/* We should thread the path when i starts at 0 through loop exit. */
+/* { dg-final { scan-tree-dump "Jumps threaded: 1" "thread2" } } */
+/* { dg-final { scan-tree-dump-times "sink" 2 "thread2" } } */
diff --git a/gcc/tree-ssa-threadbackward.cc b/gcc/tree-ssa-threadbackward.cc
index ca1af87bb40..20bb74c507f 100644
--- a/gcc/tree-ssa-threadbackward.cc
+++ b/gcc/tree-ssa-threadbackward.cc
@@ -396,6 +396,7 @@ back_threader::find_paths_to_names (basic_block bb, bitmap
interesting,
// edge might help here. Alternatively copying divergent control flow
// on the way to the backedge could be worthwhile.
bool large_non_fsm;
+ edge e;
if (m_path.length () > 1
&& (!profit.possibly_profitable_path_p (m_path, &large_non_fsm)
|| (!large_non_fsm
@@ -405,7 +406,10 @@ back_threader::find_paths_to_names (basic_block bb, bitmap
interesting,
// The backwards thread copier cannot copy blocks that do not belong
// to the same loop, so when the new source of the path entry no
// longer belongs to it we don't need to search further.
- else if (m_path[0]->loop_father != bb->loop_father)
+ else if (m_path[0]->loop_father != bb->loop_father
+ && (!(e = loop_exits_from_bb_p (m_path[0]->loop_father,
+ m_path[0]))
+ || e->dest->loop_father != bb->loop_father))
;
// Continue looking for ways to extend the path but limit the
@@ -481,13 +485,7 @@ back_threader::find_paths_to_names (basic_block bb, bitmap
interesting,
FOR_EACH_EDGE (e, iter, bb->preds)
{
if (e->flags & EDGE_ABNORMAL
- // This is like path_crosses_loops in profitable_path_p but
- // more restrictive to avoid peeling off loop iterations (see
- // tree-ssa/pr14341.c for an example).
- // ??? Note this restriction only applied when visiting an
- // interesting PHI with the former resolve_phi.
- || (!interesting_phis.is_empty ()
- && m_path[0]->loop_father != e->src->loop_father))
+ || e->src->index == ENTRY_BLOCK)
continue;
for (gphi *phi : interesting_phis)
{
diff --git a/gcc/tree-ssa-threadupdate.cc b/gcc/tree-ssa-threadupdate.cc
index db3520b42fc..91c2c1788ef 100644
--- a/gcc/tree-ssa-threadupdate.cc
+++ b/gcc/tree-ssa-threadupdate.cc
@@ -2407,8 +2407,15 @@ back_jt_path_registry::duplicate_thread_path (edge entry,
for (i = 0; i < n_region; i++)
{
/* We do not handle subloops, i.e. all the blocks must belong to the
- same loop. */
- if (region[i]->loop_father != loop)
+ same loop. Unless we thread to the subloop exit and thus the
+ path will belong to loop after the threading. */
+ if ((region[i]->loop_father != loop
+ && !(loop_exit_edge_p (region[i]->loop_father, exit)
+ && exit->dest->loop_father == loop))
+ /* Avoid creating alternate entries into the original loop. */
+ || (loop->header == entry->dest
+ && region[i] != exit->src
+ && EDGE_COUNT (region[i]->succs) > 1))
return false;
}
@@ -2812,6 +2819,13 @@ jt_path_registry::cancel_invalid_paths
(vec<jump_thread_edge *> &path)
&& flow_loop_nested_p (exit->dest->loop_father, exit->src->loop_father))
return false;
+ if (seen_latch && entry->dest == loop->header)
+ {
+ cancel_thread (&path, "Threading through latch from loop header "
+ "peels loop");
+ return true;
+ }
+
if (cfun->curr_properties & PROP_loop_opts_done)
return false;
--
2.51.0
