<html><head><style type="text/css"><!-- DIV {margin:0px;} --></style></head><body><div style="font-family:arial,helvetica,sans-serif;font-size:10pt"><div>Hi Tobi,<br><br>Thank you for your reply :). <br><br>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.<br><br>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). <br><br>Something along the lines of:<br><br><br>struct linked{<br> int val;<br> struct linked* next;<br>};<br><br>typedef struct linked item;<br>item *curr, *head;<br><br>...<br><br>while(curr) {<br>
do_something();<br> curr = curr->next ;<br> }<br><br><br>This becomes in LLVM IR:<br><br>%curr = alloca %struct.linked*, align 8<br><br>while..<br><br>%tmp15 = load %struct.linked** %curr, align 8<br></div><div style="font-family:arial, helvetica, sans-serif;font-size:10pt">%tmp16 = getelementptr inbounds %struct.linked* %tmp15, i32 0, i32 1 ( curr = curr->next ;)<br><br><br><br>And I want to transform this into a SCoP like this:<br><br>%curr_array = alloca [10 x %struct.linked], align 8<br><br>while..<br> %tmp16 = getelementptr inbounds [10 x %struct.linked]* %curr_array, i32 0, i32 1 <br><br>(replace all pointers similarly)<br><br>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.<br><br>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?<br><br><br>Thanks again and good luck with all your work on Polly!<br><br>Alexandra<br><div style="font-family:arial, helvetica, sans-serif;font-size:10pt"><font size="2" face="Tahoma"><hr size="1"><b><span style="font-weight: bold;">From:</span></b> Tobias Grosser <tobias@grosser.es><br><b><span style="font-weight: bold;">To:</span></b> llvmdev@cs.uiuc.edu; Jimborean Alexandra <xinfinity_a@yahoo.com><br><b><span style="font-weight: bold;">Sent:</span></b> Tue, July 19, 2011 10:19:54 AM<br><b><span style="font-weight: bold;">Subject:</span></b> Re: [LLVMdev] speculative parallelization in LLVM<br></font><br>
On 07/18/2011 07:03 PM, Jimborean Alexandra wrote:<br>> Hi,<br>> <br>> I plan to do some speculative parallelization in LLVM using Polly and I<br>> target loops that contain pointers and indirect references. As far as I<br>> know, Polly generates optimized code starting from the SCoPs, therefore<br>> I plan to replace all pointer accesses with array accesses, such that<br>> Polly will accept the code. Each array access should use a liner<br>> function of the enclosing loops indices.<br>> <br>> This is how I plan to implement it:<br>> <br>> 1) parse the alloca instructions and find declarations of pointers<br>> 2) for each pointer<br>> 3) delete the alloca instruction<br>> 4) create a new alloca instruction for the new array<br>> 5) replace all uses of the pointer with the new array<br>> <br>> <br>> Feed this code into Polly, get an optimized version and replace back the<br>> array accesses with
the original corresponding pointers.<br>> <br>> Please advise me whether this is a good strategy to replace the pointer<br>> accesses.<br><br><br>Hi Alexandra,<br><br>good to read you and even better that you plan to look into Polly. ;-)<br><br>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)<br><br>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.<br><br>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.<br><br>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.<br><br>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.<br><br>All the best to Strasbourg<br>Tobi<br><br></div></div>
</div></body></html>