[Bug tree-optimization/18694] New: [4.0 regression] loop miscompilation at -O1

[Bug tree-optimization/18694] New: [4.0 regression] loop miscompilation at -O1

[falk at debian dot org]

[forwarded from http://bugs.debian.org/280972]

gcc version 4.0.0 20041127 (experimental)

% gcc div.c && ./a.out 
1 2 4 8 5 10 20 40 25 50 100 200 125 250 500 1000 
% gcc -O1 div.c && ./a.out 
zsh: segmentation fault (core dumped)  ./a.out

The original reporter says he gets bogus output instead of a segfault.
This doesn't happen with gcc 3.3 or 3.4. Neither -fno-strict-aliasing
nor -fno-ivopts helps.

-- 
           Summary: [4.0 regression] loop miscompilation at -O1
           Product: gcc
           Version: 4.0.0
            Status: UNCONFIRMED
          Keywords: wrong-code
          Severity: normal
          Priority: P2
         Component: tree-optimization
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: falk at debian dot org
                CC: gcc-bugs at gcc dot gnu dot org
 GCC build triplet: alphaev68-unknown-linux-gnu
  GCC host triplet: alphaev68-unknown-linux-gnu
GCC target triplet: alphaev68-unknown-linux-gnu


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

[Bug tree-optimization/18694] [4.0 regression] loop miscompilation at -O1

[falk at debian dot org]

------- Additional Comments From falk at debian dot org  2004-11-27 22:53 -------
Created an attachment (id=7619)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=7619&action=view)
Test case


-- 


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

[Bug tree-optimization/18694] [4.0 regression] loop miscompilation at -O1 (-ftree-loop-ch)

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2004-11-27 22:56 -------
Confirmed, I don't know if this is fully a tree loop copy header (-ftree-loop-ch) bug or just something it 
does changes something else.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |rakdver at gcc dot gnu dot
                   |                            |org
             Status|UNCONFIRMED                 |NEW
     Ever Confirmed|                            |1
   Last reconfirmed|0000-00-00 00:00:00         |2004-11-27 22:56:51
               date|                            |
            Summary|[4.0 regression] loop       |[4.0 regression] loop
                   |miscompilation at -O1       |miscompilation at -O1 (-
                   |                            |ftree-loop-ch)
   Target Milestone|---                         |4.0.0


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

[Bug tree-optimization/18694] [4.0 regression] loop miscompilation at -O1 (-ftree-ch)

[rakdver at gcc dot gnu dot org]

------- Additional Comments From rakdver at gcc dot gnu dot org  2004-11-28 11:40 -------
A bit simpler testcase; no longer segfaults, but produces wrong output.  The 
reason seems to be the same (both are due to fields of t after the second
one not being initialized).

.vars dump is misscompiled (body of the innermost loop is executed only in the 
first iteration of the outer loop), so the problem is on tree level.

-- 


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

[Bug tree-optimization/18694] [4.0 regression] loop miscompilation at -O1 (-ftree-ch)

[rakdver at gcc dot gnu dot org]

------- Additional Comments From rakdver at gcc dot gnu dot org  2004-11-28 18:08 -------
The misscompilation appears in the .t54.dom3 dump.  With
-fno-tree-dominator-opts the testcase is not misscompiled.

-- 


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

[Bug tree-optimization/18694] [4.0 regression] loop miscompilation at -O1 (-ftree-ch)

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2004-11-28 18:13 -------
This is most likely related to PR 18241.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
  BugsThisDependsOn|                            |18241


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

[Bug tree-optimization/18694] [4.0 regression] loop miscompilation at -O1 (-ftree-ch)

[steven at gcc dot gnu dot org]

------- Additional Comments From steven at gcc dot gnu dot org  2004-12-04 13:56 -------
$ ./xgcc -B. -O2 t.c
$ ./a.out
1 2 5476394742290156872
$ ./xgcc -B. -O2 t.c -fno-tree-dce
$ ./a.out
1 2 4




-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
   Last reconfirmed|2004-11-27 22:56:51         |2004-12-04 13:56:43
               date|                            |


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

[Bug tree-optimization/18694] [4.0 regression] loop miscompilation at -O1 (-ftree-ch)

[steven at gcc dot gnu dot org]

------- Additional Comments From steven at gcc dot gnu dot org  2004-12-04 14:40 -------
Simpler test case:

#include <stdlib.h>
#include <stdio.h>
typedef long *GEN;

static inline long *
stoi(long n)
{
  long * z=(long *)malloc(sizeof(long));
  *z=n;
  return z;
}

void
divisors_bug(long * *t, long e)
{
  long j;
  long **d, **old_d, **act_d, **tmp;

  d = t;
  *++d = stoi(1);
  for (old_d=t,j=e; j; j--)
    {
      for (act_d=d, tmp=old_d; tmp < act_d; )
        *++d = stoi(**++tmp * 2);
      old_d=act_d;
    }
}

int main(void)
{
  long *t[4];
  long i;

  divisors_bug(t,2);
  for(i=1;i<4;i++)
    printf("%ld ",*t[i]);
  printf("\n");
  return 0;
}

When I comment out the first PHI-OPT pass, this gives:
1 2 4

With PHI-OPT not commented out, I get:
1 2 0


-- 


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

[Bug tree-optimization/18694] [4.0 regression] loop miscompilation at -O1 (-ftree-ch)

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2004-12-04 14:59 -------
(In reply to comment #8)
> Simpler test case:
> 
> When I comment out the first PHI-OPT pass, this gives:
> 1 2 4
> 
> With PHI-OPT not commented out, I get:
> 1 2 0

Are you sure because I cannot reproduce it when comment out the frist phiopt pass.  This is on ppc-
darwin by the way.  I still get a bus error.

-- 


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

[Bug tree-optimization/18694] [4.0 regression] loop miscompilation at -O1 (-ftree-ch)

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2004-12-04 17:43 -------
DOM is defintely messing it up

before
if (d_2 > tmp_14) goto <L1>; else goto <L3>;
after:
if (t_6 < d_8) goto <L1>; else goto <L3>;

the comparision changed

-- 


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

[Bug tree-optimization/18694] [4.0 regression] loop miscompilation at -O1 (-ftree-ch)

[steven at gcc dot gnu dot org]

------- Additional Comments From steven at gcc dot gnu dot org  2004-12-04 23:26 -------
Looks like a jump threading problem.  Given this test case: 
 
void 
divisors_bug(long *t, long e) 
{ 
  long int *d2; 
  long int *tmp; 
  long int *act_d; 
  long int *old_d; 
  long int *d; 
  long int j; 
  int t1, t2; 
 
  d = t; 
  ++d; 
  *d = 1; 
  old_d = t; 
  j = e; 
 
outer_loop_test: 
  if (j != 0) goto outer_loop_entry; else goto outer_loop_exit; 
 
outer_loop_entry: 
  d2 = d; 
  tmp = old_d; 
 
  inner_loop_test: 
    if (d <= tmp) goto inner_loop_exit; 
    d2++; 
    tmp++; 
    t1 = *tmp; 
    t2 = t1 * 2; 
    *d2 = t2; 
    goto inner_loop_test; 
 
  inner_loop_exit: 
  j = j - 1; 
  old_d = d; 
  d = d2; 
  goto outer_loop_test; 
 
outer_loop_exit: 
  return; 
} 
 
 
I have the following in one of the dominator passes: 
 
divisors_bug (t, e) 
{ 
  void inner_loop_exit = <<< error >>>; 
  void inner_loop_test = <<< error >>>; 
  void outer_loop_exit = <<< error >>>; 
  void outer_loop_entry = <<< error >>>; 
  void outer_loop_test = <<< error >>>; 
  int t2; 
  int t1; 
  long int j; 
  long int * d; 
  long int * old_d; 
  long int * act_d; 
  long int * tmp; 
  long int * d2; 
  long int D.1484; 
  long int D.1483; 
 
  # BLOCK 0 
  # PRED: ENTRY 
  d_8 = t_6 + 8B; 
  #   TMT.0_26 = V_MAY_DEF <TMT.0_25>; 
  *d_8 = 1; 
  if (e_10 != 0) goto <L14>; else goto <L6>; 
  # SUCC: 2 5 
 
  # BLOCK 1 
  # PRED: 4 
outer_loop_test:; 
  if (j_14 != 0) goto <L14>; else goto <L6>; 
  # SUCC: 2 5 
 
  # BLOCK 2 
  # PRED: 0 1 
  # TMT.0_23 = PHI <TMT.0_26(0), TMT.0_9(1)>; 
  # j_3 = PHI <e_10(0), j_14(1)>; 
  # old_d_2 = PHI <t_6(0), d_1(1)>; 
  # d_1 = PHI <d_8(0), d2_7(1)>; 
  # TMT.0_16 = PHI <TMT.0_26(0), TMT.0_9(1)>; 
  # tmp_15 = PHI <t_6(0), d_1(1)>; 
  # d2_13 = PHI <d_8(0), d2_7(1)>; 
<L14>:; 
  if (d_1 <= tmp_15) goto inner_loop_exit; else goto <L15>; 
  # SUCC: 4 3 
 
  # BLOCK 3 
  # PRED: 2 3 
  # TMT.0_12 = PHI <TMT.0_16(2), TMT.0_27(3)>; 
  # d2_11 = PHI <d2_13(2), d2_17(3)>; 
  # tmp_5 = PHI <tmp_15(2), tmp_18(3)>; 
<L15>:; 
  d2_17 = d2_11 + 8B; 
  tmp_18 = tmp_5 + 8B; 
  #   VUSE <TMT.0_12>; 
  D.1483_19 = *tmp_18; 
  t1_20 = (int) D.1483_19; 
  t2_21 = t1_20 * 2; 
  D.1484_22 = (long int) t2_21; 
  #   TMT.0_27 = V_MAY_DEF <TMT.0_12>; 
  *d2_17 = D.1484_22; 
  if (d_1 <= tmp_18) goto inner_loop_exit; else goto <L15>; 
  # SUCC: 4 3 
 
  # BLOCK 4 
  # PRED: 3 2 6 
  # TMT.0_9 = PHI <TMT.0_27(3), TMT.0_16(2), TMT.0_16(6)>; 
  # d2_7 = PHI <d2_17(3), d2_13(2), d2_13(6)>; 
inner_loop_exit:; 
  j_14 = j_3 - 1; 
  goto <bb 1> (outer_loop_test); 
  # SUCC: 1 
 
  # BLOCK 5 
  # PRED: 1 0 
<L6>:; 
  return; 
  # SUCC: EXIT 
 
  # BLOCK 6 
  # PRED: 
  # TMT.0_23 = PHI <>; 
  # j_3 = PHI <>; 
  # old_d_2 = PHI <>; 
  # d_1 = PHI <>; 
  # TMT.0_16 = PHI <>; 
  # tmp_15 = PHI <>; 
  # d2_13 = PHI <>; 
  goto <bb 4> (inner_loop_exit); 
  # SUCC: 4 
 
} 
 
 
which we turn into this: 
 
divisors_bug (t, e) 
{ 
  void inner_loop_exit = <<< error >>>; 
  void inner_loop_test = <<< error >>>; 
  void outer_loop_exit = <<< error >>>; 
  void outer_loop_entry = <<< error >>>; 
  void outer_loop_test = <<< error >>>; 
  int t2; 
  int t1; 
  long int j; 
  long int * d; 
  long int * old_d; 
  long int * act_d; 
  long int * tmp; 
  long int * d2; 
  long int D.1484; 
  long int D.1483; 
 
  # BLOCK 0 
  # PRED: ENTRY 
  d_8 = t_6 + 8B; 
  #   TMT.0_26 = V_MAY_DEF <TMT.0_25>; 
  *d_8 = 1; 
  if (e_10 != 0) goto <L14>; else goto <L6>; 
  # SUCC: 2 5 
 
  # BLOCK 1 
  # PRED: 4 
outer_loop_test:; 
  if (j_14 != 0) goto <L18>; else goto <L6>; 
  # SUCC: 6 5 
 
  # BLOCK 2 
  # PRED: 0 
  # TMT.0_23 = PHI <TMT.0_26(0)>; 
  # j_3 = PHI <e_10(0)>; 
  # old_d_2 = PHI <t_6(0)>; 
  # d_1 = PHI <d_8(0)>; 
  # TMT.0_16 = PHI <TMT.0_26(0)>; 
  # tmp_15 = PHI <t_6(0)>; 
  # d2_13 = PHI <d_8(0)>; 
<L14>:; 
  if (d_1 <= tmp_15) goto inner_loop_exit; else goto <L15>; 
  # SUCC: 4 3 
 
  # BLOCK 3 
  # PRED: 2 3 
  # TMT.0_12 = PHI <TMT.0_16(2), TMT.0_27(3)>; 
  # d2_11 = PHI <d2_13(2), d2_17(3)>; 
  # tmp_5 = PHI <tmp_15(2), tmp_18(3)>; 
<L15>:; 
  d2_17 = d2_11 + 8B; 
  tmp_18 = tmp_5 + 8B; 
  #   VUSE <TMT.0_12>; 
  D.1483_19 = *tmp_18; 
  t1_20 = (int) D.1483_19; 
  t2_21 = t1_20 * 2; 
  D.1484_22 = (long int) t2_21; 
  #   TMT.0_27 = V_MAY_DEF <TMT.0_12>; 
  *d2_17 = D.1484_22; 
  if (d_1 <= tmp_18) goto inner_loop_exit; else goto <L15>; 
  # SUCC: 4 3 
 
  # BLOCK 4 
  # PRED: 3 2 6 
  # TMT.0_9 = PHI <TMT.0_27(3), TMT.0_16(2), TMT.0_16(6)>; 
  # d2_7 = PHI <d2_17(3), d2_13(2), d2_13(6)>; 
inner_loop_exit:; 
  j_14 = j_3 - 1; 
  goto <bb 1> (outer_loop_test); 
  # SUCC: 1 
 
  # BLOCK 5 
  # PRED: 1 0 
<L6>:; 
  return; 
  # SUCC: EXIT 
 
  # BLOCK 6 
  # PRED: 1 
  # TMT.0_23 = PHI <TMT.0_9(1)>; 
  # j_3 = PHI <j_14(1)>; 
  # old_d_2 = PHI <d_1(1)>; 
  # d_1 = PHI <d2_7(1)>; 
  # TMT.0_16 = PHI <TMT.0_9(1)>; 
  # tmp_15 = PHI <d_1(1)>; 
  # d2_13 = PHI <d2_7(1)>; 
<L18>:; 
  goto <bb 4> (inner_loop_exit); 
  # SUCC: 4 
 
} 
 
Note that when optimizing basic block 3, we do a jump thread: 
Optimizing statement <L15>:; 
Optimizing statement d2_17 = d2_11 + 8B; 
Optimizing statement tmp_18 = tmp_5 + 8B; 
Optimizing statement D.1483_19 = *tmp_18; 
Optimizing statement t1_20 = (int) D.1483_19; 
Optimizing statement t2_21 = t1_20 * 2; 
Optimizing statement D.1484_22 = (long int) t2_21; 
Optimizing statement *d2_17 = D.1484_22; 
Optimizing statement if (d_1 <= tmp_18) goto inner_loop_exit; else goto <L15>; 
  Threaded jump 1 --> 2 to 6 
 
This is the only transformation we do in DOM in this case, and apparently 
it's not a correct one (but it's late so I'll leave it for Pinski to look 
at it more closely :-) 
 

-- 


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

[Bug tree-optimization/18694] [4.0 regression] loop miscompilation at -O1 (-ftree-ch)

[steven at gcc dot gnu dot org]

------- Additional Comments From steven at gcc dot gnu dot org  2004-12-08 22:18 -------
extern int printf (__const char *__restrict __format, ...); 
 
void 
divisors_bug(long *t, long e, long P) 
{ 
  long j; 
  long *d, *old_d, *act_d, *tmp; 
 
  d = t; 
  *++d = 5; 
  old_d = t; 
  for (j = e; j; j--) 
    { 
      act_d = d; 
      tmp = old_d; 
      while (tmp < act_d) 
        *++d = *(++tmp); 
      old_d=act_d; 
    } 
} 
 
int main(void) 
{ 
  long t[4]; 
  long i; 
 
  divisors_bug(t,2,2); 
  for(i=1;i<4;i++) 
    printf("%ld ",t[i]); 
  printf("\n"); 
  return 0; 
} 
 
Expected output: 5 5 5 
Output with -O1: 5 5 garbage 
 

-- 


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

[Bug tree-optimization/18694] [4.0 regression] loop miscompilation at -O1 (-ftree-ch)

[kazu at cs dot umass dot edu]

------- Additional Comments From kazu at cs dot umass dot edu  2004-12-09 00:47 -------
I took Steven's testcase in comment #12,
fed into GCC,
took its .t13.cfg output,
reformatted into C code,
fed that back into GCC with -O0,
and now I get the "5 5 garbage".

I separated main() to a separate file by the way.
Otherwise, I don't see the problem. 

int
divisors_bug (int *t, int e)
{
  int * d;
  int * ivtmp7;
  int * D1176;
  unsigned int ivtmp14;
  int * d22;
  unsigned int e0;
  int D1132;

  d = t + 1;
  *d = 5;
  if (e != 0) goto L2; else goto L7;

 L22:;
  ivtmp7 = D1176;

 L1:;
  d22 = d22 + 1;
  D1176 = ivtmp7 + 1;
  D1132 = *D1176;
  *d22 = D1132;
  if (d > D1176) goto L22; else goto L3;

 L3:;
  ivtmp14 = 0;

 L24:;
  ivtmp14 = ivtmp14 + 1;
  e0 = (unsigned int) e;
  if (e0 != ivtmp14) goto L24; else goto L7;

 L2:;
  if (t < d) goto L23; else goto L3;

 L23:;
  d22 = d;
  ivtmp7 = t;
  goto L1;

 L7:;
  return;
}



-- 


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

[Bug tree-optimization/18694] [4.0 regression] loop miscompilation at -O1 (-ftree-ch)

[kazu at cs dot umass dot edu]

------- Additional Comments From kazu at cs dot umass dot edu  2004-12-09 00:58 -------
Forget about comment #13.
My bad.


-- 


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

[Bug tree-optimization/18694] [4.0 regression] loop miscompilation at -O1 (-ftree-ch)

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2004-12-09 01:01 -------
(In reply to comment #12)
Here is a testcase which might be slightly easy to understand it should do (removes *a++):
extern int printf (__const char *__restrict __format, ...); 
 
void 
divisors_bug(long *t, long e, long P) 
{ 
  long int * tmp;
  long int * act_d;
  long int * old_d;
  long int * d;
  long int j;
  
  d = t + 1;
  *d = 5;
  old_d = t;
  j = e;
  while (j != 0) {
    act_d = d;
    tmp = old_d;
    while (tmp < act_d) {
      d++;
      tmp++;
      *d = *tmp;
    }
    old_d = act_d;
    j--;
  }
} 
 
int main(void) 
{ 
  long t[4]; 
  long i; 
  divisors_bug(t,2,2); 
  for(i=1;i<4;i++) 
    printf("%ld ",t[i]); 
  printf("\n"); 
  return 0; 
} 


-- 


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

[Bug tree-optimization/18694] [4.0 regression] loop miscompilation at -O1 (-ftree-ch)

[kazu at cs dot umass dot edu]

------- Additional Comments From kazu at cs dot umass dot edu  2004-12-09 01:32 -------
Here is a complete testcase that fails at DOM1.
With -O0, this testcase prints "5 5 5".
With -O1, this testcase prints "5 5 0".

I generated this testcase from final_cleanup after disabling DOM[123].

extern int printf (__const char *__restrict __format, ...); 
 
void
divisors_bug (int *t, unsigned int e)
{
  int * d23;
  unsigned int ivtmp14;
  int * ivtmp7;
  int * d;
  int * tmp;

  d23 = t + 1;
  *d23 = 5;
  if (e != 0) goto L24; else goto L6;

L24:
  tmp = t;
  d = d23;
  ivtmp14 = 0;
  goto L2;

L22:
  ivtmp7 = tmp;

L1:
  d23 = d23 + 1;
  *d23 = *(ivtmp7 + 1);
  ivtmp7 = ivtmp7 + 1;
  if (d > ivtmp7) goto L1; else goto L4;

L4:
  ivtmp14 = ivtmp14 + 1;
  if (e != ivtmp14) goto L23; else goto L6;

L23:
  tmp = d;
  d = d23;

L2:
  if (d > tmp) goto L22; else goto L4;

L6:
  return;
}

int
main (void)
{
  int t[4];
  int i;

  divisors_bug (t,2);
  for(i = 1; i < 4; i++)
    printf ("%d ", t[i]);
  printf ("\n");
  return 0;
}

-- 


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

[Bug tree-optimization/18694] [4.0 regression] loop miscompilation at -O1 (-ftree-ch)

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2004-12-09 01:33 -------
And here is a testcase which aborts and it is independent of storing to memory:
extern void abort (void);

void 
divisors_bug(long t, long e, long P) 
{ 
  long int tmp;
  long int act_d;
  long int old_d;
  long int d;
  long int j;
  
  d = t + 1;
  old_d = t;
  j = e;
  while (j != 0) {
    act_d = d;
    tmp = old_d;
    while (tmp < act_d) {
      d++;
      tmp++;
    }
    if (tmp != act_d)
      abort ();
    old_d = act_d;
    j--;
  }
} 
 
int main(void) 
{
  divisors_bug(0,2,2); 
  return 0; 
} 

-- 


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

[Bug tree-optimization/18694] [4.0 regression] loop miscompilation at -O1 (-ftree-ch)

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2004-12-09 01:46 -------
(In reply to comment #16)
> Here is a complete testcase that fails at DOM1.
> With -O0, this testcase prints "5 5 5".
> With -O1, this testcase prints "5 5 0".
> 
> I generated this testcase from final_cleanup after disabling DOM[123].

Lets look at the SSA level for this:
L23:;
  tmp_15 = d_5;
  d_16 = d23_2;

  # ivtmp14_6 = PHI <ivtmp14_13(1), ivtmp14_14(5)>;
  # d_5 = PHI <d_12(1), d_16(5)>;
  # tmp_4 = PHI <tmp_11(1), tmp_15(5)>;
  # d23_3 = PHI <d23_9(1), d23_2(5)>;
L2:;
  if (tmp_4 < d_5) goto L22; else goto L4;


See we know that this if condition cannot be proven false or true but DOM thinks is false always coming 
from BB 5 (aka L23).

[20:45] < kazu> if you are coming from bb 1, the condition is ultimately tmp_11 < d_12.  From bb 5, 
the condition is ultimately tmp_15 < d_16.


-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |law at gcc dot gnu dot org


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

[Bug tree-optimization/18694] [4.0 regression] loop miscompilation at -O1 (-ftree-ch)

[kazu at cs dot umass dot edu]

------- Additional Comments From kazu at cs dot umass dot edu  2004-12-09 02:14 -------
DOM1 is translating tmp_4 < d_5 (in L2:) into d23_2 < d23_2,
which would be false.

So the threader itself doesn't seem to be broken.  Something else is.



-- 


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

[Bug tree-optimization/18694] [4.0 regression] loop miscompilation at -O1 (-ftree-ch)

[kazu at cs dot umass dot edu]

------- Additional Comments From kazu at cs dot umass dot edu  2004-12-09 02:51 -------
Here are the PHI nodes that I am getting at L2 in thread_across_edge
called on edge L23 -> L2.

TMT.0_24 = PHI <TMT.0_26(1), TMT.0_23(5)>;
ivtmp14_6 = PHI <0(1), ivtmp14_14(5)>;
d_5 = PHI <d23_9(1), d23_2(5)>;   <- defined
tmp_4 = PHI <t_8(1), d_5(5)>;     <- used
d23_3 = PHI <d23_9(1), d23_2(5)>;

Note that d_5 is defined *and* used.
At this point, it's not safe to use SSA_NAME_VALUE for d_5.


-- 


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

[Bug tree-optimization/18694] [4.0 regression] loop miscompilation at -O1 (-ftree-ch)

[kazu at cs dot umass dot edu]

------- Additional Comments From kazu at cs dot umass dot edu  2004-12-09 03:26 -------
I meant:
At this point, it's not safe to use SSA_NAME_VALUE for tmp_4.

Maybe we shouldn't add equivalence of tmp_4 and d_5 in the first place
if d_5 is also defined in a PHI node at the same BB.


-- 


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

[Bug tree-optimization/18694] [4.0 regression] loop miscompilation at -O1 (-ftree-ch)

[kazu at cs dot umass dot edu]

------- Additional Comments From kazu at cs dot umass dot edu  2004-12-09 05:24 -------
Updated the testcase like so:

/* PR tree-optimization/18694

   The dominator optimization didn't take the PHI evaluation order
   into account when threading an edge.  */

extern void abort (void) __attribute__((noreturn));
extern void exit (int) __attribute__((noreturn));

void __attribute__((noinline))
foo (int i)
{
  int next_n = 1;
  int j = 0;

  for (; i != 0; i--)
    {
      int n;

      for (n = next_n; j < n; j++)
	next_n++;

      if (j != n)
	abort ();
    }
}

int
main (void)
{
  foo (2);
  exit (0);
}


-- 


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

[Bug tree-optimization/18694] [4.0 regression] loop miscompilation at -O1 (-ftree-ch)

[schwab at suse dot de]

------- Additional Comments From schwab at suse dot de  2004-12-09 14:19 -------
The patch does no good on ia64, it causes the stage2 compiler to be  
miscompiled.  

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |schwab at suse dot de


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

[Bug tree-optimization/18694] [4.0 regression] loop miscompilation at -O1 (-ftree-ch)

[law at redhat dot com]

------- Additional Comments From law at redhat dot com  2004-12-09 16:20 -------
Subject: Re:  [4.0 regression] loop
	miscompilation at -O1 (-ftree-ch)

On Thu, 2004-12-09 at 02:51 +0000, kazu at cs dot umass dot edu wrote:
> ------- Additional Comments From kazu at cs dot umass dot edu  2004-12-09 02:51 -------
> Here are the PHI nodes that I am getting at L2 in thread_across_edge
> called on edge L23 -> L2.
> 
> TMT.0_24 = PHI <TMT.0_26(1), TMT.0_23(5)>;
> ivtmp14_6 = PHI <0(1), ivtmp14_14(5)>;
> d_5 = PHI <d23_9(1), d23_2(5)>;   <- defined
> tmp_4 = PHI <t_8(1), d_5(5)>;     <- used
> d23_3 = PHI <d23_9(1), d23_2(5)>;
> 
> Note that d_5 is defined *and* used.
> At this point, it's not safe to use SSA_NAME_VALUE for d_5.
Presumably these PHIs are at the start of a loop?  (Otherwise
we have a use that is not dominated by its def).

It shouldn't be terribly hard to build a map of the PHI defs
and if we see a use, then record nothing into our tables.  But
I'd like to sit down and rethink that code a little -- the way
it handles loops is, err STUPID.  The nice thing is fixing how
it handles loops would go a long way towards the long standing
need to improve the selection code for jump threading.

I'm deep inside revamping tree-ssa-alias.c to make it do sane
things for 15855.  But I'll try to put those changes on hold
and deal with 18694 since 18694 represents a mis-compilation.

jeff



-- 


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

[Bug tree-optimization/18694] [4.0 regression] loop miscompilation at -O1 (-ftree-ch)

[law at redhat dot com]

------- Additional Comments From law at redhat dot com  2004-12-09 16:47 -------
Subject: Re:  [4.0 regression] loop
	miscompilation at -O1 (-ftree-ch)

On Thu, 2004-12-09 at 14:19 +0000, schwab at suse dot de wrote:
> ------- Additional Comments From schwab at suse dot de  2004-12-09 14:19 -------
> The patch does no good on ia64, it causes the stage2 compiler to be  
> miscompiled. 
Any chance you could do a little analysis on this?  All Kazu's change
does is cause us to ignore certain (bogus) equivalences.  If that's
causing stage2 to be mis-compiled, then, well we've clearly got deeper
problems.

Having at least a rough idea of the root cause of the ia64 failure 
would be good as I can keep that issue in mind as a rethink how the
jump thread selection code ought to work when dealing with loops.

You might be able to at least get some idea of the failure mode by
looking at what jumps are threaded by DOM before/after Kazu's patch.
That may be faster than actually sitting down with the debugger to
figure out what's being mis-compiled.

Jeff



-- 


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

[Bug tree-optimization/18694] [4.0 regression] loop miscompilation at -O1 (-ftree-ch)

[kazu at cs dot umass dot edu]

------- Additional Comments From kazu at cs dot umass dot edu  2004-12-09 16:58 -------
With my old patch (conservative-dom), stmt.c was miscompiled on my machine.
stage2/cc1 crashes on compiling crtstuff.c.
Replacing stmt.o with stage1/stmt.o worked for me.


-- 


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

[Bug tree-optimization/18694] [4.0 regression] loop miscompilation at -O1 (-ftree-ch)

[kazu at cs dot umass dot edu]

------- Additional Comments From kazu at cs dot umass dot edu  2004-12-09 16:59 -------
Jeff,

I agree with your comment #26.


-- 


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

[Bug tree-optimization/18694] [4.0 regression] loop miscompilation at -O1 (-ftree-ch)

[law at redhat dot com]

------- Additional Comments From law at redhat dot com  2004-12-09 17:38 -------
Subject: Re:  [4.0 regression] loop
	miscompilation at -O1 (-ftree-ch)

On Thu, 2004-12-09 at 16:58 +0000, kazu at cs dot umass dot edu wrote:
> ------- Additional Comments From kazu at cs dot umass dot edu  2004-12-09 16:58 -------
> With my old patch (conservative-dom), stmt.c was miscompiled on my machine.
> stage2/cc1 crashes on compiling crtstuff.c.
> Replacing stmt.o with stage1/stmt.o worked for me.
I'll work from that.  It ought to be enough for me to to see if one of
my theories about ignoring equivalences applies.

jeff




-- 


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

[Bug tree-optimization/18694] [4.0 regression] loop miscompilation at -O1 (-ftree-ch)

[kazu at cs dot umass dot edu]

------- Additional Comments From kazu at cs dot umass dot edu  2004-12-09 19:22 -------
Jeff,

With my new patch, stmt.i gets one fewer jump threading opportunities
(compared to what the vanilla mainline produces).
So it's very plausible that we are miscompiling stmt.c quietly.

This difference comes from DOM1 while compiling stmt.c:expand_asm_operands.

I hope this helps.

With my old patch, I got one more jump threading opportunity
(compared to what the vanilla mainline produces).
It was one of loop.i, stmt.i, and predict.i.

Since my old patch gives less information to lookup routines,
the increase in the number of opportunity seems very strange.

If you want, I can find out which of DOM[123] is causing this problem
on which function in which file for you.


-- 


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

[Bug tree-optimization/18694] [4.0 regression] loop miscompilation at -O1 (-ftree-ch)

[law at redhat dot com]

------- Additional Comments From law at redhat dot com  2004-12-09 19:52 -------
Subject: Re:  [4.0 regression] loop
	miscompilation at -O1 (-ftree-ch)

On Thu, 2004-12-09 at 19:22 +0000, kazu at cs dot umass dot edu wrote:
> ------- Additional Comments From kazu at cs dot umass dot edu  2004-12-09 19:22 -------
> Jeff,
> 
> With my new patch, stmt.i gets one fewer jump threading opportunities
> (compared to what the vanilla mainline produces).
> So it's very plausible that we are miscompiling stmt.c quietly.
Certainly possible.

> 
> This difference comes from DOM1 while compiling stmt.c:expand_asm_operands.
> 
> I hope this helps.
It does.  I'm just now getting started and knowing the routine in 
question certainly narrows the search field.

> 
> With my old patch, I got one more jump threading opportunity
> (compared to what the vanilla mainline produces).
> It was one of loop.i, stmt.i, and predict.i.
> 
> Since my old patch gives less information to lookup routines,
> the increase in the number of opportunity seems very strange.
Not really if you know the history of this code :(

The selection code (thread_across_edge) dates from before the
SSA updating code could handle threading through a block with
side effects that needed to be preserved.

So the selection code would go through some "interesting" 
contortions to prove that statements in the block were
just nops.  So for example given

X_10 = <expr>

We would lookup <expr> in the hash tables.  If we got a hit
and the result was X_n, then we would consult the current
definition of X.  If the current definition of X was X_n,
then the statement above is really just

X_10 = X_n

Which is the same as

X = X

Which is a nop and thus can be ignored.


Now if we look at your change:

       tree src = PHI_ARG_DEF_FROM_EDGE (phi, e);
       tree dst = PHI_RESULT (phi);
+      if (TREE_CODE (src) == SSA_NAME
+	  && TREE_CODE (SSA_NAME_DEF_STMT (src)) == PHI_NODE
+	  && bb_for_stmt (SSA_NAME_DEF_STMT (src)) == e->dest)
+	continue;
       record_const_or_copy (dst, src);
       register_new_def (dst, &block_defs_stack);

We see that when the IF's condition holds we continue the loop, meaning
that we don't record a new definition for the LHS of the PHI -- which
means we don't update the current definition for the PHI_RESULT's
underlying variable.

The net result is that we have the wrong current definition for some
objects.  This in turn could lead to (incorrectly) threading a jump that
was not threadable before.

It may be enough to remove the "continue" and instead move the call
to record_const_or_copy into the IF statement's THEN clause.  
That prevents recording the bogus equivalence, but still keeps
the current definition of each variable up-to-date.

This is all speculation at this point.  I'm going to dig into this
code under the control of the debugger to see what's going on when
we compile stmt.c

> 
> If you want, I can find out which of DOM[123] is causing this problem
> on which function in which file for you.
No need.

I suspect it'll be pretty obvious given that we thread jumps differently
in loop.i, stmt.i and predict.i.

jeff




-- 


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

[Bug tree-optimization/18694] [4.0 regression] loop miscompilation at -O1 (-ftree-ch)

[kazu at cs dot umass dot edu]

------- Additional Comments From kazu at cs dot umass dot edu  2004-12-10 00:28 -------
Subject: Re:  [4.0 regression] loop
 miscompilation at -O1 (-ftree-ch)

Hi Jeff,

> I believe your fast-path check is effectively equivalent to
> 
> if ((e->flags & EDGE_DFS_BACK) == 0)

I see that we call mark_dfs_back_edges at the beginning of
tree_ssa_dominator_optimize.  Now, after we call cleanup_tree_cfg, can
we trust EDGE_DFS_BACK?

No pass in cleanup_tree_cfg really adds an edge.  All we do is either
remove or redirect edges, so the real question is "Do we ever get a
new back edge without a EDGE_DFS_BACK mark as a result of edge
redirection?"  If we have a forwarder block BB flowing into the loop
header, BB's sole successor edge may be marked with a EDGE_DFS_BACK,
but its incoming edges may not be.  When we call
cleanup_forwarder_blocks, the edges that will survive are BB's
incoming edges, not the edge going out of BB, so we may end up with a
back edge without a EDGE_DFS_BACK mark.

I think we should call mark_dfs_back_edges at the beginning of every
iteration or simply use dominated_by_p, which is not too expensive -
only a couple of "if" statements, assuming the dominator infomatino is
available.

Kazu Hirata


-- 


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

[Bug tree-optimization/18694] [4.0 regression] loop miscompilation at -O1 (-ftree-ch)

[kazu at cs dot umass dot edu]

------- Additional Comments From kazu at cs dot umass dot edu  2004-12-10 02:17 -------
A patch posted at:

http://gcc.gnu.org/ml/gcc-patches/2004-12/msg00727.html


-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |patch


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

[Bug tree-optimization/18694] [4.0 regression] loop miscompilation at -O1 (-ftree-ch)

[kazu at cs dot umass dot edu]

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|unassigned at gcc dot gnu   |kazu at cs dot umass dot edu
                   |dot org                     |
             Status|NEW                         |ASSIGNED


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

[Bug tree-optimization/18694] [4.0 regression] loop miscompilation at -O1 (-ftree-ch)

[law at redhat dot com]

------- Additional Comments From law at redhat dot com  2004-12-10 18:11 -------
Subject: Re:  [4.0 regression] loop
	miscompilation at -O1 (-ftree-ch)

On Thu, 2004-12-09 at 05:24 +0000, kazu at cs dot umass dot edu wrote:
> ------- Additional Comments From kazu at cs dot umass dot edu  2004-12-09 05:24 -------
> Updated the testcase like so:
> 
> /* PR tree-optimization/18694
> 
>    The dominator optimization didn't take the PHI evaluation order
>    into account when threading an edge.  */
> 
> extern void abort (void) __attribute__((noreturn));
> extern void exit (int) __attribute__((noreturn));
> 
> void __attribute__((noinline))
> foo (int i)
> {
>   int next_n = 1;
>   int j = 0;
> 
>   for (; i != 0; i--)
>     {
>       int n;
> 
>       for (n = next_n; j < n; j++)
> 	next_n++;
> 
>       if (j != n)
> 	abort ();
>     }
> }
> 
> int
> main (void)
> {
>   foo (2);
>   exit (0);
> }
> 
> 
Can you go ahead and install this into the testsuite?  No need to xfail
since we ought to have a patch installed for the problem soon.

jeff




-- 


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

[Bug tree-optimization/18694] [4.0 regression] loop miscompilation at -O1 (-ftree-ch)

[law at redhat dot com]

------- Additional Comments From law at redhat dot com  2004-12-10 18:24 -------
Subject: Re:  [4.0 regression] loop
	miscompilation at -O1 (-ftree-ch)

On Fri, 2004-12-10 at 00:28 +0000, kazu at cs dot umass dot edu wrote:
> ------- Additional Comments From kazu at cs dot umass dot edu  2004-12-10 00:28 -------
> Subject: Re:  [4.0 regression] loop
>  miscompilation at -O1 (-ftree-ch)
> 
> Hi Jeff,
> 
> > I believe your fast-path check is effectively equivalent to
> > 
> > if ((e->flags & EDGE_DFS_BACK) == 0)
> 
> I see that we call mark_dfs_back_edges at the beginning of
> tree_ssa_dominator_optimize.  Now, after we call cleanup_tree_cfg, can
> we trust EDGE_DFS_BACK?
> 
> No pass in cleanup_tree_cfg really adds an edge.  All we do is either
> remove or redirect edges, so the real question is "Do we ever get a
> new back edge without a EDGE_DFS_BACK mark as a result of edge
> redirection?"  If we have a forwarder block BB flowing into the loop
> header, BB's sole successor edge may be marked with a EDGE_DFS_BACK,
> but its incoming edges may not be.  When we call
> cleanup_forwarder_blocks, the edges that will survive are BB's
> incoming edges, not the edge going out of BB, so we may end up with a
> back edge without a EDGE_DFS_BACK mark.
Hmm, I think you're right.


> I think we should call mark_dfs_back_edges at the beginning of every
> iteration
That might be advisable -- we use EDGE_DFS_BACK to avoid creating
irreducible loops as a result of jump threading IIRC.


>  or simply use dominated_by_p, which is not too expensive -
> only a couple of "if" statements, assuming the dominator infomatino is
> available.
EDGE_DFS_BACK would have been more efficient.  But I don't think it's
100% safe right now.

Jeff




-- 


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

[Bug tree-optimization/18694] [4.0 regression] loop miscompilation at -O1 (-ftree-ch)

[rakdver at atrey dot karlin dot mff dot cuni dot cz]

------- Additional Comments From rakdver at atrey dot karlin dot mff dot cuni dot cz  2004-12-10 18:38 -------
Subject: Re:  [4.0 regression] loop miscompilation at -O1 (-ftree-ch)

> >  or simply use dominated_by_p, which is not too expensive -
> > only a couple of "if" statements, assuming the dominator infomatino is
> > available.
> EDGE_DFS_BACK would have been more efficient.  But I don't think it's
> 100% safe right now.

not that much.  Since you do not change cfg in the progress of dominator
optimizations, you should have fast query structure for dominators
up-to-date; i.e.  testing whether a basic block dominates other takes only
two comparisons of integers.


-- 


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

[Bug tree-optimization/18694] [4.0 regression] loop miscompilation at -O1 (-ftree-ch)

[kazu at cs dot umass dot edu]

------- Additional Comments From kazu at cs dot umass dot edu  2004-12-10 18:53 -------
Subject: Re:  [4.0 regression] loop
 miscompilation at -O1 (-ftree-ch)

Hi Zdenek,

> > >  or simply use dominated_by_p, which is not too expensive -
> > > only a couple of "if" statements, assuming the dominator infomatino is
> > > available.
> > EDGE_DFS_BACK would have been more efficient.  But I don't think it's
> > 100% safe right now.
> 
> not that much.  Since you do not change cfg in the progress of dominator
> optimizations, you should have fast query structure for dominators
> up-to-date; i.e.  testing whether a basic block dominates other takes only
> two comparisons of integers.

Right.  If we have dominator information available,
mark_dfs_back_edges does nothing but duplicates a part of what the
dominator information has to offer.  (It's not that
mark_dfs_back_edges is very flow, but ....)

Kazu Hirata


-- 


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

[Bug tree-optimization/18694] [4.0 regression] loop miscompilation at -O1 (-ftree-ch)

[kazu at cs dot umass dot edu]

------- Additional Comments From kazu at cs dot umass dot edu  2004-12-10 19:08 -------
Subject: Re:  [4.0 regression] loop
 miscompilation at -O1 (-ftree-ch)

Hi Jeff,

> Note that recording tmp_1 = next_2 isn't particularly good either since 
> tmp_1 really isn't equivalent to next_2.  It's equivalent to the
> previous valueof n next_2, which was next_3.  ugh.  Anyway, I'll verify
> that Kazu's patch handles this correctly.

I think so. :-)

What thread_across_edge is really trying to do is "What would these
statements in E->dest look like if they appeared at the end of
E->src?"  Then the question is reduced to whether each statement in
E->dest is translated correctly.  To do the translation, we use
SSA_NAME_VALUE, but note that we don't use it iteratively.  In other
words, given a SSA_NAME variable VAR, we don't do this

  while (TREE_CODE (var) == SSA_NAME
	 && SSA_NAME_VALUE (var) != NULL_TREE)
    var = SSA_NAME_VALUE (var);

because SSA_NAME_VALUE is supposed to be closed so that you won't need
to iterate.  So when we follow "copy-of" relation from tmp_1 to next_2
using SSA_NAME_VALUE, we don't follow next_2 to something else.

Note also that lookup_avail_expr does not translate the expression in
hash table using SSA_NAME_VALUE.  What we translate is the expression
that we look up.

p.s.
By the way, I am now wondering how many times we succeed in threading
a back edge.

Kazu Hirata


-- 


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

[Bug tree-optimization/18694] [4.0 regression] loop miscompilation at -O1 (-ftree-ch)

[law at redhat dot com]

------- Additional Comments From law at redhat dot com  2004-12-10 19:18 -------
Subject: Re:  [4.0 regression] loop
	miscompilation at -O1 (-ftree-ch)

On Fri, 2004-12-10 at 19:08 +0000, kazu at cs dot umass dot edu wrote:

> I think so. :-)
I don't.  :(  I think it'll record tmp_1 = next_2, which is actually
wrong, even though it doesn't actually cause problems with this
testcase.


> What thread_across_edge is really trying to do is "What would these
> statements in E->dest look like if they appeared at the end of
> E->src?"  Then the question is reduced to whether each statement in
> E->dest is translated correctly.  To do the translation, we use
> SSA_NAME_VALUE, but note that we don't use it iteratively.  In other
> words, given a SSA_NAME variable VAR, we don't do this
> 
>   while (TREE_CODE (var) == SSA_NAME
> 	 && SSA_NAME_VALUE (var) != NULL_TREE)
>     var = SSA_NAME_VALUE (var);
And the reason we don't do that is we can actually get into a loop
due to equivalences created by equality tests.


> p.s.
> By the way, I am now wondering how many times we succeed in threading
> a back edge.
It does happen, but I don't know how often.
jeff




-- 


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

[Bug tree-optimization/18694] [4.0 regression] loop miscompilation at -O1 (-ftree-ch)

[law at redhat dot com]

------- Additional Comments From law at redhat dot com  2004-12-10 19:44 -------
Subject: Re:  [4.0 regression] loop
	miscompilation at -O1 (-ftree-ch)

On Fri, 2004-12-10 at 19:08 +0000, kazu at cs dot umass dot edu wrote:

> By the way, I am now wondering how many times we succeed in threading
> a back edge.
I just put in some instrumentation.  It happens relatively often.

jeff





-- 


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

[Bug tree-optimization/18694] [4.0 regression] loop miscompilation at -O1 (-ftree-ch)

[kazu at cs dot umass dot edu]

------- Additional Comments From kazu at cs dot umass dot edu  2004-12-10 19:57 -------
Subject: Re:  [4.0 regression] loop
 miscompilation at -O1 (-ftree-ch)

Hi Jeff,

> > I think so. :-)
> I don't.  :(  I think it'll record tmp_1 = next_2, which is actually
> wrong, even though it doesn't actually cause problems with this
> testcase.

IMHO, you should really think of it as tmp_1 -> next_2 or "tmp_1 is a
copy-of next_2".  It is a one-way relation, not an equivalence because
it is not symmetric.

In other words, tmp_1 -> next_2 (or SSA_NAME_VALUE (tmp_1) == next_2)
means that tmp_1 should be replaced with next_2 if you were moving a
statement in E->dest to E->src.  The other direction does not hold
because next_2 should *not* be replaced with tmp_1.  It should be
replaced with 0 instead.

Let me also think hard to see if I can prove my patch is correct or
come up with a counterexample.  I certainly don't intend to push my
patch blindly.

Oh, by the way, let's wait on putting the testcase.  I am pretty sure
people will complain about a "regression" in their test results.

Kazu Hirata


-- 


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

[Bug tree-optimization/18694] [4.0 regression] loop miscompilation at -O1 (-ftree-ch)

[law at redhat dot com]

------- Additional Comments From law at redhat dot com  2004-12-10 20:00 -------
Subject: Re:  [4.0 regression] loop
	miscompilation at -O1 (-ftree-ch)

On Fri, 2004-12-10 at 19:08 +0000, kazu at cs dot umass dot edu wrote:
> ------- Additional Comments From kazu at cs dot umass dot edu  2004-12-10 19:08 -------
> Subject: Re:  [4.0 regression] loop
>  miscompilation at -O1 (-ftree-ch)
> 
> Hi Jeff,
> 
> > Note that recording tmp_1 = next_2 isn't particularly good either since 
> > tmp_1 really isn't equivalent to next_2.  It's equivalent to the
> > previous valueof n next_2, which was next_3.  ugh.  Anyway, I'll verify
> > that Kazu's patch handles this correctly.
> 
> I think so. :-)
> 
> What thread_across_edge is really trying to do is "What would these
> statements in E->dest look like if they appeared at the end of
> E->src?"  Then the question is reduced to whether each statement in
> E->dest is translated correctly.  To do the translation, we use
> SSA_NAME_VALUE, but note that we don't use it iteratively.  In other
> words, given a SSA_NAME variable VAR, we don't do this
> 
>   while (TREE_CODE (var) == SSA_NAME
> 	 && SSA_NAME_VALUE (var) != NULL_TREE)
>     var = SSA_NAME_VALUE (var);
> 
> because SSA_NAME_VALUE is supposed to be closed so that you won't need
> to iterate.  So when we follow "copy-of" relation from tmp_1 to next_2
> using SSA_NAME_VALUE, we don't follow next_2 to something else.
> 
> Note also that lookup_avail_expr does not translate the expression in
> hash table using SSA_NAME_VALUE.  What we translate is the expression
> that we look up.
BTW, I may have a nice clean way to deal with this problem which doesn't
depend on us not walking the SSA_NAME_VALUE chain.

I'm looking into it now...

jeff




-- 


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

[Bug tree-optimization/18694] [4.0 regression] loop miscompilation at -O1 (-ftree-ch)

[law at redhat dot com]

------- Additional Comments From law at redhat dot com  2004-12-10 20:12 -------
Subject: Re:  [4.0 regression] loop
	miscompilation at -O1 (-ftree-ch)

On Fri, 2004-12-10 at 19:57 +0000, kazu at cs dot umass dot edu wrote:
> ------- Additional Comments From kazu at cs dot umass dot edu  2004-12-10 19:57 -------
> Subject: Re:  [4.0 regression] loop
>  miscompilation at -O1 (-ftree-ch)
> 
> Hi Jeff,
> 
> > > I think so. :-)
> > I don't.  :(  I think it'll record tmp_1 = next_2, which is actually
> > wrong, even though it doesn't actually cause problems with this
> > testcase.
> 
> IMHO, you should really think of it as tmp_1 -> next_2 or "tmp_1 is a
> copy-of next_2".  It is a one-way relation, not an equivalence because
> it is not symmetric.
Err, no.  You're totally warping how the the equivalency code is meant
to work.  It's a symmetric relationship and it's your patch that is
making it asymmetric.


> Let me also think hard to see if I can prove my patch is correct or
> come up with a counterexample.  I certainly don't intend to push my
> patch blindly.
Don't bother.  The patch is wrong.    There's a couple of very simple
ways to fix this problem that I'm evaluating.

Jeff



-- 


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

[Bug tree-optimization/18694] [4.0 regression] loop miscompilation at -O1 (-ftree-ch)

[kazu at cs dot umass dot edu]

------- Additional Comments From kazu at cs dot umass dot edu  2004-12-10 20:14 -------
Subject: Re:  [4.0 regression] loop
 miscompilation at -O1 (-ftree-ch)

Hi Jeff,

> BTW, I may have a nice clean way to deal with this problem which doesn't
> depend on us not walking the SSA_NAME_VALUE chain.
> 
> I'm looking into it now...

That would be great.

FYI, the only reason I am sticking to correct maintanance of
SSA_NAME_VALUE is that thread_across_edge is not the only function
that translates PHI results to PHI arguments on edge E.
lookup_avail_expr, for example, also uses SSA_NAME_VALUE, and we do
call lookup_avail_expr at tree-ssa-dom.c:582 without translating PHI
arguments on our own.

Kazu Hirata


-- 


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

[Bug tree-optimization/18694] [4.0 regression] loop miscompilation at -O1 (-ftree-ch)

[law at redhat dot com]

------- Additional Comments From law at redhat dot com  2004-12-10 20:52 -------
Subject: Re:  [4.0 regression] loop
	miscompilation at -O1 (-ftree-ch)

On Fri, 2004-12-10 at 19:08 +0000, kazu at cs dot umass dot edu wrote:
> ------- Additional Comments From kazu at cs dot umass dot edu  2004-12-10 19:08 -------
> Subject: Re:  [4.0 regression] loop
>  miscompilation at -O1 (-ftree-ch)
> 
> Hi Jeff,
> 
> > Note that recording tmp_1 = next_2 isn't particularly good either since 
> > tmp_1 really isn't equivalent to next_2.  It's equivalent to the
> > previous valueof n next_2, which was next_3.  ugh.  Anyway, I'll verify
> > that Kazu's patch handles this correctly.
> 
> I think so. :-)


So as I mentioned in a message a short while ago, there are some very
simple solutions to this problem.

  1. The simplest would be to disable jump threading on for backedges in
  loops.  Based on some simple instrumentation, that would be bad as
  it would inhibit a large number of threading opportunities (at least
  two hundred within GCC's cc1 .i files).

  2. Disable threading only if we find a PHI argument which was set
  by a PHI the same block.  This still disables a lot of threading
  opportunities. However, we can do much better with a trivial 
  improvement....

  3. Given a PHI node like x_2 = (..., x_2, ...); if we want the x_2
  alternative, then there's no need to inhibit jump threading since
  x_2 is always trivially equivalent to itself.

Option #3 only prevents two valid jump threading opportunities in the
tests I ran.  And it's implementation is pretty trivial:  


  /* Each PHI creates a temporary equivalence, record them.  */
  for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi))
    {
      tree src = PHI_ARG_DEF_FROM_EDGE (phi, e);
      tree dst = PHI_RESULT (phi);

      /* If the desired argument is not the same as this PHI's result
         and it is set by a PHI in this block, then we can not thread
         through this block.  */
      if (src != dst
          && TREE_CODE (src) == SSA_NAME
          && TREE_CODE (SSA_NAME_DEF_STMT (src)) == PHI_NODE
          && bb_for_stmt (SSA_NAME_DEF_STMT (src)) == e->dest)
        return;

      record_const_or_copy (dst, src);
      register_new_def (dst, &block_defs_stack);
    }


A final approach would be to turn that code into something like this:

  /* Each PHI creates a temporary equivalence, record them.  */
  for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi))
    {
      tree src = PHI_ARG_DEF_FROM_EDGE (phi, e);
      tree dst = PHI_RESULT (phi);

      /* If the desired argument is not the same as this PHI's result
         and it is set by a PHI in this block, then we can not thread
         through this block.  */
      if (src != dst
          && TREE_CODE (src) == SSA_NAME
          && TREE_CODE (SSA_NAME_DEF_STMT (src)) == PHI_NODE
          && bb_for_stmt (SSA_NAME_DEF_STMT (src)) == e->dest)
        {
          src = make_ssa_name (SSA_NAME_VAR (dst), build_empty_stmt());
        }

      record_const_or_copy (dst, src);
      register_new_def (dst, &block_defs_stack);
    }

Which would allow us to do full jump threading.  What I don't like about
this approach is we have to add some code to track the SSA_NAMEs we
generate in that loop so that we can release them.  Ugh.  It doesn't 
seem worth the headache.

Jeff



-- 


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

[Bug tree-optimization/18694] [4.0 regression] loop miscompilation at -O1 (-ftree-ch)

[kazu at cs dot umass dot edu]

------- Additional Comments From kazu at cs dot umass dot edu  2004-12-10 21:31 -------
Subject: Re:  [4.0 regression] loop
 miscompilation at -O1 (-ftree-ch)

Hi Jeff,

> Err, no.  You're totally warping how the the equivalency code is meant
> to work.  It's a symmetric relationship and it's your patch that is
> making it asymmetric.

I thought SSA_NAME_VALUE gets me a gimple min invariant or the
earliest SSA_NAME that has the same value.

> Don't bother.  The patch is wrong.

Can you come up with a hypothetical scenario?

Kazu Hirata


-- 


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

[Bug tree-optimization/18694] [4.0 regression] loop miscompilation at -O1 (-ftree-ch)

[law at redhat dot com]

------- Additional Comments From law at redhat dot com  2004-12-10 21:42 -------
Subject: Re:  [4.0 regression] loop
	miscompilation at -O1 (-ftree-ch)

On Fri, 2004-12-10 at 21:31 +0000, kazu at cs dot umass dot edu wrote:

> Can you come up with a hypothetical scenario?
No need.  It's fundamentally broken in that it's recording
an invalid equivalence.  It's recording that tmp_1 = next_2
which is totally bogus.

The only reason it works is because we don't walk through
all the SSA_NAME_VALUEs back to the oldest.  

jeff




-- 


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

[Bug tree-optimization/18694] [4.0 regression] loop miscompilation at -O1 (-ftree-ch)

[kazu at cs dot umass dot edu]

------- Additional Comments From kazu at cs dot umass dot edu  2004-12-10 22:25 -------
Subject: Re:  [4.0 regression] loop
 miscompilation at -O1 (-ftree-ch)

Hi Jeff,

> > Can you come up with a hypothetical scenario?
> No need.  It's fundamentally broken in that it's recording
> an invalid equivalence.  It's recording that tmp_1 = next_2
> which is totally bogus.
> 
> The only reason it works is because we don't walk through
> all the SSA_NAME_VALUEs back to the oldest.  

Yes, I was relying on that fact.

Ah, now I see that we have two different definitions of
SSA_NAME_VALUE.  Rather than pushing what I think is the right
definition, let's get a correct definition from the author of
tree-ssa-dom.c. :-) Is the following more or less correct?

  SSA_NAME_VALUE(X) gives you a gimple min invariant or an SSA_NAME
  that has the same value as X.  If we do not find a gimple min
  invariant for X, we make every effort to make SSA_NAME_VALUE(X)
  evaluate to the oldest SSA_NAME that has the same value as X (via
  record_const_or_copy, etc), but that is not guaranteed.  For the
  best result, you may have to walk SSA_NAME_VALUE, but it's
  questionable how profitable that is.

The only comment I can find for SSA_NAME_VALUE is this:

/* Get the value of this SSA_NAME, if available.  */
#define SSA_NAME_VALUE(N) \
   SSA_NAME_CHECK (N)->ssa_name.value_handle

I think it would be helpful to expand the comment for a future
reference.  To be honest, given that tree-ssa-dom.c never walks
SSA_NAME_VALUE and that record_const_or_copy makes a transitive
closure of "copy-of" relations, I was under the impression that
SSA_NAME_VALUE gives you the oldest value.

Kazu Hirata


-- 


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

[Bug tree-optimization/18694] [4.0 regression] loop miscompilation at -O1 (-ftree-ch)

[law at redhat dot com]

------- Additional Comments From law at redhat dot com  2004-12-13 20:36 -------
Should be fixed with today's checkin to tree-ssa-dom.c

-- 


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

[Bug tree-optimization/18694] [4.0 regression] loop miscompilation at -O1 (-ftree-ch)

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2004-12-13 21:01 -------
Fixed.

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


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