thr3ads.net - llvm dev - [llvm-dev] valid BasicAA behavior? [Mar 2020]

If this information is useful, please help other people find it:
Share via:

Kruse, Michael via llvm-dev

2020-Mar-17 21:20 UTC

[llvm-dev] valid BasicAA behavior?

AliasAnalysis and dependence analysis answer different problems. AA check
whether two memory ranges accessed at the same time (i.e. in the same iteration)
do not overlap. DI checks when two accesses, not necessarily executed in the
same iteration, do overlap.

DI makes use of AA in verifying that the base pointer (with unknown size), at
the beginning of the loop, themselves do not overlap. If they are allowed to,
reasoning over which iterations do access the same memory becomes ... difficult.
Note that it is possible to check at runtime whether to base pointer overlaps if
the accessed range is known. LoopAccessAnalysis (for vectorization) does this.

For the original example, if the loop outer loops is unrolled by an even factor,
the non-overlapping becomes more obvious in SSA.

Michael


________________________________
From: Chawla, Pankaj <pankaj.chawla at intel.com>
Sent: Tuesday, March 17, 2020 16:03
To: Finkel, Hal J. <hfinkel at anl.gov>; Hiroshi Yamauchi <yamauchi at
google.com>
Cc: llvm-dev at lists.llvm.org <llvm-dev at lists.llvm.org>; Kruse,
Michael <michael.kruse at anl.gov>
Subject: RE: [llvm-dev] valid BasicAA behavior?


Isn’t DependenceAnalysis dependent on conservative behavior of alias analysis?



It invokes AliasAnalysis with unknown size.



I tried it on this case and it returns this-



$ opt -analyze -basicaa -da test.ll

Src:  %0 = load double, double* %arrayidx, align 8, !tbaa !2 --> Dst:  store
double %add, double* %arrayidx6, align 8, !tbaa !2

  da analyze - none!





From: Finkel, Hal J. <hfinkel at anl.gov>
Sent: Tuesday, March 17, 2020 1:07 PM
To: Chawla, Pankaj <pankaj.chawla at intel.com>; Hiroshi Yamauchi
<yamauchi at google.com>
Cc: llvm-dev at lists.llvm.org; Kruse, Michael <michael.kruse at anl.gov>
Subject: Re: [llvm-dev] valid BasicAA behavior?



Hi, Pankaj,



You want a dependence analysis, there is a DependenceAnalysis (and also a new
DDG).



 -Hal



Hal Finkel
Lead, Compiler Technology and Programming Languages
Leadership Computing Facility
Argonne National Laboratory



________________________________

From: Chawla, Pankaj <pankaj.chawla at intel.com<mailto:pankaj.chawla at
intel.com>>
Sent: Tuesday, March 17, 2020 2:35 PM
To: Finkel, Hal J. <hfinkel at anl.gov<mailto:hfinkel at anl.gov>>;
Hiroshi Yamauchi <yamauchi at google.com<mailto:yamauchi at
google.com>>
Cc: llvm-dev at lists.llvm.org<mailto:llvm-dev at lists.llvm.org>
<llvm-dev at lists.llvm.org<mailto:llvm-dev at lists.llvm.org>>
Subject: RE: [llvm-dev] valid BasicAA behavior?



Hi Hal,



In that case what is the best way to query whether there is a loop carried
dependence between B[j] and A[j] at i-loop level?

We were operating under the assumption of ‘conservatively correct’ behavior of
alias analysis in the function scope?



Thanks,

Pankaj



From: Finkel, Hal J. <hfinkel at anl.gov<mailto:hfinkel at anl.gov>>
Sent: Tuesday, March 17, 2020 11:50 AM
To: Hiroshi Yamauchi <yamauchi at google.com<mailto:yamauchi at
google.com>>; Chawla, Pankaj <pankaj.chawla at
intel.com<mailto:pankaj.chawla at intel.com>>
Cc: llvm-dev at lists.llvm.org<mailto:llvm-dev at lists.llvm.org>
Subject: Re: [llvm-dev] valid BasicAA behavior?



BasicAA should return a result that is valid for the particular SSA values it is
provided, valid at points in the control flow where it would be valid to use
both SSA values simultaneously. In this example, the SSA values representing A
and B always point to different memory, so NoAlias seems correct.



 -Hal



Hal Finkel
Lead, Compiler Technology and Programming Languages
Leadership Computing Facility
Argonne National Laboratory



________________________________

From: llvm-dev <llvm-dev-bounces at lists.llvm.org<mailto:llvm-dev-bounces
at lists.llvm.org>> on behalf of Chawla, Pankaj via llvm-dev <llvm-dev
at lists.llvm.org<mailto:llvm-dev at lists.llvm.org>>
Sent: Tuesday, March 17, 2020 1:34 PM
To: Hiroshi Yamauchi <yamauchi at google.com<mailto:yamauchi at
google.com>>
Cc: llvm-dev at lists.llvm.org<mailto:llvm-dev at lists.llvm.org>
<llvm-dev at lists.llvm.org<mailto:llvm-dev at lists.llvm.org>>
Subject: Re: [llvm-dev] valid BasicAA behavior?



My understanding is that alias analysis returns results in the function scope,
not in loop scope.

Since both the phis access both global arrays, that should results in BasicAA
conservatively returning MayAlias.



I debugged this a little bit and narrowed it down to the section of the code in
BasicAAResult::aliasPHI() which has this comment-

      // Analyse the PHIs' inputs under the assumption that the PHIs are

      // NoAlias.

      // If the PHIs are May/MustAlias there must be (recursively) an input

      // operand from outside the PHIs' cycle that is MayAlias/MustAlias or

      // there must be an operation on the PHIs within the PHIs' value cycle

      // that causes a MayAlias.

      // Pretend the phis do not alias.



It seems to be analyzing corresponding phi operands assuming the PHIs to be
‘Noalias’ to begin with.

IMHO, this setup does not work correctly for loop header phis.





From: Hiroshi Yamauchi <yamauchi at google.com<mailto:yamauchi at
google.com>>
Sent: Tuesday, March 17, 2020 8:38 AM
To: Chawla, Pankaj <pankaj.chawla at intel.com<mailto:pankaj.chawla at
intel.com>>
Cc: llvm-dev at lists.llvm.org<mailto:llvm-dev at lists.llvm.org>
Subject: Re: [llvm-dev] valid BasicAA behavior?



Perhaps BasicAA is telling that A and B don't alias during one particular
iteration of the loop even though they are swapped?



1:                                                ; preds = %0, %35
  %2 = phi double* [ getelementptr inbounds ([1000 x double], [1000 x double]*
@Ag, i64 0, i64 0), %0 ], [ %4, %35 ]
  %3 = phi i32 [ 0, %0 ], [ %36, %35 ]
  %4 = phi double* [ getelementptr inbounds ([1000 x double], [1000 x double]*
@Bg, i64 0, i64 0), %0 ], [ %2, %35 ]
  br label %5



https://godbolt.org/z/vHJmL5



On Mon, Mar 16, 2020 at 10:28 PM Chawla, Pankaj via llvm-dev <llvm-dev at
lists.llvm.org<mailto:llvm-dev at lists.llvm.org>> wrote:

Hi all,



I have this test case-



#define N 1000

extern double Ag[N];

extern double Bg[N];



void consume(double *A, double *B);



void swap_deps() {

  double *A = Ag;

  double *B = Bg;



  for (int i = 0; i < 97; ++i) {

    for (int j = 0; j < N; ++j) {

      B[j] = A[j] + 1;

    }



    double *tmp = A;

    A = B;

    B = tmp;

  }



  consume(A, B);

}



BasicAA is returning ‘NoAlias’ when queried for phis created in the i-loop for A
and B.

I was expecting it to return MayAlias since A and B are being swapped in the
outer loop and so they access same locations in alternate iterations of the
i-loop.



Is BasicAA returning the correct result in this case?



Thanks,

Pankaj

_______________________________________________
LLVM Developers mailing list
llvm-dev at lists.llvm.org<mailto:llvm-dev at lists.llvm.org>
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20200317/d57e1547/attachment.html>

Michael Kruse via llvm-dev

2020-Mar-18 16:12 UTC

head link

[llvm-dev] valid BasicAA behavior?

Am Di., 17. März 2020 um 16:56 Uhr schrieb Chawla, Pankaj via llvm-dev
<llvm-dev at lists.llvm.org>:> All I am expecting from DA is a direction vector containing (*).
There seems to be a bug in DI, see Felipe's answer.

> I think the main problem is that currently there is no exact way DA can
query AliasAnalysis in a ‘conservatively correct’ manner.
>
> Using UnknownSize seems to be an approximate solution (workaround).
Passing an unknown size is conservatively correct. That is, it must be
correct for any possible size.

Yes, we could be better if we know all the array elements that are
accessed. Unfortunately it is also difficult, e.g. because the access
range depends on `n`, ie is non-constant. The AA interface doesn't
even allow querying for non-constant sizes.

> How do you guys feel about setting the initial cached result as MayAlias
instead of NoAlias if the query is performed for UnknownSize?
>
> If during alias query recursion we hit the same phi query again, we will
return a conservative ‘MayAlias’ knowing that we have hit a cycle (loop).
Since aliasPHI looks for any incoming value contradicting the NoAlias
assumption, it would be equivalant to always return MayAlias.


Michael

Seemingly Similar Threads

Search for more possibly parallel threads

llvm dev - Mar 2020 - valid BasicAA behavior?

[llvm-dev] valid BasicAA behavior?

[llvm-dev] valid BasicAA behavior?

Seemingly Similar Threads