[llvm-dev] handling "overlapping" register classes

[zan jyu Wong via llvm-dev]

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>