[MemorySSA] Extend allowed behavior for simplified instructions.

[asbirlea]

Summary

LoopRotate may simplify instructions, leading to the new instructions not having memory accesses created for them.
Allow this behavior, by allowing the new access to be null when the template is null, and looking upwards for the proper defined access when dealing with simplified instructions.

[george.burgess.iv]

Thanks for this! Two nits and a question

lib/Analysis/MemorySSAUpdater.cpp

487

nit: if it's straightforward to turn this into a static helper, please do so.

538

NewUseOrDef should always be non-null, no?

test/Analysis/MemorySSA/loop-rotate-simplified-clone.ll

2

; REQUIRES: asserts

[asbirlea]

Address comments.

lib/Analysis/MemorySSAUpdater.cpp

538

No, this can now be null.
Say we have a simplified instruction such that the clone is not a MemoryAccess. We pass the Template as nullptr to createDefinedAccess, and inside it we call createNewAccess which will return nullptr. Since we didn't pass a Template, the assertion won't hit, i.e. once the instruction is simplified we cannot rely on the Template info, and we can no longer assume we will actually create a MemoryAccess.
Does this make sense?

[george.burgess.iv]

lib/Analysis/MemorySSA.cpp

1690

This new optionality is surprising to me, and I think something that's not generally desirable for users of this function. Would it make sense to refactor this slightly into something like tryCreateDefinedAccess and createDefinedAccess? (the try version being the body of this function without the assert(NewAccess != nullptr), and the create literally just being try + the assert)

Alternatively, I'd be happy with an added bool CreationMustSucceed = true param that stands in for the new if (Template) conditional, if you feel that's better.

lib/Analysis/MemorySSAUpdater.cpp

538

Oh, right. I was looking at my source without the patch applied when thinking about this question. This is what I get for reviewing CLs late -- sorry. :)

[asbirlea]

Added optional bool CreationMustSucceed.

[george.burgess.iv]

Thanks!

lib/Analysis/MemorySSA.cpp

MemoryPhi *MemorySSA::createMemoryPhi(BasicBlock *BB) {
   // Phi's always are placed at the front of the block.
   insertIntoListsForBlock(Phi, BB, Beginning);
   ValueToMemoryAccess[BB] = Phi;
   return Phi;
 }
 
 MemoryUseOrDef *MemorySSA::createDefinedAccess(Instruction *I,
                                                MemoryAccess *Definition,
                                                const MemoryUseOrDef *Template) {
   assert(!isa<PHINode>(I) && "Cannot create a defined access for a PHI");
   MemoryUseOrDef *NewAccess = createNewAccess(I, AA, Template);
-  assert(
-      NewAccess != nullptr &&
-      "Tried to create a memory access for a non-memory touching instruction");
+  if (Template)
+    assert(NewAccess != nullptr && "Tried to create a memory access for a "
+                                   "non-memory touching instruction");
+  if (NewAccess)
     NewAccess->setDefiningAccess(Definition);
   return NewAccess;
 }
 
 // Return true if the instruction has ordering constraints.
 // Note specifically that this only considers stores and loads
 // because others are still considered ModRef by getModRefInfo.
 static inline bool isOrdered(const Instruction *I) {
   if (auto *SI = dyn_cast<StoreInst>(I)) {

lib/Analysis/MemorySSAUpdater.cpp

if (MPhi->getNumIncomingValues() == 1)
       removeMemoryAccess(MPhi);
   }
 }
 
 void MemorySSAUpdater::cloneUsesAndDefs(BasicBlock *BB, BasicBlock *NewBB,
                                         const ValueToValueMapTy &VMap,
                                         PhiToDefMap &MPhiMap,
                                         bool CloneWasSimplified) {
-  auto GetNewDefiningAccess = [&](MemoryAccess *MA) -> MemoryAccess * {
+  std::function<MemoryAccess *(MemoryAccess *)> GetNewDefiningAccess =
+      [&](MemoryAccess *MA) -> MemoryAccess * {
     MemoryAccess *InsnDefining = MA;
-    if (MemoryUseOrDef *DefMUD = dyn_cast<MemoryUseOrDef>(InsnDefining)) {
+    if (MemoryDef *DefMUD = dyn_cast<MemoryDef>(InsnDefining)) {
       if (!MSSA->isLiveOnEntryDef(DefMUD)) {
         Instruction *DefMUDI = DefMUD->getMemoryInst();
         assert(DefMUDI && "Found MemoryUseOrDef with no Instruction.");
         if (Instruction *NewDefMUDI =
-                cast_or_null<Instruction>(VMap.lookup(DefMUDI)))
+                cast_or_null<Instruction>(VMap.lookup(DefMUDI))) {
           InsnDefining = MSSA->getMemoryAccess(NewDefMUDI);
+          if (!CloneWasSimplified)
+            assert(InsnDefining && "Defining instruction cannot be nullptr.");
+          else if (!InsnDefining || isa<MemoryUse>(InsnDefining)) {
+            // The clone was simplified, it's no longer a MemoryDef, look up.
+            auto DefIt = DefMUD->getDefsIterator();
+            // Since simplified clones only occur in single block cloning, a
+            // previous definition must exist, otherwise NewDefMUDI would not
+            // have been found in VMap.
+            assert(DefIt != MSSA->getBlockDefs(DefMUD->getBlock())->begin() &&
+                   "Previous def must exist");
+            InsnDefining = GetNewDefiningAccess(&*(--DefIt));
+          }
+        }
       }
     } else {
       MemoryPhi *DefPhi = cast<MemoryPhi>(InsnDefining);
       if (MemoryAccess *NewDefPhi = MPhiMap.lookup(DefPhi))
         InsnDefining = NewDefPhi;
     }
     assert(InsnDefining && "Defining instruction cannot be nullptr.");
     return InsnDefining;
if (const MemoryUseOrDef *MUD = dyn_cast<MemoryUseOrDef>(&MA)) {
       // Also in LoopRotate, even when it's an instruction, due to it being
       // simplified, it may be a Use rather than a Def, so we cannot use MUD as
       // template. Calls coming from updateForClonedBlockIntoPred, ensure this.
       if (Instruction *NewInsn =
               dyn_cast_or_null<Instruction>(VMap.lookup(Insn))) {
         MemoryAccess *NewUseOrDef = MSSA->createDefinedAccess(
             NewInsn, GetNewDefiningAccess(MUD->getDefiningAccess()),
             CloneWasSimplified ? nullptr : MUD);
+        if (NewUseOrDef)
           MSSA->insertIntoListsForBlock(NewUseOrDef, NewBB, MemorySSA::End);
       }
     }
   }
 }
 
 void MemorySSAUpdater::updatePhisWhenInsertingUniqueBackedgeBlock(
     BasicBlock *Header, BasicBlock *Preheader, BasicBlock *BEBlock) {
   auto *MPhi = MSSA->getMemoryAccess(Header);

test/Analysis/MemorySSA/loop-rotate-simplified-clone.ll

+; RUN: opt -verify-memoryssa -enable-mssa-loop-dependency -loop-rotate %s -S | FileCheck %s 
+
+; CHECK-LABEL: @test()
+define dso_local void @test() {
+entry:
+  br label %preheader
+
+preheader:
+  br label %l39
+
+l39:
+  %v40 = phi float (float)* [ @foo, %preheader ], [ %v43, %crit_edge ]
+  %v41 = call float %v40(float undef)
+  %v42 = load i32, i32* undef, align 8
+  br i1 undef, label %crit_edge, label %loopexit
+
+crit_edge:
+  %v43 = load float (float)*, float (float)** undef, align 8
+  br label %l39
+
+loopexit:
+  unreachable
+}
+
+; Function Attrs: readnone
+declare dso_local float @foo(float) #0 align 32
+
+attributes #0 = { readnone }