[Bug rtl-optimization/56069] New: [4.6/4.7/4.8 Regression] RA pessimization

[Bug rtl-optimization/56069] New: [4.6/4.7/4.8 Regression] RA pessimization

[jakub at gcc dot gnu.org]

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

             Bug #: 56069
           Summary: [4.6/4.7/4.8 Regression] RA pessimization
    Classification: Unclassified
           Product: gcc
           Version: 4.8.0
            Status: UNCONFIRMED
          Keywords: missed-optimization, ra
          Severity: normal
          Priority: P3
         Component: rtl-optimization
        AssignedTo: unassigned@gcc.gnu.org
        ReportedBy: jakub@gcc.gnu.org
                CC: rsandifo@gcc.gnu.org, vmakarov@gcc.gnu.org
            Target: x86_64-linux


Since http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=139993
unsigned long foo (unsigned long mem)
{
  return (mem >> 3) | (1UL << 44);
}

unsigned long bar (unsigned long mem)
{
  return (mem >> 3) + (1UL << 44);
}

on x86_64-linux at -O2 (and -Os) the generated code for foo is one insn longer.
We used to emit:
        shrq    $3, %rdi
        movabsq $17592186044416, %rax
        orq     %rdi, %rax
        ret
but now emit:
        movq    %rdi, %rax
        movabsq $17592186044416, %rdx
        shrq    $3, %rax
        orq     %rdx, %rax
        ret

[Bug rtl-optimization/56069] [4.6/4.7/4.8 Regression] RA pessimization

[vmakarov at gcc dot gnu.org]

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

--- Comment #1 from Vladimir Makarov <vmakarov at gcc dot gnu.org> 2013-01-21 21:56:02 UTC ---
LRA does not generate any reloads (additional insns).  So I don't think it is
LRA problem.  I've checked reload.  It generates the same code.

Although I guess, it is IRA problem.  It should assign other hard registers to
improve the code.

I'll try to find a solution.

[Bug rtl-optimization/56069] [4.6/4.7/4.8 Regression] RA pessimization

[vmakarov at redhat dot com]

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

Vladimir Makarov <vmakarov at redhat dot com> changed:

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

--- Comment #2 from Vladimir Makarov <vmakarov at redhat dot com> 2013-01-22 21:01:21 UTC ---
It is definitely regmove pass drawback.  IRA can do nothing in this
case.

We have the following code before and after regmove:

    2: r62:DI=di:DI                          2: r63:DI=di:DI
      REG_DEAD di:DI                           REG_DEAD di:DI
    6: {r64:DI=r62:DI 0>>0x3;clobber fla     6: {r63:DI=r63:DI 0>>0x3;clobber
fl
      REG_DEAD r62:DI
    7: r65:DI=0x100000000000                 7: r65:DI=0x100000000000
    8: {r63:DI=r64:DI|r65:DI;clobber fla     8: {r63:DI=r63:DI|r65:DI;clobber
fl
      REG_DEAD r65:DI                          REG_DEAD r65:DI
      REG_DEAD r64:DI
   13: ax:DI=r63:DI                         13: ax:DI=r63:DI
      REG_DEAD r63:DI                          REG_DEAD r63:DI
   16: use ax:DI                            16: use ax:DI

Regmove changes r64 to r63.  It makes two equal hard reg preferences
for r63: AX or DI. Choosing either one results in worse code.

The original generated code can be achieved if regmove changes r65 to
r63.  In this case we have only one hard register preference for r63
(AX) and for r62 (DI).

It can be achieved if regmove tries all orders of commutative operands
(now regmove pass uses the first found order) using additional
heuristics (live range length and/or number of preferred hard regs) to
choose the best order.

It is not a trivial change and can not be done for given release
(gcc4.8).

Also now we have LRA and may be such regmove transformations are not
necessary.  I am going to try this for gcc4.9 when I have more time.
Still to assign ax to r65 and r63 we also need some hard register
preference propagations in IRA which is currently absent.

In any case, I think that older releases were just lucky and generated
the best code as some passes before regmove put r65 as a first input
operand.

[Bug rtl-optimization/56069] [4.6/4.7/4.8/4.9 Regression] RA pessimization

[jakub at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|---                         |4.9.0
            Summary|[4.6/4.7/4.8 Regression] RA |[4.6/4.7/4.8/4.9
                   |pessimization               |Regression] RA
                   |                            |pessimization

--- Comment #3 from Jakub Jelinek <jakub at gcc dot gnu.org> 2013-01-22 21:10:34 UTC ---
Deferring for 4.9 then.

[Bug rtl-optimization/56069] [4.7/4.8/4.9 Regression] RA pessimization

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Priority|P3                          |P2
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2013-10-25
     Ever confirmed|0                           |1

--- Comment #4 from Richard Biener <rguenth at gcc dot gnu.org> ---
Confirmed on trunk.

[Bug rtl-optimization/56069] [4.7/4.8/4.9 Regression] RA pessimization

[law at redhat dot com]

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

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

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

--- Comment #5 from Jeffrey A. Law <law at redhat dot com> ---
Maybe I'm missing something here.  We have this immediately prior to IRA:

(insn 2 4 3 2 (set (reg/v:DI 86 [ mem ])
        (reg:DI 5 di [ mem ])) j.c:2 89 {*movdi_internal}
     (expr_list:REG_DEAD (reg:DI 5 di [ mem ])
        (nil)))
(note 3 2 6 2 NOTE_INSN_FUNCTION_BEG)
(insn 6 3 7 2 (parallel [
            (set (reg:DI 88 [ D.1760 ])
                (lshiftrt:DI (reg/v:DI 86 [ mem ])
                    (const_int 3 [0x3])))
            (clobber (reg:CC 17 flags))
        ]) j.c:3 562 {*lshrdi3_1}
     (expr_list:REG_DEAD (reg/v:DI 86 [ mem ])
        (expr_list:REG_UNUSED (reg:CC 17 flags)
            (nil))))
(insn 7 6 8 2 (set (reg:DI 89)
        (const_int 17592186044416 [0x100000000000])) j.c:3 89 {*movdi_internal}
     (nil))
(insn 8 7 13 2 (parallel [
            (set (reg:DI 87 [ D.1760 ])
                (ior:DI (reg:DI 88 [ D.1760 ])
                    (reg:DI 89)))
            (clobber (reg:CC 17 flags))
        ]) j.c:3 421 {*iordi_1}
     (expr_list:REG_DEAD (reg:DI 89)
        (expr_list:REG_DEAD (reg:DI 88 [ D.1760 ])
            (expr_list:REG_UNUSED (reg:CC 17 flags)
                (expr_list:REG_EQUAL (ior:DI (reg:DI 88 [ D.1760 ])
                        (const_int 17592186044416 [0x100000000000]))
                    (nil))))))
(insn 13 8 16 2 (set (reg/i:DI 0 ax)
        (reg:DI 87 [ D.1760 ])) j.c:4 89 {*movdi_internal}
     (expr_list:REG_DEAD (reg:DI 87 [ D.1760 ])
        (nil)))
(insn 16 13 0 2 (use (reg/i:DI 0 ax)) j.c:4 -1
     (nil))

ISTM that we want (reg 86) to prefer di and (reg 87) to prefer ax by way of the
hard register copies.  (reg 88) should then prefer di by way of insn 6.

(reg 89) really doesn't need a preference and can go anywhere that doesn't
conflict.

So if we look at the IRA dump we have:

Pass 1 for finding pseudo/allocno costs

    r89: preferred GENERAL_REGS, alternative NO_REGS, allocno GENERAL_REGS
    r88: preferred GENERAL_REGS, alternative NO_REGS, allocno GENERAL_REGS
    r87: preferred AREG, alternative GENERAL_REGS, allocno GENERAL_REGS
    r86: preferred DIREG, alternative GENERAL_REGS, allocno GENERAL_REGS

Which I guess is OK.  A bit surprised to not see r88 preferring DIreg at this
point, but I guess copies implied by the 2 operand nature are handled later.

ISTM that the copy implied by insn 6 should result in 88 somehow preferring
DIreg.  Then, ideally we'd see that while 89 can go anywhere it's best to match
it with 87.

Vlad, what am I missing here?

[Bug rtl-optimization/56069] [4.7/4.8/4.9 Regression] RA pessimization

[vmakarov at gcc dot gnu.org]

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

--- Comment #6 from Vladimir Makarov <vmakarov at gcc dot gnu.org> ---
(In reply to Jeffrey A. Law from comment #5)
> Maybe I'm missing something here.  We have this immediately prior to IRA:
> 

> ISTM that we want (reg 86) to prefer di and (reg 87) to prefer ax by way of
> the hard register copies.  (reg 88) should then prefer di by way of insn 6.
> 
> (reg 89) really doesn't need a preference and can go anywhere that doesn't
> conflict.
> 
> So if we look at the IRA dump we have:
> 
> Pass 1 for finding pseudo/allocno costs
> 
>     r89: preferred GENERAL_REGS, alternative NO_REGS, allocno GENERAL_REGS
>     r88: preferred GENERAL_REGS, alternative NO_REGS, allocno GENERAL_REGS
>     r87: preferred AREG, alternative GENERAL_REGS, allocno GENERAL_REGS
>     r86: preferred DIREG, alternative GENERAL_REGS, allocno GENERAL_REGS
> 
> Which I guess is OK.  A bit surprised to not see r88 preferring DIreg at
> this point, but I guess copies implied by the 2 operand nature are handled
> later.
> 
> ISTM that the copy implied by insn 6 should result in 88 somehow preferring
> DIreg.  Then, ideally we'd see that while 89 can go anywhere it's best to
> match it with 87.
> 
> Vlad, what am I missing here?

Preferred/alternative class is misleading here.  It is not used anywhere in
IRA/LRA for allocation decision (but may be it is used by reload -- i don't
remember).  It is only used as a temporary result for allocno class
calculation.

Hard reg preferences and copies are further in the dump.  They looks as
following

cp0:a2(r88)<->a3(r86)@1000:constraint
cp1:a0(r87)<->a1(r89)@1000:constraint
cp2:a0(r87)<->a2(r88)@1000:constraint
pref0:a0(r87)<-hr0@1500
pref1:a3(r86)<-hr5@1500

This problem is well known me.  Jakub filled analogous PR.  I am working on it.
 The reason of the problem are copies created for commutative ops insns.  Two
copies give different signals for hard reg preferences through the propagation
mechanism.  It is easy to make a test for this problem because the test should
be small and involve arguments and result on small number of insns.  Therefore
we have a few such PRs.  In bigger function, the probability of the problem
occurrence is quite small.

[Bug rtl-optimization/56069] [4.7/4.8/4.9/4.10 Regression] RA pessimization

[jakub at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.9.0                       |4.9.1

--- Comment #7 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
GCC 4.9.0 has been released

[Bug rtl-optimization/56069] [4.8/4.9/4.10 Regression] RA pessimization

[jakub at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=56069

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.9.1                       |4.9.2

--- Comment #8 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
GCC 4.9.1 has been released.

[Bug rtl-optimization/56069] [4.8/4.9/5 Regression] RA pessimization

[jakub at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=56069

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.9.2                       |4.9.3

--- Comment #9 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
GCC 4.9.2 has been released.

[Bug rtl-optimization/56069] [4.9/5/6 Regression] RA pessimization

[jakub at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=56069

--- Comment #10 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
GCC 4.9.3 has been released.

[Bug rtl-optimization/56069] [4.9/5/6 Regression] RA pessimization

[jakub at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=56069

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.9.3                       |4.9.4

[Bug rtl-optimization/56069] [7 Regression] RA pessimization

[jakub at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=56069

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|9.3                         |9.4

--- Comment #23 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
GCC 9.3.0 has been released, adjusting target milestone.

[Bug rtl-optimization/56069] [7 Regression] RA pessimization

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=56069

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |ASSIGNED

[Bug rtl-optimization/56069] [7 Regression] RA pessimization

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=56069

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|9.4                         |9.5

--- Comment #24 from Richard Biener <rguenth at gcc dot gnu.org> ---
GCC 9.4 is being released, retargeting bugs to GCC 9.5.

[Bug rtl-optimization/56069] [7 Regression] RA pessimization

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=56069

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
   Target Milestone|9.5                         |8.0
         Resolution|---                         |FIXED

--- Comment #25 from Richard Biener <rguenth at gcc dot gnu.org> ---
Fixed for GCC 8 it seems.