[Bug tree-optimization/55018] New: CDDCE phase is too aggressive

[Bug tree-optimization/55018] New: CDDCE phase is too aggressive

[nmorey at kalray dot eu]

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

             Bug #: 55018
           Summary: CDDCE phase is too aggressive
    Classification: Unclassified
           Product: gcc
           Version: tree-ssa
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
        AssignedTo: unassigned@gcc.gnu.org
        ReportedBy: nmorey@kalray.eu


Created attachment 28502
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=28502
Source code to reproduce the bug

When compiling the attached source file with
 gcc  -O3 tmp.c -c

All the code from Sender_Signal function is removed during cddce2 phase.
The generated code only contains an empty infinite loop which is wrong.

Seen on:
Using built-in specs.
COLLECT_GCC=/usr/bin/gcc
COLLECT_LTO_WRAPPER=/usr/libexec/gcc/x86_64-redhat-linux/4.7.2/lto-wrapper
Target: x86_64-redhat-linux
Configured with: ../configure --prefix=/usr --mandir=/usr/share/man
--infodir=/usr/share/info --with-bugurl=http://bugzilla.redhat.com/bugzilla
--enable-bootstrap --enable-shared --enable-threads=posix
--enable-checking=release --disable-build-with-cxx
--disable-build-poststage1-with-cxx --with-system-zlib --enable-__cxa_atexit
--disable-libunwind-exceptions --enable-gnu-unique-object
--enable-linker-build-id --with-linker-hash-style=gnu
--enable-languages=c,c++,objc,obj-c++,java,fortran,ada,go,lto --enable-plugin
--enable-initfini-array --enable-java-awt=gtk --disable-dssi
--with-java-home=/usr/lib/jvm/java-1.5.0-gcj-1.5.0.0/jre
--enable-libgcj-multifile --enable-java-maintainer-mode
--with-ecj-jar=/usr/share/java/eclipse-ecj.jar --disable-libjava-multilib
--with-ppl --with-cloog --with-tune=generic --with-arch_32=i686
--build=x86_64-redhat-linux
Thread model: posix
gcc version 4.7.2 20120921 (Red Hat 4.7.2-2) (GCC)

[Bug tree-optimization/55018] CDDCE phase is too aggressive

[pinskia at gcc dot gnu.org]

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

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Version|tree-ssa                    |4.7.2

--- Comment #1 from Andrew Pinski <pinskia at gcc dot gnu.org> 2012-10-22 08:39:24 UTC ---
So it is removing an empty infinite loop?  Are you saying that is wrong?

[Bug tree-optimization/55018] CDDCE phase is too aggressive

[nmorey at kalray dot eu]

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

--- Comment #2 from Nicolas Morey-Chaisemartin <nmorey at kalray dot eu> 2012-10-22 08:41:12 UTC ---
The loop is infinite but should not be empty as it calls printf in the middle.

[Bug tree-optimization/55018] CDDCE pass is too aggressive sometimes with infinite loops

[pinskia at gcc dot gnu.org]

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

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|CDDCE phase is too          |CDDCE pass is too
                   |aggressive                  |aggressive sometimes with
                   |                            |infinite loops

--- Comment #3 from Andrew Pinski <pinskia at gcc dot gnu.org> 2012-10-22 08:43:22 UTC ---
Or rather it is removing code from an infinite loop.

[Bug tree-optimization/55018] CDDCE pass is too aggressive sometimes with infinite loops and with some builtin functions

[pinskia at gcc dot gnu.org]

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

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|CDDCE pass is too           |CDDCE pass is too
                   |aggressive sometimes with   |aggressive sometimes with
                   |infinite loops              |infinite loops and with
                   |                            |some builtin functions

--- Comment #4 from Andrew Pinski <pinskia at gcc dot gnu.org> 2012-10-22 08:45:39 UTC ---
If I change the printf to a just a normal function, CDDCE does not remove the
loop.

[Bug tree-optimization/55018] CDDCE pass is too aggressive sometimes with infinite loops and with some builtin functions

[nmorey at kalray dot eu]

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

--- Comment #5 from Nicolas Morey-Chaisemartin <nmorey at kalray dot eu> 2012-10-22 08:48:52 UTC ---
It does if it takes occurrence as a parameter:

#include <stdio.h>

extern void myFunc(int);

void Sender_signal(int Connect)
{
    int State = 3;
    int occurrence = 0;

    if (Connect) {
        State = 0;
    }

 start:


    if (Connect) {
        goto start;
    } 
    occurrence++;

    if(State != 2){
        myFunc(occurrence);
    }
    goto start;

}

[Bug tree-optimization/55018] [4.7/4.8 Regression] CDDCE pass is too aggressive sometimes with infinite loops and with some functions

[pinskia at gcc dot gnu.org]

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

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
      Known to work|                            |4.4.5
           Keywords|                            |wrong-code
   Last reconfirmed|                            |2012-10-22
                 CC|                            |pinskia at gcc dot gnu.org
     Ever Confirmed|0                           |1
            Summary|CDDCE pass is too           |[4.7/4.8 Regression] CDDCE
                   |aggressive sometimes with   |pass is too aggressive
                   |infinite loops and with     |sometimes with infinite
                   |some builtin functions      |loops and with some
                   |                            |functions
   Target Milestone|---                         |4.7.3
      Known to fail|                            |4.7.0, 4.8.0

--- Comment #6 from Andrew Pinski <pinskia at gcc dot gnu.org> 2012-10-22 08:54:43 UTC ---
(In reply to comment #5)
> It does if it takes occurrence as a parameter:

ok, I can now make a testcase which should exit but currently does not.
A Runtime testcase which works at -O1, -O2, and -O0 but goes into an infinite
loop at -O3:
void myFunc(int) __attribute__((noinline,noclone));
void myFunc(int a)
{
  if (a==100)
    __builtin_exit(0);
}

void Sender_signal(int Connect) __attribute__((noinline,noclone));
void Sender_signal(int Connect)
{
    int State = 3;
    int occurrence = 0;

    if (Connect) {
        State = 0;
    }

 start:

    if (Connect) {
        goto start;
    } 
    occurrence++;

    if(State != 2){
        myFunc(occurrence);
    }
    goto start;

}

int main(void)
{
  Sender_signal(0);
  return 0;
}

[Bug tree-optimization/55018] [4.7/4.8 Regression] CDDCE pass is too aggressive sometimes with infinite loops and with some functions

[rguenth at gcc dot gnu.org]

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

--- Comment #7 from Richard Biener <rguenth at gcc dot gnu.org> 2012-10-22 09:00:55 UTC ---
It's simple - you basically have

<bb 2>:
  if (Connect_5(D) != 0)
    goto <bb 4>;
  else
    goto <bb 5>;

<bb 3>:
  # occurrence_3 = PHI <0(5), occurrence_1(3)>
  # .MEM_17 = PHI <.MEM_9(D)(5), .MEM_2(3)>
  occurrence_1 = occurrence_3 + 1;
  # .MEM_2 = VDEF <.MEM_17>
  printf ("Sender_Signal  occurrence  %d \n", occurrence_1);
  goto <bb 3>;

and this invokes undefined behavior because occurrence_1 = occurrence_3 + 1
overflows.  Thus GCC is free to do anything.  Fixing the testcase doesn't
fix the code though:

void Sender_signal(int Connect)
{
  unsigned int occurrence = 0;
  int State = 3;
  if (Connect)
    State = 0;
start:
  if (Connect)
    goto start;
  occurrence++;
  if (State != 2)
    __builtin_printf("Sender_Signal occurrence %u\n", occurrence);
  goto start;
}

[Bug tree-optimization/55018] [4.6/4.7/4.8 Regression] CDDCE pass is too aggressive sometimes with infinite loops and with some functions

[rguenth at gcc dot gnu.org]

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

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
      Known to work|                            |4.5.4
   Target Milestone|4.7.3                       |4.6.4
            Summary|[4.7/4.8 Regression] CDDCE  |[4.6/4.7/4.8 Regression]
                   |pass is too aggressive      |CDDCE pass is too
                   |sometimes with infinite     |aggressive sometimes with
                   |loops and with some         |infinite loops and with
                   |functions                   |some functions
      Known to fail|                            |4.6.3

[Bug tree-optimization/55018] [4.6/4.7/4.8 Regression] CDDCE pass is too aggressive sometimes with infinite loops and with some functions

[jakub at gcc dot gnu.org]

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

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |jakub at gcc dot gnu.org

--- Comment #8 from Jakub Jelinek <jakub at gcc dot gnu.org> 2012-10-22 14:30:42 UTC ---
Yeah, I think this is a CDDCE bug, in particular incorrect assumption about
post-dominators in presence of infinite loops.
The problem is that with infinite loops, worst case all basic blocks on a path
from a conditional to an infinite loop that is control dependent on the
conditional can have fake edge to exit and therefore find_control_dependence
stops on those.

[Bug tree-optimization/55018] [4.6/4.7/4.8 Regression] CDDCE pass is too aggressive sometimes with infinite loops and with some functions

[jakub at gcc dot gnu.org]

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

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |ASSIGNED
         AssignedTo|unassigned at gcc dot       |jakub at gcc dot gnu.org
                   |gnu.org                     |

--- Comment #9 from Jakub Jelinek <jakub at gcc dot gnu.org> 2012-10-22 15:03:34 UTC ---
Created attachment 28508
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=28508
gcc48-pr55018.patch

Untested fix.  If such a bb has more than one succ edge, I think it ought to
have either a control stmt in it, or throwing stmt, so I think a bb with high
index (because calc_dfs_tree uses FOR_EACH_BB_REVERSE to find the still
unconnected bbs), on a path from a conditional to an infinite loop, that
doesn't contain any stmts marked already as necessary (on the testcase none at
all) is the only problem.

[Bug tree-optimization/55018] [4.6/4.7/4.8 Regression] CDDCE pass is too aggressive sometimes with infinite loops and with some functions

[steven at gcc dot gnu.org]

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

--- Comment #10 from Steven Bosscher <steven at gcc dot gnu.org> 2012-10-31 21:37:22 UTC ---
Author: steven
Date: Wed Oct 31 21:37:10 2012
New Revision: 193047

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=193047
Log:
gcc/
    PR tree-optimization/55018
    * basic-block.h (dfs_find_deadend): New prototype.
    * cfganal.c (dfs_find_deadend): No longer static.  Use bitmap
    instead of sbitmap for visited.
    (flow_dfs_compute_reverse_execute): Use dfs_find_deadend here, too.
    * dominance.c (calc_dfs_tree): If saw_unconnected,
    traverse from dfs_find_deadend of unconnected b
    instead of b directly.

testsuite/
    PR tree-optimization/55018
    * gcc.dg/torture/pr55018.c: New test.


Added:
    trunk/gcc/testsuite/gcc.dg/torture/pr55018.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/basic-block.h
    trunk/gcc/cfganal.c
    trunk/gcc/dominance.c
    trunk/gcc/testsuite/ChangeLog

[Bug tree-optimization/55018] [4.6/4.7 Regression] CDDCE pass is too aggressive sometimes with infinite loops and with some functions

[jakub at gcc dot gnu.org]

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

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|[4.6/4.7/4.8 Regression]    |[4.6/4.7 Regression] CDDCE
                   |CDDCE pass is too           |pass is too aggressive
                   |aggressive sometimes with   |sometimes with infinite
                   |infinite loops and with     |loops and with some
                   |some functions              |functions

--- Comment #11 from Jakub Jelinek <jakub at gcc dot gnu.org> 2012-11-07 11:38:15 UTC ---
Fixed by Steven for trunk.  Caused some regressions, but those are tracked
elsewhere.

[Bug tree-optimization/55018] [4.6/4.7 Regression] CDDCE pass is too aggressive sometimes with infinite loops and with some functions

[rguenth at gcc dot gnu.org]

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

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Priority|P3                          |P2

[Bug tree-optimization/55018] [4.7 Regression] CDDCE pass is too aggressive sometimes with infinite loops and with some functions

[jakub at gcc dot gnu.org]

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

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.6.4                       |4.7.4

--- Comment #12 from Jakub Jelinek <jakub at gcc dot gnu.org> 2013-04-12 15:16:34 UTC ---
GCC 4.6.4 has been released and the branch has been closed.

[Bug tree-optimization/55018] [4.7 Regression] CDDCE pass is too aggressive sometimes with infinite loops and with some functions

[rguenth at gcc dot gnu.org]

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

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
      Known to work|                            |4.8.0
         Resolution|---                         |FIXED
   Target Milestone|4.7.4                       |4.8.0
      Known to fail|4.8.0                       |4.7.4

--- Comment #13 from Richard Biener <rguenth at gcc dot gnu.org> ---
Fixed for 4.8.0.