<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:Wingdings;
panose-1:5 0 0 0 0 0 0 0 0 0;}
@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;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0cm;
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.EmailStyle17
{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:612.0pt 792.0pt;
margin:72.0pt 90.0pt 72.0pt 90.0pt;}
div.WordSection1
{page:WordSection1;}
/* List Definitions */
@list l0
{mso-list-id:799957587;
mso-list-type:hybrid;
mso-list-template-ids:-1214880770 44585902 67698691 67698693 67698689 67698691 67698693 67698689 67698691 67698693;}
@list l0:level1
{mso-level-start-at:0;
mso-level-number-format:bullet;
mso-level-text:-;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:"Calibri",sans-serif;
mso-fareast-font-family:"Times New Roman";}
@list l0:level2
{mso-level-number-format:bullet;
mso-level-text:o;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:"Courier New";
mso-bidi-font-family:"Times New Roman";}
@list l0:level3
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:Wingdings;}
@list l0:level4
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:Symbol;}
@list l0:level5
{mso-level-number-format:bullet;
mso-level-text:o;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:"Courier New";
mso-bidi-font-family:"Times New Roman";}
@list l0:level6
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:Wingdings;}
@list l0:level7
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:Symbol;}
@list l0:level8
{mso-level-number-format:bullet;
mso-level-text:o;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:"Courier New";
mso-bidi-font-family:"Times New Roman";}
@list l0:level9
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;
font-family:Wingdings;}
ol
{margin-bottom:0cm;}
ul
{margin-bottom:0cm;}
--></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"><a name="_MailEndCompose"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">I implemented IV simplification with FP SCEV and uploaded a new patch. The loop bellow is converted to “start+const*N”.<o:p></o:p></span></a></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D">(You can see the diff between patches to see what was added).
<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>
<div>
<p class="MsoNormal" style="margin-left:36.0pt;text-indent:-18.0pt;mso-list:l0 level1 lfo1">
<![if !supportLists]><span style="font-family:"Calibri",sans-serif;color:#2F5496"><span style="mso-list:Ignore">-<span style="font:7.0pt "Times New Roman"">
</span></span></span><![endif]><span dir="LTR"></span><b><i><span style="color:#2F5496"> Elena<o:p></o:p></span></i></b></p>
</div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D"><o:p> </o:p></span></p>
<div style="border:none;border-left:solid blue 1.5pt;padding:0cm 0cm 0cm 4.0pt">
<div>
<div style="border:none;border-top:solid #E1E1E1 1.0pt;padding:3.0pt 0cm 0cm 0cm">
<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"> atrick@apple.com [mailto:atrick@apple.com]
<br>
<b>Sent:</b> Monday, May 30, 2016 21:40<br>
<b>To:</b> llvm-dev <llvm-dev@lists.llvm.org><br>
<b>Cc:</b> Demikhovsky, Elena <elena.demikhovsky@intel.com>; Sanjoy Das <sanjoy@playingwithpointers.com><br>
<b>Subject:</b> Floating Point SCEV Analysis<o:p></o:p></span></p>
</div>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">My response to this patch is below, but adding a floating-point feature to SCEV should really be hashed out on the llvm-dev list first. I would like to get the attention of floating-point experts on the design review.<o:p></o:p></p>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">I’d like to see a small design proposal justifying the feature and defending it’s soundness. My concern is that the approach may not be sound, but providing this core API would encourage llvm dev’s to use the feature without thinking.<o:p></o:p></p>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">I suggest starting with SCEV’s most basic functionality and proving the validity of increasingly complex cases. Can you defend SCEV’s ability to remove loops like this?<o:p></o:p></p>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<div>
<p class="MsoNormal">float fincby(float start, int N) {<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"> float result = start;<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"> for (int i = 0; i < N; ++i) {<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"> result += 1.0f;<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"> }<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"> return result;<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">}<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">-Andy<o:p></o:p></p>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal"><a href="http://reviews.llvm.org/D20695">http://reviews.llvm.org/D20695</a><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><br>
<br>
<o:p></o:p></p>
<blockquote style="margin-top:5.0pt;margin-bottom:5.0pt">
<div>
<p class="MsoNormal">Begin forwarded message:<o:p></o:p></p>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
<div>
<p class="MsoNormal"><b><span style="font-family:"Helvetica",sans-serif">From: </span>
</b><span style="font-family:"Helvetica",sans-serif">Andrew Trick via llvm-commits <<a href="mailto:llvm-commits@lists.llvm.org">llvm-commits@lists.llvm.org</a>></span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><b><span style="font-family:"Helvetica",sans-serif">Subject: Re: [PATCH] D20695: Floating Point SCEV Analysis</span></b><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><b><span style="font-family:"Helvetica",sans-serif">Date: </span>
</b><span style="font-family:"Helvetica",sans-serif">May 30, 2016 at 11:05:35 AM PDT</span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><b><span style="font-family:"Helvetica",sans-serif">To: </span>
</b><span style="font-family:"Helvetica",sans-serif"><a href="mailto:reviews+D20695+public+faa7820b5ed6aa91@reviews.llvm.org">reviews+D20695+public+faa7820b5ed6aa91@reviews.llvm.org</a></span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><b><span style="font-family:"Helvetica",sans-serif">Cc: </span>
</b><span style="font-family:"Helvetica",sans-serif"><a href="mailto:llvm-commits@lists.llvm.org">llvm-commits@lists.llvm.org</a>,
<a href="mailto:mssimpso@codeaurora.org">mssimpso@codeaurora.org</a></span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><b><span style="font-family:"Helvetica",sans-serif">Reply-To:
</span></b><span style="font-family:"Helvetica",sans-serif">Andrew Trick <<a href="mailto:atrick@apple.com">atrick@apple.com</a>></span><o:p></o:p></p>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
<div>
<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 30, 2016, at 12:02 AM, Sanjoy Das <<a href="mailto:sanjoy@playingwithpointers.com">sanjoy@playingwithpointers.com</a>> wrote:<o:p></o:p></p>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
<div>
<p class="MsoNormal"><span style="font-size:9.0pt;font-family:"Helvetica",sans-serif">I have made some minor comments inline, but I still stand by my earlier comment that we should do something like this as a last resort. As an initial step we should at least
evaluate how far we can we can get on relevant workloads without teaching SCEV about floating point values at all.</span><o:p></o:p></p>
</div>
</blockquote>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
<div>
<p class="MsoNormal">Are there conceivable use cases for this infrastructure beyond vectorizing a small subcategory of loops of this form?<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">float x = init;<br>
for (int i=0;i<N;i++){<br>
A[i] = x;<br>
x += fp_inc; // Loop invariant variable or constant<br>
}<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">Can the vectorizer handle loops of this form without querying SCEV?<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">SCEV expressions have an inherent width. They are not infinite precision. This is the main challenge of working with SCEV expressions, as Sanjoy is well aware. What happens when incrementing a floating-point SCEV expression by a smaller
amount than ULP. Eventually that will happen in a floating-point recurrence. Do we have to prove that floating-point recurrences behave a certain way before we can legally convert them to SCEV expressions?<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">Honestly, I’m not an expert in floating-point semantics, and I wouldn’t feel comfortable adding this to SCEV without buy-in from someone who is.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">Andy<o:p></o:p></p>
</div>
</div>
<p class="MsoNormal">_______________________________________________<br>
llvm-commits mailing list<br>
<a href="mailto:llvm-commits@lists.llvm.org">llvm-commits@lists.llvm.org</a><br>
<a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-commits">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-commits</a><o:p></o:p></p>
</div>
</blockquote>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
</div>
</div>
</div>
</div>
</div>
<p>---------------------------------------------------------------------<br>
Intel Israel (74) Limited</p>
<p>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.</p></body>
</html>