<div dir="ltr">Hi Jonas,<div><br></div><div><span style="font-family:Calibri,sans-serif;font-size:15px">> * The problematic node that was spilled again, was in the ConservativelyAllocatableNodes set during reduce(). The comment in reduce() “Conservatively allocatable nodes will never spill…” indicates that perhaps this is an incorrect insertion, as the regs did in fact run out in this case.</span><br></div><div><span style="font-family:Calibri,sans-serif;font-size:15px"><br></span></div><div><font face="Calibri, sans-serif"><span style="font-size:15px">Arnaud is correct: A node should never be put into the conservatively allocatable list if there is a chance of it spilling. Off the top of my head I can imagine 2 things going wrong here:</span></font></div><div><font face="Calibri, sans-serif"><span style="font-size:15px"><br></span></font></div><div><font face="Calibri, sans-serif"><span style="font-size:15px">(1) Conservative allocability is mostly-precomputed, and updated with deltas as nodes are removed. It is possible that there is some subtle bug in this code.</span></font></div><div><font face="Calibri, sans-serif"><span style="font-size:15px"><br></span></font></div><div><font face="Calibri, sans-serif"><span style="font-size:15px">(2) I think the current conservative allocability test bakes in the assumption that all register options have non-infinite cost. If you assign infinite costs to any physical register I would expect this to blow up.</span></font></div><div><br></div><div><font face="Calibri, sans-serif"><span style="font-size:15px">Are you able to share a test case at all? If so that would be great. If not, I can add an option to the allocator to dump abstract PBQP graphs, and I could use these to test the problem on my end.</span></font></div><div><font face="Calibri, sans-serif"><span style="font-size:15px"><br></span></font></div><div><font face="Calibri, sans-serif"><span style="font-size:15px">Regards,</span></font></div><div><font face="Calibri, sans-serif"><span style="font-size:15px">Lang.</span></font></div><div><font face="Calibri, sans-serif"><span style="font-size:15px"><br></span></font></div></div><div class="gmail_extra"><br><div class="gmail_quote">On Mon, Jan 26, 2015 at 7:55 AM, Jonas Paulsson <span dir="ltr"><<a href="mailto:jonas.paulsson@ericsson.com" target="_blank">jonas.paulsson@ericsson.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">





<div lang="EN-US" link="blue" vlink="purple">
<div>
<p class="MsoNormal"><span lang="SV">Hi,<u></u><u></u></span></p>
<p class="MsoNormal"><span lang="SV"><u></u> <u></u></span></p>
<p class="MsoNormal">I have run into a test case on an out-of-tree target where PBQP fails to complete register allocation after “Attempting to spill already spilled value” (the triggered assert in InlineSpiller::spill().<u></u><u></u></p>
<p class="MsoNormal"><u></u> <u></u></p>
<p class="MsoNormal">First, the original LiveInterval is spilled. It is a load of a symbol into a narrow register class, i.e. a subset of the class of address registers. InlineSpiller decides to rematerialize the load of the symbol to lie right before its only
 user, which makes good sense. The original def is removed.<u></u><u></u></p>
<p class="MsoNormal"><u></u> <u></u></p>
<p class="MsoNormal">The new LiveInterval pushed is thus much smaller in the next PBQP round. The spill cost is marked as ‘inf’ during graph building. This small interval has also a lot of overlapping intervals and thus edges in the PBQP graph. It gets pushed
 on the node stack to later be popped after 17 others.<u></u><u></u></p>
<p class="MsoNormal">Those 17 nodes use up all registers of the narrow reg-class, and the cost vector has become all infinities. Spill option is selected again, and thus the error is a fact of spilling an already spilled value.<u></u><u></u></p>
<p class="MsoNormal"><u></u> <u></u></p>
<p class="MsoNormal">I wonder what has gone wrong here, and have some initial thoughts:<u></u><u></u></p>
<p class="MsoNormal"><u></u> <u></u></p>
<p class="MsoNormal">* The problematic node that was spilled again, was in the ConservativelyAllocatableNodes set during reduce(). The comment in reduce() “Conservatively allocatable nodes will never spill…” indicates that perhaps this is an incorrect insertion,
 as the regs did in fact run out in this case.<u></u><u></u></p>
<p class="MsoNormal">   In setup(), the node is first put into not-provably-allocatables. However, one of it’s neigbhour invoked handleDisconnectEdge(), and moves it into conservatively-allocatables, because DeniedOpts had become less than NumOpts (in isConservativelyAllocatable().<u></u><u></u></p>
<p class="MsoNormal">* There are lots of spillable nodes being popped before the one that can’t be spilled.  This seems intuitively wrong, as they are intervals that actually could be spilled.<u></u><u></u></p>
<p class="MsoNormal"><u></u> <u></u></p>
<p class="MsoNormal">I would really appreciate some help and pointers on what might be going wrong here,<span class="HOEnZb"><font color="#888888"><u></u><u></u></font></span></p><span class="HOEnZb"><font color="#888888">
<p class="MsoNormal"><u></u> <u></u></p>
<p class="MsoNormal">Jonas Paulsson<u></u><u></u></p>
<p class="MsoNormal"><u></u> <u></u></p>
</font></span></div>
</div>

</blockquote></div><br></div>