[Bug tree-optimization/41783] New: r151561 (PRE fix) regresses zeusmp

[Bug tree-optimization/41783] New: r151561 (PRE fix) regresses zeusmp

[matz at gcc dot gnu dot org]

zeusmp regressed by about 5% again with the PRE fix for PR41101, which is
r151561.  The problem is that PRE now finds a partial redundancy (where in
reality there isn't any) and the PHI node to compensate for this prevents
vectorization of a loop due to its value used outside that loop.  Testcase
extracted from zeusmp:

% cat hsmoc-1.f
      subroutine hsmoc ( )
      implicit NONE
      integer ijkn
      parameter(ijkn =   128+5)
      real*8 dt, fact, db(ijkn), w1dt(ijkn)
      integer i, is, ie, j, js, je
      common /rootr/ dt
      common /scratch/  w1dt
         do 9 i=is,ie
           do 807 j=js-1,je+1
             db (j  ) = j
 807       continue
           fact = dt * i
           do 808 j=js,je+1
             w1dt(j)= fact * db (j)
 808       continue
 9      continue
       return
       end

(compile with -march=barcelona -O3 -ffast-math -funroll-loops -fpeel-loops)
The problem is the access to 'dt' (rootr.dt), which PRE thinks is partially
redundant in the first loop (!?), hence it creates this code:

pretmp.11_53 = rootr.dt;
Loop-i:
  prephitmp.12_51 = PHI <pretmp.11_53(9), D.1376_20(20)>
...
  Loop-j1
    prephitmp.12_49 = PHI <prephitmp.12_51(11), pretmp.11_52(14)>
    ...
    pretmp.11_52 = rootr.dt;
    goto Loop-j1
  prephitmp.12_23 = PHI <prephitmp.12_51(12), prephitmp.12_49(13)>
  D.1376_20 = prephitmp.12_23;
  ...
  Loop-j2

Notice especially how we now read rootr.dt in the backedge for loop-j1,
which is much more often than before.  Originally we access it ie-is times,
now we access it (ie-is)*(je-js) times.

It's possible that this alone explains the speed regression, and not
necessarily the missed vectorization.  But the missed vectorization was
much easier to detect.


-- 
           Summary: r151561 (PRE fix) regresses zeusmp
           Product: gcc
           Version: 4.5.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: matz at gcc dot gnu dot org
  GCC host triplet: x86_64-linux


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

[Bug tree-optimization/41783] r151561 (PRE fix) regresses zeusmp

[rguenth at gcc dot gnu dot org]

------- Comment #1 from rguenth at gcc dot gnu dot org  2009-10-21 14:53 -------
Confirmed.  Btw the loop is still vectorized for me.


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
     Ever Confirmed|0                           |1
   Last reconfirmed|0000-00-00 00:00:00         |2009-10-21 14:53:32
               date|                            |
            Summary|r151561 (PRE fix) regresses |r151561 (PRE fix) regresses
                   |zeusmp                      |zeusmp


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

[Bug tree-optimization/41783] r151561 (PRE fix) regresses zeusmp

[rguenth at gcc dot gnu dot org]

------- Comment #2 from rguenth at gcc dot gnu dot org  2009-10-21 15:07 -------
Btw, the 2nd insertion is really weird (the first one in bb9 is just loop
invariant motion).


<bb 14>:
  pretmp.7_45 = rootr.dt;
  goto <bb 4>;

<bb 13>:

<bb 5>:
  # prephitmp.8_48 = PHI <prephitmp.8_47(12), prephitmp.8_50(13)>
  D.1375_18 = (real(kind=8)) i_3;
  D.1376_19 = prephitmp.8_48;
  fact_20 = D.1375_18 * D.1376_19;
  if (js_9(D) <= D.1351_12)
    goto <bb 15>;
  else
    goto <bb 16>;


it looks to me that we fail to translate over the first loop and its
header copy - something that partial-PRE ought to have accomplished.


-- 


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

[Bug tree-optimization/41783] r151561 (PRE fix) regresses zeusmp

[rguenth at gcc dot gnu dot org]

------- Comment #3 from rguenth at gcc dot gnu dot org  2009-10-21 15:14 -------
C testcase showing the likely underlying issue:

int db[100];
int dt, fact;
int main()
{
  int i;
  do
    {
      for (i=0; i<100; ++i)
        db[i] = i;
      fact = dt * i;
    }
  while (1);
}

where we not only insert into BB2 but also BB3:

<bb 2>:
  pretmp.4_16 = dt;
  goto <bb 5>;

<bb 3>:
  db[i_1] = i_1;
  i_3 = i_1 + 1;
  pretmp.4_14 = dt;

<bb 4>:
  # i_6 = PHI <0(6), i_3(3)>
  # prephitmp.5_15 = PHI <dt.0_4(6), pretmp.4_14(3)>

<bb 5>:
  # i_1 = PHI <i_6(4), 0(2)>
  # prephitmp.5_17 = PHI <prephitmp.5_15(4), pretmp.4_16(2)>
  if (i_1 <= 99)
    goto <bb 3>;
  else
    goto <bb 6>;

<bb 6>:
  dt.0_4 = prephitmp.5_17;
  fact.1_5 = i_1 * dt.0_4;
  fact = fact.1_5;
  goto <bb 4>;


-- 


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

[Bug tree-optimization/41783] r151561 (PRE fix) regresses zeusmp

[rguenth at gcc dot gnu dot org]

------- Comment #4 from rguenth at gcc dot gnu dot org  2009-10-21 15:16 -------
Which all is likely due to the fact that PHI translation does not properly
value-number translated loads and thus we create extra full redundancies
sometimes (usually resulting in extra PHI nodes, but here extra loads).

Micha, you once had a patch to "fix" this issue, right?


-- 


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

[Bug tree-optimization/41783] r151561 (PRE fix) regresses zeusmp

[matz at gcc dot gnu dot org]

------- Comment #5 from matz at gcc dot gnu dot org  2009-10-21 15:20 -------
Yes, I mean the second insertion.  The phi node generated for that one (in the
first j-loop) prevents vectorization in r151561 (I haven't really tested
newer revs that r151590).  Maybe some other stuff in later revs cleans this
PHI node up again (or the vectorizer handles it) so that the first loop is
vectorized for you.  You are sure that you talk about the first j loop that
is vectorized for you, right?  The second is also vectorized for me, that's
not the interesting one.


-- 


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

[Bug tree-optimization/41783] r151561 (PRE fix) regresses zeusmp

[matz at gcc dot gnu dot org]

------- Comment #6 from matz at gcc dot gnu dot org  2009-10-21 15:22 -------
Hmm, at least I don't remember any patch dealing with phi translation right
now.


-- 


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

[Bug tree-optimization/41783] r151561 (PRE fix) regresses zeusmp

[rguenth at gcc dot gnu dot org]

------- Comment #7 from rguenth at gcc dot gnu dot org  2009-10-21 15:26 -------
LIM cleans up the 2nd insertion for me and moves the load next to the first
insertion.  What remains is the full redundancy and elimination of all the
PHIs, so yes, your PRE patch would solve this.  And yes, it is only the 2nd
loop that is vectorized for me.


-- 


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

[Bug tree-optimization/41783] r151561 (PRE fix) regresses zeusmp

[matz at gcc dot gnu dot org]

------- Comment #8 from matz at gcc dot gnu dot org  2009-10-21 15:35 -------
But the important one (for zeusmp) is the first loop.  That isn't vectorized
anymore (but was in r151560, i.e. there it vectorized two loops).


-- 


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

[Bug tree-optimization/41783] r151561 (PRE fix) regresses zeusmp

[rguenth at gcc dot gnu dot org]

------- Comment #9 from rguenth at gcc dot gnu dot org  2009-10-21 18:08 -------
Ok, I'm pretty much sure what happens and what is wrong.  I'll fix what is
wrong
and we'll need that phi-translation fix to fixup the regressions that'll cause.


-- 


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

[Bug tree-optimization/41783] r151561 (PRE fix) regresses zeusmp

[rguenth at gcc dot gnu dot org]

------- Comment #10 from rguenth at gcc dot gnu dot org  2009-10-21 20:14 -------
Created an attachment (id=18861)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=18861&action=view)
1st part of a patch

Like this.  We should never produce new non-constant value-numbers during
phi-translation as that may spuriously increase the maximal set and thus cause
insertion of non-redundant values.

We do so for NARYs anyway - I'm not sure if that is good though.  Maybe the
idea
is that repeated translation can eventually lead to a known value.


-- 


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

[Bug tree-optimization/41783] r151561 (PRE fix) regresses zeusmp

[matz at gcc dot gnu dot org]

------- Comment #11 from matz at gcc dot gnu dot org  2009-10-22 15:13 -------
Have patch.


-- 

matz at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|unassigned at gcc dot gnu   |matz at gcc dot gnu dot org
                   |dot org                     |
             Status|NEW                         |ASSIGNED
   Last reconfirmed|2009-10-21 14:53:32         |2009-10-22 15:13:07
               date|                            |


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

[Bug tree-optimization/41783] r151561 (PRE fix) regresses zeusmp

[matz at gcc dot gnu dot org]

------- Comment #12 from matz at gcc dot gnu dot org  2009-10-26 13:00 -------
Subject: Bug 41783

Author: matz
Date: Mon Oct 26 13:00:36 2009
New Revision: 153551

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=153551
Log:
        PR tree-optimization/41783
        * tree-ssa-alias.c (get_continuation_for_phi): Export, add a special
        case for simple diamonds
        * tree-ssa-alias.h (get_continuation_for_phi): Declare.
        * tree-ssa-pre.c (translate_vuse_through_block): Add same_valid
        argument, use alias oracle to skip some vdefs.
        (phi_translate_1): Change call to above, don't allocate new
        value ids if they can stay the same.
        (compute_avail): Allow vuse walking when looking up references.

testsuite/
        * gcc.dg/pr41783.c: New test.
        * gcc.dg/tree-ssa/ssa-pre-23.c: Adjust.
        * gcc.dg/tree-ssa/ssa-pre-24.c: Don't xfail anymore.
        * gcc.dg/tree-ssa/ssa-pre-27.c: New test.

Added:
    trunk/gcc/testsuite/gcc.dg/pr41783.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/testsuite/gcc.dg/tree-ssa/ssa-pre-23.c
    trunk/gcc/testsuite/gcc.dg/tree-ssa/ssa-pre-24.c
    trunk/gcc/tree-ssa-alias.c
    trunk/gcc/tree-ssa-alias.h
    trunk/gcc/tree-ssa-pre.c


-- 


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

[Bug tree-optimization/41783] r151561 (PRE fix) regresses zeusmp

[matz at gcc dot gnu dot org]

------- Comment #13 from matz at gcc dot gnu dot org  2009-10-26 13:04 -------
Fixed.


-- 

matz at gcc dot gnu dot org changed:

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


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

[Bug tree-optimization/41783] r151561 (PRE fix) regresses zeusmp

[rguenth at gcc dot gnu dot org]

------- Comment #14 from rguenth at gcc dot gnu dot org  2009-10-30 16:14 -------
I think this fix caused 172.mgrid to regress (we likely no longer perform
predictive commoning there).  See
http://gcc.opensuse.org/SPEC/CFP/sb-vangelis-head-64/recent.html


-- 


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

[Bug tree-optimization/41783] r151561 (PRE fix) regresses zeusmp

[rguenth at gcc dot gnu dot org]

------- Comment #15 from rguenth at gcc dot gnu dot org  2009-10-30 16:39 -------
In fact we now vectorize additional loops because of less prephitemps but
that gets in the way of predictive-commoning which is much more useful here :(


-- 


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

[Bug tree-optimization/41783] r151561 (PRE fix) regresses zeusmp

[matz at gcc dot gnu dot org]

------- Comment #16 from matz at gcc dot gnu dot org  2010-01-19 16:06 -------
Subject: Bug 41783

Author: matz
Date: Tue Jan 19 16:05:57 2010
New Revision: 156043

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=156043
Log:
        PR tree-optimization/41783
        * tree-data-ref.c (toplevel): Include flags.h.
        (dump_data_dependence_relation):  Also dump the inputs if the
        result will be unknown.
        (split_constant_offset_1): Look through some conversions.
        * tree-predcom.c (determine_roots_comp): Restart a new chain if
        the offset from last element is too large.
        (ref_at_iteration): Deal also with MISALIGNED_INDIRECT_REF.
        (reassociate_to_the_same_stmt): Handle vector registers.
        * tree-vect-data-refs.c (vect_equal_offsets): Handle unary operations
        (e.g. conversions).
        * tree-vect-loop-manip.c (vect_gen_niters_for_prolog_loop): Add 
        wide_prolog_niters argument, emit widening instructions.
        (vect_do_peeling_for_alignment): Adjust caller, use widened
        variant of the iteration cound.
        * Makefile.in (tree-data-ref.o): Add $(FLAGS_H).

testsuite/
        * gfortran.dg/vect/fast-math-mgrid-resid.f: New.

Added:
    trunk/gcc/testsuite/gfortran.dg/vect/fast-math-mgrid-resid.f
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/Makefile.in
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/tree-data-ref.c
    trunk/gcc/tree-predcom.c
    trunk/gcc/tree-vect-data-refs.c
    trunk/gcc/tree-vect-loop-manip.c


-- 


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