[LLVMdev] speculative parallelization in LLVM

[Tobias Grosser]

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