test/Transforms/TailCallElim/accum_recursion.ll

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