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

matthieu at illinois.edu matthieu at illinois.edu
Mon Aug 25 11:54:00 PDT 2008

>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 


More information about the llvm-dev mailing list