thr3ads.net - llvm dev - [llvm-dev] AliasAnalysis: may-alias subcategory [Aug 2017]

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

Nema, Ashutosh via llvm-dev

2017-Aug-07 15:28 UTC

[llvm-dev] AliasAnalysis: may-alias subcategory

There are function which does have optimization opportunities but because of
may-alias memory dependencies sometimes optimization is not effective. May be
runtime checks kills the gains of optimization. For such cases aiming to do
interprocedural function specialization optimization where in the clone function
version no-alias assumption can be assumed and the original function version
will hold the default alias assumption.

i.e. 
void foo(int *A, int *B, int *C) {
  for (int i=0; i<N; i++)
       A[i] = B[i] + C[i];
}
void callFoo() {
   foo (A1, B1, C1); // A1 no-alias with B1 & C1
   foo (A2, B2, C2); // A2 no-alias with B1 & C1
   foo (A3, B3, C3); // A3 must-alias with B3/C3
}

Will be transformed to:
void foo(int *A, int *B, int *C) {
       // default loop version
}
void foo.clone(int * restrict A, int *B, int *C) {
       // Optimal loop version
}
void callFoo() {
   foo.clone(A1, B1, C1); // Call to optimal version
   foo.clone(A2, B2, C2); // Call to optimal version
   foo (A3, B3, C3); // Call to default version
}

For such cases I like to differentiate between “may-alias” and
“may-alias-because-it's-input”.

Regards,
Ashutosh

-----Original Message-----
From: Nuno Lopes [mailto:nunoplopes at sapo.pt] 
Sent: Monday, August 7, 2017 6:12 PM
To: Nema, Ashutosh <Ashutosh.Nema at amd.com>; llvm-dev <llvm-dev at
lists.llvm.org>
Subject: Re: [llvm-dev] AliasAnalysis: may-alias subcategory

You're right that stating may-alias(A, B) and may-alias(A, C) are the only
possible answers right now, since the compiler cannot possibly know if these
alias or not.
LLVM supports the noalias attribute for function parameters, which may be what
you're looking for?  http://llvm.org/docs/LangRef.html#noalias

If not, how differentiating between a may-alias and a
may-alias-because-it's-input would help?  Do you have a particular
optimization that would be enabled?

Nuno

-----Original Message-----
From: Nema, Ashutosh via llvm-dev
Sent: Monday, August 7, 2017 12:29 PM
Subject: [llvm-dev] AliasAnalysis: may-alias subcategory

Hi,

The current AliasAnalysis marks may-alias for cases when memory passed as
function argument.

i.e.
void foo(int *A, int *B, int *C) {
  for (int i=0; i<N; i++)
       A[i] = B[i] + C[i];
}

In the above example, it’s may-alias for memory ‘A’, because ’A’ is not known at
‘foo’ call sites.
Alias analysis is able to figure out memory ‘A’ is no-alias, if I modify the
above test by making ‘A’ as an stack variable.

I’m interested to find the cases where memory is always may-alias because of
input function parameter.
Probably a sub category(may-alias-because-of-function-parameter) of may-alias
may help.

Not sure llvm already has something to sub categorize may-alias cases.

Thanks,
Ashutosh

Hal Finkel via llvm-dev

2017-Aug-08 03:24 UTC

head link

[llvm-dev] AliasAnalysis: may-alias subcategory

On 08/07/2017 10:28 AM, Nema, Ashutosh via llvm-dev
wrote:> There are function which does have optimization opportunities but because
of may-alias memory dependencies sometimes optimization is not effective. May be
runtime checks kills the gains of optimization. For such cases aiming to do
interprocedural function specialization optimization where in the clone function
version no-alias assumption can be assumed and the original function version
will hold the default alias assumption.
>
> i.e.
> void foo(int *A, int *B, int *C) {
>    for (int i=0; i<N; i++)
>         A[i] = B[i] + C[i];
> }
> void callFoo() {
>     foo (A1, B1, C1); // A1 no-alias with B1 & C1
>     foo (A2, B2, C2); // A2 no-alias with B1 & C1
>     foo (A3, B3, C3); // A3 must-alias with B3/C3
> }
>
> Will be transformed to:
> void foo(int *A, int *B, int *C) {
>         // default loop version
> }
> void foo.clone(int * restrict A, int *B, int *C) {
>         // Optimal loop version
> }
> void callFoo() {
>     foo.clone(A1, B1, C1); // Call to optimal version
>     foo.clone(A2, B2, C2); // Call to optimal version
>     foo (A3, B3, C3); // Call to default version
> }
>
> For such cases I like to differentiate between “may-alias” and
“may-alias-because-it's-input”.
You can always call GetUnderlyingObjects on the relevant pointer values 
and check for those that are Arguments. Is your goal here to collect all 
of these may-alias results in some kind of cache while other 
optimizations run and then use that to specialize later?

  -Hal
>
> Regards,
> Ashutosh
>
> -----Original Message-----
> From: Nuno Lopes [mailto:nunoplopes at sapo.pt]
> Sent: Monday, August 7, 2017 6:12 PM
> To: Nema, Ashutosh <Ashutosh.Nema at amd.com>; llvm-dev <llvm-dev
at lists.llvm.org>
> Subject: Re: [llvm-dev] AliasAnalysis: may-alias subcategory
>
> You're right that stating may-alias(A, B) and may-alias(A, C) are the
only possible answers right now, since the compiler cannot possibly know if
these alias or not.
> LLVM supports the noalias attribute for function parameters, which may be
what you're looking for?  http://llvm.org/docs/LangRef.html#noalias
>
> If not, how differentiating between a may-alias and a
may-alias-because-it's-input would help?  Do you have a particular
optimization that would be enabled?
>
> Nuno
>
> -----Original Message-----
> From: Nema, Ashutosh via llvm-dev
> Sent: Monday, August 7, 2017 12:29 PM
> Subject: [llvm-dev] AliasAnalysis: may-alias subcategory
>
> Hi,
>
> The current AliasAnalysis marks may-alias for cases when memory passed as
function argument.
>
> i.e.
> void foo(int *A, int *B, int *C) {
>    for (int i=0; i<N; i++)
>         A[i] = B[i] + C[i];
> }
>
> In the above example, it’s may-alias for memory ‘A’, because ’A’ is not
known at ‘foo’ call sites.
> Alias analysis is able to figure out memory ‘A’ is no-alias, if I modify
the above test by making ‘A’ as an stack variable.
>
> I’m interested to find the cases where memory is always may-alias because
of input function parameter.
> Probably a sub category(may-alias-because-of-function-parameter) of
may-alias may help.
>
> Not sure llvm already has something to sub categorize may-alias cases.
>
> Thanks,
> Ashutosh
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
-- 
Hal Finkel
Lead, Compiler Technology and Programming Languages
Leadership Computing Facility
Argonne National Laboratory

Nema, Ashutosh via llvm-dev

2017-Aug-08 06:02 UTC

head link

[llvm-dev] AliasAnalysis: may-alias subcategory

Thanks Hal for inputs I'll try using it.

Regards,
Ashutosh

-----Original Message-----
From: Hal Finkel [mailto:hfinkel at anl.gov] 
Sent: Tuesday, August 8, 2017 8:55 AM
To: Nema, Ashutosh <Ashutosh.Nema at amd.com>; Nuno Lopes <nunoplopes
at sapo.pt>; llvm-dev <llvm-dev at lists.llvm.org>
Subject: Re: [llvm-dev] AliasAnalysis: may-alias subcategory


On 08/07/2017 10:28 AM, Nema, Ashutosh via llvm-dev
wrote:> There are function which does have optimization opportunities but because
of may-alias memory dependencies sometimes optimization is not effective. May be
runtime checks kills the gains of optimization. For such cases aiming to do
interprocedural function specialization optimization where in the clone function
version no-alias assumption can be assumed and the original function version
will hold the default alias assumption.
>
> i.e.
> void foo(int *A, int *B, int *C) {
>    for (int i=0; i<N; i++)
>         A[i] = B[i] + C[i];
> }
> void callFoo() {
>     foo (A1, B1, C1); // A1 no-alias with B1 & C1
>     foo (A2, B2, C2); // A2 no-alias with B1 & C1
>     foo (A3, B3, C3); // A3 must-alias with B3/C3 }
>
> Will be transformed to:
> void foo(int *A, int *B, int *C) {
>         // default loop version
> }
> void foo.clone(int * restrict A, int *B, int *C) {
>         // Optimal loop version
> }
> void callFoo() {
>     foo.clone(A1, B1, C1); // Call to optimal version
>     foo.clone(A2, B2, C2); // Call to optimal version
>     foo (A3, B3, C3); // Call to default version }
>
> For such cases I like to differentiate between “may-alias” and
“may-alias-because-it's-input”.
You can always call GetUnderlyingObjects on the relevant pointer values and
check for those that are Arguments. Is your goal here to collect all of these
may-alias results in some kind of cache while other optimizations run and then
use that to specialize later?

  -Hal
>
> Regards,
> Ashutosh
>
> -----Original Message-----
> From: Nuno Lopes [mailto:nunoplopes at sapo.pt]
> Sent: Monday, August 7, 2017 6:12 PM
> To: Nema, Ashutosh <Ashutosh.Nema at amd.com>; llvm-dev 
> <llvm-dev at lists.llvm.org>
> Subject: Re: [llvm-dev] AliasAnalysis: may-alias subcategory
>
> You're right that stating may-alias(A, B) and may-alias(A, C) are the
only possible answers right now, since the compiler cannot possibly know if
these alias or not.
> LLVM supports the noalias attribute for function parameters, which may 
> be what you're looking for?  http://llvm.org/docs/LangRef.html#noalias
>
> If not, how differentiating between a may-alias and a
may-alias-because-it's-input would help?  Do you have a particular
optimization that would be enabled?
>
> Nuno
>
> -----Original Message-----
> From: Nema, Ashutosh via llvm-dev
> Sent: Monday, August 7, 2017 12:29 PM
> Subject: [llvm-dev] AliasAnalysis: may-alias subcategory
>
> Hi,
>
> The current AliasAnalysis marks may-alias for cases when memory passed as
function argument.
>
> i.e.
> void foo(int *A, int *B, int *C) {
>    for (int i=0; i<N; i++)
>         A[i] = B[i] + C[i];
> }
>
> In the above example, it’s may-alias for memory ‘A’, because ’A’ is not
known at ‘foo’ call sites.
> Alias analysis is able to figure out memory ‘A’ is no-alias, if I modify
the above test by making ‘A’ as an stack variable.
>
> I’m interested to find the cases where memory is always may-alias because
of input function parameter.
> Probably a sub category(may-alias-because-of-function-parameter) of
may-alias may help.
>
> Not sure llvm already has something to sub categorize may-alias cases.
>
> Thanks,
> Ashutosh
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
--
Hal Finkel
Lead, Compiler Technology and Programming Languages Leadership Computing
Facility Argonne National Laboratory

Nuno Lopes via llvm-dev

2017-Aug-08 10:39 UTC

head link

[llvm-dev] AliasAnalysis: may-alias subcategory

>On 08/07/2017 10:28 AM, Nema, Ashutosh via llvm-dev wrote:
>> There are function which does have optimization opportunities but
because
>> of may-alias memory dependencies sometimes optimization is not
effective.
>> May be runtime checks kills the gains of >optimization. For such
cases
>> aiming to do interprocedural function specialization optimization where
>> in the clone function version no-alias assumption can be assumed and
the
>> original function version will hold the default alias assumption.
>>
>> i.e.
>> void foo(int *A, int *B, int *C) {
>>    for (int i=0; i<N; i++)
>>         A[i] = B[i] + C[i];
>> }
>> void callFoo() {
>>     foo (A1, B1, C1); // A1 no-alias with B1 & C1
>>     foo (A2, B2, C2); // A2 no-alias with B1 & C1
>>     foo (A3, B3, C3); // A3 must-alias with B3/C3
>> }
>>
>> Will be transformed to:
>> void foo(int *A, int *B, int *C) {
>>         // default loop version
>> }
>> void foo.clone(int * restrict A, int *B, int *C) {
>>         // Optimal loop version
>> }
>> void callFoo() {
>>     foo.clone(A1, B1, C1); // Call to optimal version
>>     foo.clone(A2, B2, C2); // Call to optimal version
>>     foo (A3, B3, C3); // Call to default version
>> }
>>
>> For such cases I like to differentiate between “may-alias” and 
>> “may-alias-because-it's-input”.
>
> You can always call GetUnderlyingObjects on the relevant pointer values 
> and check for those that are Arguments. Is your goal here to collect all 
> of these may-alias results in some kind of cache while other optimizations 
> run and then use that to specialize later?
Agreed.  Changing AA to include this information just for this use case 
doesn't seem like a good solution (adding a new AA result requires a lot of 
work). GetUnderlyingObjects() should do the trick.

Nuno

llvm dev - Aug 2017 - AliasAnalysis: may-alias subcategory

[llvm-dev] AliasAnalysis: may-alias subcategory

[llvm-dev] AliasAnalysis: may-alias subcategory

[llvm-dev] AliasAnalysis: may-alias subcategory

[llvm-dev] AliasAnalysis: may-alias subcategory