llvm dev - Dec 2006 - [LLVMdev] Possible bug in the linear scan register allocator

On Dec 20, 2006, at 2:06 PM, Roman Levenstein wrote:
>>
>> This will probably require a slightly more extensive patch to
>> legalizer. The current mechanism assumes either 1->1 or 1->2
>> expansion.
>
> Exactly. This is what I meant with "more chellenging";) It is
assumed
> at several places that 1->1 or 2->2 expanstions are taking place. A
> generic case is not handled yet.
>
>> It also assumes the result of expansion are of legal
>> types.
>
> Yes. And this is also a reason why it is not too obvious how to handle
> f32->f64 promotion and later f64->i64 expansion on targets that  
> support
> only f64 soft-floats.
>
> Chris Lattner wrote:
>> That would be recursively expanded to i64, then to 2x i32 if needed.
>
> I tried to set getTypeToTransformTo(f32) to return f64, even when f64
> is illegal type. But this recursive expansion does not take place with
> the current legalizer implementation. Currently, it is assumed that  
> the
> result of  getTypeToTransformTo() is a legal type. For example,
> CreateRegForValue tries to create a register of such a promoted type
> and fails in the above mentioned case.
All of the issues can be solved by adding the logic to recursively  
expand operands. They shouldn't be too complicated.
>
>
> Evan wrote:
>> That means, you will have to either 1) modify ExpandOp() to
>> handle cases which need to be recursively expanded or 2) modify it to
>
>> return a vector of SDOperand's. Solution one is what I would
pursue.
>
> Agreed. I also feel that some sort of recursive expansion is required.
>
> I also have a feeling that getTypeToTransformTo(MVT::ValueType) should
> probably also recurse until it finds a type T where
> getTypeToTransformTo(T) = T, i.e. it finds a legal type. This would
> almost solve the issue with f32->f64 promotion where both FP types are
> illegal. The only concern here is that in this case
> getTypeToTransformTo(MVT::f32) would return MVT::i64 and therefore the
> information about the fact that it should first be promoted to f64 is
> lost. The problem is that getTypeToTransformTo() is used for two
> "different" goals: to tell which type to use for register mapping
and
> to tell which type to use for promotions/expansions for the sake of
> "type system correctness". May be it would even make sense to
have two
> different mappings because of this? One mapping will be used for
> allocation of virtual registers and the like and would always return a
> legal type and the other will be used just as getTypeToTransformTo 
> () in
> LegalizeOp(), ExpandOp() and PromoteOp() and can return also illegal
> types?
No need to change getTypeToTransformTo(). There is a getTypeToExpandTo 
() that is expand the type recursively until it find a legal type.
>
>> It's not done simply because there isn't a need for it right
now. :-)
>
> Since I have this need, I'll try to find a solution for this issue and
> to provide a patch.
Great! There are a few spots where ExpandOp() are called recursively.  
It would be nice to remove those and use the general expansion  
facility instead.

Evan
>
> -Roman
>
> __________________________________________________
> Do You Yahoo!?
> Tired of spam?  Yahoo! Mail has the best spam protection around
> http://mail.yahoo.com
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

Hi,

I was working on extending soft-float support for handling expansion of
i64 and f64 into i16, i.e. on supporting the expansion of long values
of illegal types into more then two parts. For that I modified
SelectionDAGLowering::getValue() and several other functions.

This seems to work now on my test-cases, but while testing it I ran
into a different problem. I have the impression that I found a bug in
the linear-scan register allocator (local and simple allocators work
just fine on the same code). The problem is that linear scan loops for
ever under certain conditions. May be I overlook something in my target
specific code, but I think that it is wrong in any case if a register
allocator loops for ever.

I attach a part of the log file produced with "llc -debug" where you
can see reg.alloc related bits. Register naming convention is:
 rbN - for 8bit registers
 rwN - for 16bit registers
 rxN - for 32bit registers 

I also attach the C source file and the  LLVM assembler file for your
convenience.
 
My personal understanding of what is going on is that it is due to the
incorrect joining of live intervals. If I disable intervals joining by
using --join-liveintervals=false, everything works fine. 
According to the log file, what happens during joining is the
following:
 1) some of the fixed registers intervals are merged with some virtual
registers intervals
 2) later there is a need to spill one of the allocated registers, but
since all joined intervals are FIXED intervals now due to (1), they
cannot be spilled. Therefore, the register allocator loops for ever.

I would be grateful, if someone would confirm that this is a bug. And
of course, it would be very nice if one of the RegAlloc Gurus could fix
it ;)

-Roman

--- Evan Cheng <evan.cheng at apple.com> wrote:
> 
> On Dec 20, 2006, at 2:06 PM, Roman Levenstein wrote:
> 
> >>
> >> This will probably require a slightly more extensive patch to
> >> legalizer. The current mechanism assumes either 1->1 or 1->2
> >> expansion.
> >
> > Exactly. This is what I meant with "more chellenging";) It
is
> assumed
> > at several places that 1->1 or 2->2 expanstions are taking
place. A
> > generic case is not handled yet.
> >
> >> It also assumes the result of expansion are of legal
> >> types.
> >
> > Yes. And this is also a reason why it is not too obvious how to
> handle
> > f32->f64 promotion and later f64->i64 expansion on targets that
> > support
> > only f64 soft-floats.
> >
> > Chris Lattner wrote:
> >> That would be recursively expanded to i64, then to 2x i32 if
> needed.
> >
> > I tried to set getTypeToTransformTo(f32) to return f64, even when
> f64
> > is illegal type. But this recursive expansion does not take place
> with
> > the current legalizer implementation. Currently, it is assumed that
>  
> > the
> > result of  getTypeToTransformTo() is a legal type. For example,
> > CreateRegForValue tries to create a register of such a promoted
> type
> > and fails in the above mentioned case.
> 
> All of the issues can be solved by adding the logic to recursively  
> expand operands. They shouldn't be too complicated.
> 
> >
> >
> > Evan wrote:
> >> That means, you will have to either 1) modify ExpandOp() to
> >> handle cases which need to be recursively expanded or 2) modify it
> to
> >
> >> return a vector of SDOperand's. Solution one is what I would
> pursue.
> >
> > Agreed. I also feel that some sort of recursive expansion is
> required.
> >
> > I also have a feeling that getTypeToTransformTo(MVT::ValueType)
> should
> > probably also recurse until it finds a type T where
> > getTypeToTransformTo(T) = T, i.e. it finds a legal type. This would
> > almost solve the issue with f32->f64 promotion where both FP types
> are
> > illegal. The only concern here is that in this case
> > getTypeToTransformTo(MVT::f32) would return MVT::i64 and therefore
> the
> > information about the fact that it should first be promoted to f64
> is
> > lost. The problem is that getTypeToTransformTo() is used for two
> > "different" goals: to tell which type to use for register
mapping
> and
> > to tell which type to use for promotions/expansions for the sake of
> > "type system correctness". May be it would even make sense
to have
> two
> > different mappings because of this? One mapping will be used for
> > allocation of virtual registers and the like and would always
> return a
> > legal type and the other will be used just as getTypeToTransformTo 
> > () in
> > LegalizeOp(), ExpandOp() and PromoteOp() and can return also
> illegal
> > types?
> 
> No need to change getTypeToTransformTo(). There is a
> getTypeToExpandTo 
> () that is expand the type recursively until it find a legal type.
> 
> >
> >> It's not done simply because there isn't a need for it
right now.
> :-)
> >
> > Since I have this need, I'll try to find a solution for this issue
> and
> > to provide a patch.
> 
> Great! There are a few spots where ExpandOp() are called recursively.
>  
> It would be nice to remove those and use the general expansion  
> facility instead.
> 
> Evan
> 
> >
> > -Roman
> >
__________________________________________________
Do You Yahoo!?
Tired of spam?  Yahoo! Mail has the best spam protection around 
http://mail.yahoo.com 
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: RegAlloc.txt
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20061221/286571b5/attachment.txt>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: RegAllocTest.c
Type: text/x-csrc
Size: 121 bytes
Desc: 3887521155-RegAllocTest.c
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20061221/286571b5/attachment.c>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: RegAllocTest.ll
Type: text/x-csrc
Size: 1181 bytes
Desc: 4270130418-RegAllocTest.ll
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20061221/286571b5/attachment-0001.c>

On Thu, 21 Dec 2006, Roman Levenstein wrote:
> following:
> 1) some of the fixed registers intervals are merged with some virtual
> registers intervals
> 2) later there is a need to spill one of the allocated registers, but
> since all joined intervals are FIXED intervals now due to (1), they
> cannot be spilled. Therefore, the register allocator loops for ever.
>
> I would be grateful, if someone would confirm that this is a bug. And
> of course, it would be very nice if one of the RegAlloc Gurus could fix
> it ;)
This is likely a bug, probably PR711.

Unfortunately, this isn't super easy to fix, I don't have plans to do so
in the near future...

-Chris
> --- Evan Cheng <evan.cheng at apple.com> wrote:
>>
>> On Dec 20, 2006, at 2:06 PM, Roman Levenstein wrote:
>>
>>>>
>>>> This will probably require a slightly more extensive patch to
>>>> legalizer. The current mechanism assumes either 1->1 or
1->2
>>>> expansion.
>>>
>>> Exactly. This is what I meant with "more chellenging";)
It is
>> assumed
>>> at several places that 1->1 or 2->2 expanstions are taking
place. A
>>> generic case is not handled yet.
>>>
>>>> It also assumes the result of expansion are of legal
>>>> types.
>>>
>>> Yes. And this is also a reason why it is not too obvious how to
>> handle
>>> f32->f64 promotion and later f64->i64 expansion on targets
that
>>> support
>>> only f64 soft-floats.
>>>
>>> Chris Lattner wrote:
>>>> That would be recursively expanded to i64, then to 2x i32 if
>> needed.
>>>
>>> I tried to set getTypeToTransformTo(f32) to return f64, even when
>> f64
>>> is illegal type. But this recursive expansion does not take place
>> with
>>> the current legalizer implementation. Currently, it is assumed that
>>
>>> the
>>> result of  getTypeToTransformTo() is a legal type. For example,
>>> CreateRegForValue tries to create a register of such a promoted
>> type
>>> and fails in the above mentioned case.
>>
>> All of the issues can be solved by adding the logic to recursively
>> expand operands. They shouldn't be too complicated.
>>
>>>
>>>
>>> Evan wrote:
>>>> That means, you will have to either 1) modify ExpandOp() to
>>>> handle cases which need to be recursively expanded or 2) modify
it
>> to
>>>
>>>> return a vector of SDOperand's. Solution one is what I
would
>> pursue.
>>>
>>> Agreed. I also feel that some sort of recursive expansion is
>> required.
>>>
>>> I also have a feeling that getTypeToTransformTo(MVT::ValueType)
>> should
>>> probably also recurse until it finds a type T where
>>> getTypeToTransformTo(T) = T, i.e. it finds a legal type. This would
>>> almost solve the issue with f32->f64 promotion where both FP
types
>> are
>>> illegal. The only concern here is that in this case
>>> getTypeToTransformTo(MVT::f32) would return MVT::i64 and therefore
>> the
>>> information about the fact that it should first be promoted to f64
>> is
>>> lost. The problem is that getTypeToTransformTo() is used for two
>>> "different" goals: to tell which type to use for register
mapping
>> and
>>> to tell which type to use for promotions/expansions for the sake of
>>> "type system correctness". May be it would even make
sense to have
>> two
>>> different mappings because of this? One mapping will be used for
>>> allocation of virtual registers and the like and would always
>> return a
>>> legal type and the other will be used just as getTypeToTransformTo
>>> () in
>>> LegalizeOp(), ExpandOp() and PromoteOp() and can return also
>> illegal
>>> types?
>>
>> No need to change getTypeToTransformTo(). There is a
>> getTypeToExpandTo
>> () that is expand the type recursively until it find a legal type.
>>
>>>
>>>> It's not done simply because there isn't a need for it
right now.
>> :-)
>>>
>>> Since I have this need, I'll try to find a solution for this
issue
>> and
>>> to provide a patch.
>>
>> Great! There are a few spots where ExpandOp() are called recursively.
>>
>> It would be nice to remove those and use the general expansion
>> facility instead.
>>
>> Evan
>>
>>>
>>> -Roman
>>>
>
> __________________________________________________
> Do You Yahoo!?
> Tired of spam?  Yahoo! Mail has the best spam protection around
> http://mail.yahoo.com
-Chris

-- 
http://nondot.org/sabre/
http://llvm.org/