handling "overlapping" register classes

Project Infrastructure LLVM Dev List Archives
1

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

2

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

3

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