[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

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

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

s/dyn_cast/cast/ please

also please sink into the if condition

1103

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.

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);

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:
   //
   // 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.
+
+  // Above rule 1. is broken by having 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. This only happens in the
+  // presence of unreachable blocks.
+  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) {
+        MemoryPhi *Phi = dyn_cast_or_null<MemoryPhi>(MP);
+        if (Phi)
+          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,
 
   // 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);
   else
     insertUse(cast<MemoryUse>(What));
 
   // 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) {

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())

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
+
+}
+