llvm dev - Aug 2008 - [LLVMdev] Dependence Analysis [was: Flow-Sensitive AA]

On Monday 18 August 2008 17:48, David Greene wrote:
> > Normally, the conversion to SSA form is sufficient.  Can you talk
> > about cases where this matters to you?
>
> Mostly it involves tying into our memory dependence analysis which
> annotates things on program points.  I need a way to translate back
> to our optimizer data structures.
>
> So it's not "flow-sensitive AA" in the strictest sense but it
does require
> program point information.
Ok, so this is not the ideal way to do things.  AliasAnalysis was just a 
convenient way to hook into something.  But as I've gone through this
I've realized it's just not going to work very well.

What I really need is a dependence analysis interface.  I need to know
about loop-carried dependencies and that sort of things, whether two memory 
operations reference the same data, distance information, etc..  As far as I 
can tell, there's no infrastructure for this in LLVM.

I don't actually need the analysis because we have it in our optimizer. 
What
I need is some kind of interface akin to AliasAnalysis that can chain 
analyses, etc.

I'm sure there are others working on this.  I believe Vikram mentioned his 
group is working on a parallelizing compiler based on LLVM.

I would think it would be straightforward to taken the AliasAnalysis interface
and essentially duplicate it and call it DependenceAnalysis or some such 
thing.  But if someone's already done this I'd rather not duplicate the 
effort.

                                               -Dave

Wojtek Matyjewicz has written a simple DependenceAnalysis interface  
and sent email about it to llvmdev in June -- the message is  
attached.  He said he wrote several tests behind that interface --  
ZIV, strong SIV, Banerjee, and some form of the Delta test -- and two  
students in my Spring class added the Omega test.  I have not reviewed  
his interface yet because I've been traveling almost nonstop since then.

At Illinois, we are working on a parallelizing compiler but we're at  
an extremely early stage.  We too will need a dependence analysis  
interface that can support fairly aggressive analysis, including  
strong tests, direction vectors, perhaps distance vectors, and  
dependence breaking conditions.  We were going to start with Wojtek's  
interface as a strawman.  Collaborations on extending the interface or  
implementation would be very welcome.  I'm copying Matthieu Delahaye  
who is our lead programmer on this effort (he's also on llvmdev).

--Vikram
Associate Professor, Computer Science
University of Illinois at Urbana-Champaign
http://llvm.org/~vadve




On Aug 20, 2008, at 11:27 AM, Chris Lattner wrote:
> On Aug 20, 2008, at 8:56 AM, David Greene wrote:
>> What I really need is a dependence analysis interface.  I need to  
>> know
>> about loop-carried dependencies and that sort of things, whether two
>> memory
>> operations reference the same data, distance information, etc..  As
>> far as I
>> can tell, there's no infrastructure for this in LLVM.
>
> Right, this is something we've wanted for a long time, but noone has
> stepped up to add.
>
>> I don't actually need the analysis because we have it in our
>> optimizer.  What
>> I need is some kind of interface akin to AliasAnalysis that can chain
>> analyses, etc.
>
> Ok.
>
>> I'm sure there are others working on this.  I believe Vikram
>> mentioned his
>> group is working on a parallelizing compiler based on LLVM.
>
> That project is just barely starting to get off the ground and will
> take awhile before it starts doing much, as far as I know.
>
>> I would think it would be straightforward to taken the AliasAnalysis
>> interface
>> and essentially duplicate it and call it DependenceAnalysis or some
>> such
>> thing.  But if someone's already done this I'd rather not
duplicate
>> the
>> effort.
>
> In theory, it should be pretty easy to create a new DependenceAnalysis
> analysis class and start piping it around.  It would be nice if there
> was a trivial implementation so that we can write regtests.
>
> -Chris
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
-------------- next part --------------
An embedded message was scrubbed...
From: Wojciech Matyjewicz <wmatyjewicz at fastmail.fm>
Subject: [LLVMdev] Data dependence analysis
Date: Fri, 6 Jun 2008 10:43:32 -0500
Size: 5700
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20080820/7253d985/attachment.eml>