Coloring problem - Pass 0 for finding allocno costs

Coloring problem - Pass 0 for finding allocno costs

[Frank Isamov]

Hi,

In my backend, I have a problem with the pass which determines the
best register class for a virtual register (Pass 0 for finding allocno
costs).

In all insns in this example both R_REGS and D_REGS register classes
are applicable (but all registers in an insn should be from the same
register class).

This is asmcons output:

;; Function mul (mul)
(note 1 0 5 NOTE_INSN_DELETED)

(note 5 1 2 2 [bb 2] NOTE_INSN_BASIC_BLOCK)

(note 2 5 3 2 NOTE_INSN_DELETED)

(insn 3 2 4 2 a.c:2 (set (reg/v:SI 97 [ b ])
        (reg:SI 49 r1 [ b ])) 43 {movsi_regs} (expr_list:REG_DEAD
(reg:SI 49 r1 [ b ])
        (nil)))

(note 4 3 7 2 NOTE_INSN_FUNCTION_BEG)

(insn 7 4 9 2 a.c:5 (set (reg/v:SI 94 [ __a_11 ])
        (plus:SI (reg:SI 48 r0 [ a ])
            (reg/v:SI 97 [ b ]))) 0 {*addsi3_1} (expr_list:REG_DEAD
(reg:SI 48 r0 [ a ])
        (nil)))

(insn 9 7 10 2 a.c:5 (parallel [
            (set (reg:SI 100)
                (ashift:SI (reg/v:SI 97 [ b ])
                    (const_int 3 [0x3])))
            (clobber (reg:CC 88 cc))
        ]) 36 {ashlsi3} (expr_list:REG_UNUSED (reg:CC 88 cc)
        (expr_list:REG_EQUAL (ashift:SI (reg/v:SI 97 [ b ])
                (const_int 3 [0x3]))
            (nil))))

(insn 10 9 11 2 a.c:5 (set (reg:SI 101)
        (plus:SI (reg:SI 100)
            (reg/v:SI 97 [ b ]))) 0 {*addsi3_1} (expr_list:REG_DEAD (reg:SI 100)
        (expr_list:REG_DEAD (reg/v:SI 97 [ b ])
            (expr_list:REG_EQUAL (mult:SI (reg/v:SI 97 [ b ])
                    (const_int 9 [0x9]))
                (nil)))))

(insn 11 10 12 2 a.c:5 (set (reg:SI 102)
        (plus:SI (reg:SI 101)
            (reg/v:SI 94 [ __a_11 ]))) 0 {*addsi3_1}
(expr_list:REG_DEAD (reg:SI 101)
        (expr_list:REG_DEAD (reg/v:SI 94 [ __a_11 ])
            (nil))))

(note 12 11 17 2 NOTE_INSN_DELETED)

(insn 17 12 23 2 a.c:7 (parallel [
            (set (reg/i:SI 48 r0)
                (ashift:SI (reg:SI 102)
                    (const_int 10 [0xa])))
            (clobber (reg:CC 88 cc))
        ]) 36 {ashlsi3} (expr_list:REG_UNUSED (reg:CC 88 cc)
        (expr_list:REG_DEAD (reg:SI 102)
            (nil))))

(insn 23 17 0 2 a.c:7 (use (reg/i:SI 48 r0)) -1 (nil))

The problem I see is that for registers 100,101 I get best register
class D instead of R – actually they get the same cost and D is chosen
(maybe because it is first).

But they should not get the same cost since choosing D_REGS causes two
additional copies.

To my understanding the algorithm checks every insn, and since
register 100 appears only in insns in which all registers are still
virtual, any register class fits without additional cost. But later
when coloring it with d register, we need copies from r to d and back
to r.

Can someone please help with this?

Is there any reading material about this part of the IRA?

Thanks, Frank.

RE: Coloring problem - Pass 0 for finding allocno costs

[Ian Bolton]

> The problem I see is that for registers 100,101 I get best register
> class D instead of R - actually they get the same cost and D is chosen
> (maybe because it is first).

Hi Frank.

Do D and R overlap?  It would be useful to know which regs are in
which class, before trying to understand what is going on.

Can you paste an example of your define_insn from your MD file to show
how operands from D or R are both valid?  I ask this because it is
possible to express that D is more expensive than R with operand
constraints.

For general IRA info, you might like to look over my long thread on
here called "Understanding IRA".

Cheers,
Ian

Re: Coloring problem - Pass 0 for finding allocno costs

[Frank Isamov]

---------- Forwarded message ----------
From: Frank Isamov <frank.isamov@gmail.com>
Date: Thu, Mar 18, 2010 at 4:28 PM
Subject: Re: Coloring problem - Pass 0 for finding allocno costs
To: Ian Bolton <bolton@icerasemi.com>


On Thu, Mar 18, 2010 at 3:51 PM, Ian Bolton <bolton@icerasemi.com> wrote:
>> The problem I see is that for registers 100,101 I get best register
>> class D instead of R - actually they get the same cost and D is chosen
>> (maybe because it is first).
>
> Hi Frank.
>
> Do D and R overlap?  It would be useful to know which regs are in
> which class, before trying to understand what is going on.
>
> Can you paste an example of your define_insn from your MD file to show
> how operands from D or R are both valid?  I ask this because it is
> possible to express that D is more expensive than R with operand
> constraints.
>
> For general IRA info, you might like to look over my long thread on
> here called "Understanding IRA".
>
> Cheers,
> Ian
>

Hi Ian,

Thank you very much for your prompt reply.
D and R are not overlap. Please see fragments of .md and .h files below:

From the md:

(define_register_constraint "a" "R_REGS" "")
(define_register_constraint "d" "D_REGS" "")

(define_predicate "a_operand"
   (match_operand 0 "register_operand")
{
       unsigned int regno;
       if (GET_CODE (op) == SUBREG)
           op = SUBREG_REG (op);
       regno = REGNO (op);
       return (regno >= FIRST_PSEUDO_REGISTER ||
REGNO_REG_CLASS(regno) == R_REGS);
}
)

(define_predicate "d_operand"
   (match_operand 0 "register_operand")
{
       unsigned int regno;
       if (GET_CODE (op) == SUBREG)
           op = SUBREG_REG (op);
       regno = REGNO (op);
       return (regno >= FIRST_PSEUDO_REGISTER ||
REGNO_REG_CLASS(regno) == D_REGS);
}
)

(define_predicate "a_d_operand"
 (ior (match_operand 0 "a_operand")
      (match_operand 0 "d_operand")))

(define_predicate "i_a_d_operand"
 (ior (match_operand 0 "immediate_operand")
      (match_operand 0 "a_d_operand")))

(define_insn "mov<mode>_regs"
 [(set (match_operand:SISFM 0 "a_d_operand" "=a, a, a, d, d, d")
               (match_operand:SISFM 1 "i_a_d_operand"   "a, i, d, a, i, d"))]
 ""
 "move\t%1, %0"
)

(define_insn "*addsi3_1"
 [(set (match_operand:SI 0 "a_d_operand"    "=a, a,  a,d,d")
           (plus:SI (match_operand:SI 1 "a_d_operand" "%a, a,  a,d,d")
                           (match_operand:SI 2 "nonmemory_operand"
"U05,S16,a,d,U05")))]
 ""
 "adda\t%2, %1, %0"
)

;;  Arithmetic Left and Right Shift Instructions
(define_insn "<shPat><mode>3"
 [(set (match_operand:SCIM 0 "register_operand" "=a,d,d")
           (sh_oprnd:SCIM (match_operand:SCIM 1 "register_operand" "a,d,d")
                                   (match_operand:SI 2
"nonmemory_operand" "U05,d,U05")))
  (clobber (reg:CC CC_REGNUM))]
 ""
 "<shIsa>\t%2, %1, %0"
)

From the h file:

#define REG_CLASS_CONTENTS                                              \
 {
            \
   {0x00000000, 0x00000000, 0x00000000}, /* NO_REGS*/          \
   {0xFFFFFFFF, 0x0000FFFF, 0x00000000}, /* D_REGS*/          \
   {0x00000000, 0xFFFF0000, 0x0000FFFF}, /* R_REGS*/           \

ABI requires use of R registers for arguments and return value. Other
than that all of these instructions are more or less symmetrical in
sense of using D or R. So, an optimal choice would be use of R for
this example. And if D register is chosen, it involves additional copy
from R to D and back to R.

Thank you, Frank

RE: Coloring problem - Pass 0 for finding allocno costs

[Ian Bolton]

> -----Original Message-----
> From: Frank Isamov [mailto:frank.isamov@gmail.com]
> Sent: 18 March 2010 14:29
> To: Ian Bolton
> Subject: Re: Coloring problem - Pass 0 for finding allocno costs
> 
> On Thu, Mar 18, 2010 at 3:51 PM, Ian Bolton <bolton@icerasemi.com>
> wrote:
> >> The problem I see is that for registers 100,101 I get best register
> >> class D instead of R - actually they get the same cost and D is
> chosen
> >> (maybe because it is first).
> >
> > Hi Frank.
> >
> > Do D and R overlap?  It would be useful to know which regs are in
> > which class, before trying to understand what is going on.
> >
> > Can you paste an example of your define_insn from your MD file to
> show
> > how operands from D or R are both valid?  I ask this because it is
> > possible to express that D is more expensive than R with operand
> > constraints.
> >
> > For general IRA info, you might like to look over my long thread on
> > here called "Understanding IRA".
> >
> > Cheers,
> > Ian
> >
> 
> Hi Ian,
> 
> Thank you very much for your prompt reply.
> D and R are not overlap. Please see fragments of .md and .h files
> below:
> 
> From the md:
> 
> (define_register_constraint "a" "R_REGS" "")
> (define_register_constraint "d" "D_REGS" "")
> 
> (define_predicate "a_operand"
>     (match_operand 0 "register_operand")
> {
>         unsigned int regno;
>         if (GET_CODE (op) == SUBREG)
>             op = SUBREG_REG (op);
>         regno = REGNO (op);
>         return (regno >= FIRST_PSEUDO_REGISTER ||
> REGNO_REG_CLASS(regno) == R_REGS);
> }
> )
> 
> (define_predicate "d_operand"
>     (match_operand 0 "register_operand")
> {
>         unsigned int regno;
>         if (GET_CODE (op) == SUBREG)
>             op = SUBREG_REG (op);
>         regno = REGNO (op);
>         return (regno >= FIRST_PSEUDO_REGISTER ||
> REGNO_REG_CLASS(regno) == D_REGS);
> }
> )
> 
> (define_predicate "a_d_operand"
>   (ior (match_operand 0 "a_operand")
>        (match_operand 0 "d_operand")))
> 
> (define_predicate "i_a_d_operand"
>   (ior (match_operand 0 "immediate_operand")
>        (match_operand 0 "a_d_operand")))
> 
> (define_insn "mov<mode>_regs"
>   [(set (match_operand:SISFM 0 "a_d_operand" "=a, a, a, d, d, d")
>                 (match_operand:SISFM 1 "i_a_d_operand"   "a, i, d, a,
> i, d"))]
>   ""
>   "move\t%1, %0"
> )
> 
> (define_insn "*addsi3_1"
>   [(set (match_operand:SI 0 "a_d_operand"    "=a, a,  a,d,d")
>             (plus:SI (match_operand:SI 1 "a_d_operand" "%a, a,
a,d,d")
>                             (match_operand:SI 2 "nonmemory_operand"
> "U05,S16,a,d,U05")))]
>   ""
>   "adda\t%2, %1, %0"
> )
> 
> ;;  Arithmetic Left and Right Shift Instructions
> (define_insn "<shPat><mode>3"
>   [(set (match_operand:SCIM 0 "register_operand" "=a,d,d")
>             (sh_oprnd:SCIM (match_operand:SCIM 1 "register_operand"
> "a,d,d")
>                                     (match_operand:SI 2
> "nonmemory_operand" "U05,d,U05")))
>    (clobber (reg:CC CC_REGNUM))]
>   ""
>   "<shIsa>\t%2, %1, %0"
> )
> 
> From the h file:
> 
> #define REG_CLASS_CONTENTS
> \
>   {
>              \
>     {0x00000000, 0x00000000, 0x00000000}, /* NO_REGS*/          \
>     {0xFFFFFFFF, 0x0000FFFF, 0x00000000}, /* D_REGS*/          \
>     {0x00000000, 0xFFFF0000, 0x0000FFFF}, /* R_REGS*/           \
> 
> ABI requires use of R registers for arguments and return value. Other
> than that all of these instructions are more or less symmetrical in
> sense of using D or R. So, an optimal choice would be use of R for
> this example. And if D register is chosen, it involves additional copy
> from R to D and back to R.
> 
> Thank you, Frank


Hi Frank,

Have you defined REG_ALLOC_ORDER?  All other things being equal,
IRA will choose the register that comes first in the REG_ALLOC_ORDER.

In terms of operand constraints, if you replace 'd' with '?d' in
each of your operand constraints, it will show IRA that using D_REGS
is slightly more expensive than using R_REGS.  This may not always
be true, however, if the value being put in the D_REG never needs to
be returned, so this might cause IRA to use up all the R_REGS first
with things that need not be there.  I didn't like using constraints
because of this issue - the extra cost sometimes incurred is
conditional, and you can't represent that in the constraints.

Have you defined REGISTER_MOVE_COST?  In defaults.h, it is set to
2, which should be what you are looking for.  If you can get IRA to
see that the best COVER_CLASS is R_REGS then, when D_REGS is given,
there will be an added cost of 2 for that option.

One other thing: Don't overlook Pass 1.  That's where the real costs
are calculated.

I hope some of this helps.  If not, you'll have to send me your
test program and ira dump file.

Best regards,
Ian

Re: Coloring problem - Pass 0 for finding allocno costs

[Michael Matz]

[-- Attachment #1: Type: TEXT/PLAIN, Size: 1273 bytes --]

Hi,

On Thu, 18 Mar 2010, Frank Isamov wrote:

> From the h file:
> 
> #define REG_CLASS_CONTENTS                                              \
>  {
>             \
>    {0x00000000, 0x00000000, 0x00000000}, /* NO_REGS*/          \
>    {0xFFFFFFFF, 0x0000FFFF, 0x00000000}, /* D_REGS*/          \
>    {0x00000000, 0xFFFF0000, 0x0000FFFF}, /* R_REGS*/           \
> 
> ABI requires use of R registers for arguments and return value. Other
> than that all of these instructions are more or less symmetrical in
> sense of using D or R.

If that is so, you're better off not using two different register classes 
at all.  Register classes are there to describe assymetry in the ISA 
register file.  For describing ABI constraints like argument or 
caller-save registers look at FUNCTION_ARG, FUNCTION_ARG_REGNO_P, 
FUNCTION_VALUE_REGNO_P and CALL_USED_REGISTERS (and some friends).

The compiler will e.g. try to make sure to first use call-clobbered 
registers in leaf functions, so that they don't need to be saved/restored 
in the prologue/epilogue.  You don't need register classes to describe 
this.


Ciao,
Michael.

RE: Coloring problem - Pass 0 for finding allocno costs

[Ian Bolton]

> -----Original Message-----
> From: gcc-owner@gcc.gnu.org [mailto:gcc-owner@gcc.gnu.org] On Behalf Of
> Michael Matz
> Sent: 18 March 2010 15:13
> To: Frank Isamov
> Cc: gcc@gcc.gnu.org
> Subject: Re: Coloring problem - Pass 0 for finding allocno costs
> 
> Hi,
> 
> On Thu, 18 Mar 2010, Frank Isamov wrote:
> 
> > From the h file:
> >
> > #define REG_CLASS_CONTENTS
>    \
> >  {
> >             \
> >    {0x00000000, 0x00000000, 0x00000000}, /* NO_REGS*/          \
> >    {0xFFFFFFFF, 0x0000FFFF, 0x00000000}, /* D_REGS*/          \
> >    {0x00000000, 0xFFFF0000, 0x0000FFFF}, /* R_REGS*/           \
> >
> > ABI requires use of R registers for arguments and return value. Other
> > than that all of these instructions are more or less symmetrical in
> > sense of using D or R.
> 
> If that is so, you're better off not using two different register
> classes
> at all.  Register classes are there to describe assymetry in the ISA
> register file.  For describing ABI constraints like argument or
> caller-save registers look at FUNCTION_ARG, FUNCTION_ARG_REGNO_P,
> FUNCTION_VALUE_REGNO_P and CALL_USED_REGISTERS (and some friends).
> 
> The compiler will e.g. try to make sure to first use call-clobbered
> registers in leaf functions, so that they don't need to be
> saved/restored
> in the prologue/epilogue.  You don't need register classes to describe
> this.

Good spot!  But ...

In the original post, Frank mentioned that all reg classes in an
insn must match ("all registers in an insn should be from the same
register class"), so I don't think a single class would suffice because
there would be no way to enforce the above requirement.

However, I think a superclass that contains both would work, and the
CALL_USED_REGISTERS define can be used to show just the R_REGS.
Meanwhile, the matching class requirement can still be enforced via the
operand constraints.

I might be wrong, however.  I am still learning about IRA too, so feel
free to teach me something new ;-)

Re: Coloring problem - Pass 0 for finding allocno costs

[Jeff Law]

On 03/18/10 08:30, Frank Isamov wrote:
>
>  From the h file:
>
> #define REG_CLASS_CONTENTS                                              \
>   {
>              \
>     {0x00000000, 0x00000000, 0x00000000}, /* NO_REGS*/          \
>     {0xFFFFFFFF, 0x0000FFFF, 0x00000000}, /* D_REGS*/          \
>     {0x00000000, 0xFFFF0000, 0x0000FFFF}, /* R_REGS*/           \
>
> ABI requires use of R registers for arguments and return value. Other
> than that all of these instructions are more or less symmetrical in
> sense of using D or R. So, an optimal choice would be use of R for
> this example. And if D register is chosen, it involves additional copy
> from R to D and back to R.
>    
Define a union class which includes all the registers in D_REGS and 
R_REGS, then define IRA_COVER_CLASSES to that union class.  When 
register classes are mostly symmetrical, except for stuff like argument 
passing, return values and the like, you usually get better code by 
defining IRA_COVER_CLASSES with a single union class rather than the 
component subclasses.

In fact, if the only reason D & R are separate is calling conventions, 
then I'd just drop them those classes completely and define 
GENERAL_REGISTERS.   You would typically only define separate register 
classes if there are instructions which have to operate on specific 
subsets of the register file.


Jeff