<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 May 20, 2016, at 11:59 AM, Saito, Hideki <<a href="mailto:hideki.saito@intel.com" class="">hideki.saito@intel.com</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><div class="WordSection1" style="page: WordSection1; 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 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="">Adam, thanks for the clarification.<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="">FP induction analysis should be useful for other loop optimizations that care about cross-iteration dependence.<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="">Thus, I think the mechanism is best implemented as an analysis or a utility, as opposed to something confined<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="">inside vectorizer. Any objections in this general direction?</span></div></div></div></blockquote><div><br class=""></div><div>Agreed, we usually put these in Transforms/Utils/LoopUtils.h,cpp. (Obviously the goal here is not to provide an alternative to SCEV but to share simple “pattern-matching” code between the loop optimizations.)</div><div><br class=""></div><div>Adam</div><div><br class=""></div><blockquote type="cite" class=""><div class=""><div class="WordSection1" style="page: WordSection1; 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 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 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="">Thanks,<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="">Hideki<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=""><a name="_MailEndCompose" class=""><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);" class=""><o:p class=""> </o:p></span></a></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 name="_____replyseparator" class=""></a><b class=""><span style="font-size: 11pt; font-family: Calibri, sans-serif;" class="">From:</span></b><span style="font-size: 11pt; font-family: Calibri, sans-serif;" class=""><span class="Apple-converted-space"> </span><a href="mailto:anemet@apple.com" class="">anemet@apple.com</a> [<a href="mailto:anemet@apple.com" class="">mailto:anemet@apple.com</a>]<span class="Apple-converted-space"> </span><br class=""><b class="">Sent:</b><span class="Apple-converted-space"> </span>Friday, May 20, 2016 11:32 AM<br class=""><b class="">To:</b><span class="Apple-converted-space"> </span>Saito, Hideki <<a href="mailto:hideki.saito@intel.com" class="">hideki.saito@intel.com</a>><br class=""><b class="">Cc:</b><span class="Apple-converted-space"> </span>Chandler Carruth <<a href="mailto:chandlerc@google.com" class="">chandlerc@google.com</a>>; Demikhovsky, Elena <<a href="mailto:elena.demikhovsky@intel.com" class="">elena.demikhovsky@intel.com</a>>; Sanjoy Das <<a href="mailto:sanjoy@playingwithpointers.com" class="">sanjoy@playingwithpointers.com</a>>; llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org" class="">llvm-dev@lists.llvm.org</a>>; Andrew Trick <<a href="mailto:atrick@apple.com" class="">atrick@apple.com</a>><br class=""><b class="">Subject:</b><span class="Apple-converted-space"> </span>Re: [llvm-dev] Working on FP SCEV Analysis<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 class=""><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class="">Hi Hideki,<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=""><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="">I like this summary overall, thanks. More below.<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 May 20, 2016, at 10:04 AM, Saito, Hideki <<a href="mailto:hideki.saito@intel.com" style="color: purple; text-decoration: underline;" class="">hideki.saito@intel.com</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; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);" class=""> </span><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=""><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);" class="">To the best of my experience, handling case B (secondary induction) is must-have, and if I’m not mistaken,</span><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=""><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);" class="">people aren’t opposed to that.</span><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=""><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);" class=""> </span><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=""><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);" class="">For me, handling case A (primary induction) is “why not?”, but I certainly admit that that can be very naïve</span><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=""><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);" class="">thinking coming from lack of good understanding on SCEV and their proper usages. Now, let’s assume we</span><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=""><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);" class="">can postpone discussion about case A. What is the best approach to handle case B? Let me summarize</span><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=""><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);" class="">the discussion so far. Hope I didn’t miss anything.</span><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=""><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);" class=""> </span><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=""><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);" class="">1)</span><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=""><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);" class="">Extend SCEV was the initial approach taken by Elena.</span><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=""><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);" class=""> Elena thinks this solution ”looks very structured”.</span><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=""><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);" class=""> If I’m not mistaken, some people think this is overkill and overly complicates already complicated SCEV.</span><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=""><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);" class=""> Anyone care to look at the patch Elena came up with?</span><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=""><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);" class="">2)</span><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=""><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);" class="">IndVarSimplify::handleFloatingPointIV (mentioned by Andy)</span><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=""><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);" class=""> This transforms integer-valued FP (primary) IV into integer IV and convert.</span><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=""><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);" class=""> Chandler says most of Graphics shading language use case mentioned by Owen</span><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=""><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);" class=""> should be handled here.</span><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=""><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);" class=""> It certainly has the logic of detecting FP induction, but Andy punted discussions<br class=""> on non-integer valued IV issues to MichaelZ and Adam.</span><o:p class=""></o:p></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="">My understanding is that we only need this for *A* not for *B*.<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=""><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="">On the specific issue of non-integer values, there is simply no attempt made in the code to deal with them. That said, I think it should be possible to compute the trip count and then derive an integer induction variable controlling the loop.<o:p class=""></o:p></div></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><br class=""><br class=""><o:p class=""></o:p></div><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; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);" class="">3)</span><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="">extend InductionDescriptor::isInductionPHI in the vectorizer to directly analyze the PHIs without SCEV support<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=""><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);" class="">(mentioned by Adam)</span><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=""><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);" class=""> If this is the standard way to deal with all secondary inductions, it certainly looks attractive.</span><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=""><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);" class=""> Elena, would you try doing this and compare with 1)?</span><o:p class=""></o:p></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="">Just to clarify, the code is currently structured to check if the PHI is an add-recurrence that was detected by SCEV. The idea is to add a fall-back to analyze the PHI directly if its type is a float.<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=""><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="">There is already precedence for such things in LV. We support more reductions (including floating-point) than what SCEV can analyze, therefore RecurrenceDescriptor::AddReductionVar needs to analyze PHIs directly.<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=""><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><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><br class=""><br class=""><o:p class=""></o:p></div><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; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);" class=""> </span><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=""><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);" class="">Thanks,</span><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=""><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);" class="">Hideki</span><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=""><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);" class=""> </span><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=""><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);" class="">----------------------</span><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=""><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);" class="">I looked at what our FORTRAN compiler (non-LLVM) does for the following (x, y, z, and f are float by default typing,</span><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=""><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);" class="">based on names).</span><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=""><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);" class=""> </span><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=""><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);" class=""> subroutine foo(x, y, z, A, N)</span><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=""><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);" class=""> double precision A(N)</span><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=""><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);" class=""> do f = x, y, z</span><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=""><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);" class=""> A(f) = f</span><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=""><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);" class=""> enddo</span><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=""><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);" class=""> end</span><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=""><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);" class=""> </span><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=""><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);" class="">The frontend computes the trip count outside of the loop (per language rule) and uses an integer primary</span><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=""><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);" class="">induction variable (compile-generated) for loop control. So, (future) FORTRAN usage doesn’t seem to be</span><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=""><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);" class="">a good example for promoting support for case A (= FP primary induction variable).</span><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=""><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);" class=""> </span><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=""><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);" class=""> </span><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=""><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);" class=""> </span><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=""><b class=""><span style="font-size: 11pt; font-family: Calibri, sans-serif;" class="">From:</span></b><span class="apple-converted-space"><span style="font-size: 11pt; font-family: Calibri, sans-serif;" class=""> </span></span><span style="font-size: 11pt; font-family: Calibri, sans-serif;" class="">Chandler Carruth [<a href="mailto:chandlerc@google.com" style="color: purple; text-decoration: underline;" class="">mailto:chandlerc@google.com</a>]<span class="apple-converted-space"> </span><br class=""><b class="">Sent:</b><span class="apple-converted-space"> </span>Thursday, May 19, 2016 7:03 PM<br class=""><b class="">To:</b><span class="apple-converted-space"> </span>Demikhovsky, Elena <<a href="mailto:elena.demikhovsky@intel.com" style="color: purple; text-decoration: underline;" class="">elena.demikhovsky@intel.com</a>>;<span class="Apple-converted-space"> </span><a href="mailto:anemet@apple.com" style="color: purple; text-decoration: underline;" class="">anemet@apple.com</a>; Sanjoy Das <<a href="mailto:sanjoy@playingwithpointers.com" style="color: purple; text-decoration: underline;" class="">sanjoy@playingwithpointers.com</a>><br class=""><b class="">Cc:</b><span class="apple-converted-space"> </span>Saito, Hideki <<a href="mailto:hideki.saito@intel.com" style="color: purple; text-decoration: underline;" class="">hideki.saito@intel.com</a>>; llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org" style="color: purple; text-decoration: underline;" class="">llvm-dev@lists.llvm.org</a>>; Andrew Trick <<a href="mailto:atrick@apple.com" style="color: purple; text-decoration: underline;" class="">atrick@apple.com</a>><br class=""><b class="">Subject:</b><span class="apple-converted-space"> </span>Re: [llvm-dev] Working on FP SCEV Analysis</span><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=""> <o:p class=""></o:p></div></div><div class=""><div class=""><div class=""><div class=""><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class="">On Thu, May 19, 2016 at 7:03 AM Demikhovsky, Elena <<a href="mailto:elena.demikhovsky@intel.com" style="color: purple; text-decoration: underline;" class=""><span style="color: purple;" class="">elena.demikhovsky@intel.com</span></a>> wrote:<o:p class=""></o:p></div></div></div><blockquote style="border-style: none none none solid; border-left-color: rgb(204, 204, 204); border-left-width: 1pt; padding: 0in 0in 0in 6pt; margin: 5pt 0in 5pt 4.8pt;" class=""><div class=""><div class=""><div class=""><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class="">> One option would be to extend InductionDescriptor<a name="m_-4446943922801636445__MailEndCompose" class="">::isInductionPHI in the vectorizer to directly analyze the PHIs without SCEV support as Sanjoy suggested. I *think* that that could be sufficient to handle case B.</a><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=""><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);" class=""> </span><o:p class=""></o:p></div></div></div></div><div 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; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);" class="">I implemented this with FP SCEV and the code looks very structured, including SCEVExpander. Extending the existing structures without implementing FP SCEV will be problematic.</span><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=""><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);" class="">And my end goal is to handle case *<b class="">A</b>*.</span><o:p class=""></o:p></div></div></div></div></blockquote><div class=""><div class=""><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class="">Ok, but there have been *numerous* requests for an explanation of why this is important, and that hasn't emerged yet.<o:p class=""></o:p></div></div></div><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><div class=""><div class=""><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class="">We really need to have a clear understanding of the relative importance of solving these problems in order to understand the best approach.<o:p class=""></o:p></div></div></div><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><blockquote style="border-style: none none none solid; border-left-color: rgb(204, 204, 204); border-left-width: 1pt; padding: 0in 0in 0in 6pt; margin: 5pt 0in 5pt 4.8pt;" class=""><div 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; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);" class=""> </span><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=""><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: rgb(31, 73, 125);" class=""> </span><o:p class=""></o:p></div></div><div class=""><div style="margin-left: 0.5in;" class=""><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><span style="font-family: Calibri, sans-serif; color: rgb(47, 84, 150);" class="">-</span><span style="font-size: 7pt; color: rgb(47, 84, 150);" class=""> <span class="apple-converted-space"> </span></span><b class=""><i class=""><span style="color: rgb(47, 84, 150);" class=""> Elena</span></i></b><o:p class=""></o:p></div></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; color: rgb(31, 73, 125);" class=""> </span><o:p class=""></o:p></div></div><div style="border-style: none solid none none; border-right-color: blue; border-right-width: 1.5pt; padding: 0in;" class=""><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 class=""><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><a name="m_-4446943922801636445______replyseparat" class=""></a><b class=""><span style="font-size: 11pt; font-family: Calibri, sans-serif;" class="">From:</span></b><span class="apple-converted-space"><span style="font-size: 11pt; font-family: Calibri, sans-serif;" class=""> </span></span><a href="mailto:anemet@apple.com" target="_blank" style="color: purple; text-decoration: underline;" class=""><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: purple;" class="">anemet@apple.com</span></a><span class="apple-converted-space"><span style="font-size: 11pt; font-family: Calibri, sans-serif;" class=""> </span></span><span style="font-size: 11pt; font-family: Calibri, sans-serif;" class="">[mailto:</span><a href="mailto:anemet@apple.com" target="_blank" style="color: purple; text-decoration: underline;" class=""><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: purple;" class="">anemet@apple.com</span></a><span style="font-size: 11pt; font-family: Calibri, sans-serif;" class="">]<span class="apple-converted-space"> </span><br class=""><b class="">Sent:</b><span class="apple-converted-space"> </span>Thursday, May 19, 2016 07:43<br class=""><b class="">To:</b><span class="apple-converted-space"> </span>Sanjoy Das <</span><a href="mailto:sanjoy@playingwithpointers.com" target="_blank" style="color: purple; text-decoration: underline;" class=""><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: purple;" class="">sanjoy@playingwithpointers.com</span></a><span style="font-size: 11pt; font-family: Calibri, sans-serif;" class="">><br class=""><b class="">Cc:</b><span class="apple-converted-space"> </span>Demikhovsky, Elena <</span><a href="mailto:elena.demikhovsky@intel.com" target="_blank" style="color: purple; text-decoration: underline;" class=""><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: purple;" class="">elena.demikhovsky@intel.com</span></a><span style="font-size: 11pt; font-family: Calibri, sans-serif;" class="">>; Saito, Hideki <</span><a href="mailto:hideki.saito@intel.com" target="_blank" style="color: purple; text-decoration: underline;" class=""><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: purple;" class="">hideki.saito@intel.com</span></a><span style="font-size: 11pt; font-family: Calibri, sans-serif;" class="">>; llvm-dev <</span><a href="mailto:llvm-dev@lists.llvm.org" target="_blank" style="color: purple; text-decoration: underline;" class=""><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: purple;" class="">llvm-dev@lists.llvm.org</span></a><span style="font-size: 11pt; font-family: Calibri, sans-serif;" class="">>; Andrew Trick <</span><a href="mailto:atrick@apple.com" target="_blank" style="color: purple; text-decoration: underline;" class=""><span style="font-size: 11pt; font-family: Calibri, sans-serif; color: purple;" class="">atrick@apple.com</span></a><span style="font-size: 11pt; font-family: Calibri, sans-serif;" class="">></span><o:p class=""></o:p></div></div></div></div></div></div></div><div class=""><div class=""><div style="border-style: none solid none none; border-right-color: blue; border-right-width: 1.5pt; padding: 0in;" class=""><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 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=""><br class=""><b class="">Subject:</b><span class="apple-converted-space"> </span>Re: [llvm-dev] Working on FP SCEV Analysis</span><o:p class=""></o:p></div></div></div></div></div></div></div><div class=""><div class=""><div style="border-style: none solid none none; border-right-color: blue; border-right-width: 1.5pt; padding: 0in;" 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=""> <o:p class=""></o:p></div></div><div class=""><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="">On May 18, 2016, at 12:17 PM, Sanjoy Das via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org" target="_blank" style="color: purple; text-decoration: underline;" class=""><span style="color: purple;" class="">llvm-dev@lists.llvm.org</span></a>> wrote:<o:p class=""></o:p></div></div></div></blockquote></div></div></div></div><div class=""><div class=""><div style="border-style: none solid none none; border-right-color: blue; border-right-width: 1.5pt; padding: 0in;" class=""><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=""> <o:p class=""></o:p></div></div><div class=""><p class="MsoNormal" style="margin: 0in 0in 12pt; font-size: 12pt; font-family: 'Times New Roman', serif;"><span style="font-size: 7.5pt; font-family: Helvetica, sans-serif;" class=""><br class=""><br class="">Demikhovsky, Elena wrote:</span><o:p class=""></o:p></p><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=""><span style="font-size: 7.5pt; font-family: Helvetica, sans-serif;" class="">> Even then, I'd personally want to see further evidence of why the<br class="">correct solution is to model the floating point IV in SCEV rather than<br class="">find a more powerful way of converting the IV to an integer that models<br class="">> the non-integer values taken on by the IV. As an example, if the use<br class="">case is the following code with appropriate flags to relax IEEE<br class="">semantics so this looks like normal algabra etc:<br class=""><br class="">> for (float f = 0.01f; f < 1.0f; f += 0.01f) ç **A**<br class=""><br class="">...<br class=""><br class="">> I'd rather see us cleverly turn it into:<br class=""><br class="">> float f = 0.01f;<br class=""><br class="">> for (int i = 1; i < 100; i += 1, f += 0.01f) ç **B**<br class=""><br class="">I can later try to enhance IndVarSimplify::handleFloatingPointIV() in<br class="">order to convert**A** to **B**.<br class=""><br class="">But **B** is exactly the case I’m starting from. The main IV “i” is<br class="">integer. The variable “f” is also considered as IV in this loop.<br class=""><br class="">And this loop is not vectorized because “f” is floating point.<br class=""><br class="">I don’t think that the case **B** is uncommon.</span><o:p class=""></o:p></div></div></blockquote><div class=""><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><span style="font-size: 7.5pt; font-family: Helvetica, sans-serif;" class=""><br class="">If B is the case we actually care about, I'd say changing SCEV to work with floating points is an overkill. How would you expect an SCEVFAddExpr to help vectorize B, other than tell you what the initial value and the increment is (and these can be found with a simple value analysis)?</span><o:p class=""></o:p></div></div></div></blockquote></div></div></div></div><div class=""><div class=""><div style="border-style: none solid none none; border-right-color: blue; border-right-width: 1.5pt; padding: 0in;" class=""><div 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><div class=""><div class=""><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class="">One option would be to extend InductionDescriptor::isInductionPHI in the vectorizer to directly analyze the PHIs without SCEV support as Sanjoy suggested. I *think* that that could be sufficient to handle case B.<o:p class=""></o:p></div></div></div><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><div class=""><div class=""><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class="">Then if we find other pressing cases to handle we can rethink the strategy.<o:p class=""></o:p></div></div></div><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><div class=""><div class=""><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class="">Also the current diagnostics is pretty bad for Hideki’s testcase with TTT as float. This is what we currently report with -Rpass-analysis=loop-vectorize:<o:p class=""></o:p></div></div></div><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></div></div></div></div><div class=""><div class=""><div style="border-style: none solid none none; border-right-color: blue; border-right-width: 1.5pt; padding: 0in;" class=""><blockquote style="margin: 5pt 0in 5pt 30pt;" class=""><div class=""><div class=""><div class=""><div class=""><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class="">/tmp/sss.c:3:6: remark: loop not vectorized: value that could not be<o:p class=""></o:p></div></div></div></div></div><div class=""><div class=""><div class=""><div class=""><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""> identified as reduction is used outside the loop<o:p class=""></o:p></div></div></div></div></div><div class=""><div class=""><div class=""><div class=""><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""> [-Rpass-analysis=loop-vectorize]<o:p class=""></o:p></div></div></div></div></div></blockquote><div class=""><div 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><div class=""><div class=""><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class="">I have no clue why we say that the value is used outside the loop. I think this should just say that we have a loop-variant value that we couldn’t identify either as an induction or as a reduction.<o:p class=""></o:p></div></div></div><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><div class=""><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></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=""><p class="MsoNormal" style="margin: 0in 0in 12pt; font-size: 12pt; font-family: 'Times New Roman', serif;"><span style="font-size: 7.5pt; font-family: Helvetica, sans-serif;" class=""><br class="">If we're interested in handling complex variants of A directly: computing trip counts, proving away predicates etc. without translating the loops to use integer IVs (perhaps because we can't legally do so), then I can see FP-SCEV as a reasonable implementation strategy, but it looks like the general consensus is that such cases are rare and generally not worth optimizing?<br class=""><br class="">-- Sanjoy<br class=""><br class=""><br class=""></span><o:p class=""></o:p></p><blockquote style="margin-top: 5pt; margin-bottom: 5pt;" class=""><p class="MsoNormal" style="margin: 0in 0in 12pt; font-size: 12pt; font-family: 'Times New Roman', serif;"><span style="font-size: 7.5pt; font-family: Helvetica, sans-serif;" class=""><br class="">-*/Elena/*<br class=""><br class="">---------------------------------------------------------------------<br class="">Intel Israel (74) Limited<br class=""><br 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.</span><o:p class=""></o:p></p></blockquote><div class=""><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><span style="font-size: 7.5pt; font-family: Helvetica, sans-serif;" class="">_______________________________________________<br class="">LLVM Developers mailing list<br class=""></span><a href="mailto:llvm-dev@lists.llvm.org" target="_blank" style="color: purple; text-decoration: underline;" class=""><span style="font-size: 7.5pt; font-family: Helvetica, sans-serif; color: purple;" class="">llvm-dev@lists.llvm.org</span></a><span style="font-size: 7.5pt; font-family: Helvetica, sans-serif;" class=""><br class=""></span><a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" target="_blank" style="color: purple; text-decoration: underline;" class=""><span style="font-size: 7.5pt; font-family: Helvetica, sans-serif; color: purple;" class="">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</span></a><o:p class=""></o:p></div></div></div></blockquote></div><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></div></div><div class=""><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class="">---------------------------------------------------------------------<br class="">Intel Israel (74) Limited<o:p class=""></o:p></div><div style="margin: 0in 0in 0.0001pt; 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.</div></div></blockquote></div></div></div></blockquote></div></div></div></blockquote></div><br class=""></body></html>