[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 ↗

(On Diff #211961)

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

538 ↗

(On Diff #211961)

NewUseOrDef should always be non-null, no?

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

2 ↗

(On Diff #211961)

; REQUIRES: asserts

[asbirlea]

Address comments.

lib/Analysis/MemorySSAUpdater.cpp

538 ↗

(On Diff #211961)

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 ↗

(On Diff #212383)

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 ↗

(On Diff #211961)

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!

llvm/trunk/include/llvm/Analysis/MemorySSA.h

protected:
 
   void removeFromLookups(MemoryAccess *);
   void removeFromLists(MemoryAccess *, bool ShouldDelete = true);
   void insertIntoListsForBlock(MemoryAccess *, const BasicBlock *,
                                InsertionPlace);
   void insertIntoListsBefore(MemoryAccess *, const BasicBlock *,
                              AccessList::iterator);
   MemoryUseOrDef *createDefinedAccess(Instruction *, MemoryAccess *,
-                                      const MemoryUseOrDef *Template = nullptr);
+                                      const MemoryUseOrDef *Template = nullptr,
+                                      bool CreationMustSucceed = true);
 
 private:
   template <class AliasAnalysisType> class ClobberWalkerBase;
   template <class AliasAnalysisType> class CachingWalker;
   template <class AliasAnalysisType> class SkipSelfWalker;
   class OptimizeUses;
 
   CachingWalker<AliasAnalysis> *getWalkerImpl();

llvm/trunk/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) {
+                                               const MemoryUseOrDef *Template,
+                                               bool CreationMustSucceed) {
   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 (CreationMustSucceed)
+    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)) {

llvm/trunk/lib/Analysis/MemorySSAUpdater.cpp

MPhi->unorderedDeleteIncomingIf([&](const MemoryAccess *, BasicBlock *B) {
       Found = true;
       return false;
     });
     if (MPhi->getNumIncomingValues() == 1)
       removeMemoryAccess(MPhi);
   }
 }
 
-void MemorySSAUpdater::cloneUsesAndDefs(BasicBlock *BB, BasicBlock *NewBB,
+static MemoryAccess *getNewDefiningAccessForClone(MemoryAccess *MA,
                                                   const ValueToValueMapTy &VMap,
                                                   PhiToDefMap &MPhiMap,
-                                        bool CloneWasSimplified) {
-  auto GetNewDefiningAccess = [&](MemoryAccess *MA) -> MemoryAccess * {
-    MemoryAccess *InsnDefining = MA;
-    if (MemoryUseOrDef *DefMUD = dyn_cast<MemoryUseOrDef>(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)))
-          InsnDefining = MSSA->getMemoryAccess(NewDefMUDI);
-      }
-    } else {
-      MemoryPhi *DefPhi = cast<MemoryPhi>(InsnDefining);
-      if (MemoryAccess *NewDefPhi = MPhiMap.lookup(DefPhi))
-        InsnDefining = NewDefPhi;
-    }
-    assert(InsnDefining && "Defining instruction cannot be nullptr.");
-    return InsnDefining;
-  };
+                                                  bool CloneWasSimplified,
+                                                  MemorySSA *MSSA) {
+  if (MemoryDef *DefMUD = dyn_cast<MemoryDef>(InsnDefining)) {
+              cast_or_null<Instruction>(VMap.lookup(DefMUDI))) {
+        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 = getNewDefiningAccessForClone(
+              &*(--DefIt), VMap, MPhiMap, CloneWasSimplified, MSSA);
+        }
+      }
+}
 
+void MemorySSAUpdater::cloneUsesAndDefs(BasicBlock *BB, BasicBlock *NewBB,
+                                        const ValueToValueMapTy &VMap,
+                                        PhiToDefMap &MPhiMap,
+                                        bool CloneWasSimplified) {
   const MemorySSA::AccessList *Acc = MSSA->getBlockAccesses(BB);
   if (!Acc)
     return;
   for (const MemoryAccess &MA : *Acc) {
     if (const MemoryUseOrDef *MUD = dyn_cast<MemoryUseOrDef>(&MA)) {
       Instruction *Insn = MUD->getMemoryInst();
       // Entry does not exist if the clone of the block did not clone all
       // instructions. This occurs in LoopRotate when cloning instructions
       // from the old header to the old preheader. The cloned instruction may
       // also be a simplified Value, not an Instruction (see LoopRotate).
       // 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);
+            NewInsn,
+            getNewDefiningAccessForClone(MUD->getDefiningAccess(), VMap,
+                                         MPhiMap, CloneWasSimplified, MSSA),
+            /*Template=*/CloneWasSimplified ? nullptr : MUD,
+            /*CreationMustSucceed=*/CloneWasSimplified ? false : true);
+        if (NewUseOrDef)
           MSSA->insertIntoListsForBlock(NewUseOrDef, NewBB, MemorySSA::End);
       }
     }
   }
 }
 
 void MemorySSAUpdater::updatePhisWhenInsertingUniqueBackedgeBlock(
     BasicBlock *Header, BasicBlock *Preheader, BasicBlock *BEBlock) {
   auto *MPhi = MSSA->getMemoryAccess(Header);

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

+; RUN: opt -verify-memoryssa -enable-mssa-loop-dependency -loop-rotate %s -S | FileCheck %s 
+; REQUIRES: asserts
+
+; 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 }