[LLVMdev] PBQP & CalcSpillWeights

Wed Apr 11 07:16:45 PDT 2012

Hi Lang,

The assert is not triggered any longer on my testcases :)

I however still get my wrong allocation in some non trivial cases : the
pairing constraint is not fulfilled.

I have tried to modify the 'ensure pairable' pass (the pass undoing some
of the coalescer's work) to always insert register copies for
instructions with the pairable constraint, instead of being smart and
inserting the copy only when needed. This had no visible effect.
Although I am deriving from PBQPBuilder, the PBQP seems to be coalescing
some register copy, without taking into account that the source or dest
reg may have different constraints. In which part of pbqp would this be
happening ?

Cheers,
--
Arnaud de Grandmaison

On 04/05/2012 05:23 PM, Arnaud de Grandmaison wrote:
> Hi Lang,
>
> Thanks a lot for taking time to look into this. I will test the fix soon and 
> let you know the results.
>
> Cheers,
> --
> Arnaud de Grandmaison
>
> On Tuesday, April 03, 2012 17:30:33 Lang Hames wrote:
>> Hi Arnaud,
>>
>> Apologies for the delayed reply.
>>
>> Thank you for the excellent test case - it exposed a subtle bug in the
>> colorability heuristic. This has been fixed in r153958.
>>
>> In case you are curious, the bug was as follows: the PBQP solver applies
>> applies a simplification step to each matrix. When all elements of a matrix
>> row or column are equal, the value for those elements is "pushed out" to
>> the corresponding element of the cost vector, and the row/column is zeroed
>> out. This is an attempt to turn the matrices into zero matrices which can
>> be eliminated from the problem. This simplification step runs even for
>> rows/columns that are all infinite. When an all infinite row/column is
>> encountered, it will be zeroed out, and the infinite cost attached to some
>> register in the cost vector. Unfortunately the infinite-cost elements of
>> vectors were not being taken into consideration when determining
>> colorability, only the infinities in the matrices were. In your test case
>> this led to a node being falsely assumed to be colorable when it was not,
>> and pushed to the coloring stack too early. By the time it was encountered
>> in the coloring phase it had already been over-constrained, and no finite
>> cost solutions were available.
>>
>> In future I hope to make the simplification step strip infinite rows/columns
>> from the problem altogether (along with their corresponding vector
>> elements). This would speed the solver up further by avoiding consideration
>> of such impossible options.
>>
>> With the fix from r153958 applied the solver now finds a zero-cost solution
>> for the test case you sent me. This should translate to a valid register
>> allocation for your test case. Please try it out and let me know if it
>> works for you.
>>
>> Cheers,
>> Lang.
>>
>> On Tue, Mar 27, 2012 at 5:05 AM, Arnaud de Grandmaison
>> <arnaud.allarddegrandmaison at parrot.com<mailto:arnaud.allarddegrandmaison at pa
>> rrot.com>> wrote: Hi Lang,
>>
>> I have reduced the testcase as much as possible. The log of the run and the
>> dumped graphes are attached.
>>
>> Cheers,
>> --
>> Arnaud de Grandmaison
>>
>> On Tuesday, March 27, 2012 01:20:35 Lang Hames wrote:
>>> Hi Arnaud,
>>>
>>> Thanks for attaching those files. I'll take a look at them.
>>>
>>> Commit r153483 adds an option to the PBQP allocator,
>>> "-pbqp-dump-graphs", to dump the PBQP graph for each round of each
>>> function in a compilation unit. The generated files are named "<module
>>> id>.<function>.<round>.pbqpgraph", and contain a simple text
>>> representation of the PBQP graph. The PBQP allocator has been stable
>>> for some time - I think this patch should apply cleanly to the 3.0
>>> version.
>>>
>>> Can you run the failing test case through the allocator with this
>>> patch applied, passing the "-regalloc=pbqp -pbqp-dump-graphs
>>> -debug-only=regalloc" options. I'll need to take a look at the last
>>> graph dumped before the assertion is triggered.
>>>
>>> Cheers,
>>> Lang.
>>>
>>> On Mon, Mar 26, 2012 at 7:35 AM, Arnaud de Grandmaison
>>>
>>>
> <arnaud.allarddegrandmaison at parrot.com<mailto:arnaud.allarddegrandmaison at parrot.com>> 
> wrote:
>>>> Hi Lang,
>>>>
>>>>> From memory your target is not public, so I won't be able to
>>>>> reproduce
>>>>> the crash myself. Is that correct?
>>>> Correct.
>>>>
>>>>> If that's the case, I could add functionality to dump the PBQP
>>>>> graphs
>>>>> during allocation. I think they should give me enough information
>>>>> to
>>>>> debug the issue. Would you be able to share the PBQP graphs?
>>>> I can share the pbqp graph if you send me a patch with the added
>>>> functionality you want. On my side, I already checked the node cost
>>>> for
>>>> this register, which is correctly set to inf for spill, as well as
>>>> the
>>>> edge costs, and they look ok.
>>>>
>>>> I also attached my target's pbqp related file in case you want to
>>>> double check what I did. This is llvm-3.0 based. It comprises 2
>>>> passes : the FemtoPBQPBuilder, plus a FemtoPairablepass, which undo
>>>> some of the coalescer's work. The insertRegCopy may specifically
>>>> need a double check, as I am not 100% sure to have updated
>>>> correctly the LiveInterval information.
>>>>
>>>> In terms of registers, the Femto target is simplistic : a single
>>>> register
>>>> class GR16, for data and pointers, all i16. It has 16 registers, R0
>>>> to
>>>> R15; R15 is used as stack pointer, and R14 potentialy as
>>>> framepointer.
>>>> A pair is constituted from a register + its successor, i.e. (R0,
>>>> R1),
>>>> (R1,R2), (R2, R3), ... are valid pairs. This is an instruction
>>>> encoding
>>>> constraint, as we only have 16bits wide instructions. Pairs
>>>> involving
>>>> R15 are never allowed, those with R14 may be allowed, depending on
>>>> each
>>>> function.
>>>>
>>>> Most instructions have no pairing constraints, and do not appear
>>>> here,
>>>> being handled by the PBQPBuilder default base class. A few
>>>> instructions
>>>> have 1 or 2 pairs of registers, and are all handled by the 2 passes
>>>> above.
>>>>
>>>> Thanks for your help,
>>>> --
>>>> Arnaud de Grandmaison
>>>> Senior CPU engineer
>>>> Business Unit Digital Tuner
>>>>
>>>> Parrot S.A.
>>>> 174, quai de Jemmapes
>>>> 75010 Paris - France
>>>> Phone: +33 1 48 03 84 59<tel:%2B33%201%2048%2003%2084%2059>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>