303 lines · plain
1; Test optimization remarks generated by the LoopInterchange pass.2;3; RUN: opt < %s -passes=loop-interchange -cache-line-size=64 -verify-dom-info -verify-loop-info \4; RUN: -pass-remarks-output=%t -pass-remarks-missed='loop-interchange' \5; RUN: -pass-remarks='loop-interchange' -S6; RUN: cat %t | FileCheck %s7 8; RUN: opt < %s -passes=loop-interchange -cache-line-size=64 -verify-dom-info -verify-loop-info \9; RUN: -pass-remarks-output=%t -pass-remarks-missed='loop-interchange' \10; RUN: -pass-remarks='loop-interchange' -S -da-disable-delinearization-checks11; RUN: cat %t | FileCheck --check-prefix=DELIN %s12 13@A = common global [100 x [100 x i32]] zeroinitializer14@B = common global [100 x [100 x i32]] zeroinitializer15@C = common global [100 x i32] zeroinitializer16 17;;---------------------------------------Test case 01---------------------------------18;; Loops interchange is not profitable.19;; for(int i=1;i<N;i++)20;; for(int j=1;j<N;j++)21;; A[i-1][j-1] = A[i - 1][j-1] + B[i][j];22 23define void @test01(i32 %N){24entry:25 %cmp31 = icmp sgt i32 %N, 126 br i1 %cmp31, label %for.cond1.preheader.lr.ph, label %for.end1927 28for.cond1.preheader.lr.ph:29 %0 = add i32 %N, -130 br label %for.body3.lr.ph31 32for.body3.lr.ph:33 %indvars.iv34 = phi i64 [ 1, %for.cond1.preheader.lr.ph ], [ %indvars.iv.next35, %for.inc17 ]34 %1 = add nsw i64 %indvars.iv34, -135 br label %for.body336 37for.body3:38 %indvars.iv = phi i64 [ 1, %for.body3.lr.ph ], [ %indvars.iv.next, %for.body3 ]39 %2 = add nsw i64 %indvars.iv, -140 %arrayidx6 = getelementptr inbounds [100 x [100 x i32]], ptr @A, i64 0, i64 %1, i64 %241 %3 = load i32, ptr %arrayidx642 %arrayidx10 = getelementptr inbounds [100 x [100 x i32]], ptr @B, i64 0, i64 %indvars.iv34, i64 %indvars.iv43 %4 = load i32, ptr %arrayidx1044 %add = add nsw i32 %4, %345 store i32 %add, ptr %arrayidx646 %indvars.iv.next = add nuw nsw i64 %indvars.iv, 147 %lftr.wideiv = trunc i64 %indvars.iv to i3248 %exitcond = icmp eq i32 %lftr.wideiv, %049 br i1 %exitcond, label %for.inc17, label %for.body350 51for.inc17:52 %indvars.iv.next35 = add nuw nsw i64 %indvars.iv34, 153 %lftr.wideiv37 = trunc i64 %indvars.iv34 to i3254 %exitcond38 = icmp eq i32 %lftr.wideiv37, %055 br i1 %exitcond38, label %for.end19, label %for.body3.lr.ph56 57for.end19:58 ret void59}60 61; CHECK: --- !Analysis62; CHECK-NEXT: Pass: loop-interchange63; CHECK-NEXT: Name: Dependence64; CHECK-NEXT: Function: test0165; CHECK-NEXT: Args:66; CHECK-NEXT: - String: Computed dependence info, invoking the transform.67; CHECK-NEXT: ...68 69; CHECK: --- !Missed70; CHECK-NEXT: Pass: loop-interchange71; CHECK-NEXT: Name: Dependence72; CHECK-NEXT: Function: test0173; CHECK-NEXT: Args:74; CHECK-NEXT: - String: All loops have dependencies in all directions.75; CHECK-NEXT: ...76 77; DELIN: --- !Analysis78; DELIN-NEXT: Pass: loop-interchange79; DELIN-NEXT: Name: Dependence80; DELIN-NEXT: Function: test0181; DELIN-NEXT: Args:82; DELIN-NEXT: - String: Computed dependence info, invoking the transform.83; DELIN-NEXT: ...84 85; DELIN: --- !Missed86; DELIN-NEXT: Pass: loop-interchange87; DELIN-NEXT: Name: InterchangeNotProfitable88; DELIN-NEXT: Function: test0189; DELIN-NEXT: Args:90; DELIN-NEXT: - String: Interchanging loops is not considered to improve cache locality nor vectorization.91; DELIN-NEXT: ...92 93;;--------------------------------------Test case 02------------------------------------94;; [FIXME] This loop though valid is currently not interchanged due to the95;; limitation that we cannot split the inner loop latch due to multiple use of inner induction96;; variable.(used to increment the loop counter and to access A[j+1][i+1]97;; for(int i=0;i<N-1;i++)98;; for(int j=1;j<N-1;j++)99;; A[j+1][i+1] = A[j+1][i+1] + k;100 101define void @test02(i32 %k, i32 %N) {102 entry:103 %sub = add nsw i32 %N, -1104 %cmp26 = icmp sgt i32 %N, 1105 br i1 %cmp26, label %for.cond1.preheader.lr.ph, label %for.end17106 107 for.cond1.preheader.lr.ph:108 %cmp324 = icmp sgt i32 %sub, 1109 %0 = add i32 %N, -2110 %1 = sext i32 %sub to i64111 br label %for.cond1.preheader112 113 for.cond.loopexit:114 %cmp = icmp slt i64 %indvars.iv.next29, %1115 br i1 %cmp, label %for.cond1.preheader, label %for.end17116 117 for.cond1.preheader:118 %indvars.iv28 = phi i64 [ 0, %for.cond1.preheader.lr.ph ], [ %indvars.iv.next29, %for.cond.loopexit ]119 %indvars.iv.next29 = add nuw nsw i64 %indvars.iv28, 1120 br i1 %cmp324, label %for.body4, label %for.cond.loopexit121 122 for.body4:123 %indvars.iv = phi i64 [ %indvars.iv.next, %for.body4 ], [ 1, %for.cond1.preheader ]124 %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1125 %arrayidx7 = getelementptr inbounds [100 x [100 x i32]], ptr @A, i64 0, i64 %indvars.iv.next, i64 %indvars.iv.next29126 %2 = load i32, ptr %arrayidx7127 %add8 = add nsw i32 %2, %k128 store i32 %add8, ptr %arrayidx7129 %lftr.wideiv = trunc i64 %indvars.iv to i32130 %exitcond = icmp eq i32 %lftr.wideiv, %0131 br i1 %exitcond, label %for.cond.loopexit, label %for.body4132 133 for.end17:134 ret void135}136 137; CHECK: --- !Analysis138; CHECK-NEXT: Pass: loop-interchange139; CHECK-NEXT: Name: Dependence140; CHECK-NEXT: Function: test02141; CHECK-NEXT: Args:142; CHECK-NEXT: - String: Computed dependence info, invoking the transform.143; CHECK-NEXT: ...144 145; CHECK: --- !Missed146; CHECK-NEXT: Pass: loop-interchange147; CHECK-NEXT: Name: Dependence148; CHECK-NEXT: Function: test02149; CHECK-NEXT: Args:150; CHECK-NEXT: - String: All loops have dependencies in all directions.151; CHECK-NEXT: ...152 153; DELIN: --- !Analysis154; DELIN-NEXT: Pass: loop-interchange155; DELIN-NEXT: Name: Dependence156; DELIN-NEXT: Function: test02157; DELIN-NEXT: Args:158; DELIN-NEXT: - String: Computed dependence info, invoking the transform.159; DELIN-NEXT: ...160 161; DELIN: --- !Passed162; DELIN-NEXT: Pass: loop-interchange163; DELIN-NEXT: Name: Interchanged164; DELIN-NEXT: Function: test02165; DELIN-NEXT: Args:166; DELIN-NEXT: - String: Loop interchanged with enclosing loop.167; DELIN-NEXT: ...168 169;;-----------------------------------Test case 03-------------------------------170;; Test to make sure we can handle output dependencies.171;;172;; for (int i = 0; i < 2; ++i)173;; for(int j = 0; j < 3; ++j) {174;; A[j][i] = i;175;; A[j][i+1] = j;176;; }177 178@A10 = local_unnamed_addr global [3 x [3 x i32]] zeroinitializer, align 16179 180define void @test03() {181entry:182 br label %for.cond1.preheader183 184for.cond.loopexit: ; preds = %for.body4185 %exitcond28 = icmp ne i64 %indvars.iv.next27, 2186 br i1 %exitcond28, label %for.cond1.preheader, label %for.cond.cleanup187 188for.cond1.preheader: ; preds = %for.cond.loopexit, %entry189 %indvars.iv26 = phi i64 [ 0, %entry ], [ %indvars.iv.next27, %for.cond.loopexit ]190 %indvars.iv.next27 = add nuw nsw i64 %indvars.iv26, 1191 br label %for.body4192 193for.cond.cleanup: ; preds = %for.cond.loopexit194 ret void195 196for.body4: ; preds = %for.body4, %for.cond1.preheader197 %indvars.iv = phi i64 [ 0, %for.cond1.preheader ], [ %indvars.iv.next, %for.body4 ]198 %arrayidx6 = getelementptr inbounds [3 x [3 x i32]], ptr @A10, i64 0, i64 %indvars.iv, i64 %indvars.iv26199 %tmp = trunc i64 %indvars.iv26 to i32200 store i32 %tmp, ptr %arrayidx6, align 4201 %arrayidx10 = getelementptr inbounds [3 x [3 x i32]], ptr @A10, i64 0, i64 %indvars.iv, i64 %indvars.iv.next27202 %tmp1 = trunc i64 %indvars.iv to i32203 store i32 %tmp1, ptr %arrayidx10, align 4204 %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1205 %exitcond = icmp ne i64 %indvars.iv.next, 3206 br i1 %exitcond, label %for.body4, label %for.cond.loopexit207}208 209; CHECK: --- !Analysis210; CHECK-NEXT: Pass: loop-interchange211; CHECK-NEXT: Name: Dependence212; CHECK-NEXT: Function: test03213; CHECK-NEXT: Args:214; CHECK-NEXT: - String: Computed dependence info, invoking the transform.215; CHECK-NEXT: ...216 217; CHECK: --- !Passed218; CHECK-NEXT: Pass: loop-interchange219; CHECK-NEXT: Name: Interchanged220; CHECK-NEXT: Function: test03221; CHECK-NEXT: Args:222; CHECK-NEXT: - String: Loop interchanged with enclosing loop.223; CHECK-NEXT: ...224 225; DELIN: --- !Analysis226; DELIN-NEXT: Pass: loop-interchange227; DELIN-NEXT: Name: Dependence228; DELIN-NEXT: Function: test03229; DELIN-NEXT: Args:230; DELIN-NEXT: - String: Computed dependence info, invoking the transform.231; DELIN-NEXT: ...232 233; DELIN: --- !Passed234; DELIN-NEXT: Pass: loop-interchange235; DELIN-NEXT: Name: Interchanged236; DELIN-NEXT: Function: test03237; DELIN-NEXT: Args:238; DELIN-NEXT: - String: Loop interchanged with enclosing loop.239; DELIN-NEXT: ...240 241;;--------------------------------------Test case 04-------------------------------------242;; Loops not tightly nested are not interchanged243;; for(int j=0;j<N;j++) {244;; B[j] = j+k;245;; for(int i=0;i<N;i++)246;; A[j][i] = A[j][i]+B[j];247;; }248 249define void @test04(i32 %k, i32 %N){250entry:251 %cmp30 = icmp sgt i32 %N, 0252 br i1 %cmp30, label %for.body.lr.ph, label %for.end17253 254for.body.lr.ph:255 %0 = add i32 %N, -1256 %1 = zext i32 %k to i64257 br label %for.body258 259for.body:260 %indvars.iv32 = phi i64 [ 0, %for.body.lr.ph ], [ %indvars.iv.next33, %for.inc15 ]261 %2 = add nsw i64 %indvars.iv32, %1262 %arrayidx = getelementptr inbounds [100 x i32], ptr @C, i64 0, i64 %indvars.iv32263 %3 = trunc i64 %2 to i32264 store i32 %3, ptr %arrayidx265 br label %for.body3266 267for.body3:268 %indvars.iv = phi i64 [ 0, %for.body ], [ %indvars.iv.next, %for.body3 ]269 %arrayidx7 = getelementptr inbounds [100 x [100 x i32]], ptr @A, i64 0, i64 %indvars.iv32, i64 %indvars.iv270 %4 = load i32, ptr %arrayidx7271 %add10 = add nsw i32 %3, %4272 store i32 %add10, ptr %arrayidx7273 %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1274 %lftr.wideiv = trunc i64 %indvars.iv to i32275 %exitcond = icmp eq i32 %lftr.wideiv, %0276 br i1 %exitcond, label %for.inc15, label %for.body3277 278for.inc15:279 %indvars.iv.next33 = add nuw nsw i64 %indvars.iv32, 1280 %lftr.wideiv35 = trunc i64 %indvars.iv32 to i32281 %exitcond36 = icmp eq i32 %lftr.wideiv35, %0282 br i1 %exitcond36, label %for.end17, label %for.body283 284for.end17:285 ret void286}287 288; CHECK: --- !Missed289; CHECK-NEXT: Pass: loop-interchange290; CHECK-NEXT: Name: Dependence291; CHECK-NEXT: Function: test04292; CHECK-NEXT: Args:293; CHECK-NEXT: - String: All loops have dependencies in all directions.294; CHECK-NEXT: ...295 296; DELIN: --- !Missed297; DELIN-NEXT: Pass: loop-interchange298; DELIN-NEXT: Name: NotTightlyNested299; DELIN-NEXT: Function: test04300; DELIN-NEXT: Args:301; DELIN-NEXT: - String: Cannot interchange loops because they are not tightly nested.302; DELIN-NEXT: ...303