[LLVMdev] speculative parallelization in LLVM
xinfinity_a at yahoo.com
Tue Jul 19 02:12:53 PDT 2011
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* next;
typedef struct linked item;
item *curr, *head;
curr = curr->next ;
This becomes in LLVM IR:
%curr = alloca %struct.linked*, align 8
%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
%tmp16 = getelementptr inbounds [10 x %struct.linked]* %curr_array, i32 0, i32
(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
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!
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:
> 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
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
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
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
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the llvm-dev