234 lines · plain
1; Remove 'S' Scalar Dependencies #1193452; Scalar dependencies are not handled correctly, so they were removed to avoid3; miscompiles. The loop nest in this test case used to be interchanged, but it's4; no longer triggering. XFAIL'ing this test to indicate that this test should5; interchanged if scalar deps are handled correctly.6;7; XFAIL: *8 9; RUN: opt < %s -passes=loop-interchange -cache-line-size=64 -pass-remarks-output=%t -verify-dom-info -verify-loop-info \10; RUN: -pass-remarks=loop-interchange -pass-remarks-missed=loop-interchange11; RUN: FileCheck -input-file %t %s12 13; RUN: opt < %s -passes=loop-interchange,loop-interchange -cache-line-size=64 \14; RUN: -pass-remarks-output=%t -pass-remarks='loop-interchange' -S15; RUN: cat %t | FileCheck --check-prefix=PROFIT %s16 17;; We test profitability model in these test cases.18 19target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"20 21@A = common global [100 x [100 x i32]] zeroinitializer22@B = common global [100 x [100 x i32]] zeroinitializer23 24;;---------------------------------------Test case 01---------------------------------25;; Loops interchange will result in better cache locality and hence profitable. Check for interchange.26;; for(int i=1;i<100;i++)27;; for(int j=1;j<100;j++)28;; A[j][i] = A[j - 1][i] + B[j][i];29 30; CHECK: Name: Interchanged31; CHECK-NEXT: Function: interchange_0132 33define void @interchange_01() {34entry:35 br label %for2.preheader36 37for2.preheader:38 %i30 = phi i64 [ 1, %entry ], [ %i.next31, %for1.inc14 ]39 br label %for240 41for2:42 %j = phi i64 [ %i.next, %for2 ], [ 1, %for2.preheader ]43 %j.prev = add nsw i64 %j, -144 %arrayidx5 = getelementptr inbounds [100 x [100 x i32]], ptr @A, i64 0, i64 %j.prev, i64 %i3045 %lv1 = load i32, ptr %arrayidx546 %arrayidx9 = getelementptr inbounds [100 x [100 x i32]], ptr @B, i64 0, i64 %j, i64 %i3047 %lv2 = load i32, ptr %arrayidx948 %add = add nsw i32 %lv1, %lv249 %arrayidx13 = getelementptr inbounds [100 x [100 x i32]], ptr @A, i64 0, i64 %j, i64 %i3050 store i32 %add, ptr %arrayidx1351 %i.next = add nuw nsw i64 %j, 152 %exitcond = icmp eq i64 %j, 9953 br i1 %exitcond, label %for1.inc14, label %for254 55for1.inc14:56 %i.next31 = add nuw nsw i64 %i30, 157 %exitcond33 = icmp eq i64 %i30, 9958 br i1 %exitcond33, label %for.end16, label %for2.preheader59 60for.end16:61 ret void62}63 64;; ---------------------------------------Test case 02---------------------------------65;; Check loop interchange profitability model.66;; This tests profitability model when operands of getelementpointer and not exactly the induction variable but some67;; arithmetic operation on them.68;; for(int i=1;i<N;i++)69;; for(int j=1;j<N;j++)70;; A[j-1][i-1] = A[j - 1][i-1] + B[j-1][i-1];71 72; CHECK: Name: Interchanged73; CHECK-NEXT: Function: interchange_0274define void @interchange_02() {75entry:76 br label %for1.header77 78for1.header:79 %i35 = phi i64 [ 1, %entry ], [ %i.next36, %for1.inc19 ]80 %i.prev = add nsw i64 %i35, -181 br label %for282 83for2:84 %j = phi i64 [ 1, %for1.header ], [ %i.next, %for2 ]85 %j.prev = add nsw i64 %j, -186 %arrayidx6 = getelementptr inbounds [100 x [100 x i32]], ptr @A, i64 0, i64 %j.prev, i64 %i.prev87 %lv1 = load i32, ptr %arrayidx688 %arrayidx12 = getelementptr inbounds [100 x [100 x i32]], ptr @B, i64 0, i64 %j.prev, i64 %i.prev89 %lv2 = load i32, ptr %arrayidx1290 %add = add nsw i32 %lv1, %lv291 store i32 %add, ptr %arrayidx692 %i.next = add nuw nsw i64 %j, 193 %exitcond = icmp eq i64 %j, 9994 br i1 %exitcond, label %for1.inc19, label %for295 96for1.inc19:97 %i.next36 = add nuw nsw i64 %i35, 198 %exitcond39 = icmp eq i64 %i35, 9999 br i1 %exitcond39, label %for.end21, label %for1.header100 101for.end21:102 ret void103}104 105;;---------------------------------------Test case 03---------------------------------106;; Loops interchange is not profitable.107;; for(int i=1;i<100;i++)108;; for(int j=1;j<100;j++)109;; A[i-1][j-1] = A[i - 1][j-1] + B[i][j];110 111; CHECK: Name: InterchangeNotProfitable112; CHECK-NEXT: Function: interchange_03113define void @interchange_03(){114entry:115 br label %for1.header116 117for1.header:118 %i34 = phi i64 [ 1, %entry ], [ %i.next35, %for1.inc17 ]119 %i.prev = add nsw i64 %i34, -1120 br label %for2121 122for2:123 %j = phi i64 [ 1, %for1.header ], [ %i.next, %for2 ]124 %j.prev = add nsw i64 %j, -1125 %arrayidx6 = getelementptr inbounds [100 x [100 x i32]], ptr @A, i64 0, i64 %i.prev, i64 %j.prev126 %lv1 = load i32, ptr %arrayidx6127 %arrayidx10 = getelementptr inbounds [100 x [100 x i32]], ptr @B, i64 0, i64 %i34, i64 %j128 %lv2 = load i32, ptr %arrayidx10129 %add = add nsw i32 %lv1, %lv2130 store i32 %add, ptr %arrayidx6131 %i.next = add nuw nsw i64 %j, 1132 %exitcond = icmp eq i64 %j, 99133 br i1 %exitcond, label %for1.inc17, label %for2134 135for1.inc17:136 %i.next35 = add nuw nsw i64 %i34, 1137 %exitcond38 = icmp eq i64 %i34, 99138 br i1 %exitcond38, label %for.end19, label %for1.header139 140for.end19:141 ret void142}143 144;; Loops should not be interchanged in this case as it is not profitable.145;; for(int i=0;i<100;i++)146;; for(int j=0;j<100;j++)147;; A[i][j] = A[i][j]+k;148 149; CHECK: Name: InterchangeNotProfitable150; CHECK-NEXT: Function: interchange_04151define void @interchange_04(i32 %k) {152entry:153 br label %for.cond1.preheader154 155for.cond1.preheader:156 %indvars.iv21 = phi i64 [ 0, %entry ], [ %indvars.iv.next22, %for.inc10 ]157 br label %for.body3158 159for.body3:160 %indvars.iv = phi i64 [ 0, %for.cond1.preheader ], [ %indvars.iv.next, %for.body3 ]161 %arrayidx5 = getelementptr inbounds [100 x [100 x i32]], ptr @A, i64 0, i64 %indvars.iv21, i64 %indvars.iv162 %0 = load i32, ptr %arrayidx5163 %add = add nsw i32 %0, %k164 store i32 %add, ptr %arrayidx5165 %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1166 %exitcond = icmp eq i64 %indvars.iv.next, 100167 br i1 %exitcond, label %for.inc10, label %for.body3168 169for.inc10:170 %indvars.iv.next22 = add nuw nsw i64 %indvars.iv21, 1171 %exitcond23 = icmp eq i64 %indvars.iv.next22, 100172 br i1 %exitcond23, label %for.end12, label %for.cond1.preheader173 174for.end12:175 ret void176}177 178;;---------------------------------------Test case 05---------------------------------179;; This test is to make sure, that multiple invocations of loop interchange will not180;; undo previous interchange and will converge to a particular order determined by the181;; profitability analysis.182;; for(int i=1;i<100;i++)183;; for(int j=1;j<100;j++)184;; A[j][0] = A[j][0] + B[j][i];185 186; CHECK: Name: Interchanged187; CHECK-NEXT: Function: interchange_05188 189; PROFIT-LABEL: --- !Passed190; PROFIT-NEXT: Pass: loop-interchange191; PROFIT-NEXT: Name: Interchanged192; PROFIT-LABEL: Function: interchange_05193; PROFIT-NEXT: Args:194; PROFIT-NEXT: - String: Loop interchanged with enclosing loop.195; PROFIT-NEXT: ...196; PROFIT: --- !Missed197; PROFIT-NEXT: Pass: loop-interchange198; PROFIT-NEXT: Name: InterchangeNotProfitable199; PROFIT-NEXT: Function: interchange_05200; PROFIT-NEXT: Args:201; PROFIT-NEXT: - String: Interchanging loops is not considered to improve cache locality nor vectorization.202; PROFIT-NEXT: ...203define void @interchange_05() {204entry:205 br label %for2.preheader206 207for2.preheader:208 %i30 = phi i64 [ 1, %entry ], [ %i.next31, %for1.inc14 ]209 br label %for2210 211for2:212 %j = phi i64 [ %i.next, %for2 ], [ 1, %for2.preheader ]213 %j.prev = add nsw i64 %j, -1214 %arrayidx5 = getelementptr inbounds [100 x [100 x i32]], ptr @A, i64 0, i64 %j, i64 0215 %lv1 = load i32, ptr %arrayidx5216 %arrayidx9 = getelementptr inbounds [100 x [100 x i32]], ptr @B, i64 0, i64 %j, i64 %i30217 %lv2 = load i32, ptr %arrayidx9218 %add = add nsw i32 %lv1, %lv2219 %arrayidx13 = getelementptr inbounds [100 x [100 x i32]], ptr @A, i64 0, i64 %j, i64 0220 store i32 %add, ptr %arrayidx13221 %i.next = add nuw nsw i64 %j, 1222 %exitcond = icmp eq i64 %j, 99223 br i1 %exitcond, label %for1.inc14, label %for2224 225for1.inc14:226 %i.next31 = add nuw nsw i64 %i30, 1227 %exitcond33 = icmp eq i64 %i30, 99228 br i1 %exitcond33, label %for.end16, label %for2.preheader229 230for.end16:231 ret void232}233 234