<html><head><style type="text/css"><!-- DIV {margin:0px;} --></style></head><body><div style="font-family:arial,helvetica,sans-serif;font-size:10pt"><div><br></div><div style="font-family:arial, helvetica, sans-serif;font-size:10pt">This is exactly want I need to achieve with Polly actually. I think a good idea would be to define intrinsics / metadata, as you mentioned, to notify Polly that even though it cannot analyse these accesses, to ignore them and perform the code transformations. We can go even further and maybe describe these accesses with some parametric linear functions. <br><br>For instance:<br><br>while (cond1){<br> while(cond2){<br> p=p->next;<br> }<br>}<br><br><br>to introduce virtual iterators of the enclosing loops, i and j , and replace the accesses inside the loop with virtual accesses that have the form a*i + b*j + c<br><br>%1 =
polly.virtual_read() !polly !" {a1*i + b1*j + c1}"<br>polly.virtual_write(%ptr) !polly !" {a2*i + b2*j + c2}"<br><br>Next at runtime it will be easier to change the virtual accesses to the original pointers, and to compute the values to the coefficients a1, b1 ... to check if they follow the linearity. I perform dynamic instrumentation to compute the coefficients.<br><br>However, for applying the transformations, Polly should either totally ignore the virtual accesses, or assign some default values to the coefficients and take them into consideration. Our plan is to create several versions, some with different values, lets say a = 1, b= 1, c = 0, and one version where all the virtual accesses are ignored.<br><br>What is important is to be able to track the virtual accesses and to be able to replace them with the original ones.<br><br>Do you think this represents a lot of work in Polly? And do you plan to include this
kind of support to handle non-statically analysable code? In case this doesn't imply significant changes in Polly, I could start working on this. It might be a better approach than converting the code into a form accepted by Polly :)<br><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> Jimborean Alexandra <xinfinity_a@yahoo.com><br><b><span style="font-weight: bold;">Cc:</span></b> llvmdev@cs.uiuc.edu<br><b><span style="font-weight: bold;">Sent:</span></b> Tue, July 19, 2011 11:53:23 AM<br><b><span style="font-weight: bold;">Subject:</span></b> Re: [LLVMdev] speculative parallelization in LLVM<br></font><br>
On 07/19/2011 11:12 AM, Jimborean Alexandra wrote:<br>> 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<br>> understood Polly is focused on statically analysable code. As you<br>> mentioned: proving that pointer accesses actually represent virtual<br>> array accesses.<br>> <br>[...]<br>> <br>> Is this approach going to work with Polly? Or can I generate optimized<br>> code versions with Polly in a different manner when there are pointers<br>> and indirect references inside the code?<br><br>OK. Perfect. Here we are. Thanks for the nice explanation. Now I get what you plan to do and I am extremely interested in how you will solve this.<br><br>So yes, I assume the translation of your code into statically analyzable code should work. The only problem I see is that it may take some time to generate code that is really statically analyzable
and that at the same time can easily be converted back to the original code. Especially if afterwords the code is/was further optimized.<br>Furthermore, it you may trigger some cases that Polly cannot yet handle.<br><br>One thing I was reasoning about for a while, is if it is possible to<br>simplify the generation of code that Polly can recognize, such that frontends like clang, but also your tool can generate code that we can be sure Polly can handle. Here, I think it would be especially interesting to be able to make Polly also parse some kind of virtual accesses, were the details of the accesses are hidden and Polly only gets the information, that this access acts like an access to a virtual array.<br><br>Describing this virtual accesses by using some kind of intrinsics combined with meta data may be possible.<br><br>%1 = polly.virtual_read() !polly !"{A[i][2j][3k]}"<br>polly.virtual_write(%ptr) !polly !"{A[i][2j][3k]}"<br><br>Like this you can
simply transform your linked list into virtual accesses, and Polly generates the code that executes these accesses,<br>and at the end you replace them with the actual code.<br><br>(The definition of this is far from complete and the example above needs probably be changed to be actually usable. Still, I hope it gives the general idea.)<br><br>Let me know what you think and what you need exactly. Maybe we can work out together a good way to represent such virtual accesses.<br><br>Cheers<br>Tobi<br></div></div>
</div></body></html>