llvm dev - Apr 2020 - Represent Fortran alias information in LLVM IR

Hi,

We, IBM XL Fortran compiler team, is interested in representing Fortran 
alias information in LLVM IR.  We use the XL Fortran frontend to emit LLVM 
IR that includes alias information to feed to the LLVM in order to create 
object files.  For the Fortran alias representation in LLVM IR, we 
considered both TBAA and ScopeAlias/NoAlias metadata approaches, we think 
that the ScopeAlias/NoAlias metadata is more appropriate for refined alias 
information for Fortran.  The XL Fortran frontend emits the alias info in 
terms of what other symbols that a symbol alias to.  We experiment a 
scheme that represents the alias relation in terms of noalias and scope 
alias metadata in LLVM IR.  An example is shown in the attached slides and 
the full .ll file for the example is also attached.

In this experiment, we observe that the performance gain varies from 
workload to workload, and the extent can be from a few percent to 2X.  The 
compile time and the size of the IR increase as well.

We briefly investigated the possible causes of the long compile time and 
the large IR size issues.  For the compile-time performance, we observe:
- Each alias query (ScopedNoAliasAAResult::mayAliasInScopes) involves 
partitioning a metadata set based on the domains of the metadata elements. 
 One possible solution is that pre-partitioning the metadata sets and 
maintaining the partitions on updates can help.
- Intersection of noalias sets is O(n^2) as metadata elements do not have 
any ordering. Defining some order on the elements can help significantly.
- Some optimizations do not scale well when the size of the working 
instruction set increases, e.g. SCEV functions.

For the size of LLVM IR, the noalias metadata requires a flattened set of 
metadata nodes.  A hierarchical representation can reduce memory 
footprint.

With these findings, we would like to start a thread to discuss how to 
express Fortran alias in LLVM IR.  Any comments and information regarding 
any previous approaches are welcome.





Thanks,
Kelvin Li
Tarique Islam





-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20200414/1486cc58/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: Fortran alias in LLVM.pdf
Type: application/pdf
Size: 217852 bytes
Desc: not available
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20200414/1486cc58/attachment-0001.pdf>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: example.ll
Type: application/octet-stream
Size: 2656 bytes
Desc: not available
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20200414/1486cc58/attachment-0001.obj>

Hi,

any idea how aliasing rules in Fortran compare to 'restrict' in
C/__restrict in C++ ?
If they are comparable, [0].[1] could maybe help ?

Greetings,

Jeroen Dobbelaere

[0] https://lists.llvm.org/pipermail/llvm-dev/2019-October/135672.html
[1] https://reviews.llvm.org/D68484


From: llvm-dev <llvm-dev-bounces at lists.llvm.org> On Behalf Of Kelvin Li
via llvm-dev
Sent: Tuesday, April 14, 2020 20:21
To: llvm-dev at lists.llvm.org; flang-dev at lists.llvm.org
Subject: [llvm-dev] Represent Fortran alias information in LLVM IR

Hi,

We, IBM XL Fortran compiler team, is interested in representing Fortran alias
information in LLVM IR.  We use the XL Fortran frontend to emit LLVM IR that
includes alias information to feed to the LLVM in order to create object files. 
For the Fortran alias representation in LLVM IR, we considered both TBAA and
ScopeAlias/NoAlias metadata approaches, we think that the ScopeAlias/NoAlias
metadata is more appropriate for refined alias information for Fortran.  The XL
Fortran frontend emits the alias info in terms of what other symbols that a
symbol alias to.  We experiment a scheme that represents the alias relation in
terms of noalias and scope alias metadata in LLVM IR.  An example is shown in
the attached slides and the full .ll file for the example is also attached.

In this experiment, we observe that the performance gain varies from workload to
workload, and the extent can be from a few percent to 2X.  The compile time and
the size of the IR increase as well.

We briefly investigated the possible causes of the long compile time and the
large IR size issues.  For the compile-time performance, we observe:
- Each alias query (ScopedNoAliasAAResult::mayAliasInScopes) involves
partitioning a metadata set based on the domains of the metadata elements.  One
possible solution is that pre-partitioning the metadata sets and maintaining the
partitions on updates can help.
- Intersection of noalias sets is O(n^2) as metadata elements do not have any
ordering. Defining some order on the elements can help significantly.
- Some optimizations do not scale well when the size of the working instruction
set increases, e.g. SCEV functions.

For the size of LLVM IR, the noalias metadata requires a flattened set of
metadata nodes.  A hierarchical representation can reduce memory footprint.

With these findings, we would like to start a thread to discuss how to express
Fortran alias in LLVM IR.  Any comments and information regarding any previous
approaches are welcome.





Thanks,
Kelvin Li
Tarique Islam



-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20200415/9650f811/attachment.html>

Jeroen Dobbelaere via llvm-dev <llvm-dev at lists.llvm.org> writes:
> Hi,
>
> any idea how aliasing rules in Fortran compare to 'restrict' in
C/__restrict in C++ ?
> If they are comparable, [0].[1] could maybe help ?
"restrict" was originally introduced into C to mimic the Fortran
aliasing rules.  I am no expert on it but the fellow who wrote the
"restrict" proposal still works here.  I should think Jeroen's
work
would be applicable to representing Fortran aliasing rules.

                     -David
> Greetings,
>
> Jeroen Dobbelaere
>
> [0] https://lists.llvm.org/pipermail/llvm-dev/2019-October/135672.html
> [1] https://reviews.llvm.org/D68484
>
>
> From: llvm-dev <llvm-dev-bounces at lists.llvm.org> On Behalf Of
Kelvin Li via llvm-dev
> Sent: Tuesday, April 14, 2020 20:21
> To: llvm-dev at lists.llvm.org; flang-dev at lists.llvm.org
> Subject: [llvm-dev] Represent Fortran alias information in LLVM IR
>
> Hi,
>
> We, IBM XL Fortran compiler team, is interested in representing Fortran
alias information in LLVM IR.  We use the XL Fortran frontend to emit LLVM IR
that includes alias information to feed to the LLVM in order to create object
files.  For the Fortran alias representation in LLVM IR, we considered both TBAA
and ScopeAlias/NoAlias metadata approaches, we think that the ScopeAlias/NoAlias
metadata is more appropriate for refined alias information for Fortran.  The XL
Fortran frontend emits the alias info in terms of what other symbols that a
symbol alias to.  We experiment a scheme that represents the alias relation in
terms of noalias and scope alias metadata in LLVM IR.  An example is shown in
the attached slides and the full .ll file for the example is also attached.
>
> In this experiment, we observe that the performance gain varies from
workload to workload, and the extent can be from a few percent to 2X.  The
compile time and the size of the IR increase as well.
>
> We briefly investigated the possible causes of the long compile time and
the large IR size issues.  For the compile-time performance, we observe:
> - Each alias query (ScopedNoAliasAAResult::mayAliasInScopes) involves
partitioning a metadata set based on the domains of the metadata elements.  One
possible solution is that pre-partitioning the metadata sets and maintaining the
partitions on updates can help.
> - Intersection of noalias sets is O(n^2) as metadata elements do not have
any ordering. Defining some order on the elements can help significantly.
> - Some optimizations do not scale well when the size of the working
instruction set increases, e.g. SCEV functions.
>
> For the size of LLVM IR, the noalias metadata requires a flattened set of
metadata nodes.  A hierarchical representation can reduce memory footprint.
>
> With these findings, we would like to start a thread to discuss how to
express Fortran alias in LLVM IR.  Any comments and information regarding any
previous approaches are welcome.
>
>
>
>
>
> Thanks,
> Kelvin Li
> Tarique Islam
>
>
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

Hi Jeroen,

As far as I know, some dummy arguments in Fortran have the restrict 
property. 

Thanks for the information.  We were pointed to your patch during the last 
Flang technical call when we presented our work. We are still going thru 
it and we will definitely look into if it helps Fortran alias. By the way, 
the Flang technical meeting will continue to discuss Fortran alias topic 
next Monday (Apr 20, 2020 @ 11:30 EDT).  Hope that you can join and 
provide your insight.

Thanks,
Kelvin




From:   Jeroen Dobbelaere <Jeroen.Dobbelaere at synopsys.com>
To:     Kelvin Li <kli at ca.ibm.com>, "flang-dev at
lists.llvm.org"
<flang-dev at lists.llvm.org>, "llvm-dev at lists.llvm.org" 
<llvm-dev at lists.llvm.org>
Date:   2020/04/15 12:08 PM
Subject:        [EXTERNAL] RE: [llvm-dev] Represent Fortran alias 
information in LLVM IR



Hi,
 
any idea how aliasing rules in Fortran compare to 'restrict' in 
C/__restrict in C++ ?
If they are comparable, [0].[1] could maybe help ?
 
Greetings,
 
Jeroen Dobbelaere
 
[0] https://lists.llvm.org/pipermail/llvm-dev/2019-October/135672.html
[1] https://reviews.llvm.org/D68484
 
 
From: llvm-dev <llvm-dev-bounces at lists.llvm.org> On Behalf Of Kelvin Li
via llvm-dev
Sent: Tuesday, April 14, 2020 20:21
To: llvm-dev at lists.llvm.org; flang-dev at lists.llvm.org
Subject: [llvm-dev] Represent Fortran alias information in LLVM IR
 
Hi,

We, IBM XL Fortran compiler team, is interested in representing Fortran 
alias information in LLVM IR.  We use the XL Fortran frontend to emit LLVM 
IR that includes alias information to feed to the LLVM in order to create 
object files.  For the Fortran alias representation in LLVM IR, we 
considered both TBAA and ScopeAlias/NoAlias metadata approaches, we think 
that the ScopeAlias/NoAlias metadata is more appropriate for refined alias 
information for Fortran.  The XL Fortran frontend emits the alias info in 
terms of what other symbols that a symbol alias to.  We experiment a 
scheme that represents the alias relation in terms of noalias and scope 
alias metadata in LLVM IR.  An example is shown in the attached slides and 
the full .ll file for the example is also attached.

In this experiment, we observe that the performance gain varies from 
workload to workload, and the extent can be from a few percent to 2X.  The 
compile time and the size of the IR increase as well.

We briefly investigated the possible causes of the long compile time and 
the large IR size issues.  For the compile-time performance, we observe:
- Each alias query (ScopedNoAliasAAResult::mayAliasInScopes) involves 
partitioning a metadata set based on the domains of the metadata elements. 
 One possible solution is that pre-partitioning the metadata sets and 
maintaining the partitions on updates can help.
- Intersection of noalias sets is O(n^2) as metadata elements do not have 
any ordering. Defining some order on the elements can help significantly.
- Some optimizations do not scale well when the size of the working 
instruction set increases, e.g. SCEV functions.

For the size of LLVM IR, the noalias metadata requires a flattened set of 
metadata nodes.  A hierarchical representation can reduce memory 
footprint.

With these findings, we would like to start a thread to discuss how to 
express Fortran alias in LLVM IR.  Any comments and information regarding 
any previous approaches are welcome.





Thanks,
Kelvin Li
Tarique Islam






-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20200416/83148e36/attachment.html>

Hi Kelvin,


recently it came up twice that we might want to have alias information 
looking something like this:

`llvm.assume(i1 true) ['noalias'(%ptrA, %ptrB)]`

Which is supposed to mean that under the control condition of the 
`llvm.assume`,

anything derived from `%ptrA` will not alias anything derived from `%ptrB`.

We will have a separate RFC for this but I was wondering if it might 
benefit your use case.


Let me know if you need more information :)


Looking forward to your thoughts!


Cheers,

   Johannes


On 4/14/20 1:21 PM, Kelvin Li via llvm-dev wrote:
> Hi,
>
> We, IBM XL Fortran compiler team, is interested in representing Fortran
> alias information in LLVM IR.  We use the XL Fortran frontend to emit LLVM
> IR that includes alias information to feed to the LLVM in order to create
> object files.  For the Fortran alias representation in LLVM IR, we
> considered both TBAA and ScopeAlias/NoAlias metadata approaches, we think
> that the ScopeAlias/NoAlias metadata is more appropriate for refined alias
> information for Fortran.  The XL Fortran frontend emits the alias info in
> terms of what other symbols that a symbol alias to.  We experiment a
> scheme that represents the alias relation in terms of noalias and scope
> alias metadata in LLVM IR.  An example is shown in the attached slides and
> the full .ll file for the example is also attached.
>
> In this experiment, we observe that the performance gain varies from
> workload to workload, and the extent can be from a few percent to 2X.  The
> compile time and the size of the IR increase as well.
>
> We briefly investigated the possible causes of the long compile time and
> the large IR size issues.  For the compile-time performance, we observe:
> - Each alias query (ScopedNoAliasAAResult::mayAliasInScopes) involves
> partitioning a metadata set based on the domains of the metadata elements.
>   One possible solution is that pre-partitioning the metadata sets and
> maintaining the partitions on updates can help.
> - Intersection of noalias sets is O(n^2) as metadata elements do not have
> any ordering. Defining some order on the elements can help significantly.
> - Some optimizations do not scale well when the size of the working
> instruction set increases, e.g. SCEV functions.
>
> For the size of LLVM IR, the noalias metadata requires a flattened set of
> metadata nodes.  A hierarchical representation can reduce memory
> footprint.
>
> With these findings, we would like to start a thread to discuss how to
> express Fortran alias in LLVM IR.  Any comments and information regarding
> any previous approaches are welcome.
>
>
>
>
>
> Thanks,
> Kelvin Li
> Tarique Islam
>
>
>
>
>
>
>
> _______________________________________________
> LLVM Developers mailing list
> 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/20200506/678d00cc/attachment.html>

<div class="socmaildefaultfont" dir="ltr"
style="font-family:Arial, Helvetica, sans-serif;font-size:10pt"
><div dir="ltr" >Hi Johannes,</div>
<div dir="ltr" > </div>
<div dir="ltr" >Thanks for the info.  It sounds interesting.  At
this point, I am not sure if it helps or not.  Could you provide more
information?  E.g. motivating examples, rationale etc.  For the list after the
llvm.assume call, does it allow a list of more than two items?  How about if I
have many calls, does it affect compile time?</div>
<div dir="ltr" ><br>Kelvin</div>
<div dir="ltr" > </div>
<div dir="ltr" > </div>
<blockquote data-history-content-modified="1" dir="ltr"
style="border-left:solid #aaaaaa 2px; margin-left:5px; padding-left:5px;
direction:ltr; margin-right:0px" >----- Original message
-----<br>From: Johannes Doerfert
<johannesdoerfert@gmail.com><br>To: Kelvin Li
<kli@ca.ibm.com>, llvm-dev@lists.llvm.org,
flang-dev@lists.llvm.org<br>Cc:<br>Subject: [EXTERNAL] Re:
[llvm-dev] Represent Fortran alias information in LLVM IR<br>Date: Wed,
May 6, 2020 11:05 AM<br> <br><!--Notes ACF
<meta http-equiv="Content-Type" content="text/html;     
charset=utf8" >-->
<p><font face="Hack Nerd Font Mono" >Hi
Kelvin,</font></p>
<p> </p>
<p><font face="Hack Nerd Font Mono" >recently it came up
twice that we might want to have alias information looking something like
this:</font></p>
<p><font face="Hack Nerd Font Mono" >`llvm.assume(i1 true)
['noalias'(%ptrA, %ptrB)]`</font></p>
<p><font face="Hack Nerd Font Mono" >Which is supposed to
mean that under the control condition of the
`llvm.assume`,</font></p>
<p><font face="Hack Nerd Font Mono" >anything derived from
`%ptrA` will not alias anything derived from `%ptrB`.</font></p>
<p><font face="Hack Nerd Font Mono" >We will have a
separate RFC for this but I was wondering if it might benefit your use
case.</font></p>
<p> </p>
<p><font face="Hack Nerd Font Mono" >Let me know if you
need more information :)</font></p>
<p> </p>
<p><font face="Hack Nerd Font Mono" >Looking forward to
your thoughts!</font></p>
<p> </p>
<p><font face="Hack Nerd Font Mono"
>Cheers,</font></p>
<p><font face="Hack Nerd Font Mono" > 
Johannes</font></p>
<p> </p>
<div>On 4/14/20 1:21 PM, Kelvin Li via llvm-dev wrote:</div>
<blockquote
cite="mid:OF61357B01.99800180-ON8525854A.0052153B-8525854A.0064CD05@notes.na.collabserv.com"
type="cite" ><div><font size="2"
face="Default Monospace,Courier New,Courier,monospace"
>Hi,<br><br>We, IBM XL Fortran compiler team, is interested in
representing Fortran<br>alias information in LLVM IR.  We use the XL
Fortran frontend to emit LLVM<br>IR that includes alias information to
feed to the LLVM in order to create<br>object files.  For the Fortran
alias representation in LLVM IR, we<br>considered both TBAA and
ScopeAlias/NoAlias metadata approaches, we think<br>that the
ScopeAlias/NoAlias metadata is more appropriate for refined
alias<br>information for Fortran.  The XL Fortran frontend emits the alias
info in<br>terms of what other symbols that a symbol alias to.  We
experiment a<br>scheme that represents the alias relation in terms of
noalias and scope<br>alias metadata in LLVM IR.  An example is shown in
the attached slides and<br>the full .ll file for the example is also
attached.<br><br>In this experiment, we observe that the performance
gain varies from<br>workload to workload, and the extent can be from a few
percent to 2X.  The<br>compile time and the size of the IR increase as
well.<br><br>We briefly investigated the possible causes of the long
compile time and<br>the large IR size issues.  For the compile-time
performance, we observe:<br>- Each alias query
(ScopedNoAliasAAResult::mayAliasInScopes) involves<br>partitioning a
metadata set based on the domains of the metadata elements.<br> One
possible solution is that pre-partitioning the metadata sets
and<br>maintaining the partitions on updates can help.<br>-
Intersection of noalias sets is O(n^2) as metadata elements do not
have<br>any ordering. Defining some order on the elements can help
significantly.<br>- Some optimizations do not scale well when the size of
the working<br>instruction set increases, e.g. SCEV
functions.<br><br>For the size of LLVM IR, the noalias metadata
requires a flattened set of<br>metadata nodes.  A hierarchical
representation can reduce memory<br>footprint.<br><br>With
these findings, we would like to start a thread to discuss how
to<br>express Fortran alias in LLVM IR.  Any comments and information
regarding<br>any previous approaches are
welcome.<br><br><br><br><br><br>Thanks,<br>Kelvin
Li<br>Tarique
Islam</font><br><br><br><br><br><br>
</div>

<fieldset> </fieldset>
<div><font size="2" face="Default Monospace,Courier
New,Courier,monospace"
>_______________________________________________<br>LLVM Developers
mailing list<br><a href="mailto:llvm-dev@lists.llvm.org"
target="_blank">llvm-dev@lists.llvm.org</a><br><a
href="https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev"
target="_blank">https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a></font></div></blockquote></blockquote>
<div dir="ltr" > </div></div><BR>