| ; RUN: opt -S -passes=loop-simplify,loop-fusion -debug-only=loop-fusion -disable-output < %s 2>&1 | FileCheck %s |
| ; REQUIRES: asserts |
| |
| @B = common global [1024 x i32] zeroinitializer, align 16 |
| |
| ; Check that the two candidates for fusion are placed into separate candidate |
| ; sets because they are not control flow equivalent. |
| |
| ; CHECK: Performing Loop Fusion on function non_cfe |
| ; CHECK: Fusion Candidates: |
| ; CHECK: *** Fusion Candidate Set *** |
| ; CHECK: bb |
| ; CHECK: **************************** |
| ; CHECK: *** Fusion Candidate Set *** |
| ; CHECK: bb20.preheader |
| ; CHECK: **************************** |
| ; CHECK: Loop Fusion complete |
| define void @non_cfe(ptr noalias %arg, i32 %N) { |
| bb: |
| br label %bb7 |
| |
| bb7: ; preds = %bb, %bb14 |
| %.014 = phi i32 [ 0, %bb ], [ %tmp15, %bb14 ] |
| %indvars.iv23 = phi i64 [ 0, %bb ], [ %indvars.iv.next3, %bb14 ] |
| %tmp = add nsw i32 %.014, -3 |
| %tmp8 = add nuw nsw i64 %indvars.iv23, 3 |
| %tmp9 = trunc i64 %tmp8 to i32 |
| %tmp10 = mul nsw i32 %tmp, %tmp9 |
| %tmp11 = trunc i64 %indvars.iv23 to i32 |
| %tmp12 = srem i32 %tmp10, %tmp11 |
| %tmp13 = getelementptr inbounds i32, ptr %arg, i64 %indvars.iv23 |
| store i32 %tmp12, ptr %tmp13, align 4 |
| br label %bb14 |
| |
| bb14: ; preds = %bb7 |
| %indvars.iv.next3 = add nuw nsw i64 %indvars.iv23, 1 |
| %tmp15 = add nuw nsw i32 %.014, 1 |
| %exitcond4 = icmp ne i64 %indvars.iv.next3, 100 |
| br i1 %exitcond4, label %bb7, label %bb34 |
| |
| bb34: |
| %cmp = icmp slt i32 %N, 50 |
| br i1 %cmp, label %bb16, label %bb33 |
| |
| bb16: ; preds = %bb34 |
| %tmp17 = load i32, ptr %arg, align 4 |
| %tmp18 = icmp slt i32 %tmp17, 0 |
| br i1 %tmp18, label %bb20.preheader, label %bb33 |
| |
| bb20.preheader: ; preds = %bb16 |
| br label %bb22 |
| |
| bb22: ; preds = %bb20.preheader, %bb30 |
| %.02 = phi i32 [ 0, %bb20.preheader ], [ %tmp31, %bb30 ] |
| %indvars.iv1 = phi i64 [ 0, %bb20.preheader ], [ %indvars.iv.next, %bb30 ] |
| %tmp23 = add nsw i32 %.02, -3 |
| %tmp24 = add nuw nsw i64 %indvars.iv1, 3 |
| %tmp25 = trunc i64 %tmp24 to i32 |
| %tmp26 = mul nsw i32 %tmp23, %tmp25 |
| %tmp27 = trunc i64 %indvars.iv1 to i32 |
| %tmp28 = srem i32 %tmp26, %tmp27 |
| %tmp29 = getelementptr inbounds [1024 x i32], ptr @B, i64 0, i64 %indvars.iv1 |
| store i32 %tmp28, ptr %tmp29, align 4 |
| br label %bb30 |
| |
| bb30: ; preds = %bb22 |
| %indvars.iv.next = add nuw nsw i64 %indvars.iv1, 1 |
| %tmp31 = add nuw nsw i32 %.02, 1 |
| %exitcond = icmp ne i64 %indvars.iv.next, 100 |
| br i1 %exitcond, label %bb22, label %bb33.loopexit |
| |
| bb33.loopexit: ; preds = %bb30 |
| br label %bb33 |
| |
| bb33: ; preds = %bb33.loopexit, %bb16, %bb34 |
| ret void |
| } |
| |
| ; Check that fusion detects the two canddates are not adjacent (the exit block |
| ; of the first candidate is not the preheader of the second candidate). |
| |
| ; CHECK: Performing Loop Fusion on function non_adjacent |
| ; CHECK: Fusion Candidates: |
| ; CHECK: *** Fusion Candidate Set *** |
| ; CHECK-NEXT: [[LOOP1PREHEADER:bb[0-9]*]] |
| ; CHECK-NEXT: [[LOOP2PREHEADER:bb[0-9]*]] |
| ; CHECK-NEXT: **************************** |
| ; CHECK: Attempting fusion on Candidate Set: |
| ; CHECK-NEXT: [[LOOP1PREHEADER]] |
| ; CHECK-NEXT: [[LOOP2PREHEADER]] |
| ; CHECK: Fusion candidates are not adjacent. Not fusing. |
| ; CHECK: Loop Fusion complete |
| define void @non_adjacent(ptr noalias %arg) { |
| bb: |
| br label %bb5 |
| |
| bb4: ; preds = %bb11 |
| br label %bb13 |
| |
| bb5: ; preds = %bb, %bb11 |
| %.013 = phi i64 [ 0, %bb ], [ %tmp12, %bb11 ] |
| %tmp = add nsw i64 %.013, -3 |
| %tmp6 = add nuw nsw i64 %.013, 3 |
| %tmp7 = mul nsw i64 %tmp, %tmp6 |
| %tmp8 = srem i64 %tmp7, %.013 |
| %tmp9 = trunc i64 %tmp8 to i32 |
| %tmp10 = getelementptr inbounds i32, ptr %arg, i64 %.013 |
| store i32 %tmp9, ptr %tmp10, align 4 |
| br label %bb11 |
| |
| bb11: ; preds = %bb5 |
| %tmp12 = add nuw nsw i64 %.013, 1 |
| %exitcond2 = icmp ne i64 %tmp12, 100 |
| br i1 %exitcond2, label %bb5, label %bb4 |
| |
| bb13: ; preds = %bb4 |
| br label %bb16 |
| |
| bb15: ; preds = %bb23 |
| br label %bb25 |
| |
| bb16: ; preds = %bb13, %bb23 |
| %.02 = phi i64 [ 0, %bb13 ], [ %tmp24, %bb23 ] |
| %tmp17 = add nsw i64 %.02, -3 |
| %tmp18 = add nuw nsw i64 %.02, 3 |
| %tmp19 = mul nsw i64 %tmp17, %tmp18 |
| %tmp20 = srem i64 %tmp19, %.02 |
| %tmp21 = trunc i64 %tmp20 to i32 |
| %tmp22 = getelementptr inbounds [1024 x i32], ptr @B, i64 0, i64 %.02 |
| store i32 %tmp21, ptr %tmp22, align 4 |
| br label %bb23 |
| |
| bb23: ; preds = %bb16 |
| %tmp24 = add nuw nsw i64 %.02, 1 |
| %exitcond = icmp ne i64 %tmp24, 100 |
| br i1 %exitcond, label %bb16, label %bb15 |
| |
| bb25: ; preds = %bb15 |
| ret void |
| } |
| |
| ; Check that the different bounds are detected and prevent fusion. |
| |
| ; CHECK: Performing Loop Fusion on function different_bounds |
| ; CHECK: Fusion Candidates: |
| ; CHECK: *** Fusion Candidate Set *** |
| ; CHECK-NEXT: [[LOOP1PREHEADER:bb[0-9]*]] |
| ; CHECK-NEXT: [[LOOP2PREHEADER:bb[0-9]*]] |
| ; CHECK-NEXT: **************************** |
| ; CHECK: Attempting fusion on Candidate Set: |
| ; CHECK-NEXT: [[LOOP1PREHEADER]] |
| ; CHECK-NEXT: [[LOOP2PREHEADER]] |
| ; CHECK: Fusion candidates do not have identical trip counts. Not fusing. |
| ; CHECK: Loop Fusion complete |
| define void @different_bounds(ptr noalias %arg) { |
| bb: |
| br label %bb5 |
| |
| bb4: ; preds = %bb11 |
| br label %bb13 |
| |
| bb5: ; preds = %bb, %bb11 |
| %.013 = phi i64 [ 0, %bb ], [ %tmp12, %bb11 ] |
| %tmp = add nsw i64 %.013, -3 |
| %tmp6 = add nuw nsw i64 %.013, 3 |
| %tmp7 = mul nsw i64 %tmp, %tmp6 |
| %tmp8 = srem i64 %tmp7, %.013 |
| %tmp9 = trunc i64 %tmp8 to i32 |
| %tmp10 = getelementptr inbounds i32, ptr %arg, i64 %.013 |
| store i32 %tmp9, ptr %tmp10, align 4 |
| br label %bb11 |
| |
| bb11: ; preds = %bb5 |
| %tmp12 = add nuw nsw i64 %.013, 1 |
| %exitcond2 = icmp ne i64 %tmp12, 100 |
| br i1 %exitcond2, label %bb5, label %bb4 |
| |
| bb13: ; preds = %bb4 |
| br label %bb16 |
| |
| bb15: ; preds = %bb23 |
| br label %bb25 |
| |
| bb16: ; preds = %bb13, %bb23 |
| %.02 = phi i64 [ 0, %bb13 ], [ %tmp24, %bb23 ] |
| %tmp17 = add nsw i64 %.02, -3 |
| %tmp18 = add nuw nsw i64 %.02, 3 |
| %tmp19 = mul nsw i64 %tmp17, %tmp18 |
| %tmp20 = srem i64 %tmp19, %.02 |
| %tmp21 = trunc i64 %tmp20 to i32 |
| %tmp22 = getelementptr inbounds [1024 x i32], ptr @B, i64 0, i64 %.02 |
| store i32 %tmp21, ptr %tmp22, align 4 |
| br label %bb23 |
| |
| bb23: ; preds = %bb16 |
| %tmp24 = add nuw nsw i64 %.02, 1 |
| %exitcond = icmp ne i64 %tmp24, 200 |
| br i1 %exitcond, label %bb16, label %bb15 |
| |
| bb25: ; preds = %bb15 |
| ret void |
| } |
| |
| ; Check that the negative dependence between the two candidates is identified |
| ; and prevents fusion. |
| |
| ; CHECK: Performing Loop Fusion on function negative_dependence |
| ; CHECK: Fusion Candidates: |
| ; CHECK: *** Fusion Candidate Set *** |
| ; CHECK-NEXT: [[LOOP1PREHEADER:bb[0-9]*]] |
| ; CHECK-NEXT: [[LOOP2PREHEADER:bb[0-9]*]] |
| ; CHECK-NEXT: **************************** |
| ; CHECK: Attempting fusion on Candidate Set: |
| ; CHECK-NEXT: [[LOOP1PREHEADER]] |
| ; CHECK-NEXT: [[LOOP2PREHEADER]] |
| ; CHECK: Memory dependencies do not allow fusion! |
| ; CHECK: Loop Fusion complete |
| define void @negative_dependence(ptr noalias %arg) { |
| bb: |
| br label %bb7 |
| |
| bb11.preheader: ; preds = %bb9 |
| br label %bb13 |
| |
| bb7: ; preds = %bb, %bb9 |
| %indvars.iv22 = phi i64 [ 0, %bb ], [ %indvars.iv.next3, %bb9 ] |
| %tmp = getelementptr inbounds i32, ptr %arg, i64 %indvars.iv22 |
| %tmp8 = trunc i64 %indvars.iv22 to i32 |
| store i32 %tmp8, ptr %tmp, align 4 |
| br label %bb9 |
| |
| bb9: ; preds = %bb7 |
| %indvars.iv.next3 = add nuw nsw i64 %indvars.iv22, 1 |
| %exitcond4 = icmp ne i64 %indvars.iv.next3, 100 |
| br i1 %exitcond4, label %bb7, label %bb11.preheader |
| |
| bb13: ; preds = %bb11.preheader, %bb18 |
| %indvars.iv1 = phi i64 [ 0, %bb11.preheader ], [ %indvars.iv.next, %bb18 ] |
| %indvars.iv.next = add nuw nsw i64 %indvars.iv1, 1 |
| %tmp14 = getelementptr inbounds i32, ptr %arg, i64 %indvars.iv.next |
| %tmp15 = load i32, ptr %tmp14, align 4 |
| %tmp16 = shl nsw i32 %tmp15, 1 |
| %tmp17 = getelementptr inbounds [1024 x i32], ptr @B, i64 0, i64 %indvars.iv1 |
| store i32 %tmp16, ptr %tmp17, align 4 |
| br label %bb18 |
| |
| bb18: ; preds = %bb13 |
| %exitcond = icmp ne i64 %indvars.iv.next, 100 |
| br i1 %exitcond, label %bb13, label %bb19 |
| |
| bb19: ; preds = %bb18 |
| ret void |
| } |
| |
| ; Check for values defined in Loop 0 and used in Loop 1. |
| ; It is not safe to fuse in this case, because the second loop has |
| ; a use of %.01.lcssa which is defined in the body of loop 0. The |
| ; first loop must execute completely in order to compute the correct |
| ; value of %.01.lcssa to be used in the second loop. |
| |
| ; CHECK: Performing Loop Fusion on function sumTest |
| ; CHECK: Fusion Candidates: |
| ; CHECK: *** Fusion Candidate Set *** |
| ; CHECK-NEXT: [[LOOP1PREHEADER:bb[0-9]*]] |
| ; CHECK-NEXT: [[LOOP2PREHEADER:bb[0-9]*]] |
| ; CHECK-NEXT: **************************** |
| ; CHECK: Attempting fusion on Candidate Set: |
| ; CHECK-NEXT: [[LOOP1PREHEADER]] |
| ; CHECK-NEXT: [[LOOP2PREHEADER]] |
| ; CHECK: Memory dependencies do not allow fusion! |
| ; CHECK: Loop Fusion complete |
| define i32 @sumTest(ptr noalias %arg) { |
| bb: |
| br label %bb9 |
| |
| bb13.preheader: ; preds = %bb9 |
| br label %bb15 |
| |
| bb9: ; preds = %bb, %bb9 |
| %.01.lcssa = phi i32 [ 0, %bb ], [ %tmp11, %bb9 ] |
| %.013 = phi i32 [ 0, %bb ], [ %tmp11, %bb9 ] |
| %indvars.iv32 = phi i64 [ 0, %bb ], [ %indvars.iv.next4, %bb9 ] |
| %tmp = getelementptr inbounds i32, ptr %arg, i64 %indvars.iv32 |
| %tmp10 = load i32, ptr %tmp, align 4 |
| %tmp11 = add nsw i32 %.013, %tmp10 |
| %indvars.iv.next4 = add nuw nsw i64 %indvars.iv32, 1 |
| %exitcond5 = icmp ne i64 %indvars.iv.next4, 100 |
| br i1 %exitcond5, label %bb9, label %bb13.preheader |
| |
| bb14: ; preds = %bb20 |
| br label %bb21 |
| |
| bb15: ; preds = %bb13.preheader, %bb20 |
| %indvars.iv1 = phi i64 [ 0, %bb13.preheader ], [ %indvars.iv.next, %bb20 ] |
| %tmp16 = getelementptr inbounds i32, ptr %arg, i64 %indvars.iv1 |
| %tmp17 = load i32, ptr %tmp16, align 4 |
| %tmp18 = sdiv i32 %tmp17, %.01.lcssa |
| %tmp19 = getelementptr inbounds [1024 x i32], ptr @B, i64 0, i64 %indvars.iv1 |
| store i32 %tmp18, ptr %tmp19, align 4 |
| br label %bb20 |
| |
| bb20: ; preds = %bb15 |
| %indvars.iv.next = add nuw nsw i64 %indvars.iv1, 1 |
| %exitcond = icmp ne i64 %indvars.iv.next, 100 |
| br i1 %exitcond, label %bb15, label %bb14 |
| |
| bb21: ; preds = %bb14 |
| ret i32 %.01.lcssa |
| } |
| |
| ; Similar to sumTest above. The first loop computes %add and must |
| ; complete before it is used in the second loop. Thus, these two loops |
| ; also cannot be fused. |
| |
| ; CHECK: Performing Loop Fusion on function test |
| ; CHECK: Fusion Candidates: |
| ; CHECK: *** Fusion Candidate Set *** |
| ; CHECK-NEXT: [[LOOP1PREHEADER:for.body[0-9]*.preheader]] |
| ; CHECK-NEXT: [[LOOP2PREHEADER:for.body[0-9]*.preheader]] |
| ; CHECK-NEXT: **************************** |
| ; CHECK: Attempting fusion on Candidate Set: |
| ; CHECK-NEXT: [[LOOP1PREHEADER]] |
| ; CHECK-NEXT: [[LOOP2PREHEADER]] |
| ; CHECK: Memory dependencies do not allow fusion! |
| ; CHECK: Loop Fusion complete |
| define float @test(ptr nocapture %a, i32 %n) { |
| entry: |
| %conv = zext i32 %n to i64 |
| %cmp32 = icmp eq i32 %n, 0 |
| br i1 %cmp32, label %for.cond.cleanup7, label %for.body |
| |
| for.body: ; preds = %for.body, %entry |
| %i.034 = phi i64 [ %inc, %for.body ], [ 0, %entry ] |
| %sum1.033 = phi float [ %add, %for.body ], [ 0.000000e+00, %entry ] |
| %idxprom = trunc i64 %i.034 to i32 |
| %arrayidx = getelementptr inbounds float, ptr %a, i32 %idxprom |
| %0 = load float, ptr %arrayidx, align 4 |
| %add = fadd float %sum1.033, %0 |
| %inc = add nuw nsw i64 %i.034, 1 |
| %cmp = icmp ult i64 %inc, %conv |
| br i1 %cmp, label %for.body, label %for.body8 |
| |
| for.body8: ; preds = %for.body, %for.body8 |
| %i2.031 = phi i64 [ %inc14, %for.body8 ], [ 0, %for.body ] |
| %idxprom9 = trunc i64 %i2.031 to i32 |
| %arrayidx10 = getelementptr inbounds float, ptr %a, i32 %idxprom9 |
| %1 = load float, ptr %arrayidx10, align 4 |
| %div = fdiv float %1, %add |
| store float %div, ptr %arrayidx10, align 4 |
| %inc14 = add nuw nsw i64 %i2.031, 1 |
| %cmp5 = icmp ult i64 %inc14, %conv |
| br i1 %cmp5, label %for.body8, label %for.cond.cleanup7 |
| |
| for.cond.cleanup7: ; preds = %for.body8, %entry |
| %sum1.0.lcssa36 = phi float [ 0.000000e+00, %entry ], [ %add, %for.body8 ] |
| ret float %sum1.0.lcssa36 |
| } |
| |
| ; Check that non-rotated loops are not considered for fusion. |
| ; CHECK: Performing Loop Fusion on function notRotated |
| ; CHECK: Loop bb{{.*}} is not rotated! |
| ; CHECK: Loop bb{{.*}} is not rotated! |
| define void @notRotated(ptr noalias %arg) { |
| bb: |
| br label %bb5 |
| |
| bb5: ; preds = %bb14, %bb |
| %indvars.iv2 = phi i64 [ %indvars.iv.next3, %bb14 ], [ 0, %bb ] |
| %.01 = phi i32 [ 0, %bb ], [ %tmp15, %bb14 ] |
| %exitcond4 = icmp ne i64 %indvars.iv2, 100 |
| br i1 %exitcond4, label %bb7, label %bb17 |
| |
| bb7: ; preds = %bb5 |
| %tmp = add nsw i32 %.01, -3 |
| %tmp8 = add nuw nsw i64 %indvars.iv2, 3 |
| %tmp9 = trunc i64 %tmp8 to i32 |
| %tmp10 = mul nsw i32 %tmp, %tmp9 |
| %tmp11 = trunc i64 %indvars.iv2 to i32 |
| %tmp12 = srem i32 %tmp10, %tmp11 |
| %tmp13 = getelementptr inbounds i32, ptr %arg, i64 %indvars.iv2 |
| store i32 %tmp12, ptr %tmp13, align 4 |
| br label %bb14 |
| |
| bb14: ; preds = %bb7 |
| %indvars.iv.next3 = add nuw nsw i64 %indvars.iv2, 1 |
| %tmp15 = add nuw nsw i32 %.01, 1 |
| br label %bb5 |
| |
| bb17: ; preds = %bb27, %bb5 |
| %indvars.iv = phi i64 [ %indvars.iv.next, %bb27 ], [ 0, %bb5 ] |
| %.0 = phi i32 [ 0, %bb5 ], [ %tmp28, %bb27 ] |
| %exitcond = icmp ne i64 %indvars.iv, 100 |
| br i1 %exitcond, label %bb19, label %bb18 |
| |
| bb18: ; preds = %bb17 |
| br label %bb29 |
| |
| bb19: ; preds = %bb17 |
| %tmp20 = add nsw i32 %.0, -3 |
| %tmp21 = add nuw nsw i64 %indvars.iv, 3 |
| %tmp22 = trunc i64 %tmp21 to i32 |
| %tmp23 = mul nsw i32 %tmp20, %tmp22 |
| %tmp24 = trunc i64 %indvars.iv to i32 |
| %tmp25 = srem i32 %tmp23, %tmp24 |
| %tmp26 = getelementptr inbounds [1024 x i32], ptr @B, i64 0, i64 %indvars.iv |
| store i32 %tmp25, ptr %tmp26, align 4 |
| br label %bb27 |
| |
| bb27: ; preds = %bb19 |
| %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1 |
| %tmp28 = add nuw nsw i32 %.0, 1 |
| br label %bb17 |
| |
| bb29: ; preds = %bb18 |
| ret void |
| } |
