[LoopInterchange] Detect output dependency of a store instruction with itself

This patch is motivated by pr48057 where an output dependency is not detected
since loop interchange did not check a store instruction with itself.
Fixed that deficiency.

Reviewed By: bmahjour, Meinersbur, #loopoptwg

Differential Revision: https://reviews.llvm.org/D118102

4 files changed, 55 insertions, 54 deletions

diff --git a/llvm/lib/Transforms/Scalar/LoopInterchange.cpp b/llvm/lib/Transforms/Scalar/LoopInterchange.cpp
index 57ba765af18e..c59d39e9d7a1 100644
--- a/llvm/lib/Transforms/Scalar/LoopInterchange.cpp
+++ b/llvm/lib/Transforms/Scalar/LoopInterchange.cpp
@@ -118,8 +118,6 @@ static bool populateDependencyMatrix(CharMatrix &DepMatrix, unsigned Level,
       std::vector<char> Dep;
       Instruction *Src = cast<Instruction>(*I);
       Instruction *Dst = cast<Instruction>(*J);
-      if (Src == Dst)
-        continue;
       // Ignore Input dependencies.
       if (isa<LoadInst>(Src) && isa<LoadInst>(Dst))
         continue;
diff --git a/llvm/test/Transforms/LoopInterchange/lcssa-preheader.ll b/llvm/test/Transforms/LoopInterchange/lcssa-preheader.ll
index 73fa3c36790b..ab616eea9740 100644
--- a/llvm/test/Transforms/LoopInterchange/lcssa-preheader.ll
+++ b/llvm/test/Transforms/LoopInterchange/lcssa-preheader.ll
@@ -1,5 +1,6 @@
 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -basic-aa -loop-interchange -pass-remarks-missed='loop-interchange' -verify-loop-lcssa -S | FileCheck %s
+; RUN: opt < %s -basic-aa -loop-interchange -da-disable-delinearization-checks -pass-remarks-missed='loop-interchange' -verify-loop-lcssa -S | FileCheck -check-prefix=CHECK-DELIN %s
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 
@@ -12,49 +13,51 @@ target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 ;   }
 ; }
 
-define void @lcssa_08(i32 %n, i32 %m) {
-; CHECK-LABEL: @lcssa_08(
-; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[TEMP:%.*]] = alloca [16 x [16 x i32]], align 4
-; CHECK-NEXT:    [[RES:%.*]] = alloca [16 x [16 x i32]], align 4
-; CHECK-NEXT:    [[CMP24:%.*]] = icmp sgt i32 [[N:%.*]], 0
-; CHECK-NEXT:    br i1 [[CMP24]], label [[INNER_PREHEADER:%.*]], label [[FOR_COND_CLEANUP:%.*]]
-; CHECK:       outer.preheader:
-; CHECK-NEXT:    br label [[OUTER_HEADER:%.*]]
-; CHECK:       outer.header:
-; CHECK-NEXT:    [[INDVARS_IV27:%.*]] = phi i64 [ 0, [[OUTER_PREHEADER:%.*]] ], [ [[INDVARS_IV_NEXT28:%.*]], [[OUTER_LATCH:%.*]] ]
-; CHECK-NEXT:    [[CMP222:%.*]] = icmp sgt i32 [[M:%.*]], 0
-; CHECK-NEXT:    [[WIDE_TRIP_COUNT:%.*]] = zext i32 [[M]] to i64
-; CHECK-NEXT:    br i1 [[CMP222]], label [[INNER_FOR_BODY_SPLIT1:%.*]], label [[INNER_FOR_BODY_SPLIT:%.*]]
-; CHECK:       inner.preheader:
-; CHECK-NEXT:    [[WIDE_TRIP_COUNT29:%.*]] = zext i32 [[N]] to i64
-; CHECK-NEXT:    br label [[INNER_FOR_BODY:%.*]]
-; CHECK:       inner.for.body:
-; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ 0, [[INNER_PREHEADER]] ], [ [[TMP1:%.*]], [[INNER_FOR_BODY_SPLIT]] ]
-; CHECK-NEXT:    br label [[OUTER_PREHEADER]]
-; CHECK:       inner.for.body.split1:
-; CHECK-NEXT:    [[ARRAYIDX6:%.*]] = getelementptr inbounds [16 x [16 x i32]], [16 x [16 x i32]]* [[TEMP]], i64 0, i64 [[INDVARS_IV]], i64 [[INDVARS_IV27]]
-; CHECK-NEXT:    [[TMP0:%.*]] = load i32, i32* [[ARRAYIDX6]], align 4
-; CHECK-NEXT:    [[ARRAYIDX8:%.*]] = getelementptr inbounds [16 x [16 x i32]], [16 x [16 x i32]]* [[RES]], i64 0, i64 [[INDVARS_IV]], i64 [[INDVARS_IV27]]
-; CHECK-NEXT:    store i32 [[TMP0]], i32* [[ARRAYIDX8]], align 4
-; CHECK-NEXT:    [[INDVARS_IV_NEXT:%.*]] = add nuw nsw i64 [[INDVARS_IV]], 1
-; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp ne i64 [[INDVARS_IV_NEXT]], [[WIDE_TRIP_COUNT]]
-; CHECK-NEXT:    br label [[INNER_CRIT_EDGE:%.*]]
-; CHECK:       inner.for.body.split:
-; CHECK-NEXT:    [[WIDE_TRIP_COUNT_LCSSA:%.*]] = phi i64 [ [[WIDE_TRIP_COUNT]], [[OUTER_LATCH]] ], [ [[WIDE_TRIP_COUNT]], [[OUTER_HEADER]] ]
-; CHECK-NEXT:    [[TMP1]] = add nuw nsw i64 [[INDVARS_IV]], 1
-; CHECK-NEXT:    [[TMP2:%.*]] = icmp ne i64 [[TMP1]], [[WIDE_TRIP_COUNT_LCSSA]]
-; CHECK-NEXT:    br i1 [[TMP2]], label [[INNER_FOR_BODY]], label [[OUTER_CRIT_EDGE:%.*]]
-; CHECK:       inner.crit_edge:
-; CHECK-NEXT:    br label [[OUTER_LATCH]]
-; CHECK:       outer.latch:
-; CHECK-NEXT:    [[INDVARS_IV_NEXT28]] = add nuw nsw i64 [[INDVARS_IV27]], 1
-; CHECK-NEXT:    [[EXITCOND30:%.*]] = icmp ne i64 [[INDVARS_IV_NEXT28]], [[WIDE_TRIP_COUNT29]]
-; CHECK-NEXT:    br i1 [[EXITCOND30]], label [[OUTER_HEADER]], label [[INNER_FOR_BODY_SPLIT]]
-; CHECK:       outer.crit_edge:
-; CHECK-NEXT:    br label [[FOR_COND_CLEANUP]]
-; CHECK:       for.cond.cleanup:
-; CHECK-NEXT:    ret void
+;; This loop can be interchanged with -da-disable-delinearization-checks, otherwise it cannot
+;; be interchanged due to dependence.
+define void @lcssa_08(i32 %n, i32 %m) {;
+; CHECK-DELIN-LABEL: @lcssa_08(
+; CHECK-DELIN-NEXT:  entry:
+; CHECK-DELIN-NEXT:    [[TEMP:%.*]] = alloca [16 x [16 x i32]], align 4
+; CHECK-DELIN-NEXT:    [[RES:%.*]] = alloca [16 x [16 x i32]], align 4
+; CHECK-DELIN-NEXT:    [[CMP24:%.*]] = icmp sgt i32 [[N:%.*]], 0
+; CHECK-DELIN-NEXT:    br i1 [[CMP24]], label [[INNER_PREHEADER:%.*]], label [[FOR_COND_CLEANUP:%.*]]
+; CHECK-DELIN:       outer.preheader:
+; CHECK-DELIN-NEXT:    br label [[OUTER_HEADER:%.*]]
+; CHECK-DELIN:       outer.header:
+; CHECK-DELIN-NEXT:    [[INDVARS_IV27:%.*]] = phi i64 [ 0, [[OUTER_PREHEADER:%.*]] ], [ [[INDVARS_IV_NEXT28:%.*]], [[OUTER_LATCH:%.*]] ]
+; CHECK-DELIN-NEXT:    [[CMP222:%.*]] = icmp sgt i32 [[M:%.*]], 0
+; CHECK-DELIN-NEXT:    [[WIDE_TRIP_COUNT:%.*]] = zext i32 [[M]] to i64
+; CHECK-DELIN-NEXT:    br i1 [[CMP222]], label [[INNER_FOR_BODY_SPLIT1:%.*]], label [[INNER_FOR_BODY_SPLIT:%.*]]
+; CHECK-DELIN:       inner.preheader:
+; CHECK-DELIN-NEXT:    [[WIDE_TRIP_COUNT29:%.*]] = zext i32 [[N]] to i64
+; CHECK-DELIN-NEXT:    br label [[INNER_FOR_BODY:%.*]]
+; CHECK-DELIN:       inner.for.body:
+; CHECK-DELIN-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ 0, [[INNER_PREHEADER]] ], [ [[TMP1:%.*]], [[INNER_FOR_BODY_SPLIT]] ]
+; CHECK-DELIN-NEXT:    br label [[OUTER_PREHEADER]]
+; CHECK-DELIN:       inner.for.body.split1:
+; CHECK-DELIN-NEXT:    [[ARRAYIDX6:%.*]] = getelementptr inbounds [16 x [16 x i32]], [16 x [16 x i32]]* [[TEMP]], i64 0, i64 [[INDVARS_IV]], i64 [[INDVARS_IV27]]
+; CHECK-DELIN-NEXT:    [[TMP0:%.*]] = load i32, i32* [[ARRAYIDX6]], align 4
+; CHECK-DELIN-NEXT:    [[ARRAYIDX8:%.*]] = getelementptr inbounds [16 x [16 x i32]], [16 x [16 x i32]]* [[RES]], i64 0, i64 [[INDVARS_IV]], i64 [[INDVARS_IV27]]
+; CHECK-DELIN-NEXT:    store i32 [[TMP0]], i32* [[ARRAYIDX8]], align 4
+; CHECK-DELIN-NEXT:    [[INDVARS_IV_NEXT:%.*]] = add nuw nsw i64 [[INDVARS_IV]], 1
+; CHECK-DELIN-NEXT:    [[EXITCOND:%.*]] = icmp ne i64 [[INDVARS_IV_NEXT]], [[WIDE_TRIP_COUNT]]
+; CHECK-DELIN-NEXT:    br label [[INNER_CRIT_EDGE:%.*]]
+; CHECK-DELIN:       inner.for.body.split:
+; CHECK-DELIN-NEXT:    [[WIDE_TRIP_COUNT_LCSSA:%.*]] = phi i64 [ [[WIDE_TRIP_COUNT]], [[OUTER_LATCH]] ], [ [[WIDE_TRIP_COUNT]], [[OUTER_HEADER]] ]
+; CHECK-DELIN-NEXT:    [[TMP1]] = add nuw nsw i64 [[INDVARS_IV]], 1
+; CHECK-DELIN-NEXT:    [[TMP2:%.*]] = icmp ne i64 [[TMP1]], [[WIDE_TRIP_COUNT_LCSSA]]
+; CHECK-DELIN-NEXT:    br i1 [[TMP2]], label [[INNER_FOR_BODY]], label [[OUTER_CRIT_EDGE:%.*]]
+; CHECK-DELIN:       inner.crit_edge:
+; CHECK-DELIN-NEXT:    br label [[OUTER_LATCH]]
+; CHECK-DELIN:       outer.latch:
+; CHECK-DELIN-NEXT:    [[INDVARS_IV_NEXT28]] = add nuw nsw i64 [[INDVARS_IV27]], 1
+; CHECK-DELIN-NEXT:    [[EXITCOND30:%.*]] = icmp ne i64 [[INDVARS_IV_NEXT28]], [[WIDE_TRIP_COUNT29]]
+; CHECK-DELIN-NEXT:    br i1 [[EXITCOND30]], label [[OUTER_HEADER]], label [[INNER_FOR_BODY_SPLIT]]
+; CHECK-DELIN:       outer.crit_edge:
+; CHECK-DELIN-NEXT:    br label [[FOR_COND_CLEANUP]]
+; CHECK-DELIN:       for.cond.cleanup:
+; CHECK-DELIN-NEXT:    ret void
 ;
 entry:
   %temp = alloca [16 x [16 x i32]], align 4
diff --git a/llvm/test/Transforms/LoopInterchange/perserve-lcssa.ll b/llvm/test/Transforms/LoopInterchange/perserve-lcssa.ll
index a1a4d673621a..77546020bf95 100644
--- a/llvm/test/Transforms/LoopInterchange/perserve-lcssa.ll
+++ b/llvm/test/Transforms/LoopInterchange/perserve-lcssa.ll
@@ -5,7 +5,7 @@
 
 @a = common dso_local global i64 0, align 4
 @b = common dso_local global i64 0, align 4
-@c = common dso_local global [10 x [1 x i32 ]] zeroinitializer, align 16
+@c = common dso_local global [10 x [10 x i32 ]] zeroinitializer, align 16
 
 
 define void @test_lcssa_indvars1()  {
@@ -34,7 +34,7 @@ outer.header:                                     ; preds = %outer.latch, %entry
 
 inner.body:                                       ; preds = %inner.body, %outer.header
   %iv.inner = phi i64 [ 5, %outer.header ], [ %iv.inner.next, %inner.body ]
-  %v7 = getelementptr inbounds [10 x [1 x i32]], [10 x [1 x i32]]* @c, i64 0, i64 %iv.inner, i64 %iv.outer
+  %v7 = getelementptr inbounds [10 x [10 x i32]], [10 x [10 x i32]]* @c, i64 0, i64 %iv.inner, i64 %iv.outer
   store i32 0, i32* %v7, align 4
   %iv.inner.next = add nsw i64 %iv.inner, -1
   %v9 = icmp eq i64 %iv.inner, 0
@@ -81,7 +81,7 @@ outer.header:                                     ; preds = %outer.latch, %entry
 
 inner.body:                                       ; preds = %inner.body, %outer.header
   %iv.inner = phi i64 [ 5, %outer.header ], [ %iv.inner.next, %inner.body ]
-  %v7 = getelementptr inbounds [10 x [1 x i32]], [10 x [1 x i32]]* @c, i64 0, i64 %iv.inner, i64 %iv.outer
+  %v7 = getelementptr inbounds [10 x [10 x i32]], [10 x [10 x i32]]* @c, i64 0, i64 %iv.inner, i64 %iv.outer
   store i32 0, i32* %v7, align 4
   %iv.inner.next = add nsw i64 %iv.inner, -1
   %v9 = icmp eq i64 %iv.inner.next, 0
@@ -130,7 +130,7 @@ outer.header:                                     ; preds = %outer.latch, %entry
 
 inner.body:                                       ; preds = %inner.body, %outer.header
   %iv.inner = phi i64 [ 5, %outer.header ], [ %iv.inner.next, %inner.body ]
-  %v7 = getelementptr inbounds [10 x [1 x i32]], [10 x [1 x i32]]* @c, i64 0, i64 %iv.inner, i64 %iv.outer
+  %v7 = getelementptr inbounds [10 x [10 x i32]], [10 x [10 x i32]]* @c, i64 0, i64 %iv.inner, i64 %iv.outer
   store i32 0, i32* %v7, align 4
   %iv.inner.next = add nsw i64 %iv.inner, -1
   %v9 = icmp eq i64 %iv.inner, 0
diff --git a/llvm/test/Transforms/LoopInterchange/pr45743-move-from-inner-preheader.ll b/llvm/test/Transforms/LoopInterchange/pr45743-move-from-inner-preheader.ll
index f50fbb0da8e3..733647761524 100644
--- a/llvm/test/Transforms/LoopInterchange/pr45743-move-from-inner-preheader.ll
+++ b/llvm/test/Transforms/LoopInterchange/pr45743-move-from-inner-preheader.ll
@@ -1,7 +1,7 @@
 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -loop-interchange -S %s | FileCheck %s
 
-@global = external local_unnamed_addr global [2 x [10 x i32]], align 16
+@global = external local_unnamed_addr global [400 x [400 x i32]], align 16
 
 ; We need to move %tmp4 from the inner loop pre header to the outer loop header
 ; before interchanging.
@@ -23,7 +23,7 @@ define void @test1() local_unnamed_addr #0 {
 ; CHECK-NEXT:    [[OUTER_RED]] = phi i32 [ [[RED_NEXT_LCSSA:%.*]], [[INNER_SPLIT]] ], [ 0, [[INNER_PH]] ]
 ; CHECK-NEXT:    br label [[OUTER_HEADER_PREHEADER]]
 ; CHECK:       inner.split1:
-; CHECK-NEXT:    [[PTR:%.*]] = getelementptr inbounds [2 x [10 x i32]], [2 x [10 x i32]]* @global, i64 0, i64 [[INNER_IV]], i64 [[TMP4]]
+; CHECK-NEXT:    [[PTR:%.*]] = getelementptr inbounds [400 x [400 x i32]], [400 x [400 x i32]]* @global, i64 0, i64 [[INNER_IV]], i64 [[TMP4]]
 ; CHECK-NEXT:    store i32 0, i32* [[PTR]], align 4
 ; CHECK-NEXT:    [[RED_NEXT]] = or i32 [[INNER_RED]], 20
 ; CHECK-NEXT:    [[INNER_IV_NEXT:%.*]] = add nsw i64 [[INNER_IV]], 1
@@ -56,7 +56,7 @@ inner.ph:                                              ; preds = %bb1
 inner:                                              ; preds = %bb5, %bb3
   %inner.iv = phi i64 [ 0, %inner.ph ], [ %inner.iv.next, %inner ]
   %inner.red = phi i32 [ %outer.red, %inner.ph ], [ %red.next, %inner ]
-  %ptr = getelementptr inbounds [2 x [10 x i32]], [2 x [10 x i32]]* @global, i64 0, i64 %inner.iv, i64 %tmp4
+  %ptr = getelementptr inbounds [400 x [400 x i32]], [400 x [400 x i32]]* @global, i64 0, i64 %inner.iv, i64 %tmp4
   store i32 0, i32* %ptr
   %red.next = or i32 %inner.red, 20
   %inner.iv.next = add nsw i64 %inner.iv, 1
@@ -93,7 +93,7 @@ define void @test2() {
 ; CHECK:       inner:
 ; CHECK-NEXT:    [[INNER_IV:%.*]] = phi i64 [ 0, [[INNER_PH]] ], [ [[INNER_IV_NEXT:%.*]], [[INNER]] ]
 ; CHECK-NEXT:    [[INNER_RED:%.*]] = phi i32 [ [[OUTER_RED]], [[INNER_PH]] ], [ [[RED_NEXT:%.*]], [[INNER]] ]
-; CHECK-NEXT:    [[PTR:%.*]] = getelementptr inbounds [2 x [10 x i32]], [2 x [10 x i32]]* @global, i64 0, i64 [[INNER_IV]], i64 [[TMP4]]
+; CHECK-NEXT:    [[PTR:%.*]] = getelementptr inbounds [400 x [400 x i32]], [400 x [400 x i32]]* @global, i64 0, i64 [[INNER_IV]], i64 [[TMP4]]
 ; CHECK-NEXT:    store i32 0, i32* [[PTR]], align 4
 ; CHECK-NEXT:    [[RED_NEXT]] = or i32 [[INNER_RED]], 20
 ; CHECK-NEXT:    [[INNER_IV_NEXT]] = add nsw i64 [[INNER_IV]], 1
@@ -123,7 +123,7 @@ inner.ph:                                              ; preds = %bb1
 inner:                                              ; preds = %bb5, %bb3
   %inner.iv = phi i64 [ 0, %inner.ph ], [ %inner.iv.next, %inner ]
   %inner.red = phi i32 [ %outer.red, %inner.ph ], [ %red.next, %inner ]
-  %ptr = getelementptr inbounds [2 x [10 x i32]], [2 x [10 x i32]]* @global, i64 0, i64 %inner.iv, i64 %tmp4
+  %ptr = getelementptr inbounds [400 x [400 x i32]], [400 x [400 x i32]]* @global, i64 0, i64 %inner.iv, i64 %tmp4
   store i32 0, i32* %ptr
   %red.next = or i32 %inner.red, 20
   %inner.iv.next = add nsw i64 %inner.iv, 1