[LLVMdev] speculative parallelization in LLVM

[Jimborean Alexandra]

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>