[MemorySSA] Avoid adding Phis in the presence of unreachable blocks.

[asbirlea]

Summary

If a block has all incoming values with the same MemoryAccess (ignoring
incoming values from unreachable blocks), then use that incoming
MemoryAccess and do not create a Phi in the first place.

Revert IDF work-around added in rL372673; it should not be required unless
the Def inserted is the first in its block.

The patch also cleans up a series of tests, added during the many
iterations on insertDef.

The patch also fixes PR43438.
The same issue that occurs in insertDef with "adding phis, hence the IDF of
Phis is needed", can also occur in fixupDefs: the getPreviousRecursive
call only adds Phis walking on the predecessor edges, which means there
may be the case of a Phi added walking the CFG "backwards" which
triggers the needs for an additional Phi in successor blocks.
Such Phis are added during fixupDefs only in the presence of unreachable
blocks.
Hence this highlights the need to avoid adding Phis in blocks with
unreachable predecessors in the first place.

[george.burgess.iv]

Thanks!

lib/Analysis/MemorySSAUpdater.cpp

82

nit: would it be simpler to keep a count of the unreachable blocks we saw (not adding anything to PhiOps), then if PhiOps.size() > 1, just adding NumUnreachablePreds LiveOnEntryDefs?

[asbirlea]

Add testcase.

[asbirlea]

lib/Analysis/MemorySSAUpdater.cpp

82

I think having the SingleAccess is important to not end up adding Phis when multiple reachable blocks provide the same incoming access. Given this, we can't really model everything with a single counter. Yes, we can use a counter and add the LiveOnEntryDefs after the loop, but it's roughly the same amount of code/same complexity.

lib/Analysis/MemorySSAUpdater.cpp

MemoryAccess *MemorySSAUpdater::getPreviousDefRecursive(
 
   if (VisitedBlocks.insert(BB).second) {
     // Mark us visited so we can detect a cycle
     SmallVector<TrackingVH<MemoryAccess>, 8> PhiOps;
 
     // Recurse to get the values in our predecessors for placement of a
     // potential phi node. This will insert phi nodes if we cycle in order to
     // break the cycle and have an operand.
-    for (auto *Pred : predecessors(BB))
-      if (MSSA->DT->isReachableFromEntry(Pred))
-        PhiOps.push_back(getPreviousDefFromEnd(Pred, CachedPreviousDef));
-      else
+    bool UniqueIncomingAccess = true;
+    MemoryAccess *SingleAccess = nullptr;
+    for (auto *Pred : predecessors(BB)) {
+      if (MSSA->DT->isReachableFromEntry(Pred)) {
+        auto *IncomingAccess = getPreviousDefFromEnd(Pred, CachedPreviousDef);
+        if (!SingleAccess)
+          SingleAccess = IncomingAccess;
+        else if (IncomingAccess != SingleAccess)
+          UniqueIncomingAccess = false;
+        PhiOps.push_back(IncomingAccess);
+      } else
         PhiOps.push_back(MSSA->getLiveOnEntryDef());
+    }
 
     // Now try to simplify the ops to avoid placing a phi.
     // This may return null if we never created a phi yet, that's okay
     MemoryPhi *Phi = dyn_cast_or_null<MemoryPhi>(MSSA->getMemoryAccess(BB));
 
     // See if we can avoid the phi by simplifying it.
     auto *Result = tryRemoveTrivialPhi(Phi, PhiOps);
     // If we couldn't simplify, we may have to create a phi
-    if (Result == Phi) {
+    if (Result == Phi && UniqueIncomingAccess && SingleAccess)
+      Result = SingleAccess;
+    else if (Result == Phi && !(UniqueIncomingAccess && SingleAccess)) {
       if (!Phi)
         Phi = MSSA->createMemoryPhi(BB);
 
       // See if the existing phi operands match what we need.
       // Unlike normal SSA, we only allow one phi node per block, so we can't just
       // create a new one.
       if (Phi->getNumOperands() != 0) {
         // FIXME: Figure out whether this is dead code and if so remove it.
if (DefBeforeSameBlock) {
     });
   }
 
   // and that def is now our defining access.
   MD->setDefiningAccess(DefBefore);
 
   SmallVector<WeakVH, 8> FixupList(InsertedPHIs.begin(), InsertedPHIs.end());
 
-  SmallPtrSet<BasicBlock *, 2> DefiningBlocks;
-
+  // 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
     // we hit the first def along each path). This may also insert phi nodes.
     // TODO: There are other cases we can skip this work, such as when we have a
     // single successor, and only used a straight line of single pred blocks
     // backwards to find the def.  To make that work, we'd have to track whether
     // getDefRecursive only ever used the single predecessor case.  These types
     // of paths also only exist in between CFG simplifications.
 
     // If this is the first def in the block and this insert is in an arbitrary
     // place, compute IDF and place phis.
     auto Iter = MD->getDefsIterator();
     ++Iter;
     auto IterEnd = MSSA->getBlockDefs(MD->getBlock())->end();
-    if (Iter == IterEnd)
+    if (Iter == IterEnd) {
+      SmallPtrSet<BasicBlock *, 2> DefiningBlocks;
       DefiningBlocks.insert(MD->getBlock());
-
-    FixupList.push_back(MD);
-  }
-
-  ForwardIDFCalculator IDFs(*MSSA->DT);
-  SmallVector<BasicBlock *, 32> IDFBlocks;
       for (const auto &VH : InsertedPHIs)
         if (const auto *RealPHI = cast_or_null<MemoryPhi>(VH))
           DefiningBlocks.insert(RealPHI->getBlock());
+      ForwardIDFCalculator IDFs(*MSSA->DT);
+      SmallVector<BasicBlock *, 32> IDFBlocks;
       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);
         }
-    // 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.
+        // 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);
       }
-
       for (auto &MPhi : NewInsertedPHIs) {
         auto *BBIDF = MPhi->getBlock();
         for (auto *Pred : predecessors(BBIDF)) {
           DenseMap<BasicBlock *, TrackingVH<MemoryAccess>> CachedPreviousDef;
-      MPhi->addIncoming(getPreviousDefFromEnd(Pred, CachedPreviousDef), Pred);
+          MPhi->addIncoming(getPreviousDefFromEnd(Pred, CachedPreviousDef),
+                            Pred);
         }
       }
 
-  // Remember the index where we may insert new phis.
-  unsigned NewPhiIndex = InsertedPHIs.size();
+      // Re-take the index where we're adding the new phis, because the above
+      // call to getPreviousDefFromEnd, may have inserted into InsertedPHIs.
+      NewPhiIndex = InsertedPHIs.size();
       for (auto &MPhi : NewInsertedPHIs) {
         InsertedPHIs.push_back(&*MPhi);
         FixupList.push_back(&*MPhi);
       }
+    }
+    FixupList.push_back(MD);
+  }
+
   // Remember the index where we stopped inserting new phis above, since the
   // fixupDefs call in the loop below may insert more, that are already minimal.
   unsigned NewPhiIndexEnd = InsertedPHIs.size();
 
   while (!FixupList.empty()) {
     unsigned StartingPHISize = InsertedPHIs.size();
     fixupDefs(FixupList);
     FixupList.clear();

test/Analysis/MemorySSA/pr40754.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 = "systemz-unknown"
 
 @g_120 = external dso_local local_unnamed_addr global [8 x [4 x [6 x i32]]], align 4
 @g_185 = external dso_local local_unnamed_addr global i32, align 4
 @g_329 = external dso_local local_unnamed_addr global i16, align 2
 
 ; Function Attrs: norecurse noreturn nounwind
 define dso_local void @func_65() local_unnamed_addr {
 ; CHECK-LABEL: @func_65()
-  br label %1
+label0:
+  br label %label1
 
-; <label>:1:                                      ; preds = %.thread, %0
-  br label %2
+label1:                                      ; preds = %.thread, %label0
+  br label %label2
 
-; <label>:2:                                      ; preds = %.critedge, %1
-  br label %3
+label2:                                      ; preds = %.critedge, %label1
+  br label %label3
 
-; <label>:3:                                      ; preds = %5, %2
-  %storemerge = phi i32 [ 0, %2 ], [ %6, %5 ]
+label3:                                      ; preds = %label5, %label2
+  %storemerge = phi i32 [ 0, %label2 ], [ %tmp6, %label5 ]
   store i32 %storemerge, i32* @g_185, align 4
-  %4 = icmp ult i32 %storemerge, 2
-  br i1 %4, label %5, label %.thread.loopexit
+  %tmp4 = icmp ult i32 %storemerge, 2
+  br i1 %tmp4, label %label5, label %.thread.loopexit
 
-; <label>:5:                                      ; preds = %3
-  %6 = add i32 %storemerge, 1
-  %7 = zext i32 %6 to i64
-  %8 = getelementptr [8 x [4 x [6 x i32]]], [8 x [4 x [6 x i32]]]* @g_120, i64 0, i64 undef, i64 %7, i64 undef
-  %9 = load i32, i32* %8, align 4
-  %10 = icmp eq i32 %9, 0
-  br i1 %10, label %3, label %11
-
-; <label>:11:                                     ; preds = %5
-  %storemerge.lcssa4 = phi i32 [ %storemerge, %5 ]
-  %12 = icmp eq i32 %storemerge.lcssa4, 0
-  br i1 %12, label %.critedge, label %.thread.loopexit3
+label5:                                      ; preds = %label3
+  %tmp6 = add i32 %storemerge, 1
+  %tmp7 = zext i32 %tmp6 to i64
+  %tmp8 = getelementptr [8 x [4 x [6 x i32]]], [8 x [4 x [6 x i32]]]* @g_120, i64 0, i64 undef, i64 %tmp7, i64 undef
+  %tmp9 = load i32, i32* %tmp8, align 4
+  %tmp10 = icmp eq i32 %tmp9, 0
+  br i1 %tmp10, label %label3, label %label11
+
+label11:                                     ; preds = %label5
+  %storemerge.lcssa4 = phi i32 [ %storemerge, %label5 ]
+  %tmp12 = icmp eq i32 %storemerge.lcssa4, 0
+  br i1 %tmp12, label %.critedge, label %.thread.loopexit3
 
-.critedge:                                        ; preds = %11
+.critedge:                                        ; preds = %label11
   store i16 0, i16* @g_329, align 2
-  br label %2
+  br label %label2
 
-.thread.loopexit:                                 ; preds = %3
+.thread.loopexit:                                 ; preds = %label3
   br label %.thread
 
-.thread.loopexit3:                                ; preds = %11
+.thread.loopexit3:                                ; preds = %label11
   br label %.thread
 
 .thread:                                          ; preds = %.thread.loopexit3, %.thread.loopexit
-  br label %1
+  br label %label1
 }
 

test/Analysis/MemorySSA/pr41640.ll

-; RUN: opt -S -licm -enable-mssa-loop-dependency %s | FileCheck %s
-; REQUIRES: asserts
+; RUN: opt -disable-output -licm -print-memoryssa -enable-mssa-loop-dependency=true < %s 2>&1 | FileCheck %s
 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_248 = external dso_local local_unnamed_addr global i32, align 4
 @g_976 = external dso_local global i64, align 8
 @g_1087 = external dso_local global i32**, align 8
 
 ; CHECK-LABEL: @f1()
+; CHECK: 5 = MemoryPhi(
+; CHECK-NOT: 7 = MemoryPhi(
 define dso_local fastcc void @f1() unnamed_addr #0 {
 label0:
   br i1 undef, label %thread-pre-split.i.preheader, label %label5
 
 thread-pre-split.i.preheader:                     ; preds = %label0
   br label %thread-pre-split.i
 
 thread-pre-split.i.us:                            ; preds = %.critedge1.i.us

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
 }
 
 @g_1504 = external dso_local local_unnamed_addr global i16****, align 8
 
 define void @f5() {
 bb:
   tail call fastcc void @f21()
   br label %bb12.outer
 
 bb12.outer.loopexit:                              ; No predecessors!
   br label %bb12.outer
 
 bb12.outer:                                       ; preds = %bb12.outer.loopexit, %bb
   br i1 undef, label %bb12.outer.split.us, label %bb12.preheader
 
 bb12.preheader:                                   ; preds = %bb12.outer
   br label %bb12
 
 bb12.outer.split.us:                              ; preds = %bb12.outer
   br label %bb16.us.us
 
 bb16.us.us:                                       ; preds = %bb16.us.us, %bb12.outer.split.us
   br label %bb16.us.us
 
 bb12:                                             ; preds = %bb77.1, %bb12.preheader
   br i1 undef, label %bb25.preheader, label %bb77
 
 bb25.preheader:                                   ; preds = %bb12.1, %bb12
   br label %bb25
 
 bb25:                                             ; preds = %l0, %bb25.preheader
   br i1 undef, label %bb62, label %bb71.thread
 
 bb62:                                             ; preds = %bb25
   br i1 undef, label %bb92.loopexit, label %l0
 
 l0:                                                ; preds = %bb62
   br label %bb25
 
 bb71.thread:                                      ; preds = %bb25
   br label %bb92
 
 bb77:                                             ; preds = %bb12
   %tmp78 = load i16****, i16***** @g_1504, align 8
   %tmp79 = load volatile i16***, i16**** %tmp78, align 8
   br i1 undef, label %bb91, label %bb12.1
 
 bb91:                                             ; preds = %bb77.1, %bb77
   unreachable
 
 bb92.loopexit:                                    ; preds = %bb62
   br label %bb92
 
 bb92:                                             ; preds = %bb92.loopexit, %bb71.thread
   ret void
 
 bb12.1:                                           ; preds = %bb77
   br i1 undef, label %bb25.preheader, label %bb77.1
 
 bb77.1:                                           ; preds = %bb12.1
   br i1 undef, label %bb91, label %bb12
 }
 
 declare void @f21()

test/Analysis/MemorySSA/pr43044.ll

 ; RUN: opt -loop-rotate -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"
 
 declare void @llvm.lifetime.end.p0i8(i64 immarg, i8* nocapture)
 
 ; CHECK-LABEL: @func_42()
 define void @func_42() {
 entry:
   br label %for.cond1050
 
 for.cond1050.loopexit:                            ; preds = %for.cond1373
   br label %for.cond1050
 
 for.cond1050:                                     ; preds = %for.cond1050.loopexit, %entry
   %storemerge6 = phi i32 [ 2, %entry ], [ 0, %for.cond1050.loopexit ]
   %cmp1051 = icmp sgt i32 %storemerge6, -1
   br i1 %cmp1051, label %for.cond1055.preheader, label %cleanup1400.loopexit1
 
 for.cond1055.preheader:                           ; preds = %for.cond1050
   store i64 0, i64* null, align 8
   %0 = load i64, i64* null, align 8
   %tobool1383 = icmp eq i64 %0, 0
   br i1 %tobool1383, label %for.cond1055.preheader.cleanup1400.loopexit.split_crit_edge, label %for.cond1055.preheader.for.cond1055.preheader.split_crit_edge
 
 for.cond1055.preheader.for.cond1055.preheader.split_crit_edge: ; preds = %for.cond1055.preheader
   br label %for.body1376
 
 for.cond1055.preheader.cleanup1400.loopexit.split_crit_edge: ; preds = %for.cond1055.preheader
   br label %cleanup1400.loopexit.split
 
 for.cond1373:                                     ; preds = %for.body1376
   br i1 true, label %for.body1376, label %for.cond1050.loopexit
 
 for.body1376:                                     ; preds = %for.cond1373, %for.cond1055.preheader.for.cond1055.preheader.split_crit_edge
   br i1 false, label %cleanup1400.loopexit, label %for.cond1373
 
 cleanup1400.loopexit:                             ; preds = %for.body1376
   br label %cleanup1400.loopexit.split
 
 cleanup1400.loopexit.split:                       ; preds = %cleanup1400.loopexit, %for.cond1055.preheader.cleanup1400.loopexit.split_crit_edge
   br label %cleanup1400
 
 cleanup1400.loopexit1:                            ; preds = %for.cond1050
   br label %cleanup1400
 
 cleanup1400:                                      ; preds = %cleanup1400.loopexit1, %cleanup1400.loopexit.split
   call void @llvm.lifetime.end.p0i8(i64 4, i8* nonnull undef)
   unreachable
 }

test/Analysis/MemorySSA/pr43317.ll

-; RUN: opt -S -licm -enable-mssa-loop-dependency=true < %s | FileCheck %s
-; REQUIRES: asserts
+; RUN: opt -disable-output -licm -print-memoryssa -enable-mssa-loop-dependency=true < %s 2>&1 | FileCheck %s
 @v_274 = external dso_local global i64, align 1
 @v_295 = external dso_local global i16, align 1
 @v_335 = external dso_local global i32, align 1
 
 ; CHECK-LABEL: @main()
+; CHECK-NOT: 5 = MemoryPhi(
+; CHECK-NOT: 6 = MemoryPhi(
+; CHECK: 4 = MemoryPhi(
+; CHECK-NOT: 7 = MemoryPhi(
 define dso_local void @main() {
 entry:
   store i32 undef, i32* @v_335, align 1
   br i1 undef, label %gate, label %exit
 
 nopredentry1:                                     ; No predecessors!
   br label %preinfiniteloop