<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<meta name="Generator" content="Microsoft Word 15 (filtered medium)">
<style><!--
/* Font Definitions */
@font-face
{font-family:Helvetica;
panose-1:2 11 6 4 2 2 2 2 2 4;}
@font-face
{font-family:"MS Mincho";
panose-1:2 2 6 9 4 2 5 8 3 4;}
@font-face
{font-family:"Cambria Math";
panose-1:2 4 5 3 5 4 6 3 2 4;}
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
@font-face
{font-family:"\@MS Mincho";
panose-1:2 2 6 9 4 2 5 8 3 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0in;
margin-bottom:.0001pt;
font-size:12.0pt;
font-family:"Times New Roman",serif;}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:blue;
text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
{mso-style-priority:99;
color:purple;
text-decoration:underline;}
span.apple-converted-space
{mso-style-name:apple-converted-space;}
span.EmailStyle18
{mso-style-type:personal-reply;
font-family:"Calibri",sans-serif;
color:#1F497D;}
.MsoChpDefault
{mso-style-type:export-only;
font-size:10.0pt;}
@page WordSection1
{size:8.5in 11.0in;
margin:1.0in 1.0in 1.0in 1.0in;}
div.WordSection1
{page:WordSection1;}
--></style><!--[if gte mso 9]><xml>
<o:shapedefaults v:ext="edit" spidmax="1026" />
</xml><![endif]--><!--[if gte mso 9]><xml>
<o:shapelayout v:ext="edit">
<o:idmap v:ext="edit" data="1" />
</o:shapelayout></xml><![endif]-->
</head>
<body lang="EN-US" link="blue" vlink="purple">
<div class="WordSection1">
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">Adam, thanks for the clarification.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">FP induction analysis should be useful for other loop optimizations that care about cross-iteration dependence.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">Thus, I think the mechanism is best implemented as an analysis or a utility, as opposed to something confined<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">inside vectorizer. Any objections in this general direction?<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">Thanks,<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">Hideki<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><a name="_MailEndCompose"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"><o:p> </o:p></span></a></p>
<div>
<div style="border:none;border-top:solid #E1E1E1 1.0pt;padding:3.0pt 0in 0in 0in">
<p class="MsoNormal"><a name="_____replyseparator"></a><b><span style="font-size:11.0pt;font-family:"Calibri",sans-serif">From:</span></b><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"> anemet@apple.com [mailto:anemet@apple.com]
<br>
<b>Sent:</b> Friday, May 20, 2016 11:32 AM<br>
<b>To:</b> Saito, Hideki <hideki.saito@intel.com><br>
<b>Cc:</b> Chandler Carruth <chandlerc@google.com>; Demikhovsky, Elena <elena.demikhovsky@intel.com>; Sanjoy Das <sanjoy@playingwithpointers.com>; llvm-dev <llvm-dev@lists.llvm.org>; Andrew Trick <atrick@apple.com><br>
<b>Subject:</b> Re: [llvm-dev] Working on FP SCEV Analysis<o:p></o:p></span></p>
</div>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
<div>
<p class="MsoNormal">Hi Hideki,<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">I like this summary overall, thanks. More below.<o:p></o:p></p>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
<div>
<blockquote style="margin-top:5.0pt;margin-bottom:5.0pt">
<div>
<p class="MsoNormal">On May 20, 2016, at 10:04 AM, Saito, Hideki <<a href="mailto:hideki.saito@intel.com">hideki.saito@intel.com</a>> wrote:<o:p></o:p></p>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
<div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"> </span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">To the best of my experience, handling case B (secondary induction) is must-have, and if I’m not mistaken,</span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">people aren’t opposed to that.</span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"> </span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">For me, handling case A (primary induction) is “why not?”, but I certainly admit that that can be very naïve</span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">thinking coming from lack of good understanding on SCEV and their proper usages. Now, let’s assume we</span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">can postpone discussion about case A. What is the best approach to handle case B? Let me summarize</span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">the discussion so far. Hope I didn’t miss anything.</span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"> </span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">1)</span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">Extend SCEV was the initial approach taken by Elena.</span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"> Elena thinks this solution ”looks very structured”.</span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"> If I’m not mistaken, some people think this is overkill and overly complicates already complicated SCEV.</span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"> Anyone care to look at the patch Elena came up with?</span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">2)</span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">IndVarSimplify::handleFloatingPointIV (mentioned by Andy)</span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"> This transforms integer-valued FP (primary) IV into integer IV and convert.</span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"> Chandler says most of Graphics shading language use case mentioned by Owen</span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"> should be handled here.</span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"> It certainly has the logic of detecting FP induction, but Andy punted discussions<br>
on non-integer valued IV issues to MichaelZ and Adam.</span><o:p></o:p></p>
</div>
</div>
</blockquote>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">My understanding is that we only need this for *A* not for *B*.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">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></o:p></p>
</div>
<p class="MsoNormal"><br>
<br>
<o:p></o:p></p>
<blockquote style="margin-top:5.0pt;margin-bottom:5.0pt">
<div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">3)</span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">extend InductionDescriptor::isInductionPHI in the vectorizer to directly analyze the PHIs without SCEV support<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">(mentioned by Adam)</span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"> If this is the standard way to deal with all secondary inductions, it certainly looks attractive.</span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"> Elena, would you try doing this and compare with 1)?</span><o:p></o:p></p>
</div>
</div>
</blockquote>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">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></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">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></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">Adam<o:p></o:p></p>
</div>
<p class="MsoNormal"><br>
<br>
<o:p></o:p></p>
<blockquote style="margin-top:5.0pt;margin-bottom:5.0pt">
<div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"> </span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">Thanks,</span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">Hideki</span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"> </span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">----------------------</span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">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></o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">based on names).</span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"> </span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"> subroutine foo(x, y, z, A, N)</span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"> double precision A(N)</span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"> do f = x, y, z</span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"> A(f) = f</span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"> enddo</span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"> end</span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"> </span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">The frontend computes the trip count outside of the loop (per language rule) and uses an integer primary</span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">induction variable (compile-generated) for loop control. So, (future) FORTRAN usage doesn’t seem to be</span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">a good example for promoting support for case A (= FP primary induction variable).</span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"> </span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"> </span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"> </span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><b><span style="font-size:11.0pt;font-family:"Calibri",sans-serif">From:</span></b><span class="apple-converted-space"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"> </span></span><span style="font-size:11.0pt;font-family:"Calibri",sans-serif">Chandler
Carruth [<a href="mailto:chandlerc@google.com">mailto:chandlerc@google.com</a>]<span class="apple-converted-space"> </span><br>
<b>Sent:</b><span class="apple-converted-space"> </span>Thursday, May 19, 2016 7:03 PM<br>
<b>To:</b><span class="apple-converted-space"> </span>Demikhovsky, Elena <<a href="mailto:elena.demikhovsky@intel.com">elena.demikhovsky@intel.com</a>>;
<a href="mailto:anemet@apple.com">anemet@apple.com</a>; Sanjoy Das <<a href="mailto:sanjoy@playingwithpointers.com">sanjoy@playingwithpointers.com</a>><br>
<b>Cc:</b><span class="apple-converted-space"> </span>Saito, Hideki <<a href="mailto:hideki.saito@intel.com">hideki.saito@intel.com</a>>; llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a>>; Andrew Trick <<a href="mailto:atrick@apple.com">atrick@apple.com</a>><br>
<b>Subject:</b><span class="apple-converted-space"> </span>Re: [llvm-dev] Working on FP SCEV Analysis</span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"> <o:p></o:p></p>
</div>
<div>
<div>
<div>
<div>
<p class="MsoNormal">On Thu, May 19, 2016 at 7:03 AM Demikhovsky, Elena <<a href="mailto:elena.demikhovsky@intel.com"><span style="color:purple">elena.demikhovsky@intel.com</span></a>> wrote:<o:p></o:p></p>
</div>
</div>
<blockquote style="border:none;border-left:solid #CCCCCC 1.0pt;padding:0in 0in 0in 6.0pt;margin-left:4.8pt;margin-top:5.0pt;margin-right:0in;margin-bottom:5.0pt">
<div>
<div>
<div>
<p class="MsoNormal">> One option would be to extend InductionDescriptor<a name="m_-4446943922801636445__MailEndCompose">::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></o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"> </span><o:p></o:p></p>
</div>
</div>
</div>
<div>
<div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">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></o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">And my end goal is to handle case *<b>A</b>*.</span><o:p></o:p></p>
</div>
</div>
</div>
</blockquote>
<div>
<div>
<p class="MsoNormal">Ok, but there have been *numerous* requests for an explanation of why this is important, and that hasn't emerged yet.<o:p></o:p></p>
</div>
</div>
<div>
<div>
<p class="MsoNormal"> <o:p></o:p></p>
</div>
</div>
<div>
<div>
<p class="MsoNormal">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></o:p></p>
</div>
</div>
<div>
<div>
<p class="MsoNormal"> <o:p></o:p></p>
</div>
</div>
<blockquote style="border:none;border-left:solid #CCCCCC 1.0pt;padding:0in 0in 0in 6.0pt;margin-left:4.8pt;margin-top:5.0pt;margin-right:0in;margin-bottom:5.0pt">
<div>
<div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"> </span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"> </span><o:p></o:p></p>
</div>
<div>
<div style="margin-left:.5in">
<p class="MsoNormal"><span style="font-family:"Calibri",sans-serif;color:#2F5496">-</span><span style="font-size:7.0pt;color:#2F5496"> <span class="apple-converted-space"> </span></span><b><i><span style="color:#2F5496"> Elena</span></i></b><o:p></o:p></p>
</div>
</div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"> </span><o:p></o:p></p>
</div>
<div style="border:none;border-right:solid blue 1.5pt;padding:0in 0in 0in 0in">
<div>
<div style="border:none;border-top:solid #E1E1E1 1.0pt;padding:3.0pt 0in 0in 0in">
<div>
<p class="MsoNormal"><a name="m_-4446943922801636445______replyseparat"></a><b><span style="font-size:11.0pt;font-family:"Calibri",sans-serif">From:</span></b><span class="apple-converted-space"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"> </span></span><a href="mailto:anemet@apple.com" target="_blank"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:purple">anemet@apple.com</span></a><span class="apple-converted-space"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"> </span></span><span style="font-size:11.0pt;font-family:"Calibri",sans-serif">[mailto:</span><a href="mailto:anemet@apple.com" target="_blank"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:purple">anemet@apple.com</span></a><span style="font-size:11.0pt;font-family:"Calibri",sans-serif">]<span class="apple-converted-space"> </span><br>
<b>Sent:</b><span class="apple-converted-space"> </span>Thursday, May 19, 2016 07:43<br>
<b>To:</b><span class="apple-converted-space"> </span>Sanjoy Das <</span><a href="mailto:sanjoy@playingwithpointers.com" target="_blank"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:purple">sanjoy@playingwithpointers.com</span></a><span style="font-size:11.0pt;font-family:"Calibri",sans-serif">><br>
<b>Cc:</b><span class="apple-converted-space"> </span>Demikhovsky, Elena <</span><a href="mailto:elena.demikhovsky@intel.com" target="_blank"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:purple">elena.demikhovsky@intel.com</span></a><span style="font-size:11.0pt;font-family:"Calibri",sans-serif">>;
Saito, Hideki <</span><a href="mailto:hideki.saito@intel.com" target="_blank"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:purple">hideki.saito@intel.com</span></a><span style="font-size:11.0pt;font-family:"Calibri",sans-serif">>; llvm-dev
<</span><a href="mailto:llvm-dev@lists.llvm.org" target="_blank"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:purple">llvm-dev@lists.llvm.org</span></a><span style="font-size:11.0pt;font-family:"Calibri",sans-serif">>; Andrew Trick
<</span><a href="mailto:atrick@apple.com" target="_blank"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:purple">atrick@apple.com</span></a><span style="font-size:11.0pt;font-family:"Calibri",sans-serif">></span><o:p></o:p></p>
</div>
</div>
</div>
</div>
</div>
</div>
<div>
<div>
<div style="border:none;border-right:solid blue 1.5pt;padding:0in 0in 0in 0in">
<div>
<div style="border:none;border-top:solid #E1E1E1 1.0pt;padding:3.0pt 0in 0in 0in">
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"><br>
<b>Subject:</b><span class="apple-converted-space"> </span>Re: [llvm-dev] Working on FP SCEV Analysis</span><o:p></o:p></p>
</div>
</div>
</div>
</div>
</div>
</div>
<div>
<div>
<div style="border:none;border-right:solid blue 1.5pt;padding:0in 0in 0in 0in">
<div>
<p class="MsoNormal"> <o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"> <o:p></o:p></p>
</div>
<div>
<blockquote style="margin-top:5.0pt;margin-bottom:5.0pt">
<div>
<div>
<p class="MsoNormal">On May 18, 2016, at 12:17 PM, Sanjoy Das via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org" target="_blank"><span style="color:purple">llvm-dev@lists.llvm.org</span></a>> wrote:<o:p></o:p></p>
</div>
</div>
</blockquote>
</div>
</div>
</div>
</div>
<div>
<div>
<div style="border:none;border-right:solid blue 1.5pt;padding:0in 0in 0in 0in">
<div>
<blockquote style="margin-top:5.0pt;margin-bottom:5.0pt">
<div>
<p class="MsoNormal"> <o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="margin-bottom:12.0pt"><span style="font-size:7.5pt;font-family:"Helvetica",sans-serif"><br>
<br>
Demikhovsky, Elena wrote:</span><o:p></o:p></p>
<blockquote style="margin-top:5.0pt;margin-bottom:5.0pt">
<div>
<p class="MsoNormal"><span style="font-size:7.5pt;font-family:"Helvetica",sans-serif">> Even then, I'd personally want to see further evidence of why the<br>
correct solution is to model the floating point IV in SCEV rather than<br>
find a more powerful way of converting the IV to an integer that models<br>
> the non-integer values taken on by the IV. As an example, if the use<br>
case is the following code with appropriate flags to relax IEEE<br>
semantics so this looks like normal algabra etc:<br>
<br>
> for (float f = 0.01f; f < 1.0f; f += 0.01f) ç **A**<br>
<br>
...<br>
<br>
> I'd rather see us cleverly turn it into:<br>
<br>
> float f = 0.01f;<br>
<br>
> for (int i = 1; i < 100; i += 1, f += 0.01f) ç **B**<br>
<br>
I can later try to enhance IndVarSimplify::handleFloatingPointIV() in<br>
order to convert**A** to **B**.<br>
<br>
But **B** is exactly the case I’m starting from. The main IV “i” is<br>
integer. The variable “f” is also considered as IV in this loop.<br>
<br>
And this loop is not vectorized because “f” is floating point.<br>
<br>
I don’t think that the case **B** is uncommon.</span><o:p></o:p></p>
</div>
</blockquote>
<div>
<p class="MsoNormal"><span style="font-size:7.5pt;font-family:"Helvetica",sans-serif"><br>
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></o:p></p>
</div>
</div>
</blockquote>
</div>
</div>
</div>
</div>
<div>
<div>
<div style="border:none;border-right:solid blue 1.5pt;padding:0in 0in 0in 0in">
<div>
<div>
<div>
<p class="MsoNormal"> <o:p></o:p></p>
</div>
</div>
<div>
<div>
<p class="MsoNormal">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></o:p></p>
</div>
</div>
<div>
<div>
<p class="MsoNormal"> <o:p></o:p></p>
</div>
</div>
<div>
<div>
<p class="MsoNormal">Then if we find other pressing cases to handle we can rethink the strategy.<o:p></o:p></p>
</div>
</div>
<div>
<div>
<p class="MsoNormal"> <o:p></o:p></p>
</div>
</div>
<div>
<div>
<p class="MsoNormal">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></o:p></p>
</div>
</div>
<div>
<div>
<p class="MsoNormal"> <o:p></o:p></p>
</div>
</div>
</div>
</div>
</div>
</div>
<div>
<div>
<div style="border:none;border-right:solid blue 1.5pt;padding:0in 0in 0in 0in">
<blockquote style="margin-left:30.0pt;margin-top:5.0pt;margin-right:0in;margin-bottom:5.0pt">
<div>
<div>
<div>
<div>
<p class="MsoNormal">/tmp/sss.c:3:6: remark: loop not vectorized: value that could not be<o:p></o:p></p>
</div>
</div>
</div>
</div>
<div>
<div>
<div>
<div>
<p class="MsoNormal"> identified as reduction is used outside the loop<o:p></o:p></p>
</div>
</div>
</div>
</div>
<div>
<div>
<div>
<div>
<p class="MsoNormal"> [-Rpass-analysis=loop-vectorize]<o:p></o:p></p>
</div>
</div>
</div>
</div>
</blockquote>
<div>
<div>
<div>
<div>
<p class="MsoNormal"> <o:p></o:p></p>
</div>
</div>
<div>
<div>
<p class="MsoNormal">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></o:p></p>
</div>
</div>
<div>
<div>
<p class="MsoNormal"> <o:p></o:p></p>
</div>
</div>
<div>
<div>
<p class="MsoNormal">Adam<o:p></o:p></p>
</div>
</div>
</div>
<p class="MsoNormal" style="margin-bottom:12.0pt"> <o:p></o:p></p>
<blockquote style="margin-top:5.0pt;margin-bottom:5.0pt">
<div>
<p class="MsoNormal" style="margin-bottom:12.0pt"><span style="font-size:7.5pt;font-family:"Helvetica",sans-serif"><br>
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>
<br>
-- Sanjoy<br>
<br>
<br>
</span><o:p></o:p></p>
<blockquote style="margin-top:5.0pt;margin-bottom:5.0pt">
<p class="MsoNormal" style="margin-bottom:12.0pt"><span style="font-size:7.5pt;font-family:"Helvetica",sans-serif"><br>
-*/Elena/*<br>
<br>
---------------------------------------------------------------------<br>
Intel Israel (74) Limited<br>
<br>
This e-mail and any attachments may contain confidential material for<br>
the sole use of the intended recipient(s). Any review or distribution<br>
by others is strictly prohibited. If you are not the intended<br>
recipient, please contact the sender and delete all copies.</span><o:p></o:p></p>
</blockquote>
<div>
<p class="MsoNormal"><span style="font-size:7.5pt;font-family:"Helvetica",sans-serif">_______________________________________________<br>
LLVM Developers mailing list<br>
</span><a href="mailto:llvm-dev@lists.llvm.org" target="_blank"><span style="font-size:7.5pt;font-family:"Helvetica",sans-serif;color:purple">llvm-dev@lists.llvm.org</span></a><span style="font-size:7.5pt;font-family:"Helvetica",sans-serif"><br>
</span><a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" target="_blank"><span style="font-size:7.5pt;font-family:"Helvetica",sans-serif;color:purple">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</span></a><o:p></o:p></p>
</div>
</div>
</blockquote>
</div>
<div>
<p class="MsoNormal"> <o:p></o:p></p>
</div>
</div>
</div>
</div>
<div>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto">---------------------------------------------------------------------<br>
Intel Israel (74) Limited<o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto">This e-mail and any attachments may contain confidential material for<br>
the sole use of the intended recipient(s). Any review or distribution<br>
by others is strictly prohibited. If you are not the intended<br>
recipient, please contact the sender and delete all copies.<o:p></o:p></p>
</div>
</blockquote>
</div>
</div>
</div>
</blockquote>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
</body>
</html>