<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 27, 2017, at 7:27 AM, Hal Finkel <<a href="mailto:hfinkel@anl.gov" class="">hfinkel@anl.gov</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><div class="moz-cite-prefix" style="font-family: Helvetica; font-size: 10px; font-style: normal; font-variant-caps: 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; background-color: rgb(255, 255, 255);"><br class="Apple-interchange-newline">On 02/27/2017 06:29 AM, Nema, Ashutosh wrote:<br class=""></div><blockquote cite="mid:CY4PR12MB17993414B37BDE99294FD69FFB570@CY4PR12MB1799.namprd12.prod.outlook.com" type="cite" style="font-family: Helvetica; font-size: 10px; font-style: normal; font-variant-caps: 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-size-adjust: auto; -webkit-text-stroke-width: 0px; background-color: rgb(255, 255, 255);" class=""><div class="WordSection1" style="page: WordSection1;"><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class="">Thanks for looking into this.<o:p class=""></o:p></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><o:p class=""> </o:p></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class="">1) Issues with re running vectorizer:<o:p class=""></o:p></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class="">Vectorizer might generate redundant alias checks while vectorizing epilog loop.<o:p class=""></o:p></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class="">Redundant alias checks are expensive, we like to reuse the results of already computed alias checks.<o:p class=""></o:p></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class="">With metadata we can limit the width of epilog loop, but not sure about reusing alias check result.<o:p class=""></o:p></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class="">Any thoughts on rerunning vectorizer with reusing the alias check result ?</div></div></blockquote><br style="font-family: Helvetica; font-size: 10px; font-style: normal; font-variant-caps: 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; background-color: rgb(255, 255, 255);" class=""><span style="font-family: Helvetica; font-size: 10px; font-style: normal; font-variant-caps: 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; background-color: rgb(255, 255, 255); float: none; display: inline !important;" class="">One way of looking at this is: Reusing the alias-check result is really just a conditional propagation problem; if we don't already have an optimization that can combine these after the fact, then we should.</span><br style="font-family: Helvetica; font-size: 10px; font-style: normal; font-variant-caps: 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; background-color: rgb(255, 255, 255);" class=""></div></blockquote><div><br class=""></div><div>+Danny</div><div><br class=""></div><div>Isn’t Extended SSA supposed to help with this?</div><div><br class=""></div><div>I see this as a problem that needs to be solved regardless when loop-versioning is performed by multiple passes [1]. We need to be able to come up with the minimum sets of checks:</div><div><br class=""></div><div>* remove redundant checks in favor of identical dominating checks</div><div>* share (i.e. factor out) identical checks required by consecutive loops </div><div><br class=""></div><div>Ashutosh, I suggest that you try rerunning the vectorizer on the relevant testcases and file PRs about the inefficiencies you encounter.</div><div><br class=""></div><div>Adam</div><div><br class=""></div><div>[1] <a href="http://lists.llvm.org/pipermail/llvm-dev/2015-May/085922.html" class="">http://lists.llvm.org/pipermail/llvm-dev/2015-May/085922.html</a></div><br class=""><blockquote type="cite" class=""><div class=""><br style="font-family: Helvetica; font-size: 10px; font-style: normal; font-variant-caps: 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; background-color: rgb(255, 255, 255);" class=""><span style="font-family: Helvetica; font-size: 10px; font-style: normal; font-variant-caps: 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; background-color: rgb(255, 255, 255); float: none; display: inline !important;" class=""> -Hal</span><br style="font-family: Helvetica; font-size: 10px; font-style: normal; font-variant-caps: 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; background-color: rgb(255, 255, 255);" class=""><br style="font-family: Helvetica; font-size: 10px; font-style: normal; font-variant-caps: 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; background-color: rgb(255, 255, 255);" class=""><blockquote cite="mid:CY4PR12MB17993414B37BDE99294FD69FFB570@CY4PR12MB1799.namprd12.prod.outlook.com" type="cite" style="font-family: Helvetica; font-size: 10px; font-style: normal; font-variant-caps: 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-size-adjust: auto; -webkit-text-stroke-width: 0px; background-color: rgb(255, 255, 255);" class=""><div class="WordSection1" style="page: WordSection1;"><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><o:p class=""></o:p></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><o:p class=""> </o:p></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class="">2) Best & worst case for epilog vectorization.<o:p class=""></o:p></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class="">Epilog vectorization incurs additional cost of checks which decides to execute either epilog vector loop or scalar loop.<o:p class=""></o:p></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class="">These checks are:<o:p class=""></o:p></div><div style="margin: 0in 0in 0.0001pt 0.5in; font-size: 11pt; font-family: Calibri, sans-serif; color: windowtext; text-indent: -0.25in;" class=""><span class="">a)<span style="font-style: normal; font-variant-caps: normal; font-weight: normal; font-size: 7pt; line-height: normal; font-family: 'Times New Roman';" class=""> <span class="Apple-converted-space"> </span></span></span>Min trip count check for epilog vector loop.<o:p class=""></o:p></div><div style="margin: 0in 0in 0.0001pt 0.5in; font-size: 11pt; font-family: Calibri, sans-serif; color: windowtext; text-indent: -0.25in;" class=""><span class="">b)<span style="font-style: normal; font-variant-caps: normal; font-weight: normal; font-size: 7pt; line-height: normal; font-family: 'Times New Roman';" class=""> <span class="Apple-converted-space"> </span></span></span>Alias result check (only if alias check is generated for first vector version)<o:p class=""></o:p></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><o:p class=""> </o:p></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class="">Where the epilog vector trip count is large epilog vectorization with profitable width likely to give gain. Worst case probably after these additional checks executing the scalar loop.<o:p class=""></o:p></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><o:p class=""> </o:p></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class="">3) Benchmarking & results:<o:p class=""></o:p></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class="">We have observed 4% improvement in one of our internal benchmark.<o:p class=""></o:p></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class="">Tried CPU2006 and didn’t found any degrade & improvements.<o:p class=""></o:p></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class="">On code size increase I have not yet verified yet will check and get back.<o:p class=""></o:p></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><o:p class=""> </o:p></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class="">4) What should be the minimum first vector loop width to enable epilog vectorization.<o:p class=""></o:p></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class="">This count should not be small as it may degrade the performance, with my limited tests I have observed 16 is a point it shows gains with one of our internal benchmark. This require more experiments & testing to decide what should be the minimum width.<o:p class=""></o:p></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><o:p class=""> </o:p></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class="">5) Unrolling issues:<o:p class=""></o:p></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class="">As Ayal mentioned with large unroll factor the next profitable EpilogVF could be equal to VF.<o:p class=""></o:p></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class="">With the same reason the current patch enforces UF=1, as unrolling can minimize the possibility of executing epilog vector loop.<o:p class=""></o:p></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><o:p class=""> </o:p></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class="">Example to understand the new layout:<o:p class=""></o:p></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><o:p class=""> </o:p></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class="">void foo (char *A, char *B, char *C, int len) {<o:p class=""></o:p></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""> <span class="Apple-converted-space"> </span>int i = 0;<o:p class=""></o:p></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""> <span class="Apple-converted-space"> </span>for (i=0 ; i< len; i++)<o:p class=""></o:p></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""> <span class="Apple-converted-space"> </span>A[i] = B[i] + C[i];<o:p class=""></o:p></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class="">}<o:p class=""></o:p></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><o:p class=""> </o:p></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class="">This loop get vectorize with width 32 and epilog loop get vectorized with width 8.<o:p class=""></o:p></div><div style="margin: 0in 0in 0.0001pt 0.5in; font-size: 11pt; font-family: Calibri, sans-serif; color: windowtext; text-indent: -0.25in;" class=""><span class="">a)<span style="font-style: normal; font-variant-caps: normal; font-weight: normal; font-size: 7pt; line-height: normal; font-family: 'Times New Roman';" class=""> <span class="Apple-converted-space"> </span></span></span>Please check attached IR(test.ll)<o:p class=""></o:p></div><div style="margin: 0in 0in 0.0001pt 0.5in; font-size: 11pt; font-family: Calibri, sans-serif; color: windowtext; text-indent: -0.25in;" class=""><span class="">b)<span style="font-style: normal; font-variant-caps: normal; font-weight: normal; font-size: 7pt; line-height: normal; font-family: 'Times New Roman';" class=""> <span class="Apple-converted-space"> </span></span></span>To understand how alias check result got used, check temporary “acr.val” usage.<o:p class=""></o:p></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><o:p class=""> </o:p></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class="">Regards,<o:p class=""></o:p></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class="">Ashutosh<span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);" class=""><o:p class=""></o:p></span></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);" class=""><o:p class=""> </o:p></span></div><div class=""><div style="border-style: solid none none; border-top-color: rgb(225, 225, 225); border-top-width: 1pt; padding: 3pt 0in 0in;" class=""><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><b class=""><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: windowtext;" class="">From:</span></b><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: windowtext;" class=""><span class="Apple-converted-space"> </span>Zaks, Ayal [<a class="moz-txt-link-freetext" href="mailto:ayal.zaks@intel.com" style="color: purple; text-decoration: underline;">mailto:ayal.zaks@intel.com</a>]<span class="Apple-converted-space"> </span><br class=""><b class="">Sent:</b><span class="Apple-converted-space"> </span>Sunday, February 26, 2017 10:53 PM<br class=""><b class="">To:</b><span class="Apple-converted-space"> </span>Hal Finkel<span class="Apple-converted-space"> </span><a class="moz-txt-link-rfc2396E" href="mailto:hfinkel@anl.gov" style="color: purple; text-decoration: underline;"><hfinkel@anl.gov></a>; Adam Nemet<span class="Apple-converted-space"> </span><a class="moz-txt-link-rfc2396E" href="mailto:anemet@apple.com" style="color: purple; text-decoration: underline;"><anemet@apple.com></a>; Nema, Ashutosh<span class="Apple-converted-space"> </span><a class="moz-txt-link-rfc2396E" href="mailto:Ashutosh.Nema@amd.com" style="color: purple; text-decoration: underline;"><Ashutosh.Nema@amd.com></a><br class=""><b class="">Cc:</b><span class="Apple-converted-space"> </span>llvm-dev<span class="Apple-converted-space"> </span><a class="moz-txt-link-rfc2396E" href="mailto:llvm-dev@lists.llvm.org" style="color: purple; text-decoration: underline;"><llvm-dev@lists.llvm.org></a><br class=""><b class="">Subject:</b><span class="Apple-converted-space"> </span>RE: [llvm-dev] [Proposal][RFC] Epilog loop vectorization<o:p class=""></o:p></span></div></div></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><o:p class=""> </o:p></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);" class="">+1 for “</span>just rerun the vectorizer<span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);" class="">” on the scalar remainder loop, as the proposed decision process is broken down into “first determine best VF for main loop, then determine best next EpilogVF for remainder loop” anyhow:<o:p class=""></o:p></span></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);" class=""><o:p class=""> </o:p></span></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);" class=""> const LoopVectorizationCostModel::VectorizationFactor EpilogVF =<o:p class=""></o:p></span></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);" class=""> CM.identifyNextProfitableVF(VF.Width);<o:p class=""></o:p></span></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><a moz-do-not-send="true" name="_MailEndCompose" class=""></a><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);" class=""><o:p class=""> </o:p></span></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);" class="">Raising some aspects:<o:p class=""></o:p></span></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);" class=""><o:p class=""> </o:p></span></div><p class="MsoNormal" style="margin: 0in 0in 12pt; font-size: 12pt; font-family: 'Times New Roman', serif;"><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);" class="">o The unroll factor may also affect the best EpilogVF. For instance, if UF=1 then EpilogVF < VF, as the patch currently enforces. But if UF is larger the next profitable EpilogVF could be equal to VF.<o:p class=""></o:p></span></p><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);" class="">o The scalar loop serves two purposes, as determined by its two pre-headers: either as a default in case runtime dependence checks fail, or as a remainder loop in which case it is known to be vectorizable with trip count less-than VF*UF (or equal-to it*). Would be good to keep this in mind when rerunning.<o:p class=""></o:p></span></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);" class=""><o:p class=""> </o:p></span></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);" class="">(*) Note that if original loop requiresScalarEpilogue(), the trip count of the remainder loop may be equal to VF*UF, and/or the vectorized remainder loop may too require a scalar epilogue.<o:p class=""></o:p></span></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);" class=""><o:p class=""> </o:p></span></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);" class="">o It should be interesting to see how a single masked iteration that uses the original VF, say for UF=1, works. LV should hopefully already support most of what’s needed.<o:p class=""></o:p></span></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);" class=""><o:p class=""> </o:p></span></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);" class="">o The original Trip Count clearly affects the profitability of vectorizing the remainder loop. Would be good to leverage any information that can be derived about TC either statically or based on profiling, when determining EpilogVF. Potential speedups and overheads/slowdowns could possibly be demonstrated using extreme cases; what would the best and worst cases be? Perhaps TinyTripCountVectorThreshold is also affected?<o:p class=""></o:p></span></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);" class=""><o:p class=""> </o:p></span></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);" class="">o Finally, VPlan is currently modeling how to vectorize the loop body according to the potentially profitable VF’s. It’s modelling could be used to generate vector code for both body and remainder, and to consider their combined, overall cost.<o:p class=""></o:p></span></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);" class=""><o:p class=""> </o:p></span></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);" class="">Ayal.<o:p class=""></o:p></span></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);" class=""><o:p class=""> </o:p></span></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);" class=""><o:p class=""> </o:p></span></div><div class=""><div style="border-style: solid none none; border-top-color: rgb(225, 225, 225); border-top-width: 1pt; padding: 3pt 0in 0in;" class=""><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><a moz-do-not-send="true" name="_____replyseparator" class=""></a><b class=""><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: windowtext;" class="">From:</span></b><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: windowtext;" class=""><span class="Apple-converted-space"> </span>llvm-dev [</span><a moz-do-not-send="true" href="mailto:llvm-dev-bounces@lists.llvm.org" style="color: purple; text-decoration: underline;" class=""><span style="font-size: 11pt; font-family: Calibri, sans-serif;" class="">mailto:llvm-dev-bounces@lists.llvm.org</span></a><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: windowtext;" class="">]<span class="Apple-converted-space"> </span><b class="">On Behalf Of<span class="Apple-converted-space"> </span></b>Hal Finkel via llvm-dev<br class=""><b class="">Sent:</b><span class="Apple-converted-space"> </span>Friday, February 24, 2017 00:14<br class=""><b class="">To:</b><span class="Apple-converted-space"> </span>Adam Nemet <</span><a moz-do-not-send="true" href="mailto:anemet@apple.com" style="color: purple; text-decoration: underline;" class=""><span style="font-size: 11pt; font-family: Calibri, sans-serif;" class="">anemet@apple.com</span></a><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: windowtext;" class="">>; Nema, Ashutosh <</span><a moz-do-not-send="true" href="mailto:Ashutosh.Nema@amd.com" style="color: purple; text-decoration: underline;" class=""><span style="font-size: 11pt; font-family: Calibri, sans-serif;" class="">Ashutosh.Nema@amd.com</span></a><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: windowtext;" class="">><br class=""><b class="">Cc:</b><span class="Apple-converted-space"> </span>llvm-dev <</span><a moz-do-not-send="true" href="mailto:llvm-dev@lists.llvm.org" style="color: purple; text-decoration: underline;" class=""><span style="font-size: 11pt; font-family: Calibri, sans-serif;" class="">llvm-dev@lists.llvm.org</span></a><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: windowtext;" class="">><br class=""><b class="">Subject:</b><span class="Apple-converted-space"> </span>Re: [llvm-dev] [Proposal][RFC] Epilog loop vectorization<o:p class=""></o:p></span></div></div></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><o:p class=""> </o:p></div><p style="margin-right: 0in; margin-left: 0in; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><o:p class=""> </o:p></p><div class=""><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class="">On 02/22/2017 11:52 AM, Adam Nemet via llvm-dev wrote:<o:p class=""></o:p></div></div><blockquote style="margin-top: 5pt; margin-bottom: 5pt;" class=""><div class=""><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class="">Hi Ashutosh,<o:p class=""></o:p></div></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><o:p class=""> </o:p></div><div class=""><blockquote style="margin-top: 5pt; margin-bottom: 5pt;" class=""><div class=""><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class="">On Feb 22, 2017, at 1:57 AM, Nema, Ashutosh via llvm-dev <<a moz-do-not-send="true" href="mailto:llvm-dev@lists.llvm.org" style="color: purple; text-decoration: underline;" class="">llvm-dev@lists.llvm.org</a>> wrote:<o:p class=""></o:p></div></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><o:p class=""> </o:p></div><div class=""><div class=""><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><span style="font-size: 11pt;" class="">Hi,</span><span style="font-size: 11pt; font-family: Calibri, sans-serif;" class=""><o:p class=""></o:p></span></div></div><div class=""><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><span style="font-size: 11pt;" class=""> </span><span style="font-size: 11pt; font-family: Calibri, sans-serif;" class=""><o:p class=""></o:p></span></div></div><div class=""><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><span style="font-size: 11pt;" class="">This is a proposal about epilog loop vectorization.</span><span style="font-size: 11pt; font-family: Calibri, sans-serif;" class=""><o:p class=""></o:p></span></div></div><div class=""><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><span style="font-size: 11pt;" class=""> </span><span style="font-size: 11pt; font-family: Calibri, sans-serif;" class=""><o:p class=""></o:p></span></div></div><div class=""><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><span style="font-size: 11pt;" class="">Currently Loop Vectorizer inserts an epilogue loop for handling loops that don’t have known iteration counts.</span><span style="font-size: 11pt; font-family: Calibri, sans-serif;" class=""><o:p class=""></o:p></span></div></div><div class=""><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><span style="font-size: 11pt;" class=""> </span><span style="font-size: 11pt; font-family: Calibri, sans-serif;" class=""><o:p class=""></o:p></span></div></div><div class=""><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><span style="font-size: 11pt;" class="">The Loop Vectorizer supports loops with an unknown trip count, unknown trip count may not be a multiple of the vector width, and the vectorizer has to execute the last few iterations as scalar code. It keeps a scalar copy of the loop for the remaining iterations.</span><span style="font-size: 11pt; font-family: Calibri, sans-serif;" class=""><o:p class=""></o:p></span></div></div><div class=""><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><span style="font-size: 11pt;" class=""> </span><span style="font-size: 11pt; font-family: Calibri, sans-serif;" class=""><o:p class=""></o:p></span></div></div><div class=""><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><span style="font-size: 11pt;" class="">Loop with the large width has a high possibility of executing many scalar iterations.</span><span style="font-size: 11pt; font-family: Calibri, sans-serif;" class=""><o:p class=""></o:p></span></div></div><div class=""><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><span style="font-size: 11pt;" class="">i.e. i8 data type with 256bits target register can vectorize with vector width 32, with that maximum trip count possibility for scalar(epilog) loop is 31, which is significant & worth vectorizing.</span><span style="font-size: 11pt; font-family: Calibri, sans-serif;" class=""><o:p class=""></o:p></span></div></div><div class=""><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><span style="font-size: 11pt;" class=""> </span><span style="font-size: 11pt; font-family: Calibri, sans-serif;" class=""><o:p class=""></o:p></span></div></div><div class=""><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><span style="font-size: 11pt;" class="">Large vector factor has following challenges:</span><span style="font-size: 11pt; font-family: Calibri, sans-serif;" class=""><o:p class=""></o:p></span></div></div><div style="margin-left: 0.5in;" class=""><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif; text-indent: -0.25in;" class=""><span style="font-size: 11pt;" class="">1)</span><span style="font-size: 7pt;" class=""> <span class="apple-converted-space"> </span></span><span style="font-size: 11pt;" class="">Possibility of remainder iteration is substantial.</span><span style="font-size: 11pt; font-family: Calibri, sans-serif;" class=""><o:p class=""></o:p></span></div></div><div style="margin-left: 0.5in;" class=""><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif; text-indent: -0.25in;" class=""><span style="font-size: 11pt;" class="">2)</span><span style="font-size: 7pt;" class=""> <span class="apple-converted-space"> </span></span><span style="font-size: 11pt;" class="">Actual trip count at runtime is substantial but not meeting minimum trip count to execute vector loop.</span><span style="font-size: 11pt; font-family: Calibri, sans-serif;" class=""><o:p class=""></o:p></span></div></div><div class=""><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><span style="font-size: 11pt;" class=""> </span><span style="font-size: 11pt; font-family: Calibri, sans-serif;" class=""><o:p class=""></o:p></span></div></div><div class=""><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><span style="font-size: 11pt;" class="">These challenges can be addressed by mask instructions, but these instructions are limited and may not be available to all targets.</span><span style="font-size: 11pt; font-family: Calibri, sans-serif;" class=""><o:p class=""></o:p></span></div></div><div class=""><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><span style="font-size: 11pt;" class=""> </span><span style="font-size: 11pt; font-family: Calibri, sans-serif;" class=""><o:p class=""></o:p></span></div></div><div class=""><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><span style="font-size: 11pt;" class="">By epilog vectorization our aim to vectorize epilog loop where original loop is vectorized with large vector factor and has a high possibility of executing scalar iterations.</span><span style="font-size: 11pt; font-family: Calibri, sans-serif;" class=""><o:p class=""></o:p></span></div></div><div class=""><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><span style="font-size: 11pt;" class=""> </span><span style="font-size: 11pt; font-family: Calibri, sans-serif;" class=""><o:p class=""></o:p></span></div></div><div class=""><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><span style="font-size: 11pt;" class="">This require following changes:</span><span style="font-size: 11pt; font-family: Calibri, sans-serif;" class=""><o:p class=""></o:p></span></div></div><div style="margin-left: 0.5in;" class=""><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif; text-indent: -0.25in;" class=""><span style="font-size: 11pt;" class="">1)</span><span style="font-size: 7pt;" class=""> <span class="apple-converted-space"> </span></span><span style="font-size: 11pt;" class="">Costing: Preserve all profitable vector factor.</span><span style="font-size: 11pt; font-family: Calibri, sans-serif;" class=""><o:p class=""></o:p></span></div></div><div style="margin-left: 0.5in;" class=""><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif; text-indent: -0.25in;" class=""><span style="font-size: 11pt;" class="">2)</span><span style="font-size: 7pt;" class=""> <span class="apple-converted-space"> </span></span><span style="font-size: 11pt;" class="">Transform: Create an additional vector loop with next profitable vector factor.</span><span style="font-size: 11pt; font-family: Calibri, sans-serif;" class=""><o:p class=""></o:p></span></div></div></div></blockquote><div class=""><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><o:p class=""> </o:p></div></div><div class=""><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class="">Is this something that you propose to be on by default for wide VPU architectures without masking support? I.e. how widely is this applicable? If not then perhaps a better strategy would be to just annotate the remainder loop with some metadata to limit the vectorization factor and just rerun the vectorizer.<o:p class=""></o:p></div></div></div></blockquote><p class="MsoNormal" style="margin: 0in 0in 12pt; font-size: 12pt; font-family: 'Times New Roman', serif;"><br class="">Why would this solution (annotating the remainder loop to limit vectorization and rerunning the vectorization process) not be preferred regardless?<br class=""><br class="">One issue that might be relevant here are runtime aliasing checks, which are probably going to be redundant, or partially redundant, between the different vectorized versions. Will we be able to do any necessary cleanup after the fact? Moreover, we often don't hoist (unswitch) these checks out of inner loops (perhaps because they're inside the trip-count checks?); I wonder if the proposed block structure will make this situation better or worse (or have no overall effect).<br class=""><br class="">Thanks again,<br class="">Hal<br class=""><br class=""><o:p class=""></o:p></p><blockquote style="margin-top: 5pt; margin-bottom: 5pt;" class=""><div class=""><div class=""><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><o:p class=""> </o:p></div></div><div class=""><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class="">Adam<o:p class=""></o:p></div></div><p class="MsoNormal" style="margin: 0in 0in 12pt; font-size: 12pt; font-family: 'Times New Roman', serif;"><o:p class=""> </o:p></p><blockquote style="margin-top: 5pt; margin-bottom: 5pt;" class=""><div class=""><div class=""><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><span style="font-size: 11pt;" class=""> </span><span style="font-size: 11pt; font-family: Calibri, sans-serif;" class=""><o:p class=""></o:p></span></div></div><div class=""><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><span style="font-size: 11pt;" class="">Please refer attached file (BlockLayout.png) for the details about transformed block layout.</span><span style="font-size: 11pt; font-family: Calibri, sans-serif;" class=""><o:p class=""></o:p></span></div></div><div class=""><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><span style="font-size: 11pt;" class=""> </span><span style="font-size: 11pt; font-family: Calibri, sans-serif;" class=""><o:p class=""></o:p></span></div></div><div class=""><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><span style="font-size: 11pt;" class="">Patch is available at:<span class="apple-converted-space"> </span></span><a moz-do-not-send="true" href="https://reviews.llvm.org/D30247" style="color: purple; text-decoration: underline;" class=""><span style="font-size: 11pt;" class="">https://reviews.llvm.org/D30247</span></a><span style="font-size: 11pt; font-family: Calibri, sans-serif;" class=""><o:p class=""></o:p></span></div></div><div class=""><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><span style="font-size: 11pt;" class=""> </span><span style="font-size: 11pt; font-family: Calibri, sans-serif;" class=""><o:p class=""></o:p></span></div></div><div class=""><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><span style="font-size: 11pt;" class="">Regards,</span><span style="font-size: 11pt; font-family: Calibri, sans-serif;" class=""><o:p class=""></o:p></span></div></div><div class=""><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><span style="font-size: 11pt;" class="">Ashutosh</span><span style="font-size: 11pt; font-family: Calibri, sans-serif;" class=""><o:p class=""></o:p></span></div></div><div class=""><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><span style="font-size: 11pt; font-family: Calibri, sans-serif;" class=""> <o:p class=""></o:p></span></div></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><BlockLayout.png><span style="font-size: 9pt; font-family: Helvetica, sans-serif;" class="">_______________________________________________<br class="">LLVM Developers mailing list<br class=""></span><a moz-do-not-send="true" href="mailto:llvm-dev@lists.llvm.org" style="color: purple; text-decoration: underline;" class=""><span style="font-size: 9pt; font-family: Helvetica, sans-serif; color: rgb(149, 79, 114);" class="">llvm-dev@lists.llvm.org</span></a><span style="font-size: 9pt; font-family: Helvetica, sans-serif;" class=""><br class=""></span><a moz-do-not-send="true" href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" style="color: purple; text-decoration: underline;" class=""><span style="font-size: 9pt; font-family: Helvetica, sans-serif; color: rgb(149, 79, 114);" class="">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</span></a><o:p class=""></o:p></div></div></blockquote></div><p class="MsoNormal" style="margin: 0in 0in 12pt; font-size: 12pt; font-family: 'Times New Roman', serif;"><br class=""><br class=""><br class=""><o:p class=""></o:p></p><pre style="margin: 0in 0in 0.0001pt; font-size: 10pt; font-family: 'Courier New';" class="">_______________________________________________<o:p class=""></o:p></pre><pre style="margin: 0in 0in 0.0001pt; font-size: 10pt; font-family: 'Courier New';" class="">LLVM Developers mailing list<o:p class=""></o:p></pre><pre style="margin: 0in 0in 0.0001pt; font-size: 10pt; font-family: 'Courier New';" class=""><a moz-do-not-send="true" href="mailto:llvm-dev@lists.llvm.org" style="color: purple; text-decoration: underline;" class="">llvm-dev@lists.llvm.org</a><o:p class=""></o:p></pre><pre style="margin: 0in 0in 0.0001pt; font-size: 10pt; font-family: 'Courier New';" class=""><a moz-do-not-send="true" href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" style="color: purple; text-decoration: underline;" class="">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><o:p class=""></o:p></pre></blockquote><p class="MsoNormal" style="margin: 0in 0in 12pt; font-size: 12pt; font-family: 'Times New Roman', serif;"><o:p class=""> </o:p></p><pre style="margin: 0in 0in 0.0001pt; font-size: 10pt; font-family: 'Courier New';" class="">-- <o:p class=""></o:p></pre><pre style="margin: 0in 0in 0.0001pt; font-size: 10pt; font-family: 'Courier New';" class="">Hal Finkel<o:p class=""></o:p></pre><pre style="margin: 0in 0in 0.0001pt; font-size: 10pt; font-family: 'Courier New';" class="">Lead, Compiler Technology and Programming Languages<o:p class=""></o:p></pre><pre style="margin: 0in 0in 0.0001pt; font-size: 10pt; font-family: 'Courier New';" class="">Leadership Computing Facility<o:p class=""></o:p></pre><pre style="margin: 0in 0in 0.0001pt; font-size: 10pt; font-family: 'Courier New';" class="">Argonne National Laboratory<o:p class=""></o:p></pre><p style="margin-right: 0in; margin-left: 0in; font-size: 12pt; font-family: 'Times New Roman', serif;" class="">---------------------------------------------------------------------<br class="">Intel Israel (74) Limited<o:p class=""></o:p></p><p style="margin-right: 0in; margin-left: 0in; font-size: 12pt; font-family: 'Times New Roman', serif;" class="">This e-mail and any attachments may contain confidential material for<br class="">the sole use of the intended recipient(s). Any review or distribution<br class="">by others is strictly prohibited. If you are not the intended<br class="">recipient, please contact the sender and delete all copies.<o:p class=""></o:p></p></div></blockquote><br style="font-family: Helvetica; font-size: 10px; font-style: normal; font-variant-caps: 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; background-color: rgb(255, 255, 255);" class=""><pre class="moz-signature" cols="72" style="margin: 0in 0in 0.0001pt; font-size: 10pt; font-family: 'Courier New'; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px; background-color: rgb(255, 255, 255);">--
Hal Finkel
Lead, Compiler Technology and Programming Languages
Leadership Computing Facility
Argonne National Laboratory</pre></div></blockquote></div><br class=""></body></html>