Godala, Bhargav-reddy via llvm-dev
2017-Sep-25 06:40 UTC
[llvm-dev] Potential infinite loop in MemorySSAUpdater
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<mailto: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<mailto:Bhargav-reddy.Godala at
amd.com> Ext 30678
On 23-Sep-2017, at 9:27 PM, Daniel Berlin <dberlin at
dberlin.org<mailto: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<mailto: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/f9c3fcb8/attachment.html>
Daniel Berlin via llvm-dev
2017-Sep-25 22:12 UTC
[llvm-dev] Potential infinite loop in MemorySSAUpdater
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;
Bhargav Reddy via llvm-dev
2017-Sep-26 01:02 UTC
[llvm-dev] Potential infinite loop in MemorySSAUpdater
Thanks, It works!!> On 26-Sep-2017, at 3:42 AM, Daniel Berlin via llvm-dev <llvm-dev at lists.llvm.org> wrote: > > 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 <mailto: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 <mailto:dberlin at dberlin.org>] > Sent: Saturday, September 23, 2017 10:42 PM > To: Godala, Bhargav-reddy <Bhargav-reddy.Godala at amd.com <mailto:Bhargav-reddy.Godala at amd.com>> > Cc: llvm-dev at lists.llvm.org <mailto: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 <mailto: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 <mailto:Bhargav-reddy.Godala at amd.com> Ext 30678 > > > > > > > > On 23-Sep-2017, at 9:27 PM, Daniel Berlin <dberlin at dberlin.org <mailto: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 <mailto: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. > > > > > > > > > > > <fixmemssaupdater.diff>_______________________________________________ > LLVM Developers mailing list > llvm-dev at lists.llvm.org > http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20170926/6d35057b/attachment.html>