[Bug middle-end/39976] [4.5/4.6 Regression] Big sixtrack degradation on powerpc 32/64 after revision r146817

[Bug middle-end/39976] [4.5/4.6 Regression] Big sixtrack degradation on powerpc 32/64 after revision r146817

[jakub at gcc dot gnu.org]

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

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

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

--- Comment #30 from Jakub Jelinek <jakub at gcc dot gnu.org> 2010-12-15 15:32:48 UTC ---
Is this still a problem on the current trunk?

[Bug middle-end/39976] [4.5/4.6 Regression] Big sixtrack degradation on powerpc 32/64 after revision r146817

[pthaugen at gcc dot gnu.org]

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

--- Comment #31 from Pat Haugen <pthaugen at gcc dot gnu.org> 2010-12-15 21:14:46 UTC ---
Yes, the 2-block loop still exists with current trunk (r167858).

[Bug middle-end/39976] [4.5/4.6 Regression] Big sixtrack degradation on powerpc 32/64 after revision r146817

[pthaugen at gcc dot gnu.org]

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

--- Comment #32 from Pat Haugen <pthaugen at gcc dot gnu.org> 2010-12-15 21:23:50 UTC ---
Forgot to also mention that the loop is no longer a branch on count loop, so
finding it in the original thin6d.f is a little tougher than the simple egrep
'^.L|bdnz' thin6d.s and looking for bdnz not branching to immediately
preceeding label, but reduced testcase still also exhibits the problem.

[Bug middle-end/39976] [4.5/4.6 Regression] Big sixtrack degradation on powerpc 32/64 after revision r146817

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.5.2                       |4.5.3

--- Comment #33 from Richard Guenther <rguenth at gcc dot gnu.org> 2010-12-16 13:03:26 UTC ---
GCC 4.5.2 is being released, adjusting target milestone.

[Bug middle-end/39976] [4.5/4.6/4.7 Regression] Big sixtrack degradation on powerpc 32/64 after revision r146817

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.5.3                       |4.5.4

--- Comment #34 from Richard Guenther <rguenth at gcc dot gnu.org> 2011-04-28 14:51:42 UTC ---
GCC 4.5.3 is being released, adjusting target milestone.

[Bug middle-end/39976] [4.5/4.6/4.7 Regression] Big sixtrack degradation on powerpc 32/64 after revision r146817

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |WAITING

--- Comment #35 from Richard Guenther <rguenth at gcc dot gnu.org> 2011-11-05 12:37:17 UTC ---
Asking for re-confirmation again.

[Bug middle-end/39976] [4.5/4.6/4.7 Regression] Big sixtrack degradation on powerpc 32/64 after revision r146817

[pthaugen at gcc dot gnu.org]

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

Pat Haugen <pthaugen at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Last reconfirmed|2010-03-31 11:56:08         |2011-11-08

--- Comment #36 from Pat Haugen <pthaugen at gcc dot gnu.org> 2011-11-08 23:58:37 UTC ---
Yes, the inner loop is still being broken into 2 blocks with trunk revision
181173.

[Bug middle-end/39976] [4.5/4.6/4.7 Regression] Big sixtrack degradation on powerpc 32/64 after revision r146817

[wschmidt at gcc dot gnu.org]

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

William J. Schmidt <wschmidt at gcc dot gnu.org> changed:

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

--- Comment #37 from William J. Schmidt <wschmidt at gcc dot gnu.org> 2011-11-17 15:15:49 UTC ---
Using Pat's reduced test case, I found that the problem occurs when the back
arc along 7->7 (the innermost loop) is split by the following:

  Inserting a partition copy on edge BB7->BB7 :PART.153 = PART.45

Coalescing previously determined the following for these partitions:

  Partition 45 (prephitmp.35_113 - 113 222 225 343 )
  Partition 153 (prephitmp.35_322 - 322 )

Below, I've cut down the tree dump at the time of coalescing to show just the
statements involving prephitmp.35 and control flow, except for block 7 which
I've reproduced in its entirety.  The problem can be seen in block 7, where
there are two PHIs with the identical RHS:

  # prephitmp.35_322 = PHI <prephitmp.35_59(6), prephitmp.35_113(7)>
  # prephitmp.35_225 = PHI <prephitmp.35_59(6), prephitmp.35_113(7)>

225 is coalesced with 113, but 322 is not.  From what I can tell, 322 should be
equally as good a candidate for coalescing as 225.  If the duplicates had been
removed, it seems the existing coalescing algorithm would have avoided
inserting the partition copy that created the extra block.

I'm thinking these kinds of duplicate phis should be cleaned up before we get
to expand.  Is that already the intent, and this is just a bug, or is that
something that needs to be implemented somewhere in the late tree phases? 
Alternatively, should coalesce have done better here?

For what it's worth, here are the origins of the duplicate PHIs in block 7.

The first PHI is introduced in 094t.pre:

  # prephitmp.35_322 = PHI <zlvj.5_59(9), cikve.14_113(12)>

This is changed as follows in 099t.copyprop4:

  # prephitmp.35_322 = PHI <zlvj.5_59(6), cikve.14_113(8)>
  # cikve_lsm.48_225 = PHI <zlvj.5_59(6), cikve.14_113(8)>

Finally, these are renamed in 138t.copyrename4:

  # prephitmp.35_322 = PHI <prephitmp.35_59(6), prephitmp.35_113(7)>
  # prephitmp.35_225 = PHI <prephitmp.35_59(6), prephitmp.35_113(7)>

======================================================================
thin6d (integer(kind=4) & restrict nthinerr)
{
...
  # BLOCK 5 freq:2800
  # PRED: 4 [100.0%]  (fallthru,exec) 9 [86.0%]  (dfs_back,false,exec)
  # prephitmp.35_221 = PHI <prephitmp.35_284(4), prephitmp.35_228(9)>
...
  prephitmp.35_32 = D.2028_14 * pretmp.34_287 + D.2038_31;
...
  prephitmp.35_59 = D.2036_27 * pretmp.34_287 + D.2189_18;
  D.2050_70 = prephitmp.35_32 * pretmp.37_297 + pretmp.37_295;
  prephitmp.42_77 = prephitmp.35_59 * pretmp.37_299 + D.2050_70;
  D.2190_76 = -prephitmp.35_59;
...
  prephitmp.42_95 = prephitmp.35_32 * pretmp.37_299 + D.2057_88;
  if (nmz.1_3 > 2)
    goto <bb 6>;
  else
    goto <bb 9>;
  # SUCC: 6 [50.0%]  (true,exec) 9 [50.0%]  (false,exec)

  # BLOCK 6 freq:1400
  # PRED: 5 [50.0%]  (true,exec)
...
  # SUCC: 7 [100.0%]  (fallthru,exec)

  # BLOCK 7 freq:10000
  # PRED: 6 [100.0%]  (fallthru,exec) 7 [86.0%]  (dfs_back,false,exec)
  # prephitmp.35_321 = PHI <prephitmp.35_32(6), prephitmp.35_106(7)>
  # prephitmp.35_322 = PHI <prephitmp.35_59(6), prephitmp.35_113(7)>
  # prephitmp.42_325 = PHI <prephitmp.42_77(6), prephitmp.42_133(7)>
  # prephitmp.42_326 = PHI <prephitmp.42_95(6), prephitmp.42_152(7)>
  # prephitmp.35_229 = PHI <prephitmp.35_32(6), prephitmp.35_203(7)>
  # prephitmp.35_225 = PHI <prephitmp.35_59(6), prephitmp.35_113(7)>
  # ivtmp.56_220 = PHI <ivtmp.56_219(6), ivtmp.56_227(7)>
  # ivtmp.62_218 = PHI <ivtmp.62_290(6), ivtmp.62_217(7)>
  D.2067_105 = prephitmp.35_59 * prephitmp.35_322;
  D.2191_94 = -D.2067_105;
  prephitmp.35_106 = prephitmp.35_32 * prephitmp.35_321 + D.2191_94;
  D.2070_112 = prephitmp.35_32 * prephitmp.35_225;
  prephitmp.35_113 = prephitmp.35_59 * prephitmp.35_229 + D.2070_112;
  ivtmp.56_227 = ivtmp.56_220 + 8;
  D.2155_289 = (void *) ivtmp.56_227;
  D.2075_120 = MEM[base: D.2155_289, offset: 0B];
  D.2078_124 = prephitmp.35_106 * D.2075_120 + prephitmp.42_325;
  ivtmp.62_217 = ivtmp.62_218 + 8;
  D.2156_283 = (void *) ivtmp.62_217;
  D.2079_130 = MEM[base: D.2156_283, offset: 0B];
  prephitmp.42_133 = prephitmp.35_113 * D.2079_130 + D.2078_124;
  D.2192_132 = -prephitmp.35_113;
  D.2084_143 = D.2192_132 * D.2075_120 + prephitmp.42_326;
  prephitmp.42_152 = prephitmp.35_106 * D.2079_130 + D.2084_143;
  prephitmp.35_203 = prephitmp.35_106;
  if (ivtmp.56_227 == D.2161_30)
    goto <bb 8>;
  else
    goto <bb 7>;
  # SUCC: 8 [14.0%]  (true,exec) 7 [86.0%]  (dfs_back,false,exec)

  # BLOCK 8 freq:1400
  # PRED: 7 [14.0%]  (true,exec)
...
  # SUCC: 9 [100.0%]  (fallthru,exec)

  # BLOCK 9 freq:2800
  # PRED: 5 [50.0%]  (false,exec) 8 [100.0%]  (fallthru,exec)
...
  # prephitmp.35_223 = PHI <prephitmp.35_32(5), prephitmp.35_106(8)>
  # prephitmp.35_222 = PHI <prephitmp.35_59(5), prephitmp.35_113(8)>
...
  # prephitmp.35_228 = PHI <prephitmp.35_221(5), prephitmp.35_106(8)>
...
  if (ivtmp.74_156 == D.2188_100)
    goto <bb 10>;
  else
    goto <bb 5>;
  # SUCC: 10 [14.0%]  (true,exec) 5 [86.0%]  (dfs_back,false,exec)

  # BLOCK 10 freq:392
  # PRED: 9 [14.0%]  (true,exec)
  # prephitmp.35_343 = PHI <prephitmp.35_222(9)>
  # prephitmp.35_344 = PHI <prephitmp.35_223(9)>
...
  # prephitmp.35_347 = PHI <prephitmp.35_228(9)>
...
  # prephitmp.35_350 = PHI <prephitmp.35_59(9)>
  # prephitmp.35_351 = PHI <prephitmp.35_32(9)>
...
  xlvj = prephitmp.35_351;
  zlvj = prephitmp.35_350;
...
  crkve = prephitmp.35_344;
  cikve = prephitmp.35_343;
...
  crkveuk = prephitmp.35_347;
  goto <bb 3>;
  # SUCC: 3 [100.0%]  (fallthru,exec)

}
======================================================================

[Bug middle-end/39976] [4.5/4.6/4.7 Regression] Big sixtrack degradation on powerpc 32/64 after revision r146817

[wschmidt at gcc dot gnu.org]

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

--- Comment #38 from William J. Schmidt <wschmidt at gcc dot gnu.org> 2011-11-17 15:17:53 UTC ---
Created attachment 25845
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=25845
Expand details dump for reduced test case

Attaching the full details dump from cfgexpand for the reduced test case.

[Bug middle-end/39976] [4.5/4.6/4.7 Regression] Big sixtrack degradation on powerpc 32/64 after revision r146817

[matz at gcc dot gnu.org]

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

Michael Matz <matz at gcc dot gnu.org> changed:

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

--- Comment #39 from Michael Matz <matz at gcc dot gnu.org> 2011-11-17 16:56:10 UTC ---
Actually the second (redundant) PHI node is introduced in lim1 for me.
Which makes sense as the loop-invarant load and store from/to cikve
(and crkveuk) are optimized.  It's just that the values would have been
available already in one PHI node, but lim isn't setup to avoid this
redundancy.

We have plenty of passes after lim1 that could be enabled to remove this
redundancy.  Unfortunately right now only PRE does.  Even scheduling a PRE
pass (e.g. right before 2nd pass_dominator) doesn't fully help this problem,
because then we're left with this BB7:

  # prephitmp.35_361 = PHI <prephitmp.35_39(6), prephitmp.35_125(7)>
  # prephitmp.35_362 = PHI <prephitmp.35_72(6), prephitmp.35_132(7)>
  # prephitmp.42_366 = PHI <prephitmp.42_93(6), prephitmp.42_156(7)>
  # prephitmp.42_367 = PHI <prephitmp.42_114(6), prephitmp.42_179(7)>
  # ivtmp.58_257 = PHI <ivtmp.58_256(6), ivtmp.58_264(7)>
  D.3099_121 = prephitmp.35_361 * prephitmp.35_39;
  D.3101_124 = prephitmp.35_362 * prephitmp.35_72;
  prephitmp.35_125 = D.3099_121 - D.3101_124;              <--- (1)
  D.3103_128 = prephitmp.35_361 * prephitmp.35_72;         <--- (2)

No redundant PHI nodes anymore, but still _125 can't be coalesced with _361
(to avoid a backedge copy), because the setting of _125 at (1) conflicts
with the use of _361 at (2).  Swapping both instructions (or moving (1)
down, or (2) up) would alleviate this last problem.

Removing the redundant PHI node seems to be a classic lookup problem, not
so much a propagation problem.  Hence I think it would best fit into
dom, for now.

[Bug middle-end/39976] [4.5/4.6/4.7 Regression] Big sixtrack degradation on powerpc 32/64 after revision r146817

[wschmidt at gcc dot gnu.org]

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

William J. Schmidt <wschmidt at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|WAITING                     |ASSIGNED
         AssignedTo|unassigned at gcc dot       |wschmidt at gcc dot gnu.org
                   |gnu.org                     |

--- Comment #40 from William J. Schmidt <wschmidt at gcc dot gnu.org> 2011-11-18 23:21:25 UTC ---
OK, sounds good.  I'll take this one.

[Bug middle-end/39976] [4.5/4.6/4.7 Regression] Big sixtrack degradation on powerpc 32/64 after revision r146817

[pinskia at gcc dot gnu.org]

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

--- Comment #41 from Andrew Pinski <pinskia at gcc dot gnu.org> 2011-12-01 22:30:26 UTC ---
(In reply to comment #40)
> OK, sounds good.  I'll take this one.

Interesting Jeff Law posted a different patch to
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=45685 which will also fix this
issue but that one only handles constants.  Though it handles slightly more
than just redundant constant PHIs.

[Bug middle-end/39976] [4.5/4.6/4.7 Regression] Big sixtrack degradation on powerpc 32/64 after revision r146817

[wschmidt at gcc dot gnu.org]

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

--- Comment #42 from William J. Schmidt <wschmidt at gcc dot gnu.org> 2011-12-08 22:00:52 UTC ---
Author: wschmidt
Date: Thu Dec  8 22:00:38 2011
New Revision: 182140

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=182140
Log:
2011-12-08  Bill Schmidt  <wschmidt@linux.vnet.ibm.com>

    PR middle-end/39976
    * tree-ssa-dom.c (enum expr_kind): Add EXPR_PHI.
    (struct hashable_expr): Add struct phi field.
    (initialize_hash_element): Handle phis; change to use XCNEWVEC.
    (hashable_expr_equal_p): Handle phis.
    (iterative_hash_hashable_expr): Likewise.
    (print_expr_hash_elt): Likewise.
    (free_expr_hash_elt): Likewise.
    (dom_opt_enter_block): Create equivalences from redundant phis.
    (eliminate_redundant_computations): Handle redundant phis.
    (lookup_avail_expr): Handle phis.

Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/tree-ssa-dom.c

[Bug middle-end/39976] [4.5/4.6/4.7 Regression] Big sixtrack degradation on powerpc 32/64 after revision r146817

[wschmidt at gcc dot gnu.org]

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

William J. Schmidt <wschmidt at gcc dot gnu.org> changed:

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

--- Comment #43 from William J. Schmidt <wschmidt at gcc dot gnu.org> 2011-12-08 22:02:11 UTC ---
Fixed.

[Bug middle-end/39976] [4.5/4.6/4.7 Regression] Big sixtrack degradation on powerpc 32/64 after revision r146817

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.5.4                       |4.7.0
      Known to fail|                            |4.6.2

[Bug middle-end/39976] [4.5/4.6/4.7 Regression] Big sixtrack degradation on powerpc 32/64 after revision r146817

[jiangning.liu at arm dot com]

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

--- Comment #44 from Jiangning Liu <jiangning.liu at arm dot com> 2012-02-24 08:09:25 UTC ---
I'm not sure if this kind of bug has been completely fixed, and posted a
qeustion in mail list at http://gcc.gnu.org/ml/gcc/2012-02/msg00415.html .