<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:58 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-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;"><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="">Michael, she hasn’t posted a patch (or the link) yet, but she wrote “</span><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</span><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="">So, there is actual code that can be looked at. May have to wait until Sunday morning in Israel.</span></div></div></div></blockquote>Ah ok, no worries then. I just thought I missed it.</div><div><br class=""></div><div>Michael<br class=""><blockquote type="cite" class=""><div class=""><div class="WordSection1" style="page: WordSection1; font-family: Helvetica; font-size: 12px; 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;"><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=""><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:mzolotukhin@apple.com" class="">mzolotukhin@apple.com</a> [<a href="mailto:mzolotukhin@apple.com" class="">mailto:mzolotukhin@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:38 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>>; Adam Nemet <<a href="mailto:anemet@apple.com" class="">anemet@apple.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>><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 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 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="">Thanks for the summary!<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 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 via llvm-dev <<a 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; 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></blockquote><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class="">Sorry if I missed it. Could you please post a link to the patch here? I’ve been mostly speculating on how complicated the SCEV solution would be, if the actual patch happens to be really simple and obvious, we can go this way.<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="">Michael<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=""><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="">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 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 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.<o:p class=""></o:p></div></div></blockquote></div></div><div style="margin: 0in 0in 0.0001pt; font-size: 12pt; font-family: 'Times New Roman', serif;" class=""><span style="font-size: 9pt; font-family: Helvetica, sans-serif;" class="">_______________________________________________<br class="">LLVM Developers mailing list<br class=""><a href="mailto:llvm-dev@lists.llvm.org" style="color: purple; text-decoration: underline;" class="">llvm-dev@lists.llvm.org</a><br class=""><a 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></span></div></div></blockquote></div></div></div></div></blockquote></div><br class=""></body></html>