[Bug tree-optimization/61009] New: Incorrect jump threading in dom

[Bug tree-optimization/61009] New: Incorrect jump threading in dom

[tejohnson at google dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=61009

            Bug ID: 61009
           Summary: Incorrect jump threading in dom
           Product: gcc
           Version: 4.10.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: tejohnson at google dot com

Created attachment 32709
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=32709&action=edit
t.C

We ran into a runtime failure that was tracked down to the jump threading
performed during the dom1 pass. I reproduced it with trunk (updated to
r209902).

I've attached a reduced test case. Build with:

g++ -fno-tree-vrp -O2 -std=c++11 -fno-strict-aliasing t.C -S

Unfortunately it isn't runnable, but the problem is apparent in the resulting
dumps/assembly.

The code initially looks like:

   for (int j = 0; j < NKF ; ++j) {
     int field_idx = idxs[j];
     int cmp = doCmp(row_offset, field_idx);
     fprintf (stderr, "cmp=%d\n",cmp);

     if (cmp == 0) {
       continue;
     }
     if (cmp > 0) {
       is_different = true;
       break;
     } else {
       fprintf (stderr, "Incorrect\n");
       return false;
     }
   }

But after dom1 jump threading it looks something like:

   for (int j = 0; j < NKF ; ++j) {
     int field_idx = idxs[j];
     int cmp = doCmp(row_offset, field_idx);
     fprintf (stderr, "cmp=%d\n",cmp);

     if (cmp == 0) {
       goto L1
     }
     if (cmp > 0) {
       is_different = true;
       break;
     } else {
ERROR:
       fprintf (stderr, "Incorrect\n");
       return false;
     }

L1:
     ++j;
     if (j >= NKF)
        break;

     field_idx = idxs[j];
     cmp = doCmp(row_offset, field_idx);
     fprintf (stderr, "cmp=%d\n",cmp);

     if (cmp == 0) {
       goto L1
     }
     goto ERROR
   }

Notice that after threading, the duplicated code wrongly simplifies away the
check of "cmp > 0".

I've also attached the dom1 dump. The problematic jump thread is this one:

  Registering jump thread: (14, 12) incoming edge;  (12, 4) joiner;  (4, 5)
nocopy;

Since some of these blocks (12 and 14) were created by the earlier dom
optimizations, I modified tree-ssa-threadupdate.c to dump the cfg when entering
thread_through_all_blocks. The attached dump includes that extra dump.

[Bug tree-optimization/61009] Incorrect jump threading in dom

[tejohnson at google dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=61009

--- Comment #1 from Teresa Johnson <tejohnson at google dot com> ---
Created attachment 32710
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=32710&action=edit
t.C.078t.dom1

[Bug tree-optimization/61009] Incorrect jump threading in dom

[pinskia at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=61009

--- Comment #2 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Most likely related to bug 60902.

[Bug tree-optimization/61009] Incorrect jump threading in dom

[ppluzhnikov at google dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=61009

Paul Pluzhnikov <ppluzhnikov at google dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |ppluzhnikov at google dot com

--- Comment #3 from Paul Pluzhnikov <ppluzhnikov at google dot com> ---
Google ref: b/14380607

[Bug tree-optimization/61009] Incorrect jump threading in dom

[ppluzhnikov at google dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=61009

--- Comment #4 from Paul Pluzhnikov <ppluzhnikov at google dot com> ---
(In reply to Andrew Pinski from comment #2)
> Most likely related to bug 60902.

Teresa, could you verify whether r209860 (for PR60902) fixes this one as well?

[Bug tree-optimization/61009] Incorrect jump threading in dom

[law at redhat dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=61009

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

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

--- Comment #5 from Jeffrey A. Law <law at redhat dot com> ---
I really doubt this is related to 60902.

[Bug tree-optimization/61009] Incorrect jump threading in dom

[tejohnson at google dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=61009

--- Comment #6 from Teresa Johnson <tejohnson at google dot com> ---
On Tue, Apr 29, 2014 at 2:46 PM, ppluzhnikov at google dot com
<gcc-bugzilla@gcc.gnu.org> wrote:
> http://gcc.gnu.org/bugzilla/show_bug.cgi?id=61009
>
> --- Comment #4 from Paul Pluzhnikov <ppluzhnikov at google dot com> ---
> (In reply to Andrew Pinski from comment #2)
>> Most likely related to bug 60902.
>
> Teresa, could you verify whether r209860 (for PR60902) fixes this one as well?

I thought it might be a dup of that too, but I updated today to
r209902 and the problem remains.
Thanks,
Teresa

>
> --
> You are receiving this mail because:
> You reported the bug.

[Bug tree-optimization/61009] Incorrect jump threading in dom

[law at redhat dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=61009

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2014-04-30
     Ever confirmed|0                           |1

[Bug tree-optimization/61009] Incorrect jump threading in dom

[law at redhat dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=61009

--- Comment #7 from Jeffrey A. Law <law at redhat dot com> ---
I see what's happening here...  I need to think about how best to handle this
situation.  Oh how threading across loop backedges perilous.

[Bug tree-optimization/61009] Incorrect jump threading in dom

[xinliangli at gmail dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=61009

davidxl <xinliangli at gmail dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |xinliangli at gmail dot com

--- Comment #8 from davidxl <xinliangli at gmail dot com> ---
(In reply to Jeffrey A. Law from comment #7)
> I see what's happening here...  I need to think about how best to handle
> this situation.  Oh how threading across loop backedges perilous.

Any update on this issue?

David

[Bug tree-optimization/61009] Incorrect jump threading in dom

[xinliangli at gmail dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=61009

--- Comment #10 from davidxl <xinliangli at gmail dot com> ---
(In reply to Jeffrey A. Law from comment #9)
> Sorry, personal issue taking an enormous amount of my time right now.  I
> have a fully tested patch and just need to twiddle the attached test into an
> executable testcase for the regression suite.

Can you post the early version of the patch? We can help test it with larger
test cases that exposed the problem in the first place.

David

[Bug tree-optimization/61009] Incorrect jump threading in dom

[law at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=61009

--- Comment #11 from Jeffrey A. Law <law at gcc dot gnu.org> ---
Author: law
Date: Fri May  9 04:54:00 2014
New Revision: 210254

URL: http://gcc.gnu.org/viewcvs?rev=210254&root=gcc&view=rev
Log:
2014-05-08  Jeff Law  <law@redhat.com>

    PR tree-optimization/61009
    * tree-ssa-threadedge.c (thread_through_normal_block): Return a
    tri-state rather than a boolean.  When a block is too big to
    thread through, inform caller via negative return value.
    (thread_across_edge): If a block was too big for normal threading,
    then it's too big for a joiner too, so remove temporary equivalences
    and return immediately.

    PR tree-optimization/61009
    * g++.dg/tree-ssa/pr61009.C: New test.

Added:
    trunk/gcc/testsuite/g++.dg/tree-ssa/pr61009.C
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/tree-ssa-threadedge.c

[Bug tree-optimization/61009] [4.9 Regression] Incorrect jump threading in dom

[tejohnson at google dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=61009

--- Comment #13 from Teresa Johnson <tejohnson at google dot com> ---
Jeff,

Thanks for the fix! Confirming that it does indeed fix the application
issues we hit.

Teresa

On Thu, May 8, 2014 at 9:54 PM, law at gcc dot gnu.org
<gcc-bugzilla@gcc.gnu.org> wrote:
> http://gcc.gnu.org/bugzilla/show_bug.cgi?id=61009
>
> --- Comment #11 from Jeffrey A. Law <law at gcc dot gnu.org> ---
> Author: law
> Date: Fri May  9 04:54:00 2014
> New Revision: 210254
>
> URL: http://gcc.gnu.org/viewcvs?rev=210254&root=gcc&view=rev
> Log:
> 2014-05-08  Jeff Law  <law@redhat.com>
>
>     PR tree-optimization/61009
>     * tree-ssa-threadedge.c (thread_through_normal_block): Return a
>     tri-state rather than a boolean.  When a block is too big to
>     thread through, inform caller via negative return value.
>     (thread_across_edge): If a block was too big for normal threading,
>     then it's too big for a joiner too, so remove temporary equivalences
>     and return immediately.
>
>     PR tree-optimization/61009
>     * g++.dg/tree-ssa/pr61009.C: New test.
>
> Added:
>     trunk/gcc/testsuite/g++.dg/tree-ssa/pr61009.C
> Modified:
>     trunk/gcc/ChangeLog
>     trunk/gcc/testsuite/ChangeLog
>     trunk/gcc/tree-ssa-threadedge.c
>
> --
> You are receiving this mail because:
> You reported the bug.

[Bug tree-optimization/61009] [4.9 Regression] Incorrect jump threading in dom

[ppluzhnikov at google dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=61009

--- Comment #14 from Paul Pluzhnikov <ppluzhnikov at google dot com> ---
(In reply to Teresa Johnson from comment #13)

> Thanks for the fix!

Indeed.

> Confirming that it does indeed fix the application
> issues we hit.

I will add that we've had at least two separate miscompile instances due to
this bug, resulting in several thousand of our unit test failing.

Back-porting this to gcc-4_9-branch should be a relatively high priority.

[Bug tree-optimization/61009] [4.9 Regression] Incorrect jump threading in dom

[law at redhat dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=61009

--- Comment #15 from Jeffrey A. Law <law at redhat dot com> ---
Paul, it is.  I'd be surprised if both threading fixes aren't in by Monday.

[Bug tree-optimization/61009] [4.9 Regression] Incorrect jump threading in dom

[law at gcc dot gnu.org]

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

--- Comment #16 from Jeffrey A. Law <law at gcc dot gnu.org> ---
Author: law
Date: Tue May 13 20:26:51 2014
New Revision: 210400

URL: http://gcc.gnu.org/viewcvs?rev=210400&root=gcc&view=rev
Log:
2014-05-08  Jeff Law  <law@redhat.com>

    PR tree-optimization/61009
    * tree-ssa-threadedge.c (thread_through_normal_block): Return a
    tri-state rather than a boolean.  When a block is too big to
    thread through, inform caller via negative return value.
    (thread_across_edge): If a block was too big for normal threading,
    then it's too big for a joiner too, so remove temporary equivalences
    and return immediately.

    PR tree-optimization/61009
    * g++.dg/tree-ssa/pr61009.C: New test.

Added:
    branches/gcc-4_9-branch/gcc/testsuite/g++.dg/tree-ssa/pr61009.C
Modified:
    branches/gcc-4_9-branch/gcc/ChangeLog
    branches/gcc-4_9-branch/gcc/testsuite/ChangeLog
    branches/gcc-4_9-branch/gcc/tree-ssa-threadedge.c

[Bug tree-optimization/61009] [4.9 Regression] Incorrect jump threading in dom

[law at redhat dot com]

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

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

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

--- Comment #17 from Jeffrey A. Law <law at redhat dot com> ---
Fix backported to branch.

[Bug tree-optimization/61009] [4.9 Regression] Incorrect jump threading in dom

[law at gcc dot gnu.org]

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

--- Comment #18 from Jeffrey A. Law <law at gcc dot gnu.org> ---
Author: law
Date: Thu Jun 12 17:12:18 2014
New Revision: 211586

URL: http://gcc.gnu.org/viewcvs?rev=211586&root=gcc&view=rev
Log:
        PR tree-optimization/61009
    * tree-ssa-threadedge.c (thread_through_normal_block): Correct return
    value when we stop processing a block due to problematic PHIs.

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

[Bug tree-optimization/61009] [4.9 Regression] Incorrect jump threading in dom

[law at gcc dot gnu.org]

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

--- Comment #19 from Jeffrey A. Law <law at gcc dot gnu.org> ---
Author: law
Date: Thu Jun 12 18:38:29 2014
New Revision: 211589

URL: http://gcc.gnu.org/viewcvs?rev=211589&root=gcc&view=rev
Log:
        PR tree-optimization/61009
    * tree-ssa-threadedge.c (thread_through_normal_block): Correct return
    value when we stop processing a block due to problematic PHIs.

Modified:
    branches/gcc-4_9-branch/gcc/ChangeLog
    branches/gcc-4_9-branch/gcc/tree-ssa-threadedge.c