llvm dev - Jan 2013 - [LLVMdev] Splitting live ranges of half-defined registers

I have already written about something similar (either on the list, or 
in private communication), so this may look familiar.

Here's a scenario I'm observing:

First, we have some innocent looking code:
    vreg(32) = x                  // vreg(32) = 32-bit register
    ... = vreg(32)
    [...]
    vreg(64).low_half = vreg(32)  // vreg(64) = 64-bit register
    [...]

then, after register coalescing:
    vreg(64).low_half = x
    ... = vreg(64).low_half
    [...]
    [etc.]

then, the live range of the 64-bit vreg is split during register allocation:
    vreg'(64).low_half = x     // first live range starts
    ... = vreg'(64).low_half
    vreg"(64) = vreg'(64)      // next live range starts
    [...]

The problem is that vreg' only has half of it defined, and so the 
assignment vreg" = vreg' copies a register which has half of it
undefined.


My question is: is this something that was a part of the design?


The problem may arise if someone, for whatever reason, decides to 
rewrite the 64-bit copy as two 32-bit copies, e.g.
     vreg"(32).low_half  = vreg'(32).low_half     (1)
     vreg"(32).high_half = vreg'(32).high_half    (2)
When this happens, the assignment (2) basically reads an undefined register.



A scenario like this happens in real life.  Look at vreg304 below:

BB#2: derived from LLVM BB %if.end
     Predecessors according to CFG: BB#1
         %vreg61<def> = LDrih_indexed %vreg56, 3134;
IntRegs:%vreg61,%vreg56
         %vreg62<def> = LDriuh_indexed %vreg56, 680;
IntRegs:%vreg62,%vreg56
         %R1<def> = TFRI 1431655766
         ADJCALLSTACKDOWN 0, %R29<imp-def>, %R30<imp-def>, 
%R31<imp-use>, %R30<imp-use>, %R29<imp-use>
         %vreg304:subreg_loreg<def,read-undef> = ADDri_SUBr_V4 %vreg62, 
5, %vreg61; DoubleRegs:%vreg304 IntRegs:%vreg62,%vreg61
         %vreg519<def> = TFRI 3148; IntRegs:%vreg519
         %vreg523<def> = TFRI64 15; DoubleRegs:%vreg523
         %R0<def> = COPY %vreg304:subreg_loreg; DoubleRegs:%vreg304
         CALLv3 <ga:@foo>, %D0<imp-def,dead>,
%D1<imp-def,dead>,
%D2<imp-def,dead>, %R31<imp-def>, %R0<imp-use>,
%R1<imp-use>,
%R0<imp-def>, ...


Then, after live range splitting, we have vreg539 and vreg537, and right 
before the call, a copy from half-undefined vreg539:

BB#2: derived from LLVM BB %if.end
     Predecessors according to CFG: BB#1
         %vreg61<def> = LDrih_indexed %vreg56, 3134; 
IntRegs:%vreg61,%vreg56
         %vreg62<def> = LDriuh_indexed %vreg56, 680;
IntRegs:%vreg62,%vreg56
         %R1<def> = TFRI 1431655766
         ADJCALLSTACKDOWN 0, %R29<imp-def>, %R30<imp-def>, 
%R31<imp-use>, %R30<imp-use>, %R29<imp-use>
         %vreg539:subreg_loreg<def,read-undef> = ADDri_SUBr_V4 %vreg62, 
5, %vreg61; DoubleRegs:%vreg539 IntRegs:%vreg62,%vreg61
         %vreg519<def> = TFRI 3148; IntRegs:%vreg519
         %vreg523<def> = TFRI64 15; DoubleRegs:%vreg523
         %R0<def> = COPY %vreg539:subreg_loreg; DoubleRegs:%vreg539
         %vreg537<def> = COPY %vreg539; DoubleRegs:%vreg537,%vreg539
         CALLv3 <ga:@foo>, %D0<imp-def,dead>,
%D1<imp-def,dead>,
%D2<imp-def,dead>, %R31<imp-def>, %R0<imp-use>,
%R1<imp-use>,
%R0<imp-def>, ...


-Krzysztof

-- 
Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, 
hosted by The Linux Foundation

On Jan 14, 2013, at 12:56 PM, Krzysztof Parzyszek <kparzysz at
codeaurora.org> wrote:
> I have already written about something similar (either on the list, or in
private communication), so this may look familiar.
> 
> Here's a scenario I'm observing:
> 
> First, we have some innocent looking code:
>   vreg(32) = x                  // vreg(32) = 32-bit register
>   ... = vreg(32)
>   [...]
>   vreg(64).low_half = vreg(32)  // vreg(64) = 64-bit register
>   [...]
> 
> then, after register coalescing:
>   vreg(64).low_half = x
>   ... = vreg(64).low_half
>   [...]
>   [etc.]
> 
> then, the live range of the 64-bit vreg is split during register
allocation:
>   vreg'(64).low_half = x     // first live range starts
>   ... = vreg'(64).low_half
>   vreg"(64) = vreg'(64)      // next live range starts
>   [...]
> 
> The problem is that vreg' only has half of it defined, and so the
assignment vreg" = vreg' copies a register which has half of it
undefined.
> 
> 
> My question is: is this something that was a part of the design?
Yes, the register allocator only deals in full-width virtual registers, so any
copies or spills created will operate on the full register.

The coalescer can do some tricks by tracking partially defined registers, more
so in LLVM 3.2 than earlier releases.

I would like to make it possible to track independent live ranges for each lane
of a vector register. That would help both coalescing and RA, but it is a major
project.

/jakob

On 1/14/2013 3:16 PM, Jakob Stoklund Olesen wrote:
>
> On Jan 14, 2013, at 12:56 PM, Krzysztof Parzyszek <kparzysz at
codeaurora.org> wrote:
>>
>> My question is: is this something that was a part of the design?
>
> Yes, the register allocator only deals in full-width virtual registers, so
any copies or spills created will operate on the full register.
I see.

Unfortunately, this is causing some customer code to fail in 
compilation.  The direct cause of the compilation failure is a complaint 
from the register scavenger in the scenario that I described in the 
first email.

This is actually very much related to the other problem I've reported a 
while ago ("wrong value out of predecessor")---splitting (and
spilling)
of partially defined registers was also key to the failure occurring.

I can deal with this locally, so it's not a major blocker for us.

Thanks,
-Krzysztof


-- 
Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, 
hosted by The Linux Foundation