Live intervals and aliasing registers problem

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
6 messages Options
Reply | Threaded
Open this post in threaded view
|

Live intervals and aliasing registers problem

Christopher Lamb
While beginning to add vector registers to a back end I came across the following problem: as soon as I define two sets of registers that have a many-to-one mapping the live interval pass appears to double-kill the mapped-onto register. I have the following excerpts from my RegisterInfo.td.

def V4R0   : R4v<0 , "V4R0 ", []>, DwarfRegNum<0>;

def R0   : Rg<0 , "R0", [V4R0]>, DwarfRegNum<0>;
def R1   : Rg<1 , "R1", [V4R0]>, DwarfRegNum<1>;

when trying to compile:

define void @_Z3fooii(i32 %a, i32 %b) {
entry:
        %retval = select i1 false, i32 %a, i32 %b               ; <i32> [#uses=0]
        ret void

I get this error:

entry (0x8503b90, LLVM BB @0x8501b00, ID#0):
        %reg1024 = ORI %R0, 0
        %reg1025 = ORI %R1, 0
        RETL
Machine Function
********** REWRITING TWO-ADDR INSTRS **********
********** Function: _Z3fooff

********** COMPUTING LIVE INTERVALS **********
********** Function: _Z3fooii
entry:
                livein register: R0 killed +[0,2:0)
                livein register: V4R0  killed +[0,2:0)
                livein register: R1 killed +[0,6:0)
                livein register: V4R0  killed +[0,2:1)
lib/CodeGen/LiveInterval.cpp:189: failed assertion `B->end <= Start && "Cannot overlap two LiveRanges with differing ValID's" " (did you def the same reg twice in a MachineInstr?)"'

The problem here is that both R0 and R1 alias to V4R0, but because the live-in interval analysis always starts with the first instruction in the function V4R0 gets the same live range for for both when R0 kills it and when R1, as the first instruction is responsible for the earliest kill in both cases. This presents a problem as the second kill of V4R0 is marked as a second value of V4R0 as well, which causes the assert above to fire.

Either V4R0 is never alive or after R0 is killed V4R0 is only partially dead. This same situation arises even when the parameters are not live-ins to the function, all it takes is two registers which alias a third to have overlapping live ranges, such as when the following code is compiled.

define void @_Z3foov() {
entry:
%tmp1 = tail call float @_Z3onev( ) ; <float> [#uses=2]
%tmp2 = tail call float @_Z3twov( ) ; <float> [#uses=2]
%tmp5 = fcmp olt float %tmp1, %tmp2 ; <i1> [#uses=1]
%retval = select i1 %tmp5, float %tmp1, float %tmp2 ; <float> [#uses=0]
ret void
}

Does the fact that V4R0 is considered live-in mean I need to fix my target code, or does the live interval analysis need fixing to handle this corner case? Any guidance on how to approach this problem would be greatly appreciated.

Thanks
--
Christopher Lamb



_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Live intervals and aliasing registers problem

Christopher Lamb
I'm having trouble with overlapping intervals for vector registers.  
How are intervals for registers that both alias to the same larger  
register intended to be handled?

To demonstrate this problem you can use a minor addition to the Sparc  
register description.

Add this to the SparcRegisterInfo.td at line 68:

// Rtest
class Rtest<bits<5> num, string n, list<Register> aliases> :  
SparcReg<n> {
   let Num = num;
   let Aliases = aliases;
}

def ALIASING : Rtest<0, "Rtest0", [I0, I1]>, DwarfRegNum<0>;

Then attempt to build the attached llvm file using 'llvm-as <  
vecinterval.ll | llc -debug -march=sparc vecinterval -f -o  
vecinterval.s'

I get the following error:
********** COMPUTING LIVE INTERVALS **********
********** Function: _Z3fooff
entry:
                 livein register: I0 killed +[0,2:0)
                 livein register: Rtest0 killed +[0,2:0)
                 livein register: I1 killed +[0,6:0)
                 livein register: Rtest0 killed +[0,2:1)
lib/CodeGen/LiveInterval.cpp:189: failed assertion `B->end <= Start  
&& "Cannot overlap two LiveRanges with differing ValID's" " (did you  
def the same reg twice in a MachineInstr?)"'
Abort trap



--
Christopher Lamb
[hidden email]




_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

vecinterval.ll (429 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Live intervals and aliasing registers problem

Evan Cheng-2
In reply to this post by Christopher Lamb

On Mar 25, 2007, at 7:12 AM, Christopher Lamb wrote:

While beginning to add vector registers to a back end I came across the following problem: as soon as I define two sets of registers that have a many-to-one mapping the live interval pass appears to double-kill the mapped-onto register. I have the following excerpts from my RegisterInfo.td.

def V4R0   : R4v<0 , "V4R0 ", []>, DwarfRegNum<0>;

def R0   : Rg<0 , "R0", [V4R0]>, DwarfRegNum<0>;
def R1   : Rg<1 , "R1", [V4R0]>, DwarfRegNum<1>;

How are R4v and Rg defined?


when trying to compile:

define void @_Z3fooii(i32 %a, i32 %b) {
entry:
        %retval = select i1 false, i32 %a, i32 %b               ; <i32> [#uses=0]
        ret void

I get this error:

entry (0x8503b90, LLVM BB @0x8501b00, ID#0):
        %reg1024 = ORI %R0, 0
        %reg1025 = ORI %R1, 0
        RETL
Machine Function
********** REWRITING TWO-ADDR INSTRS **********
********** Function: _Z3fooff

********** COMPUTING LIVE INTERVALS **********
********** Function: _Z3fooii
entry:
                livein register: R0 killed +[0,2:0)
                livein register: V4R0  killed +[0,2:0)  <=== this is bad
                livein register: R1 killed +[0,6:0)
                livein register: V4R0  killed +[0,2:1)
lib/CodeGen/LiveInterval.cpp:189: failed assertion `B->end <= Start && "Cannot overlap two LiveRanges with differing ValID's" " (did you def the same reg twice in a MachineInstr?)"'

V4R0 should not have been killed twice. The second ORI instruction is the last use of V4R0. Are you adding the correct livein's (just R0 and R1) to the function? 

Can you dump out the machine basic block? It should have an implicit use of V4R0 at first ORI but it should not be marked kill. If it is marked kill, then you need to walk LiveVariables.cpp to find out why.

Evan



The problem here is that both R0 and R1 alias to V4R0, but because the live-in interval analysis always starts with the first instruction in the function V4R0 gets the same live range for for both when R0 kills it and when R1, as the first instruction is responsible for the earliest kill in both cases. This presents a problem as the second kill of V4R0 is marked as a second value of V4R0 as well, which causes the assert above to fire.

Either V4R0 is never alive or after R0 is killed V4R0 is only partially dead. This same situation arises even when the parameters are not live-ins to the function, all it takes is two registers which alias a third to have overlapping live ranges, such as when the following code is compiled.

define void @_Z3foov() {
entry:
%tmp1 = tail call float @_Z3onev( ) ; <float> [#uses=2]
%tmp2 = tail call float @_Z3twov( ) ; <float> [#uses=2]
%tmp5 = fcmp olt float %tmp1, %tmp2 ; <i1> [#uses=1]
%retval = select i1 %tmp5, float %tmp1, float %tmp2 ; <float> [#uses=0]
ret void
}

Does the fact that V4R0 is considered live-in mean I need to fix my target code, or does the live interval analysis need fixing to handle this corner case? Any guidance on how to approach this problem would be greatly appreciated.

Thanks
--
Christopher Lamb


_______________________________________________
LLVM Developers mailing list


_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Live intervals and aliasing registers problem

Christopher Lamb

On Mar 27, 2007, at 3:25 PM, Evan Cheng wrote:

>
> On Mar 25, 2007, at 7:12 AM, Christopher Lamb wrote:
>
>> While beginning to add vector registers to a back end I came  
>> across the following problem: as soon as I define two sets of  
>> registers that have a many-to-one mapping the live interval pass  
>> appears to double-kill the mapped-onto register. I have the  
>> following excerpts from my RegisterInfo.td.
>>
>> def V4R0   : R4v<0 , "V4R0 ", []>, DwarfRegNum<0>;
>>
>> def R0   : Rg<0 , "R0", [V4R0]>, DwarfRegNum<0>;
>> def R1   : Rg<1 , "R1", [V4R0]>, DwarfRegNum<1>;
>
> How are R4v and Rg defined?

class Rg<bits<6> num, string n, list<Register> aliases> : MyReg<n>
{
   let Num = num;
   let Aliases = aliases;
}

class R4v<bits<6> num, string n, list<Register> aliases> : MyReg<n> {
   let Num = num;
   let Aliases = aliases;
}


>>
>> when trying to compile:
>>
>> define void @_Z3fooii(i32 %a, i32 %b) {
>> entry:
>>         %retval = select i1 false, i32 %a, i32 %b               ;  
>> <i32> [#uses=0]
>>         ret void
>> }
>>
>> I get this error:
>>
>> entry (0x8503b90, LLVM BB @0x8501b00, ID#0):
>>         %reg1024 = ORI %R0, 0
>>         %reg1025 = ORI %R1, 0
>>         RETL
>> Machine Function
>> ********** REWRITING TWO-ADDR INSTRS **********
>> ********** Function: _Z3fooff
>>
>> ********** COMPUTING LIVE INTERVALS **********
>> ********** Function: _Z3fooii
>> entry:
>>                 livein register: R0 killed +[0,2:0)
>>                 livein register: V4R0  killed +[0,2:0)  <=== this  
>> is bad
>>                 livein register: R1 killed +[0,6:0)
>>                 livein register: V4R0  killed +[0,2:1)
>> lib/CodeGen/LiveInterval.cpp:189: failed assertion `B->end <=  
>> Start && "Cannot overlap two LiveRanges with differing ValID's"  
>> " (did you def the same reg twice in a MachineInstr?)"'
>
> V4R0 should not have been killed twice. The second ORI instruction  
> is the last use of V4R0. Are you adding the correct livein's (just  
> R0 and R1) to the function?

Yes, only R0 and R1 are being added.

> Can you dump out the machine basic block? It should have an  
> implicit use of V4R0 at first ORI but it should not be marked kill.  
> If it is marked kill, then you need to walk LiveVariables.cpp to  
> find out why.

Here is the beginning of the BB dump.

entry (0x8503c80, LLVM BB @0x8501af0, ID#0):
Live Ins: %R0 %R1
        %reg1024 = ORI %R0<kill>, 0
        %reg1025 = ORI %R1<kill>, 0

V4R0 is getting killed because handleLiveInRegister() is called on  
all results of getAliasSet() for each of the liveins (this is in  
LiveIntervals::computeIntervals() ).

handleRegisterDef() does a similar thing where calls  
handlePhysicalRegisterDef() on all members of getAliasSet() returned  
for the def, which also triggers this problem.

Is it calling handle*() on the alias set of a register thats the  
culprit, or is it some mishandling in KillsRegister()?

Thanks
--
Christopher Lamb



_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Live intervals and aliasing registers problem

Evan Cheng-2

On Apr 3, 2007, at 3:45 PM, Christopher Lamb wrote:


Can you dump out the machine basic block? It should have an  
implicit use of V4R0 at first ORI but it should not be marked kill.  
If it is marked kill, then you need to walk LiveVariables.cpp to  
find out why.

Here is the beginning of the BB dump.

entry (0x8503c80, LLVM BB @0x8501af0, ID#0):
Live Ins: %R0 %R1
%reg1024 = ORI %R0<kill>, 0
%reg1025 = ORI %R1<kill>, 0

V4R0 is getting killed because handleLiveInRegister() is called on  
all results of getAliasSet() for each of the liveins (this is in  
LiveIntervals::computeIntervals() ).

handleRegisterDef() does a similar thing where calls  
handlePhysicalRegisterDef() on all members of getAliasSet() returned  
for the def, which also triggers this problem.

Is it calling handle*() on the alias set of a register thats the  
culprit, or is it some mishandling in KillsRegister()?

This is a pretty serious bug. LiveVariables::KillsRegister should not kill aliases that are "larger". The correct way to fix this is to explicitly list registers that are defined, used, and killed. So your example should look like:

entry (0x8503c80, LLVM BB @0x8501af0, ID#0):
Live Ins: %R0 %R1
%reg1024 = ORI %R0<kill>, 0, %V4R0<imp-use>
%reg1025 = ORI %R1<kill>, 0, %V4R0<imp-use,kill>

KillsRegister should check for exact match rather than regsOverlap. There are probably other similar bugs in LiveVariables.

Please file a bug, I'll look at after I get back from vacation in a week.

Evan


Thanks
--
Christopher Lamb



_______________________________________________
LLVM Developers mailing list


_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Live intervals and aliasing registers problem

Christopher Lamb

On Apr 4, 2007, at 1:38 PM, Evan Cheng wrote:


On Apr 3, 2007, at 3:45 PM, Christopher Lamb wrote:


Can you dump out the machine basic block? It should have an  
implicit use of V4R0 at first ORI but it should not be marked kill.  
If it is marked kill, then you need to walk LiveVariables.cpp to  
find out why.

Here is the beginning of the BB dump.

entry (0x8503c80, LLVM BB @0x8501af0, ID#0):
Live Ins: %R0 %R1
%reg1024 = ORI %R0<kill>, 0
%reg1025 = ORI %R1<kill>, 0

V4R0 is getting killed because handleLiveInRegister() is called on  
all results of getAliasSet() for each of the liveins (this is in  
LiveIntervals::computeIntervals() ).

handleRegisterDef() does a similar thing where calls  
handlePhysicalRegisterDef() on all members of getAliasSet() returned  
for the def, which also triggers this problem.

Is it calling handle*() on the alias set of a register thats the  
culprit, or is it some mishandling in KillsRegister()?

This is a pretty serious bug. LiveVariables::KillsRegister should not kill aliases that are "larger". The correct way to fix this is to explicitly list registers that are defined, used, and killed. So your example should look like:

entry (0x8503c80, LLVM BB @0x8501af0, ID#0):
Live Ins: %R0 %R1
%reg1024 = ORI %R0<kill>, 0, %V4R0<imp-use>
%reg1025 = ORI %R1<kill>, 0, %V4R0<imp-use,kill>

KillsRegister should check for exact match rather than regsOverlap. There are probably other similar bugs in LiveVariables.

Please file a bug, I'll look at after I get back from vacation in a week.

I've filed it as PR1306. Thanks for looking into this.

--
Christopher Lamb




_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev