test/Transforms/LoopFusion/cannot_fuse.ll

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