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>
On 07/19/2011 02:11 PM, Jimborean Alexandra wrote:> > 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.Mh. I believe we should distinguish the data for Polly and for your calculations. I assumed we would use affine linear relations in the access functions (Actually isl_maps like {[i,j] -> List[10i + 30j + 10]) to define accesses such that Polly can use this access functions to calculate dependences and reschedule the code accordingly. The possibly non-affine accesses would then be hidden behind the virtual access.> 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 conosideration. 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 do you mean by totally ignoring the virtual accesses? This would mean Polly would not detect any dependences at all and we would generate always fully parallel code? Is this what you want even if the code accesses an element of a list several times and actually has dependences between these elements? I was thinking in your tool you could generate several versions of the code, where each version has another set of affine linear access functions initialized from your parametric affine linear functions. Like this Polly would schedule each version differently.> What is important is to be able to track the virtual accesses and to be > able to replace them with the original ones.What information do you need from the surrounding code? Do you need the values of i and j? Then I would propose we add them as arguments of our intrinsics: %1 = polly.virtual_read(%i, %j) !polly !" {a1*i + b1*j + c1}" polly.virtual_write(%ptr, %i, %j) !polly !" {a2*i + b2*j + c2}" Do you need anything else?> 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?Adding support for those virtual access functions should not be too difficult and I am happy to help you to add such support. I have currently no plans to work on support for non-statically analyzable code, but am also happy to support and/or add your work.> 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 :)Sounds good. What about discussing a full blown example to understand what needs to be changed in Polly and how exactly we want to represent this? Cheers Tobi
Hi> 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. Mh. I believe we should distinguish the data for Polly and for your calculations. I assumed we would use affine linear relations in the access functions (Actually isl_maps like {[i,j] -> List[10i + 30j + 10]) to define accesses such that Polly can use this access functions to calculate dependences and reschedule the code accordingly. The possibly non-affine accesses would then be hidden behind the virtual access.> 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 conosideration. 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 do you mean by totally ignoring the virtual accesses? This would mean Polly would not detect any dependences at all and we would generate always fully parallel code? Is this what you want even if the code accesses an element of a list several times and actually has dependences between these elements? I was thinking in your tool you could generate several versions of the code, where each version has another set of affine linear access functions initialized from your parametric affine linear functions. Like this Polly would schedule each version differently. Yes, this is what I meant, to assign different values at compile time to the coefficients and build several versions with Polly. By "ignoring them" I was thinking that Polly could build one more version in which it takes into consideration only the statically computable accesses, generates the transformations, and at runtime I will check if the pointer accesses comply (if the schedule is still valid with the dependencies they introduce). This might be suitable for codes with a lot of array accesses, and maybe just a few pointers. But this is just an idea, not necessarily relevant. The main strategy is to generate several versions using different access functions.> What is important is to be able to track the virtual accesses and to be > able to replace them with the original ones.What information do you need from the surrounding code? Do you need the values of i and j? Then I would propose we add them as arguments of our intrinsics: %1 = polly.virtual_read(%i, %j) !polly !" {a1*i + b1*j + c1}" polly.virtual_write(%ptr, %i, %j) !polly !" {a2*i + b2*j + c2}" Do you need anything else?> 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?Adding support for those virtual access functions should not be too difficult and I am happy to help you to add such support. I have currently no plans to work on support for non-statically analyzable code, but am also happy to support and/or add your work.> 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 :)Sounds good. What about discussing a full blown example to understand what needs to be changed in Polly and how exactly we want to represent this? Ok, I will keep this in mind. For the moment we did not decide yet upon the strategy to apply, but in case I will start extending Polly, I will reply to this message with a concrete example. Thanks for your support. Cheers, Alexandra -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20110721/53d11829/attachment.html>