<div dir="ltr">Thank you.<div><br></div><div>your command is able to vectorize the code</div></div><div class="gmail_extra"><br><div class="gmail_quote">On Wed, Oct 25, 2017 at 5:34 PM, Michael Kruse <span dir="ltr"><<a href="mailto:llvmdev@meinersbur.de" target="_blank">llvmdev@meinersbur.de</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">$ opt -O3 stencil.ll -pass-remarks=loop-vectorize -enable-load-pre=0<br>
<br>
remark: <unknown>:0:0: vectorized loop (vectorization width: 16,<br>
interleaved count: 1)<br>
<span class="HOEnZb"><font color="#888888"><br>
Michael<br>
</font></span><div class="HOEnZb"><div class="h5"><br>
2017-10-24 20:37 GMT+02:00 hameeza ahmed <<a href="mailto:hahmed2305@gmail.com">hahmed2305@gmail.com</a>>:<br>
> Thank you.<br>
><br>
> But how to resolve it, my work depends on it.<br>
><br>
> On Tue, Oct 24, 2017 at 6:30 PM, Michael Kruse <<a href="mailto:llvmdev@meinersbur.de">llvmdev@meinersbur.de</a>><br>
> wrote:<br>
>><br>
>> Your problem is due to GVN partial reduction elimination (PRE) which<br>
>> introduces a PHI node the current loop vectorizer cannot handle:<br>
>><br>
>> opt -O3 stencil.ll -pass-remarks=loop-vectorize<br>
>> -pass-remarks-missed=loop-<wbr>vectorize<br>
>> -pass-remarks-analysis=loop-<wbr>vectorize<br>
>> remark: <unknown>:0:0: loop not vectorized: value that could not be<br>
>> identified as reduction is used outside the loop<br>
>> remark: <unknown>:0:0: loop not vectorized<br>
>><br>
>> The message is not entirely accurate. The PHI is not used outside of<br>
>> the loop, but is in the loop header, therefore cannot be if-converted<br>
>> and is not a reduction. Polly also had difficulties with this<br>
>> construction as well.<br>
>><br>
>> As presented at the dev meeting, VPlan will be able to insert a<br>
>> shuffle instruction when encountering this situation.<br>
>><br>
>><br>
>> Michael<br>
>><br>
>><br>
>><br>
>><br>
>><br>
>> 2017-10-23 8:58 GMT+02:00 hameeza ahmed via llvm-dev<br>
>> <<a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a>>:<br>
>> > stencil.ll is attached here.<br>
>> ><br>
>> > On Mon, Oct 23, 2017 at 11:37 AM, Serge Preis <<a href="mailto:spreis@yandex-team.ru">spreis@yandex-team.ru</a>><br>
>> > wrote:<br>
>> >><br>
>> >><br>
>> >><br>
>> >> Hello,<br>
>> >><br>
>> >> To me this is an issue in llvm loop vectorizer (if N is large enough to<br>
>> >> prevent complete unrolling of j-loop).<br>
>> >><br>
>> >> Woud you mind to share stencil.ll than I would say more definitely what<br>
>> >> the issue is.<br>
>> >><br>
>> >> Regards,<br>
>> >> Serge.<br>
>> >><br>
>> >><br>
>> >> 22.10.2017, 03:21, "hameeza ahmed" <<a href="mailto:hahmed2305@gmail.com">hahmed2305@gmail.com</a>>:<br>
>> >><br>
>> >> Hello,<br>
>> >><br>
>> >> The following stencil function that you wrote few months ago (for<br>
>> >> computing 2D-5 point Jacobi stencil) is vectorizable.<br>
>> >><br>
>> >> void stencil(int a[][N], int b[N])<br>
>> >> {<br>
>> >> int i, j, k;<br>
>> >> for (k = 0; k < N; k++) {<br>
>> >> for (i = 1; i <= N-2; i++) {<br>
>> >> for (j = 1; j <= N-2; j++)<br>
>> >> b[j] = 0.25 * (a[i][j] + a[i-1][j] + a[i+1][j] +<br>
>> >> a[i][j-1] + a[i][j+1]);<br>
>> >> for (j = 1; j <= N-2; j++)<br>
>> >> a[i][j] = b[j];<br>
>> >> }<br>
>> >> }<br>
>> >> }<br>
>> >><br>
>> >> but when i write the above code in main i am getting error<br>
>> >><br>
>> >> opt -S -O3 stencil.ll -o stencil_o3.ll<br>
>> >> remark: <unknown>:0:0: loop not vectorized: value that could not be<br>
>> >> identified as reduction is used outside the loop<br>
>> >><br>
>> >> Why is that so?<br>
>> >><br>
>> >> my code is follows:<br>
>> >> int a[N][N], b[N];<br>
>> >> int main(void)<br>
>> >> {<br>
>> >> int i, j, k;<br>
>> >> for (k = 0; k < N; k++) {<br>
>> >> for (i = 1; i <= N-2; i++) {<br>
>> >> for (j = 1; j <= N-2; j++)<br>
>> >> b[j] = 0.25 * (a[i][j] + a[i-1][j] + a[i+1][j] +<br>
>> >> a[i][j-1] + a[i][j+1]);<br>
>> >> for (j = 1; j <= N-2; j++)<br>
>> >> a[i][j] = b[j];<br>
>> >> }<br>
>> >> }<br>
>> >> }<br>
>> >><br>
>> >><br>
>> >> Please help.<br>
>> >><br>
>> >> Thank You.<br>
>> >><br>
>> >><br>
>> >> On Mon, Jul 3, 2017 at 10:19 AM, Serge Preis <<a href="mailto:spreis@yandex-team.ru">spreis@yandex-team.ru</a>><br>
>> >> wrote:<br>
>> >><br>
>> >> Hello,<br>
>> >><br>
>> >> This is not equivalent rewrite: your original code definitely shouldn't<br>
>> >> vectorize because it has backward cross-iteration (loop-carried)<br>
>> >> dependency:<br>
>> >> your value on iteration j+1 depend on value from iteration j you've<br>
>> >> just<br>
>> >> written. In case of vectorization you need to do load-operation-store<br>
>> >> on<br>
>> >> multiple consecutive values at once and it is impossible in this case.<br>
>> >><br>
>> >> In your new code all values of a[] in right-hand side of the main loop<br>
>> >> are<br>
>> >> from previous k iteration (because on current k iteration you're<br>
>> >> writing to<br>
>> >> 'b'). So there is no way to vectorize loop in its original form, but<br>
>> >> new<br>
>> >> form is definitely vectorizable.<br>
>> >><br>
>> >> I am second to recommend you filing a bug over 'restrict' behavior. And<br>
>> >> you may in fact save some memory by making 'b' 1D array (this is not<br>
>> >> equivalent rewrite once again though)<br>
>> >><br>
>> >> // This function computes 2D-5 point Jacobi stencil<br>
>> >> void stencil(int a[][N], int b[N])<br>
>> >> {<br>
>> >> int i, j, k;<br>
>> >> for (k = 0; k < N; k++) {<br>
>> >> for (i = 1; i <= N-2; i++) {<br>
>> >> for (j = 1; j <= N-2; j++)<br>
>> >> b[j] = 0.25 * (a[i][j] + a[i-1][j] + a[i+1][j] +<br>
>> >> a[i][j-1] + a[i][j+1]);<br>
>> >> for (j = 1; j <= N-2; j++)<br>
>> >> a[i][j] = b[j];<br>
>> >> }<br>
>> >> }<br>
>> >> }<br>
>> >><br>
>> >> There is a way to vectorize your code even more efficient. This will<br>
>> >> look<br>
>> >> like more low-level, but probably closest to what you would expect from<br>
>> >> vectorization.<br>
>> >><br>
>> >> void stencil(int a[][N])<br>
>> >> {<br>
>> >> int i, j, k;<br>
>> >> for (k = 0; k < 100; k++) {<br>
>> >> for (i = 1; i <= N-2; i++) {<br>
>> >> for (j = 1; j <= N-2; j+=16) {<br>
>> >> int b[16]; // This should become a register on KNL<br>
>> >> for (v = 0; v < 16; v++) {<br>
>> >> b[v] = 0.25 * (a[i][j+v] + a[i-1][j+v] + a[i+1][j+v]<br>
>> >> +<br>
>> >> a[i][j-1+v] + a[i][j+1+v]);<br>
>> >> }<br>
>> >> for (v = 0; v < 16; v++) { // This will be a single<br>
>> >> store<br>
>> >> operation<br>
>> >> a[i][j+v] = b[v];<br>
>> >> }<br>
>> >> }<br>
>> >> // You should explicitly take care about the tail of j-loop<br>
>> >> #if !MASKED_SHORT_LOOP_<wbr>VECTORIZATION_SUPPORTED // This is not an<br>
>> >> actual<br>
>> >> name, just a designator<br>
>> >> for (;j <= N-2; j++) {<br>
>> >> a[i][j] = 0.25 * (a[i][j] + a[i-1][j] + a[i+1][j] +<br>
>> >> a[i][j-1] + a[i][j+1]);<br>
>> >> }<br>
>> >> #else<br>
>> >> for (v = 0; v < 16-(N-2-j); v++) { // This would become<br>
>> >> masked<br>
>> >> non-loop<br>
>> >> b[v] = 0.25 * (a[i][j+v] + a[i-1][j+v] + a[i+1][j+v] +<br>
>> >> a[i][j-1+v] + a[i][j+1+v]);<br>
>> >> }<br>
>> >> for (v = 0; v < 16-(N-2-j); v++) { // This will be a single<br>
>> >> masked store operation<br>
>> >> a[i][j+v] = b[v];<br>
>> >> }<br>
>> >> #endif<br>
>> >> }<br>
>> >> }<br>
>> >><br>
>> >> Unfortunalely compiler cannot do this for you: this is not equivalent<br>
>> >> transformation of original code. I am also not aware of any way to<br>
>> >> express<br>
>> >> this desired behavior less explicitly (e.g. OpenMP SIMD pragma won't<br>
>> >> work in<br>
>> >> this case).<br>
>> >><br>
>> >> Minor note: You're using 'int' for data, than multiply by 0.25 (divide<br>
>> >> by<br>
>> >> 4) and than write it back to 'int'. This will cost you 2 conversion<br>
>> >> to/from<br>
>> >> double while you may just place (...) / 4 which should be optimized to<br>
>> >> simple sequecnce with shifts (not to single shift due to signedness,<br>
>> >> but<br>
>> >> still better than conversions with changes of element size 4->8->4 and<br>
>> >> data<br>
>> >> size INT->FP->INT).<br>
>> >><br>
>> >> And by the way why do you divide by 4, not by 5 as number of points<br>
>> >> suggest?<br>
>> >><br>
>> >> Serge Preis<br>
>> >><br>
>> >><br>
>> >> 02.07.2017, 05:11, "hameeza ahmed via llvm-dev"<br>
>> >> <<a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a>>:<br>
>> >> > further i modified the code to the following;<br>
>> >> ><br>
>> >> > #include <stdio.h><br>
>> >> > #define N 100351<br>
>> >> ><br>
>> >> > // This function computes 2D-5 point Jacobi stencil<br>
>> >> > void stencil(int a[restrict][N], int b[restrict][N])<br>
>> >> > {<br>
>> >> > int i, j, k;<br>
>> >> > for (k = 0; k < N; k++) {<br>
>> >> > for (i = 1; i <= N-2; i++)<br>
>> >> > for (j = 1; j <= N-2; j++)<br>
>> >> > b[i][j] = 0.25 * (a[i][j] + a[i-1][j] + a[i+1][j] + a[i][j-1]<br>
>> >> > +<br>
>> >> > a[i][j+1]);<br>
>> >> ><br>
>> >> > for (i = 1; i <= N-2; i++)<br>
>> >> > for (j = 1; j <= N-2; j++)<br>
>> >> > a[i][j] = b[i][j];<br>
>> >> ><br>
>> >> > }<br>
>> >> > }<br>
>> >> ><br>
>> >> > but still no vectorization in IR. Also, when I set vector width<br>
>> >> > explicitly to 64, it gives the following error:<br>
>> >> ><br>
>> >> > remark: <unknown>:0:0: loop not vectorized: call instruction cannot<br>
>> >> > be<br>
>> >> > vectorized<br>
>> >> > remark: <unknown>:0:0: loop not vectorized: value that could not be<br>
>> >> > identified as reduction is used outside the loop<br>
>> >> ><br>
>> >> > I need serious help on this. Please guide me.<br>
>> >> ><br>
>> >> > On Sun, Jul 2, 2017 at 1:54 AM, hameeza ahmed <<a href="mailto:hahmed2305@gmail.com">hahmed2305@gmail.com</a>><br>
>> >> > wrote:<br>
>> >> >> Does it happen due to loop carried dependence? if yes what is the<br>
>> >> >> solution to vectorize such codes?<br>
>> >> >><br>
>> >> >> please reply. i m waiting.<br>
>> >> >><br>
>> >> >> On Jul 1, 2017 12:30 PM, "hameeza ahmed" <<a href="mailto:hahmed2305@gmail.com">hahmed2305@gmail.com</a>><br>
>> >> >> wrote:<br>
>> >> >>> I even tried polly but still my llvm IR does not contain vector<br>
>> >> >>> instructions. i used the following command;<br>
>> >> >>><br>
>> >> >>> clang -S -emit-llvm stencil.c -march=knl -O3 -mllvm -polly -mllvm<br>
>> >> >>> -polly-vectorizer=stripmine -o stencil_poly.ll<br>
>> >> >>><br>
>> >> >>> Please specify what is wrong with my code?<br>
>> >> >>><br>
>> >> >>> On Sat, Jul 1, 2017 at 4:08 PM, hameeza ahmed<br>
>> >> >>> <<a href="mailto:hahmed2305@gmail.com">hahmed2305@gmail.com</a>><br>
>> >> >>> wrote:<br>
>> >> >>>> Hello,<br>
>> >> >>>><br>
>> >> >>>> I am trying to vectorize following stencil code;<br>
>> >> >>>><br>
>> >> >>>> #include <stdio.h><br>
>> >> >>>> #define N 100351<br>
>> >> >>>><br>
>> >> >>>> // This function computes 2D-5 point Jacobi stencil<br>
>> >> >>>> void stencil(int a[restrict][N])<br>
>> >> >>>> {<br>
>> >> >>>> int i, j, k;<br>
>> >> >>>> for (k = 0; k < 100; k++)<br>
>> >> >>>> { for (i = 1; i <= N-2; i++)<br>
>> >> >>>> { for (j = 1; j <= N-2; j++)<br>
>> >> >>>> { a[i][j] = 0.25 * (a[i][j] + a[i-1][j] + a[i+1][j] +<br>
>> >> >>>> a[i][j-1] + a[i][j+1]);<br>
>> >> >>>> }<br>
>> >> >>>> }<br>
>> >> >>>> }}<br>
>> >> >>>><br>
>> >> >>>> I have used the following commands<br>
>> >> >>>><br>
>> >> >>>> clang -S -emit-llvm stencil.c -march=knl -O3 -mllvm<br>
>> >> >>>> -disable-llvm-optzns -o stencil.ll<br>
>> >> >>>><br>
>> >> >>>> opt -S -O3 stencil.ll -o stencil_o3.ll<br>
>> >> >>>><br>
>> >> >>>> llc -x86-asm-syntax=intel stencil_o3.ll -o stencil.s<br>
>> >> >>>><br>
>> >> >>>> But the code is not vectorized. It still uses the scalar<br>
>> >> >>>> instructions;<br>
>> >> >>>><br>
>> >> >>>> Please correct me.<br>
>> >> >>>><br>
>> >> >>>> Thank You<br>
>> >> > ,<br>
>> >> ><br>
>> >> > ______________________________<wbr>_________________<br>
>> >> > LLVM Developers mailing list<br>
>> >> > <a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a><br>
>> >> > <a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" rel="noreferrer" target="_blank">http://lists.llvm.org/cgi-bin/<wbr>mailman/listinfo/llvm-dev</a><br>
>> ><br>
>> ><br>
>> ><br>
>> > ______________________________<wbr>_________________<br>
>> > LLVM Developers mailing list<br>
>> > <a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a><br>
>> > <a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" rel="noreferrer" target="_blank">http://lists.llvm.org/cgi-bin/<wbr>mailman/listinfo/llvm-dev</a><br>
>> ><br>
><br>
><br>
</div></div></blockquote></div><br></div>