[LLVMdev] speculative parallelization in LLVM

[Jimborean Alexandra]

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.

In the case of a linked list for example, parsed with a pointer p = p->next, I 
expect that Polly will not handle this code. So I intend to change this pointer 
into an array (I do not expect to get correct code, but a correct SCoP). 


Something along the lines of:


struct linked{
    int val;
    struct linked* next;
};

typedef struct linked item;
item *curr, *head;

...

while(curr) {
     do_something();
      curr = curr->next ;
 }


This becomes in LLVM IR:

%curr = alloca %struct.linked*, align 8

while..

%tmp15 = load %struct.linked** %curr, align 8

%tmp16 = getelementptr inbounds %struct.linked* %tmp15, i32 0, i32 1      ( curr 
= curr->next ;)



And I want to transform this into a SCoP like this:

%curr_array = alloca [10 x %struct.linked], align 8

while..
 %tmp16 = getelementptr inbounds [10 x %struct.linked]* %curr_array, i32 0, i32 
1 


(replace all pointers similarly)

I only want Polly to accept the code (although incorrect at this point) and to 
generate optimized code. Next I will replace back all the fake arrays that I 
introduced, with the original pointer accesses and correct the code. Finally, at 
runtime, I perform code instrumentation on the optimized code to check its 
correctness.

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?


Thanks again and good luck with all your work on Polly!

Alexandra


________________________________
From: Tobias Grosser <tobias at grosser.es>
To: llvmdev at cs.uiuc.edu; Jimborean Alexandra <xinfinity_a at yahoo.com>
Sent: Tue, July 19, 2011 10:19:54 AM
Subject: Re: [LLVMdev] speculative parallelization in LLVM

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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20110719/da11c46e/attachment.html>