llvm/test/Transforms/TailCallElim/accum_recursion.ll

   1 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --version 4
   2 ; RUN: opt < %s -passes=tailcallelim -verify-dom-info -S | FileCheck %s
   3
   4 define i32 @test1_factorial(i32 %x) {
   5 ; CHECK-LABEL: define i32 @test1_factorial(
   6 ; CHECK-SAME: i32 [[X:%.*]]) {
   7 ; CHECK-NEXT:  entry:
   8 ; CHECK-NEXT:    br label [[TAILRECURSE:%.*]]
   9 ; CHECK:       tailrecurse:
  10 ; CHECK-NEXT:    [[ACCUMULATOR_TR:%.*]] = phi i32 [ 1, [[ENTRY:%.*]] ], [ [[ACCUMULATE:%.*]], [[THEN:%.*]] ]
  11 ; CHECK-NEXT:    [[X_TR:%.*]] = phi i32 [ [[X]], [[ENTRY]] ], [ [[TMP_6:%.*]], [[THEN]] ]
  12 ; CHECK-NEXT:    [[TMP_1:%.*]] = icmp sgt i32 [[X_TR]], 0
  13 ; CHECK-NEXT:    br i1 [[TMP_1]], label [[THEN]], label [[ELSE:%.*]]
  14 ; CHECK:       then:
  15 ; CHECK-NEXT:    [[TMP_6]] = add i32 [[X_TR]], -1
  16 ; CHECK-NEXT:    [[ACCUMULATE]] = mul i32 [[ACCUMULATOR_TR]], [[X_TR]]
  17 ; CHECK-NEXT:    br label [[TAILRECURSE]]
  18 ; CHECK:       else:
  19 ; CHECK-NEXT:    [[ACCUMULATOR_RET_TR:%.*]] = mul i32 [[ACCUMULATOR_TR]], 1
  20 ; CHECK-NEXT:    ret i32 [[ACCUMULATOR_RET_TR]]
  21 ;
  22 entry:
  23   %tmp.1 = icmp sgt i32 %x, 0
  24   br i1 %tmp.1, label %then, label %else
  25 then:
  26   %tmp.6 = add i32 %x, -1
  27   %recurse = call i32 @test1_factorial( i32 %tmp.6 )
  28   %accumulate = mul i32 %recurse, %x
  29   ret i32 %accumulate
  30 else:
  31   ret i32 1
  32 }
  33
  34 ; This is a more aggressive form of accumulator recursion insertion, which
  35 ; requires noticing that X doesn't change as we perform the tailcall.
  36
  37 define i32 @test2_mul(i32 %x, i32 %y) {
  38 ; CHECK-LABEL: define i32 @test2_mul(
  39 ; CHECK-SAME: i32 [[X:%.*]], i32 [[Y:%.*]]) {
  40 ; CHECK-NEXT:  entry:
  41 ; CHECK-NEXT:    br label [[TAILRECURSE:%.*]]
  42 ; CHECK:       tailrecurse:
  43 ; CHECK-NEXT:    [[ACCUMULATOR_TR:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[ACCUMULATE:%.*]], [[ENDIF:%.*]] ]
  44 ; CHECK-NEXT:    [[Y_TR:%.*]] = phi i32 [ [[Y]], [[ENTRY]] ], [ [[TMP_8:%.*]], [[ENDIF]] ]
  45 ; CHECK-NEXT:    [[TMP_1:%.*]] = icmp eq i32 [[Y_TR]], 0
  46 ; CHECK-NEXT:    br i1 [[TMP_1]], label [[RETURN:%.*]], label [[ENDIF]]
  47 ; CHECK:       endif:
  48 ; CHECK-NEXT:    [[TMP_8]] = add i32 [[Y_TR]], -1
  49 ; CHECK-NEXT:    [[ACCUMULATE]] = add i32 [[ACCUMULATOR_TR]], [[X]]
  50 ; CHECK-NEXT:    br label [[TAILRECURSE]]
  51 ; CHECK:       return:
  52 ; CHECK-NEXT:    [[ACCUMULATOR_RET_TR:%.*]] = add i32 [[ACCUMULATOR_TR]], [[X]]
  53 ; CHECK-NEXT:    ret i32 [[ACCUMULATOR_RET_TR]]
  54 ;
  55 entry:
  56   %tmp.1 = icmp eq i32 %y, 0
  57   br i1 %tmp.1, label %return, label %endif
  58 endif:
  59   %tmp.8 = add i32 %y, -1
  60   %recurse = call i32 @test2_mul( i32 %x, i32 %tmp.8 )
  61   %accumulate = add i32 %recurse, %x
  62   ret i32 %accumulate
  63 return:
  64   ret i32 %x
  65 }
  66
  67 define i64 @test3_fib(i64 %n) nounwind readnone {
  68 ; CHECK-LABEL: define i64 @test3_fib(
  69 ; CHECK-SAME: i64 [[N:%.*]]) #[[ATTR0:[0-9]+]] {
  70 ; CHECK-NEXT:  entry:
  71 ; CHECK-NEXT:    br label [[TAILRECURSE:%.*]]
  72 ; CHECK:       tailrecurse:
  73 ; CHECK-NEXT:    [[ACCUMULATOR_TR:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[ACCUMULATE:%.*]], [[BB1:%.*]] ]
  74 ; CHECK-NEXT:    [[N_TR:%.*]] = phi i64 [ [[N]], [[ENTRY]] ], [ [[TMP1:%.*]], [[BB1]] ]
  75 ; CHECK-NEXT:    switch i64 [[N_TR]], label [[BB1]] [
  76 ; CHECK-NEXT:      i64 0, label [[BB2:%.*]]
  77 ; CHECK-NEXT:      i64 1, label [[BB2]]
  78 ; CHECK-NEXT:    ]
  79 ; CHECK:       bb1:
  80 ; CHECK-NEXT:    [[TMP0:%.*]] = add i64 [[N_TR]], -1
  81 ; CHECK-NEXT:    [[RECURSE1:%.*]] = tail call i64 @test3_fib(i64 [[TMP0]]) #[[ATTR2:[0-9]+]]
  82 ; CHECK-NEXT:    [[TMP1]] = add i64 [[N_TR]], -2
  83 ; CHECK-NEXT:    [[ACCUMULATE]] = add nsw i64 [[ACCUMULATOR_TR]], [[RECURSE1]]
  84 ; CHECK-NEXT:    br label [[TAILRECURSE]]
  85 ; CHECK:       bb2:
  86 ; CHECK-NEXT:    [[ACCUMULATOR_RET_TR:%.*]] = add nsw i64 [[ACCUMULATOR_TR]], [[N_TR]]
  87 ; CHECK-NEXT:    ret i64 [[ACCUMULATOR_RET_TR]]
  88 ;
  89 entry:
  90   switch i64 %n, label %bb1 [
  91   i64 0, label %bb2
  92   i64 1, label %bb2
  93   ]
  94
  95 bb1:
  96   %0 = add i64 %n, -1
  97   %recurse1 = tail call i64 @test3_fib(i64 %0) nounwind
  98   %1 = add i64 %n, -2
  99   %recurse2 = tail call i64 @test3_fib(i64 %1) nounwind
 100   %accumulate = add nsw i64 %recurse2, %recurse1
 101   ret i64 %accumulate
 102
 103 bb2:
 104   ret i64 %n
 105 }
 106
 107 define i32 @test4_base_case_call() local_unnamed_addr {
 108 ; CHECK-LABEL: define i32 @test4_base_case_call() local_unnamed_addr {
 109 ; CHECK-NEXT:  entry:
 110 ; CHECK-NEXT:    br label [[TAILRECURSE:%.*]]
 111 ; CHECK:       tailrecurse:
 112 ; CHECK-NEXT:    [[ACCUMULATOR_TR:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[ACCUMULATE:%.*]], [[SW_DEFAULT:%.*]] ]
 113 ; CHECK-NEXT:    [[BASE:%.*]] = tail call i32 @test4_helper()
 114 ; CHECK-NEXT:    switch i32 [[BASE]], label [[SW_DEFAULT]] [
 115 ; CHECK-NEXT:      i32 1, label [[CLEANUP:%.*]]
 116 ; CHECK-NEXT:      i32 5, label [[CLEANUP]]
 117 ; CHECK-NEXT:      i32 7, label [[CLEANUP]]
 118 ; CHECK-NEXT:    ]
 119 ; CHECK:       sw.default:
 120 ; CHECK-NEXT:    [[ACCUMULATE]] = add nsw i32 [[ACCUMULATOR_TR]], 1
 121 ; CHECK-NEXT:    br label [[TAILRECURSE]]
 122 ; CHECK:       cleanup:
 123 ; CHECK-NEXT:    [[ACCUMULATOR_RET_TR:%.*]] = add nsw i32 [[ACCUMULATOR_TR]], [[BASE]]
 124 ; CHECK-NEXT:    ret i32 [[ACCUMULATOR_RET_TR]]
 125 ;
 126 entry:
 127   %base = call i32 @test4_helper()
 128   switch i32 %base, label %sw.default [
 129   i32 1, label %cleanup
 130   i32 5, label %cleanup
 131   i32 7, label %cleanup
 132   ]
 133
 134 sw.default:
 135   %recurse = call i32 @test4_base_case_call()
 136   %accumulate = add nsw i32 %recurse, 1
 137   br label %cleanup
 138
 139 cleanup:
 140   %retval.0 = phi i32 [ %accumulate, %sw.default ], [ %base, %entry ], [ %base, %entry ], [ %base, %entry ]
 141   ret i32 %retval.0
 142 }
 143
 144 declare i32 @test4_helper()
 145
 146 define i32 @test5_base_case_load(ptr nocapture %A, i32 %n) local_unnamed_addr {
 147 ; CHECK-LABEL: define i32 @test5_base_case_load(
 148 ; CHECK-SAME: ptr nocapture [[A:%.*]], i32 [[N:%.*]]) local_unnamed_addr {
 149 ; CHECK-NEXT:  entry:
 150 ; CHECK-NEXT:    br label [[TAILRECURSE:%.*]]
 151 ; CHECK:       tailrecurse:
 152 ; CHECK-NEXT:    [[ACCUMULATOR_TR:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[ACCUMULATE:%.*]], [[IF_END:%.*]] ]
 153 ; CHECK-NEXT:    [[N_TR:%.*]] = phi i32 [ [[N]], [[ENTRY]] ], [ [[SUB:%.*]], [[IF_END]] ]
 154 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[N_TR]], 0
 155 ; CHECK-NEXT:    br i1 [[CMP]], label [[IF_THEN:%.*]], label [[IF_END]]
 156 ; CHECK:       if.then:
 157 ; CHECK-NEXT:    [[BASE:%.*]] = load i32, ptr [[A]], align 4
 158 ; CHECK-NEXT:    [[ACCUMULATOR_RET_TR:%.*]] = add i32 [[ACCUMULATOR_TR]], [[BASE]]
 159 ; CHECK-NEXT:    ret i32 [[ACCUMULATOR_RET_TR]]
 160 ; CHECK:       if.end:
 161 ; CHECK-NEXT:    [[IDXPROM:%.*]] = zext i32 [[N_TR]] to i64
 162 ; CHECK-NEXT:    [[ARRAYIDX1:%.*]] = getelementptr inbounds i32, ptr [[A]], i64 [[IDXPROM]]
 163 ; CHECK-NEXT:    [[LOAD:%.*]] = load i32, ptr [[ARRAYIDX1]], align 4
 164 ; CHECK-NEXT:    [[SUB]] = add i32 [[N_TR]], -1
 165 ; CHECK-NEXT:    [[ACCUMULATE]] = add i32 [[ACCUMULATOR_TR]], [[LOAD]]
 166 ; CHECK-NEXT:    br label [[TAILRECURSE]]
 167 ;
 168 entry:
 169   %cmp = icmp eq i32 %n, 0
 170   br i1 %cmp, label %if.then, label %if.end
 171
 172 if.then:
 173   %base = load i32, ptr %A, align 4
 174   ret i32 %base
 175
 176 if.end:
 177   %idxprom = zext i32 %n to i64
 178   %arrayidx1 = getelementptr inbounds i32, ptr %A, i64 %idxprom
 179   %load = load i32, ptr %arrayidx1, align 4
 180   %sub = add i32 %n, -1
 181   %recurse = tail call i32 @test5_base_case_load(ptr %A, i32 %sub)
 182   %accumulate = add i32 %recurse, %load
 183   ret i32 %accumulate
 184 }
 185
 186 define i32 @test6_multiple_returns(i32 %x, i32 %y) local_unnamed_addr {
 187 ; CHECK-LABEL: define i32 @test6_multiple_returns(
 188 ; CHECK-SAME: i32 [[X:%.*]], i32 [[Y:%.*]]) local_unnamed_addr {
 189 ; CHECK-NEXT:  entry:
 190 ; CHECK-NEXT:    br label [[TAILRECURSE:%.*]]
 191 ; CHECK:       tailrecurse:
 192 ; CHECK-NEXT:    [[ACCUMULATOR_TR:%.*]] = phi i32 [ [[ACCUMULATOR_TR]], [[CASE99:%.*]] ], [ 0, [[ENTRY:%.*]] ], [ [[ACCUMULATE:%.*]], [[DEFAULT:%.*]] ]
 193 ; CHECK-NEXT:    [[X_TR:%.*]] = phi i32 [ [[X]], [[ENTRY]] ], [ [[SUB1:%.*]], [[CASE99]] ], [ [[SUB2:%.*]], [[DEFAULT]] ]
 194 ; CHECK-NEXT:    [[RET_TR:%.*]] = phi i32 [ poison, [[ENTRY]] ], [ [[CURRENT_RET_TR:%.*]], [[CASE99]] ], [ [[RET_TR]], [[DEFAULT]] ]
 195 ; CHECK-NEXT:    [[RET_KNOWN_TR:%.*]] = phi i1 [ false, [[ENTRY]] ], [ true, [[CASE99]] ], [ [[RET_KNOWN_TR]], [[DEFAULT]] ]
 196 ; CHECK-NEXT:    switch i32 [[X_TR]], label [[DEFAULT]] [
 197 ; CHECK-NEXT:      i32 0, label [[CASE0:%.*]]
 198 ; CHECK-NEXT:      i32 99, label [[CASE99]]
 199 ; CHECK-NEXT:    ]
 200 ; CHECK:       case0:
 201 ; CHECK-NEXT:    [[HELPER:%.*]] = tail call i32 @test6_helper()
 202 ; CHECK-NEXT:    [[ACCUMULATOR_RET_TR2:%.*]] = add i32 [[ACCUMULATOR_TR]], [[HELPER]]
 203 ; CHECK-NEXT:    [[CURRENT_RET_TR1:%.*]] = select i1 [[RET_KNOWN_TR]], i32 [[RET_TR]], i32 [[ACCUMULATOR_RET_TR2]]
 204 ; CHECK-NEXT:    ret i32 [[CURRENT_RET_TR1]]
 205 ; CHECK:       case99:
 206 ; CHECK-NEXT:    [[SUB1]] = add i32 [[X_TR]], -1
 207 ; CHECK-NEXT:    [[ACCUMULATOR_RET_TR:%.*]] = add i32 [[ACCUMULATOR_TR]], 18
 208 ; CHECK-NEXT:    [[CURRENT_RET_TR]] = select i1 [[RET_KNOWN_TR]], i32 [[RET_TR]], i32 [[ACCUMULATOR_RET_TR]]
 209 ; CHECK-NEXT:    br label [[TAILRECURSE]]
 210 ; CHECK:       default:
 211 ; CHECK-NEXT:    [[SUB2]] = add i32 [[X_TR]], -1
 212 ; CHECK-NEXT:    [[ACCUMULATE]] = add i32 [[ACCUMULATOR_TR]], [[Y]]
 213 ; CHECK-NEXT:    br label [[TAILRECURSE]]
 214 ;
 215 entry:
 216   switch i32 %x, label %default [
 217   i32 0, label %case0
 218   i32 99, label %case99
 219   ]
 220
 221 case0:
 222   %helper = call i32 @test6_helper()
 223   ret i32 %helper
 224
 225 case99:
 226   %sub1 = add i32 %x, -1
 227   %recurse1 = call i32 @test6_multiple_returns(i32 %sub1, i32 %y)
 228   ret i32 18
 229
 230 default:
 231   %sub2 = add i32 %x, -1
 232   %recurse2 = call i32 @test6_multiple_returns(i32 %sub2, i32 %y)
 233   %accumulate = add i32 %recurse2, %y
 234   ret i32 %accumulate
 235 }
 236
 237 declare i32 @test6_helper()
 238
 239 ; It is only safe to transform one accumulator per function, make sure we don't
 240 ; try to remove more.
 241
 242 define i32 @test7_multiple_accumulators(i32 %a) local_unnamed_addr {
 243 ; CHECK-LABEL: define i32 @test7_multiple_accumulators(
 244 ; CHECK-SAME: i32 [[A:%.*]]) local_unnamed_addr {
 245 ; CHECK-NEXT:  entry:
 246 ; CHECK-NEXT:    br label [[TAILRECURSE:%.*]]
 247 ; CHECK:       tailrecurse:
 248 ; CHECK-NEXT:    [[ACCUMULATOR_TR:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[ACCUMULATE1:%.*]], [[IF_THEN2:%.*]] ]
 249 ; CHECK-NEXT:    [[A_TR:%.*]] = phi i32 [ [[A]], [[ENTRY]] ], [ [[SUB:%.*]], [[IF_THEN2]] ]
 250 ; CHECK-NEXT:    [[TOBOOL:%.*]] = icmp eq i32 [[A_TR]], 0
 251 ; CHECK-NEXT:    br i1 [[TOBOOL]], label [[RETURN:%.*]], label [[IF_END:%.*]]
 252 ; CHECK:       if.end:
 253 ; CHECK-NEXT:    [[AND:%.*]] = and i32 [[A_TR]], 1
 254 ; CHECK-NEXT:    [[TOBOOL1:%.*]] = icmp eq i32 [[AND]], 0
 255 ; CHECK-NEXT:    [[SUB]] = add nsw i32 [[A_TR]], -1
 256 ; CHECK-NEXT:    br i1 [[TOBOOL1]], label [[IF_END3:%.*]], label [[IF_THEN2]]
 257 ; CHECK:       if.then2:
 258 ; CHECK-NEXT:    [[ACCUMULATE1]] = add nsw i32 [[ACCUMULATOR_TR]], 1
 259 ; CHECK-NEXT:    br label [[TAILRECURSE]]
 260 ; CHECK:       if.end3:
 261 ; CHECK-NEXT:    [[RECURSE2:%.*]] = tail call i32 @test7_multiple_accumulators(i32 [[SUB]])
 262 ; CHECK-NEXT:    [[ACCUMULATE2:%.*]] = mul nsw i32 [[RECURSE2]], 2
 263 ; CHECK-NEXT:    [[ACCUMULATOR_RET_TR:%.*]] = add nsw i32 [[ACCUMULATOR_TR]], [[ACCUMULATE2]]
 264 ; CHECK-NEXT:    ret i32 [[ACCUMULATOR_RET_TR]]
 265 ; CHECK:       return:
 266 ; CHECK-NEXT:    [[ACCUMULATOR_RET_TR1:%.*]] = add nsw i32 [[ACCUMULATOR_TR]], 0
 267 ; CHECK-NEXT:    ret i32 [[ACCUMULATOR_RET_TR1]]
 268 ;
 269 entry:
 270   %tobool = icmp eq i32 %a, 0
 271   br i1 %tobool, label %return, label %if.end
 272
 273 if.end:
 274   %and = and i32 %a, 1
 275   %tobool1 = icmp eq i32 %and, 0
 276   %sub = add nsw i32 %a, -1
 277   br i1 %tobool1, label %if.end3, label %if.then2
 278
 279 if.then2:
 280   %recurse1 = tail call i32 @test7_multiple_accumulators(i32 %sub)
 281   %accumulate1 = add nsw i32 %recurse1, 1
 282   br label %return
 283
 284 if.end3:
 285   %recurse2 = tail call i32 @test7_multiple_accumulators(i32 %sub)
 286   %accumulate2 = mul nsw i32 %recurse2, 2
 287   br label %return
 288
 289 return:
 290   %retval.0 = phi i32 [ %accumulate1, %if.then2 ], [ %accumulate2, %if.end3 ], [ 0, %entry ]
 291   ret i32 %retval.0
 292 }
 293
 294 %struct.ListNode = type { i32, ptr }
 295
 296 ; We cannot TRE commutative, non-associative intrinsics
 297 define i32 @test_non_associative_sadd_sat(ptr %a) local_unnamed_addr {
 298 ; CHECK-LABEL: define i32 @test_non_associative_sadd_sat(
 299 ; CHECK-SAME: ptr [[A:%.*]]) local_unnamed_addr {
 300 ; CHECK-NEXT:  entry:
 301 ; CHECK-NEXT:    [[TOBOOL_NOT:%.*]] = icmp eq ptr [[A]], null
 302 ; CHECK-NEXT:    br i1 [[TOBOOL_NOT]], label [[COMMON_RET6:%.*]], label [[IF_END:%.*]]
 303 ; CHECK:       common.ret6:
 304 ; CHECK-NEXT:    ret i32 -1
 305 ; CHECK:       if.end:
 306 ; CHECK-NEXT:    [[TMP0:%.*]] = load i32, ptr [[A]], align 4
 307 ; CHECK-NEXT:    [[NEXT:%.*]] = getelementptr inbounds [[STRUCT_LISTNODE:%.*]], ptr [[A]], i64 0, i32 1
 308 ; CHECK-NEXT:    [[TMP1:%.*]] = load ptr, ptr [[NEXT]], align 8
 309 ; CHECK-NEXT:    [[CALL:%.*]] = tail call i32 @test_non_associative_sadd_sat(ptr [[TMP1]])
 310 ; CHECK-NEXT:    [[DOTSROA_SPECULATED:%.*]] = tail call i32 @llvm.sadd.sat.i32(i32 [[TMP0]], i32 [[CALL]])
 311 ; CHECK-NEXT:    ret i32 [[DOTSROA_SPECULATED]]
 312 ;
 313 entry:
 314   %tobool.not = icmp eq ptr %a, null
 315   br i1 %tobool.not, label %common.ret6, label %if.end
 316
 317 common.ret6:                                      ; preds = %entry, %if.end
 318   %common.ret6.op = phi i32 [ %.sroa.speculated, %if.end ], [ -1, %entry ]
 319   ret i32 %common.ret6.op
 320
 321 if.end:                                           ; preds = %entry
 322   %0 = load i32, ptr %a
 323   %next = getelementptr inbounds %struct.ListNode, ptr %a, i64 0, i32 1
 324   %1 = load ptr, ptr %next
 325   %call = tail call i32 @test_non_associative_sadd_sat(ptr %1)
 326   %.sroa.speculated = tail call i32 @llvm.sadd.sat.i32(i32 %0, i32 %call)
 327   br label %common.ret6
 328 }
 329
 330 declare i32 @llvm.sadd.sat.i32(i32, i32)