<html><head><style type='text/css'>p { margin: 0; }</style></head><body><div style='font-family: arial,helvetica,sans-serif; font-size: 10pt; color: #000000'><br><hr id="zwchr"><blockquote style="border-left: 2px solid rgb(16, 16, 255); margin-left: 5px; padding-left: 5px; color: rgb(0, 0, 0); font-weight: normal; font-style: normal; text-decoration: none; font-family: Helvetica,Arial,sans-serif; font-size: 12pt;"><b>From: </b>"Quentin Colombet via llvm-dev" <llvm-dev@lists.llvm.org><br><b>To: </b>"vivek pandya" <vivekvpandya@gmail.com><br><b>Cc: </b>"llvm-dev" <llvm-dev@lists.llvm.org>, "Nirav Rana" <h2015087@pilani.bits-pilani.ac.in>, "Matthias Braun" <matze@braunis.de><br><b>Sent: </b>Monday, September 19, 2016 1:27:10 PM<br><b>Subject: </b>Re: [llvm-dev] [RFC] Register Rematerialization (remat) Extension<br><br>
Hi Vivek,<div class=""><br class=""><div><blockquote class=""><div class="">On Sep 19, 2016, at 11:17 AM, vivek pandya via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org" class="" target="_blank">llvm-dev@lists.llvm.org</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><div dir="ltr" class=""><br class=""><div class="gmail_extra"><br class=""><div class="gmail_quote">On Mon, Sep 19, 2016 at 6:21 PM, James Molloy <span dir="ltr" class=""><<a href="mailto:james@jamesmolloy.co.uk" target="_blank" class="">james@jamesmolloy.co.uk</a>></span> wrote:<br class=""><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;"><div dir="ltr" class="">Hi,<div class=""><br class=""></div><div class="">I've been looking at this myself for ARM, and came up with a much simpler solution: lower immediate materializations to a post-RA pseudo and expand the chain of materialization instructions after register allocation / remat. Remat only sees one instruction with no dependencies.</div><div class=""><br class=""></div><div class="">Did you look down this route and discount it?</div></div></blockquote><div class="">No actually I am not much familiar with this topic so I mostly reply on research papers available.</div><div class="">But your idea seems to be simple and good solution but I am not sure if this can cover every possible cases. </div></div></div></div></div></blockquote><div><br class=""></div><div>This is the way all targets deal with simple rematerialization involving several instructions in LLVM AFAIK.</div><div><br class=""></div><div>Basically, the target defines a pseudo instruction that encodes this sequence of instructions and expands it after register allocation. This is a case by case thing, there is no patch that can be generalized for other target.</div><div><div>For instance, look at the expansion of AArch64::<span style="font-family: Menlo; font-size: 11px;" class="">MOVi64imm.</span></div><div class=""><span style="font-family: Menlo; font-size: 11px;" class=""><br class=""></span></div></div><div id="DWT5043">The bottom line is, our rematerialization scheme is currently limited, but I am not sure your proposal get us beyond what we already support.</div></div></div></blockquote>I might have misunderstood the proposal, but why do you say that? The problem is not limited to constants (as perhaps evidenced by Ivan Baev's talk at the 2014 dev meeting). One basic thing we should get, for example, is:<br><br> q = ...;<br> r = ...;<br> for (...) {<br> // complicated stuff<br> foo(q, r, q - r); // should prefer to remat (q-r) here instead of spilling.<br> }<br><br>Also, this is all perhaps related to https://llvm.org/bugs/show_bug.cgi?id=25373#c9<br><br>Thanks again,<br>Hal<br><blockquote style="border-left: 2px solid rgb(16, 16, 255); margin-left: 5px; padding-left: 5px; color: rgb(0, 0, 0); font-weight: normal; font-style: normal; text-decoration: none; font-family: Helvetica,Arial,sans-serif; font-size: 12pt;"><div class=""><div><div></div><div><br class=""></div><div>Cheers,</div><div>Q.</div><br class=""><blockquote class=""><div class=""><div dir="ltr" class=""><div class="gmail_extra"><div class="gmail_quote"><div class=""><br class=""></div><div class="">Do you have a patch for this? I can work on this to make it work for other architectures for which this will be beneficial.</div><div class=""><br class=""></div><div class="">Sincerely,</div><div class="">Vivek</div><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;"><div dir="ltr" class=""><div class=""><br class=""></div><div class="">Cheers,</div><div class=""><br class=""></div><div class="">James</div></div><div class="HOEnZb"><div class="h5"><br class=""><div class="gmail_quote"><div dir="ltr" class="">On Wed, 14 Sep 2016 at 02:43 Gerolf Hoflehner via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org" target="_blank" class="">llvm-dev@lists.llvm.org</a>> wrote:<br class=""></div><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;"><div style="word-wrap: break-word;" class=""><div class=""><blockquote class=""><div class="">On Sep 12, 2016, at 10:14 AM, Andrew Trick via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org" target="_blank" class="">llvm-dev@lists.llvm.org</a>> wrote:</div><br class=""><div class=""><div style="word-wrap: break-word;" class=""><br class=""><div class=""><blockquote class=""><div class="">On Sep 12, 2016, at 8:51 AM, vivek pandya via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org" target="_blank" class="">llvm-dev@lists.llvm.org</a>> wrote:</div><br class=""><div class=""><div dir="ltr" class=""><div class=""><br class=""></div><div class="">1 ) As LLVM MI is already in SSA form before reg allocation so for LLVM I think it does not require to build SSA graph and converting it back after optimization completed as mentioned in [1]</div><div class=""><br class=""></div><div class="">2 ) We would like to add a pass similar to SCCP.cpp (Sparse Conditional Constant</div><div class="">Propagation based on Wegman and Zadeck's work <a href="http://dl.acm.org/citation.cfm?id=103136" target="_blank" class="">http://dl.acm.org/citation.cfm?id=103136</a>) as desribed in [1]. This pass will be scheduled to run before register allocation.</div><div class=""><br class=""></div><div class="">3 ) Output of the pass added in Step 2 will be a Map of def to instructions pointers (instructions which can be used to remat the given live range). The map will contain live ranges which is due to single instruction and multiple instructions.</div></div></div></blockquote><div class=""><br class=""></div>LiveIntervals maintains a quasi-SSA form via VNInfo. It does not allow efficient def-use queries, but use-def is there, which is all that you should need.</div></div></div></blockquote><div class=""><br class=""></div></div></div><div style="word-wrap: break-word;" class=""><div class="">I also only see a narrow and specific remat cost problem in the example: is it cheaper is issue a chain of instructions rather than a fill? And for this a use-def is sufficient.</div></div><div style="word-wrap: break-word;" class=""><div class=""><br class=""><blockquote class=""><div class=""><div style="word-wrap: break-word;" class=""><div class=""><br class=""></div><div class="">It would be great to have better remat during regalloc, but please try to avoid building additional state that needs to be maintained.</div></div></div></blockquote><div class=""><br class=""></div></div></div><div style="word-wrap: break-word;" class=""><div class="">You proposed a fairly complex scheme. The question then is always is it worth it? To answer that question you would need to investigate and break down the current remat problems (spills but should remat, remat but should spill, should remat at a different location, etc) eg. for the llvm test suite, and show that your algorithms solves the most important ones.</div></div><div style="word-wrap: break-word;" class=""><div class=""><br class=""><div class=""><br class=""></div><br class=""><blockquote class=""><div class=""><div style="word-wrap: break-word;" class=""><div class=""><br class=""></div><div class="">-Andy</div><div class=""><br class=""><blockquote class=""><div class=""><div dir="ltr" class=""><div class=""><br class=""></div><div class="">4 ) The remat APIs defined in LiveRangeEdit.cpp will use analysis from the Map</div><div class="">when a spill is required for RA.</div><div class=""><br class=""></div><div class="">5 ) The remat transformation APIs like rematerializeAt() will be teached to remat</div><div class="">live ranges with multiple instructions too.</div><div class=""><br class=""></div><div class="">6 ) A cost analysis will be require to decide between remat and spill. This should be based on at least two factors register pressure and spill cost</div><div class=""><br class=""></div><div class="">Few points:</div><div class="">--------------</div><div class="">* The analysis pass to be addes as per (2) will use target specific information</div><div class="">from TargetInstrInfo.cpp as the current remat infrastructure uses.</div><div class=""><br class=""></div><div class="">* This approach will not be on demand as the current approach is (i.e remat specific</div><div class="">code will be executed only if there is a spill) so the pass in (2) can be an</div><div class="">overhead so we may want it to enable only for higher level of optimization.</div><div class=""><br class=""></div><div class="">* Will it be possible to use existing SCCP.cpp code with few modification to lattice</div><div class="">and related mathematical operation so that it can serve both purpose?</div><div class=""><br class=""></div><div class="">* No changes in current register allocators or spill framework will be required</div><div class="">because remat entry point will be LiveRangeEdit.</div><div class=""><br class=""></div><div class="">Any other way with less overhead is always welcomed.</div><div class="">Please help us developing a plan to implement this.</div><div class=""><br class=""></div><div class="">Hoping for comments!</div><div class=""><br class=""></div><div class="">Sincerely,</div><div class="">Vivek</div><div class=""><br class=""></div></div>
_______________________________________________<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/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" 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/mailman/listinfo/llvm-dev</a><br class=""></div></blockquote></div></div>_______________________________________________<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" rel="noreferrer" target="_blank" class="">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><br class="">
</blockquote></div>
</div></div></blockquote></div><br class=""></div></div>
_______________________________________________<br class="">LLVM Developers mailing list<br class=""><a href="mailto:llvm-dev@lists.llvm.org" class="" target="_blank">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=""></div><br>_______________________________________________<br>LLVM Developers mailing list<br>llvm-dev@lists.llvm.org<br>http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev<br></blockquote><br><br><br>-- <br><div><span name="x"></span>Hal Finkel<br>Lead, Compiler Technology and Programming Languages<br>Leadership Computing Facility<br>Argonne National Laboratory<span name="x"></span><br></div></div></body></html>