[LLVMdev] speculative parallelization in LLVM

[Jimborean Alexandra]

This is exactly want I need to achieve with Polly actually. I think a good idea 
would be to define intrinsics / metadata, as you mentioned, to notify Polly that 
even though it cannot analyse these accesses, to ignore them and perform the 
code transformations. We can go even further and maybe describe these accesses 
with some parametric linear functions. 


For instance:

while (cond1){
    while(cond2){
           p=p->next;
    }
}


to introduce virtual iterators of the enclosing loops, i and j , and replace the 
accesses inside the loop with virtual accesses that have the form a*i + b*j + c

%1 = polly.virtual_read() !polly !"  {a1*i + b1*j + c1}"
polly.virtual_write(%ptr) !polly !"    {a2*i + b2*j + c2}"

Next at runtime it will be easier to change the virtual accesses to the original 
pointers, and to compute the values to the coefficients a1, b1 ... to check if 
they follow the linearity.  I perform dynamic instrumentation to compute the 
coefficients.

However, for applying the transformations, Polly should either totally ignore 
the virtual accesses, or assign some default values to the coefficients and take 
them into consideration. Our plan is to create several versions, some with 
different values, lets say  a = 1, b= 1, c = 0, and one version where all the 
virtual accesses are ignored.

What is important is to be able to track the virtual accesses and to be able to 
replace them with the original ones.

Do you think this represents a lot of work in Polly? And do you plan to include 
this kind of support to handle non-statically analysable code? In case this 
doesn't imply significant changes in Polly, I could start working on this. It 
might be a better approach than converting the code into a form accepted by 
Polly :)


Alexandra


________________________________
From: Tobias Grosser <tobias at grosser.es>
To: Jimborean Alexandra <xinfinity_a at yahoo.com>
Cc: llvmdev at cs.uiuc.edu
Sent: Tue, July 19, 2011 11:53:23 AM
Subject: Re: [LLVMdev] speculative parallelization in LLVM

On 07/19/2011 11:12 AM, Jimborean Alexandra wrote:
> Hi Tobi,
> 
> Thank you for your reply :).
> 
> I know that array accesses are handled as pointers in LLVM, but as I
> understood Polly is focused on statically analysable code. As you
> mentioned: proving that pointer accesses actually represent virtual
> array accesses.
> 
[...]
> 
> Is this approach going to work with Polly? Or can I generate optimized
> code versions with Polly in a different manner when there are pointers
> and indirect references inside the code?

OK. Perfect. Here we are. Thanks for the nice explanation. Now I get what you 
plan to do and I am extremely interested in how you will solve this.

So yes, I assume the translation of your code into statically analyzable code 
should work. The only problem I see is that it may take some time to generate 
code that is really statically analyzable and that at the same time can easily 
be converted back to the original code. Especially if afterwords the code is/was 
further optimized.
Furthermore, it you may trigger some cases that Polly cannot yet handle.

One thing I was reasoning about for a while, is if it is possible to
simplify the generation of code that Polly can recognize, such that frontends 
like clang, but also your tool can generate code that we can be sure Polly can 
handle. Here, I think it would be especially interesting to be able to make 
Polly also parse some kind of virtual accesses, were the details of the accesses 
are hidden and Polly only gets the information, that this access acts like an 
access to a virtual array.

Describing this virtual accesses by using some kind of intrinsics combined with 
meta data may be possible.

%1 = polly.virtual_read() !polly !"{A[i][2j][3k]}"
polly.virtual_write(%ptr) !polly !"{A[i][2j][3k]}"

Like this you can simply transform your linked list into virtual accesses, and 
Polly generates the code that executes these accesses,
and at the end you replace them with the actual code.

(The definition of this is far from complete and the example above needs 
probably be changed to be actually usable. Still, I hope it gives the general 
idea.)

Let me know what you think and what you need exactly. Maybe we can work out 
together a good way to represent such virtual accesses.

Cheers
Tobi
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20110719/7c082780/attachment.html>