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