[Bug c++/49073] New: g++ optimizer breaks do-while code

[Bug c++/49073] New: g++ optimizer breaks do-while code

[pjr at itee dot uq.edu.au]

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

           Summary: g++ optimizer breaks do-while code
           Product: gcc
           Version: 4.5.2
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: c++
        AssignedTo: unassigned@gcc.gnu.org
        ReportedBy: pjr@itee.uq.edu.au


Created attachment 24296
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=24296
The .ii file produced with g++ -v -save-temps -Wall -Wextra -o dow dow.cc

I recently installed Ubuntu 11.04 on a new 64bit laptop :
Linux Kernel: 2.6.38-8-generic
processor: i7-2620M
On trying to build a project of mine on the new laptop I found a problem that
appears to be related to the optimizer. Below is a simple example that exhibits
the problem - execution of a do-while loop.
With the optimizer off it appears to work OK but with any optimization on it
does not break out of the do-while loop as required. 

It works OK with optimization if I recode as a while loop.  

---- dow.cc ------
#include <iostream>
using namespace std;

int main()
{
  int a[] = {1,2,3,4,5,6,7};
  bool flag = false;
  int d = 1;
  int i = 1;
  do
    {
      d = a[i];
      if (flag && (d == 4))
        {
          cerr << "break" << endl;
          break;
        }
      i++;
      flag = (d == 3);
    } while (d < 7);

}
---------

Compiled as
g++ -Wall -Wextra -o dow dow.cc
and run as 
./dow
outputs 
break
(as it should)
Compiled with -O2
./dow
generates no output

[Bug c++/49073] g++ optimizer breaks do-while code

[jakub at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2011.05.20 06:57:01
                 CC|                            |jakub at gcc dot gnu.org
            Version|4.5.2                       |4.6.0
     Ever Confirmed|0                           |1

--- Comment #1 from Jakub Jelinek <jakub at gcc dot gnu.org> 2011-05-20 06:57:01 UTC ---
Confirmed for 4.6 and trunk, if you can reproduce it with 4.5, complain to
Ubuntu for backporting very risky patch that caused already more than one
regression.

Caused by http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=160445

Simplified testcase:
extern void abort (void);
int c;

int
main ()
{
  int a[] = { 1, 2, 3, 4, 5, 6, 7 }, d = 1, i = 1;
  _Bool f = 0;
  do
    {
      d = a[i];
      if (f && d == 4)
        {
          ++c;
          break;
        }
      i++;
      f = (d == 3);
    }
  while (d < 7);
  if (c != 1)
    abort ();
  return 0;
}

I'll have a look.

[Bug c++/49073] g++ optimizer breaks do-while code

[jakub at gcc dot gnu.org]

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

--- Comment #2 from Jakub Jelinek <jakub at gcc dot gnu.org> 2011-05-20 07:50:02 UTC ---
I think the bug is fairly obviously in and_comparisons_1 (and also in
or_comparisons_1), going through a PHI node needs to be done with lots of care.
We have:
<bb 3>:
  # i_1 = PHI <1(2), i_9(6)>
  # f_2 = PHI <0(2), f_10(6)>
  d_6 = a[i_1];
  if (f_2 != 0)
    goto <bb 4>;
  else
    goto <bb 6>;
<bb 4>:
  if (d_6 == 4)
    goto <bb 5>;
  else
    goto <bb 6>;
<bb 5>:
  c.0_7 = c;
  c.1_8 = c.0_7 + 1;
  c = c.1_8;
  goto <bb 7>;
<bb 6>:
  i_9 = i_1 + 1;
  f_10 = d_6 == 3;
  if (d_6 <= 6)
    goto <bb 3>;
  else
    goto <bb 7>;

and_comparisons_1 is called here with f_2 != 0 and d_6 == 4, it sees that
f_2 is a result of a PHI node, and performs as the comment says:
/* If every argument to the PHI produces the same result when
   ANDed with the second comparison, we win.  */
First PHI argument is 0, so it is 0 && d_6 == 4 then, and for the second case
it mistakenly follows on the SSA_NAME argument of the PHI, so f_10 and d_6 == 4
and we recurse into and_comparisons_1 with d_6 == 3 and d_6 == 4, which is of
course false.  The bug is that each of the d_6's is from a different loop
iteration.

So I think we need to give up if PHI argument is an SSA_NAME which might be
defined in a different iteration of a loop, probably some dominance checks
between the bb the PHI is defined and bb where the SSA_NAME is defined.

[Bug tree-optimization/49073] [4.6/4.7 Regression] g++ optimizer breaks do-while code

[jakub at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|---                         |4.6.1
            Summary|g++ optimizer breaks        |[4.6/4.7 Regression] g++
                   |do-while code               |optimizer breaks do-while
                   |                            |code

[Bug tree-optimization/49073] [4.6/4.7 Regression] g++ optimizer breaks do-while code

[jakub at gcc dot gnu.org]

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

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 #3 from Jakub Jelinek <jakub at gcc dot gnu.org> 2011-05-20 09:47:43 UTC ---
Created attachment 24297
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=24297
gcc46-pr49073.patch

Untested fix.

While I can imagine a testcase where the dominated_by_p CDI_DOMINATORS check
isn't sufficient, e.g. when a loop is entered in the middle as well, as
and_var_* and or_var_* immediately give up if the def stmt isn't a
GIMPLE_ASSIGN and I believe we need a GIMPLE_PHI in that case, it should
hopefully be enough this way.

Just for completeness, here is what I've been trying with -O2 -fno-tree-vrp:

extern void abort (void);
int c;
volatile int v;

__attribute__((noinline, noclone)) int
foo (int x)
{
  int a[] = { 1, 2, 3, 4, 5, 6, 7 }, d = 1, i = 1;
  _Bool f = 0;
  if (x == -1000)
    goto lab;
  do
    {
      v++;
    lab:
      d = a[i];
      if (f && d == 4)
{
  ++c;
  break;
}
      i++;
      f = (d == 3);
    }
  while (d < 7);
  if (c != 1)
    abort ();
  return 0;
}

int
main ()
{
  foo (v);
  return 0;
}

[Bug tree-optimization/49073] [4.6/4.7 Regression] g++ optimizer breaks do-while code

[jakub at gcc dot gnu.org]

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

--- Comment #4 from Jakub Jelinek <jakub at gcc dot gnu.org> 2011-05-20 14:19:07 UTC ---
Author: jakub
Date: Fri May 20 14:19:05 2011
New Revision: 173948

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=173948
Log:
    PR tree-optimization/49073
    * gimple-fold.c (and_comparisons_1, or_comparisons_1): Return
    NULL if PHI argument is SSA_NAME, whose def_stmt is dominated
    by the PHI.
    * tree-ssa-ifcombine.c (tree_ssa_ifcombine): Calculate dominators.

    * gcc.c-torture/execute/pr49073.c: New test.

Added:
    trunk/gcc/testsuite/gcc.c-torture/execute/pr49073.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/gimple-fold.c
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/tree-ssa-ifcombine.c

[Bug tree-optimization/49073] [4.6/4.7 Regression] g++ optimizer breaks do-while code

[jakub at gcc dot gnu.org]

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

--- Comment #5 from Jakub Jelinek <jakub at gcc dot gnu.org> 2011-05-20 14:35:23 UTC ---
Author: jakub
Date: Fri May 20 14:35:20 2011
New Revision: 173951

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=173951
Log:
    PR tree-optimization/49073
    * gimple-fold.c (and_comparisons_1, or_comparisons_1): Return
    NULL if PHI argument is SSA_NAME, whose def_stmt is dominated
    by the PHI.
    * tree-ssa-ifcombine.c (tree_ssa_ifcombine): Calculate dominators.

    * gcc.c-torture/execute/pr49073.c: New test.

Added:
    branches/gcc-4_6-branch/gcc/testsuite/gcc.c-torture/execute/pr49073.c
Modified:
    branches/gcc-4_6-branch/gcc/ChangeLog
    branches/gcc-4_6-branch/gcc/gimple-fold.c
    branches/gcc-4_6-branch/gcc/testsuite/ChangeLog
    branches/gcc-4_6-branch/gcc/tree-ssa-ifcombine.c

[Bug tree-optimization/49073] [4.6/4.7 Regression] g++ optimizer breaks do-while code

[jakub at gcc dot gnu.org]

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

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

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

--- Comment #6 from Jakub Jelinek <jakub at gcc dot gnu.org> 2011-05-20 14:38:58 UTC ---
Fixed.