[Bug tree-optimization/61607] DOM missed jump threading and destroyed loops

[Bug tree-optimization/61607] DOM missed jump threading and destroyed loops

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61607

--- Comment #1 from Richard Biener <rguenth at gcc dot gnu.org> ---
Optimizing block #5

1>>> COND 1 = i_1 ge_expr R_6(D)
1>>> COND 0 = i_1 lt_expr R_6(D)
LKUP STMT inter0p_13 = PHI <inter0p_2>
          inter0p_13 = PHI <inter0p_2(4)>
2>>> STMT inter0p_13 = PHI <inter0p_2>
          inter0p_13 = PHI <inter0p_2(4)>
LKUP STMT inter1p_14 = PHI <inter0p_2>
          inter1p_14 = PHI <inter0p_2(4)>
FIND: inter0p_2
0>>> COPY inter1p_14 = inter0p_2

At least record_equivalences_from_phis sets the SSA value of both to inter0p_2.

But we don't propagate inter0p_2 into the conditionals because of

      /* Do not propagate copies if the propagated value is at a deeper loop
         depth than the propagatee.  Otherwise, this may move loop variant
         variables outside of their loops and prevent coalescing
         opportunities.  If the value was loop invariant, it will be hoisted
         by LICM and exposed for copy propagation.  */
      if (loop_depth_of_name (val) > loop_depth_of_name (op))
        return;

as inter0p_2 is defined inside the loop.  Note that we don't replace
inter1p_14 by inter0p_13 either because we recorded inter0p_2 for that
as well ...

So it seems the above limitation should be enforced in a different way
(or removed).  I don't get what the comment is after anyway...  both
FRE and PRE don't care and do the propagation (and the CSE).

[Bug tree-optimization/61607] DOM missed jump threading and destroyed loops

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61607

--- Comment #2 from Richard Biener <rguenth at gcc dot gnu.org> ---
With the propagation limitation removed we get

  Registering jump thread: (2, 4) incoming edge;  (4, 5) joiner;  (5, 7)
normal;
  Cancelling jump thread: (2, 4) incoming edge;  (4, 5) joiner;  (5, 7) normal;
Jump threading proved probability of edge 7->9 too small (it is 3900, should be
5000).
  Threaded jump 5 --> 7 to 10
fix_loop_structure: removing loop 1
flow_loops_find: discovered new loop 2 with header 4

  <bb 5>:
  # inter0p_13 = PHI <inter0p_2(4)>
  # inter1p_14 = PHI <inter0p_2(4)>
  if (inter0p_2 != 0)
    goto <bb 6>;
  else
    goto <bb 10>;

  <bb 6>:
  inter[0] = 1;

  <bb 7>:
  if (inter0p_2 != 0)
    goto <bb 8>;
  else
    goto <bb 9>;

  <bb 8>:
  inter[1] = 1;

  <bb 9>:
  foo (&inter);
  inter ={v} {CLOBBER};
  return;

  <bb 10>:
  goto <bb 9>;

that still misses the threading of the true path.  And it still destroys
loop info from:

static bool
thread_block_1 (basic_block bb, bool noloop_only, bool joiners)
{
...
  /* If we thread the latch of the loop to its exit, the loop ceases to
     exist.  Make sure we do not restrict ourselves in order to preserve
     this loop.  */
  if (loop->header == bb)
    {
      e = loop_latch_edge (loop);
      vec<jump_thread_edge *> *path = THREAD_PATH (e);

      if (path
          && (((*path)[1]->type == EDGE_COPY_SRC_JOINER_BLOCK && joiners)
              || ((*path)[1]->type == EDGE_COPY_SRC_BLOCK && !joiners)))
        {
          for (unsigned int i = 1; i < path->length (); i++)
            {
              edge e2 = (*path)[i]->e;

              if (loop_exit_edge_p (loop, e2))
                {
                  loop->header = NULL;
                  loop->latch = NULL;
                  loops_state_set (LOOPS_NEED_FIXUP);

but it seems we cancel the threading later...

(gdb) 
913                   delete_jump_thread_path (path);

so it would be better if we destroyed the loop only if necessary
(I would have expected the actual edge redirection code takes care of that).
Cancelling loops unnecessarily is very bad.

[Bug tree-optimization/61607] DOM missed jump threading and destroyed loops

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61607

--- Comment #3 from Richard Biener <rguenth at gcc dot gnu.org> ---
Like with

Index: gcc/tree-ssa-threadupdate.c
===================================================================
--- gcc/tree-ssa-threadupdate.c (revision 211969)
+++ gcc/tree-ssa-threadupdate.c (working copy)
@@ -764,6 +764,14 @@ ssa_redirect_edges (struct redirection_d
          if ((*path)[1]->type != EDGE_COPY_SRC_JOINER_BLOCK)
            EDGE_SUCC (rd->dup_blocks[0], 0)->count += e->count;

+         /* If we redirect a loop latch edge cancel its loop.  */
+         if (e->src == e->src->loop_father->latch)
+           {
+             e->src->loop_father->header = NULL;
+             e->src->loop_father->latch = NULL;
+             loops_state_set (LOOPS_NEED_FIXUP);
+           }
+
          /* Redirect the incoming edge (possibly to the joiner block) to the
             appropriate duplicate block.  */
          e2 = redirect_edge_and_branch (e, rd->dup_blocks[0]);
@@ -853,32 +861,6 @@ thread_block_1 (basic_block bb, bool nol
   redirection_data
     = new hash_table<struct redirection_data> (EDGE_COUNT (bb->succs));

-  /* If we thread the latch of the loop to its exit, the loop ceases to
-     exist.  Make sure we do not restrict ourselves in order to preserve
-     this loop.  */
-  if (loop->header == bb)
-    {
-      e = loop_latch_edge (loop);
-      vec<jump_thread_edge *> *path = THREAD_PATH (e);
-
-      if (path
-         && (((*path)[1]->type == EDGE_COPY_SRC_JOINER_BLOCK && joiners)
-             || ((*path)[1]->type == EDGE_COPY_SRC_BLOCK && !joiners)))
-       {
-         for (unsigned int i = 1; i < path->length (); i++)
-           {
-             edge e2 = (*path)[i]->e;
-
-             if (loop_exit_edge_p (loop, e2))
-               {
-                 loop->header = NULL;
-                 loop->latch = NULL;
-                 loops_state_set (LOOPS_NEED_FIXUP);
-               }
-           }
-       }
-    }
-
   /* Record each unique threaded destination into a hash table for
      efficient lookups.  */
   FOR_EACH_EDGE (e, ei, bb->preds)

[Bug tree-optimization/61607] DOM missed jump threading and destroyed loops

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61607

--- Comment #4 from Richard Biener <rguenth at gcc dot gnu.org> ---
Author: rguenth
Date: Thu Jun 26 07:44:10 2014
New Revision: 212011

URL: https://gcc.gnu.org/viewcvs?rev=212011&root=gcc&view=rev
Log:
2014-06-26  Richard Biener  <rguenther@suse.de>

    PR tree-optimization/61607
    * tree-ssa-threadupdate.c (ssa_redirect_edges): Cancel the
    loop if we redirected its latch edge.
    (thread_block_1): Do not cancel loops prematurely.

Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/tree-ssa-threadupdate.c

[Bug tree-optimization/61607] DOM missed jump threading and destroyed loops

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61607

--- Comment #5 from Richard Biener <rguenth at gcc dot gnu.org> ---
Author: rguenth
Date: Thu Jun 26 11:29:34 2014
New Revision: 212026

URL: https://gcc.gnu.org/viewcvs?rev=212026&root=gcc&view=rev
Log:
2014-06-26  Richard Biener  <rguenther@suse.de>

    PR tree-optimization/61607
    * tree-ssa-copy.c (copy_prop_visit_phi_node): Adjust comment
    explaining why we restrict copies on loop depth.
    * tree-ssa-dom.c (cprop_operand): Remove restriction on
    on loop depth.
    (record_equivalences_from_phis): Instead add it here.

    * gcc.dg/tree-ssa/ssa-dom-thread-5.c: New testcase.

Added:
    trunk/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-5.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/tree-ssa-copy.c
    trunk/gcc/tree-ssa-dom.c

[Bug tree-optimization/61607] DOM missed jump threading and destroyed loops

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61607

--- Comment #6 from Richard Biener <rguenth at gcc dot gnu.org> ---
The bogus loop cancelling is fixed as well as the equivalence recording.  Still
DOM does

  Registering jump thread: (3, 4) incoming edge;  (4, 5) joiner;  (5, 6)
normal;
  Registering jump thread: (5, 7) incoming edge;  (7, 9) normal;
  Registering jump thread: (2, 4) incoming edge;  (4, 5) joiner;  (5, 7)
normal;
  Cancelling jump thread: (2, 4) incoming edge;  (4, 5) joiner;  (5, 7) normal;
  Threaded jump 5 --> 7 to 10

with result

  <bb 5>:
  # inter_I_lsm.3_24 = PHI <inter_I_lsm.3_10(4)>
  # inter_I_lsm.4_25 = PHI <inter_I_lsm.4_11(4)>
  # inter_I_lsm.5_26 = PHI <inter_I_lsm.5_12(4)>
  # inter_I_lsm.6_27 = PHI <inter_I_lsm.4_11(4)>
  if (inter_I_lsm.4_25 != 0)
    goto <bb 6>;
  else
    goto <bb 10>;

  <bb 6>:
  inter[0] = inter_I_lsm.3_24;

  <bb 7>:
  if (inter_I_lsm.4_25 != 0)
    goto <bb 8>;
  else
    goto <bb 9>;

  <bb 8>:
  inter[1] = inter_I_lsm.5_26;

  <bb 9>:
  foo (&inter);
  inter ={v} {CLOBBER};
  return;

  <bb 10>:
  goto <bb 9>;

but no attempt at threading of

  (5, 6) incoming edge -> (6->7) joiner -> (7 -> 8) normal

VRP simplfies the conditional to true afterwards - so maybe this is just
a missed simplification-after-threading in DOM?  Without VRP the
redundant conditional stays.  It still looks like a trivial missing thing to
adjust the jump we thread through ...?

[Bug tree-optimization/61607] DOM missed jump threading and destroyed loops

[law at redhat dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61607

Jeffrey A. Law <law at redhat dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |law at redhat dot com

--- Comment #7 from Jeffrey A. Law <law at redhat dot com> ---
In my testing, the missed thread is due to not following the chain of
SSA_NAME_VALUEs.  We ought to easily discover that the two conditionals outside
the loop are in fact equivalent and fully threadable.


With a quick hack to follow the chain of values we're able to trivially
discover both of the interesting jump threading opportunities:

k.c.079t.dom1:  Registering jump thread: (6, 7) incoming edge;  (7, 8) normal;
k.c.079t.dom1:  Registering jump thread: (5, 7) incoming edge;  (7, 9) normal;

[Bug tree-optimization/61607] DOM missed jump threading and destroyed loops

[law at redhat dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61607

--- Comment #9 from Jeffrey A. Law <law at redhat dot com> ---
So, the length of the SSA_NAME_VALUE chains is pretty much as expected.  The
overwhelming majority of the time there is nothing in the SSA_NAME_VALUE chain
or a single entry.  Then there's a very small percentage with a length of 2 and
roughly the same very small percentage that have a loop.

So we can reasonably iterate over the chain and break if we hit > 2 entries in
the chain.

[Bug tree-optimization/61607] DOM missed jump threading and destroyed loops

[law at redhat dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61607

Jeffrey A. Law <law at redhat dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |RESOLVED
         Resolution|---                         |FIXED

--- Comment #10 from Jeffrey A. Law <law at redhat dot com> ---
Fixed by change to follow SSA_NAME_VALUE chains on the trunk + richi's
improvements.

[Bug tree-optimization/61607] DOM missed jump threading and destroyed loops

[yroux at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61607

--- Comment #11 from Yvan Roux <yroux at gcc dot gnu.org> ---
Author: yroux
Date: Thu Mar  5 14:28:05 2015
New Revision: 221216

URL: https://gcc.gnu.org/viewcvs?rev=221216&root=gcc&view=rev
Log:
gcc/
2015-03-05  Yvan Roux  <yvan.roux@linaro.org>

    Backport from trunk r212011, r214942, r214957, r215012, r215016, r218115,
    r218733, r218746, r220491.
    2015-02-06  Sebastian Pop  <s.pop@samsung.com>
            Brian Rzycki  <b.rzycki@samsung.com>

    PR tree-optimization/64878
    * tree-ssa-threadedge.c: Include tree-ssa-loop.h.
    (fsm_find_control_statement_thread_paths): Add parameter seen_loop_phi.
    Stop recursion at loop phi nodes after having visited a loop phi node.

    2014-12-15  Richard Biener  <rguenther@suse.de>

    PR middle-end/64246
    * cfgloop.c (mark_loop_for_removal): Make safe against multiple
    invocations on the same loop.

    2014-12-15  Richard Biener  <rguenther@suse.de>

    PR tree-optimization/64284
    * tree-ssa-threadupdate.c (duplicate_seme_region): Mark
    the loop for removal if we copied the loop header.

    2014-11-27  Richard Biener  <rguenther@suse.de>

    PR tree-optimization/64083
    * tree-ssa-threadupdate.c (thread_through_all_blocks): Do not
    forcibly mark loop for removal the wrong way.

    2014-09-08  Richard Biener  <rguenther@suse.de>

    PR ipa/63196
    * tree-inline.c (copy_loops): The source loop header should
    always be non-NULL.
    (tree_function_versioning): If loops need fixup after removing
    unreachable blocks fix them.
    * omp-low.c (simd_clone_adjust): Do not add incr block to
    loop under construction.

    2014-09-08  Richard Biener  <rguenther@suse.de>

    PR bootstrap/63204
    * cfgloop.c (mark_loop_for_removal): Track former header
    unconditionally.
    * cfgloop.h (struct loop): Add former_header member unconditionally.
    * loop-init.c (fix_loop_structure): Enable bogus loop removal
    diagnostic unconditionally.

    2014-09-05  Richard Biener  <rguenther@suse.de>

    * cfgloop.c (mark_loop_for_removal): Record former header
    when ENABLE_CHECKING.
    * cfgloop.h (strut loop): Add former_header member when
    ENABLE_CHECKING.
    * loop-init.c (fix_loop_structure): Sanity check loops
    marked for removal if they re-appeared.

    2014-09-05  Richard Biener  <rguenther@suse.de>

    * cfgloop.c (mark_loop_for_removal): New function.
    * cfgloop.h (mark_loop_for_removal): Declare.
    * cfghooks.c (delete_basic_block): Use mark_loop_for_removal.
    (merge_blocks): Likewise.
    (duplicate_block): Likewise.
    * except.c (sjlj_emit_dispatch_table): Likewise.
    * tree-eh.c (cleanup_empty_eh_merge_phis): Likewise.
    * tree-ssa-threadupdate.c (ssa_redirect_edges): Likewise.
    (thread_through_loop_header): Likewise.

    2014-06-26  Richard Biener  <rguenther@suse.de>

    PR tree-optimization/61607
    * tree-ssa-threadupdate.c (ssa_redirect_edges): Cancel the
    loop if we redirected its latch edge.
    (thread_block_1): Do not cancel loops prematurely.

gcc/testsuite/
2015-03-05  Yvan Roux  <yvan.roux@linaro.org>

    Backport from trunk r218115, r218733, r218746, r220491.
    2015-02-06  Sebastian Pop  <s.pop@samsung.com>
            Brian Rzycki  <b.rzycki@samsung.com>

    PR tree-optimization/64878
    * testsuite/gcc.dg/tree-ssa/ssa-dom-thread-8.c: New.

    2014-12-15  Richard Biener  <rguenther@suse.de>

    PR middle-end/64246
    * gnat.dg/opt46.adb: New testcase.
    * gnat.dg/opt46.ads: Likewise.
    * gnat.dg/opt46_pkg.adb: Likewise.
    * gnat.dg/opt46_pkg.ads: Likewise.

    2014-12-15  Richard Biener  <rguenther@suse.de>

    PR tree-optimization/64284
    * gcc.dg/torture/pr64284.c: New testcase.

    2014-11-27  Richard Biener  <rguenther@suse.de>

    PR tree-optimization/64083
    * gcc.dg/torture/pr64083.c: New testcase.


Added:
    branches/linaro/gcc-4_9-branch/gcc/testsuite/gcc.dg/torture/pr64083.c
    branches/linaro/gcc-4_9-branch/gcc/testsuite/gcc.dg/torture/pr64284.c
   
branches/linaro/gcc-4_9-branch/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-8.c
    branches/linaro/gcc-4_9-branch/gcc/testsuite/gnat.dg/opt46.adb
    branches/linaro/gcc-4_9-branch/gcc/testsuite/gnat.dg/opt46.ads
    branches/linaro/gcc-4_9-branch/gcc/testsuite/gnat.dg/opt46_pkg.adb
    branches/linaro/gcc-4_9-branch/gcc/testsuite/gnat.dg/opt46_pkg.ads
Modified:
    branches/linaro/gcc-4_9-branch/gcc/ChangeLog.linaro
    branches/linaro/gcc-4_9-branch/gcc/cfghooks.c
    branches/linaro/gcc-4_9-branch/gcc/cfgloop.c
    branches/linaro/gcc-4_9-branch/gcc/cfgloop.h
    branches/linaro/gcc-4_9-branch/gcc/except.c
    branches/linaro/gcc-4_9-branch/gcc/loop-init.c
    branches/linaro/gcc-4_9-branch/gcc/omp-low.c
    branches/linaro/gcc-4_9-branch/gcc/testsuite/ChangeLog.linaro
    branches/linaro/gcc-4_9-branch/gcc/tree-eh.c
    branches/linaro/gcc-4_9-branch/gcc/tree-inline.c
    branches/linaro/gcc-4_9-branch/gcc/tree-ssa-threadedge.c
    branches/linaro/gcc-4_9-branch/gcc/tree-ssa-threadupdate.c