[LLVMdev] Array Dependence Analysis
sabre at nondot.org
Sun Mar 16 18:55:56 PDT 2008
>> As part of the advanced compilers course semester project (at
>> UIUC), we
>> are starting to implement array dependence analysis for LLVM.
Great! This is something we've needed for a long time.
> I'm currently working on a similar project and hoping to finish it in
> about two weeks.
Cool! I think the most critical part of this is to get a good
interface for dependence analysis. There are lots of interesting
implementations that have various time/space tradeoffs.
For example, it would be great if Omega was available as an option,
even if the compiler didn't use it by default. This argues for making
dependence analysis implementations pluggable like alias analyses.
> As for now, I'm focusing on the dependency analysis engine and publish
> only a simplistic interface (it only allows to check whether a loop
> carries a memory dependence). However, the engine is quite
> self-contained and should be easy to attach to a different interface.
> For instance, the engine will be able to find dependence direction
> vectors for an instruction pair.
Sounds good. If you have the interface nailed down, it would be good
to post what the query interface looks like. Vikram and others have a
lot of experience with dependence analysis and know what sorts of
queries various clients are interested in. They can help give
feedback on the direction you're pursuing independent of the
>> Any suggestion on features, tests and/or interface are welcome.
I'd suggest looking at:
Using the chains of recurrences algebra for data dependence testing
and induction variable substitution
MS Thesis, Johnie Birch
Array Data Dependence Testing with the Chains of Recurrences Algebra
An empirical evaluation of chains of recurrences for array dependence
>> From my experience I can say it's essential to use a precise alias
> analysis as the base for the array dependence analysis. Fortunately,
> using Data Structure or Andersen's AA for the whole program can
> really good results.
Yep, but any particular dep analysis implementation should just
require AliasAnalysis instead of a specific implementation. This lets
the client (e.g. llvm-gcc) decide what passes to plug together.
More information about the llvm-dev