
<html><head><meta http-equiv="Content-Type" content="text/html charset=utf-8"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class=""><br class=""><div><blockquote type="cite" class=""><div class="">On Sep 4, 2015, at 10:23 AM, Matthias Braun via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org" class="">llvm-dev@lists.llvm.org</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><meta http-equiv="Content-Type" content="text/html charset=utf-8" class=""><div style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class=""><div class="">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 class=""><br class=""></div><div class="">- Matthias</div><br class=""><div class=""><blockquote type="cite" class=""><div class="">On Sep 3, 2015, at 10:45 AM, Natanael Ramos via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org" class="">llvm-dev@lists.llvm.org</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><div dir="ltr" class=""><div class="gmail_default" style="font-family:arial,helvetica,sans-serif">Hello to all LLVM Developers.<br class=""><br class=""></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 id="gt-src-p" class=""><span id="result_box" class="" lang="en"><span class="">According to the</span> <span class="">documentation</span><span class="">,</span> <span class="">currently the</span> <span class="">LLVM</span> <span class="">IR</span> <span class="">is</span> <span class="">in the</span> <span class="">SSA</span><span class=""> form, but I don't see</span> additional <span class="">information</span> <span class="">about <b class="">strict</b> SSA form</span><span class="">.<br class=""><br class=""></span></span></div><div id="gt-src-p" class=""><span id="result_box" class="" 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 class="">strict</b> SSA form are chordal and</span><span id="result_box" class="" lang="en"><span class=""> for those</span><span class="">, there are</span> <span class="">polynomial algorithms</span> <span class="">for the</span> <span class="">graph coloring</span><span class=""> (<a href="http://web.cs.ucla.edu/~palsberg/paper/aplas05.pdf" class="">http://web.cs.ucla.edu/~palsberg/paper/aplas05.pdf</a>).</span></span></div></div></div></div></blockquote></div></div></div></blockquote><div><br class=""></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 class=""></div><div>Like Matthias said, for reg alloc, we are not in strict SSA anymore.</div><div><br class=""></div><div>Q.</div><br class=""><blockquote type="cite" class=""><div class=""><div style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class=""><div class=""><blockquote type="cite" class=""><div class=""><div dir="ltr" class=""><div class="gmail_default" style="font-family:arial,helvetica,sans-serif"><div id="gt-src-p" class=""><span id="result_box" class="" lang="en"><span class=""></span></span></div></div><br class="">-- <br class=""><div class="gmail_signature">Natanael Ramos <br class="">Membro do corpo discente de Ciência da Computação pelo Instituto Federal de <br class="">Minas Gerais - Campus Formiga<br class=""><br class=""></div>

</div>

_______________________________________________<br class="">LLVM Developers mailing list<br class=""><a href="mailto:llvm-dev@lists.llvm.org" class="">llvm-dev@lists.llvm.org</a><br class=""><a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" class="">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><br class=""></div></blockquote></div><br class=""></div>_______________________________________________<br class="">LLVM Developers mailing list<br class=""><a href="mailto:llvm-dev@lists.llvm.org" class="">llvm-dev@lists.llvm.org</a><br class="">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev<br class=""></div></blockquote></div><br class=""></body></html>