[MemorySSA] Rename uses when inserting memory uses.

[asbirlea]

Summary

When inserting uses from outside the MemorySSA creation, we don't
normally need to rename uses, based on the assumption that there will be
no inserted Phis (if Def existed that required a Phi, that Phi already
exists). However, when dealing with unreachable blocks, MemorySSA will
optimize away Phis whose incoming blocks are unreachable, and these Phis end
up being re-added when inserting a Use.
There are two potential solutions here:

1. Analyze the inserted Phis and clean them up if they are unneeded

(current method for cleaning up trivial phis does not cover this)

2. Leave the Phi in place and rename uses, the same way as whe inserting

defs.
This patch use approach 2.

Resolves first test in PR42940.

[asbirlea]

Note: this is incomplete.

We can always have Phis with LoE coming from unreachable blocks, but when doing an insertDef, we replace all uses of the previous def with self. If that def is LoE, we'll end up replacing the incoming value from those unreachable blocks too. So the verification of "if incoming from unreachable, then it must be LoE is too strict".

With this restriction lifted, there is still a failure from the original PR. I will update once I have the fix for that.

[asbirlea]

Updated move call to also rename Uses.
Removed asserts checking against LoE.
Added two more reduced tests.

[asbirlea]

Rebase on ToT.

[george.burgess.iv]

lgtm with a few nits. Thanks!

lib/Analysis/MemorySSAUpdater.cpp

233 ↗

(On Diff #214866)

nit: can we please add a bit to the comment above instead of immediately contradicting it? e.g.

"In cases without unreachable blocks, because uses do not create new may-defs, there are only two cases: [...]"

"In cases with unreachable blocks, where the unnecessary Phis were optimized out, adding the Use [...]"

237 ↗

(On Diff #214866)

Is there a cheap way to assert that no renaming needs to be done if RenameUses == false?

Even if it might fail to catch some cases, if we can do something as simple as if (!RenameUses && !InsertedPHIs.empty()) assert(TheBBContainingMUHasNoDefsExceptForThisPhi); that can catch trivial misuses might be valuable.

253 ↗

(On Diff #214866)

s/dyn_cast/cast/ please

also please sink into the if condition

1103 ↗

(On Diff #214866)

nit: /*RenameUses=*/

[asbirlea]

Address comments.

[asbirlea]

Remove verification assert when incoming value from unreachable can be any access.
Add additional test which showcases the above.

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

public:
   /// Moving the store into the if block, and calling insertDef, does not
   /// require RenameUses.
   /// However, changing it to:
   /// store a
   /// if (foo) { store b }
   /// load a
   /// Where a mayalias b, *does* require RenameUses be set to true.
   void insertDef(MemoryDef *Def, bool RenameUses = false);
-  void insertUse(MemoryUse *Use);
+  void insertUse(MemoryUse *Use, bool RenameUses = false);
   /// Update the MemoryPhi in `To` following an edge deletion between `From` and
   /// `To`. If `To` becomes unreachable, a call to removeBlocks should be made.
   void removeEdge(BasicBlock *From, BasicBlock *To);
   /// Update the MemoryPhi in `To` to have a single incoming edge from `From`,
   /// following a CFG change that replaced multiple edges (switch) with a direct
   /// branch.
   void removeDuplicatePhiEdgesBetween(const BasicBlock *From,
                                       const BasicBlock *To);

llvm/trunk/lib/Analysis/MemorySSA.cpp

 #ifndef NDEBUG
   for (const BasicBlock &BB : F) {
     if (MemoryPhi *Phi = getMemoryAccess(&BB)) {
       for (unsigned I = 0, E = Phi->getNumIncomingValues(); I != E; ++I) {
         auto *Pred = Phi->getIncomingBlock(I);
         auto *IncAcc = Phi->getIncomingValue(I);
         // If Pred has no unreachable predecessors, get last def looking at
         // IDoms. If, while walkings IDoms, any of these has an unreachable
-        // predecessor, then the expected incoming def is LoE.
+        // predecessor, then the incoming def can be any access.
         if (auto *DTNode = DT->getNode(Pred)) {
           while (DTNode) {
             if (auto *DefList = getBlockDefs(DTNode->getBlock())) {
               auto *LastAcc = &*(--DefList->end());
               assert(LastAcc == IncAcc &&
                      "Incorrect incoming access into phi.");
               break;
             }
             DTNode = DTNode->getIDom();
           }
-        } else if (auto *DefList = getBlockDefs(Pred)) {
+        } else {
           // If Pred has unreachable predecessors, but has at least a Def, the
           // incoming access can be the last Def in Pred, or it could have been
-          // optimized to LoE.
-          auto *LastAcc = &*(--DefList->end());
-          assert((LastAcc == IncAcc || IncAcc == getLiveOnEntryDef()) &&
-                 "Incorrect incoming access into phi.");
-        } else {
+          // optimized to LoE. After an update, though, the LoE may have been
+          // replaced by another access, so IncAcc may be any access.
           // If Pred has unreachable predecessors and no Defs, incoming access
-          // should be LoE; In practice, after an update, it may be any access.
+          // should be LoE; However, after an update, it may be any access.
         }
       }
     }
   }
 #endif
 }
 
 /// Verify that all of the blocks we believe to have valid domination numbers

llvm/trunk/lib/Analysis/MemorySSAUpdater.cpp

if (Phi) {
     removeMemoryAccess(Phi);
   }
 
   // We should only end up recursing in case we replaced something, in which
   // case, we may have made other Phis trivial.
   return recursePhi(Same);
 }
 
-void MemorySSAUpdater::insertUse(MemoryUse *MU) {
+void MemorySSAUpdater::insertUse(MemoryUse *MU, bool RenameUses) {
   InsertedPHIs.clear();
   MU->setDefiningAccess(getPreviousDef(MU));
-  // Unlike for defs, there is no extra work to do.  Because uses do not create
-  // new may-defs, there are only two cases:
-  //
+  // In cases without unreachable blocks, because uses do not create new
+  // may-defs, there are only two cases:
   // 1. There was a def already below us, and therefore, we should not have
   // created a phi node because it was already needed for the def.
   //
   // 2. There is no def below us, and therefore, there is no extra renaming work
   // to do.
+
+  // In cases with unreachable blocks, where the unnecessary Phis were
+  // optimized out, adding the Use may re-insert those Phis. Hence, when
+  // inserting Uses outside of the MSSA creation process, and new Phis were
+  // added, rename all uses if we are asked.
+
+  if (!RenameUses && !InsertedPHIs.empty()) {
+    auto *Defs = MSSA->getBlockDefs(MU->getBlock());
+    (void)Defs;
+    assert((!Defs || (++Defs->begin() == Defs->end())) &&
+           "Block may have only a Phi or no defs");
+  }
+
+  if (RenameUses && InsertedPHIs.size()) {
+    SmallPtrSet<BasicBlock *, 16> Visited;
+    BasicBlock *StartBlock = MU->getBlock();
+
+    if (auto *Defs = MSSA->getWritableBlockDefs(StartBlock)) {
+      MemoryAccess *FirstDef = &*Defs->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(MU->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)
+        if (MemoryPhi *Phi = cast_or_null<MemoryPhi>(MP))
+          MSSA->renamePass(Phi->getBlock(), nullptr, Visited);
+    }
+  }
 }
 
 // Set every incoming edge {BB, MP->getBlock()} of MemoryPhi MP to NewDef.
 static void setMemoryPhiValueForBlock(MemoryPhi *MP, const BasicBlock *BB,
                                       MemoryAccess *NewDef) {
   // Replace any operand with us an incoming block with the new defining
   // access.
   int i = MP->getBasicBlockIndex(BB);
void MemorySSAUpdater::moveTo(MemoryUseOrDef *What, BasicBlock *BB,
   // 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, true);
+    insertDef(MD, /*RenameUses=*/true);
   else
-    insertUse(cast<MemoryUse>(What));
+    insertUse(cast<MemoryUse>(What), /*RenameUses=*/true);
 
   // Clear dangling pointers. We added all MemoryPhi users, but not all
   // of them are removed by fixupDefs().
   NonOptPhis.clear();
 }
 
 // Move What before Where in the MemorySSA IR.
 void MemorySSAUpdater::moveBefore(MemoryUseOrDef *What, MemoryUseOrDef *Where) {

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

if (MSSAU && (OldMemAcc = MSSAU->getMemorySSA()->getMemoryAccess(&I))) {
     // Create a new MemoryAccess and let MemorySSA set its defining access.
     MemoryAccess *NewMemAcc = MSSAU->createMemoryAccessInBB(
         New, nullptr, New->getParent(), MemorySSA::Beginning);
     if (NewMemAcc) {
       if (auto *MemDef = dyn_cast<MemoryDef>(NewMemAcc))
         MSSAU->insertDef(MemDef, /*RenameUses=*/true);
       else {
         auto *MemUse = cast<MemoryUse>(NewMemAcc);
-        MSSAU->insertUse(MemUse);
+        MSSAU->insertUse(MemUse, /*RenameUses=*/true);
       }
     }
   }
 
   // Build LCSSA PHI nodes for any in-loop operands. Note that this is
   // particularly cheap because we can rip off the PHI node that we're
   // replacing for the number and blocks of the predecessors.
   // OPT: If this shows up in a profile, we can instead finish sinking all
if (AATags)
     PreheaderLoad->setAAMetadata(AATags);
   SSA.AddAvailableValue(Preheader, PreheaderLoad);
 
   MemoryAccess *PreheaderLoadMemoryAccess;
   if (MSSAU) {
     PreheaderLoadMemoryAccess = MSSAU->createMemoryAccessInBB(
         PreheaderLoad, nullptr, PreheaderLoad->getParent(), MemorySSA::End);
     MemoryUse *NewMemUse = cast<MemoryUse>(PreheaderLoadMemoryAccess);
-    MSSAU->insertUse(NewMemUse);
+    MSSAU->insertUse(NewMemUse, /*RenameUses=*/true);
   }
 
+  if (MSSAU && VerifyMemorySSA)
+    MSSAU->getMemorySSA()->verifyMemorySSA();
   // 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())

llvm/trunk/test/Analysis/MemorySSA/PR42940.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 = "s390x-ibm-linux"
+
+@g_77 = external dso_local global i16, align 2
+
+; CHECK-LABEL: @f1()
+define void @f1() {
+entry:
+  store i16 undef, i16* @g_77, align 2
+  br label %loop_pre
+
+unreachablelabel: ; No predecessors
+  br label %loop_pre
+
+loop_pre:
+  br label %for.cond.header
+
+for.cond.header:
+  store i32 0, i32* undef, align 4
+  br i1 undef, label %for.body, label %for.end
+
+for.body:
+  %tmp1 = load volatile i16, i16* undef, align 2
+  br label %for.end
+
+for.end:
+  br i1 undef, label %func.exit, label %for.cond.header
+
+func.exit:
+  ret void
+}
+
+@g_159 = external dso_local global i32, align 4
+
+; CHECK-LABEL: @f2()
+define void @f2() {
+entry:
+  br label %for.header.first
+
+for.header.first:
+  br label %for.body.first
+
+for.body.first:
+  store i32 0, i32* @g_159, align 4
+  br i1 undef, label %for.body.first, label %for.end.first
+
+for.end.first:
+  br i1 undef, label %lor.end, label %for.header.first
+
+lor.end:
+  br label %for.pre
+
+unreachablelabel: ; No predecessors
+  br label %for.pre
+
+for.pre:
+  br label %for.header.second
+
+for.header.second:
+  store i32 undef, i32* undef, align 4
+  br label %for.header.second
+}
+
+@g_271 = external dso_local global i8, align 2
+@g_427 = external dso_local unnamed_addr global [9 x i16], align 2
+
+; CHECK-LABEL: @f3()
+define  void @f3() {
+entry:
+  br label %for.preheader
+
+for.preheader:
+  store volatile i8 undef, i8* @g_271, align 2
+  br i1 undef, label %for.preheader, label %for.end
+
+for.end:
+  br label %lbl_1058.i
+
+unreachablelabel: ; No predecessors
+  br label %lbl_1058.i
+
+lbl_1058.i:
+  br label %for.cond3.preheader.i
+
+for.cond3.preheader.i:
+  %tmp1 = load i16, i16* getelementptr inbounds ([9 x i16], [9 x i16]* @g_427, i64 0, i64 2), align 2
+  %conv620.i129 = zext i16 %tmp1 to i32
+  %cmp621.i130 = icmp ugt i32 undef, %conv620.i129
+  %conv622.i131 = zext i1 %cmp621.i130 to i32
+  store i32 %conv622.i131, i32* undef, align 4
+  br i1 undef, label %func.exit, label %for.cond3.preheader.i
+
+func.exit:
+  ret void
+}
+
+@g_6 = external dso_local unnamed_addr global [3 x i32], align 4
+@g_244 = external dso_local global i64, align 8
+@g_1164 = external dso_local global i64, align 8
+
+; CHECK-LABEL: @f4()
+define void @f4() {
+entry:
+  br label %for.cond8.preheader
+
+for.cond8.preheader:
+  store i32 0, i32* getelementptr inbounds ([3 x i32], [3 x i32]* @g_6, i64 0, i64 2), align 4
+  br i1 undef, label %if.end, label %for.cond8.preheader
+
+if.end:
+  br i1 undef, label %cleanup1270, label %for.cond504.preheader
+
+for.cond504.preheader:
+  store i64 undef, i64* @g_244, align 8
+  br label %cleanup1270
+
+for.cond559.preheader:
+  store i64 undef, i64* @g_1164, align 8
+  br i1 undef, label %for.cond559.preheader, label %cleanup1270
+
+cleanup1270:
+  ret void
+}
+