<html><head><meta http-equiv="Content-Type" content="text/html charset=iso-8859-1"></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 Jan 15, 2015, at 4:22 PM, Ramanarayanan, Ramshankar <<a href="mailto:Ramshankar.Ramanarayanan@amd.com" class="">Ramshankar.Ramanarayanan@amd.com</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><div style="font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: 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; direction: ltr; font-family: Tahoma; font-size: 10pt;" class=""><div class="WordSection1"><div style="margin-top: 0px; margin-bottom: 0px;" class="">Hi,</div><p class="MsoNormal" style="margin-top: 0px; margin-bottom: 0px;"> </p><div style="margin-top: 0px; margin-bottom: 0px;" class="">We are proposing a loop fusion pass that tries to proactive fuse loops across function call boundaries and arbitrary control flow.</div><p class="MsoNormal" style="margin-top: 0px; margin-bottom: 0px;"> </p><div style="margin-top: 0px; margin-bottom: 0px;" class=""><a href="http://reviews.llvm.org/D7008" target="_blank" class="">http://reviews.llvm.org/D7008</a></div><p class="MsoNormal" style="margin-top: 0px; margin-bottom: 0px;"> </p><div style="margin-top: 0px; margin-bottom: 0px;" class="">With this pass, we get 103 loop fusions in SPECCPU INT 2006 462.libquantum with rate performance improving close to 2.5X in x86 (results from AMD A10-6700).</div><p class="MsoNormal" style="margin-top: 0px; margin-bottom: 0px;"> </p><div style="margin-top: 0px; margin-bottom: 0px;" class="">I took some liberties in patching up some of the code in ScalarEvolution/DependenceAnalysis/GlobalsModRef/Clang options/ and also adjusted the IPO/LTO pass managers. I would need to do a better job there but I would like to put this out as WIP for high level reviews. At this time standard loop fusion test cases may not work (cases where control dep are same or loops are truly adjacent etc). I would be doing that as well.</div><p class="MsoNormal" style="margin-top: 0px; margin-bottom: 0px;"> </p><div style="margin-top: 0px; margin-bottom: 0px;" class="">Appreciate suggestions and other help.<span class="Apple-converted-space"> </span></div><p class="MsoNormal" style="margin-top: 0px; margin-bottom: 0px;"> </p><div style="margin-top: 0px; margin-bottom: 0px;" class="">The pass initially attempts to inline calls which have loops in them. Following inlining, a separate scalar "main" pass tries to fuse loops. It is not necessary for loops to be adjacent or have the same control dependence. Specifically a control dependence closure is computed and loops that share a control dep closure prefix are taken as candidates for fusion, in case there are no other loops in a certain path between them. A loop graph is built with edges between loops which share the control dependence closure prefix. A recursive application of fusion follows on the graph from "bottom-up".</div><p class="MsoNormal" style="margin-top: 0px; margin-bottom: 0px;"> </p><div style="margin-top: 0px; margin-bottom: 0px;" class="">During fusion, program slices are taken based on the control flow closures of the two loops being fused. Example: Suppose two loops A and B are going to be fused. They share the same control dependence prefix, but their suffices vary. The suffices are used to duplicate Control flow paths that pass through both loops. Specifically paths from the first block in the control-dep closure suffix of the first loop, through the first loop's exit and following into the suffix of the second loop through the second loop's exit on to the common post-dominator of either loop's exit. The number of paths grows exponentially. At this time some heuristics are used when exploring for paths. Using profile based heuristics is a better idea.</div></div></div></div></blockquote><div><br class=""></div>Hi Ramshankar,<div class=""><br class=""><div><blockquote type="cite" class=""></blockquote></div></div><div class="">This is interesting, indeed. Thanks for soliciting input.</div><div class=""><br class=""></div><div class="">My main comment has to do with the fact that in order to get this gain you need many pieces to work together. My suggestion is to proceed in steps and develop it incrementally on trunk.</div><div class=""><br class=""></div><div class="">For example it would be good to first add a simple loop fusion pass that only merges adjacent loops and then build it up from there. Can you break down your approach into smaller, incremental steps like this? What would these steps be?</div><div class=""><br class=""></div><div class="">My other comment is about the choice of DependenceAnalysis framework. No pass currently uses this framework and I am not sure how complete the implementation is and whether it has adequate test coverage. This was my main reason for reusing the dependence analysis from the LoopVectorizer. Have you considered the same?</div><div class=""><br class=""></div><div class="">Adam</div><div class=""><br class=""></div><blockquote type="cite" class=""><div class=""><div style="font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: 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; direction: ltr; font-family: Tahoma; font-size: 10pt;" class=""><div class="WordSection1"><p class="MsoNormal" style="margin-top: 0px; margin-bottom: 0px;"> </p><div style="margin-top: 0px; margin-bottom: 0px;" class="">Also function unswitching helps by cleaning up control flow.</div><p class="MsoNormal" style="margin-top: 0px; margin-bottom: 0px;"> </p><div style="margin-top: 0px; margin-bottom: 0px;" class="">Example:</div><div style="margin-top: 0px; margin-bottom: 0px;" class="">if (a & b) {</div><div style="margin-top: 0px; margin-bottom: 0px;" class=""> if (a & c) {</div><div style="margin-top: 0px; margin-bottom: 0px;" class=""> if (t & 0xF) {</div><div style="margin-top: 0px; margin-bottom: 0px;" class=""> for (i=0; i < size; i++) {</div><div style="margin-top: 0px; margin-bottom: 0px;" class=""> if (A[i] & d) {</div><div style="margin-top: 0px; margin-bottom: 0px;" class=""> A[i] |= (1 << t);</div><div style="margin-top: 0px; margin-bottom: 0px;" class=""> }</div><div style="margin-top: 0px; margin-bottom: 0px;" class=""> }</div><div style="margin-top: 0px; margin-bottom: 0px;" class=""> }</div><div style="margin-top: 0px; margin-bottom: 0px;" class=""> }</div><div style="margin-top: 0px; margin-bottom: 0px;" class="">}</div><p class="MsoNormal" style="margin-top: 0px; margin-bottom: 0px;"> </p><div style="margin-top: 0px; margin-bottom: 0px;" class="">if (b & d) {</div><div style="margin-top: 0px; margin-bottom: 0px;" class=""> if (a & d) {</div><div style="margin-top: 0px; margin-bottom: 0px;" class=""> if (t & 0xA) {</div><div style="margin-top: 0px; margin-bottom: 0px;" class=""> for (i=0; i < size; i++) {</div><div style="margin-top: 0px; margin-bottom: 0px;" class=""> if (A[i] & d) {</div><div style="margin-top: 0px; margin-bottom: 0px;" class=""> A[i] |= (1 << t);</div><div style="margin-top: 0px; margin-bottom: 0px;" class=""> }</div><div style="margin-top: 0px; margin-bottom: 0px;" class=""> }</div><div style="margin-top: 0px; margin-bottom: 0px;" class=""> }</div><div style="margin-top: 0px; margin-bottom: 0px;" class=""> }</div><div style="margin-top: 0px; margin-bottom: 0px;" class="">}</div><p class="MsoNormal" style="margin-top: 0px; margin-bottom: 0px;"> </p><div style="margin-top: 0px; margin-bottom: 0px;" class="">After fusion we will have:</div><p class="MsoNormal" style="margin-top: 0px; margin-bottom: 0px;"> </p><div style="margin-top: 0px; margin-bottom: 0px;" class="">if (a&b && a&c && t&0xF && b&d && a&d t&0xA) {</div><div style="margin-top: 0px; margin-bottom: 0px;" class=""> for (i=0; i < size; i++) {</div><div style="margin-top: 0px; margin-bottom: 0px;" class=""> if (A[i] & d) {</div><div style="margin-top: 0px; margin-bottom: 0px;" class=""> A[i] |= (1 << t);</div><div style="margin-top: 0px; margin-bottom: 0px;" class=""> }</div><div style="margin-top: 0px; margin-bottom: 0px;" class=""> if (A[i] & d) {</div><div style="margin-top: 0px; margin-bottom: 0px;" class=""> A[i] |= (1 << t);</div><div style="margin-top: 0px; margin-bottom: 0px;" class=""> }</div><div style="margin-top: 0px; margin-bottom: 0px;" class=""> }</div><div style="margin-top: 0px; margin-bottom: 0px;" class="">} else {</div><div style="margin-top: 0px; margin-bottom: 0px;" class="">// original code</div><div style="margin-top: 0px; margin-bottom: 0px;" class=""> if (a & b) {</div><div style="margin-top: 0px; margin-bottom: 0px;" class=""> if (a & c) {</div><div style="margin-top: 0px; margin-bottom: 0px;" class=""> if (t & 0xF) {</div><div style="margin-top: 0px; margin-bottom: 0px;" class=""> for (i=0; i < size; i++) {</div><div style="margin-top: 0px; margin-bottom: 0px;" class=""> if (A[i] & d) {</div><div style="margin-top: 0px; margin-bottom: 0px;" class=""> A[i] |= (1 << t);</div><div style="margin-top: 0px; margin-bottom: 0px;" class=""> }</div><div style="margin-top: 0px; margin-bottom: 0px;" class=""> }</div><div style="margin-top: 0px; margin-bottom: 0px;" class=""> }</div><div style="margin-top: 0px; margin-bottom: 0px;" class=""> }</div><div style="margin-top: 0px; margin-bottom: 0px;" class=""> }</div><p class="MsoNormal" style="margin-top: 0px; margin-bottom: 0px;"> </p><div style="margin-top: 0px; margin-bottom: 0px;" class=""> if (b & d) {</div><div style="margin-top: 0px; margin-bottom: 0px;" class=""> if (a & d) {</div><div style="margin-top: 0px; margin-bottom: 0px;" class=""> if (t & 0xA) {</div><div style="margin-top: 0px; margin-bottom: 0px;" class=""> for (i=0; i < size; i++) {</div><div style="margin-top: 0px; margin-bottom: 0px;" class=""> if (A[i] & d) {</div><div style="margin-top: 0px; margin-bottom: 0px;" class=""> A[i] |= (1 << t);</div><div style="margin-top: 0px; margin-bottom: 0px;" class=""> }</div><div style="margin-top: 0px; margin-bottom: 0px;" class=""> }</div><div style="margin-top: 0px; margin-bottom: 0px;" class=""> }</div><div style="margin-top: 0px; margin-bottom: 0px;" class=""> }</div><div style="margin-top: 0px; margin-bottom: 0px;" class=""> }</div><div style="margin-top: 0px; margin-bottom: 0px;" class="">}</div><p class="MsoNormal" style="margin-top: 0px; margin-bottom: 0px;"> </p><div style="margin-top: 0px; margin-bottom: 0px;" class="">Thanks,</div><div style="margin-top: 0px; margin-bottom: 0px;" class="">Ramshankar</div></div></div><span style="font-family: Helvetica; font-size: 10px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: 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><br style="font-family: Helvetica; font-size: 10px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: 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=""><span style="font-family: Helvetica; font-size: 10px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: 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="">LLVM Developers mailing list</span><br style="font-family: Helvetica; font-size: 10px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: 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=""><a href="mailto:LLVMdev@cs.uiuc.edu" style="font-family: Helvetica; font-size: 10px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: 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="">LLVMdev@cs.uiuc.edu</a><span style="font-family: Helvetica; font-size: 10px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: 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><a href="http://llvm.cs.uiuc.edu/" style="font-family: Helvetica; font-size: 10px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: 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="">http://llvm.cs.uiuc.edu</a><br style="font-family: Helvetica; font-size: 10px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: 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=""><a href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev" style="font-family: Helvetica; font-size: 10px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: 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="">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a></div></blockquote></div><br class=""></body></html>