<html><head><style type='text/css'>p { margin: 0; }</style></head><body><div style='font-family: arial,helvetica,sans-serif; font-size: 10pt; color: #000000'><br><br><hr id="zwchr"><blockquote style="border-left: 2px solid rgb(16, 16, 255); margin-left: 5px; padding-left: 5px; color: rgb(0, 0, 0); font-weight: normal; font-style: normal; text-decoration: none; font-family: Helvetica,Arial,sans-serif; font-size: 12pt;"><b>From: </b>"Hal Finkel via llvm-dev" <llvm-dev@lists.llvm.org><br><b>To: </b>"Michael Zolotukhin" <mzolotukhin@apple.com><br><b>Cc: </b>"llvm-dev@lists.llvm.org >> llvm-dev" <llvm-dev@lists.llvm.org><br><b>Sent: </b>Sunday, April 24, 2016 8:09:24 AM<br><b>Subject: </b>Re: [llvm-dev] if-conversion<br><br>
<style>p { margin: 0; }</style><div id="DWT16647" style="font-family: arial,helvetica,sans-serif; font-size: 10pt; color: rgb(0, 0, 0);"><br><hr id="zwchr"><blockquote style="border-left: 2px solid rgb(16, 16, 255); margin-left: 5px; padding-left: 5px; color: rgb(0, 0, 0); font-weight: normal; font-style: normal; text-decoration: none; font-family: Helvetica,Arial,sans-serif; font-size: 12pt;"><b>From: </b>"Michael Zolotukhin" <mzolotukhin@apple.com><br><b>To: </b>"Hal Finkel" <hfinkel@anl.gov><br><b>Cc: </b>"RCU" <alex.e.susu@gmail.com>, "llvm-dev@lists.llvm.org >> llvm-dev" <llvm-dev@lists.llvm.org><br><b>Sent: </b>Saturday, April 23, 2016 2:25:23 PM<br><b>Subject: </b>Re: [llvm-dev] if-conversion<br><br>
Hi,<br class=""><div><blockquote class=""><div class="">On Apr 22, 2016, at 8:27 PM, Hal Finkel via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org" class="" target="_blank">llvm-dev@lists.llvm.org</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><div class="">Hi Rob,<br class=""><br class="">The problem here is that the d[i] array is only conditionally accessed, and so we can't if-convert the loop body. The compiler does not know that d[i] is actually dereferenceable for all i from 0 to 15 (the array might be shorter and p[i] is 0 for i past the end of d's extent).<br class=""><br class="">You can inform LLVM that it is safe to vectorize anyway by adding a pragma, like this:<br class=""><br class=""> #pragma clang loop vectorize(assume_safety)<br class=""></div></div></blockquote>I don’t think it would be enough (due to current limitations of vectorizer). The following expression will be vectorizable:</div><div><font class="" face="Menlo"> res[i] = (p[i] == 0) ? (res[i] + c[i]) : (res[i] + d[i]); // Note “+ c[i]”</font></div><div id="DWT5546">This way, vectorizer deals with similar expressions in both true and false branches, and just needs a vector select to vectorize them. In the original code it needs to figure out, that it needs some kind of “+ 0” in the true branch, and it currently fails to do so.</div></blockquote>Do we have a bug report open on this? If not, we should. You appear to be right, however, this seems not by design but by omission. It's not an explicit check in LoopVectorizationLegality::canVectorizeWithIfConvert, but that we end up IR like this:<br><br>loop:<br> ...<br> %res = load ...<br> %p = load<br> %c = icmp eq i32 %p, 0<br> %br i1 %c, label %load_and_add, label %do_store<br><br>load_and_add:<br> %d = load ...<br> %resd = add i32 %res, %d<br><br>do_store:<br> %v = phi [ %resd, %load_and_add ], [ %res, %loop ]<br> store %v, ...<br><br>And the relevant check in LoopVectorizationLegality::blockCanBePredicated, does this:<br><br> if (it->mayReadFromMemory()) {<br> LoadInst *LI = dyn_cast<LoadInst>(it);<br> if (!LI)<br> return false;<br> if (!SafePtrs.count(LI->getPointerOperand())) {<br> if (isLegalMaskedLoad(LI->getType(), LI->getPointerOperand()) ||<br> isLegalMaskedGather(LI->getType())) {<br> MaskedOp.insert(LI);<br> continue;<br> }<br> return false;<br> }<br> }<br><br>and there's no exception here for (Hints.getForce() == LoopVectorizeHints::FK_Enabled).<br><br>The check just above this (for possibly-trapping constant operands), and the corresponding check in canIfConvertPHINodes, we might also skip if we're explicitly instructed to vectorize?<br><br>Also, one exception: If you target an instruction set with predicated (masked) vector loads, then we will vectorize this loop (with or without the pragma) by generated masked loads.<br></div></blockquote>With r267514 and r267515, we should now vectorize this loop with #pragma clang vectorize(assume_safety).<br><br> -Hal<br><blockquote style="border-left: 2px solid rgb(16, 16, 255); margin-left: 5px; padding-left: 5px; color: rgb(0, 0, 0); font-weight: normal; font-style: normal; text-decoration: none; font-family: Helvetica,Arial,sans-serif; font-size: 12pt;"><div style="font-family: arial,helvetica,sans-serif; font-size: 10pt; color: rgb(0, 0, 0);"><br> -Hal<br><blockquote style="border-left: 2px solid rgb(16, 16, 255); margin-left: 5px; padding-left: 5px; color: rgb(0, 0, 0); font-weight: normal; font-style: normal; text-decoration: none; font-family: Helvetica,Arial,sans-serif; font-size: 12pt;"><div></div><div><br class=""></div><div>Another way to help vectorizer in this case is to manually hoist the loads, like this:</div><div><font class="" face="Menlo"> int tmp_d = d[i];</font></div><div><font class="" face="Menlo"> res[i] = (p[i] == 0) ? res[i] : (res[i] + tmp_d);</font></div><div><br class=""></div><div><br class=""></div><div>Hope this helps,</div><div>Michael</div><div><br class=""></div><div><blockquote class=""><div class=""><div class=""><br class="">or you can use the OpenMP 4 pragma:<br class=""><br class=""> #pragma omp simd<br class=""><br class=""> -Hal<br class=""><br class=""><hr id="zwchr"><br class=""><blockquote class="">From: "RCU via llvm-dev" <<a href="mailto:llvm-dev@lists.llvm.org" class="" target="_blank">llvm-dev@lists.llvm.org</a>><br class="">To: "<a href="mailto:llvm-dev@lists.llvm.org" class="" target="_blank">llvm-dev@lists.llvm.org</a> >> llvm-dev" <<a href="mailto:llvm-dev@lists.llvm.org" class="" target="_blank">llvm-dev@lists.llvm.org</a>><br class="">Sent: Friday, April 22, 2016 4:21:22 PM<br class="">Subject: [llvm-dev] if-conversion<br class=""><br class="">Hi.<br class=""> I'm trying to vectorize the following piece of code with Loop<br class=""> Vectorizer (from LLVM<br class="">distribution Nov 2015), but no vectorization takes place:<br class=""> int *Test(int *res, int *c, int *d, int *p) {<br class=""> int i;<br class=""><br class=""> for (i = 0; i < 16; i++) {<br class=""> //res[i] = (p[i] == 0) ? c[i] : d[i];<br class=""> res[i] = (p[i] == 0) ? res[i] : res[i] + d[i];<br class=""> }<br class=""><br class=""> return NULL;<br class=""> }<br class=""><br class=""> It seems the problem is the if conversion, which is not working<br class=""> on this simple<br class="">example, although I guess it should.<br class=""> Is it a problem of low profitability given the loads?<br class=""><br class=""> Could you please tell me if there is any way to make If<br class=""> conversion work on programs<br class="">like this.<br class=""><br class=""><br class=""> Below is an older message from 2013 about the status of if<br class=""> conversion from LLVM at<br class="">that date (from<br class=""><a href="http://lists.llvm.org/pipermail/llvm-dev/2013-November/067427.html" class="" target="_blank">http://lists.llvm.org/pipermail/llvm-dev/2013-November/067427.html</a><br class="">or<br class="">https://groups.google.com/forum/#!msg/llvm-dev/FlDGnqSGbR8/YZUN3h4IzA8J<br class="">).<br class=""><blockquote class="">Hi Rob,<br class=""><br class="">I chose to answer on the list since from time to time people come<br class="">back<br class="">to this.<br class=""><br class="">That said, I did implement the generic variant of if-conversion<br class="">that is<br class="">called "control-flow to data-flow conversion" as a basis for SIMD<br class="">vectorization. Essentially, the conversion removes all control<br class="">flow<br class="">except for loop back edges and replaces it by masks and blend<br class="">(select)<br class="">operations.<br class=""><br class="">Details on the algorithm can be found in our paper on<br class="">"Whole-Function<br class="">Vectorization" (CGO 2011). The old, LLVM-based implementation of<br class="">the<br class="">algorithm is still online at github I believe. A completely<br class="">rewritten<br class="">one will be released along with submission of my PhD thesis at the<br class="">end<br class="">of the year.<br class=""><br class="">That said, if you are only looking for if-conversion of code with<br class="">limited complexity (e.g. no side effects, no loops), it is really<br class="">simple:<br class="">- Compute masks for every block (entry mask: disjunction of<br class="">incoming<br class="">masks, exit masks: conjunctions of entry mask and (negated)<br class="">condition).<br class="">- Replace each phi by a select that uses the entry mask of the<br class="">corresponding block.<br class="">- Order blocks topologically by data dependencies, remove outgoing<br class="">edges, create unconditional branches from each block to the next<br class="">in the<br class="">list.<br class=""><br class="">Cheers,<br class="">Ralf<br class=""><br class=""><br class="">On 06/11/13 19:50, RobBishop wrote:<br class=""><blockquote class="">Hi all,<br class=""><br class="">Sorry to dig up an old thread but I wondered what the status of<br class="">if-conversion in LLVM is. Has any work been done towards<br class="">handling this as a<br class="">transform pass on the IR?<br class=""><br class="">I'm looking to implement an if-conversion pass and wanted to<br class="">ensure that I'm<br class="">not duplicating work. Is this something that others would also<br class="">find useful?<br class=""><br class="">Rob<br class=""><br class=""><br class=""><br class="">--<br class="">View this message in context:<br class=""></blockquote>http://llvm.1065342.n5.nabble.com/if-conversion-tp2349p62937.html<br class=""><blockquote class="">Sent from the LLVM - Dev mailing list archive at Nabble.com.<br class="">_______________________________________________<br class="">LLVM Developers mailing list<br class="">LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu<br class="">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev<br class=""></blockquote></blockquote><br class=""><br class=""> Thank you,<br class=""> Alex<br class="">_______________________________________________<br class="">LLVM Developers mailing list<br class="">llvm-dev@lists.llvm.org<br class="">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev<br class=""><br class=""></blockquote><br class="">-- <br class="">Hal Finkel<br class="">Assistant Computational Scientist<br class="">Leadership Computing Facility<br class="">Argonne National Laboratory<br class="">_______________________________________________<br class="">LLVM Developers mailing list<br class=""><a href="mailto:llvm-dev@lists.llvm.org" class="" target="_blank">llvm-dev@lists.llvm.org</a><br class="">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev<br class=""></div></div></blockquote></div><br class=""></blockquote><br><br><br>-- <br><div><span></span>Hal Finkel<br>Assistant Computational Scientist<br>Leadership Computing Facility<br>Argonne National Laboratory<span></span><br></div></div><br>_______________________________________________<br>LLVM Developers mailing list<br>llvm-dev@lists.llvm.org<br>http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev<br></blockquote><br><br><br>-- <br><div><span name="x"></span>Hal Finkel<br>Assistant Computational Scientist<br>Leadership Computing Facility<br>Argonne National Laboratory<span name="x"></span><br></div></div></body></html>