; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --version 4
; RUN: opt < %s -passes=tailcallelim -verify-dom-info -S | FileCheck %s

define i32 @test1_factorial(i32 %x) {
; CHECK-LABEL: define i32 @test1_factorial(
; CHECK-SAME: i32 [[X:%.*]]) {
; CHECK-NEXT:  entry:
; CHECK-NEXT:    br label [[TAILRECURSE:%.*]]
; CHECK:       tailrecurse:
; CHECK-NEXT:    [[ACCUMULATOR_TR:%.*]] = phi i32 [ 1, [[ENTRY:%.*]] ], [ [[ACCUMULATE:%.*]], [[THEN:%.*]] ]
; CHECK-NEXT:    [[X_TR:%.*]] = phi i32 [ [[X]], [[ENTRY]] ], [ [[TMP_6:%.*]], [[THEN]] ]
; CHECK-NEXT:    [[TMP_1:%.*]] = icmp sgt i32 [[X_TR]], 0
; CHECK-NEXT:    br i1 [[TMP_1]], label [[THEN]], label [[ELSE:%.*]]
; CHECK:       then:
; CHECK-NEXT:    [[TMP_6]] = add i32 [[X_TR]], -1
; CHECK-NEXT:    [[ACCUMULATE]] = mul i32 [[ACCUMULATOR_TR]], [[X_TR]]
; CHECK-NEXT:    br label [[TAILRECURSE]]
; CHECK:       else:
; CHECK-NEXT:    [[ACCUMULATOR_RET_TR:%.*]] = mul i32 [[ACCUMULATOR_TR]], 1
; CHECK-NEXT:    ret i32 [[ACCUMULATOR_RET_TR]]
;
entry:
  %tmp.1 = icmp sgt i32 %x, 0
  br i1 %tmp.1, label %then, label %else
then:
  %tmp.6 = add i32 %x, -1
  %recurse = call i32 @test1_factorial( i32 %tmp.6 )
  %accumulate = mul i32 %recurse, %x
  ret i32 %accumulate
else:
  ret i32 1
}

; This is a more aggressive form of accumulator recursion insertion, which
; requires noticing that X doesn't change as we perform the tailcall.

define i32 @test2_mul(i32 %x, i32 %y) {
; CHECK-LABEL: define i32 @test2_mul(
; CHECK-SAME: i32 [[X:%.*]], i32 [[Y:%.*]]) {
; CHECK-NEXT:  entry:
; CHECK-NEXT:    br label [[TAILRECURSE:%.*]]
; CHECK:       tailrecurse:
; CHECK-NEXT:    [[ACCUMULATOR_TR:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[ACCUMULATE:%.*]], [[ENDIF:%.*]] ]
; CHECK-NEXT:    [[Y_TR:%.*]] = phi i32 [ [[Y]], [[ENTRY]] ], [ [[TMP_8:%.*]], [[ENDIF]] ]
; CHECK-NEXT:    [[TMP_1:%.*]] = icmp eq i32 [[Y_TR]], 0
; CHECK-NEXT:    br i1 [[TMP_1]], label [[RETURN:%.*]], label [[ENDIF]]
; CHECK:       endif:
; CHECK-NEXT:    [[TMP_8]] = add i32 [[Y_TR]], -1
; CHECK-NEXT:    [[ACCUMULATE]] = add i32 [[ACCUMULATOR_TR]], [[X]]
; CHECK-NEXT:    br label [[TAILRECURSE]]
; CHECK:       return:
; CHECK-NEXT:    [[ACCUMULATOR_RET_TR:%.*]] = add i32 [[ACCUMULATOR_TR]], [[X]]
; CHECK-NEXT:    ret i32 [[ACCUMULATOR_RET_TR]]
;
entry:
  %tmp.1 = icmp eq i32 %y, 0
  br i1 %tmp.1, label %return, label %endif
endif:
  %tmp.8 = add i32 %y, -1
  %recurse = call i32 @test2_mul( i32 %x, i32 %tmp.8 )
  %accumulate = add i32 %recurse, %x
  ret i32 %accumulate
return:
  ret i32 %x
}

define i64 @test3_fib(i64 %n) nounwind readnone {
; CHECK-LABEL: define i64 @test3_fib(
; CHECK-SAME: i64 [[N:%.*]]) #[[ATTR0:[0-9]+]] {
; CHECK-NEXT:  entry:
; CHECK-NEXT:    br label [[TAILRECURSE:%.*]]
; CHECK:       tailrecurse:
; CHECK-NEXT:    [[ACCUMULATOR_TR:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[ACCUMULATE:%.*]], [[BB1:%.*]] ]
; CHECK-NEXT:    [[N_TR:%.*]] = phi i64 [ [[N]], [[ENTRY]] ], [ [[TMP1:%.*]], [[BB1]] ]
; CHECK-NEXT:    switch i64 [[N_TR]], label [[BB1]] [
; CHECK-NEXT:      i64 0, label [[BB2:%.*]]
; CHECK-NEXT:      i64 1, label [[BB2]]
; CHECK-NEXT:    ]
; CHECK:       bb1:
; CHECK-NEXT:    [[TMP0:%.*]] = add i64 [[N_TR]], -1
; CHECK-NEXT:    [[RECURSE1:%.*]] = tail call i64 @test3_fib(i64 [[TMP0]]) #[[ATTR2:[0-9]+]]
; CHECK-NEXT:    [[TMP1]] = add i64 [[N_TR]], -2
; CHECK-NEXT:    [[ACCUMULATE]] = add nsw i64 [[ACCUMULATOR_TR]], [[RECURSE1]]
; CHECK-NEXT:    br label [[TAILRECURSE]]
; CHECK:       bb2:
; CHECK-NEXT:    [[ACCUMULATOR_RET_TR:%.*]] = add nsw i64 [[ACCUMULATOR_TR]], [[N_TR]]
; CHECK-NEXT:    ret i64 [[ACCUMULATOR_RET_TR]]
;
entry:
  switch i64 %n, label %bb1 [
  i64 0, label %bb2
  i64 1, label %bb2
  ]

bb1:
  %0 = add i64 %n, -1
  %recurse1 = tail call i64 @test3_fib(i64 %0) nounwind
  %1 = add i64 %n, -2
  %recurse2 = tail call i64 @test3_fib(i64 %1) nounwind
  %accumulate = add nsw i64 %recurse2, %recurse1
  ret i64 %accumulate

bb2:
  ret i64 %n
}

define i32 @test4_base_case_call() local_unnamed_addr {
; CHECK-LABEL: define i32 @test4_base_case_call() local_unnamed_addr {
; CHECK-NEXT:  entry:
; CHECK-NEXT:    br label [[TAILRECURSE:%.*]]
; CHECK:       tailrecurse:
; CHECK-NEXT:    [[ACCUMULATOR_TR:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[ACCUMULATE:%.*]], [[SW_DEFAULT:%.*]] ]
; CHECK-NEXT:    [[BASE:%.*]] = tail call i32 @test4_helper()
; CHECK-NEXT:    switch i32 [[BASE]], label [[SW_DEFAULT]] [
; CHECK-NEXT:      i32 1, label [[CLEANUP:%.*]]
; CHECK-NEXT:      i32 5, label [[CLEANUP]]
; CHECK-NEXT:      i32 7, label [[CLEANUP]]
; CHECK-NEXT:    ]
; CHECK:       sw.default:
; CHECK-NEXT:    [[ACCUMULATE]] = add nsw i32 [[ACCUMULATOR_TR]], 1
; CHECK-NEXT:    br label [[TAILRECURSE]]
; CHECK:       cleanup:
; CHECK-NEXT:    [[ACCUMULATOR_RET_TR:%.*]] = add nsw i32 [[ACCUMULATOR_TR]], [[BASE]]
; CHECK-NEXT:    ret i32 [[ACCUMULATOR_RET_TR]]
;
entry:
  %base = call i32 @test4_helper()
  switch i32 %base, label %sw.default [
  i32 1, label %cleanup
  i32 5, label %cleanup
  i32 7, label %cleanup
  ]

sw.default:
  %recurse = call i32 @test4_base_case_call()
  %accumulate = add nsw i32 %recurse, 1
  br label %cleanup

cleanup:
  %retval.0 = phi i32 [ %accumulate, %sw.default ], [ %base, %entry ], [ %base, %entry ], [ %base, %entry ]
  ret i32 %retval.0
}

declare i32 @test4_helper()

define i32 @test5_base_case_load(ptr nocapture %A, i32 %n) local_unnamed_addr {
; CHECK-LABEL: define i32 @test5_base_case_load(
; CHECK-SAME: ptr nocapture [[A:%.*]], i32 [[N:%.*]]) local_unnamed_addr {
; CHECK-NEXT:  entry:
; CHECK-NEXT:    br label [[TAILRECURSE:%.*]]
; CHECK:       tailrecurse:
; CHECK-NEXT:    [[ACCUMULATOR_TR:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[ACCUMULATE:%.*]], [[IF_END:%.*]] ]
; CHECK-NEXT:    [[N_TR:%.*]] = phi i32 [ [[N]], [[ENTRY]] ], [ [[SUB:%.*]], [[IF_END]] ]
; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[N_TR]], 0
; CHECK-NEXT:    br i1 [[CMP]], label [[IF_THEN:%.*]], label [[IF_END]]
; CHECK:       if.then:
; CHECK-NEXT:    [[BASE:%.*]] = load i32, ptr [[A]], align 4
; CHECK-NEXT:    [[ACCUMULATOR_RET_TR:%.*]] = add i32 [[ACCUMULATOR_TR]], [[BASE]]
; CHECK-NEXT:    ret i32 [[ACCUMULATOR_RET_TR]]
; CHECK:       if.end:
; CHECK-NEXT:    [[IDXPROM:%.*]] = zext i32 [[N_TR]] to i64
; CHECK-NEXT:    [[ARRAYIDX1:%.*]] = getelementptr inbounds i32, ptr [[A]], i64 [[IDXPROM]]
; CHECK-NEXT:    [[LOAD:%.*]] = load i32, ptr [[ARRAYIDX1]], align 4
; CHECK-NEXT:    [[SUB]] = add i32 [[N_TR]], -1
; CHECK-NEXT:    [[ACCUMULATE]] = add i32 [[ACCUMULATOR_TR]], [[LOAD]]
; CHECK-NEXT:    br label [[TAILRECURSE]]
;
entry:
  %cmp = icmp eq i32 %n, 0
  br i1 %cmp, label %if.then, label %if.end

if.then:
  %base = load i32, ptr %A, align 4
  ret i32 %base

if.end:
  %idxprom = zext i32 %n to i64
  %arrayidx1 = getelementptr inbounds i32, ptr %A, i64 %idxprom
  %load = load i32, ptr %arrayidx1, align 4
  %sub = add i32 %n, -1
  %recurse = tail call i32 @test5_base_case_load(ptr %A, i32 %sub)
  %accumulate = add i32 %recurse, %load
  ret i32 %accumulate
}

define i32 @test6_multiple_returns(i32 %x, i32 %y) local_unnamed_addr {
; CHECK-LABEL: define i32 @test6_multiple_returns(
; CHECK-SAME: i32 [[X:%.*]], i32 [[Y:%.*]]) local_unnamed_addr {
; CHECK-NEXT:  entry:
; CHECK-NEXT:    br label [[TAILRECURSE:%.*]]
; CHECK:       tailrecurse:
; CHECK-NEXT:    [[ACCUMULATOR_TR:%.*]] = phi i32 [ [[ACCUMULATOR_TR]], [[CASE99:%.*]] ], [ 0, [[ENTRY:%.*]] ], [ [[ACCUMULATE:%.*]], [[DEFAULT:%.*]] ]
; CHECK-NEXT:    [[X_TR:%.*]] = phi i32 [ [[X]], [[ENTRY]] ], [ [[SUB1:%.*]], [[CASE99]] ], [ [[SUB2:%.*]], [[DEFAULT]] ]
; CHECK-NEXT:    [[RET_TR:%.*]] = phi i32 [ poison, [[ENTRY]] ], [ [[CURRENT_RET_TR:%.*]], [[CASE99]] ], [ [[RET_TR]], [[DEFAULT]] ]
; CHECK-NEXT:    [[RET_KNOWN_TR:%.*]] = phi i1 [ false, [[ENTRY]] ], [ true, [[CASE99]] ], [ [[RET_KNOWN_TR]], [[DEFAULT]] ]
; CHECK-NEXT:    switch i32 [[X_TR]], label [[DEFAULT]] [
; CHECK-NEXT:      i32 0, label [[CASE0:%.*]]
; CHECK-NEXT:      i32 99, label [[CASE99]]
; CHECK-NEXT:    ]
; CHECK:       case0:
; CHECK-NEXT:    [[HELPER:%.*]] = tail call i32 @test6_helper()
; CHECK-NEXT:    [[ACCUMULATOR_RET_TR2:%.*]] = add i32 [[ACCUMULATOR_TR]], [[HELPER]]
; CHECK-NEXT:    [[CURRENT_RET_TR1:%.*]] = select i1 [[RET_KNOWN_TR]], i32 [[RET_TR]], i32 [[ACCUMULATOR_RET_TR2]]
; CHECK-NEXT:    ret i32 [[CURRENT_RET_TR1]]
; CHECK:       case99:
; CHECK-NEXT:    [[SUB1]] = add i32 [[X_TR]], -1
; CHECK-NEXT:    [[ACCUMULATOR_RET_TR:%.*]] = add i32 [[ACCUMULATOR_TR]], 18
; CHECK-NEXT:    [[CURRENT_RET_TR]] = select i1 [[RET_KNOWN_TR]], i32 [[RET_TR]], i32 [[ACCUMULATOR_RET_TR]]
; CHECK-NEXT:    br label [[TAILRECURSE]]
; CHECK:       default:
; CHECK-NEXT:    [[SUB2]] = add i32 [[X_TR]], -1
; CHECK-NEXT:    [[ACCUMULATE]] = add i32 [[ACCUMULATOR_TR]], [[Y]]
; CHECK-NEXT:    br label [[TAILRECURSE]]
;
entry:
  switch i32 %x, label %default [
  i32 0, label %case0
  i32 99, label %case99
  ]

case0:
  %helper = call i32 @test6_helper()
  ret i32 %helper

case99:
  %sub1 = add i32 %x, -1
  %recurse1 = call i32 @test6_multiple_returns(i32 %sub1, i32 %y)
  ret i32 18

default:
  %sub2 = add i32 %x, -1
  %recurse2 = call i32 @test6_multiple_returns(i32 %sub2, i32 %y)
  %accumulate = add i32 %recurse2, %y
  ret i32 %accumulate
}

declare i32 @test6_helper()

; It is only safe to transform one accumulator per function, make sure we don't
; try to remove more.

define i32 @test7_multiple_accumulators(i32 %a) local_unnamed_addr {
; CHECK-LABEL: define i32 @test7_multiple_accumulators(
; CHECK-SAME: i32 [[A:%.*]]) local_unnamed_addr {
; CHECK-NEXT:  entry:
; CHECK-NEXT:    br label [[TAILRECURSE:%.*]]
; CHECK:       tailrecurse:
; CHECK-NEXT:    [[ACCUMULATOR_TR:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[ACCUMULATE1:%.*]], [[IF_THEN2:%.*]] ]
; CHECK-NEXT:    [[A_TR:%.*]] = phi i32 [ [[A]], [[ENTRY]] ], [ [[SUB:%.*]], [[IF_THEN2]] ]
; CHECK-NEXT:    [[TOBOOL:%.*]] = icmp eq i32 [[A_TR]], 0
; CHECK-NEXT:    br i1 [[TOBOOL]], label [[RETURN:%.*]], label [[IF_END:%.*]]
; CHECK:       if.end:
; CHECK-NEXT:    [[AND:%.*]] = and i32 [[A_TR]], 1
; CHECK-NEXT:    [[TOBOOL1:%.*]] = icmp eq i32 [[AND]], 0
; CHECK-NEXT:    [[SUB]] = add nsw i32 [[A_TR]], -1
; CHECK-NEXT:    br i1 [[TOBOOL1]], label [[IF_END3:%.*]], label [[IF_THEN2]]
; CHECK:       if.then2:
; CHECK-NEXT:    [[ACCUMULATE1]] = add nsw i32 [[ACCUMULATOR_TR]], 1
; CHECK-NEXT:    br label [[TAILRECURSE]]
; CHECK:       if.end3:
; CHECK-NEXT:    [[RECURSE2:%.*]] = tail call i32 @test7_multiple_accumulators(i32 [[SUB]])
; CHECK-NEXT:    [[ACCUMULATE2:%.*]] = mul nsw i32 [[RECURSE2]], 2
; CHECK-NEXT:    [[ACCUMULATOR_RET_TR:%.*]] = add nsw i32 [[ACCUMULATOR_TR]], [[ACCUMULATE2]]
; CHECK-NEXT:    ret i32 [[ACCUMULATOR_RET_TR]]
; CHECK:       return:
; CHECK-NEXT:    [[ACCUMULATOR_RET_TR1:%.*]] = add nsw i32 [[ACCUMULATOR_TR]], 0
; CHECK-NEXT:    ret i32 [[ACCUMULATOR_RET_TR1]]
;
entry:
  %tobool = icmp eq i32 %a, 0
  br i1 %tobool, label %return, label %if.end

if.end:
  %and = and i32 %a, 1
  %tobool1 = icmp eq i32 %and, 0
  %sub = add nsw i32 %a, -1
  br i1 %tobool1, label %if.end3, label %if.then2

if.then2:
  %recurse1 = tail call i32 @test7_multiple_accumulators(i32 %sub)
  %accumulate1 = add nsw i32 %recurse1, 1
  br label %return

if.end3:
  %recurse2 = tail call i32 @test7_multiple_accumulators(i32 %sub)
  %accumulate2 = mul nsw i32 %recurse2, 2
  br label %return

return:
  %retval.0 = phi i32 [ %accumulate1, %if.then2 ], [ %accumulate2, %if.end3 ], [ 0, %entry ]
  ret i32 %retval.0
}

%struct.ListNode = type { i32, ptr }

; We cannot TRE commutative, non-associative intrinsics
define i32 @test_non_associative_sadd_sat(ptr %a) local_unnamed_addr {
; CHECK-LABEL: define i32 @test_non_associative_sadd_sat(
; CHECK-SAME: ptr [[A:%.*]]) local_unnamed_addr {
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[TOBOOL_NOT:%.*]] = icmp eq ptr [[A]], null
; CHECK-NEXT:    br i1 [[TOBOOL_NOT]], label [[COMMON_RET6:%.*]], label [[IF_END:%.*]]
; CHECK:       common.ret6:
; CHECK-NEXT:    ret i32 -1
; CHECK:       if.end:
; CHECK-NEXT:    [[TMP0:%.*]] = load i32, ptr [[A]], align 4
; CHECK-NEXT:    [[NEXT:%.*]] = getelementptr inbounds [[STRUCT_LISTNODE:%.*]], ptr [[A]], i64 0, i32 1
; CHECK-NEXT:    [[TMP1:%.*]] = load ptr, ptr [[NEXT]], align 8
; CHECK-NEXT:    [[CALL:%.*]] = tail call i32 @test_non_associative_sadd_sat(ptr [[TMP1]])
; CHECK-NEXT:    [[DOTSROA_SPECULATED:%.*]] = tail call i32 @llvm.sadd.sat.i32(i32 [[TMP0]], i32 [[CALL]])
; CHECK-NEXT:    ret i32 [[DOTSROA_SPECULATED]]
;
entry:
  %tobool.not = icmp eq ptr %a, null
  br i1 %tobool.not, label %common.ret6, label %if.end

common.ret6:                                      ; preds = %entry, %if.end
  %common.ret6.op = phi i32 [ %.sroa.speculated, %if.end ], [ -1, %entry ]
  ret i32 %common.ret6.op

if.end:                                           ; preds = %entry
  %0 = load i32, ptr %a
  %next = getelementptr inbounds %struct.ListNode, ptr %a, i64 0, i32 1
  %1 = load ptr, ptr %next
  %call = tail call i32 @test_non_associative_sadd_sat(ptr %1)
  %.sroa.speculated = tail call i32 @llvm.sadd.sat.i32(i32 %0, i32 %call)
  br label %common.ret6
}

declare i32 @llvm.sadd.sat.i32(i32, i32)