<html><head><meta http-equiv="Content-Type" content="text/html; charset=us-ascii"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" class=""><br class=""><div><br class=""><blockquote type="cite" class=""><div class="">On Sep 10, 2018, at 5:11 PM, Preston Briggs <<a href="mailto:preston.briggs@gmail.com" class="">preston.briggs@gmail.com</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><div dir="ltr" class="">The phi instruction is irrelevant; just the way I think about things.<div class="">The question is if the allocator believes that t0 and t2 interfere.<br class=""><div class=""><br class=""></div><div class="">Perhaps the coalescing example was too simple.</div><div class="">In the general case, we can't coalesce without a notion of interference.</div><div class="">My worry is that looking at interference by ranges of instruction numbers</div><div class="">leads to inaccuracies when a range is introduced by a copy.</div></div></div></div></blockquote><div><br class=""></div><div>I can't think of a case where we wouldn't have the same accuracy as a graph coloring allocator.</div><div>If you can construct an example where we don't I'd love to hear about it.</div><div><br class=""></div><div>If you wonder about the liveness information, you can perform experiments like this (I'm using a NOOP instruction with an implicit use operand to produce some artificial uses).</div><div><br class=""></div><div>$ cat test.mir</div><div><div><div>name: somefunc</div><div>body: |</div><div> bb.0:</div><div> %0:gr32 = MOV32ri 42</div><div> JB_1 %bb.2, undef implicit $eflags</div><div> JMP_1 %bb.2</div><div><br class=""></div><div> bb.1:</div><div> %1:gr32 = MOV32ri 17</div><div> JMP_1 %bb.3</div><div><br class=""></div><div> bb.2:</div><div> NOOP implicit %0</div><div> %1 = COPY %0</div><div> JMP_1 %bb.3</div><div><br class=""></div><div> bb.3:</div><div> NOOP implicit %1</div><div><br class=""></div><div><br class=""></div><div><br class=""></div></div><div>$ llc -run-pass=liveintervals -debug-only=regalloc test.mir</div><div><div><div>********** INTERVALS **********</div><div>%0 [16r,64B:0)[112B,144r:0) 0@16r weight:0.000000e+00</div><div>%1 [80r,112B:1)[144r,176B:0)[176B,192r:2) 0@144r 1@80r 2@176B-phi weight:0.000000e+00</div><div>RegMasks:</div><div>********** MACHINEINSTRS **********</div><div># Machine code for function somefunc: NoPHIs</div><div><br class=""></div><div>0B<span class="Apple-tab-span" style="white-space:pre"> </span>bb.0:</div><div><span class="Apple-tab-span" style="white-space:pre"> </span> successors: %bb.2(0x80000000); %bb.2(100.00%)</div><div><br class=""></div><div>16B<span class="Apple-tab-span" style="white-space:pre"> </span> %0:gr32 = MOV32ri 42</div><div>32B<span class="Apple-tab-span" style="white-space:pre"> </span> JB_1 %bb.2, implicit undef $eflags</div><div>48B<span class="Apple-tab-span" style="white-space:pre"> </span> JMP_1 %bb.2</div><div><br class=""></div><div>64B<span class="Apple-tab-span" style="white-space:pre"> </span>bb.1:</div><div><span class="Apple-tab-span" style="white-space:pre"> </span> successors: %bb.3(0x80000000); %bb.3(100.00%)</div><div><br class=""></div><div>80B<span class="Apple-tab-span" style="white-space:pre"> </span> %1:gr32 = MOV32ri 17</div><div>96B<span class="Apple-tab-span" style="white-space:pre"> </span> JMP_1 %bb.3</div><div><br class=""></div><div>112B<span class="Apple-tab-span" style="white-space:pre"> </span>bb.2:</div><div><span class="Apple-tab-span" style="white-space:pre"> </span>; predecessors: %bb.0</div><div><span class="Apple-tab-span" style="white-space:pre"> </span> successors: %bb.3(0x80000000); %bb.3(100.00%)</div><div><br class=""></div><div>128B<span class="Apple-tab-span" style="white-space:pre"> </span> NOOP implicit %0:gr32</div><div>144B<span class="Apple-tab-span" style="white-space:pre"> </span> %1:gr32 = COPY %0:gr32</div><div>160B<span class="Apple-tab-span" style="white-space:pre"> </span> JMP_1 %bb.3</div><div><br class=""></div><div>176B<span class="Apple-tab-span" style="white-space:pre"> </span>bb.3:</div><div><span class="Apple-tab-span" style="white-space:pre"> </span>; predecessors: %bb.1, %bb.2</div><div><br class=""></div><div>192B<span class="Apple-tab-span" style="white-space:pre"> </span> NOOP implicit %1:gr32</div><div><br class=""></div><div># End machine code for function somefunc.</div></div><div><br class=""></div><div><br class=""></div><div>If you look at the "intervals" (the class is a misnomer since nowadays it contains a list of ranges...) in the beginning you see that %0 and %1 do not overlap anywhere.</div><div><br class=""></div><div>- Matthias</div></div></div><div><br class=""></div><blockquote type="cite" class=""><div class=""><div dir="ltr" class=""><div class=""><div class=""><br class=""></div><div class="">But perhaps I should focus on the links and, as you suggested,</div><div class="">the debugging info.</div><div class=""><br class=""></div><div class="">Thanks,</div><div class="">Preston</div><div class=""><br class=""></div><div class=""><br class=""></div><div class=""><br class=""></div></div></div><div class="gmail_extra"><br class=""><div class="gmail_quote">On Mon, Sep 10, 2018 at 5:02 PM, Matthias Braun <span dir="ltr" class=""><<a href="mailto:mbraun@apple.com" target="_blank" class="">mbraun@apple.com</a>></span> wrote:<br class=""><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" class=""><br class=""><div class=""><span class=""><br class=""><blockquote type="cite" class=""><div class="">On Sep 10, 2018, at 4:53 PM, Preston Briggs <<a href="mailto:preston.briggs@gmail.com" target="_blank" class="">preston.briggs@gmail.com</a>> wrote:</div><br class="m_5435089598488578425Apple-interchange-newline"><div class=""><div dir="ltr" class=""><div class="gmail_extra"><div class="gmail_quote"><br class="">> 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/" target="_blank" class="">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 class=""><br class=""></div><div class="">It depends on the details.</div><div class="">For example, given</div><div class=""><br class=""></div></div></div><blockquote style="margin:0 0 0 40px;border:none;padding:0px" class=""><div class="gmail_extra"><div class="gmail_quote"><div class=""><font face="monospace, monospace" class="">t0 = mumble</font></div></div></div></blockquote><blockquote style="margin:0 0 0 40px;border:none;padding:0px" class=""><div class="gmail_extra"><div class="gmail_quote"><div class=""><font face="monospace, monospace" class="">if (something) {</font></div></div></div><div class="gmail_extra"><div class="gmail_quote"><div class=""><font face="monospace, monospace" class=""> t2 = 3</font></div></div></div><div class="gmail_extra"><div class="gmail_quote"><div class=""><font face="monospace, monospace" class="">}</font></div></div></div><div class="gmail_extra"><div class="gmail_quote"><div class=""><font face="monospace, monospace" class="">else {</font></div></div></div><div class="gmail_extra"><div class="gmail_quote"><div class=""><font face="monospace, monospace" class=""> t3 = t0 + 3</font></div></div></div><div class="gmail_extra"><div class="gmail_quote"><div class=""><font face="monospace, monospace" class=""> print t0</font></div></div></div><div class="gmail_extra"><div class="gmail_quote"><div class=""><font face="monospace, monospace" class="">}</font></div></div></div><div class="gmail_extra"><div class="gmail_quote"><div class=""><font face="monospace, monospace" class="">t4 = phi(t2, t3)</font></div></div></div></blockquote><div class="gmail_extra"><div class="gmail_quote"><div class=""><br class=""></div><div class="">it's clear that t2 and t0 shouldn't interfere,</div><div class="">but some folks might say the ranges overlap.</div></div></div></div></div></blockquote><blockquote type="cite" class=""><div class=""><div dir="ltr" class=""><div class="gmail_extra"><div class="gmail_quote"><div class=""><br class=""></div><div class="">Similarly,</div><div class=""><br class=""></div></div></div><blockquote style="margin:0 0 0 40px;border:none;padding:0px" class=""><div class="gmail_extra"><div class="gmail_quote"><div class=""><font face="monospace, monospace" class="">t6 = mumble</font></div></div></div><div class="gmail_extra"><div class="gmail_quote"><div class=""><font face="monospace, monospace" class="">t7 = t6</font></div></div></div><div class="gmail_extra"><div class="gmail_quote"><div class=""><font face="monospace, monospace" class="">t8 = t6 + 5</font></div></div></div><div class="gmail_extra"><div class="gmail_quote"><div class=""><font face="monospace, monospace" class="">t9 = t7 + 10</font></div></div></div><div class="gmail_extra"><div class="gmail_quote"><div class=""><font face="monospace, monospace" class="">print t8, t9</font></div></div></div></blockquote><div class="gmail_extra"><div class="gmail_quote"><div class=""><br class=""></div><div class="">Chaitin points out that t6 and t7 shouldn't interfere,</div><div class="">even though the live ranges overlap.</div></div></div></div></div></blockquote></span><div class=""><div class="">- We go out of SSA form before allocating registers so you won't see phi instruction.</div><div class="">- In the second case the copy coalesceing pass should have coalesced t6 and t7.</div><div class=""><br class=""></div><div class="">I would expect both cases to work as you expect.</div><span class="HOEnZb"><font color="#888888" class=""><div class=""><br class=""></div><div class="">- Matthias</div><blockquote type="cite" class=""><div dir="ltr" class=""><div class="gmail_extra"><div class="gmail_quote"></div></div></div></blockquote></font></span></div><div class=""><div class="h5"><br class=""><blockquote type="cite" class=""><div class=""><div dir="ltr" class=""><div class="gmail_extra"><div class="gmail_quote"><div class=""><br class=""></div><div class="">Anyway, I'll look at the links.</div><div class=""><br class=""></div><div class="">Thanks,</div><div class="">Preston</div><div class=""><br class=""></div><div class=""><br class=""></div><div class=""><br class=""></div><div class=""> </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" class=""><div class=""><div class=""><br class=""></div><div class="">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 class=""><br class=""></div><blockquote type="cite" class=""><div class=""><div dir="ltr" class=""><div class=""><br class=""></div><div class="">I ask these questions because we (guys I work with) see loops</div><div class="">where there's a little register juggling that seems unnecessary.</div></div></div></blockquote></span><div class="">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 class=""><blockquote type="cite" class=""><div class=""><div dir="ltr" class=""><div class=""><br class=""></div><div class="">Is there a paper that describes what y'all do?</div></div></div></blockquote><div class=""><br class=""></div></span><div class="">I'm only aware of a blog post:</div><div class=""><a href="http://blog.llvm.org/2011/09/greedy-register-allocation-in-llvm-30.html" target="_blank" class="">http://blog.llvm.org/2011/09/g<wbr class="">reedy-register-allocation-in-l<wbr class="">lvm-30.html</a></div><div class="">and a dev conference talk in 2011:</div><div class=""><a href="https://llvm.org/devmtg/2011-11/" target="_blank" class="">https://llvm.org/devmtg/2011-1<wbr class="">1/</a></div><span class="m_5435089598488578425HOEnZb"><font color="#888888" class=""><div class=""><br class=""></div><div class="">- Matthias</div></font></span><span class=""><div class=""><br class=""></div><blockquote type="cite" class=""><div class=""><div dir="ltr" class=""><div class=""><br class=""></div><div class="">Thanks,</div><div class="">Preston</div><div class=""><br class=""></div></div><div class="gmail_extra"><br class=""><div class="gmail_quote">On Mon, Sep 10, 2018 at 9:57 AM, Matthias Braun <span dir="ltr" class=""><<a href="mailto:mbraun@apple.com" target="_blank" class="">mbraun@apple.com</a>></span> wrote:<br class=""><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" class="">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 class=""><br class=""></div><div class="">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 class=""><br class=""></div><div class="">- Matthias</div><div class=""><br class=""></div><div class=""><div class=""><div class=""><blockquote type="cite" class=""><div class=""><div class="m_5435089598488578425m_-4050234212288967131h5"><div class="">On Sep 10, 2018, at 9:49 AM, Preston Briggs via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org" target="_blank" class="">llvm-dev@lists.llvm.org</a>> wrote:</div><br class="m_5435089598488578425m_-4050234212288967131m_-5434489890348760605Apple-interchange-newline"></div></div><div class=""><div class=""><div class="m_5435089598488578425m_-4050234212288967131h5"><div dir="ltr" class="">Why have we ended up using linear-scan register allocation<div class=""><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" class="">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" class=""><br class=""></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" class="">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" class="">Preston</div><div class="m_5435089598488578425m_-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_5435089598488578425m_-4050234212288967131m_-5434489890348760605gmail-Apple-interchange-newline"></div><br class=""></div></div></div>
______________________________<wbr class="">_________________<br class="">LLVM Developers mailing list<br class=""><a href="mailto:llvm-dev@lists.llvm.org" target="_blank" class="">llvm-dev@lists.llvm.org</a><br class=""><a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" target="_blank" class="">http://lists.llvm.org/cgi-bin/<wbr class="">mailman/listinfo/llvm-dev</a><br class=""></div></blockquote></div><br class=""></div></div></div></blockquote></div><br class=""></div>
</div></blockquote></span></div><br class=""></div></blockquote></div><br class=""></div></div>
</div></blockquote></div></div></div><br class=""></div></blockquote></div><br class=""></div>
</div></blockquote></div><br class=""></body></html>