[GVN] Fix MemorySSA update when replacing assume(false) with stores.

[fhahn]

Summary

When replacing an assume(false) with a store, we have to be more careful
with the order we insert the new access. This patch updates the code to
look at the accesses in the block to find a suitable insertion point.

Alterantively we could check the defining access of the assume, but IIRC
there has been some discussion about making assume() readnone, so
looking at the access list might be more future proof.

Fixes PR48072.

[asbirlea]

Thank you for the fix.

llvm/lib/Transforms/Scalar/GVN.cpp

if (Cond->isZero()) {
       Type *Int8Ty = Type::getInt8Ty(V->getContext());
       // Insert a new store to null instruction before the load to indicate that
       // this code is not reachable.  FIXME: We could insert unreachable
       // instruction directly because we can modify the CFG.
       auto *NewS = new StoreInst(UndefValue::get(Int8Ty),
                                  Constant::getNullValue(Int8Ty->getPointerTo()),
                                  IntrinsicI);
       if (MSSAU) {
+        const MemoryUseOrDef *FirstNonDom = nullptr;
+        const auto *AL =
+            MSSAU->getMemorySSA()->getBlockAccesses(IntrinsicI->getParent());
+
+        // If there are accesses in the current basic block, find the first one
+        // that does not come before NewS. The new memory access is inserted
+        // after the found access or before the terminator if no such access is
+        // found.
+        if (AL) {
+          for (auto &Acc : *AL) {
+            if (auto *Current = dyn_cast<MemoryUseOrDef>(&Acc))
+              if (!Current->getMemoryInst()->comesBefore(NewS)) {
+                FirstNonDom = Current;
+                break;
+              }
+          }
+        }
+
         // This added store is to null, so it will never executed and we can
         // just use the LiveOnEntry def as defining access.
-        auto *NewDef = MSSAU->createMemoryAccessInBB(
-            NewS, MSSAU->getMemorySSA()->getLiveOnEntryDef(), NewS->getParent(),
-            MemorySSA::BeforeTerminator);
-        MSSAU->insertDef(cast<MemoryDef>(NewDef), /*RenameUses=*/true);
+        auto *NewDef =
+            FirstNonDom ? MSSAU->createMemoryAccessBefore(
+                              NewS, MSSAU->getMemorySSA()->getLiveOnEntryDef(),
+                              const_cast<MemoryUseOrDef *>(FirstNonDom))
+                        : MSSAU->createMemoryAccessInBB(
+                              NewS, MSSAU->getMemorySSA()->getLiveOnEntryDef(),
+                              NewS->getParent(), MemorySSA::BeforeTerminator);
+
+        MSSAU->insertDef(cast<MemoryDef>(NewDef), /*RenameUses=*/false);
       }
     }
     if (isAssumeWithEmptyBundle(*IntrinsicI))
       markInstructionForDeletion(IntrinsicI);
     return false;
   } else if (isa<Constant>(V)) {
     // If it's not false, and constant, it must evaluate to true. This means our
     // assume is assume(true), and thus, pointless, and we don't want to do

llvm/test/Transforms/GVN/preserve-memoryssa.ll

 for.body830:
   %lv.2 = load volatile i32, i32* %ptr.0, align 8
   call void @use(i32 %lv.2)
   br label %for.body.i22
 
 for.body.i22:
   ret i32 1
 }
+
+define void @test_assume_false_to_store_undef_1(i32* %ptr) {
+; CHECK-LABEL: @test_assume_false_to_store_undef_1(
+; CHECK-NEXT:    store i32 10, i32* [[PTR:%.*]], align 4
+; CHECK-NEXT:    store i8 undef, i8* null, align 1
+; CHECK-NEXT:    call void @f()
+; CHECK-NEXT:    ret void
+;
+  store i32 10, i32* %ptr
+  %tobool = icmp ne i16 1, 0
+  %xor = xor i1 %tobool, true
+  call void @llvm.assume(i1 %xor)
+  call void @f()
+  ret void
+}
+
+define i32 @test_assume_false_to_store_undef_2(i32* %ptr, i32* %ptr.2) {
+; CHECK-LABEL: @test_assume_false_to_store_undef_2(
+; CHECK-NEXT:    store i32 10, i32* [[PTR:%.*]], align 4
+; CHECK-NEXT:    [[LV:%.*]] = load i32, i32* [[PTR_2:%.*]], align 4
+; CHECK-NEXT:    store i8 undef, i8* null, align 1
+; CHECK-NEXT:    call void @f()
+; CHECK-NEXT:    ret i32 [[LV]]
+;
+  store i32 10, i32* %ptr
+  %lv = load i32, i32* %ptr.2
+  %tobool = icmp ne i16 1, 0
+  %xor = xor i1 %tobool, true
+  call void @llvm.assume(i1 %xor)
+  call void @f()
+  ret i32 %lv
+}
+
+define i32 @test_assume_false_to_store_undef_3(i32* %ptr, i32* %ptr.2) {
+; CHECK-LABEL: @test_assume_false_to_store_undef_3(
+; CHECK-NEXT:    store i32 10, i32* [[PTR:%.*]], align 4
+; CHECK-NEXT:    [[LV:%.*]] = load i32, i32* [[PTR_2:%.*]], align 4
+; CHECK-NEXT:    store i8 undef, i8* null, align 1
+; CHECK-NEXT:    ret i32 [[LV]]
+;
+  store i32 10, i32* %ptr
+  %lv = load i32, i32* %ptr.2
+  %tobool = icmp ne i16 1, 0
+  %xor = xor i1 %tobool, true
+  call void @llvm.assume(i1 %xor)
+  ret i32 %lv
+}
+
+declare void @f()
+
+declare void @llvm.assume(i1 noundef) #0
+
+attributes #0 = { nofree nosync nounwind willreturn }