204 lines · plain
1; NOTE: Assertions have been autogenerated by utils/update_test_checks.py2; RUN: opt < %s -passes=loop-interchange -cache-line-size=64 -verify-dom-info -verify-loop-info -verify-scev -verify-loop-lcssa -S | FileCheck %s3; RUN: opt < %s -aa-pipeline=basic-aa -passes=loop-interchange -cache-line-size=64 -verify-dom-info -verify-loop-info -verify-scev -verify-loop-lcssa -S | FileCheck %s4 5target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"6 7@A = common global [100 x [100 x i64]] zeroinitializer8@B = common global [100 x i64] zeroinitializer9 10;; for(int i=0;i<100;i++)11;; for(int j=0;j<100;j++)12;; A[j][i] = A[j][i]+k;13 14define void @interchange_01(i64 %k, i64 %N) {15; CHECK-LABEL: @interchange_01(16; CHECK-NEXT: entry:17; CHECK-NEXT: br label [[FOR2_PREHEADER:%.*]]18; CHECK: for1.header.preheader:19; CHECK-NEXT: br label [[FOR1_HEADER:%.*]]20; CHECK: for1.header:21; CHECK-NEXT: [[J23:%.*]] = phi i64 [ [[J_NEXT24:%.*]], [[FOR1_INC10:%.*]] ], [ 0, [[FOR1_HEADER_PREHEADER:%.*]] ]22; CHECK-NEXT: br label [[FOR2_SPLIT1:%.*]]23; CHECK: for2.preheader:24; CHECK-NEXT: br label [[FOR2:%.*]]25; CHECK: for2:26; CHECK-NEXT: [[J:%.*]] = phi i64 [ [[TMP0:%.*]], [[FOR2_SPLIT:%.*]] ], [ 0, [[FOR2_PREHEADER]] ]27; CHECK-NEXT: br label [[FOR1_HEADER_PREHEADER]]28; CHECK: for2.split1:29; CHECK-NEXT: [[ARRAYIDX5:%.*]] = getelementptr inbounds [100 x [100 x i64]], ptr @A, i64 0, i64 [[J]], i64 [[J23]]30; CHECK-NEXT: [[LV:%.*]] = load i64, ptr [[ARRAYIDX5]]31; CHECK-NEXT: [[ADD:%.*]] = add nsw i64 [[LV]], [[K:%.*]]32; CHECK-NEXT: store i64 [[ADD]], ptr [[ARRAYIDX5]]33; CHECK-NEXT: [[J_NEXT:%.*]] = add nuw nsw i64 [[J]], 134; CHECK-NEXT: [[EXITCOND:%.*]] = icmp eq i64 [[J]], 9935; CHECK-NEXT: br label [[FOR1_INC10]]36; CHECK: for2.split:37; CHECK-NEXT: [[TMP0]] = add nuw nsw i64 [[J]], 138; CHECK-NEXT: [[TMP1:%.*]] = icmp eq i64 [[J]], 9939; CHECK-NEXT: br i1 [[TMP1]], label [[FOR_END12:%.*]], label [[FOR2]]40; CHECK: for1.inc10:41; CHECK-NEXT: [[J_NEXT24]] = add nuw nsw i64 [[J23]], 142; CHECK-NEXT: [[EXITCOND26:%.*]] = icmp eq i64 [[J23]], 9943; CHECK-NEXT: br i1 [[EXITCOND26]], label [[FOR2_SPLIT]], label [[FOR1_HEADER]]44; CHECK: for.end12:45; CHECK-NEXT: ret void46;47entry:48 br label %for1.header49 50for1.header:51 %j23 = phi i64 [ 0, %entry ], [ %j.next24, %for1.inc10 ]52 br label %for253 54for2:55 %j = phi i64 [ %j.next, %for2 ], [ 0, %for1.header ]56 %arrayidx5 = getelementptr inbounds [100 x [100 x i64]], ptr @A, i64 0, i64 %j, i64 %j2357 %lv = load i64, ptr %arrayidx558 %add = add nsw i64 %lv, %k59 store i64 %add, ptr %arrayidx560 %j.next = add nuw nsw i64 %j, 161 %exitcond = icmp eq i64 %j, 9962 br i1 %exitcond, label %for1.inc10, label %for263 64for1.inc10:65 %j.next24 = add nuw nsw i64 %j23, 166 %exitcond26 = icmp eq i64 %j23, 9967 br i1 %exitcond26, label %for.end12, label %for1.header68 69for.end12:70 ret void71}72 73;; for(int i=0;i<100;i++)74;; for(int j=100;j>=0;j--)75;; A[j][i] = A[j][i]+k;76 77define void @interchange_02(i64 %k) {78; CHECK-LABEL: @interchange_02(79; CHECK-NEXT: entry:80; CHECK-NEXT: br label [[FOR3_PREHEADER:%.*]]81; CHECK: for1.header.preheader:82; CHECK-NEXT: br label [[FOR1_HEADER:%.*]]83; CHECK: for1.header:84; CHECK-NEXT: [[J19:%.*]] = phi i64 [ [[J_NEXT20:%.*]], [[FOR1_INC10:%.*]] ], [ 0, [[FOR1_HEADER_PREHEADER:%.*]] ]85; CHECK-NEXT: br label [[FOR3_SPLIT1:%.*]]86; CHECK: for3.preheader:87; CHECK-NEXT: br label [[FOR3:%.*]]88; CHECK: for3:89; CHECK-NEXT: [[J:%.*]] = phi i64 [ [[TMP1:%.*]], [[FOR3_SPLIT:%.*]] ], [ 100, [[FOR3_PREHEADER]] ]90; CHECK-NEXT: br label [[FOR1_HEADER_PREHEADER]]91; CHECK: for3.split1:92; CHECK-NEXT: [[ARRAYIDX5:%.*]] = getelementptr inbounds [100 x [100 x i64]], ptr @A, i64 0, i64 [[J]], i64 [[J19]]93; CHECK-NEXT: [[TMP0:%.*]] = load i64, ptr [[ARRAYIDX5]]94; CHECK-NEXT: [[ADD:%.*]] = add nsw i64 [[TMP0]], [[K:%.*]]95; CHECK-NEXT: store i64 [[ADD]], ptr [[ARRAYIDX5]]96; CHECK-NEXT: [[J_NEXT:%.*]] = add nsw i64 [[J]], -197; CHECK-NEXT: [[CMP2:%.*]] = icmp sgt i64 [[J]], 098; CHECK-NEXT: br label [[FOR1_INC10]]99; CHECK: for3.split:100; CHECK-NEXT: [[TMP1]] = add nsw i64 [[J]], -1101; CHECK-NEXT: [[TMP2:%.*]] = icmp sgt i64 [[J]], 0102; CHECK-NEXT: br i1 [[TMP2]], label [[FOR3]], label [[FOR_END11:%.*]]103; CHECK: for1.inc10:104; CHECK-NEXT: [[J_NEXT20]] = add nuw nsw i64 [[J19]], 1105; CHECK-NEXT: [[EXITCOND:%.*]] = icmp eq i64 [[J_NEXT20]], 100106; CHECK-NEXT: br i1 [[EXITCOND]], label [[FOR3_SPLIT]], label [[FOR1_HEADER]]107; CHECK: for.end11:108; CHECK-NEXT: ret void109;110entry:111 br label %for1.header112 113for1.header:114 %j19 = phi i64 [ 0, %entry ], [ %j.next20, %for1.inc10 ]115 br label %for3116 117for3:118 %j = phi i64 [ 100, %for1.header ], [ %j.next, %for3 ]119 %arrayidx5 = getelementptr inbounds [100 x [100 x i64]], ptr @A, i64 0, i64 %j, i64 %j19120 %0 = load i64, ptr %arrayidx5121 %add = add nsw i64 %0, %k122 store i64 %add, ptr %arrayidx5123 %j.next = add nsw i64 %j, -1124 %cmp2 = icmp sgt i64 %j, 0125 br i1 %cmp2, label %for3, label %for1.inc10126 127for1.inc10:128 %j.next20 = add nuw nsw i64 %j19, 1129 %exitcond = icmp eq i64 %j.next20, 100130 br i1 %exitcond, label %for.end11, label %for1.header131 132for.end11:133 ret void134}135 136;; Test to make sure we can handle output dependencies.137;;138;; for (int i = 1; i < 100; ++i)139;; for(int j = 1; j < 99; ++j) {140;; A[j][i] = i;141;; A[j][i+1] = j;142;; }143;; FIXME: DA misses this case after D35430144 145define void @interchange_10() {146; CHECK-LABEL: @interchange_10(147; CHECK-NEXT: entry:148; CHECK-NEXT: br label [[FOR2_PREHEADER:%.*]]149; CHECK: for1.header.preheader:150; CHECK-NEXT: br label [[FOR1_HEADER:%.*]]151; CHECK: for1.header:152; CHECK-NEXT: [[J23:%.*]] = phi i64 [ [[J_NEXT24:%.*]], [[FOR1_INC10:%.*]] ], [ 1, [[FOR1_HEADER_PREHEADER:%.*]] ]153; CHECK-NEXT: [[J_NEXT24]] = add nuw nsw i64 [[J23]], 1154; CHECK-NEXT: br label [[FOR2_SPLIT1:%.*]]155; CHECK: for2.preheader:156; CHECK-NEXT: br label [[FOR2:%.*]]157; CHECK: for2:158; CHECK-NEXT: [[J:%.*]] = phi i64 [ [[TMP0:%.*]], [[FOR2_SPLIT:%.*]] ], [ 1, [[FOR2_PREHEADER]] ]159; CHECK-NEXT: br label [[FOR1_HEADER_PREHEADER]]160; CHECK: for2.split1:161; CHECK-NEXT: [[J_NEXT:%.*]] = add nuw nsw i64 [[J]], 1162; CHECK-NEXT: [[ARRAYIDX5:%.*]] = getelementptr inbounds [100 x [100 x i64]], ptr @A, i64 0, i64 [[J]], i64 [[J23]]163; CHECK-NEXT: store i64 [[J]], ptr [[ARRAYIDX5]]164; CHECK-NEXT: [[ARRAYIDX10:%.*]] = getelementptr inbounds [100 x [100 x i64]], ptr @A, i64 0, i64 [[J]], i64 [[J_NEXT24]]165; CHECK-NEXT: store i64 [[J23]], ptr [[ARRAYIDX10]]166; CHECK-NEXT: [[EXITCOND:%.*]] = icmp eq i64 [[J]], 99167; CHECK-NEXT: br label [[FOR1_INC10]]168; CHECK: for2.split:169; CHECK-NEXT: [[TMP0]] = add nuw nsw i64 [[J]], 1170; CHECK-NEXT: [[TMP1:%.*]] = icmp eq i64 [[J]], 99171; CHECK-NEXT: br i1 [[TMP1]], label [[FOR_END12:%.*]], label [[FOR2]]172; CHECK: for1.inc10:173; CHECK-NEXT: [[EXITCOND26:%.*]] = icmp eq i64 [[J23]], 98174; CHECK-NEXT: br i1 [[EXITCOND26]], label [[FOR2_SPLIT]], label [[FOR1_HEADER]]175; CHECK: for.end12:176; CHECK-NEXT: ret void177;178entry:179 br label %for1.header180 181for1.header:182 %j23 = phi i64 [ 1, %entry ], [ %j.next24, %for1.inc10 ]183 %j.next24 = add nuw nsw i64 %j23, 1184 br label %for2185 186for2:187 %j = phi i64 [ %j.next, %for2 ], [ 1, %for1.header ]188 %j.next = add nuw nsw i64 %j, 1189 %arrayidx5 = getelementptr inbounds [100 x [100 x i64]], ptr @A, i64 0, i64 %j, i64 %j23190 store i64 %j, ptr %arrayidx5191 %arrayidx10 = getelementptr inbounds [100 x [100 x i64]], ptr @A, i64 0, i64 %j, i64 %j.next24192 store i64 %j23, ptr %arrayidx10193 %exitcond = icmp eq i64 %j, 99194 br i1 %exitcond, label %for1.inc10, label %for2195 196for1.inc10:197 %exitcond26 = icmp eq i64 %j23, 98198 br i1 %exitcond26, label %for.end12, label %for1.header199 200for.end12:201 ret void202 203}204