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

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

> 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.
Sure. For now, I am posting it as an attachment, because it does not
build against the current SVN version. It is really basic (for example,
it cannot produce distance vectors, breaking conditions and it does not
handle affine loop bounds), but hope you find some pieces of it useful.

The attached version does not reflect the recent changes in the LLVM IR
(larger set of first-class types) yet, so it should be built against one
of the previous revisions (it works with r50174 for sure). It have to be
configured with --with-llvmsrc and --with-llvmobj switches. Build
process will produce libmemdep.so shared library that can be load into
opt. In the archive, there is also 'test' directory with simple programs
to test the pass. I suggest using such a toolchain:

$ llvm-gcc -c -emit-llvm -O3 <program.c> -o - | opt -load=loopmemdep.so
-loopsimplify -anders-aa -loop-memdep -debug-only=loop-memdep

(Debug output is quite verbose.)

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.

Wojtek
-------------- next part --------------
A non-text attachment was scrubbed...
Name: loopmemdep.tar.bz2
Type: application/octet-stream
Size: 36506 bytes
Desc: not available
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20080821/ec3e1241/attachment.obj>

Great, thanks!  How much work do you think it will take to bring it up  
to date with the LLVM IR, except *ignoring* first-class structs and  
arrays for now?  I believe llvm-gcc does not generate those in most  
cases and we can do a lot without supporting those.  What else is  
missing relative to the current LLVM IR?

Thanks,

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




On Aug 21, 2008, at 3:37 AM, Wojciech Matyjewicz wrote:
>> 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.
>
> Sure. For now, I am posting it as an attachment, because it does not
> build against the current SVN version. It is really basic (for  
> example,
> it cannot produce distance vectors, breaking conditions and it does  
> not
> handle affine loop bounds), but hope you find some pieces of it  
> useful.
>
> The attached version does not reflect the recent changes in the LLVM  
> IR
> (larger set of first-class types) yet, so it should be built against  
> one
> of the previous revisions (it works with r50174 for sure). It have  
> to be
> configured with --with-llvmsrc and --with-llvmobj switches. Build
> process will produce libmemdep.so shared library that can be load into
> opt. In the archive, there is also 'test' directory with simple  
> programs
> to test the pass. I suggest using such a toolchain:
>
> $ llvm-gcc -c -emit-llvm -O3 <program.c> -o - | opt - 
> load=loopmemdep.so
> -loopsimplify -anders-aa -loop-memdep -debug-only=loop-memdep
>
> (Debug output is quite verbose.)
>
> 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.
>
> Wojtek
> <loopmemdep.tar.bz2>

Hi Wojtek,

This is a great start. I'll focus and try to understand your interface  
design and choices. Here are my initial thoughts based on a quick read.

The only interface provided by LoopMemDepAnalysis is "bool  
carriesDependence()" which may not be sufficient. But we can extend  
this.

The ArrayDepTest provides testDependenc() as well as testPositions().  
I'm not very clear about the testPositions(). Would it be possible for  
you to explain this ?

One nit-pick, I see that some of the interfaces use tons of parameter,  
which is something I'd like reduce for ease of use.

Thanks for posting your work.
-
Devang
On Aug 21, 2008, at 1:37 AM, Wojciech Matyjewicz wrote:
>> 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.
>
> Sure. For now, I am posting it as an attachment, because it does not
> build against the current SVN version. It is really basic (for  
> example,
> it cannot produce distance vectors, breaking conditions and it does  
> not
> handle affine loop bounds), but hope you find some pieces of it  
> useful.
>
> The attached version does not reflect the recent changes in the LLVM  
> IR
> (larger set of first-class types) yet, so it should be built against  
> one
> of the previous revisions (it works with r50174 for sure). It have  
> to be
> configured with --with-llvmsrc and --with-llvmobj switches. Build
> process will produce libmemdep.so shared library that can be load into
> opt. In the archive, there is also 'test' directory with simple  
> programs
> to test the pass. I suggest using such a toolchain:
>
> $ llvm-gcc -c -emit-llvm -O3 <program.c> -o - | opt - 
> load=loopmemdep.so
> -loopsimplify -anders-aa -loop-memdep -debug-only=loop-memdep
>
> (Debug output is quite verbose.)
>
> 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.
>
> Wojtek
> <loopmemdep.tar.bz2>_______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

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