Hi.
I'm trying to vectorize the following piece of code with Loop
Vectorizer (from LLVM
distribution Nov 2015), but no vectorization takes place:
int *Test(int *res, int *c, int *d, int *p) {
int i;
for (i = 0; i < 16; i++) {
//res[i] = (p[i] == 0) ? c[i] : d[i];
res[i] = (p[i] == 0) ? res[i] : res[i] + d[i];
}
return NULL;
}
It seems the problem is the if conversion, which is not working on this
simple
example, although I guess it should.
Is it a problem of low profitability given the loads?
Could you please tell me if there is any way to make If conversion work on
programs
like this.
Below is an older message from 2013 about the status of if conversion from
LLVM at
that date (from
http://lists.llvm.org/pipermail/llvm-dev/2013-November/067427.html or
https://groups.google.com/forum/#!msg/llvm-dev/FlDGnqSGbR8/YZUN3h4IzA8J ).
> Hi Rob,
>
> I chose to answer on the list since from time to time people come back
> to this.
>
> That said, I did implement the generic variant of if-conversion that is
> called "control-flow to data-flow conversion" as a basis for
SIMD
> vectorization. Essentially, the conversion removes all control flow
> except for loop back edges and replaces it by masks and blend (select)
> operations.
>
> Details on the algorithm can be found in our paper on "Whole-Function
> Vectorization" (CGO 2011). The old, LLVM-based implementation of the
> algorithm is still online at github I believe. A completely rewritten
> one will be released along with submission of my PhD thesis at the end
> of the year.
>
> That said, if you are only looking for if-conversion of code with
> limited complexity (e.g. no side effects, no loops), it is really simple:
> - Compute masks for every block (entry mask: disjunction of incoming
> masks, exit masks: conjunctions of entry mask and (negated) condition).
> - Replace each phi by a select that uses the entry mask of the
> corresponding block.
> - Order blocks topologically by data dependencies, remove outgoing
> edges, create unconditional branches from each block to the next in the
> list.
>
> Cheers,
> Ralf
>
>
> On 06/11/13 19:50, RobBishop wrote:
> > Hi all,
> >
> > Sorry to dig up an old thread but I wondered what the status of
> > if-conversion in LLVM is. Has any work been done towards handling
this as a
> > transform pass on the IR?
> >
> > I'm looking to implement an if-conversion pass and wanted to
ensure that I'm
> > not duplicating work. Is this something that others would also find
useful?
> >
> > Rob
> >
> >
> >
> > --
> > View this message in context:
> http://llvm.1065342.n5.nabble.com/if-conversion-tp2349p62937.html
> > Sent from the LLVM - Dev mailing list archive at Nabble.com.
> > _______________________________________________
> > LLVM Developers mailing list
> > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu
> > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Thank you,
Alex
Hi Rob, 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). You can inform LLVM that it is safe to vectorize anyway by adding a pragma, like this: #pragma clang loop vectorize(assume_safety) or you can use the OpenMP 4 pragma: #pragma omp simd -Hal ----- Original Message -----> From: "RCU via llvm-dev" <llvm-dev at lists.llvm.org> > To: "llvm-dev at lists.llvm.org >> llvm-dev" <llvm-dev at lists.llvm.org> > Sent: Friday, April 22, 2016 4:21:22 PM > Subject: [llvm-dev] if-conversion > > Hi. > I'm trying to vectorize the following piece of code with Loop > Vectorizer (from LLVM > distribution Nov 2015), but no vectorization takes place: > int *Test(int *res, int *c, int *d, int *p) { > int i; > > for (i = 0; i < 16; i++) { > //res[i] = (p[i] == 0) ? c[i] : d[i]; > res[i] = (p[i] == 0) ? res[i] : res[i] + d[i]; > } > > return NULL; > } > > It seems the problem is the if conversion, which is not working > on this simple > example, although I guess it should. > Is it a problem of low profitability given the loads? > > Could you please tell me if there is any way to make If > conversion work on programs > like this. > > > Below is an older message from 2013 about the status of if > conversion from LLVM at > that date (from > http://lists.llvm.org/pipermail/llvm-dev/2013-November/067427.html > or > https://groups.google.com/forum/#!msg/llvm-dev/FlDGnqSGbR8/YZUN3h4IzA8J > ). > > Hi Rob, > > > > I chose to answer on the list since from time to time people come > > back > > to this. > > > > That said, I did implement the generic variant of if-conversion > > that is > > called "control-flow to data-flow conversion" as a basis for SIMD > > vectorization. Essentially, the conversion removes all control > > flow > > except for loop back edges and replaces it by masks and blend > > (select) > > operations. > > > > Details on the algorithm can be found in our paper on > > "Whole-Function > > Vectorization" (CGO 2011). The old, LLVM-based implementation of > > the > > algorithm is still online at github I believe. A completely > > rewritten > > one will be released along with submission of my PhD thesis at the > > end > > of the year. > > > > That said, if you are only looking for if-conversion of code with > > limited complexity (e.g. no side effects, no loops), it is really > > simple: > > - Compute masks for every block (entry mask: disjunction of > > incoming > > masks, exit masks: conjunctions of entry mask and (negated) > > condition). > > - Replace each phi by a select that uses the entry mask of the > > corresponding block. > > - Order blocks topologically by data dependencies, remove outgoing > > edges, create unconditional branches from each block to the next > > in the > > list. > > > > Cheers, > > Ralf > > > > > > On 06/11/13 19:50, RobBishop wrote: > > > Hi all, > > > > > > Sorry to dig up an old thread but I wondered what the status of > > > if-conversion in LLVM is. Has any work been done towards > > > handling this as a > > > transform pass on the IR? > > > > > > I'm looking to implement an if-conversion pass and wanted to > > > ensure that I'm > > > not duplicating work. Is this something that others would also > > > find useful? > > > > > > Rob > > > > > > > > > > > > -- > > > View this message in context: > > http://llvm.1065342.n5.nabble.com/if-conversion-tp2349p62937.html > > > Sent from the LLVM - Dev mailing list archive at Nabble.com. > > > _______________________________________________ > > > LLVM Developers mailing list > > > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > > > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev > > > Thank you, > Alex > _______________________________________________ > LLVM Developers mailing list > llvm-dev at lists.llvm.org > http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev >-- Hal Finkel Assistant Computational Scientist Leadership Computing Facility Argonne National Laboratory
Hi,> On Apr 22, 2016, at 8:27 PM, Hal Finkel via llvm-dev <llvm-dev at lists.llvm.org> wrote: > > Hi Rob, > > 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). > > You can inform LLVM that it is safe to vectorize anyway by adding a pragma, like this: > > #pragma clang loop vectorize(assume_safety)I don’t think it would be enough (due to current limitations of vectorizer). The following expression will be vectorizable: res[i] = (p[i] == 0) ? (res[i] + c[i]) : (res[i] + d[i]); // Note “+ c[i]” 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. Another way to help vectorizer in this case is to manually hoist the loads, like this: int tmp_d = d[i]; res[i] = (p[i] == 0) ? res[i] : (res[i] + tmp_d); Hope this helps, Michael> > or you can use the OpenMP 4 pragma: > > #pragma omp simd > > -Hal > > ----- Original Message ----- >> From: "RCU via llvm-dev" <llvm-dev at lists.llvm.org> >> To: "llvm-dev at lists.llvm.org >> llvm-dev" <llvm-dev at lists.llvm.org> >> Sent: Friday, April 22, 2016 4:21:22 PM >> Subject: [llvm-dev] if-conversion >> >> Hi. >> I'm trying to vectorize the following piece of code with Loop >> Vectorizer (from LLVM >> distribution Nov 2015), but no vectorization takes place: >> int *Test(int *res, int *c, int *d, int *p) { >> int i; >> >> for (i = 0; i < 16; i++) { >> //res[i] = (p[i] == 0) ? c[i] : d[i]; >> res[i] = (p[i] == 0) ? res[i] : res[i] + d[i]; >> } >> >> return NULL; >> } >> >> It seems the problem is the if conversion, which is not working >> on this simple >> example, although I guess it should. >> Is it a problem of low profitability given the loads? >> >> Could you please tell me if there is any way to make If >> conversion work on programs >> like this. >> >> >> Below is an older message from 2013 about the status of if >> conversion from LLVM at >> that date (from >> http://lists.llvm.org/pipermail/llvm-dev/2013-November/067427.html >> or >> https://groups.google.com/forum/#!msg/llvm-dev/FlDGnqSGbR8/YZUN3h4IzA8J >> ). >>> Hi Rob, >>> >>> I chose to answer on the list since from time to time people come >>> back >>> to this. >>> >>> That said, I did implement the generic variant of if-conversion >>> that is >>> called "control-flow to data-flow conversion" as a basis for SIMD >>> vectorization. Essentially, the conversion removes all control >>> flow >>> except for loop back edges and replaces it by masks and blend >>> (select) >>> operations. >>> >>> Details on the algorithm can be found in our paper on >>> "Whole-Function >>> Vectorization" (CGO 2011). The old, LLVM-based implementation of >>> the >>> algorithm is still online at github I believe. A completely >>> rewritten >>> one will be released along with submission of my PhD thesis at the >>> end >>> of the year. >>> >>> That said, if you are only looking for if-conversion of code with >>> limited complexity (e.g. no side effects, no loops), it is really >>> simple: >>> - Compute masks for every block (entry mask: disjunction of >>> incoming >>> masks, exit masks: conjunctions of entry mask and (negated) >>> condition). >>> - Replace each phi by a select that uses the entry mask of the >>> corresponding block. >>> - Order blocks topologically by data dependencies, remove outgoing >>> edges, create unconditional branches from each block to the next >>> in the >>> list. >>> >>> Cheers, >>> Ralf >>> >>> >>> On 06/11/13 19:50, RobBishop wrote: >>>> Hi all, >>>> >>>> Sorry to dig up an old thread but I wondered what the status of >>>> if-conversion in LLVM is. Has any work been done towards >>>> handling this as a >>>> transform pass on the IR? >>>> >>>> I'm looking to implement an if-conversion pass and wanted to >>>> ensure that I'm >>>> not duplicating work. Is this something that others would also >>>> find useful? >>>> >>>> Rob >>>> >>>> >>>> >>>> -- >>>> View this message in context: >>> http://llvm.1065342.n5.nabble.com/if-conversion-tp2349p62937.html >>>> Sent from the LLVM - Dev mailing list archive at Nabble.com. >>>> _______________________________________________ >>>> LLVM Developers mailing list >>>> LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu >>>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev >> >> >> Thank you, >> Alex >> _______________________________________________ >> LLVM Developers mailing list >> llvm-dev at lists.llvm.org >> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev >> > > -- > Hal Finkel > Assistant Computational Scientist > Leadership Computing Facility > Argonne National Laboratory > _______________________________________________ > LLVM Developers mailing list > llvm-dev at lists.llvm.org > http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20160423/8589a9e7/attachment.html>