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

On Wed, 18 Apr 2012 18:16:47 -0700
Preston Briggs <preston.briggs at gmail.com> wrote:
> Hi Sanjoy,
> 
> Here's a version of Banerjee and Wolfe's Exact SIV test:
> https://sites.google.com/site/parallelizationforllvm/weak-siv-test
> It assumes you've already filtered out the easy cases handled by ZIV,
> strong SIV, etc.
> 
> I'm not confident about my uses of APInt. If you have any comments,
> I'd love to hear them.
Are you worried about properly setting the bit lengths, or about loss
of generality by restricting to constants? I've not thought about this
too deeply, but are there cases where some or all of the relevant
inputs are not constants, but yet we can still determine whether the
expressions involving them satisfy the required inequalities? One of
the nice things about SCEV is its ability, to some extent, to handle
and simplify "algebraic" expressions, and if appropriate, I think we
should use that ability.

Thanks again,
Hal
> 
> Thanks,
> Preston
> 
> 
> On Thu, Apr 12, 2012 at 5:14 AM, Sanjoy Das
> <sanjoy at playingwithpointers.com>wrote:
> 
> > 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
> >


-- 
Hal Finkel
Postdoctoral Appointee
Leadership Computing Facility
Argonne National Laboratory

> > Here's a version of Banerjee and Wolfe's Exact SIV test:
> > https://sites.google.com/site/parallelizationforllvm/weak-siv-test
> > It assumes you've already filtered out the easy cases handled by
ZIV,
> > strong SIV, etc.
> >
> > I'm not confident about my uses of APInt. If you have any
comments,
> > I'd love to hear them.
>
> Are you worried about properly setting the bit lengths,
Yes, among other things. There are several inputs. Do I need to make
efforts to ensure they're all the same bit length? Is it appropriate
to do so much computation with APInts, or should I be working with
64-bit integers?
> or about loss of generality by restricting to constants? I've not
thought about this
> too deeply, but are there cases where some or all of the relevant
> inputs are not constants, but yet we can still determine whether the
> expressions involving them satisfy the required inequalities? One of
> the nice things about SCEV is its ability, to some extent, to handle
> and simplify "algebraic" expressions, and if appropriate, I think
we
> should use that ability.
Yes, I agree. This particular test is not very flexible about symbolic
computation (computing the GCD of non-constant inputs seems tough);
one of the advantages of the more specialized tests (Strong SIV, et
al.) is that they let us get a bit further with symbolic inputs.

I've been studying the SCEV code and have ideas about how to rework
some of the SIV tests to be a bit more flexible in this respect. I
think they'll turn out well; the SCEV package is really quite
wonderful.

Preston

Hi all,

Sorry for having been quiet for so long, I have my university exams
going on, and will be able to contribute only after the coming Friday.

Thanks!
-- 
Sanjoy Das
http://playingwithpointers.com