1; RUN: opt < %s -tailcallelim -S | FileCheck %s 2 3define i32 @test1_factorial(i32 %x) { 4entry: 5 %tmp.1 = icmp sgt i32 %x, 0 ; <i1> [#uses=1] 6 br i1 %tmp.1, label %then, label %else 7then: ; 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 12else: ; 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 24define i32 @test2_mul(i32 %x, i32 %y) { 25entry: 26 %tmp.1 = icmp eq i32 %y, 0 ; <i1> [#uses=1] 27 br i1 %tmp.1, label %return, label %endif 28endif: ; 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 33return: ; 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 43define i64 @test3_fib(i64 %n) nounwind readnone { 44; CHECK-LABEL: @test3_fib( 45entry: 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 55bb1: 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 70bb2: 71; CHECK: bb2: 72 ret i64 %n 73; CHECK: ret i64 %accumulator.tr 74} 75