llvm dev - Sep 2011 - [LLVMdev] Instruction Selection

I've got a question about instruction selection for a backend I'm
writing.

The target has two register classes, RC1 and RC2. The instruction set is far
from orthogonal.

The ADD instruction is two address with both register/immediate and
register/memory forms. The register operand is in the RC1 class.

The LEA instruction is three address with the destination register in the RC2
class. There are two forms: register/immediate in which the register is RC2
class and register/register in which one register is RC1 and the other RC2.

The algorithm used to generate the instruction selection table gives a
relatively high priority to complex patterns in order to favour selection of LEA
over ADD. For my target, this means that the result of an addition will always
be an RC2 register. Depending on how the result is used, sometimes this is fine
but other times it would be better (avoid a register-register copy) if the
result were in an RC1 register.

For example:

    LOAD mem,$RC1_a
    LEA $RC2_a,$RC2_b,$RC1_a
    MOV $RC2_a,$RC1_a

needs an additional register and is larger and slower than

    MOV $RC2_b,$RC1_a
    ADD mem,$RC1_a

But

    LEA $RC2_a,$RC2_b,#8

is much better then

    MOV $RC2_b,$RC1_a
    ADD #8,$RC1_a
    MOV $RC1_a,$RC2_a

My problem therefore is that statically prioritising LEA over ADD, or
vice-versa, doesn't generate good code in all cases. It seems that I need to
defer a decision on whether to select LEA or ADD until sometime during register
allocation.

Is there a tidy way to handle this, or will I need to write some custom
selection and/or register allocation code?

Steve Montgomery

Sorry, I realised that my examples aren't clear because the MOV and LOAD
instructions are:
    MOV src, dst
    LOAD src,dst

but LEA is
    LEA dst,reg,reg/imm

On 21 Sep 2011, at 09:28, Steve Montgomery wrote:
> I've got a question about instruction selection for a backend I'm
writing.
> 
> The target has two register classes, RC1 and RC2. The instruction set is
far from orthogonal.
> 
> The ADD instruction is two address with both register/immediate and
register/memory forms. The register operand is in the RC1 class.
> 
> The LEA instruction is three address with the destination register in the
RC2 class. There are two forms: register/immediate in which the register is RC2
class and register/register in which one register is RC1 and the other RC2.
> 
> The algorithm used to generate the instruction selection table gives a
relatively high priority to complex patterns in order to favour selection of LEA
over ADD. For my target, this means that the result of an addition will always
be an RC2 register. Depending on how the result is used, sometimes this is fine
but other times it would be better (avoid a register-register copy) if the
result were in an RC1 register.
> 
> For example:
> 
>    LOAD mem,$RC1_a
>    LEA $RC2_a,$RC2_b,$RC1_a
>    MOV $RC2_a,$RC1_a
> 
> needs an additional register and is larger and slower than
> 
>    MOV $RC2_b,$RC1_a
>    ADD mem,$RC1_a
> 
> But
> 
>    LEA $RC2_a,$RC2_b,#8
> 
> is much better then
> 
>    MOV $RC2_b,$RC1_a
>    ADD #8,$RC1_a
>    MOV $RC1_a,$RC2_a
> 
> My problem therefore is that statically prioritising LEA over ADD, or
vice-versa, doesn't generate good code in all cases. It seems that I need to
defer a decision on whether to select LEA or ADD until sometime during register
allocation.
> 
> Is there a tidy way to handle this, or will I need to write some custom
selection and/or register allocation code?
> 
> Steve Montgomery 
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev