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

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>

On Wednesday 20 August 2008 14:07, Vikram S. Adve wrote:
> 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).
Is there some code of the interface we can discuss?  I'm more than happy to
provide input, requirements, etc.  I'll contribute code where I can 
(management decision there, but I'm pretty sure I can sell it).

If there's something that's been used for simple things now, let's
get it
checked in and start refining it.

                                                     -Dave

Wojtek,

Please see David's message below.  Have you or can you check in your  
code, perhaps as a project for now?  That will allow us to start  
looking at it and perhaps collaborating on it.

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




On Aug 20, 2008, at 3:05 PM, David Greene wrote:
> On Wednesday 20 August 2008 14:07, Vikram S. Adve wrote:
>
>> 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).
>
> Is there some code of the interface we can discuss?  I'm more than  
> happy to
> provide input, requirements, etc.  I'll contribute code where I can
> (management decision there, but I'm pretty sure I can sell it).
>
> If there's something that's been used for simple things now,
let's
> get it
> checked in and start refining it.
>
>                                                     -Dave