[LLVMdev] speculative parallelization in LLVM

[Tobias Grosser]

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