[MemorySSA] Check that block is reachable when adding phis.

[asbirlea]

Summary

Originally the insertDef method was only used when building MemorySSA, and was limiting the number of Phi nodes that it created.
Now it's used for updates as well, and it can create additional Phis needed for correctness.
Make sure no Phis are created in unreachable blocks (condition met during MSSA build), otherwise the renamePass will find a null DTNode.

Resolves PR41640.

[asbirlea]

Added -S.

[asbirlea]

Updated to not insert phis in unreachable blocks.

[george.burgess.iv]

Thanks!

test/Analysis/MemorySSA/pr41640.ll

1 ↗

(On Diff #197885)

; REQUIRES: asserts, please

llvm/trunk/lib/Analysis/MemorySSA.cpp

 
 /// This is the standard SSA renaming algorithm.
 ///
 /// We walk the dominator tree in preorder, renaming accesses, and then filling
 /// in phi nodes in our successors.
 void MemorySSA::renamePass(DomTreeNode *Root, MemoryAccess *IncomingVal,
                            SmallPtrSetImpl<BasicBlock *> &Visited,
                            bool SkipVisited, bool RenameAllUses) {
+  assert(Root && "Trying to rename accesses in an unreachable block");
+
   SmallVector<RenamePassData, 32> WorkStack;
   // Skip everything if we already renamed this block and we are skipping.
   // Note: You can't sink this into the if, because we need it to occur
   // regardless of whether we skip blocks or not.
   bool AlreadyVisited = !Visited.insert(Root->getBlock()).second;
   if (SkipVisited && AlreadyVisited)
     return;
 

llvm/trunk/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
+        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

llvm/trunk/test/Analysis/MemorySSA/pr41640.ll

+; RUN: opt -S -licm -enable-mssa-loop-dependency %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_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()
+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
+  br i1 undef, label %.preheader.i.us.preheader, label %label2
+
+.preheader.i.us.preheader:                        ; preds = %thread-pre-split.i.us
+  br label %.preheader.i.us
+
+.preheader.i.us:                                  ; preds = %._crit_edge.i.us, %.preheader.i.us.preheader
+  br i1 undef, label %.lr.ph.i.us, label %._crit_edge.i.us
+
+.lr.ph.i.us:                                      ; preds = %.preheader.i.us
+  br label %label1
+
+label1:                                      ; preds = %label1, %.lr.ph.i.us
+  br i1 undef, label %label1, label %._crit_edge.i.us
+
+._crit_edge.i.us:                                 ; preds = %label1, %.preheader.i.us
+  br i1 undef, label %.preheader.i.us, label %._crit_edge5.i.us
+
+._crit_edge5.i.us:                                ; preds = %._crit_edge.i.us
+  br label %label2
+
+label2:                                  ; preds = %._crit_edge5.i.us, %thread-pre-split.i.us
+  tail call void @foo16()
+  br i1 undef, label %.lr.ph8.i.us.preheader, label %label4
+
+.lr.ph8.i.us.preheader:                           ; preds = %label2
+  br label %.lr.ph8.i.us
+
+.lr.ph8.i.us:                                     ; preds = %.lr.ph8.i.us, %.lr.ph8.i.us.preheader
+  %tmp3 = load volatile i64, i64* @g_976, align 8
+  br i1 undef, label %.lr.ph8.i.us, label %._crit_edge9.i.us
+
+._crit_edge9.i.us:                                ; preds = %.lr.ph8.i.us
+  br label %label4
+
+label4:                                      ; preds = %._crit_edge9.i.us, %label2
+  br i1 true, label %f9.exit, label %.critedge1.i.us
+
+.critedge1.i.us:                                  ; preds = %label4
+  br i1 undef, label %thread-pre-split.i.us, label %f9.exit
+
+label5:                                      ; preds = %label0
+  unreachable
+
+thread-pre-split.i:                               ; preds = %.critedge1.i, %thread-pre-split.i.preheader
+  br i1 undef, label %.preheader.i.preheader, label %.critedge1.i
+
+.preheader.i.preheader:                           ; preds = %thread-pre-split.i
+  br label %.preheader.i
+
+.preheader.i:                                     ; preds = %._crit_edge.i, %.preheader.i.preheader
+  br i1 undef, label %.lr.ph.i, label %._crit_edge.i
+
+.lr.ph.i:                                         ; preds = %.preheader.i
+  br label %label6
+
+label6:                                      ; preds = %label6, %.lr.ph.i
+  br i1 undef, label %label6, label %._crit_edge.i.loopexit
+
+._crit_edge.i.loopexit:                           ; preds = %label6
+  br label %._crit_edge.i
+
+._crit_edge.i:                                    ; preds = %._crit_edge.i.loopexit, %.preheader.i
+  br i1 undef, label %.preheader.i, label %._crit_edge5.i
+
+._crit_edge5.i:                                   ; preds = %._crit_edge.i
+  br label %.critedge1.i
+
+.critedge1.i:                                     ; preds = %._crit_edge5.i, %thread-pre-split.i
+  %tmp7 = load i32, i32* @g_248, align 4
+  %tmp8 = xor i32 %tmp7, 55987
+  store i32 %tmp8, i32* @g_248, align 4
+  br i1 undef, label %thread-pre-split.i, label %f9.exit.loopexit
+
+f9.exit.loopexit:                                 ; preds = %.critedge1.i
+  br label %f9.exit
+
+f9.exit:                                          ; preds = %f9.exit.loopexit, %.critedge1.i.us, %label4
+  %tmp9 = load volatile i32**, i32*** @g_1087, align 8
+  ret void
+}
+
+declare dso_local void @foo16() local_unnamed_addr #1
+
+attributes #0 = { "target-features"="+transactional-execution,+vector" }
+attributes #1 = { "use-soft-float"="false" }