[LLVMdev] speculative parallelization in LLVM

[Tobias Grosser]

On 07/18/2011 07:03 PM, Jimborean Alexandra wrote:
> Hi,
>
> I plan to do some speculative parallelization in LLVM using Polly and I
> target loops that contain pointers and indirect references. As far as I
> know, Polly generates optimized code starting from the SCoPs, therefore
> I plan to replace all pointer accesses with array accesses, such that
> Polly will accept the code. Each array access should use a liner
> function of the enclosing loops indices.
>
> This is how I plan to implement it:
>
> 1) parse the alloca instructions and find declarations of pointers
> 2) for each pointer
> 3) delete the alloca instruction
> 4) create a new alloca instruction for the new array
> 5) replace all uses of the pointer with the new array
>
>
> Feed this code into Polly, get an optimized version and replace back the
> array accesses with the original corresponding pointers.
>
> Please advise me whether this is a good strategy to replace the pointer
> accesses.


Hi Alexandra,

good to read you and even better that you plan to look into Polly. ;-)

In respect of your plan I still do not exactly get what you want to do. 
(I still feel pretty new to all this stuff, so just let me know if 
something I say sounds wrong)

In LLVM load and store instructions always load and store from a pointer 
and there is no way to express an array access inside LLVM-IR. What 
comes closes to an array access is the combination of a getElementPtr 
instruction that calculates a pointer into an array plus a load/store 
instruction. However, this is actually not very different from directly 
calculating the pointer into the array based on normal pointer arithmetic.

As a result, in Polly we always analyze the pointer arithmetic (or the 
effects of it) and try to prove that it is conceptually equivalent to an 
access to a normal array. To prove this we use the normal LLVM provided 
alias analysis. Here we can also derive that the virtual arrays do not 
overlap (as mentioned by Renato). However, we never transform any 
pointers into arrays. We just treat them conceptually as virtual arrays.

Maybe an example would help me to understand what you plan to do. Can 
you give a very simple example (at best in both C and LLVM-IR) that 
shows what transformation you plan to perform and what kind of code you 
would be able to optimize.

There are currently quite some parts in and around Polly that need to be 
improved. Preparing code for Polly such that it fits the format we 
expect is definitely one of this. Indirect references is something, I 
did not even start to think about. Hence, ideas in this direction are 
more then welcome.

All the best to Strasbourg
Tobi