<html>
<head>
<meta content="text/html; charset=ISO-8859-1"
http-equiv="Content-Type">
</head>
<body bgcolor="#FFFFFF" text="#000000">
Hi Lang,<br>
<br>
Thanks for proposing to look into this testcase.<br>
<br>
Regarding the copies, this was done to be on the safe side. I would
normally only insert copies where needed in order to express the
pairable constraint. For example, in a case like 'instr %vreg1,
%vreg2, %vreg1', I need to insert a %vreg1 copy in order to express
the pairing constraint between the first and third arguments of
instr.<br>
<br>
Cheers,<br>
--<br>
Arnaud<br>
<br>
On 04/19/2012 02:32 AM, Lang Hames wrote:
<blockquote
cite="mid:CALLttgquxghVMY3H0NBfUQcarT_4Ya9H9WJWRAnjokQrfZqCyg@mail.gmail.com"
type="cite">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 moz-do-not-send="true"
href="mailto:arnaud.allarddegrandmaison@parrot.com">arnaud.allarddegrandmaison@parrot.com</a><mailto:<a
moz-do-not-send="true"
href="mailto:arnaud.allarddegrandmaison@pa">arnaud.allarddegrandmaison@pa</a><br>
>> <a moz-do-not-send="true"
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 moz-do-not-send="true"
href="mailto:arnaud.allarddegrandmaison@parrot.com">arnaud.allarddegrandmaison@parrot.com</a><mailto:<a
moz-do-not-send="true"
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 moz-do-not-send="true"
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 moz-do-not-send="true"
href="mailto:LLVMdev@cs.uiuc.edu">LLVMdev@cs.uiuc.edu</a>
<a moz-do-not-send="true"
href="http://llvm.cs.uiuc.edu" target="_blank">http://llvm.cs.uiuc.edu</a><br>
> <a moz-do-not-send="true"
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>
</blockquote>
<br>
<br>
<pre class="moz-signature" cols="72">--
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</pre>
</body>
</html>