[MemorySSAUpdater] Remove deleted trivial Phis from active workset

[labrinea]

Summary

Bug fix for PR37808. The regression test is a reduced version of the original reproducer attached to the bug report. As stated in the report, the problem was that InsertedPHIs was keeping dangling pointers to deleted Memory-Phis. MemoryPhis are created eagerly and sometimes get zapped shortly afterwards. I've used WeakVH instead of an expensive removal operation from the active workset.

[efriedma]

lib/Analysis/MemorySSAUpdater.cpp

208 ↗

(On Diff #152090)

remove on a SmallSetVector is linear time, which might be a problem here.

[labrinea]

lib/Analysis/MemorySSAUpdater.cpp

208 ↗

(On Diff #152090)

On a SmallVector we'd have to do a linear lookup and then move the elements around, so it should be the same in terms of complexity. Moreover, I thought it's good to have a guarantee that InsertedPHIs does not contain duplicates. What is the suggestion here?

[efriedma]

lib/Analysis/MemorySSAUpdater.cpp

208 ↗

(On Diff #152090)

It's possible to construct a set with both constant-time removal and iteration in insertion order: essentially, make a DenseMap<AssertingVH<MemoryPhi>, size_t> where the value is an index into a SmallVector<Optional<AssertingVH<MemoryPhi>>>), or something like that. Or maybe there's some simpler way to handle this I'm not thinking of.

[labrinea]

lib/Analysis/MemorySSAUpdater.cpp

208 ↗

(On Diff #152090)

I am not convinced it's worth maintaining two data structures to avoid a linear lookup, which costs nothing on a SmallVector. We do linear lookups for NonOptPhis.erase() anyway. I have a patch in case you are still interested but I am not in favour of it. In order for the DenseMap to be up to date we can't actually erase elements from InsertedPHIs but we just mark them as stale. This complicates other parts of the algorithm like insertDef() and fixupDefs().

[george.burgess.iv]

Thanks for this!

lib/Analysis/MemorySSAUpdater.cpp

208 ↗

(On Diff #152090)

I'm surprised that we're removing anything here at all, given that we rely on stable indices in InsertedPhis on lines 299-305.

Would keeping a SmallVector<WeakVH, N> (with appropriate null checks/conversions where necessary) work just as well?

(I don't see how InsertedPHIs can get a duplicate, anyway. AFAICT, when we're inserting, either:

• The phi being inserted was just created, or
• The phi being inserted was created earlier, but never had operands added, leaving it in a broken state. Prior to adding to InsertedPhis, we add operands, which should prevent us from adding it to InsertedPhis again

Am I missing something?)

[efriedma]

We do linear lookups for NonOptPhis.erase() anyway

SmallSet insertion and removal are log(N) for large N.

https://reviews.llvm.org/D48504 is a (almost) drop-in replacement for SetVector, with a constant time remove().

[labrinea]

lib/Analysis/MemorySSAUpdater.cpp

304 ↗

(On Diff #152090)

https://reviews.llvm.org/D48504 is a (almost) drop-in replacement for SetVector, with a constant time remove().

@efriedma thanks a lot for your effort on this :)

It seems we need a random access iterator here:

FixupList.append(InsertedPHIs.at(StartingPHISize), InsertedPHIs.end());

otherwise the following assertion fails

static_assert(IsRandomAccess, "The '-' operator is only defined for random access iterators.");

[labrinea]

Used the ADT from https://reviews.llvm.org/D49030

[labrinea]

Added back the header file for SmallPtrSet that was accidentally removed.

[george.burgess.iv]

lib/Analysis/MemorySSAUpdater.cpp

208 ↗

(On Diff #152090)

Just bumping this comment, since I don't think that the 'stable indices' bit is addressed by the OrderedSet ADT, and don't see a clear path for addressing that (nor prose about why it's not a problem)

[labrinea]

lib/Analysis/MemorySSAUpdater.cpp

208 ↗

(On Diff #152090)

fixupDefs() can potentially insert/remove MemoryPhis. As long as it only removes newly created Phis (not existing ones in the ADT), then the order of elements in the ADT shouldn't matter. Now looking at the line 304, it would make more sense if it was

FixupList.append(InsertedPHIs.begin() + StartingPHISize, InsertedPHIs.end());

[labrinea]

Changes to the prior revision:

• I've used std::set for InsertedPHIs to avoid linear cost lookups upon deletion.
• I've refactored insertDef() so that it no longer relies on insertion order iteration over InsertedPHIs.

[george.burgess.iv]

I'm still in favor of just replacing SmallVector<MemoryPhi *, 8> InsertedPHIs with SmallVector<WeakVH, 8> InsertedPHIs, since:

• I think it meets all of our needs here,
• it's a very straightforward change (no need to deal with removal, new containers, etc.), and
• I don't see how we can ever get a duplicate in InsertedPHIs to start with.

In any case, a few questions/nits about the current patch.

include/llvm/Analysis/MemorySSAUpdater.h

64 ↗

(On Diff #154838)

Please add a comment saying that we're using a std::set because we need insertion to not invalidate iterators, since we mutate this set while iterating over it.

(I assume that's why we're using a set here, anyway)

64 ↗

(On Diff #154838)

Also, is it possible that this would cause us to visit Phis in a nondeterministic order (thus creating new Phis in a nondeterministic order, thus having unstable numbering for MemorySSA's print output)? If so, a straightforward fix would be to make a comparator that uses the Phi's ID.

lib/Analysis/MemorySSAUpdater.cpp

297 ↗

(On Diff #154838)

Nit: If we only put Phis in here, please make it a set of MemoryPhis, not MemoryAccesses.

298 ↗

(On Diff #154838)

Nit: Cnt

299 ↗

(On Diff #154838)

In general, is there a "we'll never remove a MP from InsertedPhis if we visit it here" guarantee that I'm missing? If so, please add a comment about why we have that guarantee, since this loop appears to depend on it in a few ways.

305 ↗

(On Diff #154838)

This is quadratic WRT the size of InsertedPHIs, no?

208 ↗

(On Diff #152090)

As long as it only removes newly created Phis (not existing ones in the ADT), then the order of elements in the ADT shouldn't matter

Sure, but are you 100% sure that it can't remove a phi that's not newly-created? :) I'd be willing to buy it, but haven't reasoned about this case enough to know for certain yet.

[labrinea]

Replacing MemoryPhi * with WeakVH won't work out of the box; it requires typecasts and null checks upon iteration. It also adds and additional overhead (similar to AssertingVH though). In general, the idea of keeping null references in the ADT instead of actually deleting them seems like a workaround to me. I don't see why we should be afraid of making non trivial changes in the code if there's a fundamental bug. On that note I still believe the line 303 of the original revision is wrong since we push_back() when adding new elements:

FixupList.append(InsertedPHIs.end() - StartingPHISize, InsertedPHIs.end());

Shouldn't it be like this?

FixupList.append(InsertedPHIs.begin() + StartingPHISize, InsertedPHIs.end());

Answering some inline comments:

include/llvm/Analysis/MemorySSAUpdater.h

64 ↗

(On Diff #154838)

Please add a comment saying that we're using a std::set because we need insertion to not invalidate iterators, since we mutate this set while iterating over it.

(I assume that's why we're using a set here, anyway)

We use std::set is to avoid linear time removal from SmallVector, a concern raised by @efriedma. This was reason I created https://reviews.llvm.org/D49030. However, people from the community were tentative about adding a new ADT that is very similar to existing ones (MapVector,SetVector), which are not a good fit for InsertedPHIs though.

Also, is it possible that this would cause us to visit Phis in a nondeterministic order (thus creating new Phis in a nondeterministic order, thus having unstable numbering for MemorySSA's print output)? If so, a straightforward fix would be to make a comparator that uses the Phi's ID

Sounds like a good idea.

lib/Analysis/MemorySSAUpdater.cpp

297 ↗

(On Diff #154838)

Good catch.

299 ↗

(On Diff #154838)

No we don't have such a guarantee that's why we have to break the innermost loop and re-iterate.

305 ↗

(On Diff #154838)

Possibly.

208 ↗

(On Diff #152090)

No, I am not 100%sure we won't remove a Phi which is not newly-created. But this is no longer an issue with the latest revision of the patch, since we don't rely on insertion order iteration. However, I believe we need <AssertingVH<MemoryPhi> to avoid considering a newly created Phi, that happens to get allocated to the same address as a deleted one, as Seen. I will experiment with a new patch and update my revision shortly.

[george.burgess.iv]

It also adds and additional overhead

Any targeted fix that makes us track the lifetime of these more closely is going to add additional overhead. If anything, I imagine that adding a DenseMap insertion/deletion per Phi would be cheaper than taking n^2 time to walk said Phis.

In general, the idea of keeping null references in the ADT instead of actually deleting them seems like a workaround to me. I don't see why we should be afraid of making non trivial changes in the code if there's a fundamental bug.

I think the fundamental issue is that we create these non-minimal phi structures just to zap them shortly afterward. :) From the looks of this, though, that's a limitation imposed by the algorithm we're using. So, unless we want to try and improve that algorithm, or unless our goal is to swap to another algorithm without this limitation, anything we do here is going to boil down to a "workaround" of that quirk.

A Phi is being deleted and we need later iterations of this algorithm to take that into account. I don't understand why eagerly removing a pointer from our worklist is strictly less hacky than using WeakVH for this purpose.

If you still feel strongly that WeakVH isn't the right way, I'm happy to accept an eager removal approach if it doesn't substantially lose out in overall clarity, simplicity, and (algorithmic, within reason) performance over just using WeakVH. I don't think this patch is at that point yet, and I think we'd need a custom SetVector-but-with-constant-time-bounds, as was proposed, to get it there. (I also suspect that such a patch would end up losing out in perf/memory over WeakVH in the constant factor, but I'm sure we have lower hanging fruits than that in this code, if the speed/memory consumption here are becoming problematic.)

I don't see why we should be afraid of making non trivial changes in the code

I'm fine with making substantial changes to code if doing so is called for. My concern is more that it's not called for here. :)

On that note I still believe the line 303 of the original revision is wrong

Agreed

include/llvm/Analysis/MemorySSAUpdater.h

64 ↗

(On Diff #154838)

We use std::set is to avoid linear time removal from SmallVector

Please prefer DenseSet (or one of its variants) if all that's needed is fast set-like operations. std::set provides a number of guarantees above and beyond DenseSet (iterator validity, pointer stability, ...), and so generally ends up being slower.

That said, if we go with using IDs as keys, we'll need the ordering guarantee that std::set provides, so please add a comment noting that we're using a set for consistent Phi ordering.

lib/Analysis/MemorySSAUpdater.cpp

103 ↗

(On Diff #154838)

Please also assert that this insertion happened, so it's clear that deduplication is never a goal here.

299 ↗

(On Diff #154838)

I don't think that works in the general case, since our Seen set will retain dangling pointers. If we delete a Phi and new up one at the same pointer, we'll fail to visit it here. It's admittedly a rare case, but certainly a possibility.

305 ↗

(On Diff #154838)

With the std::set comparator change, I'd say "definitely". :)

[labrinea]

Ok, I've convinced myself that using WeakVH is the most straightforward fix for now. We shouldn't be spending more time on this.

[george.burgess.iv]

LGTM. Thanks again!

llvm/trunk/include/llvm/Analysis/MemorySSAUpdater.h

 class Instruction;
 class MemoryAccess;
 class LLVMContext;
 class raw_ostream;
 
 class MemorySSAUpdater {
 private:
   MemorySSA *MSSA;
-  SmallVector<MemoryPhi *, 8> InsertedPHIs;
+
+  /// We use WeakVH rather than a costly deletion to deal with dangling pointers.
+  /// MemoryPhis are created eagerly and sometimes get zapped shortly afterwards.
+  SmallVector<WeakVH, 16> InsertedPHIs;
+
   SmallPtrSet<BasicBlock *, 8> VisitedBlocks;
   SmallSet<AssertingVH<MemoryPhi>, 8> NonOptPhis;
 
 public:
   MemorySSAUpdater(MemorySSA *MSSA) : MSSA(MSSA) {}
   /// Insert a definition into the MemorySSA IR.  RenameUses will rename any use
   /// below the new def block (and any inserted phis).  RenameUses should be set
   /// to true if the definition may cause new aliases for loads below it.  This
private:
   getPreviousDefFromEnd(BasicBlock *,
                         DenseMap<BasicBlock *, TrackingVH<MemoryAccess>> &);
   MemoryAccess *
   getPreviousDefRecursive(BasicBlock *,
                           DenseMap<BasicBlock *, TrackingVH<MemoryAccess>> &);
   MemoryAccess *recursePhi(MemoryAccess *Phi);
   template <class RangeType>
   MemoryAccess *tryRemoveTrivialPhi(MemoryPhi *Phi, RangeType &Operands);
-  void fixupDefs(const SmallVectorImpl<MemoryAccess *> &);
+  void fixupDefs(const SmallVectorImpl<WeakVH> &);
 };
 } // end namespace llvm
 
 #endif // LLVM_ANALYSIS_MEMORYSSAUPDATER_H

llvm/trunk/lib/Analysis/MemorySSAUpdater.cpp

if (DefBeforeSameBlock) {
     }
   }
 
   // and that def is now our defining access.
   // We change them in this order otherwise we will appear in the use list
   // above and reset ourselves.
   MD->setDefiningAccess(DefBefore);
 
-  SmallVector<MemoryAccess *, 8> FixupList(InsertedPHIs.begin(),
-                                           InsertedPHIs.end());
+  SmallVector<WeakVH, 8> FixupList(InsertedPHIs.begin(), InsertedPHIs.end());
   if (!DefBeforeSameBlock) {
     // If there was a local def before us, we must have the same effect it
     // did. Because every may-def is the same, any phis/etc we would create, it
     // would also have created.  If there was no local def before us, we
     // performed a global update, and have to search all successors and make
     // sure we update the first def in each of them (following all paths until
     // we hit the first def along each path). This may also insert phi nodes.
     // TODO: There are other cases we can skip this work, such as when we have a
     // single successor, and only used a straight line of single pred blocks
     // backwards to find the def.  To make that work, we'd have to track whether
     // getDefRecursive only ever used the single predecessor case.  These types
     // of paths also only exist in between CFG simplifications.
     FixupList.push_back(MD);
   }
 
   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());
+    FixupList.append(InsertedPHIs.begin() + StartingPHISize, InsertedPHIs.end());
   }
   // Now that all fixups are done, rename all uses if we are asked.
   if (RenameUses) {
     SmallPtrSet<BasicBlock *, 16> Visited;
     BasicBlock *StartBlock = MD->getBlock();
     // We are guaranteed there is a def in the block, because we just got it
     // handed to us in this function.
     MemoryAccess *FirstDef = &*MSSA->getWritableBlockDefs(StartBlock)->begin();
     // Convert to incoming value if it's a memorydef. A phi *is* already an
     // incoming value.
     if (auto *MD = dyn_cast<MemoryDef>(FirstDef))
       FirstDef = MD->getDefiningAccess();
 
     MSSA->renamePass(MD->getBlock(), FirstDef, Visited);
     // We just inserted a phi into this block, so the incoming value will become
     // the phi anyway, so it does not matter what we pass.
-    for (auto *MP : InsertedPHIs)
-      MSSA->renamePass(MP->getBlock(), nullptr, Visited);
+    for (auto &MP : InsertedPHIs) {
+      MemoryPhi *Phi = dyn_cast_or_null<MemoryPhi>(MP);
+      if (Phi)
+        MSSA->renamePass(Phi->getBlock(), nullptr, Visited);
+    }
   }
 }
 
-void MemorySSAUpdater::fixupDefs(const SmallVectorImpl<MemoryAccess *> &Vars) {
+void MemorySSAUpdater::fixupDefs(const SmallVectorImpl<WeakVH> &Vars) {
   SmallPtrSet<const BasicBlock *, 8> Seen;
   SmallVector<const BasicBlock *, 16> Worklist;
-  for (auto *NewDef : Vars) {
+  for (auto &Var : Vars) {
+    MemoryAccess *NewDef = dyn_cast_or_null<MemoryAccess>(Var);
+    if (!NewDef)
+      continue;
     // First, see if there is a local def after the operand.
     auto *Defs = MSSA->getWritableBlockDefs(NewDef->getBlock());
     auto DefIter = NewDef->getDefsIterator();
 
     // The temporary Phi is being fixed, unmark it for not to optimize.
     if (MemoryPhi *Phi = dyn_cast<MemoryPhi>(NewDef))
       NonOptPhis.erase(Phi);
 

llvm/trunk/test/Transforms/GVNHoist/pr37808.ll

+; RUN: opt < %s -gvn-hoist -S | FileCheck %s
+
+define void @func() {
+; CHECK-LABEL: @func()
+; CHECK:       bb6:
+; CHECK:         store i64 0, i64* undef, align 8
+; CHECK:       bb7:
+; CHECK-NOT:     store i64 0, i64* undef, align 8
+; CHECK:       bb8:
+; CHECK-NOT:     store i64 0, i64* undef, align 8
+
+entry:
+  br label %bb1
+
+bb1:
+  br label %bb2
+
+bb2:
+  br label %bb3
+
+bb3:
+  br i1 undef, label %bb4, label %bb2
+
+bb4:
+  br i1 undef, label %bb5, label %bb3
+
+bb5:
+  br label %bb6
+
+bb6:
+  br i1 undef, label %bb7, label %bb8
+
+bb7:
+  store i64 0, i64* undef, align 8
+  unreachable
+
+bb8:
+  store i64 0, i64* undef, align 8
+  ret void
+}