test/Transforms/TailCallElim/accum_recursion.ll

   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: 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: 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: @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 }