[LLVMdev] SIV tests in LoopDependence Analysis, Sanjoy's patch

[Preston Briggs]

Hi Sanjoy,

Thanks for the update.

Reading through LoopDependenceAnalysis.h

   - 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
   - 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).

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
here<https://sites.google.com/site/parallelizationforllvm/representing-dependences>).
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.

The definition for Dependence should probably be a class with a number of
methods.
You currently have a field for Result.  Don't think it's useful.
On the other hand, I'd include Kind, one of Flow, Antri, Output, and Input.
You absolutely need a flag indicating the possibility of a loop-independent
dependence.
You need your vector of levels.
I think I'd include pointers to the source and destination here.
I'd have methods for things like:

   - bool confused(), returns true if all levels are <=>
   - bool consistent(), returns true is all levels are Scalar or have a
   distance
   - unsigned loopCarried(), return the level of the left-most non-equal
   direction

The methods could be implemented by a computation or by looking at a flag
that's computed once.

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.

I'd encourage more discussion (indeed, any discussion) of all this before
hacking up more code. Read the stuff I've written
here<https://sites.google.com/site/parallelizationforllvm/>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.

I'll review the actual implementation in LoopDependenceAnalysis.cpp in
another note.

Thanks,
Preston



On Sun, Mar 25, 2012 at 9:49 PM, Sanjoy Das
<sanjoy at playingwithpointers.com>wrote:

> Hi Hal, Preston!
>
> Sorry for the delay!  Got busy with some offline work.
>
> I've worked on my previous code to calculate direction and distance
> vectors whenever possible (strong SIV, basically).  I think the
> current code is much clearer and would like your opinions on it.
>
> I have attached the patch and also pushed to the github repo I
> mentioned [1].
>
> Thanks!
>
> [1] https://github.com/sanjoy/llvm/tree/lda
> --
> Sanjoy Das.
> http://playingwithpointers.com
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20120327/3aef292e/attachment.html>