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

[matthieu at illinois.edu]

>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