thr3ads.net - llvm dev - [LLVMdev] [LLVMDev] Register Allocation and copy instructions [Nov 2010]

If this information is useful, please help other people find it:
Share via:

Jeff Kunkel

2010-Nov-08 20:04 UTC

[LLVMdev] [LLVMDev] 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<def> = 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<def> = MOVZX32rm16 <fi#-2>, 1, %reg0, 0, %reg0;
mem:LD2[FixedStack-2] GR32:%reg16390
        %reg16385<def> = COPY %reg16390:sub_16bit<kill>;
GR16:%reg16385
GR32:%reg16390
        %reg16391<def> = MOVZX32rm16 <fi#-1>, 1, %reg0, 0, %reg0;
mem:LD2[FixedStack-1] GR32:%reg16391
        %reg16384<def> = COPY %reg16391:sub_16bit<kill>;
GR16:%reg16384
GR32:%reg16391
    Successors according to CFG: BB#1
...

2:
BB#0: derived from LLVM BB %entry
        %EDX<def> = MOVZX32rm16 <fi#-2>, 1, %reg0, 0, %reg0;
mem:LD2[FixedStack-2]
        %CX<def> = COPY %EDX
        %ESI<def> = MOVZX32rm16 <fi#-1>, 1, %reg0, 0, %reg0;
mem:LD2[FixedStack-1]
        %AX<def> = 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<def> = MOVZX32rm16 <fi#-2>, 1, %reg0, 0, %reg0;
mem:LD2[FixedStack-2] GR32:%reg16390
        %reg16385<def> = COPY %reg16390:sub_16bit<kill>;
GR16:%reg16385
GR32:%reg16390
        %reg16391<def> = MOVZX32rm16 <fi#-1>, 1, %reg0, 0, %reg0;
mem:LD2[FixedStack-1] GR32:%reg16391
        %reg16384<def> = COPY %reg16391:sub_16bit<kill>;
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<def> = PHI %reg16385, <BB#0>, %reg16394,
<BB#1>;
GR16:%reg16386,16385,16394
        %reg16387<def> = PHI %reg16384, <BB#0>, %reg16398,
<BB#1>;
GR16:%reg16387,16384,16398
        %reg16393<def> = MOV16ri 1; GR16:%reg16393
        %reg16398<def> = COPY %reg16387; GR16:%reg16398,16387
        %reg16398<def> = XOR16rr %reg16398, %reg16386,
%EFLAGS<imp-def>;
GR16:%reg16398,16386
        %reg16397<def> = COPY %reg16398; GR16:%reg16397,16398
        %reg16397<def> = XOR16ri %reg16397, 32767, %EFLAGS<imp-def>;
GR16:%reg16397
        %reg16396<def> = COPY %reg16397; GR16:%reg16396,16397
        %reg16396<def> = AND16rr %reg16396, %reg16386,
%EFLAGS<imp-def>;
GR16:%reg16396,16386
        %reg16394<def> = COPY %reg16396; GR16:%reg16394,16396
        %reg16394<def> = SHL16ri %reg16394, 1, %EFLAGS<imp-def>;
GR16:%reg16394
        CMP16ri %reg16394, 0, %EFLAGS<imp-def>; GR16:%reg16394
        JNE_4 <BB#1>, %EFLAGS<imp-use>
    Successors according to CFG: BB#2 BB#1

BB#2: derived from LLVM BB %bb12
    Predecessors according to CFG: BB#1
        %AX<def> = 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<def> = MOVZX32rm16 <fi#-2>, 1, %reg0, 0, %reg0;
mem:LD2[FixedStack-2]
        %CX<def> = COPY %EDX
        %ESI<def> = MOVZX32rm16 <fi#-1>, 1, %reg0, 0, %reg0;
mem:LD2[FixedStack-1]
        %AX<def> = COPY %ESI
    Successors according to CFG: BB#1

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

BB#2: derived from LLVM BB %bb12
    Predecessors according to CFG: BB#1
        RET
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20101108/56e4bc55/attachment.html>

Jakob Stoklund Olesen

2010-Nov-08 23:31 UTC

head link

[LLVMdev] [LLVMDev] Register Allocation and copy instructions

On Nov 8, 2010, at 12:04 PM, Jeff Kunkel wrote:
> 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<def> = COPY %reg16390. Furthermore, how
should I handle this case.
> BB#0: derived from LLVM BB %entry
>         %reg16390<def> = MOVZX32rm16 <fi#-2>, 1, %reg0, 0,
%reg0; mem:LD2[FixedStack-2] GR32:%reg16390
>         %reg16385<def> = COPY %reg16390:sub_16bit<kill>;
GR16:%reg16385 GR32:%reg16390
>         %reg16391<def> = MOVZX32rm16 <fi#-1>, 1, %reg0, 0,
%reg0; mem:LD2[FixedStack-1] GR32:%reg16391
>         %reg16384<def> = COPY %reg16391:sub_16bit<kill>;
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

Jeff Kunkel

2010-Nov-09 13:28 UTC

head link

[LLVMdev] [LLVMDev] Register Allocation and copy instructions

>
>
> > BB#0: derived from LLVM BB %entry
> >         %reg16390<def> = MOVZX32rm16 <fi#-2>, 1, %reg0, 0,
%reg0;
> mem:LD2[FixedStack-2] GR32:%reg16390
> >         %reg16385<def> = COPY %reg16390:sub_16bit<kill>;
GR16:%reg16385
> GR32:%reg16390
> >         %reg16391<def> = MOVZX32rm16 <fi#-1>, 1, %reg0, 0,
%reg0;
> mem:LD2[FixedStack-1] GR32:%reg16391
> >         %reg16384<def> = COPY %reg16391:sub_16bit<kill>;
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
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20101109/a22570f6/attachment.html>

Maybe Matching Threads

Search for more maybe matching threads

llvm dev - Nov 2010 - [LLVMdev] [LLVMDev] Register Allocation and copy instructions

[LLVMdev] [LLVMDev] Register Allocation and copy instructions

[LLVMdev] [LLVMDev] Register Allocation and copy instructions

[LLVMdev] [LLVMDev] Register Allocation and copy instructions

Maybe Matching Threads