[llvm-dev] if-conversion

Sat Apr 23 12:25:23 PDT 2016

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>