llvm dev - Oct 2015 - handling "overlapping" register classes

I'm working on generating code for a machine that has a register set kind
of like the 68000.

For those who don't recall, the 68K has 8 Data registers that can be used
for ordinary integer
instructions like add, subtract, multiply, shift, etc., and 8 Address
registers that can be use for
integer addition and a few other things, especially base registers for
addressing modes.
The Data register, on the other hand, cannot be used as base registers.

So, neither is more general than the other. We can use either for integer
addition,
but only Address registers as base registers and only Data registers for
integer
multiplication, etc. (I may have a few details wrong, but since this is
only an example,
I don't think they're too important.)

Back when, I defined 3 register classes: Address, Data, and General,
where Address = 1, Data = 2, and General = 3.
My approach was to begin by defining every symbolic register (aka live
range)
as General. Then I'd walk through all the instructions, intersecting the
requirements
for the particular instruction to yield a perhaps less general register
class.

For example, an Add instruction would require and produce General registers
(since we
have add instructions for both Address and Data registers). But an
addressing mode
would require an Address register, so when we notice a General register
being used in
an addressing mode, intersection the Addressing requirement (= 1) with the
General
register (= 3) yields 1, implying the register needs to be an Address
register.

When building the interference graph and noting that 2 live ranges were
simultaneously live,
if the intersection of their classes was non-zero, I'd add an interference
to the IG.
Similarly, I'd make symbolic registers of Address class interfere with all
the machine's
Data registers and vice versa. In this fashion, since live ranges that are
more restricted
(have higher degree) tend to be colored first, live ranges that must be
Address or
must be Data will end up in the right place, with the coloring algorithm
naturally
balancing everyone's requirements.

Care is required when a live range ends up with class = 0; implies copies
are required.

So, finally, my question: Is there any similar scheme in LLVM's code
generator?
What I'm looking for is a way to select the one of the two available
integer addition
instructions (add using Address registers or add using Data registers) so
as to
minimize the number of Address-Data copies.

Thanks,
Preston
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20151005/ed960a91/attachment.html>

> On Oct 5, 2015, at 19:41, Preston Briggs via llvm-dev <llvm-dev at
lists.llvm.org> wrote:
> 
> I'm working on generating code for a machine that has a register set
kind of like the 68000.
> 
> For those who don't recall, the 68K has 8 Data registers that can be
used for ordinary integer
> instructions like add, subtract, multiply, shift, etc., and 8 Address
registers that can be use for
> integer addition and a few other things, especially base registers for
addressing modes.
> The Data register, on the other hand, cannot be used as base registers.
[…]
> So, finally, my question: Is there any similar scheme in LLVM's code
generator?
> What I'm looking for is a way to select the one of the two available
integer addition
> instructions (add using Address registers or add using Data registers) so
as to
> minimize the number of Address-Data copies.
Hi Preston,

Short answer: No, LLVM can’t do that, and you have to roll your own pass to
select add instructions.

There is some support implemented for what you describe: Tablegen and the
register allocator understand overlapping register classes. Tablegen will create
a function to compute the intersection of two register classes, and it will
create synthetic register classes to ensure that there is always an exact
answer, no matter how you defined your register classes in the XXXRegisters.td
file. See TargetRegisterInfo::getCommonSubClass().

The instruction selector computes a register class for each live range by
intersecting the requirements of each use-instruction like you describe. It also
knows to insert copies when the intersection becomes empty. It doesn’t do this
intelligently, but it does generate legal code.

When live ranges are split during register allocation, the register class of the
fragments is recomputed in case it becomes possible to use a larger register
class. See MachineRegisterInfo::recomputeRegClass().

We don’t compute an interference graph, but you could use getCommonSubClass() to
test if two register classes are overlapping.

I think LLVM’s instruction selection would be improved for many targets if it
supported a generalization of your problem. It’s what I called “register bank
selection” here: http://www.2pi.dk/llvm/global-isel.html
<http://www.2pi.dk/llvm/global-isel.html> The current instruction selector
design uses a fixed mapping from IR types to register banks.

It seems to me that the problem of optimal register bank selection could be
expressed in similar terms as the problem of optimal global live range
splitting, and I suspect that the algorithm in SpillPlacement.cpp could be
generalized.

Thanks,
/jakob
> 
> So, neither is more general than the other. We can use either for integer
addition,
> but only Address registers as base registers and only Data registers for
integer
> multiplication, etc. (I may have a few details wrong, but since this is
only an example,
> I don't think they're too important.)
> 
> Back when, I defined 3 register classes: Address, Data, and General,
> where Address = 1, Data = 2, and General = 3.
> My approach was to begin by defining every symbolic register (aka live
range)
> as General. Then I'd walk through all the instructions, intersecting
the requirements
> for the particular instruction to yield a perhaps less general register
class.
> 
> For example, an Add instruction would require and produce General registers
(since we
> have add instructions for both Address and Data registers). But an
addressing mode
> would require an Address register, so when we notice a General register
being used in
> an addressing mode, intersection the Addressing requirement (= 1) with the
General
> register (= 3) yields 1, implying the register needs to be an Address
register.
> 
> When building the interference graph and noting that 2 live ranges were
simultaneously live,
> if the intersection of their classes was non-zero, I'd add an
interference to the IG.
> Similarly, I'd make symbolic registers of Address class interfere with
all the machine's
> Data registers and vice versa. In this fashion, since live ranges that are
more restricted
> (have higher degree) tend to be colored first, live ranges that must be
Address or
> must be Data will end up in the right place, with the coloring algorithm
naturally
> balancing everyone's requirements.
> 
> Care is required when a live range ends up with class = 0; implies copies
are required.
> 
> So, finally, my question: Is there any similar scheme in LLVM's code
generator?
> What I'm looking for is a way to select the one of the two available
integer addition
> instructions (add using Address registers or add using Data registers) so
as to
> minimize the number of Address-Data copies.
> 
> Thanks,
> Preston
> 
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20151007/c6dd94ef/attachment.html>

Hi,
    I used to hack on a Blackfin backend of LLVM, which may have the same
problem.
    There is a Blackfin backend in LLVM 3.0. Blackfin has D registers for
data processing and P registers for pointer. The original author of the
backend defines two register class D, P, a Load may defined as:

    def LOAD32p: F1<(outs DP:$dst), (ins P:$ptr),
                "$dst = [$ptr];",
                [(set DP:$dst, (load P:$ptr))]>;

    when using this kind of description, the backend will select the legal
instruction, but may insert too may copies between D registers and P
registers.
    I found a way to remove these redundant copies. Actually, we can do a
backward data flow analysis to find out if a D register will finally copied
to a P register.
    for example:
        v_D1 <- v_P1
        v_D0 <- v_D1 * 2
        v_P0 <- v_D0
        v_D2 <- LOAD v_P0
    We can start from LOAD instruction, and trace backward to find out that
D0 will finally mov to a pointer. So, we can replace instructions with:
        v_P0 <- v_P1 + v_P1
        v_D2 <- LOAD v_P0

    see function `translatePointerOperation' at
https://gitcafe.com/zyfwong/llvm-3.6.0/blob/master/lib/Target/Blackfin/BlackfinISelLowering.cpp

Cheers,
Huang

On Wed, Oct 7, 2015 at 3:03 PM, Jakob Stoklund Olesen via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
>
> On Oct 5, 2015, at 19:41, Preston Briggs via llvm-dev <
> llvm-dev at lists.llvm.org> wrote:
>
> I'm working on generating code for a machine that has a register set
kind
> of like the 68000.
>
> For those who don't recall, the 68K has 8 Data registers that can be
used
> for ordinary integer
> instructions like add, subtract, multiply, shift, etc., and 8 Address
> registers that can be use for
> integer addition and a few other things, especially base registers for
> addressing modes.
> The Data register, on the other hand, cannot be used as base registers.
>
>
> […]
>
> So, finally, my question: Is there any similar scheme in LLVM's code
> generator?
> What I'm looking for is a way to select the one of the two available
> integer addition
> instructions (add using Address registers or add using Data registers) so
> as to
> minimize the number of Address-Data copies.
>
>
> Hi Preston,
>
> Short answer: No, LLVM can’t do that, and you have to roll your own pass
> to select add instructions.
>
> There is some support implemented for what you describe: Tablegen and the
> register allocator understand overlapping register classes. Tablegen will
> create a function to compute the intersection of two register classes, and
> it will create synthetic register classes to ensure that there is always an
> exact answer, no matter how you defined your register classes in the
> XXXRegisters.td file. See TargetRegisterInfo::getCommonSubClass().
>
> The instruction selector computes a register class for each live range by
> intersecting the requirements of each use-instruction like you describe. It
> also knows to insert copies when the intersection becomes empty. It doesn’t
> do this intelligently, but it does generate legal code.
>
> When live ranges are split during register allocation, the register class
> of the fragments is recomputed in case it becomes possible to use a larger
> register class. See MachineRegisterInfo::recomputeRegClass().
>
> We don’t compute an interference graph, but you could use
> getCommonSubClass() to test if two register classes are overlapping.
>
> I think LLVM’s instruction selection would be improved for many targets if
> it supported a generalization of your problem. It’s what I called “register
> bank selection” here: http://www.2pi.dk/llvm/global-isel.html The current
> instruction selector design uses a fixed mapping from IR types to register
> banks.
>
> It seems to me that the problem of optimal register bank selection could
> be expressed in similar terms as the problem of optimal global live range
> splitting, and I suspect that the algorithm in SpillPlacement.cpp could be
> generalized.
>
> Thanks,
> /jakob
>
>
> So, neither is more general than the other. We can use either for integer
> addition,
> but only Address registers as base registers and only Data registers for
> integer
> multiplication, etc. (I may have a few details wrong, but since this is
> only an example,
> I don't think they're too important.)
>
> Back when, I defined 3 register classes: Address, Data, and General,
> where Address = 1, Data = 2, and General = 3.
> My approach was to begin by defining every symbolic register (aka live
> range)
> as General. Then I'd walk through all the instructions, intersecting
the
> requirements
> for the particular instruction to yield a perhaps less general register
> class.
>
> For example, an Add instruction would require and produce General
> registers (since we
> have add instructions for both Address and Data registers). But an
> addressing mode
> would require an Address register, so when we notice a General register
> being used in
> an addressing mode, intersection the Addressing requirement (= 1) with the
> General
> register (= 3) yields 1, implying the register needs to be an Address
> register.
>
> When building the interference graph and noting that 2 live ranges were
> simultaneously live,
> if the intersection of their classes was non-zero, I'd add an
interference
> to the IG.
> Similarly, I'd make symbolic registers of Address class interfere with
all
> the machine's
> Data registers and vice versa. In this fashion, since live ranges that are
> more restricted
> (have higher degree) tend to be colored first, live ranges that must be
> Address or
> must be Data will end up in the right place, with the coloring algorithm
> naturally
> balancing everyone's requirements.
>
> Care is required when a live range ends up with class = 0; implies copies
> are required.
>
> So, finally, my question: Is there any similar scheme in LLVM's code
> generator?
> What I'm looking for is a way to select the one of the two available
> integer addition
> instructions (add using Address registers or add using Data registers) so
> as to
> minimize the number of Address-Data copies.
>
> Thanks,
> Preston
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
>
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20151007/1a54231f/attachment.html>