llvm/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
   7         br i1 %tmp.1, label %then, label %else
   8 then:
   9         %tmp.6 = add i32 %x, -1
  10         %recurse = call i32 @test1_factorial( i32 %tmp.6 )
  11         %accumulate = mul i32 %recurse, %x
  12         ret i32 %accumulate
  13 else:
  14         ret i32 1
  15 }
  16
  17 ; CHECK-LABEL: define i32 @test1_factorial(
  18 ; CHECK: tailrecurse:
  19 ; CHECK: %accumulator.tr = phi i32 [ 1, %entry ], [ %accumulate, %then ]
  20 ; CHECK: then:
  21 ; CHECK-NOT: %recurse
  22 ; CHECK: %accumulate = mul i32 %accumulator.tr, %x.tr
  23 ; CHECK: else:
  24 ; CHECK: %accumulator.ret.tr = mul i32 %accumulator.tr, 1
  25 ; CHECK: ret i32 %accumulator.ret.tr
  26
  27 ; This is a more aggressive form of accumulator recursion insertion, which
  28 ; requires noticing that X doesn't change as we perform the tailcall.
  29
  30 define i32 @test2_mul(i32 %x, i32 %y) {
  31 entry:
  32         %tmp.1 = icmp eq i32 %y, 0
  33         br i1 %tmp.1, label %return, label %endif
  34 endif:
  35         %tmp.8 = add i32 %y, -1
  36         %recurse = call i32 @test2_mul( i32 %x, i32 %tmp.8 )
  37         %accumulate = add i32 %recurse, %x
  38         ret i32 %accumulate
  39 return:
  40         ret i32 %x
  41 }
  42
  43 ; CHECK-LABEL: define i32 @test2_mul(
  44 ; CHECK: tailrecurse:
  45 ; CHECK: %accumulator.tr = phi i32 [ 0, %entry ], [ %accumulate, %endif ]
  46 ; CHECK: endif:
  47 ; CHECK-NOT: %recurse
  48 ; CHECK: %accumulate = add i32 %accumulator.tr, %x
  49 ; CHECK: return:
  50 ; CHECK: %accumulator.ret.tr = add i32 %accumulator.tr, %x
  51 ; CHECK: ret i32 %accumulator.ret.tr
  52
  53 define i64 @test3_fib(i64 %n) nounwind readnone {
  54 entry:
  55   switch i64 %n, label %bb1 [
  56     i64 0, label %bb2
  57     i64 1, label %bb2
  58   ]
  59
  60 bb1:
  61   %0 = add i64 %n, -1
  62   %recurse1 = tail call i64 @test3_fib(i64 %0) nounwind
  63   %1 = add i64 %n, -2
  64   %recurse2 = tail call i64 @test3_fib(i64 %1) nounwind
  65   %accumulate = add nsw i64 %recurse2, %recurse1
  66   ret i64 %accumulate
  67
  68 bb2:
  69   ret i64 %n
  70 }
  71
  72 ; CHECK-LABEL: define i64 @test3_fib(
  73 ; CHECK: tailrecurse:
  74 ; CHECK: %accumulator.tr = phi i64 [ 0, %entry ], [ %accumulate, %bb1 ]
  75 ; CHECK: bb1:
  76 ; CHECK-NOT: %recurse2
  77 ; CHECK: %accumulate = add nsw i64 %accumulator.tr, %recurse1
  78 ; CHECK: bb2:
  79 ; CHECK: %accumulator.ret.tr = add nsw i64 %accumulator.tr, %n.tr
  80 ; CHECK: ret i64 %accumulator.ret.tr
  81
  82 define i32 @test4_base_case_call() local_unnamed_addr {
  83 entry:
  84   %base = call i32 @test4_helper()
  85   switch i32 %base, label %sw.default [
  86     i32 1, label %cleanup
  87     i32 5, label %cleanup
  88     i32 7, label %cleanup
  89   ]
  90
  91 sw.default:
  92   %recurse = call i32 @test4_base_case_call()
  93   %accumulate = add nsw i32 %recurse, 1
  94   br label %cleanup
  95
  96 cleanup:
  97   %retval.0 = phi i32 [ %accumulate, %sw.default ], [ %base, %entry ], [ %base, %entry ], [ %base, %entry ]
  98   ret i32 %retval.0
  99 }
 100
 101 declare i32 @test4_helper()
 102
 103 ; CHECK-LABEL: define i32 @test4_base_case_call(
 104 ; CHECK: tailrecurse:
 105 ; CHECK: %accumulator.tr = phi i32 [ 0, %entry ], [ %accumulate, %sw.default ]
 106 ; CHECK: sw.default:
 107 ; CHECK-NOT: %recurse
 108 ; CHECK: %accumulate = add nsw i32 %accumulator.tr, 1
 109 ; CHECK: cleanup:
 110 ; CHECK: %accumulator.ret.tr = add nsw i32 %accumulator.tr, %base
 111 ; CHECK: ret i32 %accumulator.ret.tr
 112
 113 define i32 @test5_base_case_load(i32* nocapture %A, i32 %n) local_unnamed_addr {
 114 entry:
 115   %cmp = icmp eq i32 %n, 0
 116   br i1 %cmp, label %if.then, label %if.end
 117
 118 if.then:
 119   %base = load i32, i32* %A, align 4
 120   ret i32 %base
 121
 122 if.end:
 123   %idxprom = zext i32 %n to i64
 124   %arrayidx1 = getelementptr inbounds i32, i32* %A, i64 %idxprom
 125   %load = load i32, i32* %arrayidx1, align 4
 126   %sub = add i32 %n, -1
 127   %recurse = tail call i32 @test5_base_case_load(i32* %A, i32 %sub)
 128   %accumulate = add i32 %recurse, %load
 129   ret i32 %accumulate
 130 }
 131
 132 ; CHECK-LABEL: define i32 @test5_base_case_load(
 133 ; CHECK: tailrecurse:
 134 ; CHECK: %accumulator.tr = phi i32 [ 0, %entry ], [ %accumulate, %if.end ]
 135 ; CHECK: if.then:
 136 ; CHECK: %accumulator.ret.tr = add i32 %accumulator.tr, %base
 137 ; CHECK: ret i32 %accumulator.ret.tr
 138 ; CHECK: if.end:
 139 ; CHECK-NOT: %recurse
 140 ; CHECK: %accumulate = add i32 %accumulator.tr, %load
 141
 142 define i32 @test6_multiple_returns(i32 %x, i32 %y) local_unnamed_addr {
 143 entry:
 144   switch i32 %x, label %default [
 145     i32 0, label %case0
 146     i32 99, label %case99
 147   ]
 148
 149 case0:
 150   %helper = call i32 @test6_helper()
 151   ret i32 %helper
 152
 153 case99:
 154   %sub1 = add i32 %x, -1
 155   %recurse1 = call i32 @test6_multiple_returns(i32 %sub1, i32 %y)
 156   ret i32 18
 157
 158 default:
 159   %sub2 = add i32 %x, -1
 160   %recurse2 = call i32 @test6_multiple_returns(i32 %sub2, i32 %y)
 161   %accumulate = add i32 %recurse2, %y
 162   ret i32 %accumulate
 163 }
 164
 165 declare i32 @test6_helper()
 166
 167 ; CHECK-LABEL: define i32 @test6_multiple_returns(
 168 ; CHECK: tailrecurse:
 169 ; CHECK: %accumulator.tr = phi i32 [ %accumulator.tr, %case99 ], [ 0, %entry ], [ %accumulate, %default ]
 170 ; CHECK: %ret.tr = phi i32 [ undef, %entry ], [ %current.ret.tr, %case99 ], [ %ret.tr, %default ]
 171 ; CHECK: %ret.known.tr = phi i1 [ false, %entry ], [ true, %case99 ], [ %ret.known.tr, %default ]
 172 ; CHECK: case0:
 173 ; CHECK: %accumulator.ret.tr2 = add i32 %accumulator.tr, %helper
 174 ; CHECK: %current.ret.tr1 = select i1 %ret.known.tr, i32 %ret.tr, i32 %accumulator.ret.tr2
 175 ; CHECK: case99:
 176 ; CHECK-NOT: %recurse
 177 ; CHECK: %accumulator.ret.tr = add i32 %accumulator.tr, 18
 178 ; CHECK: %current.ret.tr = select i1 %ret.known.tr, i32 %ret.tr, i32 %accumulator.ret.tr
 179 ; CHECK: default:
 180 ; CHECK-NOT: %recurse
 181 ; CHECK: %accumulate = add i32 %accumulator.tr, %y
 182
 183 ; It is only safe to transform one accumulator per function, make sure we don't
 184 ; try to remove more.
 185
 186 define i32 @test7_multiple_accumulators(i32 %a) local_unnamed_addr {
 187 entry:
 188   %tobool = icmp eq i32 %a, 0
 189   br i1 %tobool, label %return, label %if.end
 190
 191 if.end:
 192   %and = and i32 %a, 1
 193   %tobool1 = icmp eq i32 %and, 0
 194   %sub = add nsw i32 %a, -1
 195   br i1 %tobool1, label %if.end3, label %if.then2
 196
 197 if.then2:
 198   %recurse1 = tail call i32 @test7_multiple_accumulators(i32 %sub)
 199   %accumulate1 = add nsw i32 %recurse1, 1
 200   br label %return
 201
 202 if.end3:
 203   %recurse2 = tail call i32 @test7_multiple_accumulators(i32 %sub)
 204   %accumulate2 = mul nsw i32 %recurse2, 2
 205   br label %return
 206
 207 return:
 208   %retval.0 = phi i32 [ %accumulate1, %if.then2 ], [ %accumulate2, %if.end3 ], [ 0, %entry ]
 209   ret i32 %retval.0
 210 }
 211
 212 ; CHECK-LABEL: define i32 @test7_multiple_accumulators(
 213 ; CHECK: tailrecurse:
 214 ; CHECK: %accumulator.tr = phi i32 [ 0, %entry ], [ %accumulate1, %if.then2 ]
 215 ; CHECK: if.then2:
 216 ; CHECK-NOT: %recurse1
 217 ; CHECK: %accumulate1 = add nsw i32 %accumulator.tr, 1
 218 ; CHECK: if.end3:
 219 ; CHECK: %recurse2
 220 ; CHECK: %accumulator.ret.tr = add nsw i32 %accumulator.tr, %accumulate2
 221 ; CHECK: ret i32 %accumulator.ret.tr
 222 ; CHECK: return:
 223 ; CHECK: %accumulator.ret.tr1 = add nsw i32 %accumulator.tr, 0
 224 ; CHECK: ret i32 %accumulator.ret.tr1