[MemorySSA] Use SetVector to avoid nondeterminism.

[asbirlea]

Summary

Use a SetVector for DeadBlockSet.
Resolves PR42574.

[asbirlea]

I'd be interested if there's a better way to use a SmallSetVector, without needing the "8". I don't see an Impl version.
The only alternative I came up with was something like:

template <class OrderedSetT>
void removeBlocks(const OrderedSetT &DeadBlocks);

[dblaikie]

In D64601#1581711, @asbirlea wrote:

I'd be interested if there's a better way to use a SmallSetVector, without needing the "8". I don't see an Impl version.
The only alternative I came up with was something like:

template <class OrderedSetT>
void removeBlocks(const OrderedSetT &DeadBlocks);

You can use SetVector's "getArrayRef" and pass it as "void removeBlocks(ArrayRef<BasicBlock *> DeadBlocks);"

[asbirlea]

You can use SetVector's "getArrayRef" and pass it as "void removeBlocks(ArrayRef<BasicBlock *> DeadBlocks);"

removeBlocks is querying DeadBlocks with count(...). I can change the code to walk the Vector/ArrayRef, but it defeats the purpose of building a set.
It may be ok to change all callsites to just use vector too, assuming the normal expected size is small, but it may be costly for pathological cases (large number of deadblocks).
If folks have a preference either way, please let me know.

[dblaikie]

In D64601#1581770, @asbirlea wrote:

You can use SetVector's "getArrayRef" and pass it as "void removeBlocks(ArrayRef<BasicBlock *> DeadBlocks);"

removeBlocks is querying DeadBlocks with count(...). I can change the code to walk the Vector/ArrayRef, but it defeats the purpose of building a set.
It may be ok to change all callsites to just use vector too, assuming the normal expected size is small, but it may be costly for pathological cases (large number of deadblocks).
If folks have a preference either way, please let me know.

Oh, sorry, I didn't look too closely & thought it was only iterating over the container.

Yeah, I'd just leave it the way you had it with the 8 in there.

[george.burgess.iv]

Thanks! If it's easy to come up with a small regression test (like David mentioned on the bug, reverse_iteration may be a great help), please do so and commit it with this. Otherwise, LGTM as-is.

Yeah, I'd just leave it the way you had it with the 8 in there.

+1.

[asbirlea]

Hmm, AFAICT, there is no opt flag equivalent for LLVM_ENABLE_REVERSE_ITERATION. Did I miss it?

Would adding Mikael's test with the following checks work? I'm thinking the use list order is pretty specific to add as a CHECK, hence the arch restriction, but it may still be too specific.

; RUN: opt -simplifycfg -enable-mssa-loop-dependency -S --preserve-ll-uselistorder %s | FileCheck %s
; REQUIRES: x86-registered-target
; CHECK-LABEL: @n
; CHECK: uselistorder i16 0, { 3, 2, 4, 1, 5, 0, 6 }

[dblaikie]

In D64601#1583240, @asbirlea wrote:

Hmm, AFAICT, there is no opt flag equivalent for LLVM_ENABLE_REVERSE_ITERATION. Did I miss it?

Nah, you didn't miss it - for performance reasons (I think/assume/vaguely recall) it's not a value that can be changed at runtime - it's a compile time configuration option.

Much like writing a test that fails (or, once some bug is fixed, passes) under asan - it's OK that a test might have only demonstrated the failure under one build mode or another, not necessarily under all of them. (heck, lots of tests are run against specific targets (which isn't always great, because sometimes the tests could be written portably and aren't (I've done this as much/more than anyone else - lots of the debug info tests are x86 only)) - which aren't compiled on every buildbot)

Would adding Mikael's test with the following checks work? I'm thinking the use list order is pretty specific to add as a CHECK, hence the arch restriction, but it may still be too specific.

; RUN: opt -simplifycfg -enable-mssa-loop-dependency -S --preserve-ll-uselistorder %s | FileCheck %s
; REQUIRES: x86-registered-target
; CHECK-LABEL: @n
; CHECK: uselistorder i16 0, { 3, 2, 4, 1, 5, 0, 6 }

If the test case is as reduced as possible while still demonstrating a change in behavior between forward and reverse iteration - yeah, I think that's OK. (not ideal, and maybe leave a note that the test case might not carry its weight - if someone in the future finds maintaining the test to be especially burdensome, it can probably be deleted without a huge deal)

Does this test case exercise/justify all the container changes in this patch? (seemed like a lot of containers got changed - which I'm a bit wary of because the non-ordered containers are more efficient, so best not to switch to them unnecessarily)

• Dave

[asbirlea]

I don't know if a bot exists with LLVM_ENABLE_REVERSE_ITERATION set to true, but if it does, then the check I proposed for the uselist order would likely fail, no?

; CHECK: uselistorder i16 0, { 3, 2, 4, 1, 5, 0, 6 }

Does this test case exercise/justify all the container changes in this patch?

The test shows the need for an ordered container in removeBlocks. The patch changes all callsites for this method, and the sets it changes are also not used for much except the call to removeBlocks, so I think it should be fine.

[dblaikie]

In D64601#1583538, @asbirlea wrote:

I don't know if a bot exists with LLVM_ENABLE_REVERSE_ITERATION set to true, but if it does, then the check I proposed for the uselist order would likely fail, no?

I believe there is (or some people with a vested interest in it - they might not be testing with an official buildbot). I think it's appropriate for you to validate that the test/change are justified by the reverse iteration mode before committing (by using a local build with reverse iteration).

; CHECK: uselistorder i16 0, { 3, 2, 4, 1, 5, 0, 6 }

Does this test case exercise/justify all the container changes in this patch?

The test shows the need for an ordered container in removeBlocks. The patch changes all callsites for this method, and the sets it changes are also not used for much except the call to removeBlocks, so I think it should be fine.

Ah, makes sense - sorry for being vague/not looking more closely at the patch.

Does it seem like all call sites have the same ordering requirement? (or could some callers benefit from/get away with an unordered container?) - maybe that question's not worth trying to answer, not sure.

[asbirlea]

Add test.
Tested with LLVM_ENABLE_REVERSE_ITERATION enabled and without.

[asbirlea]

Add comment in test.

[dblaikie]

Sounds good!

[asbirlea]

I'm planning to go ahead with the patch as is, and if the test tickles any bots, we can disable/remove/update it.

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

 // instruction moving API, then just call moveBefore, moveAfter,or moveTo with
 // the right arguments.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_ANALYSIS_MEMORYSSAUPDATER_H
 #define LLVM_ANALYSIS_MEMORYSSAUPDATER_H
 
+#include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/LoopIterator.h"
 #include "llvm/Analysis/MemorySSA.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/CFGDiff.h"
public:
 
   /// Remove all MemoryAcceses in a set of BasicBlocks about to be deleted.
   /// Assumption we make here: all uses of deleted defs and phi must either
   /// occur in blocks about to be deleted (thus will be deleted as well), or
   /// they occur in phis that will simply lose an incoming value.
   /// Deleted blocks still have successor info, but their predecessor edges and
   /// Phi nodes may already be updated. Instructions in DeadBlocks should be
   /// deleted after this call.
-  void removeBlocks(const SmallPtrSetImpl<BasicBlock *> &DeadBlocks);
+  void removeBlocks(const SmallSetVector<BasicBlock *, 8> &DeadBlocks);
 
   /// Instruction I will be changed to an unreachable. Remove all accesses in
   /// I's block that follow I (inclusive), and update the Phis in the blocks'
   /// successors.
   void changeToUnreachable(const Instruction *I);
 
   /// Conditional branch BI is changed or replaced with an unconditional branch
   /// to `To`. Update Phis in BI's successors to remove BI's BB.

llvm/trunk/lib/Analysis/MemorySSAUpdater.cpp

while (PhisSize-- > 0)
               cast_or_null<MemoryPhi>(PhisToOptimize.pop_back_val())) {
         auto OperRange = MP->operands();
         tryRemoveTrivialPhi(MP, OperRange);
       }
   }
 }
 
 void MemorySSAUpdater::removeBlocks(
-    const SmallPtrSetImpl<BasicBlock *> &DeadBlocks) {
+    const SmallSetVector<BasicBlock *, 8> &DeadBlocks) {
   // First delete all uses of BB in MemoryPhis.
   for (BasicBlock *BB : DeadBlocks) {
     Instruction *TI = BB->getTerminator();
     assert(TI && "Basic block expected to have a terminator instruction");
     for (BasicBlock *Succ : successors(TI))
       if (!DeadBlocks.count(Succ))
         if (MemoryPhi *MP = MSSA->getMemoryAccess(Succ)) {
           MP->unorderedDeleteIncomingBlock(BB);

llvm/trunk/lib/Transforms/Scalar/LoopSimplifyCFG.cpp

if (MSSAU) {
         MSSAU->getMemorySSA()->verifyMemorySSA();
     }
   }
 
   /// Delete loop blocks that have become unreachable after folding. Make all
   /// relevant updates to DT and LI.
   void deleteDeadLoopBlocks() {
     if (MSSAU) {
-      SmallPtrSet<BasicBlock *, 8> DeadLoopBlocksSet(DeadLoopBlocks.begin(),
+      SmallSetVector<BasicBlock *, 8> DeadLoopBlocksSet(DeadLoopBlocks.begin(),
                                                         DeadLoopBlocks.end());
       MSSAU->removeBlocks(DeadLoopBlocksSet);
     }
 
     // The function LI.erase has some invariants that need to be preserved when
     // it tries to remove a loop which is not the top-level loop. In particular,
     // it requires loop's preheader to be strictly in loop's parent. We cannot
     // just remove blocks one by one, because after removal of preheader we may
     // break this invariant for the dead loop. So we detatch and erase all dead

llvm/trunk/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp

for (auto &VMap : VMaps)
         if (!DT.isReachableFromEntry(ClonedBB)) {
           for (BasicBlock *SuccBB : successors(ClonedBB))
             SuccBB->removePredecessor(ClonedBB);
           DeadBlocks.push_back(ClonedBB);
         }
 
   // Remove all MemorySSA in the dead blocks
   if (MSSAU) {
-    SmallPtrSet<BasicBlock *, 16> DeadBlockSet(DeadBlocks.begin(),
+    SmallSetVector<BasicBlock *, 8> DeadBlockSet(DeadBlocks.begin(),
                                                  DeadBlocks.end());
     MSSAU->removeBlocks(DeadBlockSet);
   }
 
   // Drop any remaining references to break cycles.
   for (BasicBlock *BB : DeadBlocks)
     BB->dropAllReferences();
   // Erase them from the IR.
   for (BasicBlock *BB : DeadBlocks)
     BB->eraseFromParent();
 }
 
 static void deleteDeadBlocksFromLoop(Loop &L,
                                      SmallVectorImpl<BasicBlock *> &ExitBlocks,
                                      DominatorTree &DT, LoopInfo &LI,
                                      MemorySSAUpdater *MSSAU) {
   // Find all the dead blocks tied to this loop, and remove them from their
   // successors.
-  SmallPtrSet<BasicBlock *, 16> DeadBlockSet;
+  SmallSetVector<BasicBlock *, 8> DeadBlockSet;
 
   // Start with loop/exit blocks and get a transitive closure of reachable dead
   // blocks.
   SmallVector<BasicBlock *, 16> DeathCandidates(ExitBlocks.begin(),
                                                 ExitBlocks.end());
   DeathCandidates.append(L.blocks().begin(), L.blocks().end());
   while (!DeathCandidates.empty()) {
     auto *BB = DeathCandidates.pop_back_val();

llvm/trunk/lib/Transforms/Utils/Local.cpp

bool llvm::removeUnreachableBlocks(Function &F, LazyValueInfo *LVI,
 
   // If there are unreachable blocks in the CFG...
   if (Reachable.size() == F.size())
     return Changed;
 
   assert(Reachable.size() < F.size());
   NumRemoved += F.size()-Reachable.size();
 
-  SmallPtrSet<BasicBlock *, 16> DeadBlockSet;
+  SmallSetVector<BasicBlock *, 8> DeadBlockSet;
   for (Function::iterator I = ++F.begin(), E = F.end(); I != E; ++I) {
     auto *BB = &*I;
     if (Reachable.count(BB))
       continue;
     DeadBlockSet.insert(BB);
   }
 
   if (MSSAU)

llvm/trunk/lib/Transforms/Utils/LoopSimplify.cpp

for (unsigned i = 0, e = ExitingBlocks.size(); i != e; ++i) {
       const std::vector<DomTreeNodeBase<BasicBlock> *> &Children =
         Node->getChildren();
       while (!Children.empty()) {
         DomTreeNode *Child = Children.front();
         DT->changeImmediateDominator(Child, Node->getIDom());
       }
       DT->eraseNode(ExitingBlock);
       if (MSSAU) {
-        SmallPtrSet<BasicBlock *, 1> ExitBlockSet{ExitingBlock};
+        SmallSetVector<BasicBlock *, 8> ExitBlockSet;
+        ExitBlockSet.insert(ExitingBlock);
         MSSAU->removeBlocks(ExitBlockSet);
       }
 
       BI->getSuccessor(0)->removePredecessor(
           ExitingBlock, /* KeepOneInputPHIs */ PreserveLCSSA);
       BI->getSuccessor(1)->removePredecessor(
           ExitingBlock, /* KeepOneInputPHIs */ PreserveLCSSA);
       ExitingBlock->eraseFromParent();

llvm/trunk/test/Analysis/MemorySSA/nondeterminism.ll

+; RUN: opt -simplifycfg -enable-mssa-loop-dependency -S --preserve-ll-uselistorder %s | FileCheck %s
+; REQUIRES: x86-registered-target
+; CHECK-LABEL: @n
+; CHECK: uselistorder i16 0, { 3, 2, 4, 1, 5, 0, 6 }
+
+; Note: test was added in an effort to ensure determinism when updating memoryssa. See PR42574.
+; If the uselistorder check becomes no longer relevant, the test can be disabled or removed.
+
+%rec9 = type { i16, i32, i32 }
+
+@a = global [1 x [1 x %rec9]] zeroinitializer
+
+define i16 @n() {
+  br label %..split_crit_edge
+
+..split_crit_edge:                                ; preds = %0
+  br label %.split
+
+bb4.us4:                                          ; preds = %bb2.split.us32, %bb6.us28
+  %i.4.01.us5 = phi i16 [ %_tmp49.us30, %bb6.us28 ]
+  br label %g.exit4.us21
+
+bb1.i.us14:                                       ; preds = %bb4.us4
+  br label %g.exit4.us21
+
+g.exit4.us21:                                     ; preds = %bb1.i.us14, %g.exit4.critedge.us9
+  %i.4.02.us22 = phi i16 [ %i.4.01.us5, %bb4.us4 ], [ %i.4.01.us5, %bb1.i.us14 ]
+  br label %bb6.us28
+
+bb5.us26:                                         ; preds = %g.exit4.us21
+  br label %bb6.us28
+
+bb6.us28:                                         ; preds = %bb5.us26, %g.exit4.us21
+  %i.4.03.us29 = phi i16 [ %i.4.02.us22, %bb5.us26 ], [ %i.4.02.us22, %g.exit4.us21 ]
+  %_tmp49.us30 = add nuw nsw i16 %i.4.03.us29, 1
+  br label %bb4.us4
+
+bb4.us.us:                                        ; preds = %bb2.split.us.us, %bb6.us.us
+  %i.4.01.us.us = phi i16  [ %_tmp49.us.us, %bb6.us.us ]
+  br label %bb1.i.us.us
+
+bb1.i.us.us:                                      ; preds = %bb4.us.us
+  br label %g.exit4.us.us
+
+g.exit4.us.us:                                    ; preds = %bb1.i.us.us, %g.exit4.critedge.us.us
+  %i.4.02.us.us = phi i16 [ %i.4.01.us.us, %bb1.i.us.us ]
+  br label %bb5.us.us
+
+bb5.us.us:                                        ; preds = %g.exit4.us.us
+  br label %bb6.us.us
+
+bb6.us.us:                                        ; preds = %bb5.us.us, %g.exit4.us.us
+  %i.4.03.us.us = phi i16 [ %i.4.02.us.us, %bb5.us.us ]
+  %_tmp49.us.us = add nuw nsw i16 %i.4.03.us.us, 1
+  br label %bb4.us.us
+
+
+.split:                                           ; preds = %..split_crit_edge
+  br label %bb2
+
+bb2:                                              ; preds = %.split, %bb7
+  %h.3.0 = phi i16 [ undef, %.split ], [ %_tmp53, %bb7 ]
+  br label %bb2.bb2.split_crit_edge
+
+bb2.bb2.split_crit_edge:                          ; preds = %bb2
+  br label %bb2.split
+
+bb2.split.us:                                     ; preds = %bb2
+  br label %bb4.us
+
+bb4.us:                                           ; preds = %bb6.us, %bb2.split.us
+  %i.4.01.us = phi i16 [ 0, %bb2.split.us ]
+  br label %bb1.i.us
+
+g.exit4.critedge.us:                              ; preds = %bb4.us
+  br label %g.exit4.us
+
+bb1.i.us:                                         ; preds = %bb4.us
+  br label %g.exit4.us
+
+g.exit4.us:                                       ; preds = %bb1.i.us, %g.exit4.critedge.us
+  %i.4.02.us = phi i16 [ %i.4.01.us, %g.exit4.critedge.us ], [ %i.4.01.us, %bb1.i.us ]
+  br label %bb5.us
+
+bb5.us:                                           ; preds = %g.exit4.us
+  br label %bb7
+
+bb2.split:                                        ; preds = %bb2.bb2.split_crit_edge
+  br label %bb4
+
+bb4:                                              ; preds = %bb2.split, %bb6
+  %i.4.01 = phi i16 [ 0, %bb2.split ]
+  %_tmp16 = getelementptr [1 x [1 x %rec9]], [1 x [1 x %rec9]]* @a, i16 0, i16 %h.3.0, i16 %i.4.01, i32 0
+  %_tmp17 = load i16, i16* %_tmp16, align 1
+  br label %g.exit4.critedge
+
+bb1.i:                                            ; preds = %bb4
+  br label %g.exit4
+
+g.exit4.critedge:                                 ; preds = %bb4
+  %_tmp28.c = getelementptr [1 x [1 x %rec9]], [1 x [1 x %rec9]]* @a, i16 0, i16 %h.3.0, i16 %i.4.01, i32 1
+  %_tmp29.c = load i32, i32* %_tmp28.c, align 1
+  %_tmp30.c = trunc i32 %_tmp29.c to i16
+  br label %g.exit4
+
+g.exit4:                                          ; preds = %g.exit4.critedge, %bb1.i
+  %i.4.02 = phi i16 [ %i.4.01, %g.exit4.critedge ], [ %i.4.01, %bb1.i ]
+  %_tmp41 = getelementptr [1 x [1 x %rec9]], [1 x [1 x %rec9]]* @a, i16 0, i16 %h.3.0, i16 %i.4.02, i32 2
+  br label %bb6
+
+bb5:                                              ; preds = %g.exit4
+  br label %bb6
+
+bb6:                                              ; preds = %bb5, %g.exit4
+  %i.4.03 = phi i16 [ %i.4.02, %bb5 ], [ %i.4.02, %g.exit4 ]
+  %_tmp49 = add nuw nsw i16 %i.4.03, 1
+  br label %bb7
+
+bb7:                                              ; preds = %bb7.us-lcssa.us, %bb7.us-lcssa
+  %_tmp53 = add nsw i16 %h.3.0, 1
+  br label %bb2
+}