llvm dev - Jun 2015 - [LLVMdev] Alias analysis across loop iterations (aka loop carried dependency analysis)

Hi all,

With alias analysis, it is possible to detect if an access in the loop body will
alias - or not.
With SCEV, you can find out how a variable evolves over different loop
iterations.

Is there a pass that combines these two and can tell me
- for which n an access A in iteration X will alias with an access B in
iteration X+n
and/or
- if an access A in iteration X will (not) alias with an access B in iteration
X+n
?

Inside the loop vectorizer, there is a helper class  (MemoryDepChecker) that
seems
to do some analysis that comes close. Is that all we have or did I miss a pass ?

Thanks,

Jeroen Dobbelaere

Hi Jeroen,

I think you may want to have a look at the DependenceAnalysis pass.

Regards,
  Roel

On 04/06/15 10:52, Jeroen Dobbelaere wrote:
> Hi all,
>
> With alias analysis, it is possible to detect if an access in the loop body
will alias - or not.
> With SCEV, you can find out how a variable evolves over different loop
iterations.
>
> Is there a pass that combines these two and can tell me
> - for which n an access A in iteration X will alias with an access B in
iteration X+n
> and/or
> - if an access A in iteration X will (not) alias with an access B in
iteration X+n
> ?
>
> Inside the loop vectorizer, there is a helper class  (MemoryDepChecker)
that seems
> to do some analysis that comes close. Is that all we have or did I miss a
pass ?
>
> Thanks,
>
> Jeroen Dobbelaere
>
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>

On 06/04/2015 10:52 AM, Jeroen Dobbelaere wrote:
> Hi all,
>
> With alias analysis, it is possible to detect if an access in the loop body
will alias - or not.
> With SCEV, you can find out how a variable evolves over different loop
iterations.
>
> Is there a pass that combines these two and can tell me
> - for which n an access A in iteration X will alias with an access B in
iteration X+n
> and/or
> - if an access A in iteration X will (not) alias with an access B in
iteration X+n
> ?
>
> Inside the loop vectorizer, there is a helper class  (MemoryDepChecker)
that seems
> to do some analysis that comes close. Is that all we have or did I miss a
pass ?
Dear Jeroen,

in the context of Polly there is also a dependence analysis pass that 
provides you precise data dependences using for arbitrary piecewise 
affine accesses using the isl library to solve the necessary ILP 
problems. With our recent changes of Polly it should be reasonably 
simple to use this pass as a pure analysis pass.

Best,
Tobias