[llvm-dev] if-conversion
Hal Finkel via llvm-dev
llvm-dev at lists.llvm.org
Mon Apr 25 19:13:34 PDT 2016
----- Original Message -----
> From: "Hal Finkel via llvm-dev" <llvm-dev at lists.llvm.org>
> To: "Michael Zolotukhin" <mzolotukhin at apple.com>
> Cc: "llvm-dev at lists.llvm.org >> llvm-dev" <llvm-dev at lists.llvm.org>
> Sent: Sunday, April 24, 2016 8:09:24 AM
> Subject: Re: [llvm-dev] if-conversion
> ----- Original Message -----
> > From: "Michael Zolotukhin" <mzolotukhin at apple.com>
>
> > To: "Hal Finkel" <hfinkel at anl.gov>
>
> > Cc: "RCU" <alex.e.susu at gmail.com>, "llvm-dev at lists.llvm.org >>
> > llvm-dev" <llvm-dev at lists.llvm.org>
>
> > Sent: Saturday, April 23, 2016 2:25:23 PM
>
> > Subject: Re: [llvm-dev] if-conversion
>
> > 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.
>
> 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:
> loop:
> ...
> %res = load ...
> %p = load
> %c = icmp eq i32 %p, 0
> %br i1 %c, label %load_and_add, label %do_store
> load_and_add:
> %d = load ...
> %resd = add i32 %res, %d
> do_store:
> %v = phi [ %resd, %load_and_add ], [ %res, %loop ]
> store %v, ...
> And the relevant check in
> LoopVectorizationLegality::blockCanBePredicated, does this:
> if (it->mayReadFromMemory()) {
> LoadInst *LI = dyn_cast<LoadInst>(it);
> if (!LI)
> return false;
> if (!SafePtrs.count(LI->getPointerOperand())) {
> if (isLegalMaskedLoad(LI->getType(), LI->getPointerOperand()) ||
> isLegalMaskedGather(LI->getType())) {
> MaskedOp.insert(LI);
> continue;
> }
> return false;
> }
> }
> and there's no exception here for (Hints.getForce() ==
> LoopVectorizeHints::FK_Enabled).
> 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?
> 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.
With r267514 and r267515, we should now vectorize this loop with #pragma clang vectorize(assume_safety).
-Hal
> -Hal
> > 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
> >
>
> --
> 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
--
Hal Finkel
Assistant Computational Scientist
Leadership Computing Facility
Argonne National Laboratory
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20160425/eb1a037a/attachment-0001.html>
More information about the llvm-dev
mailing list