llvm/test/Transforms/TailCallElim/accum_recursion.ll

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