<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 Jun 23, 2016, at 12:06 PM, Vikram TV <<a href="mailto:vikram.tarikere@gmail.com" class="">vikram.tarikere@gmail.com</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 Thu, Jun 23, 2016 at 11:34 PM, Adam Nemet <span dir="ltr" class=""><<a href="mailto:anemet@apple.com" target="_blank" class="">anemet@apple.com</a>></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=""><br class=""><div class=""><div class=""><div class="h5"><blockquote type="cite" class=""><div class=""><br class=""></div><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;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing: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 style="word-wrap:break-word" class=""><div class=""><span class=""><div class=""><br class=""></div></span><div class="">Hi Vikram,</div><div class=""><br class=""></div><div class="">Is the analysis result specific to a loop nest or to a loop nest together with a set of reference groups?</div></div></div></blockquote><div class="">The result is specific to each loop in the loop nest and the calculations are based on the references in the loop nest.</div></div></div></blockquote><div class=""><br class=""></div></div></div><div class="">Sorry can you please rephrase/elaborate, I don’t understand what you mean. Analysis results are retained unless a transformation invalidates them. My question is how the reference groups affect all this.</div></div></div></blockquote><div class=""> </div><div class="">Sorry, I now understood that you meant llvm's analysis result (I thought how the analysis calculates the result). The analysis result is specific to each loop in its loop nest. Reference groups are necessary during cost computation only.</div></div></div></div></div></blockquote><div><br class=""></div><div>Hi Vikram,</div><div><br class=""></div><div>Let me ask you differently. This analysis can be thought of as having two inputs, (1) a loop or loops (?) and (2) the reference group. If a transformation pass requires some analysis, the analysis result would have to be computed unless it has already been computed and no transformation has invalidated it since the last use.</div><div><br class=""></div><div>My question how does this apply to this pass. Consider this sequence of passes:</div><div><br class=""></div><div>1. loop fusion of loops L1 and L2</div><div><br class=""></div></div><blockquote style="margin: 0 0 0 40px; border: none; padding: 0px;" class=""><div><div>Computes Loop Cost for L1 and L2 with the reference group that includes accesses from the both groups.</div><div><br class=""></div><div>Let’s assume here that the transformation does not occur at the end so the analysis result is still valid at this point.</div></div></blockquote><div><div><br class=""></div><div>2. loop distribution/fission for loop L1</div><div><br class=""></div></div><blockquote style="margin: 0 0 0 40px; border: none; padding: 0px;" class=""><div><div>Does this have to recompute the Loop Cost for L1 because now the reference group only includes accesses from L1?</div><div><br class=""></div></div></blockquote>To put it different my question what the tag/key is when caching the analysis result. Is it the loop only or also the reference group.<div class=""><br class=""></div><div class=""><div class="">Adam<br class=""><div><br class=""><blockquote type="cite" class=""><div class=""><div dir="ltr" class=""><div class="gmail_extra"><div class="gmail_quote"><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=""><br class=""></div><div class="">You could probably describe how you envision this analysis would be used with something like Loop Fusion.</div></div></div></blockquote><div class=""> </div><div class="">For Loop Interchange, the cost calculated for each loop can provide a desired ordering of the loops. Loop interchange can start interchanging the loops to match the desired order iff interchange legality check passes.<br class=""></div><div class="">Eg: For matrix multiplication case,</div><div class=""> for (i = 0 to 5000)<br class=""> for (j = 0 to 5000)<br class=""> for (k = 0 to 5000)</div><div class=""> C[i,j] = C[i,j] + A[i,k]* B[k,j]</div><div class=""> Here, based on cache line size and the cache penalties for the references (please refer to first mail of the thread or the reference paper for different penalties), following costs result:</div><div class=""> Loop i cost: <span style="white-space: pre-wrap;" class="">2.501750e+11</span></div><div class=""><span style="white-space: pre-wrap;" class=""> Loop j cost: </span><span style="white-space: pre-wrap;" class="">6.256252e+10</span></div><div class=""><span style="white-space: pre-wrap;" class=""> Loop k cost: </span><span style="white-space: pre-wrap;" class="">1.563688e+11</span></div><div class=""><font class=""><span style="white-space:pre-wrap" class="">Loop cost here is nothing but the total cache penalities due to all references, including penalties due to outer loops. So lower costing loop is a better fit for innermost loop because it has better cache locality. This would result in the desired loop order: i, k, j; and LoopInterchange can interchange 'j' and 'k' loops given the legality check passes (a nearest ordering for which legality is correct is also an optimal loop ordering).</span></font></div><div class=""><font class=""><span style="white-space:pre-wrap" class=""><br class=""></span></font></div><div class=""><font class=""><span style="white-space:pre-wrap" class="">For fusion/fission, loop costs due to cache can be calculated by assigning cache penalties for references with respect to loops before and after fusion/fission. The costs will be a profitability measure for fusion/fission.</span></font></div><div class=""><font class=""><span style="white-space:pre-wrap" class=""><br class=""></span></font></div><div class=""><font class=""><span style="white-space:pre-wrap" class="">I think use case description was very brief in a previous mail. So I have elaborated this time. More details can also be found in <a href="http://www.cs.utexas.edu/users/mckinley/papers/asplos-1994.pdf" class="">http://www.cs.utexas.edu/users/mckinley/papers/asplos-1994.pdf</a>.</span></font></div><div class=""><font class=""><span style="white-space:pre-wrap" class=""><br class=""></span></font></div><div class=""><font class=""><span style="white-space:pre-wrap" class="">Thanks</span></font></div></div><div class="gmail_signature" data-smartmail="gmail_signature"><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></blockquote></div><br class=""></div></div></body></html>