<div dir="ltr"><div class="gmail_extra"><div class="gmail_quote"><br>> The underlying liveness datastructure is a list of ranges where each vreg is alive</div><div class="gmail_quote">> (ranges in terms of instructions numbered). I remember a couple of later linear scan</div><div class="gmail_quote">> papers describing the same thing (Traub <a href="http://et.al">et.al</a>. being the first if I remember correctly).</div><div class="gmail_quote">> That should be as accurate as you can get in terms of liveness information.<div><br></div><div>It depends on the details.</div><div>For example, given</div><div><br></div></div></div><blockquote style="margin:0 0 0 40px;border:none;padding:0px"><div class="gmail_extra"><div class="gmail_quote"><div><font face="monospace, monospace">t0 = mumble</font></div></div></div></blockquote><blockquote style="margin:0 0 0 40px;border:none;padding:0px"><div class="gmail_extra"><div class="gmail_quote"><div><font face="monospace, monospace">if (something) {</font></div></div></div><div class="gmail_extra"><div class="gmail_quote"><div><font face="monospace, monospace"> t2 = 3</font></div></div></div><div class="gmail_extra"><div class="gmail_quote"><div><font face="monospace, monospace">}</font></div></div></div><div class="gmail_extra"><div class="gmail_quote"><div><font face="monospace, monospace">else {</font></div></div></div><div class="gmail_extra"><div class="gmail_quote"><div><font face="monospace, monospace"> t3 = t0 + 3</font></div></div></div><div class="gmail_extra"><div class="gmail_quote"><div><font face="monospace, monospace"> print t0</font></div></div></div><div class="gmail_extra"><div class="gmail_quote"><div><font face="monospace, monospace">}</font></div></div></div><div class="gmail_extra"><div class="gmail_quote"><div><font face="monospace, monospace">t4 = phi(t2, t3)</font></div></div></div></blockquote><div class="gmail_extra"><div class="gmail_quote"><div><br></div><div>it's clear that t2 and t0 shouldn't interfere,</div><div>but some folks might say the ranges overlap.</div><div><br></div><div>Similarly,</div><div><br></div></div></div><blockquote style="margin:0 0 0 40px;border:none;padding:0px"><div class="gmail_extra"><div class="gmail_quote"><div><font face="monospace, monospace">t6 = mumble</font></div></div></div><div class="gmail_extra"><div class="gmail_quote"><div><font face="monospace, monospace">t7 = t6</font></div></div></div><div class="gmail_extra"><div class="gmail_quote"><div><font face="monospace, monospace">t8 = t6 + 5</font></div></div></div><div class="gmail_extra"><div class="gmail_quote"><div><font face="monospace, monospace">t9 = t7 + 10</font></div></div></div><div class="gmail_extra"><div class="gmail_quote"><div><font face="monospace, monospace">print t8, t9</font></div></div></div></blockquote><div class="gmail_extra"><div class="gmail_quote"><div><br></div><div>Chaitin points out that t6 and t7 shouldn't interfere,</div><div>even though the live ranges overlap.</div><div><br></div><div>Anyway, I'll look at the links.</div><div><br></div><div>Thanks,</div><div>Preston</div><div><br></div><div><br></div><div><br></div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div style="word-wrap:break-word;line-break:after-white-space"><div><div><br></div><div>We have separate aggressive coalescing pass before allocation. The register allocator will later perform live range splitting inside the main allocation loop as it seems fit.</div><span class=""><div><br></div><blockquote type="cite"><div><div dir="ltr"><div><br></div><div>I ask these questions because we (guys I work with) see loops</div><div>where there's a little register juggling that seems unnecessary.</div></div></div></blockquote></span><div>Well your best bet is to learn reading the output of `-mllvm -print-machineinstrs -mllvm -debug-only=regalloc` (which can take a while)...</div><span class=""><br><blockquote type="cite"><div><div dir="ltr"><div><br></div><div>Is there a paper that describes what y'all do?</div></div></div></blockquote><div><br></div></span><div>I'm only aware of a blog post:</div><div><a href="http://blog.llvm.org/2011/09/greedy-register-allocation-in-llvm-30.html" target="_blank">http://blog.llvm.org/2011/09/<wbr>greedy-register-allocation-in-<wbr>llvm-30.html</a></div><div>and a dev conference talk in 2011:</div><div><a href="https://llvm.org/devmtg/2011-11/" target="_blank">https://llvm.org/devmtg/2011-<wbr>11/</a></div><span class="HOEnZb"><font color="#888888"><div><br></div><div>- Matthias</div></font></span><span class=""><div><br></div><blockquote type="cite"><div><div dir="ltr"><div><br></div><div>Thanks,</div><div>Preston</div><div><br></div></div><div class="gmail_extra"><br><div class="gmail_quote">On Mon, Sep 10, 2018 at 9:57 AM, Matthias Braun <span dir="ltr"><<a href="mailto:mbraun@apple.com" target="_blank">mbraun@apple.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div style="word-wrap:break-word;line-break:after-white-space">I would not describe LLVMs register allocator as linear scan, it's closer to graph coloring than linear scan IMO (though doesn't really matcher either approach).<div><br></div><div>RegAllocGreedy assigns the registers in an order based on the priority value computed in enqueu() we are not just scanning from top to bottom of the program. We also perform actual interference checks we just don't happen to build up an explicit interference graph up front.</div><div><br></div><div>- Matthias</div><div><br></div><div><div><div><blockquote type="cite"><div><div class="m_-4050234212288967131h5"><div>On Sep 10, 2018, at 9:49 AM, Preston Briggs via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>> wrote:</div><br class="m_-4050234212288967131m_-5434489890348760605Apple-interchange-newline"></div></div><div><div><div class="m_-4050234212288967131h5"><div dir="ltr">Why have we ended up using linear-scan register allocation<div><span style="color:rgb(34,34,34);font-family:arial,sans-serif;font-size:12.8px;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial;float:none;display:inline">by default (instead of, e.g., coloring)?</span><div style="color:rgb(34,34,34);font-family:arial,sans-serif;font-size:12.8px;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial"><br></div><div style="color:rgb(34,34,34);font-family:arial,sans-serif;font-size:12.8px;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial">Thanks,</div><div style="color:rgb(34,34,34);font-family:arial,sans-serif;font-size:12.8px;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial">Preston</div><div class="m_-4050234212288967131m_-5434489890348760605gmail-yj6qo" style="color:rgb(34,34,34);font-family:arial,sans-serif;font-size:12.8px;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial"></div><br class="m_-4050234212288967131m_-5434489890348760605gmail-Apple-interchange-newline"></div><br></div></div></div>
______________________________<wbr>_________________<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/<wbr>mailman/listinfo/llvm-dev</a><br></div></blockquote></div><br></div></div></div></blockquote></div><br></div>
</div></blockquote></span></div><br></div></blockquote></div><br></div></div>