[MemorySSAUpdater] Avoid creating self-referencing MemoryDefs

[labrinea]

Summary

Fix for https://bugs.llvm.org/show_bug.cgi?id=38807, which occurred while compiling SemaTemplateInstantiate.cpp with clang and GVNHoist enabled.
In the following example:

      1=def(entry)
      /        \
2=def(1)       4=def(1)
3=def(2)       5=def(4)

When removing the MemoryDef 2=def(1) from its basic block, and just before adding it to the end of the parent basic block, we first replace all its uses with the defining memory access:

3=def(2) -> 3=def(1)

Then we call insertDef for adding 2=def(1) to the parent basic block, where we replace the uses of 1=def(entry) with 2=def(1). Doing so we create a self reference:

2=def(1) -> 2=def(2)  (bad)
3=def(1) -> 3=def(2)  (ok)
4=def(1) -> 4=def(2)  (ok)

[labrinea]

lib/Analysis/MemorySSAUpdater.cpp

276

Removing the comment as this is already happening and it's what we are trying to fix.

406

Another way to fix this would be to add What->replaceUsesOfWith(What->getDefiningAccess(), nullptr); here, so that What gets removed from the Uses of its defining memory access. This would make sure that the graph of Uses/Users is in a correct state before calling insertDef(). However I haven't tested it thoroughly and it's also more expensive so I am in favor of the current fix.

test/Transforms/GVNHoist/pr38807.ll

32

I am not sure why but the gep remains after the hoist, and goes away with dead code elimination. Is that correct @sebpop ?

42

Same here.

[sebpop]

Looks good to me.

test/Transforms/GVNHoist/pr38807.ll

32

gvn hoist does not need to implement a dce.

lib/Analysis/MemorySSAUpdater.cpp

void MemorySSAUpdater::insertDef(MemoryDef *MD, bool RenameUses) {
   // There is a def before us, which means we can replace any store/phi uses
   // of that thing with us, since we are in the way of whatever was there
   // before.
   // We now define that def's memorydefs and memoryphis
   if (DefBeforeSameBlock) {
     for (auto UI = DefBefore->use_begin(), UE = DefBefore->use_end();
          UI != UE;) {
       Use &U = *UI++;
-      // Leave the uses alone
-      if (isa<MemoryUse>(U.getUser()))
+      // Leave the MemoryUses alone.
+      // Also make sure we skip ourselves to avoid self references.
+      if (isa<MemoryUse>(U.getUser()) || U.getUser() == MD)
         continue;
       U.set(MD);
     }
   }
 
   // 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<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
void MemorySSAUpdater::moveTo(MemoryUseOrDef *What, BasicBlock *BB,
                               WhereType Where) {
   // Mark MemoryPhi users of What not to be optimized.
   for (auto *U : What->users())
     if (MemoryPhi *PhiUser = dyn_cast<MemoryPhi>(U))
       NonOptPhis.insert(PhiUser);
 
   // Replace all our users with our defining access.
   What->replaceAllUsesWith(What->getDefiningAccess());
 
   // Let MemorySSA take care of moving it around in the lists.
   MSSA->moveTo(What, BB, Where);
 
   // Now reinsert it into the IR and do whatever fixups needed.
   if (auto *MD = dyn_cast<MemoryDef>(What))
     insertDef(MD);
   else
     insertUse(cast<MemoryUse>(What));

test/Transforms/GVNHoist/pr38807.ll

+; RUN: opt < %s -early-cse-memssa -gvn-hoist -S | FileCheck %s
+
+; Make sure opt doesn't crash. On top of that, the instructions
+; of the side blocks should be hoisted to the entry block.
+
+%s = type { i32, i64 }
+%S = type { %s, i32 }
+
+;CHECK-LABEL: @foo
+
+define void @foo(i32* %arg) {
+bb0:
+  %0 = bitcast i32* %arg to %S*
+  %call.idx.i = getelementptr %S, %S* %0, i64 0, i32 0, i32 0
+  %call.idx.val.i = load i32, i32* %call.idx.i
+  br label %bb1
+
+;CHECK: bb1:
+;CHECK:   %call264 = call zeroext i1 @bar
+;CHECK:   store i32 %call.idx.val.i, i32* %call.idx.i
+;CHECK:   %1 = getelementptr inbounds %S, %S* %0, i64 0, i32 0, i32 1
+;CHECK:   store i64 undef, i64* %1
+;CHECK:   br i1 %call264, label %bb2, label %bb3
+
+bb1:
+  %call264 = call zeroext i1 @bar()
+  br i1 %call264, label %bb2, label %bb3
+
+;CHECK:     bb2:
+;CHECK-NOT:   store i32 %call.idx.val.i, i32* %call.idx.i
+;CHECK-NOT:   store i64 undef, i64* %{.*}
+
+bb2:
+  store i32 %call.idx.val.i, i32* %call.idx.i
+  %1 = getelementptr inbounds %S, %S* %0, i64 0, i32 0, i32 1
+  store i64 undef, i64* %1
+  ret void
+
+;CHECK:     bb3:
+;CHECK-NOT:   store i32 %call.idx.val.i, i32* %call.idx.i
+;CHECK-NOT:   store i64 undef, i64* %{.*}
+
+bb3:
+  store i32 %call.idx.val.i, i32* %call.idx.i
+  %2 = getelementptr inbounds %S, %S* %0, i64 0, i32 0, i32 1
+  store i64 undef, i64* %2
+  ret void
+}
+
+declare zeroext i1 @bar()