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

Vikram S. Adve vadve at cs.uiuc.edu
Wed Aug 20 12:07:49 PDT 2008

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).

Associate Professor, Computer Science
University of Illinois at Urbana-Champaign

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>

More information about the llvm-dev mailing list