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

>Polyhedral representations are powerful but somewhat expensive to  
>construct and simple dependence tests don't construct them.  Forcing  
>all dependence test results to go through them would be overkill.
   
>Also, many loop transforms, e.g., loop interchange, don't need the  
>polyhedral info, just direction vectors.  You could instead provide  
>both direction vectors and polyhedral info  through the interface,  
>with some way to check if either is available.
So far I see 3 ways of expressing dependencies:
- Loop level
- Direction vector
- Polyhedral representation

Polyhedral representation subsume direction vector and direction vector subsume
loop level. We can as well:
- create a hierarchy of dependence type and implementing the logic for isa, cast
and dyn_cast.
- Provide some constructors to build a dependence type from a less precise one.
This does not scale well with the number of type to maintain. But as long as
there is few types (3 so far) this is maintainable.
>
>>
>> - Supporting delinearisation.
>
>
>I think this should be a separate pass.
I agree. It should be an analysis pass queried by the dependence analysis as a
fall back whenever all the dependence tests from the other indexes were
non-conclusive.

--Matthieu