[MemorySSA & LoopPassManager] Update MemorySSA in formDedicatedExitBlocks.

MemorySSA is now updated when forming dedicated exit blocks.
Resolves PR40037.

llvm-svn: 354623

6 files changed, 129 insertions, 11 deletions

diff --git a/llvm/include/llvm/Transforms/Utils/LoopUtils.h b/llvm/include/llvm/Transforms/Utils/LoopUtils.h
index a5883ac79bb..f81b7367292 100644
--- a/llvm/include/llvm/Transforms/Utils/LoopUtils.h
+++ b/llvm/include/llvm/Transforms/Utils/LoopUtils.h
@@ -59,7 +59,7 @@ BasicBlock *InsertPreheaderForLoop(Loop *L, DominatorTree *DT, LoopInfo *LI,
 /// predecessors to use a dedicated loop exit block. We update the dominator
 /// tree and loop info if provided, and will preserve LCSSA if requested.
 bool formDedicatedExitBlocks(Loop *L, DominatorTree *DT, LoopInfo *LI,
-                             bool PreserveLCSSA);
+                             MemorySSAUpdater *MSSAU, bool PreserveLCSSA);
 
 /// Ensures LCSSA form for every instruction from the Worklist in the scope of
 /// innermost containing loop.
diff --git a/llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp b/llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp
index db7da8edd51..befdfc5cef0 100644
--- a/llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp
+++ b/llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp
@@ -267,7 +267,8 @@ static void rewritePHINodesForExitAndUnswitchedBlocks(BasicBlock &ExitBB,
 /// loops reachable and need to move the current loop up the loop nest or even
 /// to an entirely separate nest.
 static void hoistLoopToNewParent(Loop &L, BasicBlock &Preheader,
-                                 DominatorTree &DT, LoopInfo &LI) {
+                                 DominatorTree &DT, LoopInfo &LI,
+                                 MemorySSAUpdater *MSSAU) {
   // If the loop is already at the top level, we can't hoist it anywhere.
   Loop *OldParentL = L.getParentLoop();
   if (!OldParentL)
@@ -328,7 +329,8 @@ static void hoistLoopToNewParent(Loop &L, BasicBlock &Preheader,
     // unswitching it is possible to get new non-dedicated exits out of parent
     // loop so let's conservatively form dedicated exit blocks and figure out
     // if we can optimize later.
-    formDedicatedExitBlocks(OldContainingL, &DT, &LI, /*PreserveLCSSA*/ true);
+    formDedicatedExitBlocks(OldContainingL, &DT, &LI, MSSAU,
+                            /*PreserveLCSSA*/ true);
   }
 }
 
@@ -535,7 +537,10 @@ static bool unswitchTrivialBranch(Loop &L, BranchInst &BI, DominatorTree &DT,
   // If this was full unswitching, we may have changed the nesting relationship
   // for this loop so hoist it to its correct parent if needed.
   if (FullUnswitch)
-    hoistLoopToNewParent(L, *NewPH, DT, LI);
+    hoistLoopToNewParent(L, *NewPH, DT, LI, MSSAU);
+
+  if (MSSAU && VerifyMemorySSA)
+    MSSAU->getMemorySSA()->verifyMemorySSA();
 
   LLVM_DEBUG(dbgs() << "    done: unswitching trivial branch...\n");
   ++NumTrivial;
@@ -804,7 +809,10 @@ static bool unswitchTrivialSwitch(Loop &L, SwitchInst &SI, DominatorTree &DT,
 
   // We may have changed the nesting relationship for this loop so hoist it to
   // its correct parent if needed.
-  hoistLoopToNewParent(L, *NewPH, DT, LI);
+  hoistLoopToNewParent(L, *NewPH, DT, LI, MSSAU);
+
+  if (MSSAU && VerifyMemorySSA)
+    MSSAU->getMemorySSA()->verifyMemorySSA();
 
   ++NumTrivial;
   ++NumSwitches;
@@ -2239,7 +2247,7 @@ static void unswitchNontrivialInvariants(
     // introduced new, non-dedicated exits. At least try to re-form dedicated
     // exits for these loops. This may fail if they couldn't have dedicated
     // exits to start with.
-    formDedicatedExitBlocks(&UpdateL, &DT, &LI, /*PreserveLCSSA*/ true);
+    formDedicatedExitBlocks(&UpdateL, &DT, &LI, MSSAU, /*PreserveLCSSA*/ true);
   };
 
   // For non-child cloned loops and hoisted loops, we just need to update LCSSA
diff --git a/llvm/lib/Transforms/Utils/LoopSimplify.cpp b/llvm/lib/Transforms/Utils/LoopSimplify.cpp
index ca29f6787e2..c347b5e26e3 100644
--- a/llvm/lib/Transforms/Utils/LoopSimplify.cpp
+++ b/llvm/lib/Transforms/Utils/LoopSimplify.cpp
@@ -317,7 +317,7 @@ static Loop *separateNestedLoop(Loop *L, BasicBlock *Preheader,
 
   // Split edges to exit blocks from the inner loop, if they emerged in the
   // process of separating the outer one.
-  formDedicatedExitBlocks(L, DT, LI, PreserveLCSSA);
+  formDedicatedExitBlocks(L, DT, LI, nullptr, PreserveLCSSA);
 
   if (PreserveLCSSA) {
     // Fix LCSSA form for L. Some values, which previously were only used inside
@@ -530,7 +530,7 @@ ReprocessLoop:
   // predecessors that are inside of the loop.  This check guarantees that the
   // loop preheader/header will dominate the exit blocks.  If the exit block has
   // predecessors from outside of the loop, split the edge now.
-  if (formDedicatedExitBlocks(L, DT, LI, PreserveLCSSA))
+  if (formDedicatedExitBlocks(L, DT, LI, nullptr, PreserveLCSSA))
     Changed = true;
 
   // If the header has more than two predecessors at this point (from the
diff --git a/llvm/lib/Transforms/Utils/LoopUnrollRuntime.cpp b/llvm/lib/Transforms/Utils/LoopUnrollRuntime.cpp
index a9d41945b27..2f1a759870c 100644
--- a/llvm/lib/Transforms/Utils/LoopUnrollRuntime.cpp
+++ b/llvm/lib/Transforms/Utils/LoopUnrollRuntime.cpp
@@ -938,11 +938,11 @@ bool llvm::UnrollRuntimeLoopRemainder(Loop *L, unsigned Count,
   if (OtherExits.size() > 0) {
     // Generate dedicated exit blocks for the original loop, to preserve
     // LoopSimplifyForm.
-    formDedicatedExitBlocks(L, DT, LI, PreserveLCSSA);
+    formDedicatedExitBlocks(L, DT, LI, nullptr, PreserveLCSSA);
     // Generate dedicated exit blocks for the remainder loop if one exists, to
     // preserve LoopSimplifyForm.
     if (remainderLoop)
-      formDedicatedExitBlocks(remainderLoop, DT, LI, PreserveLCSSA);
+      formDedicatedExitBlocks(remainderLoop, DT, LI, nullptr, PreserveLCSSA);
   }
 
   auto UnrollResult = LoopUnrollResult::Unmodified;
diff --git a/llvm/lib/Transforms/Utils/LoopUtils.cpp b/llvm/lib/Transforms/Utils/LoopUtils.cpp
index 5539ff12e4a..44f47bf71ca 100644
--- a/llvm/lib/Transforms/Utils/LoopUtils.cpp
+++ b/llvm/lib/Transforms/Utils/LoopUtils.cpp
@@ -19,6 +19,7 @@
 #include "llvm/Analysis/InstructionSimplify.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/LoopPass.h"
+#include "llvm/Analysis/MemorySSAUpdater.h"
 #include "llvm/Analysis/MustExecute.h"
 #include "llvm/Analysis/ScalarEvolution.h"
 #include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
@@ -46,6 +47,7 @@ using namespace llvm::PatternMatch;
 static const char *LLVMLoopDisableNonforced = "llvm.loop.disable_nonforced";
 
 bool llvm::formDedicatedExitBlocks(Loop *L, DominatorTree *DT, LoopInfo *LI,
+                                   MemorySSAUpdater *MSSAU,
                                    bool PreserveLCSSA) {
   bool Changed = false;
 
@@ -81,7 +83,7 @@ bool llvm::formDedicatedExitBlocks(Loop *L, DominatorTree *DT, LoopInfo *LI,
       return false;
 
     auto *NewExitBB = SplitBlockPredecessors(
-        BB, InLoopPredecessors, ".loopexit", DT, LI, nullptr, PreserveLCSSA);
+        BB, InLoopPredecessors, ".loopexit", DT, LI, MSSAU, PreserveLCSSA);
 
     if (!NewExitBB)
       LLVM_DEBUG(
diff --git a/llvm/test/Analysis/MemorySSA/pr40037.ll b/llvm/test/Analysis/MemorySSA/pr40037.ll
new file mode 100644
index 00000000000..f1ba38498cc
--- /dev/null
+++ b/llvm/test/Analysis/MemorySSA/pr40037.ll
@@ -0,0 +1,108 @@
+; REQUIRES: asserts
+; RUN: opt -S -mtriple=systemz-unknown -mcpu=z13  -O3 -enable-mssa-loop-dependency -enable-simple-loop-unswitch -verify-memoryssa  < %s | 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_225 = external dso_local global i16, align 2
+@g_967 = external dso_local global i8, align 2
+@g_853 = external dso_local global i32***, align 8
+@g_320 = external dso_local global { i8, i8, i8, i8, i8, i8, i8, i8 }, align 4
+
+; Function Attrs: nounwind
+; CHECK-LABEL: @main(
+define dso_local void @main() #0 {
+bb:
+  call void @func_1()
+  unreachable
+}
+
+; Function Attrs: nounwind
+define dso_local void @func_1() #0 {
+bb:
+  call void @func_23()
+  unreachable
+}
+
+; Function Attrs: nounwind
+define dso_local void @func_23() #0 {
+bb:
+  %tmp = alloca i32****, align 8
+  %tmp1 = alloca i32*****, align 8
+  store i32**** @g_853, i32***** %tmp, align 8, !tbaa !1
+  store i32***** %tmp, i32****** %tmp1, align 8, !tbaa !1
+  br label %bb2
+
+bb2:                                              ; preds = %bb21, %bb
+  br label %bb3
+
+bb3:                                              ; preds = %bb7, %bb2
+  %tmp4 = load i8, i8* @g_967, align 2, !tbaa !5
+  %tmp5 = sext i8 %tmp4 to i32
+  %tmp6 = icmp sle i32 %tmp5, 5
+  br i1 %tmp6, label %bb7, label %bb8
+
+bb7:                                              ; preds = %bb3
+  call void @safe_sub_func_uint64_t_u_u()
+  br label %bb3
+
+bb8:                                              ; preds = %bb3
+  store i16 0, i16* @g_225, align 2, !tbaa !6
+  br label %bb9
+
+bb9:                                              ; preds = %bb25, %bb8
+  %tmp10 = load i16, i16* @g_225, align 2, !tbaa !6
+  %tmp11 = sext i16 %tmp10 to i32
+  %tmp12 = icmp ne i32 %tmp11, 1
+  br i1 %tmp12, label %bb13, label %bb28
+
+bb13:                                             ; preds = %bb9
+  %tmp14 = load i32*****, i32****** %tmp1, align 8, !tbaa !1
+  %tmp15 = load i32****, i32***** %tmp14, align 8, !tbaa !1
+  %tmp16 = load i32***, i32**** %tmp15, align 8, !tbaa !1
+  %tmp17 = load i32**, i32*** %tmp16, align 8, !tbaa !1
+  %tmp18 = load i32*, i32** %tmp17, align 8, !tbaa !1
+  %tmp19 = load i32, i32* %tmp18, align 4, !tbaa !8
+  %tmp20 = icmp ne i32 %tmp19, 0
+  br i1 %tmp20, label %bb28, label %bb21
+
+bb21:                                             ; preds = %bb13
+  %tmp22 = load i32, i32* bitcast ({ i8, i8, i8, i8, i8, i8, i8, i8 }* @g_320 to i32*), align 4
+  %tmp23 = ashr i32 %tmp22, 16
+  %tmp24 = icmp ne i32 %tmp23, 0
+  br i1 %tmp24, label %bb2, label %bb25
+
+bb25:                                             ; preds = %bb21
+  %tmp26 = load i16, i16* @g_225, align 2, !tbaa !6
+  %tmp27 = add i16 %tmp26, 1
+  store i16 %tmp27, i16* @g_225, align 2, !tbaa !6
+  br label %bb9
+
+bb28:                                             ; preds = %bb13, %bb9
+  ret void
+}
+
+; Function Attrs: nounwind
+define dso_local void @func_33() #0 {
+bb:
+  unreachable
+}
+
+; Function Attrs: nounwind
+declare dso_local void @safe_sub_func_uint64_t_u_u() #0
+
+attributes #0 = { nounwind "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "less-precise-fpmad"="false" "min-legal-vector-width"="0" "no-frame-pointer-elim"="false" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="z13" "target-features"="+transactional-execution,+vector" "unsafe-fp-math"="false" "use-soft-float"="false" }
+
+!llvm.ident = !{!0}
+
+!0 = !{!"clang version 8.0.0 (http://llvm.org/git/clang.git a674a04e68bcf09f9a0423f3f589589596bc01a6) (http://llvm.org/git/llvm.git 1fe1ffe00e034128d1c5504254fdd4742f48bb9a)"}
+!1 = !{!2, !2, i64 0}
+!2 = !{!"any pointer", !3, i64 0}
+!3 = !{!"omnipotent char", !4, i64 0}
+!4 = !{!"Simple C/C++ TBAA"}
+!5 = !{!3, !3, i64 0}
+!6 = !{!7, !7, i64 0}
+!7 = !{!"short", !3, i64 0}
+!8 = !{!9, !9, i64 0}
+!9 = !{!"int", !3, i64 0}
+