test/Transforms/IndVarSimplify/skip-predication-infinite-subloop.ll

; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
; RUN: opt < %s -passes=indvars -indvars-predicate-loops=1 -S | FileCheck %s

; Predication must be skipped if an observable infinite loop may exist in the
; loop nest.
define void @infinite_subloop_skips_predication() {
; CHECK-LABEL: @infinite_subloop_skips_predication(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    br label [[OUTER_HEADER:%.*]]
; CHECK:       outer.header:
; CHECK-NEXT:    [[IV:%.*]] = phi i8 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[OUTER_LATCH:%.*]] ]
; CHECK-NEXT:    br label [[INNER_HEADER:%.*]]
; CHECK:       exit:
; CHECK-NEXT:    ret void
; CHECK:       inner.header:
; CHECK-NEXT:    [[INNER_COND:%.*]] = icmp eq i8 [[IV]], 1
; CHECK-NEXT:    br i1 [[INNER_COND]], label [[INNER_HEADER]], label [[OUTER_LATCH]]
; CHECK:       outer.latch:
; CHECK-NEXT:    [[IV_NEXT]] = add nuw i8 [[IV]], 1
; CHECK-NEXT:    [[OUTER_COND:%.*]] = icmp eq i8 [[IV_NEXT]], -1
; CHECK-NEXT:    br i1 [[OUTER_COND]], label [[EXIT:%.*]], label [[OUTER_HEADER]]
;
entry:
  br label %outer.header

outer.header:
  %iv = phi i8 [ 0, %entry ], [ %iv.next, %outer.latch ]
  br label %inner.header

exit:
  ret void

inner.header:
  %inner.cond = icmp eq i8 %iv, 1
  br i1 %inner.cond, label %inner.header, label %outer.latch

outer.latch:
  %iv.next = add nuw i8 %iv, 1
  %outer.cond = icmp eq i8 %iv.next, -1
  br i1 %outer.cond, label %exit, label %outer.header
}

; !llvm.loop.mustprogress makes the side-effect-free inner loop finite.
define void @mustprogress_subloop_still_predicated() {
; CHECK-LABEL: @mustprogress_subloop_still_predicated(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    br label [[OUTER_HEADER:%.*]]
; CHECK:       outer.header:
; CHECK-NEXT:    [[IV:%.*]] = phi i8 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[OUTER_LATCH:%.*]] ]
; CHECK-NEXT:    br label [[INNER_HEADER:%.*]]
; CHECK:       exit:
; CHECK-NEXT:    ret void
; CHECK:       inner.header:
; CHECK-NEXT:    [[INNER_COND:%.*]] = icmp eq i8 [[IV]], 1
; CHECK-NEXT:    br i1 [[INNER_COND]], label [[INNER_HEADER]], label [[OUTER_LATCH]], !llvm.loop [[LOOP0:![0-9]+]]
; CHECK:       outer.latch:
; CHECK-NEXT:    [[IV_NEXT]] = add nuw i8 [[IV]], 1
; CHECK-NEXT:    br i1 true, label [[EXIT:%.*]], label [[OUTER_HEADER]]
;
entry:
  br label %outer.header

outer.header:
  %iv = phi i8 [ 0, %entry ], [ %iv.next, %outer.latch ]
  br label %inner.header

exit:
  ret void

inner.header:
  %inner.cond = icmp eq i8 %iv, 1
  br i1 %inner.cond, label %inner.header, label %outer.latch, !llvm.loop !0

outer.latch:
  %iv.next = add nuw i8 %iv, 1
  %outer.cond = icmp eq i8 %iv.next, -1
  br i1 %outer.cond, label %exit, label %outer.header
}

; A mustprogress function makes the side-effect-free nest finite.
define void @mustprogress_function_subloop_predicated() mustprogress {
; CHECK-LABEL: @mustprogress_function_subloop_predicated(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    br label [[OUTER_HEADER:%.*]]
; CHECK:       outer.header:
; CHECK-NEXT:    [[IV:%.*]] = phi i8 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[OUTER_LATCH:%.*]] ]
; CHECK-NEXT:    br label [[INNER_HEADER:%.*]]
; CHECK:       exit:
; CHECK-NEXT:    ret void
; CHECK:       inner.header:
; CHECK-NEXT:    [[INNER_COND:%.*]] = icmp eq i8 [[IV]], 1
; CHECK-NEXT:    br i1 [[INNER_COND]], label [[INNER_HEADER]], label [[OUTER_LATCH]]
; CHECK:       outer.latch:
; CHECK-NEXT:    [[IV_NEXT]] = add nuw i8 [[IV]], 1
; CHECK-NEXT:    br i1 true, label [[EXIT:%.*]], label [[OUTER_HEADER]]
;
entry:
  br label %outer.header

outer.header:
  %iv = phi i8 [ 0, %entry ], [ %iv.next, %outer.latch ]
  br label %inner.header

exit:
  ret void

inner.header:
  %inner.cond = icmp eq i8 %iv, 1
  br i1 %inner.cond, label %inner.header, label %outer.latch

outer.latch:
  %iv.next = add nuw i8 %iv, 1
  %outer.cond = icmp eq i8 %iv.next, -1
  br i1 %outer.cond, label %exit, label %outer.header
}

; Likewise for willreturn.
define void @willreturn_function_subloop_predicated() willreturn {
; CHECK-LABEL: @willreturn_function_subloop_predicated(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    br label [[OUTER_HEADER:%.*]]
; CHECK:       outer.header:
; CHECK-NEXT:    [[IV:%.*]] = phi i8 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[OUTER_LATCH:%.*]] ]
; CHECK-NEXT:    br label [[INNER_HEADER:%.*]]
; CHECK:       exit:
; CHECK-NEXT:    ret void
; CHECK:       inner.header:
; CHECK-NEXT:    [[INNER_COND:%.*]] = icmp eq i8 [[IV]], 1
; CHECK-NEXT:    br i1 [[INNER_COND]], label [[INNER_HEADER]], label [[OUTER_LATCH]]
; CHECK:       outer.latch:
; CHECK-NEXT:    [[IV_NEXT]] = add nuw i8 [[IV]], 1
; CHECK-NEXT:    br i1 true, label [[EXIT:%.*]], label [[OUTER_HEADER]]
;
entry:
  br label %outer.header

outer.header:
  %iv = phi i8 [ 0, %entry ], [ %iv.next, %outer.latch ]
  br label %inner.header

exit:
  ret void

inner.header:
  %inner.cond = icmp eq i8 %iv, 1
  br i1 %inner.cond, label %inner.header, label %outer.latch

outer.latch:
  %iv.next = add nuw i8 %iv, 1
  %outer.cond = icmp eq i8 %iv.next, -1
  br i1 %outer.cond, label %exit, label %outer.header
}

; The irreducible cycle may run forever (iv == 1), so predication is skipped.
define void @irreducible_cycle_skips_predication() {
; CHECK-LABEL: @irreducible_cycle_skips_predication(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    br label [[OUTER_HEADER:%.*]]
; CHECK:       outer.header:
; CHECK-NEXT:    [[IV:%.*]] = phi i8 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[OUTER_LATCH:%.*]] ]
; CHECK-NEXT:    [[C:%.*]] = icmp eq i8 [[IV]], 1
; CHECK-NEXT:    br i1 [[C]], label [[IRR_A:%.*]], label [[IRR_B:%.*]]
; CHECK:       irr.a:
; CHECK-NEXT:    br i1 [[C]], label [[IRR_B]], label [[OUTER_LATCH]]
; CHECK:       irr.b:
; CHECK-NEXT:    br i1 [[C]], label [[IRR_A]], label [[OUTER_LATCH]]
; CHECK:       exit:
; CHECK-NEXT:    ret void
; CHECK:       outer.latch:
; CHECK-NEXT:    [[IV_NEXT]] = add nuw i8 [[IV]], 1
; CHECK-NEXT:    [[OUTER_COND:%.*]] = icmp eq i8 [[IV_NEXT]], -1
; CHECK-NEXT:    br i1 [[OUTER_COND]], label [[EXIT:%.*]], label [[OUTER_HEADER]]
;
entry:
  br label %outer.header

outer.header:
  %iv = phi i8 [ 0, %entry ], [ %iv.next, %outer.latch ]
  %c = icmp eq i8 %iv, 1
  br i1 %c, label %irr.a, label %irr.b

irr.a:
  br i1 %c, label %irr.b, label %outer.latch

irr.b:
  br i1 %c, label %irr.a, label %outer.latch

exit:
  ret void

outer.latch:
  %iv.next = add nuw i8 %iv, 1
  %outer.cond = icmp eq i8 %iv.next, -1
  br i1 %outer.cond, label %exit, label %outer.header
}

; !llvm.loop.mustprogress on the outer loop also covers the irreducible cycle.
define void @mustprogress_outer_irreducible_cycle_predicated() {
; CHECK-LABEL: @mustprogress_outer_irreducible_cycle_predicated(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    br label [[OUTER_HEADER:%.*]]
; CHECK:       outer.header:
; CHECK-NEXT:    [[IV:%.*]] = phi i8 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[OUTER_LATCH:%.*]] ]
; CHECK-NEXT:    [[C:%.*]] = icmp eq i8 [[IV]], 1
; CHECK-NEXT:    br i1 [[C]], label [[IRR_A:%.*]], label [[IRR_B:%.*]]
; CHECK:       irr.a:
; CHECK-NEXT:    br i1 [[C]], label [[IRR_B]], label [[OUTER_LATCH]]
; CHECK:       irr.b:
; CHECK-NEXT:    br i1 [[C]], label [[IRR_A]], label [[OUTER_LATCH]]
; CHECK:       exit:
; CHECK-NEXT:    ret void
; CHECK:       outer.latch:
; CHECK-NEXT:    [[IV_NEXT]] = add nuw i8 [[IV]], 1
; CHECK-NEXT:    br i1 true, label [[EXIT:%.*]], label [[OUTER_HEADER]], !llvm.loop [[LOOP2:![0-9]+]]
;
entry:
  br label %outer.header

outer.header:
  %iv = phi i8 [ 0, %entry ], [ %iv.next, %outer.latch ]
  %c = icmp eq i8 %iv, 1
  br i1 %c, label %irr.a, label %irr.b

irr.a:
  br i1 %c, label %irr.b, label %outer.latch

irr.b:
  br i1 %c, label %irr.a, label %outer.latch

exit:
  ret void

outer.latch:
  %iv.next = add nuw i8 %iv, 1
  %outer.cond = icmp eq i8 %iv.next, -1
  br i1 %outer.cond, label %exit, label %outer.header, !llvm.loop !2
}

!0 = distinct !{!0, !1}
!1 = !{!"llvm.loop.mustprogress"}
!2 = distinct !{!2, !1}