<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)"><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:0in;
margin-bottom:.0001pt;
font-size:12.0pt;
font-family:"Times New Roman",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
{mso-style-priority:99;
mso-margin-top-alt:auto;
margin-right:0in;
mso-margin-bottom-alt:auto;
margin-left:0in;
font-size:12.0pt;
font-family:"Times New Roman",serif;}
p.MsoListParagraph, li.MsoListParagraph, div.MsoListParagraph
{mso-style-priority:34;
margin-top:0in;
margin-right:0in;
margin-bottom:0in;
margin-left:.5in;
margin-bottom:.0001pt;
font-size:12.0pt;
font-family:"Times New Roman",serif;}
span.EmailStyle18
{mso-style-type:personal-reply;
font-family:"Calibri",sans-serif;
color:#1F497D;}
.MsoChpDefault
{mso-style-type:export-only;
font-family:"Calibri",sans-serif;}
@page WordSection1
{size:8.5in 11.0in;
margin:1.0in 1.0in 1.0in 1.0in;}
div.WordSection1
{page:WordSection1;}
/* List Definitions */
@list l0
{mso-list-id:920218656;
mso-list-type:hybrid;
mso-list-template-ids:2135072268 67698705 67698713 67698715 67698703 67698713 67698715 67698703 67698713 67698715;}
@list l0:level1
{mso-level-text:"%1\)";
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;}
@list l0:level2
{mso-level-number-format:alpha-lower;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;}
@list l0:level3
{mso-level-number-format:roman-lower;
mso-level-tab-stop:none;
mso-level-number-position:right;
text-indent:-9.0pt;}
@list l0:level4
{mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;}
@list l0:level5
{mso-level-number-format:alpha-lower;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;}
@list l0:level6
{mso-level-number-format:roman-lower;
mso-level-tab-stop:none;
mso-level-number-position:right;
text-indent:-9.0pt;}
@list l0:level7
{mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;}
@list l0:level8
{mso-level-number-format:alpha-lower;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;}
@list l0:level9
{mso-level-number-format:roman-lower;
mso-level-tab-stop:none;
mso-level-number-position:right;
text-indent:-9.0pt;}
ol
{margin-bottom:0in;}
ul
{margin-bottom:0in;}
--></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><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'>Hi Daniel,<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'><o:p> </o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'>Thanks for the info. I’ve started looking into converting EarlyCSE to use MemorySSA first since 1) I don’t think it needs any additional MemorySSA update API and 2) the particular case I’m looking at needs EarlyCSE to catch more load cases before LICM to be profitable.<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'>I have a prototype working, but have run into two issues:<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'><o:p> </o:p></span></p><p class=MsoListParagraph style='text-indent:-.25in;mso-list:l0 level1 lfo1'><![if !supportLists]><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'><span style='mso-list:Ignore'>1)<span style='font:7.0pt "Times New Roman"'> </span></span></span><![endif]><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'>readonly calls are treated as clobbers by MemorySSA which leads to extra walking of MemoryDefs to not regress some EarlyCSE test cases. This isn’t a huge deal, I’m just wondering if it is intentional or something that just hasn’t been gotten to yet.<o:p></o:p></span></p><p class=MsoListParagraph style='text-indent:-.25in;mso-list:l0 level1 lfo1'><![if !supportLists]><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'><span style='mso-list:Ignore'>2)<span style='font:7.0pt "Times New Roman"'> </span></span></span><![endif]><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'>There seems to be a bug in the CachingMemorySSAWalker invalidation causing it to return MemoryAccess nodes that have been removed. In the case I’m seeing, a call node is removed from MemorySSA which causes CachingMemorySSAWalker::invalidateInfo() to clear the CachedUpwardsClobberingCall map. However, this same call node is present as a value in the CachedUpwardsClobberingAccess map, so when a later query is made with the load whose immediate def used to be the call, the removed call node is returned. The simple fix below resolves the issue, but may be too big of a hammer?<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'><o:p> </o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'>@@ -802,17 +836,8 @@ void CachingMemorySSAWalker::invalidateInfo(MemoryAccess *MA) {<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'> doCacheRemove(MA, Q, Q.StartingLoc);<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'> return;<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'> }<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'>- // If it is not a use, the best we can do right now is destroy the cache.<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'>- bool IsCall = false;<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'>-<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'>- if (auto *MUD = dyn_cast<MemoryUseOrDef>(MA)) {<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'>- Instruction *I = MUD->getMemoryInst();<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'>- IsCall = bool(ImmutableCallSite(I));<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'>- }<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'>- if (IsCall)<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'>- CachedUpwardsClobberingCall.clear();<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'>- else<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'>- CachedUpwardsClobberingAccess.clear();<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'>+ CachedUpwardsClobberingCall.clear();<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'>+ CachedUpwardsClobberingAccess.clear();<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'> }<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'> <o:p></o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'> void CachingMemorySSAWalker::doCacheRemove(const MemoryAccess *M,<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'><o:p> </o:p></span></p><div style='mso-element:para-border-div;border:dashed #2F6FAB 1.0pt;padding:12.0pt 12.0pt 12.0pt 12.0pt;background:#F9F9F9'><p class=MsoNormal style='line-height:15.6pt;background:#F9F9F9;border:none;padding:0in'><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'>--<o:p></o:p></span></p><p class=MsoNormal style='line-height:15.6pt;background:#F9F9F9;border:none;padding:0in'><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'>Geoff Berry<o:p></o:p></span></p><p class=MsoNormal style='line-height:15.6pt;background:#F9F9F9;border:none;padding:0in'><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'>Employee of Qualcomm Innovation Center, Inc.<o:p></o:p></span></p><p class=MsoNormal style='line-height:15.6pt;background:#F9F9F9;border:none;padding:0in'><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'> Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, a Linux Foundation Collaborative Project<o:p></o:p></span></p></div><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'><o:p> </o:p></span></p><p class=MsoNormal><b><span style='font-size:11.0pt;font-family:"Calibri",sans-serif'>From:</span></b><span style='font-size:11.0pt;font-family:"Calibri",sans-serif'> Daniel Berlin [mailto:dberlin@dberlin.org] <br><b>Sent:</b> Monday, April 11, 2016 4:17 PM<br><b>To:</b> Geoff Berry <gberry@codeaurora.org><br><b>Cc:</b> llvm-dev <llvm-dev@lists.llvm.org>; Sanjoy Das <sanjoy@playingwithpointers.com>; Hal Finkel <hfinkel@anl.gov><br><b>Subject:</b> Re: [LICM][MemorySSA] Converting LICM pass to use MemorySSA to avoid AliasSet collapse issue<o:p></o:p></span></p><p class=MsoNormal><o:p> </o:p></p><div><p class=MsoNormal><o:p> </o:p></p><div><p class=MsoNormal><o:p> </o:p></p><div><p class=MsoNormal>On Mon, Apr 11, 2016 at 12:03 PM, Geoff Berry <<a href="mailto:gberry@codeaurora.org" target="_blank">gberry@codeaurora.org</a>> wrote:<o:p></o:p></p><blockquote style='border:none;border-left:solid #CCCCCC 1.0pt;padding:0in 0in 0in 6.0pt;margin-left:4.8pt;margin-right:0in'><div><div><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'>Hi All,<o:p></o:p></p><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'> <o:p></o:p></p><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'>I’m looking into converting LICM to use MemorySSA instead of AliasSets to determine when it is safe to hoist/sink/promote loads and stores to get around the issue of alias set collapse (see discussion [1]). <o:p></o:p></p></div></div></blockquote><div><p class=MsoNormal><o:p> </o:p></p></div><div><p class=MsoNormal>Thank you<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:0in 0in 0in 6.0pt;margin-left:4.8pt;margin-right:0in'><div><div><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'>I have a prototype implementation, but have run into two issues that I could use input from the designers of MemorySSA to resolve:<o:p></o:p></p><p>1)<span style='font-size:7.0pt'> </span>Is MemorySSA intended to be maintained across passes? More specifically how is it intended to interact with the Pass Manager? In my current prototype I’m just building it at the start of LICM.<o:p></o:p></p></div></div></blockquote><div><p class=MsoNormal>I am working on it, it will be preserved/destroyed like any analysis pass.<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:0in 0in 0in 6.0pt;margin-left:4.8pt;margin-right:0in'><div><div><p>2)<span style='font-size:7.0pt'> </span>What is the intended method for dealing with changes to the function that invalidate the MemorySSA form? I see that there is a way to remove nodes from the MemorySSA graph, but for other transformations (e.g. hoisting a load) am I supposed to just update the MemorySSA graph myself?<o:p></o:p></p></div></div></blockquote><div><p class=MsoNormal><o:p> </o:p></p></div><div><p class=MsoNormal>For hoisting loads, i have an API that will work abotu to be under review over here:<o:p></o:p></p></div><div><p class=MsoNormal><a href="http://reviews.llvm.org/D18090">http://reviews.llvm.org/D18090</a><o:p></o:p></p></div><div><p class=MsoNormal>a load hoist will look something like this to update:<o:p></o:p></p></div><div><div><p class=MsoNormal><o:p> </o:p></p></div><div><p class=MsoNormal> // We also hoist operands of loads using this function, so check to see if<o:p></o:p></p></div><div><p class=MsoNormal> // this is really a memory access before we try to update MemorySSA for it.<o:p></o:p></p></div><div><p class=MsoNormal> MemoryAccess *HoistCandAccess = MSSA->getMemoryAccess(HoistCand);<o:p></o:p></p></div><div><p class=MsoNormal> if (HoistCandAccess) {<o:p></o:p></p></div><div><p class=MsoNormal> MemoryUseOrDef *MUD = cast<MemoryUseOrDef>(HoistCandAccess);<o:p></o:p></p></div><div><p class=MsoNormal> // What is happening here is that we are creating the hoisted access<o:p></o:p></p></div><div><p class=MsoNormal> // and destroying the old accesses.<o:p></o:p></p></div><div><p class=MsoNormal> MSSA->createMemoryAccess(HoistedInst, MUD->getDefiningAccess(), BB,<o:p></o:p></p></div><div><p class=MsoNormal> MemorySSA::End);<o:p></o:p></p></div><div><p class=MsoNormal> MSSA->removeMemoryAccess(HoistCandAccess);<o:p></o:p></p></div><div><p class=MsoNormal> MSSA->removeMemoryAccess(MSSA->getMemoryAccess(ElseInst));<o:p></o:p></p></div><div><p class=MsoNormal> }<o:p></o:p></p></div><div><p class=MsoNormal><o:p> </o:p></p></div><div><p class=MsoNormal><o:p> </o:p></p></div><div><p class=MsoNormal>(this is "create a new access with this memorydef as it's definition, kill these two old loads").<o:p></o:p></p></div><div><p class=MsoNormal><o:p> </o:p></p></div><div><p class=MsoNormal><o:p> </o:p></p></div><div><p class=MsoNormal>A store sink is slightly harder, but it will be similar.<o:p></o:p></p></div><div><p class=MsoNormal><o:p> </o:p></p></div><div><p class=MsoNormal>Comments welcome!<o:p></o:p></p></div><div><p class=MsoNormal><o:p> </o:p></p></div><p class=MsoNormal> <o:p></o:p></p></div><blockquote style='border:none;border-left:solid #CCCCCC 1.0pt;padding:0in 0in 0in 6.0pt;margin-left:4.8pt;margin-right:0in'><div><div><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'> <o:p></o:p></p><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'> <o:p></o:p></p><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'>[1] <a href="http://lists.llvm.org/pipermail/llvm-dev/2015-April/084881.html" target="_blank">http://lists.llvm.org/pipermail/llvm-dev/2015-April/084881.html</a><o:p></o:p></p><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'> <o:p></o:p></p><div style='border:dashed #2F6FAB 1.0pt;padding:12.0pt 12.0pt 12.0pt 12.0pt'><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;line-height:15.6pt;background:#F9F9F9'>--<o:p></o:p></p><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;line-height:15.6pt;background:#F9F9F9'>Geoff Berry<o:p></o:p></p><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;line-height:15.6pt;background:#F9F9F9'>Employee of Qualcomm Innovation Center, Inc.<o:p></o:p></p><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;line-height:15.6pt;background:#F9F9F9'>Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, a Linux Foundation Collaborative Project<o:p></o:p></p></div><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'> <o:p></o:p></p></div></div></blockquote></div><p class=MsoNormal><o:p> </o:p></p></div></div></div></body></html>