<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<meta name="Generator" content="Microsoft Exchange Server">
<!-- converted from rtf -->
<style><!-- .EmailQuote { margin-left: 1pt; padding-left: 4pt; border-left: #800000 2px solid; } --></style>
</head>
<body>
<font face="Calibri" size="2"><span style="font-size:11pt;">
<div><font color="#1F497D"> </font></div>
<div>>What situations are they common in?</div>
<div><font color="#1F497D"> </font></div>
<div><font color="#1F497D">ICC Vectorizer made a paradigm shift a while ago.</font></div>
<div style="text-indent:36pt;"><font color="#1F497D">If there aren’t a clear reason why something can’t be vectorized, we should try our best to vectorize.</font></div>
<div><font color="#1F497D">The rest is a performance modeling (and priority to implement) question, not a capability question.</font></div>
<div><font color="#1F497D">We believe this is a good paradigm to follow in a vectorizer development. It was a big departure from</font></div>
<div><font color="#1F497D">“vectorize when all things look nice to vectorizer”.</font></div>
<div><font color="#1F497D"> </font></div>
<div><font color="#1F497D">We shouldn’t give up vectorizing simply because programmer wrote a FP induction code.(*)</font></div>
<div><font color="#1F497D">Then, the next question is what’s the best solution for that problem, and extending SCEV</font></div>
<div><font color="#1F497D">appears to be one of the obvious directions to explore.</font></div>
<div><font color="#1F497D"> </font></div>
<div><font color="#1F497D">Thanks,</font></div>
<div><font color="#1F497D">Hideki Saito</font></div>
<div><font color="#1F497D">Intel Compilers and Languages</font></div>
<a name="_MailEndCompose"></a>
<div><font color="#1F497D">----------------------</font></div>
<div><font color="#1F497D">(*) Quick (and dirty) overview of vectorization legality</font></div>
<div><font color="#1F497D">Vectorization is a cross-iteration optimization. We need to have a solution for cross-iteration dependences.</font></div>
<div><font color="#1F497D">Forward dependencies are considered “safe for vectorization” since vector execution order naturally satisfy them.</font></div>
<div><font color="#1F497D">Backward dependencies are unsafe, unless vectorizer knows how to “break” them. Induction is cyclic dependence</font></div>
<div><font color="#1F497D">by nature and as such considered unsafe for vectorization, unless vectorizer knows how to break them.</font></div>
<div><font color="#1F497D">[Given a CFG that executes from top to bottom, forward dependence is the downward data dependence edge.]</font></div>
<div><font color="#1F497D"> </font></div>
<a name="_____replyseparator"></a>
<div>_____________________________________________<br>
<b>From:</b> Demikhovsky, Elena <br>
<b>Sent:</b> Tuesday, May 17, 2016 3:15 AM<br>
<b>To:</b> Sanjoy Das <sanjoy@playingwithpointers.com>; Chandler Carruth <chandlerc@google.com><br>
<b>Cc:</b> llvm-dev <llvm-dev@lists.llvm.org>; Hal Finkel (hfinkel@anl.gov) <hfinkel@anl.gov>; Adam Nemet (anemet@apple.com) <anemet@apple.com>; Andrew Trick <atrick@apple.com>; mzolotukhin@apple.com; Zaks, Ayal <ayal.zaks@intel.com>; Saito, Hideki <hideki.saito@intel.com><br>
<b>Subject:</b> RE: [llvm-dev] Working on FP SCEV Analysis</div>
<div> </div>
<div> </div>
<div>Hi Sanjoy,</div>
<div> </div>
<div>Please see my answers bellow:</div>
<div> </div>
<div> - Core motivation: why do we even care about optimizing floating</div>
<div> point induction variables? What situations are they common in? Do</div>
<div> programmers _expect_ compilers to optimize them well? (I haven't</div>
<div> worked on our vectorizers so pardon the possibly stupid question)</div>
<div> in the example you gave, why do you need SCEV to analyze the</div>
<div> increment to vectorize the loop (i.e how does it help)? What are</div>
<div> some other concrete cases you'll want to optimize?</div>
<div> </div>
<div><b><i>[Demikhovsky, Elena] I gave an example of loop that can be vectorized in the fast-math mode. ICC compiler vectorizes loops with *primary* and *secondary* IVs:</i></b></div>
<div><b><i>This is the example for *primary* induction:</i></b></div>
<div> </div>
<div><b><i>(1) for (float i = 0.5; i < 0.75; i+=0.05) {} → i is a "primary" IV</i></b></div>
<div> </div>
<div><b><i>And for *secondary*:</i></b></div>
<div> </div>
<div><b><i>(2) for (int i = 0, float x = start; i < N; i++, x += delta) {} → x is a "secondary" IV</i></b></div>
<div> </div>
<div><b><i>Now I'm working only on (2)</i></b></div>
<div> </div>
<div> - I presume you'll want SCEV expressions for `sitofp` and `uitofp`.</div>
<div> </div>
<div><b><i>[Demikhovsky, Elena] I'm adding these expressions, of course. They are similar to "truncate" and "zext", in terms of implementation.</i></b></div>
<div> </div>
<div> (The most important question:) With these in the game, what is the</div>
<div> canonical representation of SCEV expressions that can be expressed</div>
<div> as, say, both `sitofp(A + B)` and `sitofp(A) + sitofp(B)`?</div>
<div><b><i>[Demikhovsky, Elena] Meanwhile I have (start + delta * sitofp(i)).</i></b></div>
<div><b><i>I don't know how far we can go with FP simplification and under what flags. The first implementation does not assume that sitofp(A + B) is equal to sitofp(A) + sitofp(B)</i></b></div>
<div> </div>
<div> </div>
<div> Will we have a way to mark expressions (like we have `nsw` and</div>
<div> `nuw` for `sext` and `zext`) which we can distribute `sitofp` and</div>
<div> `uitofp` over?</div>
<div><b><i>[Demikhovsky, Elena] I assume that sitofp and uitofp should be 2 different operations. </i></b></div>
<div> </div>
<div> Same questions for `fptosi` and `fptoui`.</div>
<div><b><i>[Demikhovsky, Elena] the same answer as above, because I don’t want to combine these operations</i></b></div>
<div> </div>
<div> - How will you partition the logic between floating and integer</div>
<div> expressions in SCEV-land? Will you have, say, `SCEVAddExpr` do</div>
<div> different things based on type, or will you split it into</div>
<div> `SCEVIAddExpr` and `SCEVFAddExpr`? [0]</div>
<div> </div>
<div><b><i>[Demikhovsky, Elena] Yes, I’m introducing SCEVFAddExpr and </i></b><b><i>SCEVFMulExpr - </i></b><b><i>(start + delta * sitofp(i))</i></b></div>
<div> </div>
<div> * There are likely to be similarities too -- e.g. the "inductive"</div>
<div> or "control flow" aspect of `SCEVAddRecExpr` is likely to be</div>
<div> common between floating point add recurrences[1], and integer add</div>
<div> recurrences; and part of figuring out the partitioning is also</div>
<div> figuring out how to re-use these bits of logic.</div>
<div><b><i>[Demikhovsky, Elena] I’m adding SCEVFAddRecExpr to describe the recurrence of FP IV</i></b></div>
<div> </div>
<div> </div>
<div>[0]: I'll prefer the latter since e.g. integer addition is associative, but floating point addition isn't; and it is better to force programmers to handle the two operations differently.</div>
<div> </div>
<div>[1]: For instance, things like this:</div>
<div><a href="https://github.com/llvm-mirror/llvm/blob/master/lib/Analysis/ScalarEvolution.cpp#L7564">https://github.com/llvm-mirror/llvm/blob/master/lib/Analysis/ScalarEvolution.cpp#L7564</a></div>
<div>are likely to stay common between floating point and integer add recs.</div>
<div> </div>
<div>-- Sanjoy</div>
<div> </div>
</span></font>
</body>
</html>