<html><head><meta http-equiv="Content-Type" content="text/html charset=utf-8"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class=""><br class=""><div><blockquote type="cite" class=""><div class="">On Feb 22, 2016, at 6:27 AM, Vikram TV <<a href="mailto:vikram.tarikere@gmail.com" class="">vikram.tarikere@gmail.com</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><br class="Apple-interchange-newline"><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class=""><div class="gmail_quote" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;">On Fri, Feb 19, 2016 at 10:46 PM, Vikram TV<span class="Apple-converted-space"> </span><span dir="ltr" class=""><<a href="mailto:vikram.tarikere@gmail.com" target="_blank" class="">vikram.tarikere@gmail.com</a>></span><span class="Apple-converted-space"> </span>wrote:<br class=""><blockquote class="gmail_quote" style="margin: 0px 0px 0px 0.8ex; border-left-width: 1px; border-left-color: rgb(204, 204, 204); border-left-style: solid; padding-left: 1ex;"><div dir="ltr" class="">Hi,<div class=""><br class=""></div><div class="">Thanks for the reply. Few thoughts inlined.</div><div class="gmail_extra"><br class=""><div class="gmail_quote"><span class="">On Fri, Feb 19, 2016 at 8:00 AM, Adam Nemet<span class="Apple-converted-space"> </span><span dir="ltr" class=""><<a href="mailto:anemet@apple.com" target="_blank" class="">anemet@apple.com</a>></span><span class="Apple-converted-space"> </span>wrote:<br class=""><blockquote class="gmail_quote" style="margin: 0px 0px 0px 0.8ex; border-left-width: 1px; border-left-color: rgb(204, 204, 204); border-left-style: solid; padding-left: 1ex;"><div style="word-wrap: break-word;" class="">Hi Vikram,<div class=""><br class=""><div class=""><div class=""><span class=""><blockquote type="cite" class=""><div class="">On Feb 18, 2016, at 9:21 AM, Vikram TV 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="">Hi all,<div class=""><br class=""></div><div class="">I have created a patch (up for review at:<span class="Apple-converted-space"> </span><a href="http://reviews.llvm.org/D17386" target="_blank" class="">http://reviews.llvm.org/D17386</a>) that does Loop Fusion implementation.</div><div class=""><br class=""></div><div class="">Approach:</div><div class="">Legality: Currently it can fuse two adjacent loops whose iteration spaces are same and are at same depth. <br class=""></div><div class=""><br class=""></div><div class="">Dependence legality: Currently, dependence legality cannot be checked across loops. Hence the loops are cloned along a versioned path, unconditionally fused along that path and then the dependence legality is checked on the fused loop keeping the instructions from original loops in context. Fusion is illegal if there is a backward dependence between memory accesses whose source was in first loop and sink was in second loop.</div><div class="">Currently, LoopAccessAnalysis is used to check dependence legality.</div></div></div></blockquote><div class=""><br class=""></div></span><div class="">Thanks for writing up the design here.</div><div class=""><br class=""></div><div class="">I think we have a pretty strong policy against creating temporary instructions and here you actually create an entire loop just to check legality.</div></div></div></div></div></blockquote></span><div class="">I didn't understand the consequences here. A subsequent DCE pass or explicit removal in this case is taking care of the temporaries. Any pointers in this regard would be helpful.</div></div></div></div></blockquote></div></div></blockquote><div><br class=""></div><div>Efficiency? All you need for the legality is the dependences so why not analyze those rather than recreate the entire underlying state from the lowest levels (i.e. instructions) with a bunch of data structures and analyses on top that you will all throw away at the end.</div><div><br class=""></div><div>Here is one pointer: <a href="http://article.gmane.org/gmane.comp.compilers.llvm.cvs/300603" class="">http://article.gmane.org/gmane.comp.compilers.llvm.cvs/300603</a>. You may be able to find more by searching the archives.</div><br class=""><blockquote type="cite" class=""><div class=""><div class="gmail_quote" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;"><blockquote class="gmail_quote" style="margin: 0px 0px 0px 0.8ex; border-left-width: 1px; border-left-color: rgb(204, 204, 204); border-left-style: solid; padding-left: 1ex;"><div dir="ltr" class=""><div class="gmail_extra"><div class="gmail_quote"><span class=""><blockquote class="gmail_quote" style="margin: 0px 0px 0px 0.8ex; border-left-width: 1px; border-left-color: rgb(204, 204, 204); border-left-style: solid; padding-left: 1ex;"><div style="word-wrap: break-word;" class=""><div class=""><div class=""><div class=""><div class=""><br class=""></div><div class="">It would probably be a better design to add the capability of adding two LAI objects together. This would effectively simulate the fusion on the analysis side so you could query the legality from that.</div></div></div></div></div></blockquote></span><div class="">I am not sure how the underlying analysis like SCEV would behave in this case. As per my understanding, it queries for a particular loop while we have populated accesses from two different loops. But assuming that it works, we would lose the ability to try/test using DependenceAnalysis in future. Currently, it is very easy to replace LoopAccessAnalysis with DependenceAnalysis.</div></div></div></div></blockquote></div></div></blockquote><div><br class=""></div><div>Yes, the SCEV part could be problematic. I am wondering if LAA could analyze pointers on the same underlying object without calling SCEV’s getMinusSCEV(). E.g. deciding that the the dependence distance is 1 between {A, +, 1}<L1> and {A+1, +, 1}<L2> assuming we added those two recurrences in the same loop should not be hard.</div><div><br class=""></div><div>I would certainly prefer keeping the heavy lifting for this outside of ScalarEvolution which is already pretty complex. We could of course still refactor parts of SCEV if that it is helpful for LAA to work this out.</div><div><br class=""></div><div>I am not sure I understand your LAA, DA argument. They are already pretty different (e.g. memchecks). I see DA more of a drop-in for MemoryDepChecker inside LAA.</div><div><br class=""></div><div>Adam</div><br class=""><blockquote type="cite" class=""><div class=""><div class="gmail_quote" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;"><blockquote class="gmail_quote" style="margin: 0px 0px 0px 0.8ex; border-left-width: 1px; border-left-color: rgb(204, 204, 204); border-left-style: solid; padding-left: 1ex;"><div dir="ltr" class=""><div class="gmail_extra"><div class="gmail_quote"><span class=""><blockquote class="gmail_quote" style="margin: 0px 0px 0px 0.8ex; border-left-width: 1px; border-left-color: rgb(204, 204, 204); border-left-style: solid; padding-left: 1ex;"><div style="word-wrap: break-word;" class=""><div class=""><div class=""><div class=""><div class=""><br class=""></div><div class="">Specifically, you could check if you have backward dependences between instructions in L2 to instructions in L1 which would be illegal.</div><div class=""><br class=""></div><div class="">As a side effect you’d also get the total set of memchecks which you could filter to only include checks where the participating pointers come from different loops. (This is quite similar to LoopDistribution.)</div></div></div></div></div></blockquote></span><div class="">I am happy to add a routine in a subsequent patch that filter the checks.</div></div></div></div></blockquote><div class="">Just to clarify, I meant to filter the runtime checks which is currently not done in the patch.</div><blockquote class="gmail_quote" style="margin: 0px 0px 0px 0.8ex; border-left-width: 1px; border-left-color: rgb(204, 204, 204); border-left-style: solid; padding-left: 1ex;"><div dir="ltr" class=""><div class="gmail_extra"><div class="gmail_quote"><span class=""><blockquote class="gmail_quote" style="margin: 0px 0px 0px 0.8ex; border-left-width: 1px; border-left-color: rgb(204, 204, 204); border-left-style: solid; padding-left: 1ex;"><div style="word-wrap: break-word;" class=""><div class=""><div class=""><div class=""><div class=""><br class=""></div><div class="">Also I don’t think it should be too hard to teach LVer to be able to version two consecutive loops (or arbitrary CFG?).</div></div></div></div></div></blockquote></span><div class="">I think yes. Instead of Loop Versioning deciding to version, code can be factored out so that it versions unconditionally "also" as requested by the pass that uses it. </div><div class=""><div class="h5"><blockquote class="gmail_quote" style="margin: 0px 0px 0px 0.8ex; border-left-width: 1px; border-left-color: rgb(204, 204, 204); border-left-style: solid; padding-left: 1ex;"><div style="word-wrap: break-word;" class=""><div class=""><div class=""><div class=""><div class=""><br class=""></div><div class="">Let me know what you think,</div><div class="">Adam</div><div class=""><br class=""></div><blockquote type="cite" class=""><div class=""><div class=""><div class=""><div dir="ltr" class=""><div class=""><br class=""></div><div class="">A basic diagram below tries to explain the approach taken to test dependence legality on two adjacent loops (L1 and L2).</div><div class=""><br class=""></div><div class=""><div class=""> <span class="Apple-converted-space"> </span>L1PH (PH: Preheader)</div><div class=""> <span class="Apple-converted-space"> </span>| </div><div class=""> <span class="Apple-converted-space"> </span>L1 </div><div class=""> <span class="Apple-converted-space"> </span>| </div><div class=""> <span class="Apple-converted-space"> </span>CB (L1Exit/L2PH: ConnectingBlock (CB) )</div><div class=""> <span class="Apple-converted-space"> </span>| </div><div class=""> <span class="Apple-converted-space"> </span>L2 </div><div class=""> <span class="Apple-converted-space"> </span>| </div><div class=""> <span class="Apple-converted-space"> </span>L2Exit</div></div><div class=""><br class=""></div><div class="">is versioned as:</div><div class=""><br class=""></div><div class=""><div class=""> <span class="Apple-converted-space"> </span>BooleanBB </div><div class=""> <span class="Apple-converted-space"> </span>/\ </div><div class=""> L1PH L1PH.clone</div><div class=""> | | </div><div class=""> <span class="Apple-converted-space"> </span>L1 L1.clone </div><div class=""> | | </div><div class=""> <span class="Apple-converted-space"> </span>CB CB.clone </div><div class=""> | | </div><div class=""> <span class="Apple-converted-space"> </span>L2 L2.clone </div><div class=""> <span class="Apple-converted-space"> </span>\ / </div><div class=""> L2Exit</div></div><div class=""><br class=""></div><div class="">And fused as:</div><div class=""><div class=""><br class=""></div><div class=""> <span class="Apple-converted-space"> </span>BooleanBB </div><div class=""> <span class="Apple-converted-space"> </span>/\</div><div class=""> L1PH FusedPH</div><div class=""> | |</div><div class=""> <span class="Apple-converted-space"> </span>L1 L1Blocks</div><div class=""> | | \</div><div class=""> CB L2Blocks |</div><div class=""> | | |/</div><div class=""> <span class="Apple-converted-space"> </span>L2 |</div><div class=""> \ /</div><div class=""> CommonExit</div></div><div class=""><br class=""></div><div class="">Profitability: Yet to be added.</div><div class=""><br class=""></div><div class="">Further, based on legality and profitability success, the fused loop is either retained or removed. If runtime checks are necessary, both original and fused loops are retained; otherwise the original loops are removed.</div><div class=""><br class=""></div><div class="">Currently, I have scheduled the fusion pass after distribution pass. Such a schedule negates the effect of the other pass, but given that the distribution (and fusion) pass is experimental and off by default, I felt it was okay to schedule that way till a global profitability is implemented.</div><div class=""><br class=""></div><div class="">Please share your feedback about the design and implementation.</div><div class=""><br class=""></div><div class="">Thank you</div><div class="">-- <br class=""></div><div class=""><div class=""><div dir="ltr" class=""><div class=""><div dir="ltr" class=""><div class=""><br class=""></div><div class="">Good time...</div><div class="">Vikram TV</div><div class="">CompilerTree Technologies</div><div class="">Mysore, Karnataka, INDIA</div></div></div></div></div></div></div></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></div></div></blockquote></div></div></div><div class=""><div class="h5"><br class=""><br clear="all" class=""><div class=""><br class=""></div>--<span class="Apple-converted-space"> </span><br class=""><div class=""><div dir="ltr" class=""><div class=""><div dir="ltr" class=""><div class=""><br class=""></div><div class="">Good time...</div><div class="">Vikram TV</div><div class="">CompilerTree Technologies</div><div class="">Mysore, Karnataka, INDIA</div></div></div></div></div></div></div></div></div></blockquote></div><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class=""><br clear="all" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class=""><div style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class=""><br class=""></div><span style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px; float: none; display: inline !important;" class="">--<span class="Apple-converted-space"> </span></span><br style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class=""><div class="gmail_signature" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;"><div dir="ltr" class=""><div class=""><div dir="ltr" class=""><div class=""><br class=""></div><div class="">Good time...</div><div class="">Vikram TV</div><div class="">CompilerTree Technologies</div><div class="">Mysore, Karnataka, INDIA</div></div></div></div></div></div></blockquote></div><br class=""></body></html>