llvm/test/Transforms/LoopInterchange/preserve-lcssa.ll

; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --version 6
; RUN: opt < %s -passes=loop-interchange -loop-interchange-profitabilities=ignore -loop-interchange-threshold=-100 -verify-loop-lcssa -S | FileCheck %s

; Test case for PR41725. The induction variables in the latches escape the
; loops and we must move some PHIs around.

@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 [10 x i32 ]] zeroinitializer, align 16


define void @test_lcssa_indvars1()  {
; CHECK-LABEL: define void @test_lcssa_indvars1() {
; CHECK-NEXT:  [[ENTRY:.*:]]
; CHECK-NEXT:    br label %[[INNER_BODY_PREHEADER:.*]]
; CHECK:       [[OUTER_HEADER_PREHEADER:.*]]:
; CHECK-NEXT:    br label %[[OUTER_HEADER:.*]]
; CHECK:       [[OUTER_HEADER]]:
; CHECK-NEXT:    [[IV_OUTER:%.*]] = phi i64 [ [[IV_OUTER_NEXT:%.*]], %[[OUTER_LATCH:.*]] ], [ 0, %[[OUTER_HEADER_PREHEADER]] ]
; CHECK-NEXT:    br label %[[INNER_BODY_SPLIT1:.*]]
; CHECK:       [[INNER_BODY_PREHEADER]]:
; CHECK-NEXT:    br label %[[INNER_BODY:.*]]
; CHECK:       [[INNER_BODY]]:
; CHECK-NEXT:    [[IV_INNER:%.*]] = phi i64 [ [[TMP1:%.*]], %[[INNER_BODY_SPLIT:.*]] ], [ 5, %[[INNER_BODY_PREHEADER]] ]
; CHECK-NEXT:    br label %[[OUTER_HEADER_PREHEADER]]
; CHECK:       [[INNER_BODY_SPLIT1]]:
; CHECK-NEXT:    [[V7:%.*]] = getelementptr inbounds [10 x [10 x i32]], ptr @c, i64 0, i64 [[IV_INNER]], i64 [[IV_OUTER]]
; CHECK-NEXT:    store i32 0, ptr [[V7]], align 4
; CHECK-NEXT:    [[IV_INNER_NEXT:%.*]] = add nsw i64 [[IV_INNER]], -1
; CHECK-NEXT:    [[V9:%.*]] = icmp eq i64 [[IV_INNER]], 0
; CHECK-NEXT:    br label %[[OUTER_LATCH]]
; CHECK:       [[INNER_BODY_SPLIT]]:
; CHECK-NEXT:    [[TMP0:%.*]] = phi i64 [ [[IV_OUTER_NEXT]], %[[OUTER_LATCH]] ]
; CHECK-NEXT:    [[TMP1]] = add nsw i64 [[IV_INNER]], -1
; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq i64 [[IV_INNER]], 0
; CHECK-NEXT:    br i1 [[TMP2]], label %[[EXIT:.*]], label %[[INNER_BODY]]
; CHECK:       [[OUTER_LATCH]]:
; CHECK-NEXT:    [[IV_OUTER_NEXT]] = add nuw nsw i64 [[IV_OUTER]], 1
; CHECK-NEXT:    [[V5:%.*]] = icmp ult i64 [[IV_OUTER]], 2
; CHECK-NEXT:    br i1 [[V5]], label %[[OUTER_HEADER]], label %[[INNER_BODY_SPLIT]]
; CHECK:       [[EXIT]]:
; CHECK-NEXT:    [[V4_LCSSA:%.*]] = phi i64 [ [[TMP0]], %[[INNER_BODY_SPLIT]] ]
; CHECK-NEXT:    [[V8_LCSSA_LCSSA:%.*]] = phi i64 [ [[TMP1]], %[[INNER_BODY_SPLIT]] ]
; CHECK-NEXT:    store i64 [[V8_LCSSA_LCSSA]], ptr @b, align 4
; CHECK-NEXT:    store i64 [[V4_LCSSA]], ptr @a, align 4
; CHECK-NEXT:    ret void
;
entry:
  br label %outer.header

outer.header:                                     ; preds = %outer.latch, %entry
  %iv.outer = phi i64 [ 0, %entry ], [ %iv.outer.next, %outer.latch ]
  br label %inner.body

inner.body:                                       ; preds = %inner.body, %outer.header
  %iv.inner = phi i64 [ 5, %outer.header ], [ %iv.inner.next, %inner.body ]
  %v7 = getelementptr inbounds [10 x [10 x i32]], ptr @c, i64 0, i64 %iv.inner, i64 %iv.outer
  store i32 0, ptr %v7, align 4
  %iv.inner.next = add nsw i64 %iv.inner, -1
  %v9 = icmp eq i64 %iv.inner, 0
  br i1 %v9, label %outer.latch, label %inner.body

outer.latch:                                      ; preds = %inner.body
  %v8.lcssa = phi i64 [ %iv.inner.next, %inner.body ]
  %iv.outer.next = add nuw nsw i64 %iv.outer, 1
  %v5 = icmp ult i64 %iv.outer, 2
  br i1 %v5, label %outer.header, label %exit

exit:                                             ; preds = %outer.latch
  %v4.lcssa = phi i64 [ %iv.outer.next, %outer.latch ]
  %v8.lcssa.lcssa = phi i64 [ %v8.lcssa, %outer.latch ]
  store i64 %v8.lcssa.lcssa, ptr @b, align 4
  store i64 %v4.lcssa, ptr @a, align 4
  ret void
}


define void @test_lcssa_indvars2()  {
; CHECK-LABEL: define void @test_lcssa_indvars2() {
; CHECK-NEXT:  [[ENTRY:.*:]]
; CHECK-NEXT:    br label %[[INNER_BODY_PREHEADER:.*]]
; CHECK:       [[OUTER_HEADER_PREHEADER:.*]]:
; CHECK-NEXT:    br label %[[OUTER_HEADER:.*]]
; CHECK:       [[OUTER_HEADER]]:
; CHECK-NEXT:    [[IV_OUTER:%.*]] = phi i64 [ [[IV_OUTER_NEXT:%.*]], %[[OUTER_LATCH:.*]] ], [ 0, %[[OUTER_HEADER_PREHEADER]] ]
; CHECK-NEXT:    br label %[[INNER_BODY_SPLIT1:.*]]
; CHECK:       [[INNER_BODY_PREHEADER]]:
; CHECK-NEXT:    br label %[[INNER_BODY:.*]]
; CHECK:       [[INNER_BODY]]:
; CHECK-NEXT:    [[IV_INNER:%.*]] = phi i64 [ [[TMP1:%.*]], %[[INNER_BODY_SPLIT:.*]] ], [ 5, %[[INNER_BODY_PREHEADER]] ]
; CHECK-NEXT:    br label %[[OUTER_HEADER_PREHEADER]]
; CHECK:       [[INNER_BODY_SPLIT1]]:
; CHECK-NEXT:    [[V7:%.*]] = getelementptr inbounds [10 x [10 x i32]], ptr @c, i64 0, i64 [[IV_INNER]], i64 [[IV_OUTER]]
; CHECK-NEXT:    store i32 0, ptr [[V7]], align 4
; CHECK-NEXT:    [[IV_INNER_NEXT:%.*]] = add nsw i64 [[IV_INNER]], -1
; CHECK-NEXT:    [[V9:%.*]] = icmp eq i64 [[IV_INNER_NEXT]], 0
; CHECK-NEXT:    br label %[[OUTER_LATCH]]
; CHECK:       [[INNER_BODY_SPLIT]]:
; CHECK-NEXT:    [[TMP0:%.*]] = phi i64 [ [[IV_OUTER]], %[[OUTER_LATCH]] ]
; CHECK-NEXT:    [[TMP1]] = add nsw i64 [[IV_INNER]], -1
; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq i64 [[TMP1]], 0
; CHECK-NEXT:    br i1 [[TMP2]], label %[[EXIT:.*]], label %[[INNER_BODY]]
; CHECK:       [[OUTER_LATCH]]:
; CHECK-NEXT:    [[IV_OUTER_NEXT]] = add nuw nsw i64 [[IV_OUTER]], 1
; CHECK-NEXT:    [[V5:%.*]] = icmp ult i64 [[IV_OUTER_NEXT]], 2
; CHECK-NEXT:    br i1 [[V5]], label %[[OUTER_HEADER]], label %[[INNER_BODY_SPLIT]]
; CHECK:       [[EXIT]]:
; CHECK-NEXT:    [[V4_LCSSA:%.*]] = phi i64 [ [[TMP0]], %[[INNER_BODY_SPLIT]] ]
; CHECK-NEXT:    [[V8_LCSSA_LCSSA:%.*]] = phi i64 [ [[IV_INNER]], %[[INNER_BODY_SPLIT]] ]
; CHECK-NEXT:    store i64 [[V8_LCSSA_LCSSA]], ptr @b, align 4
; CHECK-NEXT:    store i64 [[V4_LCSSA]], ptr @a, align 4
; CHECK-NEXT:    ret void
;
entry:
  br label %outer.header

outer.header:                                     ; preds = %outer.latch, %entry
  %iv.outer = phi i64 [ 0, %entry ], [ %iv.outer.next, %outer.latch ]
  br label %inner.body

inner.body:                                       ; preds = %inner.body, %outer.header
  %iv.inner = phi i64 [ 5, %outer.header ], [ %iv.inner.next, %inner.body ]
  %v7 = getelementptr inbounds [10 x [10 x i32]], ptr @c, i64 0, i64 %iv.inner, i64 %iv.outer
  store i32 0, ptr %v7, align 4
  %iv.inner.next = add nsw i64 %iv.inner, -1
  %v9 = icmp eq i64 %iv.inner.next, 0
  br i1 %v9, label %outer.latch, label %inner.body

outer.latch:                                      ; preds = %inner.body
  %v8.lcssa = phi i64 [ %iv.inner, %inner.body ]
  %iv.outer.next = add nuw nsw i64 %iv.outer, 1
  %v5 = icmp ult i64 %iv.outer.next, 2
  br i1 %v5, label %outer.header, label %exit

exit:                                             ; preds = %outer.latch
  %v4.lcssa = phi i64 [ %iv.outer, %outer.latch ]
  %v8.lcssa.lcssa = phi i64 [ %v8.lcssa, %outer.latch ]
  store i64 %v8.lcssa.lcssa, ptr @b, align 4
  store i64 %v4.lcssa, ptr @a, align 4
  ret void
}

define void @test_lcssa_indvars3()  {
; CHECK-LABEL: define void @test_lcssa_indvars3() {
; CHECK-NEXT:  [[ENTRY:.*:]]
; CHECK-NEXT:    br label %[[INNER_BODY_PREHEADER:.*]]
; CHECK:       [[OUTER_HEADER_PREHEADER:.*]]:
; CHECK-NEXT:    br label %[[OUTER_HEADER:.*]]
; CHECK:       [[OUTER_HEADER]]:
; CHECK-NEXT:    [[IV_OUTER:%.*]] = phi i64 [ [[IV_OUTER_NEXT:%.*]], %[[OUTER_LATCH:.*]] ], [ 0, %[[OUTER_HEADER_PREHEADER]] ]
; CHECK-NEXT:    br label %[[INNER_BODY_SPLIT1:.*]]
; CHECK:       [[INNER_BODY_PREHEADER]]:
; CHECK-NEXT:    br label %[[INNER_BODY:.*]]
; CHECK:       [[INNER_BODY]]:
; CHECK-NEXT:    [[IV_INNER:%.*]] = phi i64 [ [[TMP1:%.*]], %[[INNER_BODY_SPLIT:.*]] ], [ 5, %[[INNER_BODY_PREHEADER]] ]
; CHECK-NEXT:    br label %[[OUTER_HEADER_PREHEADER]]
; CHECK:       [[INNER_BODY_SPLIT1]]:
; CHECK-NEXT:    [[V7:%.*]] = getelementptr inbounds [10 x [10 x i32]], ptr @c, i64 0, i64 [[IV_INNER]], i64 [[IV_OUTER]]
; CHECK-NEXT:    store i32 0, ptr [[V7]], align 4
; CHECK-NEXT:    [[IV_INNER_NEXT:%.*]] = add nsw i64 [[IV_INNER]], -1
; CHECK-NEXT:    [[V9:%.*]] = icmp eq i64 [[IV_INNER]], 0
; CHECK-NEXT:    br label %[[OUTER_LATCH]]
; CHECK:       [[INNER_BODY_SPLIT]]:
; CHECK-NEXT:    [[TMP0:%.*]] = phi i64 [ [[IV_OUTER_NEXT]], %[[OUTER_LATCH]] ]
; CHECK-NEXT:    [[TMP1]] = add nsw i64 [[IV_INNER]], -1
; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq i64 [[IV_INNER]], 0
; CHECK-NEXT:    br i1 [[TMP2]], label %[[EXIT:.*]], label %[[INNER_BODY]]
; CHECK:       [[OUTER_LATCH]]:
; CHECK-NEXT:    [[IV_OUTER_NEXT]] = add nuw nsw i64 [[IV_OUTER]], 1
; CHECK-NEXT:    [[V5:%.*]] = icmp ult i64 [[IV_OUTER]], 2
; CHECK-NEXT:    br i1 [[V5]], label %[[OUTER_HEADER]], label %[[INNER_BODY_SPLIT]]
; CHECK:       [[EXIT]]:
; CHECK-NEXT:    [[V4_LCSSA:%.*]] = phi i64 [ [[TMP0]], %[[INNER_BODY_SPLIT]] ]
; CHECK-NEXT:    [[V8_LCSSA_LCSSA:%.*]] = phi i64 [ [[TMP1]], %[[INNER_BODY_SPLIT]] ]
; CHECK-NEXT:    [[V8_LCSSA_LCSSA_2:%.*]] = phi i64 [ [[TMP1]], %[[INNER_BODY_SPLIT]] ]
; CHECK-NEXT:    [[R1:%.*]] = add i64 [[V8_LCSSA_LCSSA]], [[V8_LCSSA_LCSSA_2]]
; CHECK-NEXT:    store i64 [[R1]], ptr @b, align 4
; CHECK-NEXT:    store i64 [[V4_LCSSA]], ptr @a, align 4
; CHECK-NEXT:    ret void
;
entry:
  br label %outer.header

outer.header:                                     ; preds = %outer.latch, %entry
  %iv.outer = phi i64 [ 0, %entry ], [ %iv.outer.next, %outer.latch ]
  br label %inner.body

inner.body:                                       ; preds = %inner.body, %outer.header
  %iv.inner = phi i64 [ 5, %outer.header ], [ %iv.inner.next, %inner.body ]
  %v7 = getelementptr inbounds [10 x [10 x i32]], ptr @c, i64 0, i64 %iv.inner, i64 %iv.outer
  store i32 0, ptr %v7, align 4
  %iv.inner.next = add nsw i64 %iv.inner, -1
  %v9 = icmp eq i64 %iv.inner, 0
  br i1 %v9, label %outer.latch, label %inner.body

outer.latch:                                      ; preds = %inner.body
  %v8.lcssa = phi i64 [ %iv.inner.next, %inner.body ]
  ;%const.lcssa = phi i64 [ 111, %inner.body ]
  %iv.outer.next = add nuw nsw i64 %iv.outer, 1
  %v5 = icmp ult i64 %iv.outer, 2
  br i1 %v5, label %outer.header, label %exit

exit:                                             ; preds = %outer.latch
  %v4.lcssa = phi i64 [ %iv.outer.next, %outer.latch ]
  %v8.lcssa.lcssa = phi i64 [ %v8.lcssa, %outer.latch ]
  %v8.lcssa.lcssa.2 = phi i64 [ %v8.lcssa, %outer.latch ]
  %r1 = add i64 %v8.lcssa.lcssa, %v8.lcssa.lcssa.2
  store i64 %r1, ptr @b, align 4
  store i64 %v4.lcssa, ptr @a, align 4
  ret void
}


; Make sure we do not crash for loops without reachable exits.
define void @no_reachable_exits(i1 %c0, i1 %c1, i1 %c2, ptr %p) {
; CHECK-LABEL: define void @no_reachable_exits(
; CHECK-SAME: i1 [[C0:%.*]], i1 [[C1:%.*]], i1 [[C2:%.*]], ptr [[P:%.*]]) {
; CHECK-NEXT:  [[BB:.*:]]
; CHECK-NEXT:    br label %[[OUTER_PH:.*]]
; CHECK:       [[OUTER_PH]]:
; CHECK-NEXT:    br label %[[OUTER_HEADER:.*]]
; CHECK:       [[OUTER_HEADER]]:
; CHECK-NEXT:    [[TMP2:%.*]] = phi i32 [ 0, %[[OUTER_PH]] ], [ [[TMP8:%.*]], %[[OUTER_LATCH:.*]] ]
; CHECK-NEXT:    br i1 [[C0]], label %[[INNER_PH:.*]], label %[[OUTER_LATCH]]
; CHECK:       [[INNER_PH]]:
; CHECK-NEXT:    br label %[[INNER_BODY:.*]]
; CHECK:       [[INNER_BODY]]:
; CHECK-NEXT:    [[TMP31:%.*]] = phi i32 [ 0, %[[INNER_PH]] ], [ [[TMP6:%.*]], %[[INNER_BODY]] ]
; CHECK-NEXT:    [[TMP5:%.*]] = load ptr, ptr [[P]], align 8
; CHECK-NEXT:    [[TMP6]] = add nsw i32 [[TMP31]], 1
; CHECK-NEXT:    br i1 [[C1]], label %[[INNER_BODY]], label %[[OUTER_LATCH_LOOPEXIT:.*]]
; CHECK:       [[OUTER_LATCH_LOOPEXIT]]:
; CHECK-NEXT:    br label %[[OUTER_LATCH]]
; CHECK:       [[OUTER_LATCH]]:
; CHECK-NEXT:    [[TMP8]] = add nsw i32 [[TMP2]], 1
; CHECK-NEXT:    br i1 [[C2]], label %[[OUTER_HEADER]], label %[[EXIT:.*]]
; CHECK:       [[EXIT]]:
; CHECK-NEXT:    unreachable
;
bb:
  br label %outer.ph

outer.ph:                              ; preds = %bb
  br label %outer.header

outer.header:                                    ; preds = %outer.ph, %outer.latch
  %tmp2 = phi i32 [ 0, %outer.ph ], [ %tmp8, %outer.latch ]
  br i1 %c0, label %inner.ph, label %outer.latch

inner.ph:                                        ; preds = %outer.header
  br label %inner.body

inner.body:                                              ; preds = %inner.ph, %inner.body
  %tmp31 = phi i32 [ 0, %inner.ph ], [ %tmp6, %inner.body]
  %tmp5 = load ptr, ptr %p, align 8
  %tmp6 = add nsw i32 %tmp31, 1
  br i1 %c1, label %inner.body, label %outer.latch

outer.latch:                                              ; preds = %inner.body, %outer.header
  %tmp8 = add nsw i32 %tmp2, 1
  br i1 %c2, label %outer.header, label %exit

exit:                                              ; preds = %outer.latch
  unreachable
}