[Bug rtl-optimization/110034] New: The first popped allcono doesn't take precedence over later popped in ira coloring

[Bug rtl-optimization/110034] New: The first popped allcono doesn't take precedence over later popped in ira coloring

[guihaoc at gcc dot gnu.org]

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

            Bug ID: 110034
           Summary: The first popped allcono doesn't take precedence over
                    later popped in ira coloring
           Product: gcc
           Version: 13.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: rtl-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: guihaoc at gcc dot gnu.org
  Target Milestone: ---

Followings are ira dumps from a test case. r134 has only one cp(shuffle) with
r173. The r173 and r124 both have preferred hard register r3. r134 is first
popped the register but it fails to get hard register r3 as the conflict cost
is high. If r173 is aheaf of r134, the r134 can get hard register r3 as there
is no hop between r3 and r134 after r173 is assigned r3. Seems the first popped
allcono(r134) doesn't take precedence over later popped allcono(r124).

r173 has a preferred hard register and has no conflict allcono. So r173 can
always be assigned r3. 

;; a29(r173,l0) conflicts:
;;     total conflict hard regs:
;;     conflict hard regs:

...

  cp11:a18(r134)<->a29(r173)@125:shuffle
  pref0:a12(r158)<-hr100@711
  pref1:a23(r144)<-hr100@920
  pref2:a25(r140)<-hr100@1842
  pref3:a29(r173)<-hr3@2000
  pref4:a0(r124)<-hr3@125

...

        Start updating from pref of hr3 for a29r173:
          a18r134 (hr3): update cost by -62, conflict cost by -62

...

      Pushing a1(r169,l0)(cost 0)
      Pushing a0(r124,l0)(cost 0)
      Pushing a22(r146,l0)(cost 0)
      Pushing a20(r125,l0)(cost 0)
      Pushing a29(r173,l0)(cost 0)
      Pushing a18(r134,l0)(cost 0)
      Popping a18(r134,l0)  -- (9=0,0) (10=0,0) (8=0,0) (7=0,0) (6=0,0) (5=0,0)
(4=0,0) (3=-62,147) (11=0,0) (0=8000,8000) (31=7,7) (30=7,7) (29=7,7) (28=7,7)
(27=7,7) (26=7,7) (25=7,7) (24=7,7) (23=7,7) (22=7,7) (21=7,7) (20=7,7)
(19=7,7) (18=7,7) (17=7,7) (16=7,7) (15=7,7) (14=7,7) (12=0,0)
        Start restoring from a18r134:
          a29r173 (hr3): update cost by -62, conflict cost by -62
        Start updating from a18r134 by copies:
          a29r173 (hr9): update cost by -250, conflict cost by -250
        assign reg 9
      Popping a29(r173,l0)  -- (9=1750,1750) (10=2000,2000) (8=2000,2000)
(7=2000,2000) (6=2000,2000) (5=2000,2000) (4=2000,2000) (3=-2062,-2062)
(11=2000,2000) (0=2000,2000) (31=2007,2007) (30=2007,2007) (29=2007,2007)
(28=2007,2007) (27=2007,2007) (26=2007,2007) (25=2007,2007) (24=2007,2007)
(23=2007,2007) (22=2007,2007) (21=2007,2007) (20=2007,2007) (19=2007,2007)
(18=2007,2007) (17=2007,2007) (16=2007,2007) (15=2007,2007) (14=2007,2007)
(12=2000,2000)
        Start restoring from a29r173:
        Start updating from a29r173 by copies:
        assign reg 3

...

      Popping a0(r124,l0)  -- (8=0,0) (7=0,0) (6=0,0) (5=0,0) (4=0,0)
(3=-250,-250) (11=0,0) (0=0,0) (31=7,7) (30=7,7) (29=7,7) (28=7,7) (27=7,7)
(26=7,7) (25=7,7) (24=7,7) (23=7,7) (22=7,7) (21=7,7) (20=7,7) (19=7,7)
(18=7,7) (17=7,7) (16=7,7) (15=7,7) (14=7,7) (12=0,0)
        Start restoring from a0r124:
        Start updating from a0r124 by copies:
          a1r169 (hr3): update cost by -44, conflict cost by -44
          a2r177 (hr3): update cost by -11, conflict cost by -11
        assign reg 3

[Bug rtl-optimization/110034] The first popped allcono doesn't take precedence over later popped in ira coloring

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |missed-optimization, ra
                 CC|                            |vmakarov at gcc dot gnu.org

--- Comment #1 from Richard Biener <rguenth at gcc dot gnu.org> ---
Do you have a testcase that reproduces this?  Please also specify target and
options.

[Bug rtl-optimization/110034] The first popped allcono doesn't take precedence over later popped in ira coloring

[guihaoc at gcc dot gnu.org]

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

HaoChen Gui <guihaoc at gcc dot gnu.org> changed:

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

--- Comment #2 from HaoChen Gui <guihaoc at gcc dot gnu.org> ---
Created attachment 55214
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=55214&action=edit
test case

Compile it with -O3 -mcpu=power9 -fira-verbose=20 > ira_dump.out 2>&1

[Bug rtl-optimization/110034] The first popped allcono doesn't take precedence over later popped in ira coloring

[guihaoc at gcc dot gnu.org]

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

--- Comment #3 from HaoChen Gui <guihaoc at gcc dot gnu.org> ---
Created attachment 55215
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=55215&action=edit
ira dump

[Bug rtl-optimization/110034] The first popped allcono doesn't take precedence over later popped in ira coloring

[vmakarov at gcc dot gnu.org]

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

--- Comment #4 from Vladimir Makarov <vmakarov at gcc dot gnu.org> ---
Thank you for providing the test case.

To be honest I don't see why assigning to hr3 to r134 is better.
Currently we have the following assignments:

hr9->r134; hr3->r173; hr3->r124

and the related preferences:

  cp11:a18(r134)<->a29(r173)@125:shuffle
  pref3:a29(r173)<-hr3@2000
  pref4:a0(r124)<-hr3@125

This removes cost 2000 (pref3) and cost 125 (pref4) and adds cost 125
(cp11).  The profit is 2000

If we started with r173, we would have the following assignments:

hr3->r173; hr3->r134; <some hard reg but hr3>->r124

This would remove cost 2000 (pref3) and cost 125 (cp11) and add cost
125 (pref).  The profit would be the same 2000.

Choice of heuristics is very time consuming.  I spent a lot of time to
try and benchmark numerous ones.  I clearly remember that introduction
of pseudo threads for colorable busket gave visible performance
improvement.  Currently we assign pseudos from a thread with the
biggest frequency first (r173 and r134) and a pseudo (r134) with the
biggest frequency first from the same thread.  I think it is logical.

Also it is always possible to find a test (not this case) where
heuristics give some undesirable results.  RA is NP-complete task even
in the simplest formulation. We can not get the optimal solution for
reasonable time.

Still I am open to change any heuristic if somebody can show that it
improves performance for some credible benchmark (I prefer SPEC2007)
on major GCC targets.

[Bug rtl-optimization/110034] The first popped allcono doesn't take precedence over later popped in ira coloring

[guihaoc at gcc dot gnu.org]

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

--- Comment #5 from HaoChen Gui <guihaoc at gcc dot gnu.org> ---
(In reply to Vladimir Makarov from comment #4)
> Thank you for providing the test case.
> 
> To be honest I don't see why assigning to hr3 to r134 is better.
> Currently we have the following assignments:
> 
> hr9->r134; hr3->r173; hr3->r124
> 
> and the related preferences:
> 
>   cp11:a18(r134)<->a29(r173)@125:shuffle
>   pref3:a29(r173)<-hr3@2000
>   pref4:a0(r124)<-hr3@125
> 
> This removes cost 2000 (pref3) and cost 125 (pref4) and adds cost 125
> (cp11).  The profit is 2000
> 
> If we started with r173, we would have the following assignments:
> 
> hr3->r173; hr3->r134; <some hard reg but hr3>->r124
> 
> This would remove cost 2000 (pref3) and cost 125 (cp11) and add cost
> 125 (pref).  The profit would be the same 2000.
> 
> Choice of heuristics is very time consuming.  I spent a lot of time to
> try and benchmark numerous ones.  I clearly remember that introduction
> of pseudo threads for colorable busket gave visible performance
> improvement.  Currently we assign pseudos from a thread with the
> biggest frequency first (r173 and r134) and a pseudo (r134) with the
> biggest frequency first from the same thread.  I think it is logical.
> 
> Also it is always possible to find a test (not this case) where
> heuristics give some undesirable results.  RA is NP-complete task even
> in the simplest formulation. We can not get the optimal solution for
> reasonable time.
> 
> Still I am open to change any heuristic if somebody can show that it
> improves performance for some credible benchmark (I prefer SPEC2007)
> on major GCC targets.

Thanks for your explanation. I agree with it. I also checked the assembly and
found there is no potential performance gain when r3 is assigned to r134. It
should be not a bug.

[Bug rtl-optimization/110034] The first popped allcono doesn't take precedence over later popped in ira coloring

[guihaoc at gcc dot gnu.org]

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

HaoChen Gui <guihaoc at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         Resolution|---                         |INVALID
             Status|UNCONFIRMED                 |RESOLVED

--- Comment #6 from HaoChen Gui <guihaoc at gcc dot gnu.org> ---
It's not a problem.