Register Allocation and copy instructions

Hi, while writing my register allocator, I have come across a case which confuses me because the llvm definition cannot be mapped to machine code.

For instance I come across (1) and I reduce it to (2). However a copy instruction cannot move from EDX to CX. What mechanics in LLVM will tell me that I cannot make this move during register allocation, or how can I tell from (1) that I cannot execute %reg16385 = COPY %reg16390. Furthermore, how should I handle this case.

1:

Machine code for function test5:

Frame Objects:
fi#-2: size=2, align=4, fixed, at location [SP+8]
fi#-1: size=2, align=8, fixed, at location [SP+4]
Function Live Outs: %AX

BB#0: derived from LLVM BB %entry
%reg16390 = MOVZX32rm16 <fi#-2>, 1, %reg0, 0, %reg0; mem:LD2[FixedStack-2] GR32:%reg16390
%reg16385 = COPY %reg16390:sub_16bit; GR16:%reg16385 GR32:%reg16390
%reg16391 = MOVZX32rm16 <fi#-1>, 1, %reg0, 0, %reg0; mem:LD2[FixedStack-1] GR32:%reg16391
%reg16384 = COPY %reg16391:sub_16bit; GR16:%reg16384 GR32:%reg16391
Successors according to CFG: BB#1

2:
BB#0: derived from LLVM BB %entry
%EDX = MOVZX32rm16 <fi#-2>, 1, %reg0, 0, %reg0; mem:LD2[FixedStack-2]
%CX = COPY %EDX
%ESI = MOVZX32rm16 <fi#-1>, 1, %reg0, 0, %reg0; mem:LD2[FixedStack-1]
%AX = COPY %ESI

Below is the full code for the function.

Machine code for function test5:

Frame Objects:
fi#-2: size=2, align=4, fixed, at location [SP+8]
fi#-1: size=2, align=8, fixed, at location [SP+4]
Function Live Outs: %AX

BB#0: derived from LLVM BB %entry
%reg16390 = MOVZX32rm16 <fi#-2>, 1, %reg0, 0, %reg0; mem:LD2[FixedStack-2] GR32:%reg16390
%reg16385 = COPY %reg16390:sub_16bit; GR16:%reg16385 GR32:%reg16390
%reg16391 = MOVZX32rm16 <fi#-1>, 1, %reg0, 0, %reg0; mem:LD2[FixedStack-1] GR32:%reg16391
%reg16384 = COPY %reg16391:sub_16bit; GR16:%reg16384 GR32:%reg16391
Successors according to CFG: BB#1

BB#1: derived from LLVM BB %bb
Predecessors according to CFG: BB#0 BB#1
%reg16386 = PHI %reg16385, <BB#0>, %reg16394, <BB#1>; GR16:%reg16386,16385,16394
%reg16387 = PHI %reg16384, <BB#0>, %reg16398, <BB#1>; GR16:%reg16387,16384,16398
%reg16393 = MOV16ri 1; GR16:%reg16393
%reg16398 = COPY %reg16387; GR16:%reg16398,16387
%reg16398 = XOR16rr %reg16398, %reg16386, %EFLAGS; GR16:%reg16398,16386
%reg16397 = COPY %reg16398; GR16:%reg16397,16398
%reg16397 = XOR16ri %reg16397, 32767, %EFLAGS; GR16:%reg16397
%reg16396 = COPY %reg16397; GR16:%reg16396,16397
%reg16396 = AND16rr %reg16396, %reg16386, %EFLAGS; GR16:%reg16396,16386
%reg16394 = COPY %reg16396; GR16:%reg16394,16396
%reg16394 = SHL16ri %reg16394, 1, %EFLAGS; GR16:%reg16394
CMP16ri %reg16394, 0, %EFLAGS; GR16:%reg16394
JNE_4 <BB#1>, %EFLAGS
Successors according to CFG: BB#2 BB#1

BB#2: derived from LLVM BB %bb12
Predecessors according to CFG: BB#1
%AX = COPY %reg16398; GR16:%reg16398
RET

End machine code for function test5.

After Register Allocation:

Machine code for function test5:

Frame Objects:
fi#-2: size=2, align=4, fixed, at location [SP+8]
fi#-1: size=2, align=8, fixed, at location [SP+4]
Function Live Outs: %AX

BB#0: derived from LLVM BB %entry
%EDX = MOVZX32rm16 <fi#-2>, 1, %reg0, 0, %reg0; mem:LD2[FixedStack-2]
%CX = COPY %EDX
%ESI = MOVZX32rm16 <fi#-1>, 1, %reg0, 0, %reg0; mem:LD2[FixedStack-1]
%AX = COPY %ESI
Successors according to CFG: BB#1

BB#1: derived from LLVM BB %bb
Predecessors according to CFG: BB#0 BB#1
%AX = XOR16rr %AX, %CX, %EFLAGS
%DX = COPY %AX
%DX = XOR16ri %DX, 32767, %EFLAGS
%DX = AND16rr %DX, %CX, %EFLAGS
%CX = SHL16ri %CX, 1, %EFLAGS
CMP16ri %CX, 0, %EFLAGS
JNE_4 <BB#1>, %EFLAGS
Successors according to CFG: BB#2 BB#1

BB#2: derived from LLVM BB %bb12
Predecessors according to CFG: BB#1
RET

MachineOperands can refer to sub-registers of virtual registers. That is what is happening here. It is not specific to COPY instructions, but it happens a lot for them.

You should look at how the other register allocators are rewriting virtual registers to physicals.

/jakob

BB#0: derived from LLVM BB %entry
%reg16390 = MOVZX32rm16 <fi#-2>, 1, %reg0, 0, %reg0; mem:LD2[FixedStack-2] GR32:%reg16390
%reg16385 = COPY %reg16390:sub_16bit; GR16:%reg16385 GR32:%reg16390
%reg16391 = MOVZX32rm16 <fi#-1>, 1, %reg0, 0, %reg0; mem:LD2[FixedStack-1] GR32:%reg16391
%reg16384 = COPY %reg16391:sub_16bit; GR16:%reg16384 GR32:%reg16391
Successors according to CFG: BB#1

MachineOperands can refer to sub-registers of virtual registers. That is what is happening here. It is not specific to COPY instructions, but it happens a lot for them.

You should look at how the other register allocators are rewriting virtual registers to physicals.

/jakob

Thanks, it looks like all I have to do is check the ‘sub_16bit’ flag from the operand. This flag makes it possible for the target register class of a virtual register to change.

  • Jeff Kunkel