[llvm-dev] Potential infinite loop in MemorySSAUpdater
Daniel Berlin via llvm-dev
llvm-dev at lists.llvm.org
Mon Sep 25 15:12:43 PDT 2017
We should only add phis that were newly inserted, not ones that were
already found. There are two cases we will hvae inserted phis:
Part of the recursive call, or right in this function.
The easiest way to differentiate new phis from old ones is whether they
have 0 operands.
I expect the attached will fix it.
If not, please file a bug with reproducible IR.
On Sun, Sep 24, 2017 at 11:40 PM, Godala, Bhargav-reddy <
Bhargav-reddy.Godala at amd.com> wrote:
> I understand that changing the starting element to “InsertedPHIs.being()
> + StartingPHISize” it will be finite but given that InsrtedPHIs is
> finite.
>
>
>
> 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.
>
>
>
> template <class RangeType>
>
> MemoryAccess *MemorySSAUpdater::tryRemoveTrivialPhi(MemoryPhi *Phi,
>
> RangeType &Operands) {
>
> // Detect equal or self arguments
>
> MemoryAccess *Same = nullptr;
>
> for (auto &Op : Operands) {
>
> // If the same or self, good so far
>
> if (Op == Phi || Op == Same)
>
> continue;
>
> // not the same, return the phi since it's not eliminatable by us
>
> if (Same)
>
> return Phi;
>
> Same = cast<MemoryAccess>(Op);
>
> }
>
> // Never found a non-self reference, the phi is undef
>
> if (Same == nullptr)
>
> return MSSA->getLiveOnEntryDef();
>
> if (Phi) {
>
> Phi->replaceAllUsesWith(Same);
>
> removeMemoryAccess(Phi);
>
> }
>
>
>
> // We should only end up recursing in case we replaced something, in
> which
>
> // case, we may have made other Phis trivial.
>
> return recursePhi(Same);
>
> }
>
>
>
> 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.
>
>
>
> // See if we can avoid the phi by simplifying it.
>
> auto *Result = tryRemoveTrivialPhi(Phi, PhiOps);
>
> // If we couldn't simplify, we may have to create a phi
>
> if (Result == Phi) {
>
> if (!Phi)
>
> Phi = MSSA->createMemoryPhi(BB);
>
>
>
> // These will have been filled in by the recursive read we did above.
>
> if (PHIExistsButNeedsUpdate) {
>
> std::copy(PhiOps.begin(), PhiOps.end(), Phi->op_begin());
>
> std::copy(pred_begin(BB), pred_end(BB), Phi->block_begin());
>
> } else {
>
> unsigned i = 0;
>
> for (auto *Pred : predecessors(BB))
>
> Phi->addIncoming(PhiOps[i++], Pred);
>
> }
>
>
>
> Result = Phi;
>
> }
>
> if (MemoryPhi *MP = dyn_cast<MemoryPhi>(Result))
>
> InsertedPHIs.push_back(MP);
>
> // Set ourselves up for the next variable by resetting visited state.
>
> VisitedBlocks.erase(BB);
>
> return Result;
>
>
>
> In above code which is part of “MemoryAccess *MemorySSAUpdater::
> getPreviousDefRecursive(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.
>
>
>
> My question is what is the intended behavior when Result is non null and
> Phi is null??
>
>
>
> Below is the dump for the sample case I’m observing. It’s the state of
> InsertedPHIs after every invocation of fixupDefs.
>
>
>
> For reference I included, some dumps that I introduced, below:
>
>
>
> Inserted PHIs
>
> at 0: 470 = MemoryPhi({if.then753,274},{Perl_hv_placeholders_get.exit,
> 275})
>
>
>
> Inserted PHIs
>
> at 0: 470 = MemoryPhi({if.then753,274},{Perl_hv_placeholders_get.exit,
> 275})
>
>
>
> at 1: 470 = MemoryPhi({if.then753,274},{Perl_hv_placeholders_get.exit,
> 275})
>
>
>
> Inserted PHIs
>
> at 0: 470 = MemoryPhi({if.then753,274},{Perl_hv_placeholders_get.exit,
> 275})
>
>
>
> at 1: 470 = MemoryPhi({if.then753,274},{Perl_hv_placeholders_get.exit,
> 275})
>
>
>
> at 2: 470 = MemoryPhi({if.then753,274},{Perl_hv_placeholders_get.exit,
> 275})
>
>
>
> Inserted PHIs
>
> at 0: 470 = MemoryPhi({if.then753,274},{Perl_hv_placeholders_get.exit,
> 275})
>
>
>
> at 1: 470 = MemoryPhi({if.then753,274},{Perl_hv_placeholders_get.exit,
> 275})
>
>
>
> at 2: 470 = MemoryPhi({if.then753,274},{Perl_hv_placeholders_get.exit,
> 275})
>
>
>
> at 3: 470 = MemoryPhi({if.then753,274},{Perl_hv_placeholders_get.exit,
> 275})
>
>
>
>
>
>
>
> *From:* Daniel Berlin [mailto:dberlin at dberlin.org]
> *Sent:* Saturday, September 23, 2017 10:42 PM
> *To:* Godala, Bhargav-reddy <Bhargav-reddy.Godala at amd.com>
> *Cc:* llvm-dev at lists.llvm.org
> *Subject:* Re: [llvm-dev] Potential infinite loop in MemorySSAUpdater
>
>
>
>
>
>
>
> On Sat, Sep 23, 2017 at 9:55 AM, Godala, Bhargav-reddy <
> Bhargav-reddy.Godala at amd.com> wrote:
>
>
>
> With regards
> Bhargav Reddy Godala
> Software Engineer 2
> Bangalore, India
> E-mail: Bhargav-reddy.Godala at amd.com Ext 30678
>
>
>
>
>
>
>
> On 23-Sep-2017, at 9:27 PM, Daniel Berlin <dberlin at dberlin.org> wrote:
>
>
>
>
>
>
>
> On Sat, Sep 23, 2017 at 8:38 AM, Godala, Bhargav-reddy via llvm-dev <
> llvm-dev at lists.llvm.org> wrote:
>
> Hi,
>
>
>
> Can some one explain the intended behaviour of following loop in void
> MemorySSAUpdater::insertDef(MemoryDef *MD, bool RenameUses) function.
>
>
>
> while (!FixupList.empty()) {
>
> unsigned StartingPHISize = InsertedPHIs.size();
>
> fixupDefs(FixupList);
>
> FixupList.clear();
>
> // Put any new phis on the fixup list, and process them
>
> FixupList.append(InsertedPHIs.end() - StartingPHISize,
> InsertedPHIs.end());
>
> }
>
>
>
> 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.
>
>
>
>
>
>
>
> Above loop never terminates unless elements from InsertedPHIs are removed
> as and when they are processed.
>
>
>
> Yes, the loop is slightly off.
>
>
>
> The intention is to process any new phis added by fixupdefs.
>
> However, it really should be InsertedPHIs.start() + StartingPHISize.
>
>
>
> 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.
>
>
>
> It is not iterating over inserted phis, it is iterating over the phis
> added by fixupdefs.
>
>
>
> Thus, it does not matter whether things are removed from insertedphis, and
> it definitely is not infinite in that case.
>
> 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.
>
> You can see it is cleared at the beginning of each insertuse/insertdef.
>
>
>
> 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.
>
>
>
> 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.
>
>
>
> So let's go through the loop itself.
>
>
>
> At the beginning, the fixup list will contain a single def.
>
> Let's look at a fixed version of the loop:
>
>
>
> while (!FixupList.empty()) {
>
> unsigned StartingPHISize = InsertedPHIs.size();
>
> fixupDefs(FixupList);
>
> FixupList.clear();
>
> // Put any new phis on the fixup list, and process them
>
> FixupList.append(InsertedPHIs.begin() + StartingPHISize,
> InsertedPHIs.end());
>
> }
>
>
>
>
>
> Fixup list contains 1 def.
>
> Let's say Insertedphis looks like this { A, B }
>
> StartingPHISize = 2
>
> we fix up the def, which may create new phis
>
> Let's say insertedphis now looks like this {A, B, C, D}
>
> We clear the fixuplist
>
> We now append only the new phis to the fixup list. That is, those that
> come *after* StartingPHISize in the list.
>
> Fixuplist will now contain {C, D}
>
> Iteration 1 ends
>
>
>
> Iteration 2:
>
> Fixup list is {C, D}
> Insertedphis looks like {A, B, C, D }
>
> StartingPHISize = 4
>
> we fixup these defs. Assume it creates a new phi
>
> Insertedphis looks like {A, B, C, D, E }
>
> We clear the fixup list.
>
> We now append only the new phis to the fixup list.
>
> FIxuplist will now contain {E}
>
> Iteration 2 ends
>
>
>
> Fixup list is {E}
>
> Insertedphis looks like {A, B, C, D, E }
>
> StartingPHISize = 5
>
> we fixup these defs. Assume it creates no new phis
>
> Insertedphis looks like {A, B, C, D, E }
>
> We clear the fixup list.
>
> InsertedPHIs.begin() + StartingPHISize == InsertedPHIs.end(), so we add
> nothing
>
> The fixuplist is empty, so the loop ends.
>
>
>
> We are guaranteed insertedphis can only grow to the number of basic blocks.
>
> Once it contains a phi for every basic block, the loop must terminate,
> because no new phis can be added.
>
>
>
> 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,.
>
> That would be a bug if that occurs.
>
>
>
> Otherwise, the loop must terminate when a phi is in every block other than
> start.
>
>
>
>
>
>
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20170925/f6785eae/attachment-0001.html>
-------------- next part --------------
diff --git a/lib/Analysis/MemorySSAUpdater.cpp b/lib/Analysis/MemorySSAUpdater.cpp
index 1ff84471c09..f28f8bd6bce 100644
--- a/lib/Analysis/MemorySSAUpdater.cpp
+++ b/lib/Analysis/MemorySSAUpdater.cpp
@@ -85,12 +85,11 @@ MemoryAccess *MemorySSAUpdater::getPreviousDefRecursive(BasicBlock *BB) {
unsigned i = 0;
for (auto *Pred : predecessors(BB))
Phi->addIncoming(PhiOps[i++], Pred);
+ InsertedPHIs.push_back(Phi);
}
-
Result = Phi;
}
- if (MemoryPhi *MP = dyn_cast<MemoryPhi>(Result))
- InsertedPHIs.push_back(MP);
+
// Set ourselves up for the next variable by resetting visited state.
VisitedBlocks.erase(BB);
return Result;
More information about the llvm-dev
mailing list