Hi Sanjoy,<div><br></div><div>Thanks for the update.</div><div><br></div><div>Reading through LoopDependenceAnalysis.h</div><div><ul><li>I'd sure like to see some design documentation (this is true for most of the LLVM code I've seen). Tell us what the plan is, only then talk about the implementation</li>
<li>I hate the names Subscript and Subscripts. Implies each entry corresponds to a subscript, but that's not true. Each entry corresponds to a level in the loop nest. There may be several subscript pairs summarized in a single level entry. I'd suggest Level, or LoopLevel, or some such, more closely related to the literature. Indicating that entries are related to the loop nest, versus suggesting that they somehow correspond to subscripts (which are associated with memory references).</li>
</ul></div><div>Your definition for Subscript has a Kind that's either Independent, Dependent, or Unknown. This seems all wrong. If some level is independent, then no dependence exists at all (not just at this level). Otherwise, there will absolutely be a direction (3 bits) and perhaps a distance. I'd also like to see a bit for Scalar, and perhaps a few more (see <a href="https://sites.google.com/site/parallelizationforllvm/representing-dependences">here</a>). Unknown isn't special; it just mean there's a dependence and any direction is possible. We indicate Unknown by setting all 3 bits in the direction vector (same for Scalar). In this way, we can test for the validity of many xforms by simply examining the direction vectors; don't need to look at other flags.</div>
<div><br></div><div>The definition for Dependence should probably be a class with a number of methods.</div><div>You currently have a field for Result.  Don't think it's useful.</div><div>On the other hand, I'd include Kind, one of Flow, Antri, Output, and Input.</div>
<div>You absolutely need a flag indicating the possibility of a loop-independent dependence.</div><div>You need your vector of levels.</div><div>I think I'd include pointers to the source and destination here.</div><div>
I'd have methods for things like:</div><div><ul><li>bool confused(), returns true if all levels are <=></li><li>bool consistent(), returns true is all levels are Scalar or have a distance</li><li>unsigned loopCarried(), return the level of the left-most non-equal direction</li>
</ul></div><div>The methods could be implemented by a computation or by looking at a flag that's computed once.</div><div><br></div><div>I'd very much like to see the dependence representation and tests separated from the collection of dependences associated with a loop nest. People working on loop nests will need to be able to access the associated dependences in various ways (e.g., give me all the dependences carried by a certain level) that you can't yet predict. Make 'em define their own structures. You should focus on the tests.</div>
<div><br></div><div>I'd encourage more discussion (indeed, any discussion) of all this before hacking up more code. Read the stuff I've written <a href="https://sites.google.com/site/parallelizationforllvm/">here</a> and comment, or I'll get you access and you can write directly That's not to say what you've written is a waste; I think it's quite wonderful. You've implemented most of the tough parts and I'm confident it will all prove useful in the final solution.</div>
<div><br></div><div>I'll review the actual implementation in LoopDependenceAnalysis.cpp in another note.</div><div><br></div><div>Thanks,</div><div>Preston</div><div><br></div><div><br></div><div><br><div class="gmail_quote">
On Sun, Mar 25, 2012 at 9:49 PM, Sanjoy Das <span dir="ltr"><<a href="mailto:sanjoy@playingwithpointers.com">sanjoy@playingwithpointers.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
Hi Hal, Preston!<br>
<br>
Sorry for the delay!  Got busy with some offline work.<br>
<br>
I've worked on my previous code to calculate direction and distance<br>
vectors whenever possible (strong SIV, basically).  I think the<br>
current code is much clearer and would like your opinions on it.<br>
<br>
I have attached the patch and also pushed to the github repo I<br>
mentioned [1].<br>
<br>
Thanks!<br>
<br>
[1] <a href="https://github.com/sanjoy/llvm/tree/lda" target="_blank">https://github.com/sanjoy/llvm/tree/lda</a><br>
<div class="HOEnZb"><div class="h5">--<br>
Sanjoy Das.<br>
<a href="http://playingwithpointers.com" target="_blank">http://playingwithpointers.com</a><br>
</div></div></blockquote></div><br></div>