Hi Arnaud,<div><br></div><div><div class="gmail_quote"><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="#606420"><div><div class="im">
<p class="MsoNormal"><font size="3" face="Times New Roman"><span style="font-size:12.0pt">> Hmm. Let me make sure I'm reading this right. The constraints are that:<br>
> a) All four operands have distinct registers.<u></u><u></u></span></font></p>
<p class="MsoNormal"><font size="3" face="Times New Roman"><span style="font-size:12.0pt">> b) The first two are in a consecutive pair (second > first)<u></u><u></u></span></font></p>
<p class="MsoNormal"><font size="3" face="Times New Roman"><span style="font-size:12.0pt">> c) The second two are in a consecutive pair (fourth > third)<u></u><u></u></span></font></p>
</div><p class="MsoNormal"><font size="2" color="#003366" face="Arial"><span style="font-size:10.0pt;font-family:Arial;color:#003366">Constraints b & c are OK, but a is too strict : “mpra %R0, %R1, %R0, %R1” is OK. But I though, may be wrongly, that “mpra %vreg1,
%vreg2, %vreg3, %vreg4” meant %vreg1 and %vreg3 will be allocated to different physical registers, or they would have been coalesced. For example, the pass I added after the coalescer ensures that instructions like “mpra %vreg1, %vreg2, %vreg1, %vreg4” (impossible
for pbqp to solve) is transformed to “mpra %vreg1, %vreg2, %vreg3, %vreg4” with the proper copy of %vreg1 to %vreg3 inserted.</span></font></p></div></div></blockquote><div><span class="Apple-style-span" style="font-family: Arial; font-size: 13px; "><br>
</span></div><div><span class="Apple-style-span" style="font-family: Arial; font-size: 13px; ">“mpra %vreg1, %vreg2, %vreg3, %vreg4” does not imply that vreg1 and vreg3 will be allocated different physical registers. It only says that they <i>can</i> (subject to constraints) be allocated different registers.</span></div>
<div><span class="Apple-style-span" style="color: rgb(0, 51, 102); font-family: Arial; font-size: 13px; "><br></span></div><div><span class="Apple-style-span" style="font-family: Arial; font-size: 13px; "><meta http-equiv="content-type" content="text/html; charset=utf-8">“mpra %vreg1, %vreg2, %vreg1, %vreg4” is not impossible for PBQP to solve. Provided you have added the pairing constraint between vreg1 & vreg2, and between vreg1 & vreg4, this simply means that the constraints will force vreg2 and vreg4 to be allocated the same physical register. The PBQP allocator will always generate something like "mpra RX, RY, RX, RY" for this set of vreg operands.</span></div>
<div><span class="Apple-style-span" style="font-family: Arial; font-size: 13px; "><br></span></div><div><span class="Apple-style-span" style="font-family: Arial; font-size: 13px; ">By inserting the copy from %vreg1 to %vreg3 you have relaxed the problem for PBQP: It can allocate the same register to %vreg1 and %vreg3, or it can allocate different ones.</span></div>
<div><span class="Apple-style-span" style="font-family: Arial; font-size: 13px; "><br></span></div><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="#606420">
<div><div class="im">
<p class="MsoNormal"><font size="3" face="Times New Roman"><span style="font-size:12.0pt">>That said my understanding of your pairing constraints would definitely prohibit </span></font><span><font size="2" face="Arial"><span style="font-size:10.0pt;font-family:Arial">mpra
%R0, %R2, %R1, %R3 under any circumstances, even with out the<u></u><u></u></span></font></span></p>
<p class="MsoNormal"><span><font size="2" face="Arial"><span style="font-size:10.0pt;font-family:Arial">> distinction constraint. Either I've misunderstood your constraints, or there is a bug somewhere.</span></font></span><font size="2" color="navy" face="Arial"><span style="font-size:10.0pt;font-family:Arial;color:navy"><u></u><u></u></span></font></p>
</div><div>
<p class="MsoNormal"><font size="2" color="#003366" face="Arial"><span style="font-size:10.0pt;font-family:Arial;color:#003366">You got the contraints right. I was surprised to have to add a “safety net” to prevent the impossible case; at first I though pbqp
could “backtrack” once it discovers it gets to an impossible case… My backend is private, so I can not share it.</span></font><span class="Apple-style-span" style="color: rgb(0, 51, 102); font-family: Arial; font-size: 13px; "> </span></p>
</div></div></div></blockquote><div><br></div><div>The PBQP allocator currently does not do any backtracking. The "backpropagation" phase, which some people mistake for backtracking, is actually just the graph reconstruction/coloring phase (equivalent to the "select" phase of a graph coloring allocator).</div>
<div> </div><div>I am very surprised to hear that the allocator does generate cases like "<span class="Apple-style-span" style="font-family: Arial; font-size: 13px; ">mpra %R0, %R2, %R1, %R3". It is possible that there is a bug in the solver, but in my experience the source of most bugs is the constraint matrices. Have you put infinite costs on the spill option of the pairing constraint? E.g.</span></div>
<div><span class="Apple-style-span" style="font-family: Arial; font-size: 13px; "><br></span></div><div><span class="Apple-style-span" style="font-size: 13px; "><font class="Apple-style-span" face="'courier new', monospace"> SP R0 R1 R2 R3</font></span></div>
<div><span class="Apple-style-span" style="font-size: 13px; "><font class="Apple-style-span" face="'courier new', monospace">SP I I I I I</font></span></div><div><span class="Apple-style-span" style="font-size: 13px; "><font class="Apple-style-span" face="'courier new', monospace">R0 I I 0 I I</font></span></div>
<div><span class="Apple-style-span" style="font-size: 13px; "><font class="Apple-style-span" face="'courier new', monospace">R1 I I I 0 I</font></span></div><div><span class="Apple-style-span" style="font-size: 13px; "><font class="Apple-style-span" face="'courier new', monospace">R2 I I I I 0</font></span></div>
<div><span class="Apple-style-span" style="font-size: 13px; "><font class="Apple-style-span" face="'courier new', monospace">R3 I 0 I I I</font></span></div><meta http-equiv="content-type" content="text/html; charset=utf-8"><div>
<br></div><div>If that's the case then an unfortunate combination of vreg uses in more than on mpra instruction could cause the situation you're seeing. Consider:</div><div><br></div><div>mpra %vreg0, %vreg1, %vreg2, %vreg3</div>
<div>mpra %vreg0, %vreg2, %vreg1, %vreg3</div><div><br></div><div>With this sequence there is no way the PBQP allocator can construct a correct solution (i.e one with finite costs).</div><div><br></div><div>The solution is to remove the infinities from the spill option on the pairing matrix:</div>
<div><br></div><div><meta http-equiv="content-type" content="text/html; charset=utf-8"><div><span class="Apple-style-span" style="font-size: 13px; "><font class="Apple-style-span" face="'courier new', monospace"> SP R0 R1 R2 R3</font></span></div>
<div><span class="Apple-style-span" style="font-size: 13px; "><font class="Apple-style-span" face="'courier new', monospace">SP 0 0 0 0 0</font></span></div><div><span class="Apple-style-span" style="font-size: 13px; "><font class="Apple-style-span" face="'courier new', monospace">R0 0 I 0 I I</font></span></div>
<div><span class="Apple-style-span" style="font-size: 13px; "><font class="Apple-style-span" face="'courier new', monospace">R1 0 I I 0 I</font></span></div><div><span class="Apple-style-span" style="font-size: 13px; "><font class="Apple-style-span" face="'courier new', monospace">R2 0 I I I 0</font></span></div>
<div><span class="Apple-style-span" style="font-size: 13px; "><font class="Apple-style-span" face="'courier new', monospace">R3 0 0 I I I</font></span></div></div><div><span class="Apple-style-span" style="font-size: 13px; "><font class="Apple-style-span" face="'courier new', monospace"><br>
</font></span></div><div>This will allow the allocator to spill as necessary in order to find a correct allocation. </div><div> </div><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="#606420"><div><div><p class="MsoNormal"><font size="2" color="#003366" face="Arial"><span style="font-size:10.0pt;font-family:Arial;color:#003366">I will trace what’s happening with
</span></font><font size="2" color="#003366" face="Arial"><span style="font-size:10.0pt;font-family:Arial;color:#003366">vregsToAlloc and keep you updated.</span></font></p></div></div></div></blockquote><div><br></div><div>
Thank you. I will be interested to know what your investigations turn up.</div><div><br></div><div>Regards,</div><div>Lang.</div></div></div>