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

On Aug 21, 2008, at 1:37 AM, Wojciech Matyjewicz wrote:
> I am investigating what changes are necessary to add support for
> first-class structs and arrays and will prepare a version to check  
> in as
> a LLVM project if there still is interest.
We want to model this as an analysis and make following changes.

- Rename LoopMemDepAnalysis as  DataDependenceAnalysis. Various  
transformation passes will use this interface to access data  
dependence info. This is an external interface. Put this in include/ 
llvm/Analysis.
- Make DirectionVector (and later on DistanceVector) independent  
interface and put them in ADT.
- Put various tests, DeltaTest, in lib/Analysis folder. The  
transformation pass does not need to see these details.
- DataDependenceAnalysis will select various dependence tests based on  
user selection.  We want a interface similar to AnalysisGroup used by  
Alias Analysis, but we also want to allow the possibility of running  
multiple tests at the same time.
- Make ArrayDepTester a private implementation detail of  
DataDependenceAnalysis.

What do you think ?
-
Devang

Hi,

On Fri, 2008-08-29 at 09:24 -0700, Devang Patel wrote:
[...]
> - Put various tests, DeltaTest, in lib/Analysis folder. The  
> transformation pass does not need to see these details.

I believe some low-level tests should actually not be implemented as a
separate Analysis but placed into Support. For instance, DeltaTest would
use GCD or other tests on a different set of indexes once constraints
are propagated. This means these tests are called on expressions that
are not necessarily present in the code itself.

> - DataDependenceAnalysis will select various dependence tests based
> on  
> user selection.  We want a interface similar to AnalysisGroup used
> by  
> Alias Analysis, but we also want to allow the possibility of running  
> multiple tests at the same time.
That will probably be the most difficult part. But with all the people
that shows interest on using or adding new analysis here, I am hopeful
we will obtain an acceptable stable API.

Regards,
Matthieu Delahaye

On Aug 29, 2008, at 10:15 AM, Matthieu Delahaye wrote:
> Hi,
>
> On Fri, 2008-08-29 at 09:24 -0700, Devang Patel wrote:
> [...]
>> - Put various tests, DeltaTest, in lib/Analysis folder. The
>> transformation pass does not need to see these details.
>
>
> I believe some low-level tests should actually not be implemented as a
> separate Analysis but placed into Support. For instance, DeltaTest  
> would
> use GCD or other tests on a different set of indexes once constraints
> are propagated. This means these tests are called on expressions that
> are not necessarily present in the code itself.
This requires the GCD Analysis test to provide interface to evaluate  
expression on demand. SCEV also does the same thing.
-
Devang
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20080829/296fd718/attachment.html>

> We want to model this as an analysis and make following changes.
> 
> - Rename LoopMemDepAnalysis as  DataDependenceAnalysis. Various  
> transformation passes will use this interface to access data  
> dependence info. This is an external interface. Put this in include/ 
> llvm/Analysis.
> - Make DirectionVector (and later on DistanceVector) independent  
> interface and put them in ADT.
> - Put various tests, DeltaTest, in lib/Analysis folder. The  
> transformation pass does not need to see these details.
> - DataDependenceAnalysis will select various dependence tests based on  
> user selection.  We want a interface similar to AnalysisGroup used by  
> Alias Analysis, but we also want to allow the possibility of running  
> multiple tests at the same time.
> - Make ArrayDepTester a private implementation detail of  
> DataDependenceAnalysis.
> 
> What do you think ?
It makes sense to me. However, I don't have idea how to organize
dependence analysis internally to allow for flexibility and precision at
the same time.

The second hard part is, I guess, designing good analysis interface. For
instance: how should distance vectors be represented? as separate
objects or annotations to distance vectors? The number of distance
(direction) vectors grows quadratically with the size of the loop
(roughly) what may constitute a problem for really large loops.

Unfortunately, I won't have time to help you with the implementation
now. But feel free to use any pieces of the code I have posted.

Wojtek

On Sep 2, 2008, at 5:24 PM, Wojciech Matyjewicz wrote:
> Unfortunately, I won't have time to help you with the implementation
> now. But feel free to use any pieces of the code I have posted.

I believe that Matthieu Delahaye is planning to work on this project  
so that should not be a problem.  Your code will be helpful to him as  
a starting point so thanks for that!  If you ever want to get back  
into this, please let us know.

--Vikram
http://www.cs.uiuc.edu/~vadve
http://llvm.org/



-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20080902/2f4aae42/attachment.html>

On Friday 29 August 2008 12:15, Matthieu Delahaye wrote:
> > - DataDependenceAnalysis will select various dependence tests based
> > on
> > user selection.  We want a interface similar to AnalysisGroup used
> > by
> > Alias Analysis, but we also want to allow the possibility of running
> > multiple tests at the same time.
>
> That will probably be the most difficult part. But with all the people
> that shows interest on using or adding new analysis here, I am hopeful
> we will obtain an acceptable stable API.
Can you elaborate on the complexity here?  Why is this any different from
the way AliasAnalysis works?  Yes, there will be a different API but the
concept is the same -- if I can't make a solid decision, hand it off to the
next analysis in the chain.

                                                  -Dave