[Bug tree-optimization/52424] New: dom prematurely pops entries from const_and_copies stack

[Bug tree-optimization/52424] New: dom prematurely pops entries from const_and_copies stack

[wschmidt at gcc dot gnu.org]

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

             Bug #: 52424
           Summary: dom prematurely pops entries from const_and_copies
                    stack
    Classification: Unclassified
           Product: gcc
           Version: 4.7.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
        AssignedTo: wschmidt@gcc.gnu.org
        ReportedBy: wschmidt@gcc.gnu.org
                CC: bergner@vnet.ibm.com, jiangning.liu@arm.com,
                    rguenther@suse.de


Created attachment 26775
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=26775
Proposed patch of tree-ssa-dom.c

Jiangning Liu reported that the following C code has recently experienced
degraded performance on trunk.  (Jiangning, please fill in the
Host/Target/Build fields for your configuration, or tell me what they are if
you don't have access.  The problem is not related to specific targets in any
event.)

int *l, *r, *g;
void test_func(int n)
{
    int i;
    static int j;
    static int pos, direction, direction_pre;

    pos = 0;
    direction = 1;

    for ( i = 0; i < n; i++ )
    {
        direction_pre = direction;

        for ( j = 0; j <= 400; j++ )
        {

            if ( g[pos] == 200 )
                break;

            if ( direction == 0 )
                pos = l[pos];
            else
                pos = r[pos];

            if ( pos == -1 )
            {
                if ( direction_pre != direction )
                    break;

                pos = 0;
                direction = !direction;
            }

        }

        f(g[pos]);
    }
}

When compiled with -O2, the dom2 details dump shows that a redundant phi is
detected in block 12:

<bb 12>:
  # prephitmp.28_89 = PHI <pos.4_18(10), pos.6_24(11)>
  # pos_lsm.33_53 = PHI <pos.4_18(10), pos.6_24(11)>

LKUP STMT prephitmp.28_89 = PHI <pos.4_18, pos.6_24>
          prephitmp.28_89 = PHI <pos.4_18(10), pos.6_24(11)>
2>>> STMT prephitmp.28_89 = PHI <pos.4_18, pos.6_24>
          prephitmp.28_89 = PHI <pos.4_18(10), pos.6_24(11)>
LKUP STMT pos_lsm.33_53 = PHI <pos.4_18, pos.6_24>
          pos_lsm.33_53 = PHI <pos.4_18(10), pos.6_24(11)>
FIND: prephitmp.28_89
0>>> COPY pos_lsm.33_53 = prephitmp.28_89

However, the COPY is incorrectly removed from the const_and_copy stack after
block 13 is processed.  It should not be removed until after the last block
dominated by bb12 (bb18) is processed.  As a result, the copy is not propagated
into a PHI in block 15:

  # pos_lsm.33_123 = PHI <pos_lsm.33_53(14)>

As a result, an extra copy is eventually introduced that degrades performance.

I tracked down the extra removal of const_and_copy stack entries to
tree-ssa-threadedge.c:remove_temporary_equivalences.  This removes pairs of
entries that were introduced by thread_across_edge, and also removes a NULL
marker entry beneath those entries.  Thus calls to thread_across_edge must be
preceded by a push of such a marker entry.

thread_across_edge is called from tree-ssa-dom.c:dom_thread_across_edge, which
is called in three places within dom_opt_leave_block.  In two of those places,
the push of a marker entry is present.  In the third, it isn't.  Adding the
marker push appears to correct the problem.

I've attached a proposed fix.  Jiangning, can you please apply this and see if
your performance problem is resolved?

Thanks,
Bill

[Bug tree-optimization/52424] dom prematurely pops entries from const_and_copies stack

[jiangning.liu at arm dot com]

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

--- Comment #1 from Jiangning Liu <jiangning.liu at arm dot com> 2012-02-29 03:23:46 UTC ---
> I've attached a proposed fix.  Jiangning, can you please apply this and see if
> your performance problem is resolved?

Bill,

Confirmed, I think your patch works for my big case and I do see the redundant
copies are removed from final binary code. Benchmark performance boosts
accordingly as well, although there still might be other potential problems.

Thanks a lot for your quick patch. And are you going to check-in to trunk soon
for 4.7? It would be also better if you can add a test case.

-Jiangning

[Bug tree-optimization/52424] dom prematurely pops entries from const_and_copies stack

[jiangning.liu at arm dot com]

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

--- Comment #2 from Jiangning Liu <jiangning.liu at arm dot com> 2012-02-29 03:42:17 UTC ---
> Jiangning Liu reported that the following C code has recently experienced
> degraded performance on trunk.  (Jiangning, please fill in the
> Host/Target/Build fields for your configuration, or tell me what they are if
> you don't have access.  The problem is not related to specific targets in any
> event.)
> 

Seems I don't have access.

Host: arm*-*-*
Target: arm*-*-*
Build: arm*-*-*

[Bug tree-optimization/52424] dom prematurely pops entries from const_and_copies stack

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2012-02-29
     Ever Confirmed|0                           |1

--- Comment #3 from Richard Guenther <rguenth at gcc dot gnu.org> 2012-02-29 09:13:19 UTC ---
At this point we'd need a testcase that regressed from a previous GCC release
and mark this bug as a regression.  The patch looks nearly obvious.

[Bug tree-optimization/52424] dom prematurely pops entries from const_and_copies stack

[wschmidt at gcc dot gnu.org]

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

--- Comment #4 from William J. Schmidt <wschmidt at gcc dot gnu.org> 2012-02-29 13:06:40 UTC ---
Author: wschmidt
Date: Wed Feb 29 13:06:28 2012
New Revision: 184662

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=184662
Log:
2012-02-29  Bill Schmidt  <wschmidt@linux.vnet.ibm.com>

    PR tree-optimization/52424
    * tree-ssa-dom.c (dom_opt_leave_block): Push a marker before
    calling dom_thread_across_edge.


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

[Bug tree-optimization/52424] dom prematurely pops entries from const_and_copies stack

[wschmidt at gcc dot gnu.org]

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

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

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

--- Comment #5 from William J. Schmidt <wschmidt at gcc dot gnu.org> 2012-02-29 13:08:15 UTC ---
Fixed.

[Bug tree-optimization/52424] dom prematurely pops entries from const_and_copies stack

[wschmidt at gcc dot gnu.org]

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

--- Comment #6 from William J. Schmidt <wschmidt at gcc dot gnu.org> 2012-02-29 20:26:33 UTC ---
Author: wschmidt
Date: Wed Feb 29 20:26:29 2012
New Revision: 184670

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=184670
Log:
2012-02-29  Bill Schmidt  <wschmidt@linux.vnet.ibm.com>

    PR tree-optimization/52424
    * tree-ssa-dom.c (dom_opt_leave_block): Push a marker before
    calling dom_thread_across_edge.


Modified:
    branches/ibm/gcc-4_5-branch/gcc/ChangeLog.ibm
    branches/ibm/gcc-4_5-branch/gcc/tree-ssa-dom.c

[Bug tree-optimization/52424] dom prematurely pops entries from const_and_copies stack

[wschmidt at gcc dot gnu.org]

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

--- Comment #7 from William J. Schmidt <wschmidt at gcc dot gnu.org> 2012-02-29 20:27:45 UTC ---
Author: wschmidt
Date: Wed Feb 29 20:27:41 2012
New Revision: 184671

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=184671
Log:
2012-02-29  Bill Schmidt  <wschmidt@linux.vnet.ibm.com>

    PR tree-optimization/52424
    * tree-ssa-dom.c (dom_opt_leave_block): Push a marker before
    calling dom_thread_across_edge.


Modified:
    branches/ibm/gcc-4_6-branch/gcc/ChangeLog.ibm
    branches/ibm/gcc-4_6-branch/gcc/tree-ssa-dom.c

[Bug tree-optimization/52424] dom prematurely pops entries from const_and_copies stack

[pinskia at gcc dot gnu.org]

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

--- Comment #8 from Andrew Pinski <pinskia at gcc dot gnu.org> 2012-02-29 20:47:34 UTC ---
I think this is related to PR 45685.

[Bug tree-optimization/52424] dom prematurely pops entries from const_and_copies stack

[wschmidt at gcc dot gnu.org]

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

--- Comment #9 from William J. Schmidt <wschmidt at gcc dot gnu.org> 2012-02-29 22:19:03 UTC ---
(In reply to comment #8)
> I think this is related to PR 45685.

On the surface this looked like a good possibility.  However, I just tried
compiling the code from that PR on powerpc64 with this patch applied (-O3 -S
-mcpu=power7 -misel) and summation_helper_1 is still generating an extra branch
while summation_helper_2 produces a conditional move.

The only difference in the tree-optimized dumps between the two involve
cond_exprs whose operands appear in reverse order, and some of the -1's are
(unsigned)(-1) instead (i.e., 4294967295).  This appears to be enough for ifcvt
to miss the opportunity.