[LLVMdev] Possible bug in the linear scan register allocator

[Chris Lattner]

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/