<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=us-ascii">
<meta name="Generator" content="Microsoft Word 15 (filtered medium)">
<style><!--
/* Font Definitions */
@font-face
{font-family:"Cambria Math";
panose-1:2 4 5 3 5 4 6 3 2 4;}
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0cm;
margin-bottom:.0001pt;
font-size:11.0pt;
font-family:"Calibri",sans-serif;}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:blue;
text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
{mso-style-priority:99;
color:purple;
text-decoration:underline;}
p.msonormal0, li.msonormal0, div.msonormal0
{mso-style-name:msonormal;
mso-margin-top-alt:auto;
margin-right:0cm;
mso-margin-bottom-alt:auto;
margin-left:0cm;
font-size:11.0pt;
font-family:"Calibri",sans-serif;}
span.EmailStyle18
{mso-style-type:personal;
font-family:"Calibri",sans-serif;
color:windowtext;}
span.EmailStyle19
{mso-style-type:personal-compose;
font-family:"Calibri",sans-serif;
color:windowtext;}
.MsoChpDefault
{mso-style-type:export-only;
font-family:"Calibri",sans-serif;}
@page WordSection1
{size:612.0pt 792.0pt;
margin:72.0pt 72.0pt 72.0pt 72.0pt;}
div.WordSection1
{page:WordSection1;}
--></style><!--[if gte mso 9]><xml>
<o:shapedefaults v:ext="edit" spidmax="1026" />
</xml><![endif]--><!--[if gte mso 9]><xml>
<o:shapelayout v:ext="edit">
<o:idmap v:ext="edit" data="1" />
</o:shapelayout></xml><![endif]-->
</head>
<body lang="EN-US" link="blue" vlink="purple">
<div class="WordSection1">
<p class="MsoNormal">Hi Kelvin, Tarique,<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">I finally found some time to look into your example in more depth.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">As Johannes mentioned in one of the LLVM Alias Analysis Technical calls, mapping a 'generic table' that
<o:p></o:p></p>
<p class="MsoNormal">tracks and provides alias information for any two pointers would not be an efficient way of keeping track of the aliasing<o:p></o:p></p>
<p class="MsoNormal">in llvm-ir.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">Reconstructing the (minimal) necessary scopes and intrinsics for a such a 'generic table' is also not an easy problem<o:p></o:p></p>
<p class="MsoNormal">(and not fast to solve as well).<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">I have been wondering on how to tackle the example that you provided. Reconstructing the optimal or a sensible 'noalias' set<o:p></o:p></p>
<p class="MsoNormal">by hand did not seem easy. So I went for a different approach: I created a c++ program that should represent as close as possible<o:p></o:p></p>
<p class="MsoNormal">what you are describing in fortran (and the resulting llvm-ir code). There is space for improvement here, Fortran seems to be able<o:p></o:p></p>
<p class="MsoNormal">to provide extra alias information. But it should be a good start to show how a (hierarchical based) mapping can be done.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">------- test03.cpp<o:p></o:p></p>
<p class="MsoNormal">// COMPILE: ../bin/clang++ -c test03.cpp -S -O3 -ffull-restrict -emit-llvm -mllvm -unroll-max-count=0 -mllvm --interleave-loops=false<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">// Roughly equivalent c++ structure:<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">#define restrict __restrict<o:p></o:p></p>
<p class="MsoNormal">namespace m {<o:p></o:p></p>
<p class="MsoNormal"> struct N {<o:p></o:p></p>
<p class="MsoNormal"> int* restrict tgtA01;<o:p></o:p></p>
<p class="MsoNormal"> int* restrict tgtA02;<o:p></o:p></p>
<p class="MsoNormal"> int* restrict tgtA03;<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal"> int* p_1_SetA;<o:p></o:p></p>
<p class="MsoNormal"> int* p_2_SetA;<o:p></o:p></p>
<p class="MsoNormal"> int* p_3_SetA;<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal"> // invisible to others ! But not easy to represent in c++, so there is room for improvement here<o:p></o:p></p>
<p class="MsoNormal"> int tgtB01;<o:p></o:p></p>
<p class="MsoNormal"> int tgtB02;<o:p></o:p></p>
<p class="MsoNormal"> int tgtB03;<o:p></o:p></p>
<p class="MsoNormal"> } N;<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal"> extern void init_var(int&);<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal"> void init_ptr() {<o:p></o:p></p>
<p class="MsoNormal"> N.p_1_SetA = nullptr;<o:p></o:p></p>
<p class="MsoNormal"> N.p_2_SetA = nullptr;<o:p></o:p></p>
<p class="MsoNormal"> N.p_3_SetA = nullptr;<o:p></o:p></p>
<p class="MsoNormal"> }<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal"> void compute(int & __restrict n) { // the 'n' parameters seems to be passed as a 'i32* noalias'<o:p></o:p></p>
<p class="MsoNormal"> int idx;<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal"> init_var(N.tgtB01);<o:p></o:p></p>
<p class="MsoNormal"> init_var(N.tgtB02);<o:p></o:p></p>
<p class="MsoNormal"> init_var(N.tgtB03);<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal"> {<o:p></o:p></p>
<p class="MsoNormal"> auto &assoc_tgtA01 = *N.tgtA01;<o:p></o:p></p>
<p class="MsoNormal"> auto &assoc_tgtA02 = *N.tgtA02;<o:p></o:p></p>
<p class="MsoNormal"> auto &assoc_tgtB02 = N.tgtB02;<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal"> for (idx = 1; idx <= n; ++idx) {<o:p></o:p></p>
<p class="MsoNormal"> assoc_tgtA01 = assoc_tgtA01 * N.tgtB03 + assoc_tgtA02 * (*N.tgtA03) + N.tgtB01 * assoc_tgtB02;<o:p></o:p></p>
<p class="MsoNormal"> }<o:p></o:p></p>
<p class="MsoNormal"> }<o:p></o:p></p>
<p class="MsoNormal"> }<o:p></o:p></p>
<p class="MsoNormal">}<o:p></o:p></p>
<p class="MsoNormal">------<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">Compiling this code with the full restrict patches results in similar code as you provided (no loads and stores inside the loop).<o:p></o:p></p>
<p class="MsoNormal">Notes:<o:p></o:p></p>
<p class="MsoNormal">- only two scopes are used:<o:p></o:p></p>
<p class="MsoNormal">-- one for 'n' (a local scope)<o:p></o:p></p>
<p class="MsoNormal">-- one for 'tgtA01',..,'tgtA03' (aka, the 'unknown scope', as they reside outside the function).
<o:p></o:p></p>
<p class="MsoNormal"> Because those are three different pointers, they are treated as pointing to separate objects,<o:p></o:p></p>
<p class="MsoNormal"> although they do share the same scope.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">Greetings,<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">Jeroen Dobbelaere<o:p></o:p></p>
<p class="MsoNormal"><o:p></o:p></p>
<div style="border:none;border-left:solid blue 1.5pt;padding:0cm 0cm 0cm 4.0pt">
<div>
<div style="border:none;border-top:solid #E1E1E1 1.0pt;padding:3.0pt 0cm 0cm 0cm">
<p class="MsoNormal"><b>From:</b> Kelvin Li <kli@ca.ibm.com> <br>
<b>Sent:</b> Monday, November 23, 2020 17:32<br>
<b>To:</b> Jeroen Dobbelaere <dobbel@synopsys.com>; llvm-dev@lists.llvm.org<br>
<b>Cc:</b> Tarique Islam <tislam@ca.ibm.com><br>
<b>Subject:</b> [AA] Question on the full restrict patch<o:p></o:p></p>
</div>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal"><span style="font-size:10.0pt;font-family:"Arial",sans-serif">Hi Jeroen,</span><br>
<br>
<span style="font-size:10.0pt;font-family:"Arial",sans-serif">In working on a scheme to represent Fortran alias information precisely,</span><br>
<span style="font-size:10.0pt;font-family:"Arial",sans-serif">we encounter a situation in which two alias sets partially overlap. We would</span><br>
<span style="font-size:10.0pt;font-family:"Arial",sans-serif">like to seek any idea of representing such alias sets, particular, in the scheme of</span><br>
<span style="font-size:10.0pt;font-family:"Arial",sans-serif">the full restrict alias approach in D68484.</span><br>
<br>
<span style="font-size:10.0pt;font-family:"Arial",sans-serif">Consider the following Fortran code,
</span><br>
<br>
<span style="font-size:10.0pt;font-family:"Arial",sans-serif">module m</span><br>
<span style="font-size:10.0pt;font-family:"Arial",sans-serif"> implicit none</span><br>
<span style="font-size:10.0pt;font-family:"Arial",sans-serif">!set A: variables *with* the TARGET attribute</span><br>
<span style="font-size:10.0pt;font-family:"Arial",sans-serif"> integer, allocatable, target :: tgtA01, tgtA02, tgtA03</span><br>
<span style="font-size:10.0pt;font-family:"Arial",sans-serif"> integer, pointer :: p_1_SetA, p_2_SetA, p_3_SetA</span><br>
<br>
<span style="font-size:10.0pt;font-family:"Arial",sans-serif">!set B: variables *without* the TARGET attribute</span><br>
<span style="font-size:10.0pt;font-family:"Arial",sans-serif"> integer :: tgtB01, tgtB02, tgtB03</span><br>
<br>
<span style="font-size:10.0pt;font-family:"Arial",sans-serif"> contains</span><br>
<span style="font-size:10.0pt;font-family:"Arial",sans-serif"> subroutine init_ptr()</span><br>
<span style="font-size:10.0pt;font-family:"Arial",sans-serif"> p_1_SetA = 0 ; p_2_SetA = 0 ; p_3_SetA = 0</span><br>
<span style="font-size:10.0pt;font-family:"Arial",sans-serif"> end subroutine init_ptr</span><br>
<br>
<span style="font-size:10.0pt;font-family:"Arial",sans-serif"> subroutine compute(n)</span><br>
<span style="font-size:10.0pt;font-family:"Arial",sans-serif"> integer :: idx, n</span><br>
<br>
<span style="font-size:10.0pt;font-family:"Arial",sans-serif"> call init_var(tgtB01)</span><br>
<span style="font-size:10.0pt;font-family:"Arial",sans-serif"> call init_var(tgtB02)</span><br>
<span style="font-size:10.0pt;font-family:"Arial",sans-serif"> call init_var(tgtB03)</span><br>
<br>
<span style="font-size:10.0pt;font-family:"Arial",sans-serif"> associate(assoc_tgtA01 => tgtA01, assoc_tgtA02 => tgtA02, assoc_tgtB02 => tgtB02)</span><br>
<span style="font-size:10.0pt;font-family:"Arial",sans-serif"> do idx = 1, n</span><br>
<span style="font-size:10.0pt;font-family:"Arial",sans-serif"> assoc_tgtA01 = assoc_tgtA01 * tgtB03 + assoc_tgtA02 * tgtA03 + tgtB01 * assoc_tgtB02</span><br>
<span style="font-size:10.0pt;font-family:"Arial",sans-serif"> end do</span><br>
<span style="font-size:10.0pt;font-family:"Arial",sans-serif"> end associate</span><br>
<span style="font-size:10.0pt;font-family:"Arial",sans-serif"> end subroutine compute</span><br>
<span style="font-size:10.0pt;font-family:"Arial",sans-serif">end module</span><br>
<br>
<span style="font-size:10.0pt;font-family:"Arial",sans-serif">The alias analysis in frontend can generate the following alias sets for</span><br>
<span style="font-size:10.0pt;font-family:"Arial",sans-serif">"tgtA01" and "tgtA02".</span><br>
<br>
<span style="font-size:10.0pt;font-family:"Arial",sans-serif"> -------------------------------</span><br>
<span style="font-size:10.0pt;font-family:"Arial",sans-serif"> "tgtA01" is aliased to:</span><br>
<span style="font-size:10.0pt;font-family:"Arial",sans-serif"> "__m_NMOD__&&_m" "__m_NMOD_init_ptr" "__m_NMOD_compute" "init_var"</span><br>
<span style="font-size:10.0pt;font-family:"Arial",sans-serif"> "p_1_SetA" "p_2_SetA" "p_3_SetA"</span><br>
<span style="font-size:10.0pt;font-family:"Arial",sans-serif"> "assoc_tgtA01" "tgtA01"</span><br>
<span style="font-size:10.0pt;font-family:"Arial",sans-serif"> -------------------------------</span><br>
<span style="font-size:10.0pt;font-family:"Arial",sans-serif"> "tgtA02" is aliased to:</span><br>
<span style="font-size:10.0pt;font-family:"Arial",sans-serif"> "__m_NMOD__&&_m" "__m_NMOD_init_ptr" "__m_NMOD_compute" "init_var"</span><br>
<span style="font-size:10.0pt;font-family:"Arial",sans-serif"> "p_1_SetA" "p_2_SetA" "p_3_SetA"</span><br>
<span style="font-size:10.0pt;font-family:"Arial",sans-serif"> "assoc_tgtA02" "tgtA02"</span><br>
<span style="font-size:10.0pt;font-family:"Arial",sans-serif"> -------------------------------</span><br>
<br>
<span style="font-size:10.0pt;font-family:"Arial",sans-serif">If we express this alias info with the scheme that we presented in the last LLVM</span><br>
<span style="font-size:10.0pt;font-family:"Arial",sans-serif">Developers' Meeting (</span><a href="https://urldefense.com/v3/__https:/youtu.be/Vp4GklTXDys__;!!A4F2R9G_pg!M47wpuFvIB8nYHqyIHGWMVh8KC2Qey52i3II-OppwxkfGZroge9Sd3Dsm27DZ_TCRtx4hTyK$"><span style="font-size:10.0pt;font-family:"Arial",sans-serif">https://youtu.be/Vp4GklTXDys</span></a><span style="font-size:10.0pt;font-family:"Arial",sans-serif">),
the optimizer manages to</span><br>
<span style="font-size:10.0pt;font-family:"Arial",sans-serif">move the loop invariant code out of the loop body. We think that the optimizer</span><br>
<span style="font-size:10.0pt;font-family:"Arial",sans-serif">can make use of the alias information even though there is an overlap in the two</span><br>
<span style="font-size:10.0pt;font-family:"Arial",sans-serif">alias sets. With the D69542 patch (</span><a href="https://urldefense.com/v3/__https:/reviews.llvm.org/D69542__;!!A4F2R9G_pg!M47wpuFvIB8nYHqyIHGWMVh8KC2Qey52i3II-OppwxkfGZroge9Sd3Dsm27DZ_TCRh8Eigua$"><span style="font-size:10.0pt;font-family:"Arial",sans-serif">https://reviews.llvm.org/D69542</span></a><span style="font-size:10.0pt;font-family:"Arial",sans-serif">),
we would</span><br>
<span style="font-size:10.0pt;font-family:"Arial",sans-serif">like to know if there is any way to express that with the intrinsics proposed in</span><br>
<span style="font-size:10.0pt;font-family:"Arial",sans-serif">the full restrict patch.</span><br>
<br>
<span style="font-size:10.0pt;font-family:"Arial",sans-serif">We attach the ll files for reference.</span><br>
<br>
<span style="font-size:10.0pt;font-family:"Arial",sans-serif">Note: The options --unroll-max-count=0 --interleave-loops=false</span><br>
<span style="font-size:10.0pt;font-family:"Arial",sans-serif">-passes=default<O3> -aa-pipeline=default are used in opt.</span><br>
<br>
<span style="font-size:10.0pt;font-family:"Arial",sans-serif">Attachments</span><br>
<span style="font-size:10.0pt;font-family:"Arial",sans-serif">0. alias-sets-from-fe.txt - full alias sets generated from Fortran frontend</span><br>
<span style="font-size:10.0pt;font-family:"Arial",sans-serif">1. before-opt-without-alias-from-fe.ll - IR before opt (NO alias info is emitted)</span><br>
<span style="font-size:10.0pt;font-family:"Arial",sans-serif">2. after-opt-without-alias-from-fe.ll - IR after opt (NO alias info is emitted)</span><br>
<span style="font-size:10.0pt;font-family:"Arial",sans-serif">3. before-opt-with-alias-from-fe.ll - IR before opt (noalias/alias.scope metadata is emitted)</span><br>
<span style="font-size:10.0pt;font-family:"Arial",sans-serif">4. after-opt-with-alias-from-fe.ll - IR after opt (noalias/alias.scope metadata is emitted)</span><br>
<br>
<br>
<br>
<br>
<br>
<br>
<span style="font-size:10.0pt;font-family:"Arial",sans-serif">Thanks,</span><br>
<span style="font-size:10.0pt;font-family:"Arial",sans-serif">Kelvin</span><o:p></o:p></p>
</div>
</div>
</body>
</html>