[Bug rtl-optimization/45685] [4.6 Regression] GCC optimizer for Intel x64 generates inefficient code

[Bug rtl-optimization/45685] [4.6 Regression] GCC optimizer for Intel x64 generates inefficient code

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |missed-optimization
           Priority|P3                          |P2

[Bug rtl-optimization/45685] [4.6 Regression] GCC optimizer for Intel x64 generates inefficient code

[jakub at gcc dot gnu.org]

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

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

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

--- Comment #8 from Jakub Jelinek <jakub at gcc dot gnu.org> 2010-11-04 17:41:45 UTC ---
With -fno-tree-loop-if-convert -O3 the generated code for #c4 testcase is
actually better, but still one insn longer than 4.4.x.

[Bug rtl-optimization/45685] [4.6 Regression] GCC optimizer for Intel x64 generates inefficient code

[ebotcazou at gcc dot gnu.org]

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

Eric Botcazou <ebotcazou at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |ASSIGNED
                 CC|                            |ebotcazou at gcc dot
                   |                            |gnu.org
         AssignedTo|unassigned at gcc dot       |ebotcazou at gcc dot
                   |gnu.org                     |gnu.org

--- Comment #9 from Eric Botcazou <ebotcazou at gcc dot gnu.org> 2010-11-24 15:15:20 UTC ---
Investigating.

[Bug rtl-optimization/45685] [4.6 Regression] GCC optimizer for Intel x64 generates inefficient code

[jakub at gcc dot gnu.org]

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

--- Comment #10 from Jakub Jelinek <jakub at gcc dot gnu.org> 2010-11-24 15:27:41 UTC ---
I guess it would be helpful if some tree pass figured out that computing
cond_expr is usually quite expensive, and that instead of computing 4 different
cond_exprs (always one in wider type, one in narrower type and one with ? -1 :
1 and one with ? 1 : -1 for the same condition) it is more efficient to compute
it just once (in wider mode) and then negate and/or cast to narrower mode to
get the other needed results.

[Bug rtl-optimization/45685] [4.6 Regression] GCC optimizer for Intel x64 generates inefficient code

[rguenth at gcc dot gnu.org]

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

--- Comment #11 from Richard Guenther <rguenth at gcc dot gnu.org> 2010-11-24 15:55:45 UTC ---
Separating predicate computation from predicate use should help this.

[Bug tree-optimization/45685] [4.6 Regression] missed conditional move opportunity in loop

[ebotcazou at gcc dot gnu.org]

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

Eric Botcazou <ebotcazou at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |NEW
          Component|rtl-optimization            |tree-optimization
         AssignedTo|ebotcazou at gcc dot        |unassigned at gcc dot
                   |gnu.org                     |gnu.org

--- Comment #12 from Eric Botcazou <ebotcazou at gcc dot gnu.org> 2010-11-24 18:31:18 UTC ---
Clearly ifcvt.c is overwhelmed here and somewhat shoots itself in the foot.
The noce_emit_store_flag transformation in pass n creates insns that block the
cond_move_process_if_block conversion in pass n+1 because the new insns are
(rightfully) deemed unsuitable.  Quite tricky to overcome in my opinion.

As Jakub said, creating 3 almost identical cond_expr:

  prephitmp.9_39 = [cond_expr] D.2693_11 <= 0 ? -1 : 1;
  prephitmp.10_40 = [cond_expr] D.2693_11 <= 0 ? 1 : -1;
  prephitmp.11_41 = [cond_expr] D.2693_11 <= 0 ? 1 : -1;

for only one in the source code:

      int val = (products[i] > 0) ? 1 : -1;

is simply unreasonable.  Thus recategorizing.

[Bug tree-optimization/45685] [4.6 Regression] missed conditional move opportunity in loop

[ekuznetsov at divxcorp dot com]

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

--- Comment #13 from Eugene K. <ekuznetsov at divxcorp dot com> 2010-11-25 00:19:19 UTC ---
Further down in that gimple code

val_3 = [cond_expr] i_19 != D.2699_25 ? prephitmp.10_40 : val_4;
prephitmp.11_43 = [cond_expr] i_19 != D.2699_25 ? prephitmp.11_41 :
prephitmp.9_39;

this is duplicate too. The only difference seems to be that the result of one
operation is stored as a 64-bit type and the other is added to a 32-bit
variable. This trickles down into the assembly shown in comment 4 in both
versions: 4.4.4 produces two cmov instructions "cmovne %r11, %r8; cmove %r9d,
%ecx" where one should be sufficient, and 4.4.4 produces a cmov and a branch.

[Bug tree-optimization/45685] [4.6 Regression] missed conditional move opportunity in loop

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |rguenth at gcc dot gnu.org,
                   |                            |spop at gcc dot gnu.org

--- Comment #14 from Richard Guenther <rguenth at gcc dot gnu.org> 2010-11-25 11:13:06 UTC ---
First of all tree if-conversion goes crazy here.

What Jakub refers to (optimizing the constants) should be done while we
still have the PHIs around:

<bb 5>:
  # val_4 = PHI <1(4), -1(3)>
  # prephitmp.26_45 = PHI <-1(4), 1(3)>
  # prephitmp.27_46 = PHI <4294967295(4), 1(3)>
  # prephitmp.27_48 = PHI <1(4), 4294967295(3)>

here at least prephitmp.26_45 = -val_4, prephitmp.27_46 = -prephitmp.27_48,
etc.

Now - we can teach PRE not to do PHI insertions for sign changes or
negations, but it's hard to tell if the insertion involved further
simplifications that are worthwhile.

We go from

<bb 5>:
  # val_4 = PHI <1(4), -1(11)>
...
  if (D.4323_24 != i_19)
    goto <bb 6>;
  else
    goto <bb 12>;

<bb 12>:
  goto <bb 7>;

<bb 6>:
  val_25 = -val_4;

<bb 7>:
  # val_3 = PHI <val_4(12), val_25(6)>
...
  D.4326_28 = (unsigned int) val_3;

to the above, inserting for -val_4 and (unsigned int) val_3.

That said, if-conversion should be improved for the case of generating
constants.

[Bug tree-optimization/45685] [4.6 Regression] missed conditional move opportunity in loop

[law at redhat dot com]

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

Jeffrey A. Law <law at redhat dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |law at redhat dot com

--- Comment #15 from Jeffrey A. Law <law at redhat dot com> 2011-01-24 16:56:02 UTC ---
Alternately, we could have phi-opts clean this up.  ISTM it's not that complex
to determine if two PHI nodes have closely related values such as negation,
trivial conversions, etc.

While this kind of optimization doesn't directly result in a performance
improvement, it may make it easier for later opts to improve the code.  This
would help codesize as we'd be replacing a pair of constant loads with a
negation, trivial type conversion, etc.

[Bug tree-optimization/45685] [4.6 Regression] missed conditional move opportunity in loop

[law at redhat dot com]

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

Jeffrey A. Law <law at redhat dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Blocks|                            |42632
   Target Milestone|4.6.0                       |4.7.0

--- Comment #17 from Jeffrey A. Law <law at redhat dot com> 2011-02-17 19:41:27 UTC ---
Potential fix is attached.  Gets the desired code, triggers several hundred
times during a bootstrap.  Haven't checked compile-time, runtime performance or
codesize issues.  Did verify bootstrap & regression test were on
x86_64-unknown-linux-gnu.

Clearly not stage4 material.

[Bug tree-optimization/45685] [4.6 Regression] missed conditional move opportunity in loop

[law at redhat dot com]

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

--- Comment #16 from Jeffrey A. Law <law at redhat dot com> 2011-02-17 19:39:24 UTC ---
Created attachment 23389
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=23389
potential fix

[Bug tree-optimization/45685] [4.6/4.7 Regression] missed conditional move opportunity in loop

[jakub at gcc dot gnu.org]

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

--- Comment #18 from Jakub Jelinek <jakub at gcc dot gnu.org> 2011-12-01 22:41:46 UTC ---
What about stage3 material?

[Bug tree-optimization/45685] [4.6/4.7 Regression] missed conditional move opportunity in loop

[law at redhat dot com]

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

--- Comment #19 from Jeffrey A. Law <law at redhat dot com> 2011-12-02 05:26:00 UTC ---
I did some runtime testing on this shortly after 4.7 stage1 opened; the net
result was actually a regression.  I didn't delve into why due to time
constraints.

Without analysis as to why the patch regressed spec, I wouldn't be comfortable
suggesting it for any stage.

jeff

[Bug tree-optimization/45685] [4.6/4.7 Regression] missed conditional move opportunity in loop

[rguenth at gcc dot gnu.org]

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

--- Comment #20 from Richard Guenther <rguenth at gcc dot gnu.org> 2011-12-02 09:52:27 UTC ---
Probably a better place than phi-opt would be RTL expansion (thus, out-of-SSA
for the PHI nodes) where based on target cost those constants could be
materialized differently.

[Bug tree-optimization/45685] [4.6/4.7/4.8 Regression] missed conditional move opportunity in loop

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.7.0                       |4.7.1

--- Comment #21 from Richard Guenther <rguenth at gcc dot gnu.org> 2012-03-22 08:27:33 UTC ---
GCC 4.7.0 is being released, adjusting target milestone.

[Bug tree-optimization/45685] [4.6/4.7/4.8 Regression] missed conditional move opportunity in loop

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.7.1                       |4.7.2

--- Comment #22 from Richard Guenther <rguenth at gcc dot gnu.org> 2012-06-14 08:50:56 UTC ---
GCC 4.7.1 is being released, adjusting target milestone.

[Bug tree-optimization/45685] [4.6/4.7/4.8 Regression] missed conditional move opportunity in loop

[jakub at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.7.2                       |4.7.3

--- Comment #23 from Jakub Jelinek <jakub at gcc dot gnu.org> 2012-09-20 10:21:23 UTC ---
GCC 4.7.2 has been released.

[Bug tree-optimization/45685] [4.6/4.7/4.8 Regression] missed conditional move opportunity in loop

[steven at gcc dot gnu.org]

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

Steven Bosscher <steven at gcc dot gnu.org> changed:

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

--- Comment #24 from Steven Bosscher <steven at gcc dot gnu.org> 2013-03-13 20:45:30 UTC ---
(In reply to comment #19)
> I did some runtime testing on this shortly after 4.7 stage1 opened; the
> net result was actually a regression.  I didn't delve into why due to
> time constraints.
> 
> Without analysis as to why the patch regressed spec, I wouldn't be
> comfortable suggesting it for any stage.

Still looks like an interesting approach, tho'.
Do you plan to have a look at this for GCC 4.9?

[Bug tree-optimization/45685] [4.6/4.7/4.8/4.9 Regression] missed conditional move opportunity in loop

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.7.3                       |4.7.4

--- Comment #25 from Richard Biener <rguenth at gcc dot gnu.org> 2013-04-11 07:59:44 UTC ---
GCC 4.7.3 is being released, adjusting target milestone.

[Bug tree-optimization/45685] [4.7/4.8/4.9 Regression] missed conditional move opportunity in loop

[law at redhat dot com]

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

--- Comment #26 from Jeffrey A. Law <law at redhat dot com> ---
Looking at this again, I think there's another solution.  Basically we've got
conditional negation occurring in both loops.   There's a reasonably good
sequence to turn that into straight line code.

result = (input ^ -cond) + cond

Will negate the input when cond is true.  It looks a bit ugly, but
significantly helps simplify the first loop where we go from 23 insns down to
just 18 insns.  It helps the second loop as well, but the results aren't as
dramatic.

>From an implementation standpoint, it fits quite well into the existing phi-opt
code structure.

[Bug tree-optimization/45685] [4.7/4.8/4.9 Regression] missed conditional move opportunity in loop

[law at gcc dot gnu.org]

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

--- Comment #27 from Jeffrey A. Law <law at gcc dot gnu.org> ---
Author: law
Date: Fri Dec 13 16:34:39 2013
New Revision: 205963

URL: http://gcc.gnu.org/viewcvs?rev=205963&root=gcc&view=rev
Log:
    PR tree-optimization/45685
    * tree-ssa-phiopt.c (neg_replacement): New function.
    (tree_ssa_phiopt_worker): Call it.

    PR tree-optimization/45685
    * gcc.dg/tree-ssa/pr45685.c: New test.

Added:
    trunk/gcc/testsuite/gcc.dg/tree-ssa/pr45685.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/tree-ssa-phiopt.c

[Bug tree-optimization/45685] [4.7/4.8/4.9 Regression] missed conditional move opportunity in loop

[law at redhat dot com]

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

Jeffrey A. Law <law at redhat dot com> changed:

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

--- Comment #28 from Jeffrey A. Law <law at redhat dot com> ---
Resolved by recent checkin.

[Bug tree-optimization/45685] [4.7/4.8/4.9 Regression] missed conditional move opportunity in loop

[ktkachov at gcc dot gnu.org]

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

ktkachov at gcc dot gnu.org changed:

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

--- Comment #29 from ktkachov at gcc dot gnu.org ---
Created attachment 31445
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=31445&action=edit
Dump from phiopt1 pass on arm

Hi Jeff,

This test now fails on arm. I've attached the dump that I get. We don't do any
conversion on arm now.

[Bug tree-optimization/45685] [4.7/4.8/4.9 Regression] missed conditional move opportunity in loop

[ktkachov at gcc dot gnu.org]

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

ktkachov at gcc dot gnu.org changed:

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

--- Comment #30 from ktkachov at gcc dot gnu.org ---
Reopening...

[Bug tree-optimization/45685] [4.7/4.8/4.9 Regression] missed conditional move opportunity in loop

[ktkachov at gcc dot gnu.org]

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

ktkachov at gcc dot gnu.org changed:

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

--- Comment #31 from ktkachov at gcc dot gnu.org ---
It seems I just had a weird out-of date tree. It passes on trunk. Sorry for the
noise

[Bug rtl-optimization/45685] New: GCC optimizer for Intel x64 generates inefficient code

[ekuznetsov at divxcorp dot com]

I've attached two copies of a simple function. They are identical except for
the type of the internal variable (one uses 'int64_t', the other uses 'int').
When compiled with GCC 4.4.3 on a x64 platform using -O3 optimizations, the
assembly code for the first version will contain a conditional move instruction
'cmov', the second version will contain a branch. Since branches are extremely
slow, the second version ends up two times slower than the first version.


-- 
           Summary: GCC optimizer for Intel x64 generates inefficient code
           Product: gcc
           Version: 4.4.3
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: rtl-optimization
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: ekuznetsov at divxcorp dot com


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

[Bug rtl-optimization/45685] [4.6 Regression] GCC optimizer for Intel x64 generates inefficient code

[hjl dot tools at gmail dot com]

------- Comment #6 from hjl dot tools at gmail dot com  2010-09-17 13:04 -------
(In reply to comment #4)
> This all happens in IF conversion pass.
> 
> 4.6 regresses in the sense that a branch is emitted instead of cmov for:
> 

This is caused by revision 159106:

http://gcc.gnu.org/ml/gcc-cvs/2010-05/msg00156.html


-- 

hjl dot tools at gmail dot com changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |matz at suse dot de
            Summary|GCC optimizer for Intel x64 |[4.6 Regression] GCC
                   |generates inefficient code  |optimizer for Intel x64
                   |                            |generates inefficient code
   Target Milestone|---                         |4.6.0
            Version|4.4.3                       |4.6.0


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

[Bug rtl-optimization/45685] [4.6 Regression] GCC optimizer for Intel x64 generates inefficient code

[matz at gcc dot gnu dot org]

------- Comment #7 from matz at gcc dot gnu dot org  2010-09-17 13:45 -------
It might have been exposed by that revision, but that merely points out
a deficiency in RTL if conversion.  The final gimple code doesn't have
explicit jumps in the inner loop, but uses cond_expr:

<bb 3>:
  # s_22 = PHI <0(2), s_30(3)>
  # i_19 = PHI <0(2), i_31(3)>
  D.2693_11 = MEM[base: products_9(D), index: i_19, step: 8, offset: 0B];
  val_4 = [cond_expr] D.2693_11 <= 0 ? -1 : 1;
  prephitmp.9_39 = [cond_expr] D.2693_11 <= 0 ? -1 : 1;
  prephitmp.10_40 = [cond_expr] D.2693_11 <= 0 ? 1 : -1;
  prephitmp.11_41 = [cond_expr] D.2693_11 <= 0 ? 1 : -1;
  D.2698_21 = D.2693_11 * prephitmp.9_39;
  D.2699_25 = (long unsigned int) D.2698_21;
  val_3 = [cond_expr] i_19 != D.2699_25 ? prephitmp.10_40 : val_4;
  prephitmp.11_43 = [cond_expr] i_19 != D.2699_25 ? prephitmp.11_41 :
prephitmp.9_39;
  MEM[base: products_9(D), index: i_19, step: 8, offset: 0B] = prephitmp.11_43;
  s_30 = val_3 + s_22;
  i_31 = i_19 + 1;
  if (i_31 != count_7(D))
    goto <bb 3>;
  else
    goto <bb 4>;


-- 


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