Bug 49073 - [4.6/4.7 Regression] g++ optimizer breaks do-while code
Summary: [4.6/4.7 Regression] g++ optimizer breaks do-while code
Status: RESOLVED FIXED
Alias: None
Product: gcc
Classification: Unclassified
Component: tree-optimization (show other bugs)
Version: 4.6.0
: P3 normal
Target Milestone: 4.6.1
Assignee: Jakub Jelinek
URL:
Keywords:
Depends on:
Blocks:
 
Reported: 2011-05-20 00:34 UTC by pjr
Modified: 2011-05-20 14:38 UTC (History)
1 user (show)

See Also:
Host:
Target:
Build:
Known to work:
Known to fail:
Last reconfirmed: 2011-05-20 06:57:01


Attachments
The .ii file produced with g++ -v -save-temps -Wall -Wextra -o dow dow.cc (60.07 KB, application/octet-stream)
2011-05-20 00:34 UTC, pjr
Details
gcc46-pr49073.patch (1.20 KB, patch)
2011-05-20 09:47 UTC, Jakub Jelinek
Details | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description pjr 2011-05-20 00:34:29 UTC
Created attachment 24296 [details]
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
Comment 1 Jakub Jelinek 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.
Comment 2 Jakub Jelinek 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.
Comment 3 Jakub Jelinek 2011-05-20 09:47:43 UTC
Created attachment 24297 [details]
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;
}
Comment 4 Jakub Jelinek 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
Comment 5 Jakub Jelinek 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
Comment 6 Jakub Jelinek 2011-05-20 14:38:58 UTC
Fixed.