<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="">Resending to new llvm-dev...<div class=""><br class=""><div><blockquote type="cite" class=""><div class="">On Sep 17, 2015, at 4:48 PM, Michael Zolotukhin <<a href="mailto:mzolotukhin@apple.com" class="">mzolotukhin@apple.com</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><meta http-equiv="Content-Type" content="text/html charset=utf-8" class=""><div style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class="">Hi Alex,<div class=""><br class=""><div class=""><blockquote type="cite" class=""><div class="">On Sep 17, 2015, at 4:04 PM, Alex Susu <<a href="mailto:alex.e.susu@gmail.com" class="">alex.e.susu@gmail.com</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><div dir="ltr" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: 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;" class=""><div class=""><div class=""><div class=""> Hello, Michael,<br class=""></div> Thank you for the answer.<br class=""></div> I think I found the reason why the code does not get vectorized at all (none of the loops get vectorized): LLVM's LoopVectorizer does NOT work well with the inner loop doing reduction on float, even if using -ffast-math.<br class=""></div></div></div></blockquote>Yes, LLVM Vectorizer has some problems with float reductions, but there has been some work done on this recently (and more to come). Also, diagnostics are much better than they were before. So, I tried the following case (which is very similar to yours) with a recent compiler:</div><div class=""><div class=""><font face="Menlo" class="">$ cat red.c</font></div><div class=""><font face="Menlo" class="">float foo(float *A, float *B, int *C, int N) {</font></div><div class=""><font face="Menlo" class=""> int i = 0;</font></div><div class=""><font face="Menlo" class=""> float r = 0.0;</font></div><div class=""><font face="Menlo" class=""> for (i = 0; i < N; i++) {</font></div><div class=""><font face="Menlo" class=""> r += A[i] * B[C[i]];</font></div><div class=""><font face="Menlo" class=""> }</font></div><div class=""><font face="Menlo" class=""> return r;</font></div><div class=""><font face="Menlo" class="">}</font></div><div class=""><br class=""></div><div class="">It's not vectorized without '-ffast-math':</div><div class=""><div class=""><font face="Menlo" class="">$ bin/clang -O3 red.c -Rpass=loop-vectorize -S -Rpass-analysis=loop-vectorize</font></div><div class=""><font face="Menlo" class="">red.c:6:7: remark: loop not vectorized: cannot prove it is safe to reorder floating-point operations; allow reordering by specifying '#pragma clang loop vectorize(enable)' before the loop or by providing the compiler option '-ffast-math'.</font></div><div class=""><font face="Menlo" class=""> [-Rpass-analysis=loop-vectorize]</font></div><div class=""><font face="Menlo" class=""> r += A[i] * B[C[i]];</font></div><div class=""><font face="Menlo" class=""> ^</font></div><div class=""><br class=""></div></div><div class="">but even with '-ffast-math' the cost heuristic says that vectorization isn't beneficial:</div><div class=""><div class=""><font face="Menlo" class="">$ bin/clang -O3 red.c -Rpass=loop-vectorize -S -Rpass-analysis=loop-vectorize -ffast-math</font></div><div class=""><font face="Menlo" class="">red.c:6:10: remark: the cost-model indicates that vectorization is not beneficial [-Rpass-analysis=loop-vectorize]</font></div><div class=""><font face="Menlo" class=""> r += A[i] * B[C[i]];</font></div><div class=""><font face="Menlo" class=""> ^</font></div><div class=""><font face="Menlo" class="">red.c:6:10: remark: the cost-model indicates that interleaving is not beneficial [-Rpass-analysis=loop-vectorize]</font></div><div class=""><br class=""></div></div><div class="">When I overrode the cost model by adding the suggested pragma before the loop, I finally got the loop vectorized:</div><div class=""><div class=""><font face="Menlo" class="">$ bin/clang -O3 red.c -Rpass=loop-vectorize -S -Rpass-analysis=loop-vectorize</font></div><div class=""><font face="Menlo" class="">red.c:6:10: remark: vectorized loop (vectorization width: 2, interleaved count: 2) [-Rpass=loop-vectorize]</font></div><div class=""><font face="Menlo" class=""> r += A[i] * B[C[i]];</font></div><div class=""><font face="Menlo" class=""> ^</font></div><div class=""><br class=""></div><div class="">BTW, I don't expect much gains from vectorization of this particular loop. Expression B[C[i]] requires a lot of auxiliary instructions in vector version, so it mitigates most of the gains from vectorization.</div><div class=""><br class=""></div></div><div class=""><br class=""></div></div><div class=""><blockquote type="cite" class=""><div class=""><div dir="ltr" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: 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;" class=""><div class=""> I attach sample code that shows this - however, the float NON-vectorization is not always happening - mabye it's some memory corruption in the LLVM LoopVectorizer, which sometimes results in a bad state.<br class=""></div></div></div></blockquote>Do you mean that sometimes you got the float loop vectorized? If that’s so, it sounds really strange..</div><div class=""><br class=""><blockquote type="cite" class=""><div class=""><div dir="ltr" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: 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;" class=""><br class=""><div class=""> Let me know if I can provide more info.<br class=""><div class=""> I'd like to mention I'm using the LLVM built from the repository - downloaded on Jul 14th, 2015.<br class=""></div></div></div></div></blockquote><div class="">If you really want to vectorize this loop, I'd suggest updating LLVM and using pragma. If you have any questions, I'd be glad to help with them, if I can.</div><div class=""><br class=""></div><div class="">Best regards,</div><div class="">Michael</div><br class=""><blockquote type="cite" class=""><div class=""><div dir="ltr" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: 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;" class=""><div class=""><br class=""><br class=""></div><div class=""> Best regards,<br class=""></div><div class=""> Alex<br class=""></div><div class=""><br class=""><br class=""></div></div><div class="gmail_extra" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: 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;"><br class=""><div class="gmail_quote">On Wed, Jul 8, 2015 at 9:17 PM, Michael Zolotukhin<span class="Apple-converted-space"> </span><span dir="ltr" class=""><<a href="mailto:mzolotukhin@apple.com" target="_blank" class="">mzolotukhin@apple.com</a>></span><span class="Apple-converted-space"> </span>wrote:<br class=""><blockquote class="gmail_quote" style="margin: 0px 0px 0px 0.8ex; border-left-width: 1px; border-left-color: rgb(204, 204, 204); border-left-style: solid; padding-left: 1ex;"><div style="word-wrap: break-word;" class="">Hi Alex,<div class=""><br class=""></div><div class="">Example from the link you provided looks like this:</div><div class=""><pre style="margin-top: 0px; padding: 5px; border: 0px; font-size: 13px; overflow: auto; width: auto; max-height: 600px; background-color: rgb(238, 238, 238); font-family: Consolas, Menlo, Monaco, 'Lucida Console', 'Liberation Mono', 'DejaVu Sans Mono', 'Bitstream Vera Sans Mono', 'Courier New', monospace, sans-serif; color: rgb(57, 51, 24); word-wrap: normal;" class=""><code style="margin: 0px; padding: 0px; border: 0px; font-family: Consolas, Menlo, Monaco, 'Lucida Console', 'Liberation Mono', 'DejaVu Sans Mono', 'Bitstream Vera Sans Mono', 'Courier New', monospace, sans-serif; white-space: inherit;" class=""><span style="margin: 0px; padding: 0px; border: 0px; color: rgb(0, 0, 139);" class="">for</span><span style="margin: 0px; padding: 0px; border: 0px;" class=""> </span><span style="margin: 0px; padding: 0px; border: 0px;" class="">(</span><span style="margin: 0px; padding: 0px; border: 0px;" class="">i</span><span style="margin: 0px; padding: 0px; border: 0px;" class="">=</span><span style="margin: 0px; padding: 0px; border: 0px; color: rgb(128, 0, 0);" class="">0</span><span style="margin: 0px; padding: 0px; border: 0px;" class="">;</span><span style="margin: 0px; padding: 0px; border: 0px;" class=""> i</span><span style="margin: 0px; padding: 0px; border: 0px;" class=""><</span><span style="margin: 0px; padding: 0px; border: 0px;" class="">M</span><span style="margin: 0px; padding: 0px; border: 0px;" class="">;</span><span style="margin: 0px; padding: 0px; border: 0px;" class=""> i</span><span style="margin: 0px; padding: 0px; border: 0px;" class="">++</span><span style="margin: 0px; padding: 0px; border: 0px;" class=""> </span><span style="margin: 0px; padding: 0px; border: 0px;" class="">){</span><span style="margin: 0px; padding: 0px; border: 0px;" class="">
z</span><span style="margin: 0px; padding: 0px; border: 0px;" class="">[</span><span style="margin: 0px; padding: 0px; border: 0px;" class="">i</span><span style="margin: 0px; padding: 0px; border: 0px;" class="">]=</span><span style="margin: 0px; padding: 0px; border: 0px; color: rgb(128, 0, 0);" class="">0</span><span style="margin: 0px; padding: 0px; border: 0px;" class="">;</span><span style="margin: 0px; padding: 0px; border: 0px;" class="">
</span><span style="margin: 0px; padding: 0px; border: 0px; color: rgb(0, 0, 139);" class="">for</span><span style="margin: 0px; padding: 0px; border: 0px;" class=""> </span><span style="margin: 0px; padding: 0px; border: 0px;" class="">(</span><span style="margin: 0px; padding: 0px; border: 0px;" class="">ckey</span><span style="margin: 0px; padding: 0px; border: 0px;" class="">=</span><span style="margin: 0px; padding: 0px; border: 0px;" class="">row_ptr</span><span style="margin: 0px; padding: 0px; border: 0px;" class="">[</span><span style="margin: 0px; padding: 0px; border: 0px;" class="">i</span><span style="margin: 0px; padding: 0px; border: 0px;" class="">];</span><span style="margin: 0px; padding: 0px; border: 0px;" class=""> ckey</span><span style="margin: 0px; padding: 0px; border: 0px;" class=""><</span><span style="margin: 0px; padding: 0px; border: 0px;" class="">row_ptr</span><span style="margin: 0px; padding: 0px; border: 0px;" class="">[</span><span style="margin: 0px; padding: 0px; border: 0px;" class="">i</span><span style="margin: 0px; padding: 0px; border: 0px;" class="">+</span><span style="margin: 0px; padding: 0px; border: 0px; color: rgb(128, 0, 0);" class="">1</span><span style="margin: 0px; padding: 0px; border: 0px;" class="">];</span><span style="margin: 0px; padding: 0px; border: 0px;" class=""> ckey</span><span style="margin: 0px; padding: 0px; border: 0px;" class="">++)</span><span style="margin: 0px; padding: 0px; border: 0px;" class=""> </span><span style="margin: 0px; padding: 0px; border: 0px;" class="">{</span><span style="margin: 0px; padding: 0px; border: 0px;" class="">
</span><span style="margin: 0px; padding: 0px; border: 0px;" class=""> z</span><span style="margin: 0px; padding: 0px; border: 0px;" class="">[</span><span style="margin: 0px; padding: 0px; border: 0px;" class="">i</span><span style="margin: 0px; padding: 0px; border: 0px;" class="">]</span><span style="margin: 0px; padding: 0px; border: 0px;" class=""> </span><span style="margin: 0px; padding: 0px; border: 0px;" class="">+=</span><span style="margin: 0px; padding: 0px; border: 0px;" class=""> data</span><span style="margin: 0px; padding: 0px; border: 0px;" class="">[</span><span style="margin: 0px; padding: 0px; border: 0px;" class="">ckey</span><span style="margin: 0px; padding: 0px; border: 0px;" class="">]*</span><span style="margin: 0px; padding: 0px; border: 0px;" class="">x</span><span style="margin: 0px; padding: 0px; border: 0px;" class="">[</span><span style="white-space: inherit; margin: 0px; padding: 0px; border: 0px;" class="">colind</span><span style="white-space: inherit; margin: 0px; padding: 0px; border: 0px;" class="">[</span><span style="white-space: inherit; margin: 0px; padding: 0px; border: 0px;" class="">ckey]</span><span style="margin: 0px; padding: 0px; border: 0px;" class="">];</span><span style="margin: 0px; padding: 0px; border: 0px;" class="">
</span><span style="margin: 0px; padding: 0px; border: 0px;" class="">}</span><span style="margin: 0px; padding: 0px; border: 0px;" class="">
</span><span style="margin: 0px; padding: 0px; border: 0px;" class="">}</span></code></pre><div class="">Is it the loop you are trying to vectorize? I don’t see any ‘if’ inside the innermost loop.</div><div class=""><br class=""></div><div class="">But anyway, here vectorizer might have following troubles:</div><div class="">1) iteration count of the innermost loop is unknown.</div><div class="">2) Gather accesses ( a[b[i]] ). With AVX512 set of instructions it’s possible to generate efficient code for such case, but a) I think it’s not supported yet, b) if this ISA isn’t available, then vectorized code would need to ‘manually’ gather scalar values to vector, which might be slow (and thus, vectorizer might decide to leave the code scalar).</div><div class=""><br class=""></div><div class="">And here is a list of papers vectorizer is based on:</div><div class=""><div class=""><font face="Menlo" class="">// The reduction-variable vectorization is based on the paper:</font></div><div class=""><font face="Menlo" class="">// D. Nuzman and R. Henderson. Multi-platform Auto-vectorization.</font></div><div class=""><font face="Menlo" class="">//</font></div><div class=""><font face="Menlo" class="">// Variable uniformity checks are inspired by:</font></div><div class=""><font face="Menlo" class="">// Karrenberg, R. and Hack, S. Whole Function Vectorization.</font></div><div class=""><font face="Menlo" class="">//</font></div><div class=""><font face="Menlo" class="">// The interleaved access vectorization is based on the paper:</font></div><div class=""><font face="Menlo" class="">// Dorit Nuzman, Ira Rosen and Ayal Zaks. Auto-Vectorization of Interleaved</font></div><div class=""><font face="Menlo" class="">// Data for SIMD</font></div><div class=""><font face="Menlo" class="">//</font></div><div class=""><font face="Menlo" class="">// Other ideas/concepts are from:</font></div><div class=""><font face="Menlo" class="">// A. Zaks and D. Nuzman. Autovectorization in GCC-two years later.</font></div><div class=""><font face="Menlo" class="">//</font></div><div class=""><font face="Menlo" class="">// S. Maleki, Y. Gao, M. Garzaran, T. Wong and D. Padua. An Evaluation of</font></div><div class=""><font face="Menlo" class="">// Vectorizing Compilers.</font></div></div><div class="">And probably, some of the parts are written from scratch with no reference to a paper.</div><div class=""><br class=""></div><div class="">The presentations you found are a good starting point, but while they’re still good from getting basics of the vectorizer, they are a bit outdated now in a sense that a lot of new features has been added since then (and bugs fixed:) ). Also, I’d recommend trying a newer LLVM version - I don’t think it’ll handle the example above, but it would be much more convenient to investigate why the loop isn’t vectorized and fix vectorizer if we figure out how.</div><div class=""><br class=""></div><div class="">Best regards,</div><div class="">Michael</div><div class=""><br class=""></div><div class=""><blockquote type="cite" class=""><div class=""><div class="h5"><div class="">On Jul 8, 2015, at 10:01 AM, RCU <<a href="mailto:alex.e.susu@gmail.com" target="_blank" class="">alex.e.susu@gmail.com</a>> wrote:</div><br class=""></div></div><div class=""><div class=""><div class="h5"> Hello.<br class=""> I am trying to vectorize a CSR SpMV (sparse matrix vector multiplication) procedure but the LLVM loop vectorizer is not able to handle such code.<br class=""> I am using cland and llvm version 3.4 (on Ubuntu 12.10). I use the -fvectorize option with clang and -loop-vectorize with opt-3.4 .<br class=""> The CSR SpMV function is inspired from<span class="Apple-converted-space"> </span><a href="http://stackoverflow.com/questions/13636464/slow-sparse-matrix-vector-product-csr-using-open-mp" target="_blank" class="">http://stackoverflow.com/questions/13636464/slow-sparse-matrix-vector-product-csr-using-open-mp</a><span class="Apple-converted-space"> </span>(I can provide the exact code samples used).<br class=""><br class=""> Basically the problem is the loop vectorizer does NOT work with if inside loop (be it 2 nested loops or a modification of SpMV I did with just 1 loop - I can provide the exact code) changing the value of the accumulator z. I can sort of understand why LLVM isn't able to vectorize the code.<br class=""> However, at<span class="Apple-converted-space"> </span><a href="http://llvm.org/docs/Vectorizers.html#if-conversion" target="_blank" class="">http://llvm.org/docs/Vectorizers.html#if-conversion</a><span class="Apple-converted-space"> </span>it is written:<br class=""> <<The Loop Vectorizer is able to "flatten" the IF statement in the code and generate a single stream of instructions.<br class=""> The Loop Vectorizer supports any control flow in the innermost loop.<br class=""> The innermost loop may contain complex nesting of IFs, ELSEs and even GOTOs.>><br class=""> Could you please tell me what are these lines exactly trying to say.<br class=""><br class=""> Could you please tell me what algorithm is the LLVM loop vectorizer using (maybe the algorithm is described in a paper) - I currently found only 2 presentations on this topic:<span class="Apple-converted-space"> </span><a href="http://llvm.org/devmtg/2013-11/slides/Rotem-Vectorization.pdf" target="_blank" class="">http://llvm.org/devmtg/2013-11/slides/Rotem-Vectorization.pdf</a><span class="Apple-converted-space"> </span>and<span class="Apple-converted-space"> </span><a href="https://urldefense.proofpoint.com/v2/url?u=https-3A__archive.fosdem.org_2014_schedule_event_llvmautovec_attachments_audio_321_export_events_attachments_llvmautovec_audio_321_AutoVectorizationLLVM.pdf&d=BQMFaQ&c=eEvniauFctOgLOKGJOplqw&r=ygVmcuuQ1MUhRUoJm-IgPtgjmvM0byfjlHDg99vufEI&m=wB_Hvsma5X84froglc2I4UFz1HGlCGpZpM7nxKKO_B8&s=pi6FRG39lC4JeMV5Onu3CZkX34HTM_85dUhLBBr4dKI&e=" target="_blank" class="">https://archive.fosdem.org/2014/schedule/event/llvmautovec/attachments/audio/321/export/events/attachments/llvmautovec/audio/321/AutoVectorizationLLVM.pdf</a>.<br class=""><br class=""> Thank you very much,<br class=""> Alex<br class=""></div></div>_______________________________________________<br class="">LLVM Developers mailing list<br class=""><a href="mailto:LLVMdev@cs.uiuc.edu" target="_blank" class="">LLVMdev@cs.uiuc.edu</a><span class="Apple-converted-space"> </span> <a href="https://urldefense.proofpoint.com/v2/url?u=http-3A__llvm.cs.uiuc.edu&d=BQMFaQ&c=eEvniauFctOgLOKGJOplqw&r=ygVmcuuQ1MUhRUoJm-IgPtgjmvM0byfjlHDg99vufEI&m=wB_Hvsma5X84froglc2I4UFz1HGlCGpZpM7nxKKO_B8&s=FRPFoePA5qDz4sI9_rCux2_hmquZMsQkZdiz5BsCUmI&e=" target="_blank" class="">http://llvm.cs.uiuc.edu</a><br class=""><a href="https://urldefense.proofpoint.com/v2/url?u=http-3A__lists.cs.uiuc.edu_mailman_listinfo_llvmdev&d=BQMFaQ&c=eEvniauFctOgLOKGJOplqw&r=ygVmcuuQ1MUhRUoJm-IgPtgjmvM0byfjlHDg99vufEI&m=wB_Hvsma5X84froglc2I4UFz1HGlCGpZpM7nxKKO_B8&s=Dd31y32iLFcIPCQ4SwWGWfg1Fc0g5dGL6xRRJxnXaIY&e=" target="_blank" class="">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a><br class=""></div></blockquote></div><br class=""></div></div></blockquote></div><br class=""></div><span id="cid:F3C91E59-2799-4283-9396-3286826B5668@apple.com" class=""><test_case_LoopVectorizer.zip></span></div></blockquote></div><br class=""></div></div></div></blockquote></div><br class=""></div></body></html>