<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40"><head><meta http-equiv=Content-Type content="text/html; charset=us-ascii"><meta name=Generator content="Microsoft Word 14 (filtered medium)"><style><!--
/* Font Definitions */
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
@font-face
{font-family:Tahoma;
panose-1:2 11 6 4 3 5 4 4 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0cm;
margin-bottom:.0001pt;
font-size:11.0pt;
font-family:"Calibri","sans-serif";}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:blue;
text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
{mso-style-priority:99;
color:purple;
text-decoration:underline;}
p.MsoListParagraph, li.MsoListParagraph, div.MsoListParagraph
{mso-style-priority:34;
margin-top:0cm;
margin-right:0cm;
margin-bottom:0cm;
margin-left:36.0pt;
margin-bottom:.0001pt;
font-size:11.0pt;
font-family:"Calibri","sans-serif";}
span.EmailStyle18
{mso-style-type:personal;
font-family:"Calibri","sans-serif";
color:windowtext;}
span.EmailStyle19
{mso-style-type:personal-reply;
font-family:"Calibri","sans-serif";
color:#1F497D;}
.MsoChpDefault
{mso-style-type:export-only;
font-size:10.0pt;}
@page WordSection1
{size:612.0pt 792.0pt;
margin:72.0pt 72.0pt 72.0pt 72.0pt;}
div.WordSection1
{page:WordSection1;}
--></style><!--[if gte mso 9]><xml>
<o:shapedefaults v:ext="edit" spidmax="1026" />
</xml><![endif]--><!--[if gte mso 9]><xml>
<o:shapelayout v:ext="edit">
<o:idmap v:ext="edit" data="1" />
</o:shapelayout></xml><![endif]--></head><body lang=EN-GB link=blue vlink=purple><div class=WordSection1><p class=MsoNormal><span style='color:#1F497D'>Hi Jonas,<o:p></o:p></span></p><p class=MsoNormal><span style='color:#1F497D'><o:p> </o:p></span></p><p class=MsoNormal><span style='color:#1F497D'>I think you may be facing a problem with the reduction order. I found out it is important and can affect the quality of the allocation, and with your case, it affects the allocability.<o:p></o:p></span></p><p class=MsoNormal><span style='color:#1F497D'><o:p> </o:p></span></p><p class=MsoNormal><span style='color:#1F497D'>With your example, I think the node should be pushed amongst the last nodes onto the reduction order list: spilling is not an option, so it is more constrained and should be allocated first. It should simply not have made it into the ConservativelyAllocatableNodes. It should have stayed into the NotProvablyAllocatableNodes set, and the SpillCostComparator will ensure it is on the top of the reduction list (because its spill cost is +inf).<o:p></o:p></span></p><p class=MsoNormal><span style='color:#1F497D'><o:p> </o:p></span></p><p class=MsoNormal><span style='color:#1F497D'>The logic using NodeMetadata::isConservativelyAllocatable should be tweaked to detect such nodes. This would take place in RegAllocSolverImpl, because the node costs cannot be accessed in NodeMetadata.<o:p></o:p></span></p><p class=MsoNormal><span style='color:#1F497D'><o:p> </o:p></span></p><p class=MsoNormal><span style='color:#1F497D'>Lang will probably be able to give a more educated answer than mine.<o:p></o:p></span></p><p class=MsoNormal><span style='color:#1F497D'><o:p> </o:p></span></p><p class=MsoNormal><span style='color:#1F497D'>Thanks for using PBQP !<o:p></o:p></span></p><p class=MsoNormal><span style='color:#1F497D'><o:p> </o:p></span></p><p class=MsoNormal><span style='color:#1F497D'>Cheers,<o:p></o:p></span></p><p class=MsoNormal><span style='color:#1F497D'>Arnaud<o:p></o:p></span></p><p class=MsoNormal><span style='color:#1F497D'><o:p> </o:p></span></p><div><div style='border:none;border-top:solid #B5C4DF 1.0pt;padding:3.0pt 0cm 0cm 0cm'><p class=MsoNormal style='margin-left:36.0pt'><b><span lang=EN-US style='font-size:10.0pt;font-family:"Tahoma","sans-serif"'>From:</span></b><span lang=EN-US style='font-size:10.0pt;font-family:"Tahoma","sans-serif"'> llvmdev-bounces@cs.uiuc.edu [mailto:llvmdev-bounces@cs.uiuc.edu] <b>On Behalf Of </b>Jonas Paulsson<br><b>Sent:</b> 26 January 2015 16:56<br><b>To:</b> llvmdev@cs.uiuc.edu; Lang Hames<br><b>Subject:</b> [LLVMdev] PBQP crash<o:p></o:p></span></p></div></div><p class=MsoNormal style='margin-left:36.0pt'><o:p> </o:p></p><p class=MsoNormal style='margin-left:36.0pt'><span lang=SV>Hi,<o:p></o:p></span></p><p class=MsoNormal style='margin-left:36.0pt'><span lang=SV><o:p> </o:p></span></p><p class=MsoNormal style='margin-left:36.0pt'><span lang=EN-US>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().<o:p></o:p></span></p><p class=MsoNormal style='margin-left:36.0pt'><span lang=EN-US><o:p> </o:p></span></p><p class=MsoNormal style='margin-left:36.0pt'><span lang=EN-US>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.<o:p></o:p></span></p><p class=MsoNormal style='margin-left:36.0pt'><span lang=EN-US><o:p> </o:p></span></p><p class=MsoNormal style='margin-left:36.0pt'><span lang=EN-US>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.<o:p></o:p></span></p><p class=MsoNormal style='margin-left:36.0pt'><span lang=EN-US>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.<o:p></o:p></span></p><p class=MsoNormal style='margin-left:36.0pt'><span lang=EN-US><o:p> </o:p></span></p><p class=MsoNormal style='margin-left:36.0pt'><span lang=EN-US>I wonder what has gone wrong here, and have some initial thoughts:<o:p></o:p></span></p><p class=MsoNormal style='margin-left:36.0pt'><span lang=EN-US><o:p> </o:p></span></p><p class=MsoNormal style='margin-left:36.0pt'><span lang=EN-US>* 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.<o:p></o:p></span></p><p class=MsoNormal style='margin-left:36.0pt'><span lang=EN-US> 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().<o:p></o:p></span></p><p class=MsoNormal style='margin-left:36.0pt'><span lang=EN-US>* 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.<o:p></o:p></span></p><p class=MsoNormal style='margin-left:36.0pt'><span lang=EN-US><o:p> </o:p></span></p><p class=MsoNormal style='margin-left:36.0pt'><span lang=EN-US>I would really appreciate some help and pointers on what might be going wrong here,<o:p></o:p></span></p><p class=MsoNormal style='margin-left:36.0pt'><span lang=EN-US><o:p> </o:p></span></p><p class=MsoNormal style='margin-left:36.0pt'><span lang=EN-US>Jonas Paulsson<o:p></o:p></span></p><p class=MsoNormal style='margin-left:36.0pt'><span lang=EN-US><o:p> </o:p></span></p></div></body></html>