| ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py |
| ; RUN: opt < %s -passes=loop-interchange -verify-loop-lcssa -S | FileCheck %s |
| |
| ; A cross-level reduction (%acc) over the (j, i) pair, nested in an outer k loop |
| ; and guarded by an if, so the reduction seed %mul lives in a dedicated, |
| ; single-predecessor preheader of the j loop. When j and i interchange, the |
| ; reduction PHI moves to the new outer header and its seed edge references %mul. |
| ; The preheader-content swap must run before the LCSSA rebuild so that %mul is |
| ; relocated into the new outer preheader and dominates that edge; otherwise |
| ; formLCSSAForInstructions is handed dominance-broken IR. |
| ; |
| ; Generated with 'clang -O1 -fno-unroll-loops -S -emit-llvm' |
| ; |
| ; long reduction_seed_in_guarded_preheader(long Arr[restrict 100][100], const long * restrict guard) { |
| ; long total = 0; |
| ; for (long k = 0; k < 100; ++k) |
| ; if (guard[k]) { |
| ; long acc = k * 7; // reduction seed |
| ; for (long j = 0; j < 100; ++j) |
| ; for (long i = 0; i < 100; ++i) |
| ; acc += Arr[i][j]; // j/i interchange candidate |
| ; total += acc; |
| ; } |
| ; return total; |
| ; } |
| |
| define i64 @reduction_seed_in_guarded_preheader(ptr noalias readonly %Arr, ptr noalias readonly %guard) { |
| ; CHECK-LABEL: @reduction_seed_in_guarded_preheader( |
| ; CHECK-NEXT: entry: |
| ; CHECK-NEXT: br label [[FOR_BODY:%.*]] |
| ; CHECK: for.cond.cleanup: |
| ; CHECK-NEXT: [[TOTAL_1_LCSSA:%.*]] = phi i64 [ [[TOTAL_1:%.*]], [[FOR_INC15:%.*]] ] |
| ; CHECK-NEXT: ret i64 [[TOTAL_1_LCSSA]] |
| ; CHECK: for.body: |
| ; CHECK-NEXT: [[K_032:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[INC16:%.*]], [[FOR_INC15]] ] |
| ; CHECK-NEXT: [[TOTAL_031:%.*]] = phi i64 [ 0, [[ENTRY]] ], [ [[TOTAL_1]], [[FOR_INC15]] ] |
| ; CHECK-NEXT: [[ARRAYIDX:%.*]] = getelementptr inbounds nuw [8 x i8], ptr [[GUARD:%.*]], i64 [[K_032]] |
| ; CHECK-NEXT: [[TMP0:%.*]] = load i64, ptr [[ARRAYIDX]], align 8 |
| ; CHECK-NEXT: [[TOBOOL_NOT:%.*]] = icmp eq i64 [[TMP0]], 0 |
| ; CHECK-NEXT: br i1 [[TOBOOL_NOT]], label [[FOR_INC15]], label [[FOR_BODY8_PREHEADER:%.*]] |
| ; CHECK: if.then: |
| ; CHECK-NEXT: br label [[FOR_COND5_PREHEADER:%.*]] |
| ; CHECK: for.cond5.preheader: |
| ; CHECK-NEXT: [[J_030:%.*]] = phi i64 [ 0, [[IF_THEN:%.*]] ], [ [[INC12:%.*]], [[FOR_COND_CLEANUP7:%.*]] ] |
| ; CHECK-NEXT: [[ACC_127:%.*]] = phi i64 [ [[ADD:%.*]], [[FOR_COND_CLEANUP7]] ], [ [[ACC_029:%.*]], [[IF_THEN]] ] |
| ; CHECK-NEXT: [[INVARIANT_GEP:%.*]] = getelementptr inbounds nuw [8 x i8], ptr [[ARR:%.*]], i64 [[J_030]] |
| ; CHECK-NEXT: br label [[FOR_BODY8_SPLIT1:%.*]] |
| ; CHECK: for.body8.preheader: |
| ; CHECK-NEXT: [[MUL:%.*]] = mul nuw nsw i64 [[K_032]], 7 |
| ; CHECK-NEXT: br label [[FOR_BODY8:%.*]] |
| ; CHECK: for.cond.cleanup3: |
| ; CHECK-NEXT: [[ADD_LCSSA_LCSSA:%.*]] = phi i64 [ [[ADD_LCSSA:%.*]], [[FOR_BODY8_SPLIT:%.*]] ] |
| ; CHECK-NEXT: [[ADD14:%.*]] = add nsw i64 [[ADD_LCSSA_LCSSA]], [[TOTAL_031]] |
| ; CHECK-NEXT: br label [[FOR_INC15]] |
| ; CHECK: for.cond.cleanup7: |
| ; CHECK-NEXT: [[INC12]] = add nuw nsw i64 [[J_030]], 1 |
| ; CHECK-NEXT: [[EXITCOND33_NOT:%.*]] = icmp eq i64 [[INC12]], 100 |
| ; CHECK-NEXT: br i1 [[EXITCOND33_NOT]], label [[FOR_BODY8_SPLIT]], label [[FOR_COND5_PREHEADER]] |
| ; CHECK: for.body8: |
| ; CHECK-NEXT: [[I_028:%.*]] = phi i64 [ [[TMP2:%.*]], [[FOR_BODY8_SPLIT]] ], [ 0, [[FOR_BODY8_PREHEADER]] ] |
| ; CHECK-NEXT: [[ACC_029]] = phi i64 [ [[MUL]], [[FOR_BODY8_PREHEADER]] ], [ [[ADD_LCSSA]], [[FOR_BODY8_SPLIT]] ] |
| ; CHECK-NEXT: br label [[IF_THEN]] |
| ; CHECK: for.body8.split1: |
| ; CHECK-NEXT: [[GEP:%.*]] = getelementptr inbounds nuw [800 x i8], ptr [[INVARIANT_GEP]], i64 [[I_028]] |
| ; CHECK-NEXT: [[TMP1:%.*]] = load i64, ptr [[GEP]], align 8 |
| ; CHECK-NEXT: [[ADD]] = add i64 [[TMP1]], [[ACC_127]] |
| ; CHECK-NEXT: [[INC:%.*]] = add nuw nsw i64 [[I_028]], 1 |
| ; CHECK-NEXT: [[EXITCOND_NOT:%.*]] = icmp eq i64 [[INC]], 100 |
| ; CHECK-NEXT: br label [[FOR_COND_CLEANUP7]] |
| ; CHECK: for.body8.split: |
| ; CHECK-NEXT: [[ADD_LCSSA]] = phi i64 [ [[ADD]], [[FOR_COND_CLEANUP7]] ] |
| ; CHECK-NEXT: [[TMP2]] = add nuw nsw i64 [[I_028]], 1 |
| ; CHECK-NEXT: [[TMP3:%.*]] = icmp eq i64 [[TMP2]], 100 |
| ; CHECK-NEXT: br i1 [[TMP3]], label [[FOR_COND_CLEANUP3:%.*]], label [[FOR_BODY8]] |
| ; CHECK: for.inc15: |
| ; CHECK-NEXT: [[TOTAL_1]] = phi i64 [ [[ADD14]], [[FOR_COND_CLEANUP3]] ], [ [[TOTAL_031]], [[FOR_BODY]] ] |
| ; CHECK-NEXT: [[INC16]] = add nuw nsw i64 [[K_032]], 1 |
| ; CHECK-NEXT: [[EXITCOND34_NOT:%.*]] = icmp eq i64 [[INC16]], 100 |
| ; CHECK-NEXT: br i1 [[EXITCOND34_NOT]], label [[FOR_COND_CLEANUP:%.*]], label [[FOR_BODY]] |
| ; |
| entry: |
| br label %for.body |
| |
| for.cond.cleanup: ; preds = %for.inc15 |
| ret i64 %total.1 |
| |
| for.body: ; preds = %entry, %for.inc15 |
| %k.032 = phi i64 [ 0, %entry ], [ %inc16, %for.inc15 ] |
| %total.031 = phi i64 [ 0, %entry ], [ %total.1, %for.inc15 ] |
| %arrayidx = getelementptr inbounds nuw [8 x i8], ptr %guard, i64 %k.032 |
| %0 = load i64, ptr %arrayidx, align 8 |
| %tobool.not = icmp eq i64 %0, 0 |
| br i1 %tobool.not, label %for.inc15, label %if.then |
| |
| if.then: ; preds = %for.body |
| %mul = mul nuw nsw i64 %k.032, 7 |
| br label %for.cond5.preheader |
| |
| for.cond5.preheader: ; preds = %if.then, %for.cond.cleanup7 |
| %j.030 = phi i64 [ 0, %if.then ], [ %inc12, %for.cond.cleanup7 ] |
| %acc.029 = phi i64 [ %mul, %if.then ], [ %add, %for.cond.cleanup7 ] |
| %invariant.gep = getelementptr inbounds nuw [8 x i8], ptr %Arr, i64 %j.030 |
| br label %for.body8 |
| |
| for.cond.cleanup3: ; preds = %for.cond.cleanup7 |
| %add14 = add nsw i64 %add, %total.031 |
| br label %for.inc15 |
| |
| for.cond.cleanup7: ; preds = %for.body8 |
| %inc12 = add nuw nsw i64 %j.030, 1 |
| %exitcond33.not = icmp eq i64 %inc12, 100 |
| br i1 %exitcond33.not, label %for.cond.cleanup3, label %for.cond5.preheader |
| |
| for.body8: ; preds = %for.cond5.preheader, %for.body8 |
| %i.028 = phi i64 [ 0, %for.cond5.preheader ], [ %inc, %for.body8 ] |
| %acc.127 = phi i64 [ %acc.029, %for.cond5.preheader ], [ %add, %for.body8 ] |
| %gep = getelementptr inbounds nuw [800 x i8], ptr %invariant.gep, i64 %i.028 |
| %1 = load i64, ptr %gep, align 8 |
| %add = add nsw i64 %1, %acc.127 |
| %inc = add nuw nsw i64 %i.028, 1 |
| %exitcond.not = icmp eq i64 %inc, 100 |
| br i1 %exitcond.not, label %for.cond.cleanup7, label %for.body8 |
| |
| for.inc15: ; preds = %for.body, %for.cond.cleanup3 |
| %total.1 = phi i64 [ %add14, %for.cond.cleanup3 ], [ %total.031, %for.body ] |
| %inc16 = add nuw nsw i64 %k.032, 1 |
| %exitcond34.not = icmp eq i64 %inc16, 100 |
| br i1 %exitcond34.not, label %for.cond.cleanup, label %for.body |
| } |
