[llvm-dev] valid BasicAA behavior?

Tue Mar 17 14:20:53 PDT 2020

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>