1 ; RUN: opt < %s -tailcallelim -S | FileCheck %s 2 3 define i32 @test1_factorial(i32 %x) { 4 entry: 5 %tmp.1 = icmp sgt i32 %x, 0 ; <i1> [#uses=1] 6 br i1 %tmp.1, label %then, label %else 7 then: ; preds = %entry 8 %tmp.6 = add i32 %x, -1 ; <i32> [#uses=1] 9 %tmp.4 = call i32 @test1_factorial( i32 %tmp.6 ) ; <i32> [#uses=1] 10 %tmp.7 = mul i32 %tmp.4, %x ; <i32> [#uses=1] 11 ret i32 %tmp.7 12 else: ; preds = %entry 13 ret i32 1 14 } 15 16 ; CHECK-LABEL: define i32 @test1_factorial( 17 ; CHECK: phi i32 18 ; CHECK-NOT: call i32 19 ; CHECK: else: 20 21 ; This is a more aggressive form of accumulator recursion insertion, which 22 ; requires noticing that X doesn't change as we perform the tailcall. 23 24 define i32 @test2_mul(i32 %x, i32 %y) { 25 entry: 26 %tmp.1 = icmp eq i32 %y, 0 ; <i1> [#uses=1] 27 br i1 %tmp.1, label %return, label %endif 28 endif: ; preds = %entry 29 %tmp.8 = add i32 %y, -1 ; <i32> [#uses=1] 30 %tmp.5 = call i32 @test2_mul( i32 %x, i32 %tmp.8 ) ; <i32> [#uses=1] 31 %tmp.9 = add i32 %tmp.5, %x ; <i32> [#uses=1] 32 ret i32 %tmp.9 33 return: ; preds = %entry 34 ret i32 %x 35 } 36 37 ; CHECK-LABEL: define i32 @test2_mul( 38 ; CHECK: phi i32 39 ; CHECK-NOT: call i32 40 ; CHECK: return: 41 42 43 define i64 @test3_fib(i64 %n) nounwind readnone { 44 ; CHECK-LABEL: @test3_fib( 45 entry: 46 ; CHECK: tailrecurse: 47 ; CHECK: %accumulator.tr = phi i64 [ %n, %entry ], [ %3, %bb1 ] 48 ; CHECK: %n.tr = phi i64 [ %n, %entry ], [ %2, %bb1 ] 49 switch i64 %n, label %bb1 [ 50 ; CHECK: switch i64 %n.tr, label %bb1 [ 51 i64 0, label %bb2 52 i64 1, label %bb2 53 ] 54 55 bb1: 56 ; CHECK: bb1: 57 %0 = add i64 %n, -1 58 ; CHECK: %0 = add i64 %n.tr, -1 59 %1 = tail call i64 @test3_fib(i64 %0) nounwind 60 ; CHECK: %1 = tail call i64 @test3_fib(i64 %0) 61 %2 = add i64 %n, -2 62 ; CHECK: %2 = add i64 %n.tr, -2 63 %3 = tail call i64 @test3_fib(i64 %2) nounwind 64 ; CHECK-NOT: tail call i64 @test3_fib 65 %4 = add nsw i64 %3, %1 66 ; CHECK: add nsw i64 %accumulator.tr, %1 67 ret i64 %4 68 ; CHECK: br label %tailrecurse 69 70 bb2: 71 ; CHECK: bb2: 72 ret i64 %n 73 ; CHECK: ret i64 %accumulator.tr 74 } 75
