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

[Preston Briggs]

Hi Sanjoy,

Reading through LoopDependenceAnalysis::analyseStrongSIV(), I noticed one
problem and one confusion.

My confusion related to your naming of the two instructions as A and B.
It's consistent all through LoopDependenceAnalysis. I'd prefer something
like source and destination, so I can keep track of which is which. It
didn't matter so much when you were simply proving or disproving
dependence, but when you compute direction, it's suddenly crucial.

The problem is the computation of direction from distance. The code says:

if (distance->isZero())
  S->Direction = Subscript::EQ;
else if (isGT)
  S->Direction = Subscript::GT;
else
  S->Direction = Subscript::LT;


While it looks sensible, it's incorrect. Correct is


if (distance->isZero())
  S->Direction = Subscript::EQ;
else if (isGT)
  S->Direction = Subscript::LT; // !!
else
  S->Direction = Subscript::GT; // !!


The Delta test paper (Section 1.3) and the 1st printing of Allen & Kennedy
(Definition 2.10) are similarly incorrect.
See http://www.elsevierdirect.com/companion.jsp?ISBN=9781558602861
particularly the replacement for page 46.

I'm also confused about the math, but I'll keep working on it.

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/20120405/2d6e8e30/attachment.html>