237 lines · plain
1; RUN: opt < %s -passes=loop-interchange -cache-line-size=64 \2; RUN: -pass-remarks-output=%t -disable-output -loop-interchange-profitabilities=vectorize3; RUN: FileCheck -input-file %t %s4 5@A = dso_local global [256 x [256 x float]] zeroinitializer6@B = dso_local global [256 x [256 x float]] zeroinitializer7@C = dso_local global [256 x [256 x float]] zeroinitializer8@D = global [256 x [256 x [256 x float]]] zeroinitializer9@E = global [256 x [256 x [256 x float]]] zeroinitializer10 11; Check that the below loops are exchanged for vectorization.12;13; for (int i = 0; i < 256; i++) {14; for (int j = 1; j < 256; j++) {15; A[i][j] = A[i][j-1] + B[i][j];16; C[i][j] += 1;17; }18; }19;20 21; CHECK: --- !Passed22; CHECK-NEXT: Pass: loop-interchange23; CHECK-NEXT: Name: Interchanged24; CHECK-NEXT: Function: interchange_necessary_for_vectorization25; CHECK-NEXT: Args:26; CHECK-NEXT: - String: Loop interchanged with enclosing loop.27define void @interchange_necessary_for_vectorization() {28entry:29 br label %for.i.header30 31for.i.header:32 %i = phi i64 [ 1, %entry ], [ %i.next, %for.i.inc ]33 br label %for.j.body34 35for.j.body:36 %j = phi i64 [ 1, %for.i.header ], [ %j.next, %for.j.body ]37 %j.dec = add nsw i64 %j, -138 %a.load.index = getelementptr nuw inbounds [256 x [256 x float]], ptr @A, i64 0, i64 %i, i64 %j.dec39 %b.index = getelementptr nuw inbounds [256 x [256 x float]], ptr @B, i64 0, i64 %i, i64 %j40 %c.index = getelementptr nuw inbounds [256 x [256 x float]], ptr @C, i64 0, i64 %i, i64 %j41 %a = load float, ptr %a.load.index, align 442 %b = load float, ptr %b.index, align 443 %c = load float, ptr %c.index, align 444 %add.0 = fadd float %a, %b45 %a.store.index = getelementptr nuw inbounds [256 x [256 x float]], ptr @A, i64 0, i64 %i, i64 %j46 store float %add.0, ptr %a.store.index, align 447 %add.1 = fadd float %c, 1.048 store float %add.1, ptr %c.index, align 449 %j.next = add nuw nsw i64 %j, 150 %cmp.j = icmp eq i64 %j.next, 25651 br i1 %cmp.j, label %for.i.inc, label %for.j.body52 53for.i.inc:54 %i.next = add nuw nsw i64 %i, 155 %cmp.i = icmp eq i64 %i.next, 25656 br i1 %cmp.i, label %exit, label %for.i.header57 58exit:59 ret void60}61 62; Check that the following innermost loop can be vectorized so that63; interchanging is unnecessary.64;65; for (int i = 0; i < 256; i++)66; for (int j = 1; j < 256; j++)67; A[i][j-1] = A[i][j] + B[i][j];68;69 70; CHECK: --- !Missed71; CHECK-NEXT: Pass: loop-interchange72; CHECK-NEXT: Name: InterchangeNotProfitable73; CHECK-NEXT: Function: interchange_unnecesasry_for_vectorization74; CHECK-NEXT: Args:75; CHECK-NEXT: - String: Insufficient information to calculate the cost of loop for interchange.76define void @interchange_unnecesasry_for_vectorization() {77entry:78 br label %for.i.header79 80for.i.header:81 %i = phi i64 [ 1, %entry ], [ %i.next, %for.i.inc ]82 br label %for.j.body83 84for.j.body:85 %j = phi i64 [ 1, %for.i.header ], [ %j.next, %for.j.body ]86 %j.dec = add nsw i64 %j, -187 %a.load.index = getelementptr nuw inbounds [256 x [256 x float]], ptr @A, i64 0, i64 %i, i64 %j88 %b.index = getelementptr nuw inbounds [256 x [256 x float]], ptr @B, i64 0, i64 %i, i64 %j89 %a = load float, ptr %a.load.index, align 490 %b = load float, ptr %b.index, align 491 %add = fadd float %a, %b92 %a.store.index = getelementptr nuw inbounds [256 x [256 x float]], ptr @A, i64 0, i64 %i, i64 %j.dec93 store float %add, ptr %a.store.index, align 494 %j.next = add nuw nsw i64 %j, 195 %cmp.j = icmp eq i64 %j.next, 25696 br i1 %cmp.j, label %for.i.inc, label %for.j.body97 98for.i.inc:99 %i.next = add nuw nsw i64 %i, 1100 %cmp.i = icmp eq i64 %i.next, 256101 br i1 %cmp.i, label %exit, label %for.i.header102 103exit:104 ret void105}106 107; Check that the below loops are exchanged to allow innermost loop108; vectorization. We cannot vectorize the j-loop because it has a lexically109; backward dependency, but the i-loop can be vectorized because all the110; loop-carried dependencies are lexically forward. LoopVectorize currently only111; vectorizes innermost loop, hence move the i-loop to that position.112;113; for (int i = 0; i < 255; i++) {114; for (int j = 1; j < 256; j++) {115; A[i][j] = A[i][j-1] + B[i][j];116; C[i][j] += C[i+1][j];117; }118; }119;120 121; CHECK: --- !Passed122; CHECK-NEXT: Pass: loop-interchange123; CHECK-NEXT: Name: Interchanged124; CHECK-NEXT: Function: interchange_necessary_for_vectorization2125; CHECK-NEXT: Args:126; CHECK-NEXT: - String: Loop interchanged with enclosing loop.127define void @interchange_necessary_for_vectorization2() {128entry:129 br label %for.i.header130 131for.i.header:132 %i = phi i64 [ 1, %entry ], [ %i.next, %for.i.inc ]133 %i.inc = add nuw nsw i64 %i, 1134 br label %for.j.body135 136for.j.body:137 %j = phi i64 [ 1, %for.i.header ], [ %j.next, %for.j.body ]138 %j.dec = add nsw i64 %j, -1139 %a.load.index = getelementptr inbounds [256 x [256 x float]], ptr @A, i64 0, i64 %i, i64 %j.dec140 %b.index = getelementptr inbounds [256 x [256 x float]], ptr @B, i64 0, i64 %i, i64 %j141 %c.load.index = getelementptr inbounds [256 x [256 x float]], ptr @C, i64 0, i64 %i.inc, i64 %j142 %c.store.index = getelementptr inbounds [256 x [256 x float]], ptr @C, i64 0, i64 %i, i64 %j143 %a = load float, ptr %a.load.index144 %b = load float, ptr %b.index145 %c0 = load float, ptr %c.load.index146 %c1 = load float, ptr %c.store.index147 %add.0 = fadd float %a, %b148 %a.store.index = getelementptr inbounds [256 x [256 x float]], ptr @A, i64 0, i64 %i, i64 %j149 store float %add.0, ptr %a.store.index150 %add.1 = fadd float %c0, %c1151 store float %add.1, ptr %c.store.index152 %j.next = add nuw nsw i64 %j, 1153 %cmp.j = icmp eq i64 %j.next, 256154 br i1 %cmp.j, label %for.i.inc, label %for.j.body155 156for.i.inc:157 %i.next = add nuw nsw i64 %i, 1158 %cmp.i = icmp eq i64 %i.next, 255159 br i1 %cmp.i, label %exit, label %for.i.header160 161exit:162 ret void163}164 165; Check that no interchange is performed for the following loop. Interchanging166; the j-loop and k-loop makes the innermost loop vectorizble, since the j-loop167; has only forward dependencies. However, at the moment, a loop body consisting168; of multiple BBs is handled pesimistically. Hence the j-loop isn't moved to169; the innermost place.170;171; for (int i = 0; i < 255; i++) {172; for (int j = 0; j < 255; j++) {173; for (int k = 0; k < 128; k++) {174; E[i][j][k] = D[i+1][j+1][2*k];175; if (cond)176; D[i][j][k+1] = 1.0;177; }178; }179 180; CHECK: --- !Missed181; CHECK-NEXT: Pass: loop-interchange182; CHECK-NEXT: Name: InterchangeNotProfitable183; CHECK-NEXT: Function: multiple_BBs_in_loop184; CHECK-NEXT: Args:185; CHECK-NEXT: - String: Interchanging loops is not considered to improve cache locality nor vectorization.186; CHECK: --- !Missed187; CHECK-NEXT: Pass: loop-interchange188; CHECK-NEXT: Name: InterchangeNotProfitable189; CHECK-NEXT: Function: multiple_BBs_in_loop190; CHECK-NEXT: Args:191; CHECK-NEXT: - String: Interchanging loops is not considered to improve cache locality nor vectorization.192define void @multiple_BBs_in_loop() {193entry:194 br label %for.i.header195 196for.i.header:197 %i = phi i64 [ 0, %entry ], [ %i.inc, %for.i.inc ]198 %i.inc = add nuw nsw i64 %i, 1199 br label %for.j.header200 201for.j.header:202 %j = phi i64 [ 0, %for.i.header ], [ %j.inc, %for.j.inc ]203 %j.inc = add nuw nsw i64 %j, 1204 br label %for.k.body205 206for.k.body:207 %k = phi i64 [ 0, %for.j.header ], [ %k.inc, %for.k.inc ]208 %k.inc = add nuw nsw i64 %k, 1209 %k.2 = mul nuw nsw i64 %k, 2210 %d.index = getelementptr inbounds [256 x [256 x [256 x float]]], ptr @D, i64 0, i64 %i.inc, i64 %j.inc, i64 %k.2211 %e.index = getelementptr inbounds [256 x [256 x [256 x float]]], ptr @E, i64 0, i64 %i, i64 %j, i64 %k212 %d.load = load float, ptr %d.index213 store float %d.load, ptr %e.index214 %cond = freeze i1 undef215 br i1 %cond, label %if.then, label %for.k.inc216 217if.then:218 %d.index2 = getelementptr inbounds [256 x [256 x [256 x float]]], ptr @D, i64 0, i64 %i, i64 %j, i64 %k.inc219 store float 1.0, ptr %d.index2220 br label %for.k.inc221 222for.k.inc:223 %cmp.k = icmp eq i64 %k.inc, 128224 br i1 %cmp.k, label %for.j.inc, label %for.k.body225 226for.j.inc:227 %cmp.j = icmp eq i64 %j.inc, 255228 br i1 %cmp.j, label %for.i.inc, label %for.j.header229 230for.i.inc:231 %cmp.i = icmp eq i64 %i.inc, 255232 br i1 %cmp.i, label %exit, label %for.i.header233 234exit:235 ret void236}237