<div dir="ltr">Hi Daniel, <br><br>Thanks! I wonder if there's a way to reuse some code in Reassociation. Looks like most of the logic we want to implement is in Reassociate.cpp already. But the entire pass seems too expensive to run with CGP or after each instcombine. <div><br></div><div>Jingyue</div></div><br><div class="gmail_quote">On Fri, Mar 13, 2015 at 10:43 AM Daniel Berlin <<a href="mailto:dberlin@dberlin.org">dberlin@dberlin.org</a>> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div class="gmail_quote">On Fri, Mar 13, 2015 at 10:16 AM Mark Heffernan <<a href="mailto:meheff@google.com" target="_blank">meheff@google.com</a>> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div class="gmail_extra"><div class="gmail_quote">On Thu, Mar 12, 2015 at 2:34 PM, Hal Finkel <span dir="ltr"><<a href="mailto:hfinkel@anl.gov" target="_blank">hfinkel@anl.gov</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">It is not clear to me at all that preventing the merging is the right solution. There are a large number of analysis, including alias analysis, and optimizations that use GetUnderlyingObject, and related routines to search back through GEPs. They only do this up to some small finite depth (six, IIRC). So reducing the GEP depth is likely the right solution for InstCombine (which has the job of canonicalizing the IR).<br>
<br>
We should, however, pull these apart somewhere, and probably in some way that is address-mode aware. I'd recommend trying to split non-free (via the addressing-mode) loop-invariant parts of GEPs out of loops in CodeGenPrep.<br></blockquote><div><br></div></div></div></div><div dir="ltr"><div class="gmail_extra"><div class="gmail_quote"><div>Thanks, Hal.  I'll have a look at CGP to see how this might be done.  It's a little more complicated than just pulling the GEP apart, there needs to be a loop-invariant-aware reassociation to undo the damage done by the initial merge.</div></div></div></div></blockquote><div><br></div></div></div><div dir="ltr"><div class="gmail_quote"><div>So, this is in fact, just using the ranks reassociation would normally use, to do splitting :)</div><div><br></div><div>That is, even outside of geps, you end up with chains of operations where, if you moved the operands around, you would expose loop-invariant calculation.<br></div><div><br></div><div>Reassociation builds a rank map ordered by RPO traversal of the CFG, and uses it to place operations at the same rank into the same expression.  This guarantees deeper loops have higher ranks.</div><div>For your purposes, if you have it calculated already, you could just use loop depth instead of RPO ordering, since you only care about invariantness (the downside to not using RPO here is that you may increase register pressure. The upside is it's easier to reason about the ranks for your purposes).</div><div><br></div><div>Anyway, reassociate tries to place operations with the lowest ranks into leaf computations, since those are "the most loop invariant".</div><div><br></div><div>You want to do exactly the same thing, with likely the same algorithm, splitting geps as necessary into "leaf geps" to place low-ranking operations in the same gep.</div><div><br></div><div>The only heuristic part is "what is the lowest rank you want to split for".</div><div>If you have stuff at rank 0 and stuff not at rank 0, you always want to split out the rank 0 stuff.</div><div>rank 1 and rank 2, well, if you are using loop depth, it can only  be invariant in a loop of rank 2, etc.</div><div>You don't need to split if rank == highest rank in functions, since you are guaranteed it is not invariant in any loop in that case<br></div></div></div>
______________________________<u></u>_________________<br>
LLVM Developers mailing list<br>
<a href="mailto:LLVMdev@cs.uiuc.edu" target="_blank">LLVMdev@cs.uiuc.edu</a>         <a href="http://llvm.cs.uiuc.edu" target="_blank">http://llvm.cs.uiuc.edu</a><br>
<a href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev" target="_blank">http://lists.cs.uiuc.edu/<u></u>mailman/listinfo/llvmdev</a><br>
</blockquote></div>