<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=utf-8"><meta name=Generator content="Microsoft Word 15 (filtered medium)"><!--[if !mso]><style>v\:* {behavior:url(#default#VML);}
o\:* {behavior:url(#default#VML);}
w\:* {behavior:url(#default#VML);}
.shape {behavior:url(#default#VML);}
</style><![endif]--><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;}
@font-face
{font-family:Consolas;
panose-1:2 11 6 9 2 2 4 3 2 4;}
@font-face
{font-family:"Segoe UI";
panose-1:2 11 5 2 4 2 4 2 2 3;}
/* 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;}
pre
{mso-style-priority:99;
mso-style-link:"HTML Preformatted Char";
margin:0cm;
margin-bottom:.0001pt;
font-size:10.0pt;
font-family:"Courier New";}
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.m-5619189094996677201m-6267006566340524503gmail-
{mso-style-name:m_-5619189094996677201m_-6267006566340524503gmail-;}
span.m-5619189094996677201hoenzb
{mso-style-name:m_-5619189094996677201hoenzb;}
span.HTMLPreformattedChar
{mso-style-name:"HTML Preformatted Char";
mso-style-priority:99;
mso-style-link:"HTML Preformatted";
font-family:Consolas;}
span.EmailStyle23
{mso-style-type:personal;
font-family:"Calibri",sans-serif;
color:windowtext;}
span.EmailStyle24
{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 Alina,<o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>My only concern with that design is that it seems that you can go from MustModRef into Ref or Mod, and that is not true.<o:p></o:p></p><p class=MsoNormal>Assuming my understanding of what ModRef & friends mean is correct, this is the lattice (where green are the official names, and black are my comments): <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><img width=599 height=203 style='width:6.2361in;height:2.118in' id="Picture_x0020_1" src="cid:image001.jpg@01D36451.837BE5E0"><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>AFAIU, MustModRef means that an operation *<b>must</b>* read and write to the given location. Moreover, it *<b>must</b>* alias with that allocation.<o:p></o:p></p><p class=MsoNormal>Therefore, we cannot go from MustModRef into MayRef, because MayRef implies there<span style='font-family:"Times New Roman",serif'>’</span>s no write; there<span style='font-family:"Times New Roman",serif'>’</span>s at most a read.<o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>What confused me first is that Mod has 2 <span style='font-family:"Times New Roman",serif'>“</span>mays<span style='font-family:"Times New Roman",serif'>”</span>: may read, and if it does it may be to the given location.<o:p></o:p></p><p class=MsoNormal>While MustMod has 2 <span style='font-family:"Times New Roman",serif'>“</span>musts<span style='font-family:"Times New Roman",serif'>”</span>: must read, and it must read exactly from the given location.<o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>Your lattice doesn<span style='font-family:"Times New Roman",serif'>’</span>t have the intermediate values (1 may + 1 must, like MustModMayAlias), but that would increase significantly the size of the lattice. I don<span style='font-family:"Times New Roman",serif'>’</span>t know which clients would benefit of that precision increase (if any) <span style='font-family:"Times New Roman",serif'>–</span> didn<span style='font-family:"Times New Roman",serif'>’</span>t think about that.<o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>Nuno<o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal><a name="_MailEndCompose"><o:p> </o:p></a></p><span style='mso-bookmark:_MailEndCompose'></span><p class=MsoNormal><b>From:</b> Alina Sbirlea<br><b>Sent:</b> 22 November 2017 23:06<br><b>To:</b> Hal Finkel <hfinkel@anl.gov>; Daniel Berlin <dberlin@dberlin.org>; George Burgess IV <george.burgess.iv@gmail.com>; llvm-dev <llvm-dev@lists.llvm.org>; Sanjoy Das <sanjoy@playingwithpointers.com><br><b>Subject:</b> Re: [llvm-dev] Expose aliasing information in getModRefInfo (or viceversa?)<o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><div><p class=MsoNormal>Re-opening this discussion, to get some feedback.<o:p></o:p></p><div><p class=MsoNormal><o:p> </o:p></p></div><div><p class=MsoNormal>Adding alias info is under review in <a href="https://reviews.llvm.org/D38862">https://reviews.llvm.org/D38862</a>.<o:p></o:p></p></div><div><p class=MsoNormal><o:p> </o:p></p></div><div><p class=MsoNormal>An issue that came up, that was bugging me before is how to reason of what is top/bottom of the lattice, and what is the default to test against.<o:p></o:p></p></div><div><p class=MsoNormal>So talking offline is Sanjoy, we reached a slightly different conclusion which makes more sense to me.<o:p></o:p></p></div><div><p class=MsoNormal><o:p> </o:p></p></div><div><p class=MsoNormal>Current patch has:<o:p></o:p></p></div><div><div><p class=MsoNormal><span style='font-size:9.5pt'>enum ModRefInfo {<br> MRI_NoModRef = 0,<br> MRI_Ref = 1,<br> MRI_Mod = 2,<br> MRI_ModRef = MRI_Ref | MRI_Mod,<br> MRI_Must = 4,<o:p></o:p></span></p></div><div><p class=MsoNormal><span style='font-size:9.5pt'> MRI_MustRef = MRI_Ref | MRI_Must,<o:p></o:p></span></p></div><div><p class=MsoNormal><span style='font-size:9.5pt'> MRI_MustMod = MRI_Mod | MRI_Must,<o:p></o:p></span></p></div><div><p class=MsoNormal><span style='font-size:9.5pt'> MRI_MustModRef = MRI_ModRef | MRI_Must<br>};<o:p></o:p></span></p></div></div><div><p class=MsoNormal><span style='font-size:9.5pt'><o:p> </o:p></span></p></div><div><p class=MsoNormal><span style='font-size:9.5pt'>Proposed change:<o:p></o:p></span></p></div><div><div><p class=MsoNormal><span style='font-size:9.5pt'>enum ModRefInfo {<o:p></o:p></span></p></div><div><div><p class=MsoNormal><span style='font-size:9.5pt'> MRI_Must = 0,<o:p></o:p></span></p></div><div><p class=MsoNormal><span style='font-size:9.5pt'> MRI_MustRef = 1,<o:p></o:p></span></p></div><div><p class=MsoNormal><span style='font-size:9.5pt'> MRI_MustMod = 2,<o:p></o:p></span></p></div><div><p class=MsoNormal><span style='font-size:9.5pt'> MRI_MustModRef = MRI_MustRef | MRI_MustMod<o:p></o:p></span></p></div><p class=MsoNormal><span style='font-size:9.5pt'> MRI_NoModRef = 4,<br> MRI_Ref = MRI_NoModRef | MRI_MustRef , /* Same semantics as right now, i.e. MayRef */<o:p></o:p></span></p></div><div><p class=MsoNormal><span style='font-size:9.5pt'> MRI_Mod = MRI_NoModRef | MRI_MustMod , /* Same semantics as right now, i.e. MayMod */<o:p></o:p></span></p></div><div><p class=MsoNormal><span style='font-size:9.5pt'> MRI_ModRef = MRI_Ref | MRI_Mod, /* Same semantics as right now, i.e. May Ref or Mod */<o:p></o:p></span></p></div><div><p class=MsoNormal><span style='font-size:9.5pt'>};<o:p></o:p></span></p></div><div><p class=MsoNormal><span style='font-size:9.5pt'><o:p> </o:p></span></p></div><div><p class=MsoNormal><span style='font-size:9.5pt'>With this change:<o:p></o:p></span></p></div><div><p class=MsoNormal><span style='font-size:9.5pt'>- the same approach of "set a bit to 0 when additional info is available" will apply to the Must bit, as it does to Ref and Mod.<o:p></o:p></span></p></div><div><p class=MsoNormal><span style='font-size:9.5pt'>- we could keep the same checks with MRI_NoModRef<o:p></o:p></span></p></div><div><p class=MsoNormal><span style='font-size:9.5pt'>- MRI_ModRef remains the most conservative answer (top).<o:p></o:p></span></p></div><div><p class=MsoNormal><span style='font-size:9.5pt'>- finding MRI_Must gives more info than MRI_NoModRef, so it makes sense to be bottom.<o:p></o:p></span></p></div><div><p class=MsoNormal><span style='font-size:9.5pt'>- MRI_NoModRef means "no mod or ref, and no must alias".<o:p></o:p></span></p></div><div><p class=MsoNormal><span style='font-size:9.5pt'><o:p> </o:p></span></p></div><div><p class=MsoNormal><span style='font-size:9.5pt'>The only obvious change I see right now will be to to add " | MRI_NoModRef", essentially setting the default to "not must alias".<o:p></o:p></span></p></div><div><p class=MsoNormal><span style='font-size:10.0pt;font-family:"Segoe UI",sans-serif;color:black'>For GlobalsModRef, we can also always set </span><span style='font-size:9.5pt'>MRI_NoModRef bit.<o:p></o:p></span></p></div><div><p class=MsoNormal><span style='font-size:9.5pt'><o:p> </o:p></span></p></div><div><p class=MsoNormal><span style='font-size:9.5pt'>I may be missing details here, happy to elaborate.<o:p></o:p></span></p></div><div><p class=MsoNormal><span style='font-size:9.5pt'><o:p> </o:p></span></p></div><div><p class=MsoNormal><span style='font-size:9.5pt'>Happy Thanksgiving!<o:p></o:p></span></p></div><div><p class=MsoNormal><span style='font-size:9.5pt'><o:p> </o:p></span></p></div><div><p class=MsoNormal><span style='font-size:9.5pt'>Alina<o:p></o:p></span></p></div><div><p class=MsoNormal><span style='font-size:9.5pt'><o:p> </o:p></span></p></div></div><div><p class=MsoNormal><o:p> </o:p></p></div></div><div><p class=MsoNormal><o:p> </o:p></p><div><p class=MsoNormal>On Tue, Oct 10, 2017 at 1:13 PM, Alina Sbirlea <<a href="mailto:alina.sbirlea@gmail.com" target="_blank">alina.sbirlea@gmail.com</a>> wrote:<o:p></o:p></p><blockquote style='border:none;border-left:solid #CCCCCC 1.0pt;padding:0cm 0cm 0cm 6.0pt;margin-left:4.8pt;margin-right:0cm'><div><div><p class=MsoNormal><o:p> </o:p></p><div><div><div><p class=MsoNormal>On Tue, Oct 10, 2017 at 1:05 PM, Hal Finkel <<a href="mailto:hfinkel@anl.gov" target="_blank">hfinkel@anl.gov</a>> wrote:<o:p></o:p></p><blockquote style='border:none;border-left:solid #CCCCCC 1.0pt;padding:0cm 0cm 0cm 6.0pt;margin-left:4.8pt;margin-right:0cm'><div><div><div><p><o:p> </o:p></p><div><p class=MsoNormal>On 10/10/2017 02:49 PM, Alina Sbirlea wrote:<o:p></o:p></p></div><blockquote style='margin-top:5.0pt;margin-bottom:5.0pt'><div><div><div><blockquote style='border:none;border-left:solid #CCCCCC 1.0pt;padding:0cm 0cm 0cm 6.0pt;margin-left:4.8pt;margin-right:0cm'><div><div><div><div><p class=MsoNormal>Sigh<o:p></o:p></p></div><div><p class=MsoNormal>I should have taken the time to give a better example.<o:p></o:p></p></div><div><p class=MsoNormal>The must-alias part is irrelevant to an example (it only requires read-onlyness)<o:p></o:p></p></div><div><p class=MsoNormal><o:p> </o:p></p></div><div><p class=MsoNormal>You said "LICM doesn't move calls, so we'd never really care about must-alias for promotion". I was just pointing out other things move calls any may want to know.<o:p></o:p></p></div><div><p class=MsoNormal> <o:p></o:p></p></div><div><p class=MsoNormal>If you want an example where the must-alias part would matter:<o:p></o:p></p></div><div><p class=MsoNormal><o:p> </o:p></p></div><div><p class=MsoNormal>*a = something<o:p></o:p></p></div><div><p class=MsoNormal>foo(a)<o:p></o:p></p></div><div><p class=MsoNormal>b = *a<o:p></o:p></p></div><div><p class=MsoNormal><o:p> </o:p></p></div><div><p class=MsoNormal>If foo mustalias a (and only a) not only can you move foo with a, you can actually clone foo here, change it to be pass-by-value, and promote the argument inside of it (if you wanted to).<o:p></o:p></p></div><div><p class=MsoNormal><o:p> </o:p></p></div><div><p class=MsoNormal>So you can use this info to, for example, do interprocedural promotion.<o:p></o:p></p></div><div><p class=MsoNormal><o:p> </o:p></p></div><blockquote style='border:none;border-left:solid #CCCCCC 1.0pt;padding:0cm 0cm 0cm 6.0pt;margin-left:4.8pt;margin-right:0cm'><div><div><p class=MsoNormal><o:p> </o:p></p></div><div><p class=MsoNormal>Are we instead looking to set a MRI_Must bit, disjunct of MRI_Mod, and test for MRI_Ref&MRI_Must or MRI_Mod&MRI_Must?<o:p></o:p></p></div></div></blockquote><div><p class=MsoNormal><o:p> </o:p></p></div><div><p class=MsoNormal>Yes.<o:p></o:p></p></div></div></div></div></blockquote><div><p class=MsoNormal><o:p> </o:p></p></div><div><p class=MsoNormal>I didn't mean to pick on the example, sorry if that's how it came through.<o:p></o:p></p></div><div><p class=MsoNormal><o:p> </o:p></p></div><div><p class=MsoNormal>Since the consensus is to expose the Must info in ModRefInfo, I'm trying to figure out how to add it in a way that makes sense to me.<o:p></o:p></p></div><div><p class=MsoNormal>The way I see ModRefInfo is designed right now is to lower the lattice to NoModRef as fast as possible (start with ModRef as top, get to NoModRef as bottom). The implementation is based on having either Mod or Ref and masking out everything else. <o:p></o:p></p></div><div><p class=MsoNormal>Introducing a Must bit, means setting it occasionally (since May is conservative) and then preserving it, so the opposite: start lattice at bottom, set to top.<o:p></o:p></p></div><div><p class=MsoNormal><o:p> </o:p></p></div><p class=MsoNormal>What I was trying, that *somewhat* made sense:<br>enum ModRefInfo {<br> MRI_NoModRef = 0,<br> MRI_Ref = 1,<br> MRI_Mod = 2,<br> MRI_ModRef = MRI_Ref | MRI_Mod,<br> MRI_Must = 4,<o:p></o:p></p></div><div><p class=MsoNormal> MRI_MustRef = MRI_Ref | MRI_Must,<o:p></o:p></p></div><div><p class=MsoNormal> MRI_MustMod = MRI_Mod | MRI_Must,<o:p></o:p></p></div><div><p class=MsoNormal> MRI_MustModRef = MRI_ModRef | MRI_Must<br>};<o:p></o:p></p></div><p class=MsoNormal>// + shift values in FunctionModRefLocation to 8, 16, 32.<o:p></o:p></p></div><div><p class=MsoNormal><o:p> </o:p></p></div><div><p class=MsoNormal>Recursive masking of MRI_Ref/MRI_Mod would get replaced by MRI_MustRef/MRI_MustMod.<o:p></o:p></p></div><div><p class=MsoNormal>But the top of the lattice is still MRI_ModRef.<o:p></o:p></p></div><div><p class=MsoNormal>While the implementation details *may* be ok to resolve, there are calls checking for equality to MRI_Ref or MRI_Mod (not &), so adding the occasional Must bit seems bad.<o:p></o:p></p></div></div></blockquote><p class=MsoNormal><o:p> </o:p></p></div></div><p class=MsoNormal>I don't see this as a major problem. Please feel free to fix these places by replacing the equality checks with mask checks.<o:p></o:p></p></div></blockquote><div><p class=MsoNormal><o:p> </o:p></p></div></div></div><div><p class=MsoNormal>Ok, thank you!<o:p></o:p></p></div><blockquote style='border:none;border-left:solid #CCCCCC 1.0pt;padding:0cm 0cm 0cm 6.0pt;margin-left:4.8pt;margin-right:0cm'><div><p class=MsoNormal><span style='color:#888888'><br><br><span class=m-5619189094996677201hoenzb> -Hal</span></span><br><br><br><o:p></o:p></p><blockquote style='margin-top:5.0pt;margin-bottom:5.0pt'><div><div><p class=MsoNormal>So I guess my question is, what's the right approach here? I feel like I'm not on the right path.<o:p></o:p></p></div><div><div><p class=MsoNormal><o:p> </o:p></p></div><div><blockquote style='border:none;border-left:solid #CCCCCC 1.0pt;padding:0cm 0cm 0cm 6.0pt;margin-left:4.8pt;margin-right:0cm'><div><div><div><div><p class=MsoNormal><o:p> </o:p></p></div><blockquote style='border:none;border-left:solid #CCCCCC 1.0pt;padding:0cm 0cm 0cm 6.0pt;margin-left:4.8pt;margin-right:0cm'><div><p class=MsoNormal>In getModRefInfo(CS, Loc), the MRI_Must bit would then be set if doesAccessArgPointees and ArgAlias == MustAlias for all Args, which seems correct.<o:p></o:p></p></div></blockquote><div><p class=MsoNormal><o:p> </o:p></p></div><div><p class=MsoNormal><o:p> </o:p></p></div><div><p class=MsoNormal>alias == MustAlias for Loc, not for all args.<o:p></o:p></p></div><div><p class=MsoNormal>(IE It it returns a singular result about Loc, not a result about all args)<o:p></o:p></p></div><div><p class=MsoNormal><o:p> </o:p></p></div><div><p class=MsoNormal>To get the set answer for all args, we'd have to query further.<o:p></o:p></p></div></div></div></div></blockquote><div><p class=MsoNormal><o:p> </o:p></p></div><div><p class=MsoNormal>Yes, that's what I meant. In getModRefInfo(CS, Loc) there is a loop over all args, it checks alias() for each one.<o:p></o:p></p></div></div><p class=MsoNormal><o:p> </o:p></p></div></div></blockquote><p class=MsoNormal><br><br><o:p></o:p></p><pre>-- <o:p></o:p></pre><pre>Hal Finkel<o:p></o:p></pre><pre>Lead, Compiler Technology and Programming Languages<o:p></o:p></pre><pre>Leadership Computing Facility<o:p></o:p></pre><pre>Argonne National Laboratory<o:p></o:p></pre></div></blockquote></div><p class=MsoNormal><o:p> </o:p></p></div></div></blockquote></div><p class=MsoNormal><o:p> </o:p></p></div></div></body></html>