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.
Thank you,
Alexandra
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20110718/7b621bbb/attachment.html>
On 18 July 2011 18:03, Jimborean Alexandra <xinfinity_a at yahoo.com> wrote:> 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 arrayHi, I'm no expert in auto-vectorization, but I guess you'll be restricted to pointers that are guaranteed not to overlap, which depending on how you structure your code, are not many. You can't just transform *any* pointer access to array access by replacing them by allocas (that, afaik, cannot overlap). Also, the allocas inside functions with pointer arguments store a pointer to the original pointer, so you'd have to go back to the caller and change *that* alloca, only you can't do that because you're not sure the callee will always be called, unless you want to make a whole refactoring of all pointer allocas in all functions in all modules, and even so, you'll be restricted to the accesses that don't overlap. I could be talking non-sense (please let me know if I am), but I feel that if it were that simple, we'd see much more mainstream auto-vectorizing compilers... cheers, --renato
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
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>