[LLVMdev] Dependence Analysis [was: Flow-Sensitive AA]

[Vikram S. Adve]

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>