<html><head><meta http-equiv="Content-Type" content="text/html charset=utf-8"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class="">Thanks, It works!!<div class=""><div class=""><br class=""></div><div class=""><div class=""><div><blockquote type="cite" class=""><div class="">On 26-Sep-2017, at 3:42 AM, Daniel Berlin via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org" class="">llvm-dev@lists.llvm.org</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><div dir="ltr" class="">We should only add phis that were newly inserted, not ones that were already found. There are two cases we will hvae inserted phis:<div class=""><br class=""></div><div class="">Part of the recursive call, or right in this function.</div><div class="">The easiest way to differentiate new phis from old ones is whether they have 0 operands.</div><div class="">I expect the attached will fix it.</div><div class="">If not, please file a bug with reproducible IR.</div><div class=""><br class=""></div></div><div class="gmail_extra"><br class=""><div class="gmail_quote">On Sun, Sep 24, 2017 at 11:40 PM, Godala, Bhargav-reddy <span dir="ltr" class=""><<a href="mailto:Bhargav-reddy.Godala@amd.com" target="_blank" class="">Bhargav-reddy.Godala@amd.com</a>></span> wrote:<br class=""><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div lang="EN-US" link="blue" vlink="purple" class="">
<div class="m_-8138000392476004278WordSection1"><p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d" class="">I understand that changing the starting element to “</span><span style="font-family:"Menlo",serif" class="">InsertedPHIs.being() + StartingPHISize</span><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d" class="">”
it will be finite but given that InsrtedPHIs is finite. <u class=""></u><u class=""></u></span></p><p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d" class=""><u class=""></u> <u class=""></u></span></p><p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d" class="">I have a case where one element(same element is appened to InsertedPHIs) is added to InsertedPHIs every time fixupDefs is invoked. I traced the issue why this
was happening.<u class=""></u><u class=""></u></span></p><p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d" class=""><u class=""></u> <u class=""></u></span></p><p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d" class="">template <class RangeType><u class=""></u><u class=""></u></span></p><p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d" class="">MemoryAccess *MemorySSAUpdater::<wbr class="">tryRemoveTrivialPhi(MemoryPhi *Phi,<u class=""></u><u class=""></u></span></p><p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d" class=""> <wbr class=""> RangeType &Operands) {<u class=""></u><u class=""></u></span></p><p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d" class=""> // Detect equal or self arguments<u class=""></u><u class=""></u></span></p><p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d" class=""> MemoryAccess *Same = nullptr;<u class=""></u><u class=""></u></span></p><p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d" class=""> for (auto &Op : Operands) {<u class=""></u><u class=""></u></span></p><p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d" class=""> // If the same or self, good so far<u class=""></u><u class=""></u></span></p><p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d" class=""> if (Op == Phi || Op == Same)<u class=""></u><u class=""></u></span></p><p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d" class=""> continue;<u class=""></u><u class=""></u></span></p><p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d" class=""> // not the same, return the phi since it's not eliminatable by us<u class=""></u><u class=""></u></span></p><p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d" class=""> if (Same)<u class=""></u><u class=""></u></span></p><p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d" class=""> return Phi;<u class=""></u><u class=""></u></span></p><p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d" class=""> Same = cast<MemoryAccess>(Op);<u class=""></u><u class=""></u></span></p><p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d" class=""> }<u class=""></u><u class=""></u></span></p><p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d" class=""> // Never found a non-self reference, the phi is undef<u class=""></u><u class=""></u></span></p><p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d" class=""> if (Same == nullptr)<u class=""></u><u class=""></u></span></p><p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d" class=""> return MSSA->getLiveOnEntryDef();<u class=""></u><u class=""></u></span></p><p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d" class=""> if (Phi) {<u class=""></u><u class=""></u></span></p><p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d" class=""> Phi->replaceAllUsesWith(Same);<u class=""></u><u class=""></u></span></p><p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d" class=""> removeMemoryAccess(Phi);<u class=""></u><u class=""></u></span></p><p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d" class=""> }<u class=""></u><u class=""></u></span></p><p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d" class=""><u class=""></u> <u class=""></u></span></p><p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d" class=""> // We should only end up recursing in case we replaced something, in which<u class=""></u><u class=""></u></span></p><p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d" class=""> // case, we may have made other Phis trivial.<u class=""></u><u class=""></u></span></p><p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d" class=""> return recursePhi(Same);<u class=""></u><u class=""></u></span></p><p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d" class="">}<u class=""></u><u class=""></u></span></p><p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d" class=""><u class=""></u> <u class=""></u></span></p><p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d" class="">In above function what happens when Same is not null and Phi is null. I have one particular case where it retruns non null MemoryPhi element.<u class=""></u><u class=""></u></span></p><p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d" class=""><u class=""></u> <u class=""></u></span></p><p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d" class=""> // See if we can avoid the phi by simplifying it.<u class=""></u><u class=""></u></span></p><p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d" class=""> auto *Result = tryRemoveTrivialPhi(Phi, PhiOps);<u class=""></u><u class=""></u></span></p><p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d" class=""> // If we couldn't simplify, we may have to create a phi<u class=""></u><u class=""></u></span></p><p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d" class=""> if (Result == Phi) {<u class=""></u><u class=""></u></span></p><p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d" class=""> if (!Phi)<u class=""></u><u class=""></u></span></p><p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d" class=""> Phi = MSSA->createMemoryPhi(BB);<u class=""></u><u class=""></u></span></p><p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d" class=""><u class=""></u> <u class=""></u></span></p><p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d" class=""> // These will have been filled in by the recursive read we did above.<u class=""></u><u class=""></u></span></p><p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d" class=""> if (PHIExistsButNeedsUpdate) {<u class=""></u><u class=""></u></span></p><p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d" class=""> std::copy(PhiOps.begin(), PhiOps.end(), Phi->op_begin());<u class=""></u><u class=""></u></span></p><p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d" class=""> std::copy(pred_begin(BB), pred_end(BB), Phi->block_begin());<u class=""></u><u class=""></u></span></p><p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d" class=""> } else {<u class=""></u><u class=""></u></span></p><p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d" class=""> unsigned i = 0;<u class=""></u><u class=""></u></span></p><p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d" class=""> for (auto *Pred : predecessors(BB))<u class=""></u><u class=""></u></span></p><p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d" class=""> Phi->addIncoming(PhiOps[i++], Pred);<u class=""></u><u class=""></u></span></p><p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d" class=""> }<u class=""></u><u class=""></u></span></p><p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d" class=""><u class=""></u> <u class=""></u></span></p><p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d" class=""> Result = Phi;<u class=""></u><u class=""></u></span></p><p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d" class=""> }<u class=""></u><u class=""></u></span></p><p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d" class=""> if (MemoryPhi *MP = dyn_cast<MemoryPhi>(Result))<u class=""></u><u class=""></u></span></p><p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d" class=""> InsertedPHIs.push_back(MP);<u class=""></u><u class=""></u></span></p><p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d" class=""> // Set ourselves up for the next variable by resetting visited state.<u class=""></u><u class=""></u></span></p><p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d" class=""> VisitedBlocks.erase(BB);<u class=""></u><u class=""></u></span></p><p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d" class=""> return Result;<u class=""></u><u class=""></u></span></p><p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d" class=""><u class=""></u> <u class=""></u></span></p><p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d" class="">In above code which is part of “MemoryAccess *MemorySSAUpdater::<wbr class="">getPreviousDefRecursive(<wbr class="">BasicBlock *BB)” function. If Result is non null and Phi is null then
InsertedPHIs is updated but Result is not added to the Basic Block BB.<u class=""></u><u class=""></u></span></p><p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d" class=""><u class=""></u> <u class=""></u></span></p><p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d" class="">My question is what is the intended behavior when Result is non null and Phi is null??<u class=""></u><u class=""></u></span></p><p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d" class=""><u class=""></u> <u class=""></u></span></p><p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d" class="">Below is the dump for the sample case I’m observing. It’s the state of InsertedPHIs after every invocation of fixupDefs.<u class=""></u><u class=""></u></span></p><p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d" class=""><u class=""></u> <u class=""></u></span></p><p class="MsoNormal"><span style="font-family:Monaco" class="">For reference I included, some dumps that I introduced, below:</span><u class=""></u><u class=""></u></p><p class="MsoNormal"> <u class=""></u><u class=""></u></p><p class="MsoNormal"><span style="font-family:Monaco" class="">Inserted PHIs</span><u class=""></u><u class=""></u></p><p class="MsoNormal"><span style="font-family:Monaco" class="">at 0: 470 = MemoryPhi({if.then753,274},{<wbr class="">Perl_hv_placeholders_get.exit,<wbr class="">275})</span><u class=""></u><u class=""></u></p><p class="MsoNormal"> <u class=""></u><u class=""></u></p><p class="MsoNormal"><span style="font-family:Monaco" class="">Inserted PHIs</span><u class=""></u><u class=""></u></p><p class="MsoNormal"><span style="font-family:Monaco" class="">at 0: 470 = MemoryPhi({if.then753,274},{<wbr class="">Perl_hv_placeholders_get.exit,<wbr class="">275})</span><u class=""></u><u class=""></u></p><p class="MsoNormal"> <u class=""></u><u class=""></u></p><p class="MsoNormal"><span style="font-family:Monaco" class="">at 1: 470 = MemoryPhi({if.then753,274},{<wbr class="">Perl_hv_placeholders_get.exit,<wbr class="">275})</span><u class=""></u><u class=""></u></p><p class="MsoNormal"> <u class=""></u><u class=""></u></p><p class="MsoNormal"><span style="font-family:Monaco" class="">Inserted PHIs</span><u class=""></u><u class=""></u></p><p class="MsoNormal"><span style="font-family:Monaco" class="">at 0: 470 = MemoryPhi({if.then753,274},{<wbr class="">Perl_hv_placeholders_get.exit,<wbr class="">275})</span><u class=""></u><u class=""></u></p><p class="MsoNormal"> <u class=""></u><u class=""></u></p><p class="MsoNormal"><span style="font-family:Monaco" class="">at 1: 470 = MemoryPhi({if.then753,274},{<wbr class="">Perl_hv_placeholders_get.exit,<wbr class="">275})</span><u class=""></u><u class=""></u></p><p class="MsoNormal"> <u class=""></u><u class=""></u></p><p class="MsoNormal"><span style="font-family:Monaco" class="">at 2: 470 = MemoryPhi({if.then753,274},{<wbr class="">Perl_hv_placeholders_get.exit,<wbr class="">275})</span><u class=""></u><u class=""></u></p><p class="MsoNormal"> <u class=""></u><u class=""></u></p><p class="MsoNormal"><span style="font-family:Monaco" class="">Inserted PHIs</span><u class=""></u><u class=""></u></p><p class="MsoNormal"><span style="font-family:Monaco" class="">at 0: 470 = MemoryPhi({if.then753,274},{<wbr class="">Perl_hv_placeholders_get.exit,<wbr class="">275})</span><u class=""></u><u class=""></u></p><p class="MsoNormal"> <u class=""></u><u class=""></u></p><p class="MsoNormal"><span style="font-family:Monaco" class="">at 1: 470 = MemoryPhi({if.then753,274},{<wbr class="">Perl_hv_placeholders_get.exit,<wbr class="">275})</span><u class=""></u><u class=""></u></p><p class="MsoNormal"> <u class=""></u><u class=""></u></p><p class="MsoNormal"><span style="font-family:Monaco" class="">at 2: 470 = MemoryPhi({if.then753,274},{<wbr class="">Perl_hv_placeholders_get.exit,<wbr class="">275})</span><u class=""></u><u class=""></u></p><p class="MsoNormal"> <u class=""></u><u class=""></u></p><p class="MsoNormal"><span style="font-family:Monaco" class="">at 3: 470 = MemoryPhi({if.then753,274},{<wbr class="">Perl_hv_placeholders_get.exit,<wbr class="">275})</span><span style="font-size:9.0pt;font-family:"Helvetica",sans-serif" class=""><br class="">
<br class="">
</span><u class=""></u><u class=""></u></p><p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d" class=""><u class=""></u> <u class=""></u></span></p><p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d" class=""><u class=""></u> <u class=""></u></span></p><p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d" class=""><u class=""></u> <u class=""></u></span></p><p class="MsoNormal"><b class=""><span style="font-size:11.0pt;font-family:"Calibri",sans-serif" class="">From:</span></b><span style="font-size:11.0pt;font-family:"Calibri",sans-serif" class=""> Daniel Berlin [mailto:<a href="mailto:dberlin@dberlin.org" target="_blank" class="">dberlin@dberlin.org</a>]
<br class="">
<b class="">Sent:</b> Saturday, September 23, 2017 10:42 PM<br class="">
<b class="">To:</b> Godala, Bhargav-reddy <<a href="mailto:Bhargav-reddy.Godala@amd.com" target="_blank" class="">Bhargav-reddy.Godala@amd.com</a>><br class="">
<b class="">Cc:</b> <a href="mailto:llvm-dev@lists.llvm.org" target="_blank" class="">llvm-dev@lists.llvm.org</a><br class="">
<b class="">Subject:</b> Re: [llvm-dev] Potential infinite loop in MemorySSAUpdater<u class=""></u><u class=""></u></span></p><div class=""><div class="h5"><p class="MsoNormal"><u class=""></u> <u class=""></u></p>
<div class=""><p class="MsoNormal"><u class=""></u> <u class=""></u></p>
<div class=""><p class="MsoNormal"><u class=""></u> <u class=""></u></p>
<div class=""><p class="MsoNormal">On Sat, Sep 23, 2017 at 9:55 AM, Godala, Bhargav-reddy <<a href="mailto:Bhargav-reddy.Godala@amd.com" target="_blank" class="">Bhargav-reddy.Godala@amd.com</a>> wrote:<u class=""></u><u class=""></u></p>
<blockquote style="border:none;border-left:solid #cccccc 1.0pt;padding:0in 0in 0in 6.0pt;margin-left:4.8pt;margin-right:0in" class="">
<div class=""><p class="MsoNormal"><span class="m_-8138000392476004278gmail-"><u class=""></u> <u class=""></u></span></p>
<div class="">
<div class=""><p class="MsoNormal"><span style="font-size: 9pt; font-family: Helvetica, sans-serif;" class="">With regards<br class="">
Bhargav Reddy Godala<br class="">
Software Engineer 2<br class="">
Bangalore, India<br class="">
E-mail: <a href="mailto:Bhargav-reddy.Godala@amd.com" target="_blank" class="">Bhargav-reddy.Godala@<wbr class="">amd.com</a> Ext 30678<u class=""></u><u class=""></u></span></p>
</div>
<div class=""><p class="MsoNormal"><span style="font-size: 9pt; font-family: Helvetica, sans-serif;" class=""><u class=""></u> <u class=""></u></span></p>
</div><p class="MsoNormal"><u class=""></u> <u class=""></u></p>
</div><p class="MsoNormal"><u class=""></u> <u class=""></u></p>
<div class="">
<blockquote style="margin-top:5.0pt;margin-bottom:5.0pt" class="">
<div class=""><p class="MsoNormal">On 23-Sep-2017, at 9:27 PM, Daniel Berlin <<a href="mailto:dberlin@dberlin.org" target="_blank" class="">dberlin@dberlin.org</a>> wrote:<u class=""></u><u class=""></u></p>
</div><p class="MsoNormal"><u class=""></u> <u class=""></u></p>
<div class="">
<div class=""><p class="MsoNormal"><u class=""></u> <u class=""></u></p>
<div class=""><p class="MsoNormal"><u class=""></u> <u class=""></u></p>
<div class=""><p class="MsoNormal">On Sat, Sep 23, 2017 at 8:38 AM, Godala, Bhargav-reddy via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org" target="_blank" class="">llvm-dev@lists.llvm.org</a>> wrote:<u class=""></u><u class=""></u></p>
<blockquote style="border:none;border-left:solid #cccccc 1.0pt;padding:0in 0in 0in 6.0pt;margin-left:4.8pt;margin-right:0in" class="">
<div class=""><p class="MsoNormal">Hi, <u class=""></u><u class=""></u></p>
<div class=""><p class="MsoNormal"><u class=""></u> <u class=""></u></p>
</div>
<div class=""><p class="MsoNormal">Can some one explain the intended behaviour of following loop in void MemorySSAUpdater::insertDef(<wbr class="">MemoryDef *MD, bool RenameUses) function.<u class=""></u><u class=""></u></p>
</div>
<div class=""><p class="MsoNormal"><u class=""></u> <u class=""></u></p>
</div>
<div class="">
<div class=""><p class="MsoNormal"><span style="font-family:"Menlo",serif" class=""> while (!FixupList.empty()) {</span><u class=""></u><u class=""></u></p>
</div>
<div class=""><p class="MsoNormal"><span style="font-family:"Menlo",serif" class=""> unsigned StartingPHISize = InsertedPHIs.size();</span><u class=""></u><u class=""></u></p>
</div>
<div class=""><p class="MsoNormal"><span style="font-family:"Menlo",serif" class=""> fixupDefs(FixupList);</span><u class=""></u><u class=""></u></p>
</div>
<div class=""><p class="MsoNormal"><span style="font-family:"Menlo",serif" class=""> FixupList.clear();</span><u class=""></u><u class=""></u></p>
</div>
<div class=""><p class="MsoNormal"><span style="font-family:"Menlo",serif" class=""> // Put any new phis on the fixup list, and process them</span><u class=""></u><u class=""></u></p>
</div>
<div class=""><p class="MsoNormal"><span style="font-family:"Menlo",serif" class=""> FixupList.append(InsertedPHIs.<wbr class="">end() - StartingPHISize, InsertedPHIs.end());</span><u class=""></u><u class=""></u></p>
</div>
<div class=""><p class="MsoNormal"><span style="font-family:"Menlo",serif" class=""> }</span><u class=""></u><u class=""></u></p>
</div>
<div class=""><p class="MsoNormal"><u class=""></u> <u class=""></u></p>
</div>
<div class=""><p class="MsoNormal">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.<u class=""></u><u class=""></u></p>
</div>
</div>
</div>
</blockquote>
<div class=""><p class="MsoNormal"><u class=""></u> <u class=""></u></p>
</div>
<div class=""><p class="MsoNormal"> <u class=""></u><u class=""></u></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" class="">
<div class="">
<div class="">
<div class=""><p class="MsoNormal"><u class=""></u> <u class=""></u></p>
</div>
<div class=""><p class="MsoNormal">Above loop never terminates unless elements from InsertedPHIs are removed as and when they are processed.<u class=""></u><u class=""></u></p>
</div>
</div>
</div>
</blockquote>
<div class=""><p class="MsoNormal"><u class=""></u> <u class=""></u></p>
</div>
<div class=""><p class="MsoNormal">Yes, the loop is slightly off.<u class=""></u><u class=""></u></p>
</div>
</div>
</div>
</div>
</div>
</blockquote>
<blockquote style="margin-top:5.0pt;margin-bottom:5.0pt" class="">
<div class="">
<div class="">
<div class="">
<div class="">
<div class=""><p class="MsoNormal"><u class=""></u> <u class=""></u></p>
</div>
<div class=""><p class="MsoNormal">The intention is to process any new phis added by fixupdefs.<u class=""></u><u class=""></u></p>
</div>
<div class=""><p class="MsoNormal">However, it really should be InsertedPHIs.start() + StartingPHISize.<u class=""></u><u class=""></u></p>
</div>
</div>
</div>
</div>
</div>
</blockquote>
<div class=""><p class="MsoNormal"><u class=""></u> <u class=""></u></p>
</div><p class="MsoNormal">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.<u class=""></u><u class=""></u></p>
</div>
</div>
</blockquote>
<div class=""><p class="MsoNormal"><u class=""></u> <u class=""></u></p>
</div>
<div class=""><p class="MsoNormal">It is not iterating over inserted phis, it is iterating over the phis added by fixupdefs. <u class=""></u><u class=""></u></p>
</div>
<div class=""><p class="MsoNormal"><u class=""></u> <u class=""></u></p>
</div>
<div class=""><p class="MsoNormal">Thus, it does not matter whether things are removed from insertedphis, and it definitely is not infinite in that case.<u class=""></u><u class=""></u></p>
</div>
<div class=""><p class="MsoNormal">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.<u class=""></u><u class=""></u></p>
</div>
<div class=""><p class="MsoNormal">You can see it is cleared at the beginning of each insertuse/insertdef.<u class=""></u><u class=""></u></p>
</div>
<div class=""><p class="MsoNormal"><u class=""></u> <u class=""></u></p>
</div>
<div class=""><p class="MsoNormal">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.<u class=""></u><u class=""></u></p>
</div>
<div class=""><p class="MsoNormal"><u class=""></u> <u class=""></u></p>
</div>
<div class=""><p class="MsoNormal">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.<u class=""></u><u class=""></u></p>
</div>
<div class=""><p class="MsoNormal"><u class=""></u> <u class=""></u></p>
</div>
<div class=""><p class="MsoNormal">So let's go through the loop itself.<u class=""></u><u class=""></u></p>
</div>
<div class=""><p class="MsoNormal"><u class=""></u> <u class=""></u></p>
</div>
<div class=""><p class="MsoNormal">At the beginning, the fixup list will contain a single def.<u class=""></u><u class=""></u></p>
</div>
<div class=""><p class="MsoNormal">Let's look at a fixed version of the loop:<u class=""></u><u class=""></u></p>
</div>
<div class="">
<div class=""><p class="MsoNormal"><u class=""></u> <u class=""></u></p>
</div>
<div class=""><p class="MsoNormal"> while (!FixupList.empty()) {<u class=""></u><u class=""></u></p>
</div>
<div class=""><p class="MsoNormal"> unsigned StartingPHISize = InsertedPHIs.size();<u class=""></u><u class=""></u></p>
</div>
<div class=""><p class="MsoNormal"> fixupDefs(FixupList);<u class=""></u><u class=""></u></p>
</div>
<div class=""><p class="MsoNormal"> FixupList.clear();<u class=""></u><u class=""></u></p>
</div>
<div class=""><p class="MsoNormal"> // Put any new phis on the fixup list, and process them<u class=""></u><u class=""></u></p>
</div>
<div class=""><p class="MsoNormal"> FixupList.append(InsertedPHIs.<wbr class="">begin() + StartingPHISize, InsertedPHIs.end());<u class=""></u><u class=""></u></p>
</div>
<div class=""><p class="MsoNormal"> }<u class=""></u><u class=""></u></p>
</div>
</div>
<div class=""><p class="MsoNormal"><u class=""></u> <u class=""></u></p>
</div>
<div class=""><p class="MsoNormal"><u class=""></u> <u class=""></u></p>
</div>
<div class=""><p class="MsoNormal">Fixup list contains 1 def. <u class=""></u><u class=""></u></p>
</div>
<div class=""><p class="MsoNormal">Let's say Insertedphis looks like this { A, B }<u class=""></u><u class=""></u></p>
</div>
<div class=""><p class="MsoNormal">StartingPHISize = 2<u class=""></u><u class=""></u></p>
</div>
<div class=""><p class="MsoNormal">we fix up the def, which may create new phis<u class=""></u><u class=""></u></p>
</div>
<div class=""><p class="MsoNormal">Let's say insertedphis now looks like this {A, B, C, D}<u class=""></u><u class=""></u></p>
</div>
<div class=""><p class="MsoNormal">We clear the fixuplist<u class=""></u><u class=""></u></p>
</div>
<div class=""><p class="MsoNormal">We now append only the new phis to the fixup list. That is, those that come *after* StartingPHISize in the list.<u class=""></u><u class=""></u></p>
</div>
<div class=""><p class="MsoNormal">Fixuplist will now contain {C, D}<u class=""></u><u class=""></u></p>
</div>
<div class=""><p class="MsoNormal">Iteration 1 ends<u class=""></u><u class=""></u></p>
</div>
<div class=""><p class="MsoNormal"><u class=""></u> <u class=""></u></p>
</div>
<div class=""><p class="MsoNormal">Iteration 2:<u class=""></u><u class=""></u></p>
</div>
<div class=""><p class="MsoNormal">Fixup list is {C, D}<br class="">
Insertedphis looks like {A, B, C, D }<u class=""></u><u class=""></u></p>
</div>
<div class=""><p class="MsoNormal">StartingPHISize = 4<u class=""></u><u class=""></u></p>
</div>
<div class=""><p class="MsoNormal">we fixup these defs. Assume it creates a new phi<u class=""></u><u class=""></u></p>
</div>
<div class="">
<div class=""><p class="MsoNormal">Insertedphis looks like {A, B, C, D, E }<u class=""></u><u class=""></u></p>
</div>
</div>
<div class=""><p class="MsoNormal">We clear the fixup list.<u class=""></u><u class=""></u></p>
</div>
<div class=""><p class="MsoNormal">We now append only the new phis to the fixup list.<u class=""></u><u class=""></u></p>
</div>
<div class=""><p class="MsoNormal">FIxuplist will now contain {E}<u class=""></u><u class=""></u></p>
</div>
<div class=""><p class="MsoNormal">Iteration 2 ends<u class=""></u><u class=""></u></p>
</div>
<div class=""><p class="MsoNormal"><u class=""></u> <u class=""></u></p>
</div>
<div class=""><p class="MsoNormal">Fixup list is {E}<u class=""></u><u class=""></u></p>
</div>
<div class="">
<div class=""><p class="MsoNormal">Insertedphis looks like {A, B, C, D, E }<u class=""></u><u class=""></u></p>
</div>
</div>
<div class=""><p class="MsoNormal">StartingPHISize = 5<u class=""></u><u class=""></u></p>
</div>
<div class=""><p class="MsoNormal">we fixup these defs. Assume it creates no new phis<u class=""></u><u class=""></u></p>
</div>
<div class="">
<div class=""><p class="MsoNormal">Insertedphis looks like {A, B, C, D, E }<u class=""></u><u class=""></u></p>
</div>
</div>
<div class="">
<div class=""><p class="MsoNormal">We clear the fixup list.<u class=""></u><u class=""></u></p>
</div>
</div>
<div class=""><p class="MsoNormal">InsertedPHIs.begin() + StartingPHISize == InsertedPHIs.end(), so we add nothing<u class=""></u><u class=""></u></p>
</div>
<div class=""><p class="MsoNormal">The fixuplist is empty, so the loop ends. <u class=""></u><u class=""></u></p>
</div>
<div class=""><p class="MsoNormal"><u class=""></u> <u class=""></u></p>
</div>
<div class=""><p class="MsoNormal">We are guaranteed insertedphis can only grow to the number of basic blocks.<u class=""></u><u class=""></u></p>
</div>
<div class=""><p class="MsoNormal">Once it contains a phi for every basic block, the loop must terminate, because no new phis can be added.<u class=""></u><u class=""></u></p>
</div>
<div class=""><p class="MsoNormal"><u class=""></u> <u class=""></u></p>
</div>
<div class=""><p class="MsoNormal">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,.<u class=""></u><u class=""></u></p>
</div>
<div class=""><p class="MsoNormal">That would be a bug if that occurs.<u class=""></u><u class=""></u></p>
</div>
<div class=""><p class="MsoNormal"><u class=""></u> <u class=""></u></p>
</div>
<div class=""><p class="MsoNormal">Otherwise, the loop must terminate when a phi is in every block other than start.<u class=""></u><u class=""></u></p>
</div>
<div class=""><p class="MsoNormal"><u class=""></u> <u class=""></u></p>
</div>
<div class=""><p class="MsoNormal"><u class=""></u> <u class=""></u></p>
</div>
<div class=""><p class="MsoNormal"><u class=""></u> <u class=""></u></p>
</div>
</div><p class="MsoNormal"><u class=""></u> <u class=""></u></p>
</div>
</div>
</div></div></div>
</div>
</blockquote></div><br class=""></div>
<span id="cid:7FCC526A-98CA-4A36-A201-050BF9DF66E6@amd.com"><fixmemssaupdater.diff></span>_______________________________________________<br class="">LLVM Developers mailing list<br class=""><a href="mailto:llvm-dev@lists.llvm.org" class="">llvm-dev@lists.llvm.org</a><br class="">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev<br class=""></div></blockquote></div><br class=""></div></div></div></body></html>