[LLVMdev] speculative parallelization in LLVM
tobias at grosser.es
Tue Jul 19 01:19:54 PDT 2011
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 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
More information about the llvm-dev