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

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

Chawla, Pankaj via llvm-dev

2020-Mar-17 19:35 UTC

[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>
Sent: Tuesday, March 17, 2020 11:50 AM
To: Hiroshi Yamauchi <yamauchi at google.com>; Chawla, Pankaj
<pankaj.chawla at intel.com>
Cc: 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/12e768fd/attachment.html>

Finkel, Hal J. via llvm-dev

2020-Mar-17 20:06 UTC

head link

[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>
Sent: Tuesday, March 17, 2020 2:35 PM
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>
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>
Sent: Tuesday, March 17, 2020 11:50 AM
To: Hiroshi Yamauchi <yamauchi at google.com>; Chawla, Pankaj
<pankaj.chawla at intel.com>
Cc: 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/d21f59a6/attachment.html>

Chawla, Pankaj via llvm-dev

2020-Mar-17 21:03 UTC

head link

[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/9ca56205/attachment.html>

De Azevedo Piovezan, Felipe via llvm-dev

2020-Mar-18 12:32 UTC

head link

[llvm-dev] valid BasicAA behavior?

Be careful with a known bug in DA + pointer swapping:

http://lists.llvm.org/pipermail/llvm-dev/2019-May/132725.html
https://bugs.llvm.org/show_bug.cgi?id=42143

________________________________
From: llvm-dev <llvm-dev-bounces at lists.llvm.org> on behalf of Finkel,
Hal J. via llvm-dev <llvm-dev at lists.llvm.org>
Sent: Tuesday, March 17, 2020 4:06 PM
To: Chawla, Pankaj <pankaj.chawla at intel.com>; 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?

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>
Sent: Tuesday, March 17, 2020 2:35 PM
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>
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>
Sent: Tuesday, March 17, 2020 11:50 AM
To: Hiroshi Yamauchi <yamauchi at google.com>; Chawla, Pankaj
<pankaj.chawla at intel.com>
Cc: 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/20200318/f142984a/attachment.html>

llvm dev - Mar 2020 - valid BasicAA behavior?

[llvm-dev] valid BasicAA behavior?

[llvm-dev] valid BasicAA behavior?

[llvm-dev] valid BasicAA behavior?

[llvm-dev] valid BasicAA behavior?