[LLVMdev] Instruction Selection

[Steve Montgomery]

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