llvm/test/Transforms/SLPVectorizer/order-reduction-infinite-loop.ll

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

; Test for infinite loop bug introduced in commit 94e366ef2060 which added
; support for ordered reductions. The worklist processing could re-add
; instructions without tracking which were already visited, causing an
; infinite loop on reduction chains with complex dependencies.
;
; This test ensures the pass completes in reasonable time and doesn't hang.

define void @pr_slp_ordered_reduction_hang(ptr %inp, ptr %out, i32 %itr) {
; CHECK-LABEL: @pr_slp_ordered_reduction_hang(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[VAL1:%.*]] = load float, ptr [[INP:%.*]], align 4
; CHECK-NEXT:    [[ARRAYIDX1:%.*]] = getelementptr inbounds float, ptr [[INP]], i64 1
; CHECK-NEXT:    [[VAL2:%.*]] = load float, ptr [[ARRAYIDX1]], align 4
; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt i32 [[ITR:%.*]], 0
; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP:%.*]], label [[EXIT:%.*]]
; CHECK:       loop:
; CHECK-NEXT:    [[I:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[INC:%.*]], [[LOOP]] ]
; CHECK-NEXT:    [[X1:%.*]] = phi float [ [[VAL1]], [[ENTRY]] ], [ [[ADD49_7:%.*]], [[LOOP]] ]
; CHECK-NEXT:    [[Y1:%.*]] = phi float [ [[VAL2]], [[ENTRY]] ], [ [[ADD47_7:%.*]], [[LOOP]] ]
; CHECK:         [[INC]] = add nuw nsw i32 [[I]], 1
; CHECK-NEXT:    [[CMP_LOOP:%.*]] = icmp slt i32 [[INC]], [[ITR]]
; CHECK-NEXT:    br i1 [[CMP_LOOP]], label [[LOOP]], label [[EXIT]]
; CHECK:       exit:
; CHECK-NEXT:    [[RESULT:%.*]] = phi float [ [[VAL1]], [[ENTRY]] ], [ [[ADD49_7]], [[LOOP]] ]
; CHECK-NEXT:    store float [[RESULT]], ptr [[OUT:%.*]], align 4
; CHECK-NEXT:    ret void
;
entry:
  %val1 = load float, ptr %inp, align 4
  %arrayidx1 = getelementptr inbounds float, ptr %inp, i64 1
  %val2 = load float, ptr %arrayidx1, align 4
  %cmp = icmp sgt i32 %itr, 0
  br i1 %cmp, label %loop, label %exit

loop:
  %i = phi i32 [ 0, %entry ], [ %inc, %loop ]
  %x1 = phi float [ %val1, %entry ], [ %add49.7, %loop ]
  %y1 = phi float [ %val2, %entry ], [ %add47.7, %loop ]

  ; Multiple iterations of fibonacci-like fadd chain
  ; Each value depends on the previous two, creating a complex
  ; dependency pattern that triggers the ordered reduction path
  %add35 = fadd float %y1, %x1
  %add37 = fadd float %x1, %add35
  %add39 = fadd float %add35, %add37
  %add41 = fadd float %add37, %add39
  %add43 = fadd float %add39, %add41
  %add45 = fadd float %add41, %add43
  %add47 = fadd float %add43, %add45
  %add49 = fadd float %add45, %add47

  %add35.1 = fadd float %add47, %add49
  %add37.1 = fadd float %add49, %add35.1
  %add39.1 = fadd float %add35.1, %add37.1
  %add41.1 = fadd float %add37.1, %add39.1
  %add43.1 = fadd float %add39.1, %add41.1
  %add45.1 = fadd float %add41.1, %add43.1
  %add47.1 = fadd float %add43.1, %add45.1
  %add49.1 = fadd float %add45.1, %add47.1

  %add35.2 = fadd float %add47.1, %add49.1
  %add37.2 = fadd float %add49.1, %add35.2
  %add39.2 = fadd float %add35.2, %add37.2
  %add41.2 = fadd float %add37.2, %add39.2
  %add43.2 = fadd float %add39.2, %add41.2
  %add45.2 = fadd float %add41.2, %add43.2
  %add47.2 = fadd float %add43.2, %add45.2
  %add49.2 = fadd float %add45.2, %add47.2

  %add35.3 = fadd float %add47.2, %add49.2
  %add37.3 = fadd float %add49.2, %add35.3
  %add39.3 = fadd float %add35.3, %add37.3
  %add41.3 = fadd float %add37.3, %add39.3
  %add43.3 = fadd float %add39.3, %add41.3
  %add45.3 = fadd float %add41.3, %add43.3
  %add47.3 = fadd float %add43.3, %add45.3
  %add49.3 = fadd float %add45.3, %add47.3

  %add35.4 = fadd float %add47.3, %add49.3
  %add37.4 = fadd float %add49.3, %add35.4
  %add39.4 = fadd float %add35.4, %add37.4
  %add41.4 = fadd float %add37.4, %add39.4
  %add43.4 = fadd float %add39.4, %add41.4
  %add45.4 = fadd float %add41.4, %add43.4
  %add47.4 = fadd float %add43.4, %add45.4
  %add49.4 = fadd float %add45.4, %add47.4

  %add35.5 = fadd float %add47.4, %add49.4
  %add37.5 = fadd float %add49.4, %add35.5
  %add39.5 = fadd float %add35.5, %add37.5
  %add41.5 = fadd float %add37.5, %add39.5
  %add43.5 = fadd float %add39.5, %add41.5
  %add45.5 = fadd float %add41.5, %add43.5
  %add47.5 = fadd float %add43.5, %add45.5
  %add49.5 = fadd float %add45.5, %add47.5

  %add35.6 = fadd float %add47.5, %add49.5
  %add37.6 = fadd float %add49.5, %add35.6
  %add39.6 = fadd float %add35.6, %add37.6
  %add41.6 = fadd float %add37.6, %add39.6
  %add43.6 = fadd float %add39.6, %add41.6
  %add45.6 = fadd float %add41.6, %add43.6
  %add47.6 = fadd float %add43.6, %add45.6
  %add49.6 = fadd float %add45.6, %add47.6

  %add35.7 = fadd float %add47.6, %add49.6
  %add37.7 = fadd float %add49.6, %add35.7
  %add39.7 = fadd float %add35.7, %add37.7
  %add41.7 = fadd float %add37.7, %add39.7
  %add43.7 = fadd float %add39.7, %add41.7
  %add45.7 = fadd float %add41.7, %add43.7
  %add47.7 = fadd float %add43.7, %add45.7
  %add49.7 = fadd float %add45.7, %add47.7

  %inc = add nuw nsw i32 %i, 1
  %cmp.loop = icmp slt i32 %inc, %itr
  br i1 %cmp.loop, label %loop, label %exit

exit:
  %result = phi float [ %val1, %entry ], [ %add49.7, %loop ]
  store float %result, ptr %out, align 4
  ret void
}