[LLVMdev] Register Pairing
207 views
Skip to first unread message
Borja Ferrer
Nov 27, 2010, 11:56:34 AM11/27/10
to llv...@cs.uiuc.edu
Hello, some months ago i wrote to the mailing list asking some questions about register pairing, i've been experimenting several things with the help i got back then.
Some background first: this issue is for a backend for an 8bit microcontroller with only 8bit regs, however it has a few 16bit instructions that only work with fixed register pairs, so it doesnt allow all combinations of regs. This introduces some problems because if data wider than 8bits is expanded into 8bit operations the 16bit instructions never get selected, also the reg allocator should allocate adjacent regs to form the pairs. The most important 16 bit instruction is data movement, this instruction can move register pairs in a single cycle, doing something like this:
mov r25, r23
mov r24, r22
into:
movw r25:r24, r23:r22
The key point here is that the movw instruction can only move data of fixed pairs in this way. movw Rdest+1:Rdest, Rorig+1:Rorig, so movw R25:R23, R21:R18 is illegal because registers pairs aren't adjacent.
Explaining this as if it was for x86 may make things more clear. Suppose we only have 8bit regs (ah, al, cl, ch, bl, bh, etc...) with 8 bit instructions and a few 16 bit instrs that only work with ax, bx, cx,.... We could pair ah:al to form ax, and so on. Then we have a movw instruction that is able to work with reg pairs, such as ax, bx, cx, etc... This way if we store a short in ah:al we could copy it into another pair, but storing it into al:cl would be bad because movw wouldnt be emitted. Also these reg pairs would be stored in a pseudo reg class so the 16 bit intrs would be emitted, otherwise none of them would be produced.
Going back to my case I want to favor storing 16bit or wider data in adjacent regs to favor the insertion of this instruction like HARD_REGNO_MODE_OK in gcc. To overcome this problem and to select 16bit instructions automatically by LLVM i thought on working always with 16 bit register pairs. I created a pseudo reg class that contains the reg pairs marking each pair with its 2 subregs of 8 bits. Then i marked the i16 type legal with addRegisterClass(), although this is nearly a lie because i16 is only legal in a few specific cases, it makes LLVM think that working with the pairs is fine.
Now for example to perform a 16 bit sum consider this code:
typedef unsigned short t;
t foo(t a, t b, t c)
{
return a+b;
}
Incoming args come in register pairs, split them into the 8bit subregs perform the addition and combine them again into the pair ready for the next operation, in this case we're returning the result. This gives me this code before instr sel:
# Machine code for function foo:
Function Live Ins: %R25R24 in reg%16384, %R23R22 in reg%16385
Function Live Outs: %R25R24
BB#0: derived from LLVM BB %entry
Live Ins: %R25R24 %R23R22
%reg16385<def> = COPY %R23R22; WDREGS:%reg16385 // COPY B
%reg16384<def> = COPY %R25R24; WDREGS:%reg16384 // COPY A
%reg16387<def> = COPY %reg16384:ssub_0; GPR8:%reg16387 WDREGS:%reg16384 // EXTRACT LO BYTE OF A
%reg16388<def> = COPY %reg16385:ssub_0; GPR8:%reg16388 WDREGS:%reg16385 // EXTRACT LO BYTE OF B
%reg16389<def> = COPY %reg16384:ssub_1; GPR8:%reg16389 WDREGS:%reg16384 // EXTRACT HI BYTE OF A
%reg16390<def> = COPY %reg16385:ssub_1; GPR8:%reg16390 WDREGS:%reg16385 // EXTRACT HI BYTE OF B
%reg16391<def> = ADDRdRr %reg16388, %reg16387<kill>, %SREG<imp-def>; GPR8:%reg16391,16388,16387 // ADD LO BYTES
%reg16392<def> = ADCRdRr %reg16390, %reg16389<kill>, %SREG<imp-def,dead>, %SREG<imp-use>; GPR8:%reg16392,16390,16389 // ADDC HI BYTES
%reg16393<def> = REG_SEQUENCE %reg16391<kill>, ssub_0, %reg16392<kill>, ssub_1; WDREGS:%reg16393 GPR8:%reg16391,16392 // COMBINE INTO REG PAIR AGAIN
%R25R24<def> = COPY %reg16393; WDREGS:%reg16393 // COPY REG PAIR INTO RETURN REG.
RET
This is fine until we get to the register allocation stage, there it does:
BB#0: derived from LLVM BB %entry
Live Ins: %R25R24 %R23R22
%R18<def> = COPY %R24
%R19<def> = COPY %R25
%R24<def> = COPY %R22<kill>, %R25R24<imp-def>
%R24<def> = ADDRdRr %R24, %R18<kill>, %SREG<imp-def>
%R25<def> = COPY %R23<kill>
%R25<def> = ADCRdRr %R25, %R19<kill>, %SREG<imp-def,dead>, %SREG<imp-use,kill>
RET %R25R24<imp-use,kill>
Here instead of splitting the pair into its own subregs, it's copying each subreg into r18 and r19 making useless movements.
The optimal code should be:
add r24, r22
adc r25, r23
So my first question would be how to solve this?
And going on further, is this the correct way to model the pairs to get the behaviour i need, or is there a better and direct way of handling this? You can think of the x86 example i wrote before.
Thanks for your help.
Some background first: this issue is for a backend for an 8bit microcontroller with only 8bit regs, however it has a few 16bit instructions that only work with fixed register pairs, so it doesnt allow all combinations of regs. This introduces some problems because if data wider than 8bits is expanded into 8bit operations the 16bit instructions never get selected, also the reg allocator should allocate adjacent regs to form the pairs. The most important 16 bit instruction is data movement, this instruction can move register pairs in a single cycle, doing something like this:
mov r25, r23
mov r24, r22
into:
movw r25:r24, r23:r22
The key point here is that the movw instruction can only move data of fixed pairs in this way. movw Rdest+1:Rdest, Rorig+1:Rorig, so movw R25:R23, R21:R18 is illegal because registers pairs aren't adjacent.
Explaining this as if it was for x86 may make things more clear. Suppose we only have 8bit regs (ah, al, cl, ch, bl, bh, etc...) with 8 bit instructions and a few 16 bit instrs that only work with ax, bx, cx,.... We could pair ah:al to form ax, and so on. Then we have a movw instruction that is able to work with reg pairs, such as ax, bx, cx, etc... This way if we store a short in ah:al we could copy it into another pair, but storing it into al:cl would be bad because movw wouldnt be emitted. Also these reg pairs would be stored in a pseudo reg class so the 16 bit intrs would be emitted, otherwise none of them would be produced.
Going back to my case I want to favor storing 16bit or wider data in adjacent regs to favor the insertion of this instruction like HARD_REGNO_MODE_OK in gcc. To overcome this problem and to select 16bit instructions automatically by LLVM i thought on working always with 16 bit register pairs. I created a pseudo reg class that contains the reg pairs marking each pair with its 2 subregs of 8 bits. Then i marked the i16 type legal with addRegisterClass(), although this is nearly a lie because i16 is only legal in a few specific cases, it makes LLVM think that working with the pairs is fine.
Now for example to perform a 16 bit sum consider this code:
typedef unsigned short t;
t foo(t a, t b, t c)
{
return a+b;
}
Incoming args come in register pairs, split them into the 8bit subregs perform the addition and combine them again into the pair ready for the next operation, in this case we're returning the result. This gives me this code before instr sel:
# Machine code for function foo:
Function Live Ins: %R25R24 in reg%16384, %R23R22 in reg%16385
Function Live Outs: %R25R24
BB#0: derived from LLVM BB %entry
Live Ins: %R25R24 %R23R22
%reg16385<def> = COPY %R23R22; WDREGS:%reg16385 // COPY B
%reg16384<def> = COPY %R25R24; WDREGS:%reg16384 // COPY A
%reg16387<def> = COPY %reg16384:ssub_0; GPR8:%reg16387 WDREGS:%reg16384 // EXTRACT LO BYTE OF A
%reg16388<def> = COPY %reg16385:ssub_0; GPR8:%reg16388 WDREGS:%reg16385 // EXTRACT LO BYTE OF B
%reg16389<def> = COPY %reg16384:ssub_1; GPR8:%reg16389 WDREGS:%reg16384 // EXTRACT HI BYTE OF A
%reg16390<def> = COPY %reg16385:ssub_1; GPR8:%reg16390 WDREGS:%reg16385 // EXTRACT HI BYTE OF B
%reg16391<def> = ADDRdRr %reg16388, %reg16387<kill>, %SREG<imp-def>; GPR8:%reg16391,16388,16387 // ADD LO BYTES
%reg16392<def> = ADCRdRr %reg16390, %reg16389<kill>, %SREG<imp-def,dead>, %SREG<imp-use>; GPR8:%reg16392,16390,16389 // ADDC HI BYTES
%reg16393<def> = REG_SEQUENCE %reg16391<kill>, ssub_0, %reg16392<kill>, ssub_1; WDREGS:%reg16393 GPR8:%reg16391,16392 // COMBINE INTO REG PAIR AGAIN
%R25R24<def> = COPY %reg16393; WDREGS:%reg16393 // COPY REG PAIR INTO RETURN REG.
RET
This is fine until we get to the register allocation stage, there it does:
BB#0: derived from LLVM BB %entry
Live Ins: %R25R24 %R23R22
%R18<def> = COPY %R24
%R19<def> = COPY %R25
%R24<def> = COPY %R22<kill>, %R25R24<imp-def>
%R24<def> = ADDRdRr %R24, %R18<kill>, %SREG<imp-def>
%R25<def> = COPY %R23<kill>
%R25<def> = ADCRdRr %R25, %R19<kill>, %SREG<imp-def,dead>, %SREG<imp-use,kill>
RET %R25R24<imp-use,kill>
Here instead of splitting the pair into its own subregs, it's copying each subreg into r18 and r19 making useless movements.
The optimal code should be:
add r24, r22
adc r25, r23
So my first question would be how to solve this?
And going on further, is this the correct way to model the pairs to get the behaviour i need, or is there a better and direct way of handling this? You can think of the x86 example i wrote before.
Thanks for your help.
Message has been deleted
Jakob Stoklund Olesen
Nov 29, 2010, 1:37:27 PM11/29/10
to Borja Ferrer, llv...@cs.uiuc.edu
On Nov 27, 2010, at 8:56 AM, Borja Ferrer wrote:
> Some background first: this issue is for a backend for an 8bit microcontroller with only 8bit regs, however it has a few 16bit instructions that only work with fixed register pairs, so it doesnt allow all combinations of regs. This introduces some problems because if data wider than 8bits is expanded into 8bit operations the 16bit instructions never get selected, also the reg allocator should allocate adjacent regs to form the pairs. The most important 16 bit instruction is data movement, this instruction can move register pairs in a single cycle
Are you doing this only to take advantage of a double move instruction?
If so, I think you are better off just using 8-bit registers. The 16-bit code will never be as good as 8-bit code if you don't have a number of 16-bit instructions.
[...]
> typedef unsigned short t;
> t foo(t a, t b, t c)
> {
> return a+b;
> }
[...]
> This is fine until we get to the register allocation stage, there it does:
> BB#0: derived from LLVM BB %entry
> Live Ins: %R25R24 %R23R22
> %R18<def> = COPY %R24
> %R19<def> = COPY %R25
> %R24<def> = COPY %R22<kill>, %R25R24<imp-def>
> %R24<def> = ADDRdRr %R24, %R18<kill>, %SREG<imp-def>
> %R25<def> = COPY %R23<kill>
> %R25<def> = ADCRdRr %R25, %R19<kill>, %SREG<imp-def,dead>, %SREG<imp-use,kill>
> RET %R25R24<imp-use,kill>
>
> Here instead of splitting the pair into its own subregs, it's copying each subreg into r18 and r19 making useless movements.
> The optimal code should be:
> add r24, r22
> adc r25, r23
>
> So my first question would be how to solve this?
You should not expect LLVM to generate optimal code for toy examples, that is not the design goal. You example requires a lot of trickery to compile optimally, and it is not clear that such tricks would benefit more realistic code.
How are you doing on real code?
/jakob
_______________________________________________
LLVM Developers mailing list
LLV...@cs.uiuc.edu http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Borja Ferrer
Dec 1, 2010, 4:02:04 PM12/1/10
to Jakob Stoklund Olesen, jdk...@gmail.com, llv...@cs.uiuc.edu
Jeff thanks for those suggestions, that's exactly what i would like to do, however i dont know how to do it with my current knowledge :\ As far as i understand patterns only take one instruction as an input (while the pattern you wrote before takes two) and also, i dont know how to handle register copying (COPY) in the .td file because they're handled in a different way to the rest of instructions.
Jakob i know my approach is not very suitable watching the results i got. The example i wrote in my previous email was just a trivial function to see if what i was trying to do was good.
Without doing what i mentioned and letting LLVM expand all operations wider than 8 bits as you asked, the code produced is excellent supposing that many of the moves there should be 16 bit moves reducing code size and right register allocation, also something important for me is that the code is better than gcc's. When i say right reg allocation it doesnt mean it's doing things wrong, i mean it's getting regs freely without pairing regs because i dont know how to do it. So now i have to push things further and implement these details to make the backend introduce those 16 bit instructions i dont know how to insert, and this is where i need help.
My 2 big questions are:
- How to tell the register allocator to store 16 bit data in two contiguous 8 bit regs being the low part an even reg? Remember data would be expanded into 8 bit ops, so when we're working with dags after type legalization do we really know the original type before expansion?
As an example, storing a short in r21:r20 would be valid, but r20:r19 or r20:r18 would be invalid because the in the first case the low reg is odd and in the second case regs arent contiguous.
To store data wider than 16 bits, for example for a 32 bit int we would use 2 register pairs (4 8bit regs) but here the pairs dont need to be contiguous so storing it r25:r24:r19:r18 is completely fine.
As i said in my previous email this is achieved by using HARD_REGNO_MODE_OK in gcc.
- Second, assuming the previous point works so the register constraints are done, how would i then proceed and combine two 8 bit instructions into a 16 bit one as Jeff pointed out in his email?
For example i want to combine a 16 bit add like this:
// b = b + 1:
(b stored in r25:r24)
add r24, 1
adc r25, 0
into
adw r25:r24, 1
and the one im talking all my mails about
move r25, r23
move r24, r22
into
movw r25:r24, r23:r22
or
move r18, r2
move r19, r3
into
movw r19:r18, r3:r2
any combination of moves with reg pairs are valid.
I wrote a function pass to test, it scanned for moves and checked if next instruction was a move to see if globally it was a 16 move and replace those 2 insts with a movw. But this pass lacked lots of details for example if a different instruction was placed in between the moves it wouldnt be able to detect it.
Your help is really appreciated, and thanks to both for your patience.
Jakob i know my approach is not very suitable watching the results i got. The example i wrote in my previous email was just a trivial function to see if what i was trying to do was good.
Without doing what i mentioned and letting LLVM expand all operations wider than 8 bits as you asked, the code produced is excellent supposing that many of the moves there should be 16 bit moves reducing code size and right register allocation, also something important for me is that the code is better than gcc's. When i say right reg allocation it doesnt mean it's doing things wrong, i mean it's getting regs freely without pairing regs because i dont know how to do it. So now i have to push things further and implement these details to make the backend introduce those 16 bit instructions i dont know how to insert, and this is where i need help.
My 2 big questions are:
- How to tell the register allocator to store 16 bit data in two contiguous 8 bit regs being the low part an even reg? Remember data would be expanded into 8 bit ops, so when we're working with dags after type legalization do we really know the original type before expansion?
As an example, storing a short in r21:r20 would be valid, but r20:r19 or r20:r18 would be invalid because the in the first case the low reg is odd and in the second case regs arent contiguous.
To store data wider than 16 bits, for example for a 32 bit int we would use 2 register pairs (4 8bit regs) but here the pairs dont need to be contiguous so storing it r25:r24:r19:r18 is completely fine.
As i said in my previous email this is achieved by using HARD_REGNO_MODE_OK in gcc.
- Second, assuming the previous point works so the register constraints are done, how would i then proceed and combine two 8 bit instructions into a 16 bit one as Jeff pointed out in his email?
For example i want to combine a 16 bit add like this:
// b = b + 1:
(b stored in r25:r24)
add r24, 1
adc r25, 0
into
adw r25:r24, 1
and the one im talking all my mails about
move r25, r23
move r24, r22
into
movw r25:r24, r23:r22
move r18, r2
move r19, r3
into
movw r19:r18, r3:r2
any combination of moves with reg pairs are valid.
I wrote a function pass to test, it scanned for moves and checked if next instruction was a move to see if globally it was a 16 move and replace those 2 insts with a movw. But this pass lacked lots of details for example if a different instruction was placed in between the moves it wouldnt be able to detect it.
Your help is really appreciated, and thanks to both for your patience.
Lang Hames
Dec 1, 2010, 8:57:29 PM12/1/10
to Borja Ferrer, jdk...@gmail.com, llv...@cs.uiuc.edu
Hi Borja,
Without doing what i mentioned and letting LLVM expand all operations wider than 8 bits as you asked, the code produced is excellent supposing that many of the moves there should be 16 bit moves reducing code size and right register allocation, also something important for me is that the code is better than gcc's. When i say right reg allocation it doesnt mean it's doing things wrong, i mean it's getting regs freely without pairing regs because i dont know how to do it. So now i have to push things further and implement these details to make the backend introduce those 16 bit instructions i dont know how to insert, and this is where i need help.
I'm not sure how to help with inserting the 16-bit instructions, but if you go with using allocating 8-bit virtuals the PBQP allocator can handle the pairing constraint. An overview of how to use the allocator is given in http://lists.cs.uiuc.edu/pipermail/llvmdev/2010-September/034781.html , and the follow up emails. If you think it might be useful and have any questions I'd be happy to help.
Cheers,
Lang.
Borja Ferrer
Dec 5, 2010, 11:17:12 AM12/5/10
to Lang Hames, llv...@cs.uiuc.edu
Hello Lang, thanks for the suggestion :) it's very interesting. I'll take a read to the email you've pointed out there to understand how it works. Btw, does this mean that only your allocator is able to handle or support this type of constraint?
As a follow up to my previous email, the following code is a real example of what i was explaining, Lang this example is exactly why i need the constraints and how to combine instructions.
typedef short t;
extern t mcos(t a);
extern t mdiv(t a, t b);
t foo(t a, t b)
{
short p1 = mcos(b);
short p2 = mcos(a);
return mdiv(p1&p2, p1^p2);
}
This C code produces:
; a<- r25:r24 b<--r23:r22
mov r18, r24
mov r19, r25 <-- can be combined into a movw r19:r18, r25:r24
mov r25, r23
mov r24, r22 <-- can be combined into a movw r25:r24, r23:r22
call mcos
; here we have the case i was explaining, pairs dont match because they're the other way round, function result is in r25:r24
; but it's storing the hi part in r20 instead of r21, so we cant insert a movw
mov r20, r25
mov r21, r24 <--- should be mov r21, r25; mov r20, r24 to be able to insert a movw
mov r25, r19
mov r24, r18 <-- can be combined into a movw r25:r24, r19:r18
call mcos
; same problem as above, again it's moving the hi part in r25 into r18 instead of r19 so we've lost another movw here
mov r18, r25 <-- should be mov r19, r25
and r18, r20
mov r19, r24 <-- should be mov r18, r24
and r19, r21
mov r23, r25 <-- this *
eor r23, r20
mov r22, r24 <-- * and this could be combined into movw r23:r22, r25:r24
eor r22, r21
mov r25, r18
mov r24, r19 <-- because the result returned by the second call to mcos is stored in r18:r19 (other way round)
; we've lost another movw
call mdiv
ret
As you can see there are three cases were we've lost the opportunity of inserting a movw. This is a very important instruction because if we're able to insert it everywhere it's possible we can reduce the code in 7 instructions and 7 cycles which is a huge gain. Ignoring these issues the code produced is optimal. I hope this example make things more clearer. Also, as i said in my previous email i wrote a function pass searching for 2 moves in a row and combining them into a movw since i dont know a better way of combining machine instructions, however in this case it wouldnt work for the second half of the program because there are "and" and "xor" instructions in between the moves breaking the simple heuristic the function pass has.
Thanks for the help.
As a follow up to my previous email, the following code is a real example of what i was explaining, Lang this example is exactly why i need the constraints and how to combine instructions.
typedef short t;
extern t mcos(t a);
extern t mdiv(t a, t b);
t foo(t a, t b)
{
short p1 = mcos(b);
short p2 = mcos(a);
return mdiv(p1&p2, p1^p2);
}
This C code produces:
; a<- r25:r24 b<--r23:r22
mov r18, r24
mov r19, r25 <-- can be combined into a movw r19:r18, r25:r24
mov r25, r23
mov r24, r22 <-- can be combined into a movw r25:r24, r23:r22
call mcos
; here we have the case i was explaining, pairs dont match because they're the other way round, function result is in r25:r24
; but it's storing the hi part in r20 instead of r21, so we cant insert a movw
mov r20, r25
mov r21, r24 <--- should be mov r21, r25; mov r20, r24 to be able to insert a movw
mov r25, r19
mov r24, r18 <-- can be combined into a movw r25:r24, r19:r18
call mcos
; same problem as above, again it's moving the hi part in r25 into r18 instead of r19 so we've lost another movw here
mov r18, r25 <-- should be mov r19, r25
and r18, r20
mov r19, r24 <-- should be mov r18, r24
and r19, r21
mov r23, r25 <-- this *
eor r23, r20
mov r22, r24 <-- * and this could be combined into movw r23:r22, r25:r24
eor r22, r21
mov r25, r18
mov r24, r19 <-- because the result returned by the second call to mcos is stored in r18:r19 (other way round)
; we've lost another movw
call mdiv
ret
As you can see there are three cases were we've lost the opportunity of inserting a movw. This is a very important instruction because if we're able to insert it everywhere it's possible we can reduce the code in 7 instructions and 7 cycles which is a huge gain. Ignoring these issues the code produced is optimal. I hope this example make things more clearer. Also, as i said in my previous email i wrote a function pass searching for 2 moves in a row and combining them into a movw since i dont know a better way of combining machine instructions, however in this case it wouldnt work for the second half of the program because there are "and" and "xor" instructions in between the moves breaking the simple heuristic the function pass has.
Thanks for the help.
Lang Hames
Dec 5, 2010, 7:33:45 PM12/5/10
to Borja Ferrer, llv...@cs.uiuc.edu
Hi Borja
Hello Lang, thanks for the suggestion :) it's very interesting. I'll take a read to the email you've pointed out there to understand how it works. Btw, does this mean that only your allocator is able to handle or support this type of constraint?
I believe so. The other allocators can support pairs, but you have to introduce a new register class to describe them, which can lead to the issues you've already seen.
The PBQP allocator lets you keep your original register classes and describe the constraint that certain virtual registers need to be allocated adjacent physicals. The Scholz/Eckstein paper I referenced has an example of an architecture where pairing is a requirement and they show how to encode this using infinite costs to prevent illegal non-adjacent assignments. You can do better still. Since your pairs are an optimization rather than a requirement you can encode the cost of failing to assign adjacent physicals and let the PBQP solver try to find a minimal cost solution.
You'll still have to combine the instructions yourself, but at least the pairing will be taken care of. Perhaps you can alter your instruction scheduling to try to keep copies together. Or you can make your copy combiner a bit smarter and have it check data dependencies to see if code can be shuffled to enable you to combine extra moves?
- Lang.
Reply all
Reply to author
Forward
0 new messages