<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">On Sat, Sep 23, 2017 at 9:55 AM, Godala, Bhargav-reddy <span dir="ltr"><<a href="mailto:Bhargav-reddy.Godala@amd.com" target="_blank">Bhargav-reddy.Godala@amd.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">



<div style="word-wrap:break-word"><span class="gmail-">
<br>
<div>
<div style="color:rgb(0,0,0);font-family:Helvetica;font-size:12px;font-style:normal;font-variant-caps:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px">
With regards<br>
Bhargav Reddy Godala<br>
Software Engineer 2<br>
Bangalore, India<br>
E-mail: <a href="mailto:Bhargav-reddy.Godala@amd.com" target="_blank">Bhargav-reddy.Godala@<wbr>amd.com</a> Ext 30678</div>
<div style="color:rgb(0,0,0);font-family:Helvetica;font-size:12px;font-style:normal;font-variant-caps:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px">
<br>
</div>
<br class="gmail-m_-7518378742009748960Apple-interchange-newline">
</div>
<br>
</span><div><span class="gmail-">
<blockquote type="cite">
<div>On 23-Sep-2017, at 9:27 PM, Daniel Berlin <<a href="mailto:dberlin@dberlin.org" target="_blank">dberlin@dberlin.org</a>> wrote:</div>
<br class="gmail-m_-7518378742009748960Apple-interchange-newline">
<div>
<div dir="ltr"><br>
<div class="gmail_extra"><br>
<div class="gmail_quote">On Sat, Sep 23, 2017 at 8:38 AM, Godala, Bhargav-reddy via llvm-dev
<span dir="ltr"><<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
<div style="word-wrap:break-word">Hi,
<div><br>
</div>
<div>Can some one explain the intended behaviour of following loop in void MemorySSAUpdater::insertDef(Me<wbr>moryDef *MD, bool RenameUses) function.</div>
<div><br>
</div>
<div>
<div><font face="Menlo">  while (!FixupList.empty()) {</font></div>
<div><font face="Menlo">    unsigned StartingPHISize = InsertedPHIs.size();</font></div>
<div><font face="Menlo">    fixupDefs(FixupList);</font></div>
<div><font face="Menlo">    FixupList.clear();</font></div>
<div><font face="Menlo">    // Put any new phis on the fixup list, and process them</font></div>
<div><font face="Menlo">    FixupList.append(InsertedPHIs.<wbr>end() - StartingPHISize, InsertedPHIs.end());</font></div>
<div><font face="Menlo">  }</font></div>
<div><br>
</div>
<div>With the latest code on trunk compilation of perlbench SPEC CPU 2017 INT benchmark with “-O3 -inline-threshold=1000 and -enable-gvn-hoist” options is looping infinitely on the above loop.</div>
</div>
</div>
</blockquote>
<div><br>
</div>
<div> <br>
</div>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
<div style="word-wrap:break-word">
<div>
<div><br>
</div>
<div>Above loop never terminates unless elements from InsertedPHIs are removed as and when they are processed.</div>
</div>
</div>
</blockquote>
<div><br>
</div>
<div>Yes, the loop is slightly off.</div>
</div>
</div>
</div>
</div>
</blockquote>
<blockquote type="cite">
<div>
<div dir="ltr">
<div class="gmail_extra">
<div class="gmail_quote">
<div><br>
</div>
<div>The intention is to process any new phis added by fixupdefs.</div>
<div>However, it really should be InsertedPHIs.start() + StartingPHISize.</div>
</div>
</div>
</div>
</div>
</blockquote>
<div><br>
</div></span>
Even in that case it still is infinite, as there is no call to clear already processed elements(MemoryPhi) in InsertedPHIs. fixupDefs function only inserts new elements but not remove any that are processed.</div></div></blockquote><div><br></div><div>It is not iterating over inserted phis, it is iterating over the phis added by fixupdefs. </div><div><br></div><div>Thus, it does not matter whether things are removed from insertedphis, and it definitely is not infinite in that case.</div><div>1. insertedphis represents the set of  phis inserted during updating for a given def/use. It should never be cleared until a new insertuse/insertdef call happens.<br></div><div>You can see it is cleared at the beginning of each insertuse/insertdef.</div><div><br></div><div>2. Prior to this loop, insertedphis will contain the initial set of phis required by a  new def insertion.  This in turn may require new phis.  That is what this loop does. It fixes up the defs that inserting a new phi requires, and iteratively processes any new phis that process  creates.</div><div><br></div><div>The number of phis you must have to inserted is bounded by the number of basic blocks.  At worst, you will insert a single phi at every merge point.  This is a finite number.  So the number of phis the loop must go through is finite.</div><div><br></div><div>So let's go through the loop itself.<br></div><div><br></div><div>At the beginning, the fixup list will contain a single def.</div><div>Let's look at a fixed version of the loop:</div><div><div><br></div><div>  while (!FixupList.empty()) {</div><div>    unsigned StartingPHISize = InsertedPHIs.size();</div><div>    fixupDefs(FixupList);</div><div>    FixupList.clear();</div><div>    // Put any new phis on the fixup list, and process them</div><div>    FixupList.append(InsertedPHIs.begin() + StartingPHISize, InsertedPHIs.end());</div><div>  }</div></div><div><br></div><div><br></div><div>Fixup list contains 1 def. </div><div>Let's say Insertedphis looks like this { A, B }</div><div>StartingPHISize = 2</div><div>we fix up the def, which may create new phis</div><div>Let's say insertedphis now looks like this {A, B, C, D}</div><div>We clear the fixuplist</div><div>We now append only the new phis to the fixup list.  That is, those that come *after* StartingPHISize in the list.</div><div>Fixuplist will now contain {C, D}</div><div>Iteration 1 ends</div><div><br></div><div>Iteration 2:</div><div>Fixup list is {C, D}<br>Insertedphis looks like {A, B, C, D }</div><div>StartingPHISize = 4</div><div>we fixup these defs.  Assume it creates a new phi</div><div><div>Insertedphis looks like {A, B, C, D, E }</div></div><div>We clear the fixup list.</div><div>We now append only the new phis to the fixup list.</div><div>FIxuplist will now contain {E}</div><div>Iteration 2 ends</div><div><br></div><div>Fixup list is {E}</div><div><div>Insertedphis looks like {A, B, C, D, E }</div></div><div>StartingPHISize = 5</div><div>we fixup these defs. Assume it creates no new phis</div><div><div>Insertedphis looks like {A, B, C, D, E }</div></div><div><div>We clear the fixup list.</div></div><div>InsertedPHIs.begin() + StartingPHISize == InsertedPHIs.end(), so we add nothing</div><div>The fixuplist is empty, so the loop ends. </div><div><br></div><div>We are guaranteed insertedphis can only grow to the number of basic blocks.</div><div>Once it contains a phi for every basic block, the loop must terminate, because no new phis can be added.</div><div><br></div><div>The only way the loop can be finite is if we add phis where phis already exist, as MemorySSA is a single phi per block form,.</div><div>That would be a bug if that occurs.</div><div><br></div><div>Otherwise, the loop must terminate when a phi is in every block other than start.</div><div><br></div><div><br></div><div><br></div></div><br></div></div>