llvm/test/Transforms/LoopFusion/cannot_fuse.ll

   1 ; RUN: opt -S -passes=loop-simplify,loop-fusion -debug-only=loop-fusion -disable-output < %s 2>&1 | FileCheck %s
   2 ; REQUIRES: asserts
   3
   4 @B = common global [1024 x i32] zeroinitializer, align 16
   5
   6 ; Check that the two candidates for fusion are placed into separate candidate
   7 ; sets because they are not control flow equivalent.
   8
   9 ; CHECK: Performing Loop Fusion on function non_cfe
  10 ; CHECK: Fusion Candidates:
  11 ; CHECK: *** Fusion Candidate Set ***
  12 ; CHECK: bb
  13 ; CHECK: ****************************
  14 ; CHECK: *** Fusion Candidate Set ***
  15 ; CHECK: bb20.preheader
  16 ; CHECK: ****************************
  17 ; CHECK: Loop Fusion complete
  18 define void @non_cfe(ptr noalias %arg, i32 %N) {
  19 bb:
  20   br label %bb7
  21
  22 bb7:                                              ; preds = %bb, %bb14
  23   %.014 = phi i32 [ 0, %bb ], [ %tmp15, %bb14 ]
  24   %indvars.iv23 = phi i64 [ 0, %bb ], [ %indvars.iv.next3, %bb14 ]
  25   %tmp = add nsw i32 %.014, -3
  26   %tmp8 = add nuw nsw i64 %indvars.iv23, 3
  27   %tmp9 = trunc i64 %tmp8 to i32
  28   %tmp10 = mul nsw i32 %tmp, %tmp9
  29   %tmp11 = trunc i64 %indvars.iv23 to i32
  30   %tmp12 = srem i32 %tmp10, %tmp11
  31   %tmp13 = getelementptr inbounds i32, ptr %arg, i64 %indvars.iv23
  32   store i32 %tmp12, ptr %tmp13, align 4
  33   br label %bb14
  34
  35 bb14:                                             ; preds = %bb7
  36   %indvars.iv.next3 = add nuw nsw i64 %indvars.iv23, 1
  37   %tmp15 = add nuw nsw i32 %.014, 1
  38   %exitcond4 = icmp ne i64 %indvars.iv.next3, 100
  39   br i1 %exitcond4, label %bb7, label %bb34
  40
  41 bb34:
  42   %cmp = icmp slt i32 %N, 50
  43   br i1 %cmp, label %bb16, label %bb33
  44
  45 bb16:                                             ; preds = %bb34
  46   %tmp17 = load i32, ptr %arg, align 4
  47   %tmp18 = icmp slt i32 %tmp17, 0
  48   br i1 %tmp18, label %bb20.preheader, label %bb33
  49
  50 bb20.preheader:                                   ; preds = %bb16
  51   br label %bb22
  52
  53 bb22:                                             ; preds = %bb20.preheader, %bb30
  54   %.02 = phi i32 [ 0, %bb20.preheader ], [ %tmp31, %bb30 ]
  55   %indvars.iv1 = phi i64 [ 0, %bb20.preheader ], [ %indvars.iv.next, %bb30 ]
  56   %tmp23 = add nsw i32 %.02, -3
  57   %tmp24 = add nuw nsw i64 %indvars.iv1, 3
  58   %tmp25 = trunc i64 %tmp24 to i32
  59   %tmp26 = mul nsw i32 %tmp23, %tmp25
  60   %tmp27 = trunc i64 %indvars.iv1 to i32
  61   %tmp28 = srem i32 %tmp26, %tmp27
  62   %tmp29 = getelementptr inbounds [1024 x i32], ptr @B, i64 0, i64 %indvars.iv1
  63   store i32 %tmp28, ptr %tmp29, align 4
  64   br label %bb30
  65
  66 bb30:                                             ; preds = %bb22
  67   %indvars.iv.next = add nuw nsw i64 %indvars.iv1, 1
  68   %tmp31 = add nuw nsw i32 %.02, 1
  69   %exitcond = icmp ne i64 %indvars.iv.next, 100
  70   br i1 %exitcond, label %bb22, label %bb33.loopexit
  71
  72 bb33.loopexit:                                    ; preds = %bb30
  73   br label %bb33
  74
  75 bb33:                                             ; preds = %bb33.loopexit, %bb16, %bb34
  76   ret void
  77 }
  78
  79 ; Check that fusion detects the two canddates are not adjacent (the exit block
  80 ; of the first candidate is not the preheader of the second candidate).
  81
  82 ; CHECK: Performing Loop Fusion on function non_adjacent
  83 ; CHECK: Fusion Candidates:
  84 ; CHECK: *** Fusion Candidate Set ***
  85 ; CHECK-NEXT: [[LOOP1PREHEADER:bb[0-9]*]]
  86 ; CHECK-NEXT: [[LOOP2PREHEADER:bb[0-9]*]]
  87 ; CHECK-NEXT: ****************************
  88 ; CHECK: Attempting fusion on Candidate Set:
  89 ; CHECK-NEXT: [[LOOP1PREHEADER]]
  90 ; CHECK-NEXT: [[LOOP2PREHEADER]]
  91 ; CHECK: Fusion candidates are not adjacent. Not fusing.
  92 ; CHECK: Loop Fusion complete
  93 define void @non_adjacent(ptr noalias %arg) {
  94 bb:
  95   br label %bb5
  96
  97 bb4:                                              ; preds = %bb11
  98   br label %bb13
  99
 100 bb5:                                              ; preds = %bb, %bb11
 101   %.013 = phi i64 [ 0, %bb ], [ %tmp12, %bb11 ]
 102   %tmp = add nsw i64 %.013, -3
 103   %tmp6 = add nuw nsw i64 %.013, 3
 104   %tmp7 = mul nsw i64 %tmp, %tmp6
 105   %tmp8 = srem i64 %tmp7, %.013
 106   %tmp9 = trunc i64 %tmp8 to i32
 107   %tmp10 = getelementptr inbounds i32, ptr %arg, i64 %.013
 108   store i32 %tmp9, ptr %tmp10, align 4
 109   br label %bb11
 110
 111 bb11:                                             ; preds = %bb5
 112   %tmp12 = add nuw nsw i64 %.013, 1
 113   %exitcond2 = icmp ne i64 %tmp12, 100
 114   br i1 %exitcond2, label %bb5, label %bb4
 115
 116 bb13:                                             ; preds = %bb4
 117   br label %bb16
 118
 119 bb15:                                             ; preds = %bb23
 120   br label %bb25
 121
 122 bb16:                                             ; preds = %bb13, %bb23
 123   %.02 = phi i64 [ 0, %bb13 ], [ %tmp24, %bb23 ]
 124   %tmp17 = add nsw i64 %.02, -3
 125   %tmp18 = add nuw nsw i64 %.02, 3
 126   %tmp19 = mul nsw i64 %tmp17, %tmp18
 127   %tmp20 = srem i64 %tmp19, %.02
 128   %tmp21 = trunc i64 %tmp20 to i32
 129   %tmp22 = getelementptr inbounds [1024 x i32], ptr @B, i64 0, i64 %.02
 130   store i32 %tmp21, ptr %tmp22, align 4
 131   br label %bb23
 132
 133 bb23:                                             ; preds = %bb16
 134   %tmp24 = add nuw nsw i64 %.02, 1
 135   %exitcond = icmp ne i64 %tmp24, 100
 136   br i1 %exitcond, label %bb16, label %bb15
 137
 138 bb25:                                             ; preds = %bb15
 139   ret void
 140 }
 141
 142 ; Check that the different bounds are detected and prevent fusion.
 143
 144 ; CHECK: Performing Loop Fusion on function different_bounds
 145 ; CHECK: Fusion Candidates:
 146 ; CHECK: *** Fusion Candidate Set ***
 147 ; CHECK-NEXT: [[LOOP1PREHEADER:bb[0-9]*]]
 148 ; CHECK-NEXT: [[LOOP2PREHEADER:bb[0-9]*]]
 149 ; CHECK-NEXT: ****************************
 150 ; CHECK: Attempting fusion on Candidate Set:
 151 ; CHECK-NEXT: [[LOOP1PREHEADER]]
 152 ; CHECK-NEXT: [[LOOP2PREHEADER]]
 153 ; CHECK: Fusion candidates do not have identical trip counts. Not fusing.
 154 ; CHECK: Loop Fusion complete
 155 define void @different_bounds(ptr noalias %arg) {
 156 bb:
 157   br label %bb5
 158
 159 bb4:                                              ; preds = %bb11
 160   br label %bb13
 161
 162 bb5:                                              ; preds = %bb, %bb11
 163   %.013 = phi i64 [ 0, %bb ], [ %tmp12, %bb11 ]
 164   %tmp = add nsw i64 %.013, -3
 165   %tmp6 = add nuw nsw i64 %.013, 3
 166   %tmp7 = mul nsw i64 %tmp, %tmp6
 167   %tmp8 = srem i64 %tmp7, %.013
 168   %tmp9 = trunc i64 %tmp8 to i32
 169   %tmp10 = getelementptr inbounds i32, ptr %arg, i64 %.013
 170   store i32 %tmp9, ptr %tmp10, align 4
 171   br label %bb11
 172
 173 bb11:                                             ; preds = %bb5
 174   %tmp12 = add nuw nsw i64 %.013, 1
 175   %exitcond2 = icmp ne i64 %tmp12, 100
 176   br i1 %exitcond2, label %bb5, label %bb4
 177
 178 bb13:                                             ; preds = %bb4
 179   br label %bb16
 180
 181 bb15:                                             ; preds = %bb23
 182   br label %bb25
 183
 184 bb16:                                             ; preds = %bb13, %bb23
 185   %.02 = phi i64 [ 0, %bb13 ], [ %tmp24, %bb23 ]
 186   %tmp17 = add nsw i64 %.02, -3
 187   %tmp18 = add nuw nsw i64 %.02, 3
 188   %tmp19 = mul nsw i64 %tmp17, %tmp18
 189   %tmp20 = srem i64 %tmp19, %.02
 190   %tmp21 = trunc i64 %tmp20 to i32
 191   %tmp22 = getelementptr inbounds [1024 x i32], ptr @B, i64 0, i64 %.02
 192   store i32 %tmp21, ptr %tmp22, align 4
 193   br label %bb23
 194
 195 bb23:                                             ; preds = %bb16
 196   %tmp24 = add nuw nsw i64 %.02, 1
 197   %exitcond = icmp ne i64 %tmp24, 200
 198   br i1 %exitcond, label %bb16, label %bb15
 199
 200 bb25:                                             ; preds = %bb15
 201   ret void
 202 }
 203
 204 ; Check that the negative dependence between the two candidates is identified
 205 ; and prevents fusion.
 206
 207 ; CHECK: Performing Loop Fusion on function negative_dependence
 208 ; CHECK: Fusion Candidates:
 209 ; CHECK: *** Fusion Candidate Set ***
 210 ; CHECK-NEXT: [[LOOP1PREHEADER:bb[0-9]*]]
 211 ; CHECK-NEXT: [[LOOP2PREHEADER:bb[0-9]*]]
 212 ; CHECK-NEXT: ****************************
 213 ; CHECK: Attempting fusion on Candidate Set:
 214 ; CHECK-NEXT: [[LOOP1PREHEADER]]
 215 ; CHECK-NEXT: [[LOOP2PREHEADER]]
 216 ; CHECK: Memory dependencies do not allow fusion!
 217 ; CHECK: Loop Fusion complete
 218 define void @negative_dependence(ptr noalias %arg) {
 219 bb:
 220   br label %bb7
 221
 222 bb11.preheader:                                   ; preds = %bb9
 223   br label %bb13
 224
 225 bb7:                                              ; preds = %bb, %bb9
 226   %indvars.iv22 = phi i64 [ 0, %bb ], [ %indvars.iv.next3, %bb9 ]
 227   %tmp = getelementptr inbounds i32, ptr %arg, i64 %indvars.iv22
 228   %tmp8 = trunc i64 %indvars.iv22 to i32
 229   store i32 %tmp8, ptr %tmp, align 4
 230   br label %bb9
 231
 232 bb9:                                              ; preds = %bb7
 233   %indvars.iv.next3 = add nuw nsw i64 %indvars.iv22, 1
 234   %exitcond4 = icmp ne i64 %indvars.iv.next3, 100
 235   br i1 %exitcond4, label %bb7, label %bb11.preheader
 236
 237 bb13:                                             ; preds = %bb11.preheader, %bb18
 238   %indvars.iv1 = phi i64 [ 0, %bb11.preheader ], [ %indvars.iv.next, %bb18 ]
 239   %indvars.iv.next = add nuw nsw i64 %indvars.iv1, 1
 240   %tmp14 = getelementptr inbounds i32, ptr %arg, i64 %indvars.iv.next
 241   %tmp15 = load i32, ptr %tmp14, align 4
 242   %tmp16 = shl nsw i32 %tmp15, 1
 243   %tmp17 = getelementptr inbounds [1024 x i32], ptr @B, i64 0, i64 %indvars.iv1
 244   store i32 %tmp16, ptr %tmp17, align 4
 245   br label %bb18
 246
 247 bb18:                                             ; preds = %bb13
 248   %exitcond = icmp ne i64 %indvars.iv.next, 100
 249   br i1 %exitcond, label %bb13, label %bb19
 250
 251 bb19:                                             ; preds = %bb18
 252   ret void
 253 }
 254
 255 ; Check for values defined in Loop 0 and used in Loop 1.
 256 ; It is not safe to fuse in this case, because the second loop has
 257 ; a use of %.01.lcssa which is defined in the body of loop 0. The
 258 ; first loop must execute completely in order to compute the correct
 259 ; value of %.01.lcssa to be used in the second loop.
 260
 261 ; CHECK: Performing Loop Fusion on function sumTest
 262 ; CHECK: Fusion Candidates:
 263 ; CHECK: *** Fusion Candidate Set ***
 264 ; CHECK-NEXT: [[LOOP1PREHEADER:bb[0-9]*]]
 265 ; CHECK-NEXT: [[LOOP2PREHEADER:bb[0-9]*]]
 266 ; CHECK-NEXT: ****************************
 267 ; CHECK: Attempting fusion on Candidate Set:
 268 ; CHECK-NEXT: [[LOOP1PREHEADER]]
 269 ; CHECK-NEXT: [[LOOP2PREHEADER]]
 270 ; CHECK: Memory dependencies do not allow fusion!
 271 ; CHECK: Loop Fusion complete
 272 define i32 @sumTest(ptr noalias %arg) {
 273 bb:
 274   br label %bb9
 275
 276 bb13.preheader:                                   ; preds = %bb9
 277   br label %bb15
 278
 279 bb9:                                              ; preds = %bb, %bb9
 280   %.01.lcssa = phi i32 [ 0, %bb ], [ %tmp11, %bb9 ]
 281   %.013 = phi i32 [ 0, %bb ], [ %tmp11, %bb9 ]
 282   %indvars.iv32 = phi i64 [ 0, %bb ], [ %indvars.iv.next4, %bb9 ]
 283   %tmp = getelementptr inbounds i32, ptr %arg, i64 %indvars.iv32
 284   %tmp10 = load i32, ptr %tmp, align 4
 285   %tmp11 = add nsw i32 %.013, %tmp10
 286   %indvars.iv.next4 = add nuw nsw i64 %indvars.iv32, 1
 287   %exitcond5 = icmp ne i64 %indvars.iv.next4, 100
 288   br i1 %exitcond5, label %bb9, label %bb13.preheader
 289
 290 bb14:                                             ; preds = %bb20
 291   br label %bb21
 292
 293 bb15:                                             ; preds = %bb13.preheader, %bb20
 294   %indvars.iv1 = phi i64 [ 0, %bb13.preheader ], [ %indvars.iv.next, %bb20 ]
 295   %tmp16 = getelementptr inbounds i32, ptr %arg, i64 %indvars.iv1
 296   %tmp17 = load i32, ptr %tmp16, align 4
 297   %tmp18 = sdiv i32 %tmp17, %.01.lcssa
 298   %tmp19 = getelementptr inbounds [1024 x i32], ptr @B, i64 0, i64 %indvars.iv1
 299   store i32 %tmp18, ptr %tmp19, align 4
 300   br label %bb20
 301
 302 bb20:                                             ; preds = %bb15
 303   %indvars.iv.next = add nuw nsw i64 %indvars.iv1, 1
 304   %exitcond = icmp ne i64 %indvars.iv.next, 100
 305   br i1 %exitcond, label %bb15, label %bb14
 306
 307 bb21:                                             ; preds = %bb14
 308   ret i32 %.01.lcssa
 309 }
 310
 311 ; Similar to sumTest above. The first loop computes %add and must
 312 ; complete before it is used in the second loop. Thus, these two loops
 313 ; also cannot be fused.
 314
 315 ; CHECK: Performing Loop Fusion on function test
 316 ; CHECK: Fusion Candidates:
 317 ; CHECK: *** Fusion Candidate Set ***
 318 ; CHECK-NEXT: [[LOOP1PREHEADER:for.body[0-9]*.preheader]]
 319 ; CHECK-NEXT: [[LOOP2PREHEADER:for.body[0-9]*.preheader]]
 320 ; CHECK-NEXT: ****************************
 321 ; CHECK: Attempting fusion on Candidate Set:
 322 ; CHECK-NEXT: [[LOOP1PREHEADER]]
 323 ; CHECK-NEXT: [[LOOP2PREHEADER]]
 324 ; CHECK: Memory dependencies do not allow fusion!
 325 ; CHECK: Loop Fusion complete
 326 define float @test(ptr nocapture %a, i32 %n) {
 327 entry:
 328   %conv = zext i32 %n to i64
 329   %cmp32 = icmp eq i32 %n, 0
 330   br i1 %cmp32, label %for.cond.cleanup7, label %for.body
 331
 332 for.body:                                         ; preds = %for.body, %entry
 333   %i.034 = phi i64 [ %inc, %for.body ], [ 0, %entry ]
 334   %sum1.033 = phi float [ %add, %for.body ], [ 0.000000e+00, %entry ]
 335   %idxprom = trunc i64 %i.034 to i32
 336   %arrayidx = getelementptr inbounds float, ptr %a, i32 %idxprom
 337   %0 = load float, ptr %arrayidx, align 4
 338   %add = fadd float %sum1.033, %0
 339   %inc = add nuw nsw i64 %i.034, 1
 340   %cmp = icmp ult i64 %inc, %conv
 341   br i1 %cmp, label %for.body, label %for.body8
 342
 343 for.body8:                                        ; preds = %for.body, %for.body8
 344   %i2.031 = phi i64 [ %inc14, %for.body8 ], [ 0, %for.body ]
 345   %idxprom9 = trunc i64 %i2.031 to i32
 346   %arrayidx10 = getelementptr inbounds float, ptr %a, i32 %idxprom9
 347   %1 = load float, ptr %arrayidx10, align 4
 348   %div = fdiv float %1, %add
 349   store float %div, ptr %arrayidx10, align 4
 350   %inc14 = add nuw nsw i64 %i2.031, 1
 351   %cmp5 = icmp ult i64 %inc14, %conv
 352   br i1 %cmp5, label %for.body8, label %for.cond.cleanup7
 353
 354 for.cond.cleanup7:                                ; preds = %for.body8, %entry
 355   %sum1.0.lcssa36 = phi float [ 0.000000e+00, %entry ], [ %add, %for.body8 ]
 356   ret float %sum1.0.lcssa36
 357 }
 358
 359 ; Check that non-rotated loops are not considered for fusion.
 360 ; CHECK: Performing Loop Fusion on function notRotated
 361 ; CHECK: Loop bb{{.*}} is not rotated!
 362 ; CHECK: Loop bb{{.*}} is not rotated!
 363 define void @notRotated(ptr noalias %arg) {
 364 bb:
 365   br label %bb5
 366
 367 bb5:                                              ; preds = %bb14, %bb
 368   %indvars.iv2 = phi i64 [ %indvars.iv.next3, %bb14 ], [ 0, %bb ]
 369   %.01 = phi i32 [ 0, %bb ], [ %tmp15, %bb14 ]
 370   %exitcond4 = icmp ne i64 %indvars.iv2, 100
 371   br i1 %exitcond4, label %bb7, label %bb17
 372
 373 bb7:                                              ; preds = %bb5
 374   %tmp = add nsw i32 %.01, -3
 375   %tmp8 = add nuw nsw i64 %indvars.iv2, 3
 376   %tmp9 = trunc i64 %tmp8 to i32
 377   %tmp10 = mul nsw i32 %tmp, %tmp9
 378   %tmp11 = trunc i64 %indvars.iv2 to i32
 379   %tmp12 = srem i32 %tmp10, %tmp11
 380   %tmp13 = getelementptr inbounds i32, ptr %arg, i64 %indvars.iv2
 381   store i32 %tmp12, ptr %tmp13, align 4
 382   br label %bb14
 383
 384 bb14:                                             ; preds = %bb7
 385   %indvars.iv.next3 = add nuw nsw i64 %indvars.iv2, 1
 386   %tmp15 = add nuw nsw i32 %.01, 1
 387   br label %bb5
 388
 389 bb17:                                             ; preds = %bb27, %bb5
 390   %indvars.iv = phi i64 [ %indvars.iv.next, %bb27 ], [ 0, %bb5 ]
 391   %.0 = phi i32 [ 0, %bb5 ], [ %tmp28, %bb27 ]
 392   %exitcond = icmp ne i64 %indvars.iv, 100
 393   br i1 %exitcond, label %bb19, label %bb18
 394
 395 bb18:                                             ; preds = %bb17
 396   br label %bb29
 397
 398 bb19:                                             ; preds = %bb17
 399   %tmp20 = add nsw i32 %.0, -3
 400   %tmp21 = add nuw nsw i64 %indvars.iv, 3
 401   %tmp22 = trunc i64 %tmp21 to i32
 402   %tmp23 = mul nsw i32 %tmp20, %tmp22
 403   %tmp24 = trunc i64 %indvars.iv to i32
 404   %tmp25 = srem i32 %tmp23, %tmp24
 405   %tmp26 = getelementptr inbounds [1024 x i32], ptr @B, i64 0, i64 %indvars.iv
 406   store i32 %tmp25, ptr %tmp26, align 4
 407   br label %bb27
 408
 409 bb27:                                             ; preds = %bb19
 410   %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
 411   %tmp28 = add nuw nsw i32 %.0, 1
 412   br label %bb17
 413
 414 bb29:                                             ; preds = %bb18
 415   ret void
 416 }