<p dir="ltr">Thanks for your answers. </p>
<p dir="ltr">Yes, coloring can be done in polinomial time, but spilling and Coalescing are still NP. </p>
<div class="gmail_quote">Em 04/09/2015 2:35 PM, "Quentin Colombet" <<a href="mailto:qcolombet@apple.com">qcolombet@apple.com</a>> escreveu:<br type="attribution"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div style="word-wrap:break-word"><br><div><blockquote type="cite"><div>On Sep 4, 2015, at 10:23 AM, Matthias Braun via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>> wrote:</div><br><div><div style="word-wrap:break-word"><div>LLVM has multiple intermediate representations. Before register allocation llvm IR is translated into the representation most often called machine IR (MIR) which is in strict SSA form for some passes but is then lowered to non SSA form in the PHIElimination and TwoAddressInstruction passes.</div><div><br></div><div>- Matthias</div><br><div><blockquote type="cite"><div>On Sep 3, 2015, at 10:45 AM, Natanael Ramos via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>> wrote:</div><br><div><div dir="ltr"><div class="gmail_default" style="font-family:arial,helvetica,sans-serif">Hello to all LLVM Developers.<br><br></div><div class="gmail_default" style="font-family:arial,helvetica,sans-serif">The LLVM IR is in strict SSA form (i.e. every variable is defined before it is used along every path from the entry to exit point)?<div><span lang="en"><span>According to the</span> <span>documentation</span><span>,</span> <span>currently the</span> <span>LLVM</span> <span>IR</span> <span>is</span> <span>in the</span> <span>SSA</span><span> form, but I don't see</span> additional <span>information</span> <span>about <b>strict</b> SSA form</span><span>.<br><br></span></span></div><div><span lang="en">The strict SSA form provide opportunities of optimization in register allocation, because is proved that all interference graphs of the IR in <b>strict</b> SSA form are chordal and</span><span lang="en"><span> for those</span><span>, there are</span> <span>polynomial algorithms</span> <span>for the</span> <span>graph coloring</span><span> (<a href="http://web.cs.ucla.edu/~palsberg/paper/aplas05.pdf" target="_blank">http://web.cs.ucla.edu/~palsberg/paper/aplas05.pdf</a>).</span></span></div></div></div></div></blockquote></div></div></div></blockquote><div><br></div><div>This is true only when you set aside the hardware constraints IIRC.</div><div>Anyway, the hard part in the allocator is spilling and coalescing, not coloring.</div><div><br></div><div>Like Matthias said, for reg alloc, we are not in strict SSA anymore.</div><div><br></div><div>Q.</div><br><blockquote type="cite"><div><div style="word-wrap:break-word"><div><blockquote type="cite"><div><div dir="ltr"><div class="gmail_default" style="font-family:arial,helvetica,sans-serif"><div><span lang="en"><span></span></span></div></div><br>-- <br><div>Natanael Ramos <br>Membro do corpo discente de Ciência da Computação pelo Instituto Federal de <br>Minas Gerais - Campus Formiga<br><br></div>
</div>
_______________________________________________<br>LLVM Developers mailing list<br><a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a><br><a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" target="_blank">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><br></div></blockquote></div><br></div>_______________________________________________<br>LLVM Developers mailing list<br><a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a><br><a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" target="_blank">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><br></div></blockquote></div><br></div></blockquote></div>