[llvm-dev] handling "overlapping" register classes

Wed Oct 7 00:03:57 PDT 2015

> 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>