test/Transforms/LoopVectorize/early-exit-branch-weights.ll

; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --filter "br i1|= select |!prof|!llvm.loop|^.*:" --version 6
; RUN: opt -passes=loop-vectorize -force-vector-width=4 -force-vector-interleave=1 -S %s | FileCheck %s --check-prefix=VF4
; RUN: opt -passes=loop-vectorize -force-vector-width=2 -force-vector-interleave=1 -S %s | FileCheck %s --check-prefix=VF2

; The uncountable exit is taken with probability 1/4 per original iteration.
define i64 @early_exit_taken_1_in_4(ptr dereferenceable(1024) %a) !prof !0 {
; VF4-LABEL: define i64 @early_exit_taken_1_in_4(
; VF4-SAME: ptr dereferenceable(1024) [[A:%.*]]) !prof [[PROF0:![0-9]+]] {
; VF4:  [[ENTRY:.*:]]
; VF4:  [[VECTOR_PH:.*:]]
; VF4:  [[VECTOR_BODY:.*]]:
; VF4:    br i1 [[TMP3:%.*]], label %[[VECTOR_EARLY_EXIT:.*]], label %[[VECTOR_BODY_INTERIM:.*]]
; VF4:  [[VECTOR_BODY_INTERIM]]:
; VF4:    br i1 [[TMP4:%.*]], label %[[MIDDLE_BLOCK:.*]], label %[[VECTOR_BODY]], !llvm.loop [[LOOP1:![0-9]+]]
; VF4:  [[MIDDLE_BLOCK]]:
; VF4:  [[VECTOR_EARLY_EXIT]]:
; VF4:  [[FOUND:.*:]]
; VF4:  [[EXIT:.*:]]
;
; VF2-LABEL: define i64 @early_exit_taken_1_in_4(
; VF2-SAME: ptr dereferenceable(1024) [[A:%.*]]) !prof [[PROF0:![0-9]+]] {
; VF2:  [[ENTRY:.*:]]
; VF2:  [[VECTOR_PH:.*:]]
; VF2:  [[VECTOR_BODY:.*]]:
; VF2:    br i1 [[TMP3:%.*]], label %[[VECTOR_EARLY_EXIT:.*]], label %[[VECTOR_BODY_INTERIM:.*]]
; VF2:  [[VECTOR_BODY_INTERIM]]:
; VF2:    br i1 [[TMP4:%.*]], label %[[MIDDLE_BLOCK:.*]], label %[[VECTOR_BODY]], !llvm.loop [[LOOP1:![0-9]+]]
; VF2:  [[MIDDLE_BLOCK]]:
; VF2:  [[VECTOR_EARLY_EXIT]]:
; VF2:  [[FOUND:.*:]]
; VF2:  [[EXIT:.*:]]
;
entry:
  br label %loop.header

loop.header:
  %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop.latch ]
  %gep = getelementptr inbounds i8, ptr %a, i64 %iv
  %l = load i8, ptr %gep, align 1
  %c = icmp eq i8 %l, 42
  br i1 %c, label %found, label %loop.latch, !prof !1

loop.latch:
  %iv.next = add nuw i64 %iv, 1
  %ec = icmp eq i64 %iv.next, 1024
  br i1 %ec, label %exit, label %loop.header

found:
  ret i64 %iv

exit:
  ret i64 -1
}

; Same, with the early exit as the false successor, so the weights are reversed.
define i64 @early_exit_negated(ptr dereferenceable(1024) %a) !prof !0 {
; VF4-LABEL: define i64 @early_exit_negated(
; VF4-SAME: ptr dereferenceable(1024) [[A:%.*]]) !prof [[PROF0]] {
; VF4:  [[ENTRY:.*:]]
; VF4:  [[VECTOR_PH:.*:]]
; VF4:  [[VECTOR_BODY:.*]]:
; VF4:    br i1 [[TMP3:%.*]], label %[[VECTOR_EARLY_EXIT:.*]], label %[[VECTOR_BODY_INTERIM:.*]]
; VF4:  [[VECTOR_BODY_INTERIM]]:
; VF4:    br i1 [[TMP4:%.*]], label %[[MIDDLE_BLOCK:.*]], label %[[VECTOR_BODY]], !llvm.loop [[LOOP4:![0-9]+]]
; VF4:  [[MIDDLE_BLOCK]]:
; VF4:  [[VECTOR_EARLY_EXIT]]:
; VF4:  [[FOUND:.*:]]
; VF4:  [[EXIT:.*:]]
;
; VF2-LABEL: define i64 @early_exit_negated(
; VF2-SAME: ptr dereferenceable(1024) [[A:%.*]]) !prof [[PROF0]] {
; VF2:  [[ENTRY:.*:]]
; VF2:  [[VECTOR_PH:.*:]]
; VF2:  [[VECTOR_BODY:.*]]:
; VF2:    br i1 [[TMP3:%.*]], label %[[VECTOR_EARLY_EXIT:.*]], label %[[VECTOR_BODY_INTERIM:.*]]
; VF2:  [[VECTOR_BODY_INTERIM]]:
; VF2:    br i1 [[TMP4:%.*]], label %[[MIDDLE_BLOCK:.*]], label %[[VECTOR_BODY]], !llvm.loop [[LOOP4:![0-9]+]]
; VF2:  [[MIDDLE_BLOCK]]:
; VF2:  [[VECTOR_EARLY_EXIT]]:
; VF2:  [[FOUND:.*:]]
; VF2:  [[EXIT:.*:]]
;
entry:
  br label %loop.header

loop.header:
  %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop.latch ]
  %gep = getelementptr inbounds i8, ptr %a, i64 %iv
  %l = load i8, ptr %gep, align 1
  %c = icmp ne i8 %l, 42
  br i1 %c, label %loop.latch, label %found, !prof !2

loop.latch:
  %iv.next = add nuw i64 %iv, 1
  %ec = icmp eq i64 %iv.next, 1024
  br i1 %ec, label %exit, label %loop.header

found:
  ret i64 %iv

exit:
  ret i64 -1
}

; Without weights on the original exit condition there is nothing to derive.
define i64 @early_exit_no_weights(ptr dereferenceable(1024) %a) !prof !0 {
; VF4-LABEL: define i64 @early_exit_no_weights(
; VF4-SAME: ptr dereferenceable(1024) [[A:%.*]]) !prof [[PROF0]] {
; VF4:  [[ENTRY:.*:]]
; VF4:  [[VECTOR_PH:.*:]]
; VF4:  [[VECTOR_BODY:.*]]:
; VF4:    br i1 [[TMP3:%.*]], label %[[VECTOR_EARLY_EXIT:.*]], label %[[VECTOR_BODY_INTERIM:.*]]
; VF4:  [[VECTOR_BODY_INTERIM]]:
; VF4:    br i1 [[TMP4:%.*]], label %[[MIDDLE_BLOCK:.*]], label %[[VECTOR_BODY]], !llvm.loop [[LOOP5:![0-9]+]]
; VF4:  [[MIDDLE_BLOCK]]:
; VF4:  [[VECTOR_EARLY_EXIT]]:
; VF4:  [[FOUND:.*:]]
; VF4:  [[EXIT:.*:]]
;
; VF2-LABEL: define i64 @early_exit_no_weights(
; VF2-SAME: ptr dereferenceable(1024) [[A:%.*]]) !prof [[PROF0]] {
; VF2:  [[ENTRY:.*:]]
; VF2:  [[VECTOR_PH:.*:]]
; VF2:  [[VECTOR_BODY:.*]]:
; VF2:    br i1 [[TMP3:%.*]], label %[[VECTOR_EARLY_EXIT:.*]], label %[[VECTOR_BODY_INTERIM:.*]]
; VF2:  [[VECTOR_BODY_INTERIM]]:
; VF2:    br i1 [[TMP4:%.*]], label %[[MIDDLE_BLOCK:.*]], label %[[VECTOR_BODY]], !llvm.loop [[LOOP5:![0-9]+]]
; VF2:  [[MIDDLE_BLOCK]]:
; VF2:  [[VECTOR_EARLY_EXIT]]:
; VF2:  [[FOUND:.*:]]
; VF2:  [[EXIT:.*:]]
;
entry:
  br label %loop.header

loop.header:
  %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop.latch ]
  %gep = getelementptr inbounds i8, ptr %a, i64 %iv
  %l = load i8, ptr %gep, align 1
  %c = icmp eq i8 %l, 42
  br i1 %c, label %found, label %loop.latch

loop.latch:
  %iv.next = add nuw i64 %iv, 1
  %ec = icmp eq i64 %iv.next, 1024
  br i1 %ec, label %exit, label %loop.header

found:
  ret i64 %iv

exit:
  ret i64 -1
}

; Which of several uncountable exits a vector iteration takes is not known.
define i64 @three_early_exits(ptr dereferenceable(1024) %a, ptr dereferenceable(1024) %b) !prof !0 {
; VF4-LABEL: define i64 @three_early_exits(
; VF4-SAME: ptr dereferenceable(1024) [[A:%.*]], ptr dereferenceable(1024) [[B:%.*]]) !prof [[PROF0]] {
; VF4:  [[ENTRY:.*:]]
; VF4:  [[VECTOR_PH:.*:]]
; VF4:  [[VECTOR_BODY:.*]]:
; VF4:    [[TMP5:%.*]] = select <4 x i1> [[TMP2:%.*]], <4 x i1> splat (i1 true), <4 x i1> [[TMP3:%.*]]
; VF4:    [[TMP6:%.*]] = select <4 x i1> [[TMP5]], <4 x i1> splat (i1 true), <4 x i1> [[TMP4:%.*]]
; VF4:    br i1 [[TMP8:%.*]], label %[[VECTOR_EARLY_EXIT_CHECK:.*]], label %[[VECTOR_BODY_INTERIM:.*]]
; VF4:  [[VECTOR_BODY_INTERIM]]:
; VF4:    br i1 [[TMP9:%.*]], label %[[MIDDLE_BLOCK:.*]], label %[[VECTOR_BODY]], !llvm.loop [[LOOP6:![0-9]+]]
; VF4:  [[MIDDLE_BLOCK]]:
; VF4:  [[VECTOR_EARLY_EXIT_CHECK]]:
; VF4:    br i1 [[TMP10:%.*]], label %[[VECTOR_EARLY_EXIT_0:.*]], label %[[VECTOR_EARLY_EXIT_CHECK_0:.*]]
; VF4:  [[VECTOR_EARLY_EXIT_CHECK_0]]:
; VF4:    br i1 [[TMP11:%.*]], label %[[VECTOR_EARLY_EXIT_1:.*]], label %[[VECTOR_EARLY_EXIT_2:.*]]
; VF4:  [[VECTOR_EARLY_EXIT_2]]:
; VF4:  [[VECTOR_EARLY_EXIT_1]]:
; VF4:  [[VECTOR_EARLY_EXIT_0]]:
; VF4:  [[EXIT_0:.*:]]
; VF4:  [[EXIT_1:.*:]]
; VF4:  [[EXIT_2:.*:]]
; VF4:  [[EXIT:.*:]]
;
; VF2-LABEL: define i64 @three_early_exits(
; VF2-SAME: ptr dereferenceable(1024) [[A:%.*]], ptr dereferenceable(1024) [[B:%.*]]) !prof [[PROF0]] {
; VF2:  [[ENTRY:.*:]]
; VF2:  [[VECTOR_PH:.*:]]
; VF2:  [[VECTOR_BODY:.*]]:
; VF2:    [[TMP5:%.*]] = select <2 x i1> [[TMP2:%.*]], <2 x i1> splat (i1 true), <2 x i1> [[TMP3:%.*]]
; VF2:    [[TMP6:%.*]] = select <2 x i1> [[TMP5]], <2 x i1> splat (i1 true), <2 x i1> [[TMP4:%.*]]
; VF2:    br i1 [[TMP8:%.*]], label %[[VECTOR_EARLY_EXIT_CHECK:.*]], label %[[VECTOR_BODY_INTERIM:.*]]
; VF2:  [[VECTOR_BODY_INTERIM]]:
; VF2:    br i1 [[TMP9:%.*]], label %[[MIDDLE_BLOCK:.*]], label %[[VECTOR_BODY]], !llvm.loop [[LOOP6:![0-9]+]]
; VF2:  [[MIDDLE_BLOCK]]:
; VF2:  [[VECTOR_EARLY_EXIT_CHECK]]:
; VF2:    br i1 [[TMP10:%.*]], label %[[VECTOR_EARLY_EXIT_0:.*]], label %[[VECTOR_EARLY_EXIT_CHECK_0:.*]]
; VF2:  [[VECTOR_EARLY_EXIT_CHECK_0]]:
; VF2:    br i1 [[TMP11:%.*]], label %[[VECTOR_EARLY_EXIT_1:.*]], label %[[VECTOR_EARLY_EXIT_2:.*]]
; VF2:  [[VECTOR_EARLY_EXIT_2]]:
; VF2:  [[VECTOR_EARLY_EXIT_1]]:
; VF2:  [[VECTOR_EARLY_EXIT_0]]:
; VF2:  [[EXIT_0:.*:]]
; VF2:  [[EXIT_1:.*:]]
; VF2:  [[EXIT_2:.*:]]
; VF2:  [[EXIT:.*:]]
;
entry:
  br label %loop.header

loop.header:
  %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop.latch ]
  %gep.a = getelementptr inbounds i8, ptr %a, i64 %iv
  %l.a = load i8, ptr %gep.a, align 1
  %gep.b = getelementptr inbounds i8, ptr %b, i64 %iv
  %l.b = load i8, ptr %gep.b, align 1
  %c.0 = icmp eq i8 %l.a, %l.b
  br i1 %c.0, label %exit.0, label %check.1

check.1:
  %c.1 = icmp ult i8 %l.a, 34
  br i1 %c.1, label %exit.1, label %check.2

check.2:
  %c.2 = icmp ugt i8 %l.b, 100
  br i1 %c.2, label %exit.2, label %loop.latch

loop.latch:
  %iv.next = add nuw i64 %iv, 1
  %ec = icmp eq i64 %iv.next, 1024
  br i1 %ec, label %exit, label %loop.header

exit.0:
  ret i64 %iv

exit.1:
  ret i64 100

exit.2:
  ret i64 200

exit:
  ret i64 -1
}

define i64 @early_exit_not_profiled(ptr dereferenceable(1024) %a) {
; VF4-LABEL: define i64 @early_exit_not_profiled(
; VF4-SAME: ptr dereferenceable(1024) [[A:%.*]]) {
; VF4:  [[ENTRY:.*:]]
; VF4:  [[VECTOR_PH:.*:]]
; VF4:  [[VECTOR_BODY:.*]]:
; VF4:    br i1 [[TMP3:%.*]], label %[[VECTOR_EARLY_EXIT:.*]], label %[[VECTOR_BODY_INTERIM:.*]]
; VF4:  [[VECTOR_BODY_INTERIM]]:
; VF4:    br i1 [[TMP4:%.*]], label %[[MIDDLE_BLOCK:.*]], label %[[VECTOR_BODY]], !llvm.loop [[LOOP7:![0-9]+]]
; VF4:  [[MIDDLE_BLOCK]]:
; VF4:  [[VECTOR_EARLY_EXIT]]:
; VF4:  [[FOUND:.*:]]
; VF4:  [[EXIT:.*:]]
;
; VF2-LABEL: define i64 @early_exit_not_profiled(
; VF2-SAME: ptr dereferenceable(1024) [[A:%.*]]) {
; VF2:  [[ENTRY:.*:]]
; VF2:  [[VECTOR_PH:.*:]]
; VF2:  [[VECTOR_BODY:.*]]:
; VF2:    br i1 [[TMP3:%.*]], label %[[VECTOR_EARLY_EXIT:.*]], label %[[VECTOR_BODY_INTERIM:.*]]
; VF2:  [[VECTOR_BODY_INTERIM]]:
; VF2:    br i1 [[TMP4:%.*]], label %[[MIDDLE_BLOCK:.*]], label %[[VECTOR_BODY]], !llvm.loop [[LOOP7:![0-9]+]]
; VF2:  [[MIDDLE_BLOCK]]:
; VF2:  [[VECTOR_EARLY_EXIT]]:
; VF2:  [[FOUND:.*:]]
; VF2:  [[EXIT:.*:]]
;
entry:
  br label %loop.header

loop.header:
  %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop.latch ]
  %gep = getelementptr inbounds i8, ptr %a, i64 %iv
  %l = load i8, ptr %gep, align 1
  %c = icmp eq i8 %l, 42
  br i1 %c, label %found, label %loop.latch, !prof !1

loop.latch:
  %iv.next = add nuw i64 %iv, 1
  %ec = icmp eq i64 %iv.next, 1024
  br i1 %ec, label %exit, label %loop.header

found:
  ret i64 %iv

exit:
  ret i64 -1
}

!0 = !{!"function_entry_count", i64 1000}
!1 = !{!"branch_weights", i32 1, i32 3}
!2 = !{!"branch_weights", i32 3, i32 1}
;.
; VF4: [[PROF0]] = !{!"function_entry_count", i64 1000}
; VF4: [[LOOP1]] = distinct !{[[LOOP1]], [[META2:![0-9]+]], [[META3:![0-9]+]]}
; VF4: [[META2]] = !{!"llvm.loop.isvectorized", i32 1}
; VF4: [[META3]] = !{!"llvm.loop.unroll.runtime.disable"}
; VF4: [[LOOP4]] = distinct !{[[LOOP4]], [[META2]], [[META3]]}
; VF4: [[LOOP5]] = distinct !{[[LOOP5]], [[META2]], [[META3]]}
; VF4: [[LOOP6]] = distinct !{[[LOOP6]], [[META2]], [[META3]]}
; VF4: [[LOOP7]] = distinct !{[[LOOP7]], [[META2]], [[META3]]}
;.
; VF2: [[PROF0]] = !{!"function_entry_count", i64 1000}
; VF2: [[LOOP1]] = distinct !{[[LOOP1]], [[META2:![0-9]+]], [[META3:![0-9]+]]}
; VF2: [[META2]] = !{!"llvm.loop.isvectorized", i32 1}
; VF2: [[META3]] = !{!"llvm.loop.unroll.runtime.disable"}
; VF2: [[LOOP4]] = distinct !{[[LOOP4]], [[META2]], [[META3]]}
; VF2: [[LOOP5]] = distinct !{[[LOOP5]], [[META2]], [[META3]]}
; VF2: [[LOOP6]] = distinct !{[[LOOP6]], [[META2]], [[META3]]}
; VF2: [[LOOP7]] = distinct !{[[LOOP7]], [[META2]], [[META3]]}
;.