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

[Wojciech Matyjewicz]

> 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