llvm dev - Apr 2012 - [LLVMdev] SIV tests in LoopDependence Analysis, Sanjoy's patch

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>

Wait Are you really setting isGT to true if the distance is less than zero?
If so, I think your code is ok, but the naming could use a rework.

Preston

On Thu, Apr 5, 2012 at 4:09 PM, Preston Briggs <preston.briggs at
gmail.com>wrote:
> 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/0e75b69a/attachment.html>

Hi Sanjoy,

I reworked the code for analyzeStrongSIV to fix a couple of mistakes, plus
squeeze all the advantage possible from the symbolic manipulation provided
by the SCEVs. It's sketched out here:
https://sites.google.com/site/parallelizationforllvm/strong-siv-test

Does it makes sense to you?

Thanks,
Preston


On Thu, Apr 5, 2012 at 4:09 PM, Preston Briggs <preston.briggs at
gmail.com>wrote:
> 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/20120408/d401085c/attachment.html>

Hi,

Here is a preliminary (monolithic) version you can comment on.  This
is still buggy, however, and I'll be testing for and fixing bugs over
the next few days.  I've used your version of the strong siv test.

Thanks!
-- 
Sanjoy Das.
http://playingwithpointers.com
-------------- next part --------------
A non-text attachment was scrubbed...
Name: patch.diff
Type: application/octet-stream
Size: 40632 bytes
Desc: not available
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20120412/261b2eb9/attachment.obj>