[MemorySSA] Rename uses in blocks with Phis.

[asbirlea]

Summary

Renaming should include blocks with existing Phis.

Resolves PR45927.

[george.burgess.iv]

but when prinitng we were still seeing an unoptimized access
as MustAlias due to the flag not being reset

oof. maybe we should make the accessor for the AliasResult do return isOptimized() ? actualResult : MayAlias;?

lgtm either way though -- thanks for this!

[asbirlea]

Updated the printing in separate revision. Rebase.

[george.burgess.iv]

(still lgtm. :) )

[asbirlea]

Update to different approach.

[asbirlea]

Incorrect previous approach. The renaming needs to start at the block with the new def, but it needs to rename all blocks in the IDF, not just those with phis added.

llvm/lib/Analysis/MemorySSAUpdater.cpp

if (DefBeforeSameBlock) {
     });
   }
 
   // and that def is now our defining access.
   MD->setDefiningAccess(DefBefore);
 
   SmallVector<WeakVH, 8> FixupList(InsertedPHIs.begin(), InsertedPHIs.end());
 
+  SmallSet<WeakVH, 8> ExistingPhis;
+
   // Remember the index where we may insert new phis.
   unsigned NewPhiIndex = InsertedPHIs.size();
   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
if (!DefBeforeSameBlock) {
     IDFs.setDefiningBlocks(DefiningBlocks);
     IDFs.calculate(IDFBlocks);
     SmallVector<AssertingVH<MemoryPhi>, 4> NewInsertedPHIs;
     for (auto *BBIDF : IDFBlocks) {
       auto *MPhi = MSSA->getMemoryAccess(BBIDF);
       if (!MPhi) {
         MPhi = MSSA->createMemoryPhi(BBIDF);
         NewInsertedPHIs.push_back(MPhi);
+      } else {
+        ExistingPhis.insert(MPhi);
       }
       // Add the phis created into the IDF blocks to NonOptPhis, so they are not
       // optimized out as trivial by the call to getPreviousDefFromEnd below.
       // Once they are complete, all these Phis are added to the FixupList, and
       // removed from NonOptPhis inside fixupDefs(). Existing Phis in IDF may
       // need fixing as well, and potentially be trivial before this insertion,
       // hence add all IDF Phis. See PR43044.
       NonOptPhis.insert(MPhi);
if (RenameUses) {
     MSSA->renamePass(MD->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);
     }
+    // Existing Phi blocks may need renaming too, if an access was previously
+    // optimized and the inserted Defs "covers" the Optimized value.
+    for (auto &MP : ExistingPhis) {
+      MemoryPhi *Phi = dyn_cast_or_null<MemoryPhi>(MP);
+      if (Phi)
+        MSSA->renamePass(Phi->getBlock(), nullptr, Visited);
+    }
   }
 }
 
 void MemorySSAUpdater::fixupDefs(const SmallVectorImpl<WeakVH> &Vars) {
   SmallPtrSet<const BasicBlock *, 8> Seen;
   SmallVector<const BasicBlock *, 16> Worklist;
   for (auto &Var : Vars) {
     MemoryAccess *NewDef = dyn_cast_or_null<MemoryAccess>(Var);
if (!isa<MemoryUse>(MA) && !MA->use_empty()) {
     // flags on users of phi nodes if doing the below makes a phi node have all
     // the same arguments. Instead, we prefer users to removeMemoryAccess those
     // phi nodes, because doing it here would be N^3.
     if (MA->hasValueHandle())
       ValueHandleBase::ValueIsRAUWd(MA, NewDefTarget);
     // Note: We assume MemorySSA is not used in metadata since it's not really
     // part of the IR.
 
+    assert(NewDefTarget != MA && "Going into an infinite loop");
     while (!MA->use_empty()) {
       Use &U = *MA->use_begin();
       if (auto *MUD = dyn_cast<MemoryUseOrDef>(U.getUser()))
         MUD->resetOptimized();
       if (OptimizePhis)
         if (MemoryPhi *MP = dyn_cast<MemoryPhi>(U.getUser()))
           PhisToCheck.insert(MP);
       U.set(NewDefTarget);

llvm/test/Analysis/MemorySSA/pr45927.ll

+; RUN: opt -disable-output -loop-simplify -lcssa -licm -print-memoryssa < %s 2>&1 | FileCheck %s
+; RUN: opt -disable-output -aa-pipeline=basic-aa -passes='loop-mssa(licm),print<memoryssa>' < %s 2>&1 | FileCheck %s
+
+
+@a = external dso_local global i16, align 1
+@c = external dso_local global i16, align 1
+
+; CHECK-LABEL: @main()
+
+; CHECK: entry:
+; CHECK-NEXT: %res.addr.i = alloca i16
+; CHECK-NEXT: ; MemoryUse(liveOnEntry)
+; CHECK-NEXT: %c.promoted = load i16, i16* @c
+; CHECK-NEXT: br label %for.cond.i
+
+; CHECK: for.cond.i:
+; CHECK-NEXT: ; [[NO5:.*]] = MemoryPhi({entry,liveOnEntry},{f.exit.i,[[NO5]]})
+; CHECK-NEXT: %inc.i1 = phi i16 [ %inc.i, %f.exit.i ], [ %c.promoted, %entry ]
+; CHECK-NEXT: %inc.i = add nsw i16 %inc.i1, 1
+; CHECK-NEXT: br i1 false, label %f.exit.thread.i, label %f.exit.i
+
+; CHECK: f.exit.thread.i:
+; CHECK-NEXT: %inc.i.lcssa = phi i16 [ %inc.i, %for.cond.i ]
+; CHECK-NEXT: ; [[NO6:.*]] = MemoryDef([[NO5]])
+; CHECK-NEXT: store i16 %inc.i.lcssa, i16* @c, align 1
+; CHECK-NEXT: ; [[NO2:.*]] = MemoryDef([[NO6]])
+; CHECK-NEXT: store i16 1, i16* @a, align 1
+; CHECK-NEXT: ; MemoryUse([[NO2]])
+; CHECK-NEXT: %tmp2 = load i16, i16* @c, align 1
+; CHECK-NEXT: br label %g.exit
+
+; CHECK: f.exit.i
+; CHECK-NEXT: br i1 false, label %g.exit.loopexit, label %for.cond.i
+
+; CHECK: g.exit.loopexit:
+; CHECK-NEXT: %inc.i.lcssa2 = phi i16 [ %inc.i, %f.exit.i ]
+; CHECK-NEXT: ; [[NO7:.*]] = MemoryDef([[NO5]])
+; CHECK-NEXT: store i16 %inc.i.lcssa2, i16* @c, align 1
+; CHECK-NEXT: br label %g.exit
+
+; CHECK: g.exit
+; CHECK-NEXT: ; [[NO4:.*]] = MemoryPhi({f.exit.thread.i,[[NO2]]},{g.exit.loopexit,[[NO7]]})
+; CHECK-NEXT: ; MemoryUse([[NO4]])
+; CHECK-NEXT:  %tmp1 = load i16, i16* @c, align 1
+; CHECK-NEXT: ; [[NO3:.*]] = MemoryDef([[NO4]])
+; CHECK-NEXT:  store i16 %tmp1, i16* %res.addr.i, align 1
+; CHECK-NEXT:  ret void
+
+define dso_local void @main() {
+entry:
+  %res.addr.i = alloca i16, align 1
+  br label %for.cond.i
+
+for.cond.i:                                       ; preds = %f.exit.i, %entry
+  %tmp0 = load i16, i16* @c, align 1
+  %inc.i = add nsw i16 %tmp0, 1
+  store i16 %inc.i, i16* @c, align 1
+  br i1 false, label %f.exit.thread.i, label %f.exit.i
+
+f.exit.thread.i:                                  ; preds = %for.cond.i
+  store i16 1, i16* @a, align 1
+  %tmp2 = load i16, i16* @c, align 1
+  br label %g.exit
+
+f.exit.i:                                         ; preds = %for.cond.i
+  br i1 false, label %g.exit, label %for.cond.i
+
+g.exit:                                           ; preds = %f.exit.i, %f.exit.thread.i
+  %tmp1 = load i16, i16* @c, align 1
+  store i16 %tmp1, i16* %res.addr.i, align 1
+  ret void
+}
+