<div dir="ltr">The idea seems sound, but do you really have a CPU in which such a complex rematerialization is better than an L1 cache load from the stack frame?<div><br></div><div><div> lis 3, 12414</div><div> ori 3, 3, 27470</div><div> sldi 3, 3, 32</div><div> oris 3, 3, 35809</div><div> ori 30, 3, 20615</div></div><div><br></div><div>I'm not familiar with modern PPC64 but seems like a lose on PPC G5 and from the docs I quickly found (2 cycle latency on dependent int ALU ops) Power8 too.</div><div><br></div><div>OK, maybe (if I didn't screw up the rldimi):</div><div><br></div><div><div> lis 3, 12414</div><div> lis 30, 35809</div><div> ori 3, 3, 27470</div><div> ori 30, 30, 20615<br></div><div> rldimi 30, 3, 32, 0</div></div><div><br></div><div>Or is there something that optimizes such sequences building constants?</div></div><div class="gmail_extra"><br><div class="gmail_quote">On Mon, Sep 12, 2016 at 6:51 PM, vivek pandya via llvm-dev <span dir="ltr"><<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div>Hello Developers,<br></div><div><br></div><div>I am working with my other batchmates to improve register remat in LLVM.</div><div>We want to remat live ranges made of multiple instruction.</div><div><br></div><div>Just to support our proposal here is a simple example that currently remat does</div><div>not cover</div><div><br></div><div>$ cat ~/tmp/tl.c</div><div>void foo(long);</div><div>void bar() {</div><div> for (int i = 0; i < 1600; ++i)</div><div> foo(3494348345984503943);</div><div>}</div><div><br></div><div>$ clang -O3 -S -o - ~/tmp/tl.c -target powerpc64</div><div>...</div><div># BB#0: # %entry</div><div>...</div><div> lis 3, 12414</div><div> ori 3, 3, 27470</div><div> sldi 3, 3, 32</div><div> oris 3, 3, 35809</div><div> ori 30, 3, 20615</div><div>...</div><div>.LBB0_1: # %for.body</div><div> mr 3, 30</div><div> bl foo</div><div>...</div><div><br></div><div>There is a sequence of instructions used to materialize the constant, the first </div><div>one (the lis) is trivially rematerialiable, and the others depend only on that one,</div><div>and have no side effects. If we otherwise needed to spill the constant, we might</div><div>wish to move the entire set of instructions that compute the value into the loop body.</div><div>(Many thanks to Hal Finkel for this example and head start)</div><div><br></div><div>We are following very old but effective paper "Rematerialization"</div><div><a href="http://dl.acm.org/citation.cfm?id=143143" target="_blank">http://dl.acm.org/citation.<wbr>cfm?id=143143</a> ------------------------------<wbr>[1]</div><div><br></div><div>This extension will specially improve code quality for RICS backends like </div><div>powerpc, MIPS, ARM, AArch64 etc.</div><div><br></div><div>Here is a tentative apporach ( after reading the above mentioned paper and current remat code) that I would like to follow.</div><div><br></div><div>Please share your views because this may be totally wrong direction. Also I will</div><div>be happy if this gets into main line LLVM code but if community don't want</div><div>to make remat heavy than please guide me for my class project perspective.</div><div><br></div><div>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><br></div><div>2 ) We would like to add a pass similar to SCCP.cpp (Sparse Conditional Constant</div><div>Propagation based on Wegman and Zadeck's work <a href="http://dl.acm.org/citation.cfm?id=103136" target="_blank">http://dl.acm.org/citation.<wbr>cfm?id=103136</a>) as desribed in [1]. This pass will be scheduled to run before register allocation.</div><div><br></div><div>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><br></div><div>4 ) The remat APIs defined in LiveRangeEdit.cpp will use analysis from the Map</div><div>when a spill is required for RA.</div><div><br></div><div>5 ) The remat transformation APIs like rematerializeAt() will be teached to remat</div><div>live ranges with multiple instructions too.</div><div><br></div><div>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><br></div><div>Few points:</div><div>--------------</div><div>* The analysis pass to be addes as per (2) will use target specific information</div><div>from TargetInstrInfo.cpp as the current remat infrastructure uses.</div><div><br></div><div>* This approach will not be on demand as the current approach is (i.e remat specific</div><div>code will be executed only if there is a spill) so the pass in (2) can be an</div><div>overhead so we may want it to enable only for higher level of optimization.</div><div><br></div><div>* Will it be possible to use existing SCCP.cpp code with few modification to lattice</div><div>and related mathematical operation so that it can serve both purpose?</div><div><br></div><div>* No changes in current register allocators or spill framework will be required</div><div>because remat entry point will be LiveRangeEdit.</div><div><br></div><div>Any other way with less overhead is always welcomed.</div><div>Please help us developing a plan to implement this.</div><div><br></div><div>Hoping for comments!</div><div><br></div><div>Sincerely,</div><div>Vivek</div><div><br></div></div>
<br>______________________________<wbr>_________________<br>
LLVM Developers mailing list<br>
<a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a><br>
<a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" rel="noreferrer" target="_blank">http://lists.llvm.org/cgi-bin/<wbr>mailman/listinfo/llvm-dev</a><br>
<br></blockquote></div><br></div>