1; RUN: opt -S -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 18define void @non_cfe(i32* noalias %arg, i32 %N) { 19bb: 20 br label %bb7 21 22bb7: ; 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, i32* %arg, i64 %indvars.iv23 32 store i32 %tmp12, i32* %tmp13, align 4 33 br label %bb14 34 35bb14: ; 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 41bb34: 42 %cmp = icmp slt i32 %N, 50 43 br i1 %cmp, label %bb16, label %bb33 44 45bb16: ; preds = %bb34 46 %tmp17 = load i32, i32* %arg, align 4 47 %tmp18 = icmp slt i32 %tmp17, 0 48 br i1 %tmp18, label %bb20.preheader, label %bb33 49 50bb20.preheader: ; preds = %bb16 51 br label %bb22 52 53bb22: ; 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], [1024 x i32]* @B, i64 0, i64 %indvars.iv1 63 store i32 %tmp28, i32* %tmp29, align 4 64 br label %bb30 65 66bb30: ; 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 72bb33.loopexit: ; preds = %bb30 73 br label %bb33 74 75bb33: ; 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 93define void @non_adjacent(i32* noalias %arg) { 94bb: 95 br label %bb5 96 97bb4: ; preds = %bb11 98 br label %bb13 99 100bb5: ; 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, i32* %arg, i64 %.013 108 store i32 %tmp9, i32* %tmp10, align 4 109 br label %bb11 110 111bb11: ; 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 116bb13: ; preds = %bb4 117 br label %bb16 118 119bb15: ; preds = %bb23 120 br label %bb25 121 122bb16: ; 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], [1024 x i32]* @B, i64 0, i64 %.02 130 store i32 %tmp21, i32* %tmp22, align 4 131 br label %bb23 132 133bb23: ; 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 138bb25: ; 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 155define void @different_bounds(i32* noalias %arg) { 156bb: 157 br label %bb5 158 159bb4: ; preds = %bb11 160 br label %bb13 161 162bb5: ; 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, i32* %arg, i64 %.013 170 store i32 %tmp9, i32* %tmp10, align 4 171 br label %bb11 172 173bb11: ; 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 178bb13: ; preds = %bb4 179 br label %bb16 180 181bb15: ; preds = %bb23 182 br label %bb25 183 184bb16: ; 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], [1024 x i32]* @B, i64 0, i64 %.02 192 store i32 %tmp21, i32* %tmp22, align 4 193 br label %bb23 194 195bb23: ; 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 200bb25: ; 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 218define void @negative_dependence(i32* noalias %arg) { 219bb: 220 br label %bb7 221 222bb11.preheader: ; preds = %bb9 223 br label %bb13 224 225bb7: ; preds = %bb, %bb9 226 %indvars.iv22 = phi i64 [ 0, %bb ], [ %indvars.iv.next3, %bb9 ] 227 %tmp = getelementptr inbounds i32, i32* %arg, i64 %indvars.iv22 228 %tmp8 = trunc i64 %indvars.iv22 to i32 229 store i32 %tmp8, i32* %tmp, align 4 230 br label %bb9 231 232bb9: ; 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 237bb13: ; 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, i32* %arg, i64 %indvars.iv.next 241 %tmp15 = load i32, i32* %tmp14, align 4 242 %tmp16 = shl nsw i32 %tmp15, 1 243 %tmp17 = getelementptr inbounds [1024 x i32], [1024 x i32]* @B, i64 0, i64 %indvars.iv1 244 store i32 %tmp16, i32* %tmp17, align 4 245 br label %bb18 246 247bb18: ; preds = %bb13 248 %exitcond = icmp ne i64 %indvars.iv.next, 100 249 br i1 %exitcond, label %bb13, label %bb19 250 251bb19: ; 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 272define i32 @sumTest(i32* noalias %arg) { 273bb: 274 br label %bb9 275 276bb13.preheader: ; preds = %bb9 277 br label %bb15 278 279bb9: ; 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, i32* %arg, i64 %indvars.iv32 284 %tmp10 = load i32, i32* %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 290bb14: ; preds = %bb20 291 br label %bb21 292 293bb15: ; preds = %bb13.preheader, %bb20 294 %indvars.iv1 = phi i64 [ 0, %bb13.preheader ], [ %indvars.iv.next, %bb20 ] 295 %tmp16 = getelementptr inbounds i32, i32* %arg, i64 %indvars.iv1 296 %tmp17 = load i32, i32* %tmp16, align 4 297 %tmp18 = sdiv i32 %tmp17, %.01.lcssa 298 %tmp19 = getelementptr inbounds [1024 x i32], [1024 x i32]* @B, i64 0, i64 %indvars.iv1 299 store i32 %tmp18, i32* %tmp19, align 4 300 br label %bb20 301 302bb20: ; 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 307bb21: ; 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 326define float @test(float* nocapture %a, i32 %n) { 327entry: 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 332for.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, float* %a, i32 %idxprom 337 %0 = load float, float* %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 343for.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, float* %a, i32 %idxprom9 347 %1 = load float, float* %arrayidx10, align 4 348 %div = fdiv float %1, %add 349 store float %div, float* %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 354for.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! 363define void @notRotated(i32* noalias %arg) { 364bb: 365 br label %bb5 366 367bb5: ; 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 373bb7: ; 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, i32* %arg, i64 %indvars.iv2 381 store i32 %tmp12, i32* %tmp13, align 4 382 br label %bb14 383 384bb14: ; 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 389bb17: ; 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 395bb18: ; preds = %bb17 396 br label %bb29 397 398bb19: ; 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], [1024 x i32]* @B, i64 0, i64 %indvars.iv 406 store i32 %tmp25, i32* %tmp26, align 4 407 br label %bb27 408 409bb27: ; 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 414bb29: ; preds = %bb18 415 ret void 416} 417