[MemorySSA] Make insertDef insert corresponding phi nodes.

[asbirlea]

Summary

The original assumption for the insertDef method was that it would not
materialize Defs out of no-where, hence it will not insert phis needed
after inserting a Def.

However, when cloning an instruction (use case used in LICM), we do
materialize Defs "out of no-where". If the block receiving a Def has at
least one other Def, then no processing is needed. If the block just
received its first Def, we must check where Phi placement is needed.
The only new usage of insertDef is in LICM, hence the trigger for the bug.

But the original goal of the method also fails to apply for the move()
method. If we move a Def from the entry point of a diamond to either the
left or right blocks, then the merge block must add a phi.
While this usecase does not currently occur, or may be viewed as an
incorrect transformation, MSSA must behave corectly given the scenario.

Resolves PR40749 and PR40754.

[asbirlea]

Nit: add missed CHECK in test.

[george.burgess.iv]

Thanks for this!

lib/Analysis/MemorySSAUpdater.cpp

274 ↗

(On Diff #188272)

It's unclear to me why this is necessary. We keep an OptimizedID in MemoryDefs to catch these kinds of movements and transparently invalidate the cached optimized Access in those cases. Does that not work here?

(It also seems sort of unrelated to this patch, unless I'm missing something?)

301 ↗

(On Diff #188272)

nit: I think there's a general preference for preincrement when the difference doesn't matter.

319 ↗

(On Diff #188272)

This was pretty tricky for me to reason about. If you're 100% certain that all of this is correct, feel free to leave this as is. Otherwise, can we please shuffle these new InsertedPhis into an intermediate SmallVector<AssertingVH<MemoryPhi>, N>? The idea would be to keep them there, loop over the new SmallVector, and transfer them into InsertedPhis after the for (auto *Pred : predecessors) loop below.

Sharing my work anyway:

getPreviousDefFromEnd is interesting here, since it'll *also* do Phi insertion/population/trivial removal.

I think we should be fine on the population bit: it only ever calls getPreviousDefFromEnd, so existing Phis should never be stomped by it.

Similarly, insertion should be OK, since it only inserts a Phi when we reach a cycle, and the set of Phis should be relatively complete with the ones we've just added.

Trivial removal is a bit more tricky. You can totally make it recurse on a trivial Phi we've just created. The fun bit is that it only recurses on the *Users* of the value we're replacing a Phi with. So the question is whether we can end up in a world with a partially-formed Phi (e.g. we add one pred of IDFPhi, so IDFPhi is now a User, and thus a candidate for trivial deletion). I don't *think* that should be a problem, since we should have a complete and minimal (modulo the Phis we're in the process of inserting) set of Phis at this point. Since getPreviousDefRecursive guarantees minimality in most cases(*), I don't see how we can be handed a trivial Phi to put in the Incoming list for this.

(*) - The other cases result from irreducible control flow. That's technically nonminimal, but AFAICT it's a nonminimal form that we won't trivially eliminate later on, so...

322 ↗

(On Diff #188272)

nit: Would it make sense to hoist this out of one (or both?) loops? Seems like sharing work between getPreviousDefFromEnd invocations is harmless.

341 ↗

(On Diff #188272)

Why are we looping over all of the InsertedPhis? Shouldn't this just be the subset of them that we added as a part of the IDF stuff above? (Any Phis we add as a part of getPreviousDef should already be minimal, AIUI)

342 ↗

(On Diff #188272)

nit: should this be cast_or_null? WeakVH doesn't track across RAUWs IIRC

Please also bring this into the if (...)

test/Analysis/MemorySSA/pr40749.ll

1 ↗

(On Diff #188272)

; REQUIRES: asserts?

[asbirlea]

Address comments.

[asbirlea]

lib/Analysis/MemorySSAUpdater.cpp

274 ↗

(On Diff #188272)

IIUC, if we have a def, let's call it DefLower, that is optimized to DefBefore replaced here, then DefLower maintains a field: operator 1, pointing to the optimized access), making it a user of DefBefore. If we replace that user with MD, we're optimized DefLower to MD, which may not be correct. Calling resetOptimized will also remove the optimized user. This relates to D56467.

Yes, it's unrelated to this patch, I noticed it when making the changes below and added the change. I can split it up if you prefer it.

319 ↗

(On Diff #188272)

I *think* I followed the guidelines you outlined. All newly inserted phis are kept separate while calling the recursive getPreviousDef, and removing non-minimal phis is only done of these new phis.
Please let me know if I missed anything.

[george.burgess.iv]

lib/Analysis/MemorySSAUpdater.cpp

285 ↗

(On Diff #188452)

Please sink NewInsertedPhis into the if (Iter == IterEnd) { block (removing the trivial Phis later on in this function may invalidate them; I haven't reasoned about whether or not this'll actually happen, but I can't see why we'd care about the guarantee that that doesn't happen, so ...)

344 ↗

(On Diff #188452)

Please grab the value for IdxE before the FixupList.empty() loop above; that can add Phis, and it shouldn't be profitable to try to remove them (or if it is, it'd be nice to have an explicit example of where that can happen...)

274 ↗

(On Diff #188272)

If we replace that user with MD, we're optimized DefLower to MD, which may not be correct

You're totally correct. isOptimized() isn't just bit, though: it should be verifying that getOptimized()->getID() == SomeCachedIDInTheMemoryDef. In this case, that test won't pass, so the MemoryDef in question should be considered unoptimized.

Calling resetOptimized will also remove the optimized user. This relates to D56467.

Looking at D56467 again, that sounds like broken verification code more than anything. We lazily invalidate caches for Uses (e.g. a Use's DefiningAccess); I don't see why we should treat Defs any differently. Sorry for not catching that earlier.

If we wanna land this change now and fix the verification later, I'm OK with that. But for all intents and purposes, Uses that originate from MemoryDefs' OptimizedAccesses shouldn't be treated as Uses unless the MemoryDef still reports itself to be optimized.

...If we find ourselves iterating over the Users of MemoryDefs often, it may be worth making an iterator that skips invalidated Users. IDK whether that's a common use-case (pun intended) or not, though.

I can split it up if you prefer it.

It's small enough that I'm OK with bundling it. I was just making sure it wasn't related in a way that I was missing

319 ↗

(On Diff #188272)

Yup :)

[asbirlea]

Address comments.

lib/Analysis/MemorySSAUpdater.cpp

285 ↗

(On Diff #188452)

You're right, I meant to clear it after adding to InsertedPhis, but sinking to reduce its scope is better!

274 ↗

(On Diff #188272)

You're right that replacing the Def should make the user unoptimized due to the different IDs. Removing the change, and I'll see if I can find the test that failed the verification in the previous patch. Arbitrary insertions may trigger a verification failure from here as well.

322 ↗

(On Diff #188272)

Yes...but I'd rather not do it here. The current code seems convoluted enough that I'd do any refactoring change separate.

[george.burgess.iv]

Thanks again!

llvm/trunk/lib/Analysis/MemorySSAUpdater.cpp

void MemorySSAUpdater::insertDef(MemoryDef *MD, bool RenameUses) {
   if (DefBeforeSameBlock) {
     for (auto UI = DefBefore->use_begin(), UE = DefBefore->use_end();
          UI != UE;) {
       Use &U = *UI++;
       // Leave the MemoryUses alone.
       // Also make sure we skip ourselves to avoid self references.
       if (isa<MemoryUse>(U.getUser()) || U.getUser() == MD)
         continue;
+      // Defs are automatically unoptimized when the user is set to MD below,
+      // because the isOptimized() call will fail to find the same ID.
       U.set(MD);
     }
   }
 
   // and that def is now our defining access.
   MD->setDefiningAccess(DefBefore);
 
+  // Remember the index where we may insert new phis below.
+  unsigned NewPhiIndex = InsertedPHIs.size();
+
   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.
+
+    // If this is the first def in the block and this insert is in an arbitrary
+    // place, compute IDF and place phis.
+    auto Iter = MD->getDefsIterator();
+    ++Iter;
+    auto IterEnd = MSSA->getBlockDefs(MD->getBlock())->end();
+    if (Iter == IterEnd) {
+      ForwardIDFCalculator IDFs(*MSSA->DT);
+      SmallVector<BasicBlock *, 32> IDFBlocks;
+      SmallPtrSet<BasicBlock *, 2> DefiningBlocks;
+      DefiningBlocks.insert(MD->getBlock());
+      IDFs.setDefiningBlocks(DefiningBlocks);
+      IDFs.calculate(IDFBlocks);
+      SmallVector<AssertingVH<MemoryPhi>, 4> NewInsertedPHIs;
+      for (auto *BBIDF : IDFBlocks)
+        if (!MSSA->getMemoryAccess(BBIDF))
+          NewInsertedPHIs.push_back(MSSA->createMemoryPhi(BBIDF));
+
+      for (auto &MPhi : NewInsertedPHIs) {
+        auto *BBIDF = MPhi->getBlock();
+        for (auto *Pred : predecessors(BBIDF)) {
+          DenseMap<BasicBlock *, TrackingVH<MemoryAccess>> CachedPreviousDef;
+          MPhi->addIncoming(getPreviousDefFromEnd(Pred, CachedPreviousDef),
+                            Pred);
+        }
+      }
+
+      // Re-take the index where we're adding the new phis, because the above
+      // call to getPreviousDefFromEnd, may have inserted into InsertedPHIs.
+      NewPhiIndex = InsertedPHIs.size();
+      for (auto &MPhi : NewInsertedPHIs) {
+        InsertedPHIs.push_back(&*MPhi);
+        FixupList.push_back(&*MPhi);
+      }
+    }
+
     FixupList.push_back(MD);
   }
 
+  // Remember the index where we stopped inserting new phis above, since the
+  // fixupDefs call in the loop below may insert more, that are already minimal.
+  unsigned NewPhiIndexEnd = InsertedPHIs.size();
+
   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());
   }
+
+  // Optimize potentially non-minimal phis added in this method.
+  for (unsigned Idx = NewPhiIndex; Idx < NewPhiIndexEnd; ++Idx) {
+    if (auto *MPhi = cast_or_null<MemoryPhi>(InsertedPHIs[Idx])) {
+      auto OperRange = MPhi->operands();
+      tryRemoveTrivialPhi(MPhi, OperRange);
+    }
+  }
+
   // 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

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

if (MSSAU) {
     MemoryUse *NewMemUse = cast<MemoryUse>(PreheaderLoadMemoryAccess);
     MSSAU->insertUse(NewMemUse);
   }
 
   // Rewrite all the loads in the loop and remember all the definitions from
   // stores in the loop.
   Promoter.run(LoopUses);
 
+  if (MSSAU && VerifyMemorySSA)
+    MSSAU->getMemorySSA()->verifyMemorySSA();
   // If the SSAUpdater didn't use the load in the preheader, just zap it now.
   if (PreheaderLoad->use_empty())
     eraseInstruction(*PreheaderLoad, *SafetyInfo, CurAST, MSSAU);
 
   return true;
 }
 
 /// Returns an owning pointer to an alias set which incorporates aliasing info

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

+; RUN: opt -licm -enable-mssa-loop-dependency -verify-memoryssa -S < %s | FileCheck %s
+; REQUIRES: asserts
+
+target datalayout = "E-m:e-i1:8:16-i8:8:16-i64:64-f128:64-v128:64-a:8:16-n32:64"
+target triple = "systemz-unknown"
+
+@g_3 = external dso_local local_unnamed_addr global i32, align 4
+@g_57 = external dso_local local_unnamed_addr global i8, align 2
+@g_82 = external dso_local global [8 x i16], align 2
+@g_107 = external dso_local local_unnamed_addr global i32, align 4
+
+define internal fastcc void @foo1() unnamed_addr{
+; CHECK-LABEL: @foo1()
+entry:
+  %.pre.pre = load i32, i32* @g_3, align 4
+  br label %loop1
+
+loop1:
+  %tmp0 = phi i32 [ undef, %entry ], [ %var18.lcssa, %loopexit ]
+  br label %preheader
+
+preheader:
+  %indvars.iv = phi i64 [ 0, %loop1 ], [ %indvars.iv.next, %loop6 ]
+  %phi18 = phi i32 [ %tmp0, %loop1 ], [ 0, %loop6 ]
+  %phi87 = phi i32 [ 0, %loop1 ], [ %tmp7, %loop6 ]
+  %tmp1 = getelementptr inbounds [8 x i16], [8 x i16]* @g_82, i64 0, i64 %indvars.iv
+  %tmp2 = load i16, i16* %tmp1, align 2
+  %tmp3 = trunc i16 %tmp2 to i8
+  store i8 %tmp3, i8* @g_57, align 2
+  store i32 8, i32* @g_107, align 4
+  %tmp4 = icmp eq i32 %.pre.pre, 0
+  %spec.select = select i1 %tmp4, i32 %phi18, i32 14
+  %tmp5 = trunc i64 %indvars.iv to i32
+  switch i32 %spec.select, label %loopexit [
+    i32 0, label %loop6
+    i32 14, label %loop9
+  ]
+
+loop6:
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %tmp7 = add nuw nsw i32 %phi87, 1
+  %tmp8 = icmp ult i64 %indvars.iv.next, 6
+  br i1 %tmp8, label %preheader, label %loop9
+
+loop9:
+  %phi8.lcssa = phi i32 [ %tmp5, %preheader ], [ %tmp7, %loop6 ]
+  %tmp10 = trunc i32 %phi8.lcssa to i8
+  %tmp11 = tail call i16* @func_101(i16* getelementptr inbounds ([8 x i16], [8 x i16]* @g_82, i64 0, i64 6), i16* undef, i8 zeroext %tmp10)
+  unreachable
+
+loopexit:
+  %var18.lcssa = phi i32 [ %phi18, %preheader ]
+  br label %loop1
+
+}
+
+declare dso_local i16* @func_101(i16*, i16*, i8) local_unnamed_addr
+

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

+; RUN: opt -licm -enable-mssa-loop-dependency -verify-memoryssa -S < %s | FileCheck %s
+; REQUIRES: asserts
+
+target datalayout = "E-m:e-i1:8:16-i8:8:16-i64:64-f128:64-v128:64-a:8:16-n32:64"
+target triple = "systemz-unknown"
+
+@g_120 = external dso_local local_unnamed_addr global [8 x [4 x [6 x i32]]], align 4
+@g_185 = external dso_local local_unnamed_addr global i32, align 4
+@g_329 = external dso_local local_unnamed_addr global i16, align 2
+
+; Function Attrs: norecurse noreturn nounwind
+define dso_local void @func_65() local_unnamed_addr {
+; CHECK-LABEL: @func_65()
+  br label %1
+
+; <label>:1:                                      ; preds = %.thread, %0
+  br label %2
+
+; <label>:2:                                      ; preds = %.critedge, %1
+  br label %3
+
+; <label>:3:                                      ; preds = %5, %2
+  %storemerge = phi i32 [ 0, %2 ], [ %6, %5 ]
+  store i32 %storemerge, i32* @g_185, align 4
+  %4 = icmp ult i32 %storemerge, 2
+  br i1 %4, label %5, label %.thread.loopexit
+
+; <label>:5:                                      ; preds = %3
+  %6 = add i32 %storemerge, 1
+  %7 = zext i32 %6 to i64
+  %8 = getelementptr [8 x [4 x [6 x i32]]], [8 x [4 x [6 x i32]]]* @g_120, i64 0, i64 undef, i64 %7, i64 undef
+  %9 = load i32, i32* %8, align 4
+  %10 = icmp eq i32 %9, 0
+  br i1 %10, label %3, label %11
+
+; <label>:11:                                     ; preds = %5
+  %storemerge.lcssa4 = phi i32 [ %storemerge, %5 ]
+  %12 = icmp eq i32 %storemerge.lcssa4, 0
+  br i1 %12, label %.critedge, label %.thread.loopexit3
+
+.critedge:                                        ; preds = %11
+  store i16 0, i16* @g_329, align 2
+  br label %2
+
+.thread.loopexit:                                 ; preds = %3
+  br label %.thread
+
+.thread.loopexit3:                                ; preds = %11
+  br label %.thread
+
+.thread:                                          ; preds = %.thread.loopexit3, %.thread.loopexit
+  br label %1
+}
+

llvm/trunk/unittests/Analysis/MemorySSATest.cpp

TEST_F(MemorySSATest, CreateLoadsAndStoreUpdater) {
 
   // Create a store on the left
   // Add the store
   B.SetInsertPoint(Left, Left->begin());
   StoreInst *LeftStore = B.CreateStore(B.getInt8(16), PointerArg);
   MemoryAccess *LeftStoreAccess = Updater.createMemoryAccessInBB(
       LeftStore, nullptr, Left, MemorySSA::Beginning);
   Updater.insertDef(cast<MemoryDef>(LeftStoreAccess), false);
-  // We don't touch existing loads, so we need to create a new one to get a phi
+
+  // MemoryPHI should exist after adding LeftStore.
+  MP = MSSA.getMemoryAccess(Merge);
+  EXPECT_NE(MP, nullptr);
+
   // Add the second load
   B.SetInsertPoint(Merge, Merge->begin());
   LoadInst *SecondLoad = B.CreateLoad(B.getInt8Ty(), PointerArg);
 
-  // MemoryPHI should not already exist.
-  MP = MSSA.getMemoryAccess(Merge);
-  EXPECT_EQ(MP, nullptr);
-
   // Create the load memory access
   MemoryUse *SecondLoadAccess = cast<MemoryUse>(Updater.createMemoryAccessInBB(
       SecondLoad, nullptr, Merge, MemorySSA::Beginning));
   Updater.insertUse(SecondLoadAccess);
   // Now the load should be a phi of the entry store and the left store
   MemoryPhi *MergePhi =
       dyn_cast<MemoryPhi>(SecondLoadAccess->getDefiningAccess());
   EXPECT_NE(MergePhi, nullptr);
TEST_F(MemorySSATest, CreateALoadUpdater) {
   MemorySSAUpdater Updater(&MSSA);
   B.SetInsertPoint(Left, Left->begin());
   // Add the store
   StoreInst *SI = B.CreateStore(B.getInt8(16), PointerArg);
   MemoryAccess *StoreAccess =
       Updater.createMemoryAccessInBB(SI, nullptr, Left, MemorySSA::Beginning);
   Updater.insertDef(cast<MemoryDef>(StoreAccess));
 
+  // MemoryPHI should be created when inserting the def
+  MemoryPhi *MP = MSSA.getMemoryAccess(Merge);
+  EXPECT_NE(MP, nullptr);
+
   // Add the load
   B.SetInsertPoint(Merge, Merge->begin());
   LoadInst *LoadInst = B.CreateLoad(B.getInt8Ty(), PointerArg);
 
-  // MemoryPHI should not already exist.
-  MemoryPhi *MP = MSSA.getMemoryAccess(Merge);
-  EXPECT_EQ(MP, nullptr);
-
   // Create the load memory acccess
   MemoryUse *LoadAccess = cast<MemoryUse>(Updater.createMemoryAccessInBB(
       LoadInst, nullptr, Merge, MemorySSA::Beginning));
   Updater.insertUse(LoadAccess);
   MemoryAccess *DefiningAccess = LoadAccess->getDefiningAccess();
   EXPECT_TRUE(isa<MemoryPhi>(DefiningAccess));
   MSSA.verifyMemorySSA();
 }