1; NOTE: Assertions have been autogenerated by utils/update_test_checks.py 2; RUN: opt < %s -basic-aa -loop-interchange -verify-dom-info -verify-loop-info -verify-scev -verify-loop-lcssa -S | FileCheck %s 3; RUN: opt < %s -aa-pipeline=basic-aa -passes=loop-interchange -verify-dom-info -verify-loop-info -verify-scev -verify-loop-lcssa -S | FileCheck %s 4 5target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" 6target triple = "x86_64-unknown-linux-gnu" 7 8@A = common global [100 x [100 x i64]] zeroinitializer 9@B = common global [100 x i64] zeroinitializer 10 11;; for(int i=0;i<100;i++) 12;; for(int j=0;j<100;j++) 13;; A[j][i] = A[j][i]+k; 14 15define void @interchange_01(i64 %k, i64 %N) { 16; CHECK-LABEL: @interchange_01( 17; CHECK-NEXT: entry: 18; CHECK-NEXT: br label [[FOR2_PREHEADER:%.*]] 19; CHECK: for1.header.preheader: 20; CHECK-NEXT: br label [[FOR1_HEADER:%.*]] 21; CHECK: for1.header: 22; CHECK-NEXT: [[J23:%.*]] = phi i64 [ [[J_NEXT24:%.*]], [[FOR1_INC10:%.*]] ], [ 0, [[FOR1_HEADER_PREHEADER:%.*]] ] 23; CHECK-NEXT: br label [[FOR2_SPLIT1:%.*]] 24; CHECK: for2.preheader: 25; CHECK-NEXT: br label [[FOR2:%.*]] 26; CHECK: for2: 27; CHECK-NEXT: [[J:%.*]] = phi i64 [ [[TMP0:%.*]], [[FOR2_SPLIT:%.*]] ], [ 0, [[FOR2_PREHEADER]] ] 28; CHECK-NEXT: br label [[FOR1_HEADER_PREHEADER]] 29; CHECK: for2.split1: 30; CHECK-NEXT: [[ARRAYIDX5:%.*]] = getelementptr inbounds [100 x [100 x i64]], [100 x [100 x i64]]* @A, i64 0, i64 [[J]], i64 [[J23]] 31; CHECK-NEXT: [[LV:%.*]] = load i64, i64* [[ARRAYIDX5]] 32; CHECK-NEXT: [[ADD:%.*]] = add nsw i64 [[LV]], [[K:%.*]] 33; CHECK-NEXT: store i64 [[ADD]], i64* [[ARRAYIDX5]] 34; CHECK-NEXT: [[J_NEXT:%.*]] = add nuw nsw i64 [[J]], 1 35; CHECK-NEXT: [[EXITCOND:%.*]] = icmp eq i64 [[J]], 99 36; CHECK-NEXT: br label [[FOR1_INC10]] 37; CHECK: for2.split: 38; CHECK-NEXT: [[TMP0]] = add nuw nsw i64 [[J]], 1 39; CHECK-NEXT: [[TMP1:%.*]] = icmp eq i64 [[J]], 99 40; CHECK-NEXT: br i1 [[TMP1]], label [[FOR_END12:%.*]], label [[FOR2]] 41; CHECK: for1.inc10: 42; CHECK-NEXT: [[J_NEXT24]] = add nuw nsw i64 [[J23]], 1 43; CHECK-NEXT: [[EXITCOND26:%.*]] = icmp eq i64 [[J23]], 99 44; CHECK-NEXT: br i1 [[EXITCOND26]], label [[FOR2_SPLIT]], label [[FOR1_HEADER]] 45; CHECK: for.end12: 46; CHECK-NEXT: ret void 47; 48entry: 49 br label %for1.header 50 51for1.header: 52 %j23 = phi i64 [ 0, %entry ], [ %j.next24, %for1.inc10 ] 53 br label %for2 54 55for2: 56 %j = phi i64 [ %j.next, %for2 ], [ 0, %for1.header ] 57 %arrayidx5 = getelementptr inbounds [100 x [100 x i64]], [100 x [100 x i64]]* @A, i64 0, i64 %j, i64 %j23 58 %lv = load i64, i64* %arrayidx5 59 %add = add nsw i64 %lv, %k 60 store i64 %add, i64* %arrayidx5 61 %j.next = add nuw nsw i64 %j, 1 62 %exitcond = icmp eq i64 %j, 99 63 br i1 %exitcond, label %for1.inc10, label %for2 64 65for1.inc10: 66 %j.next24 = add nuw nsw i64 %j23, 1 67 %exitcond26 = icmp eq i64 %j23, 99 68 br i1 %exitcond26, label %for.end12, label %for1.header 69 70for.end12: 71 ret void 72} 73 74;; for(int i=0;i<100;i++) 75;; for(int j=100;j>=0;j--) 76;; A[j][i] = A[j][i]+k; 77 78define void @interchange_02(i64 %k) { 79; CHECK-LABEL: @interchange_02( 80; CHECK-NEXT: entry: 81; CHECK-NEXT: br label [[FOR3_PREHEADER:%.*]] 82; CHECK: for1.header.preheader: 83; CHECK-NEXT: br label [[FOR1_HEADER:%.*]] 84; CHECK: for1.header: 85; CHECK-NEXT: [[J19:%.*]] = phi i64 [ [[J_NEXT20:%.*]], [[FOR1_INC10:%.*]] ], [ 0, [[FOR1_HEADER_PREHEADER:%.*]] ] 86; CHECK-NEXT: br label [[FOR3_SPLIT1:%.*]] 87; CHECK: for3.preheader: 88; CHECK-NEXT: br label [[FOR3:%.*]] 89; CHECK: for3: 90; CHECK-NEXT: [[J:%.*]] = phi i64 [ [[TMP1:%.*]], [[FOR3_SPLIT:%.*]] ], [ 100, [[FOR3_PREHEADER]] ] 91; CHECK-NEXT: br label [[FOR1_HEADER_PREHEADER]] 92; CHECK: for3.split1: 93; CHECK-NEXT: [[ARRAYIDX5:%.*]] = getelementptr inbounds [100 x [100 x i64]], [100 x [100 x i64]]* @A, i64 0, i64 [[J]], i64 [[J19]] 94; CHECK-NEXT: [[TMP0:%.*]] = load i64, i64* [[ARRAYIDX5]] 95; CHECK-NEXT: [[ADD:%.*]] = add nsw i64 [[TMP0]], [[K:%.*]] 96; CHECK-NEXT: store i64 [[ADD]], i64* [[ARRAYIDX5]] 97; CHECK-NEXT: [[J_NEXT:%.*]] = add nsw i64 [[J]], -1 98; CHECK-NEXT: [[CMP2:%.*]] = icmp sgt i64 [[J]], 0 99; CHECK-NEXT: br label [[FOR1_INC10]] 100; CHECK: for3.split: 101; CHECK-NEXT: [[TMP1]] = add nsw i64 [[J]], -1 102; CHECK-NEXT: [[TMP2:%.*]] = icmp sgt i64 [[J]], 0 103; CHECK-NEXT: br i1 [[TMP2]], label [[FOR3]], label [[FOR_END11:%.*]] 104; CHECK: for1.inc10: 105; CHECK-NEXT: [[J_NEXT20]] = add nuw nsw i64 [[J19]], 1 106; CHECK-NEXT: [[EXITCOND:%.*]] = icmp eq i64 [[J_NEXT20]], 100 107; CHECK-NEXT: br i1 [[EXITCOND]], label [[FOR3_SPLIT]], label [[FOR1_HEADER]] 108; CHECK: for.end11: 109; CHECK-NEXT: ret void 110; 111entry: 112 br label %for1.header 113 114for1.header: 115 %j19 = phi i64 [ 0, %entry ], [ %j.next20, %for1.inc10 ] 116 br label %for3 117 118for3: 119 %j = phi i64 [ 100, %for1.header ], [ %j.next, %for3 ] 120 %arrayidx5 = getelementptr inbounds [100 x [100 x i64]], [100 x [100 x i64]]* @A, i64 0, i64 %j, i64 %j19 121 %0 = load i64, i64* %arrayidx5 122 %add = add nsw i64 %0, %k 123 store i64 %add, i64* %arrayidx5 124 %j.next = add nsw i64 %j, -1 125 %cmp2 = icmp sgt i64 %j, 0 126 br i1 %cmp2, label %for3, label %for1.inc10 127 128for1.inc10: 129 %j.next20 = add nuw nsw i64 %j19, 1 130 %exitcond = icmp eq i64 %j.next20, 100 131 br i1 %exitcond, label %for.end11, label %for1.header 132 133for.end11: 134 ret void 135} 136 137;; Test to make sure we can handle output dependencies. 138;; 139;; for (int i = 1; i < 100; ++i) 140;; for(int j = 1; j < 99; ++j) { 141;; A[j][i] = i; 142;; A[j][i+1] = j; 143;; } 144;; FIXME: DA misses this case after D35430 145 146define void @interchange_10() { 147; CHECK-LABEL: @interchange_10( 148; CHECK-NEXT: entry: 149; CHECK-NEXT: br label [[FOR1_HEADER:%.*]] 150; CHECK: for1.header: 151; CHECK-NEXT: [[J23:%.*]] = phi i64 [ 1, [[ENTRY:%.*]] ], [ [[J_NEXT24:%.*]], [[FOR1_INC10:%.*]] ] 152; CHECK-NEXT: [[J_NEXT24]] = add nuw nsw i64 [[J23]], 1 153; CHECK-NEXT: br label [[FOR2:%.*]] 154; CHECK: for2: 155; CHECK-NEXT: [[J:%.*]] = phi i64 [ [[J_NEXT:%.*]], [[FOR2]] ], [ 1, [[FOR1_HEADER]] ] 156; CHECK-NEXT: [[J_NEXT]] = add nuw nsw i64 [[J]], 1 157; CHECK-NEXT: [[ARRAYIDX5:%.*]] = getelementptr inbounds [100 x [100 x i64]], [100 x [100 x i64]]* @A, i64 0, i64 [[J]], i64 [[J23]] 158; CHECK-NEXT: store i64 [[J]], i64* [[ARRAYIDX5]] 159; CHECK-NEXT: [[ARRAYIDX10:%.*]] = getelementptr inbounds [100 x [100 x i64]], [100 x [100 x i64]]* @A, i64 0, i64 [[J]], i64 [[J_NEXT24]] 160; CHECK-NEXT: store i64 [[J23]], i64* [[ARRAYIDX10]] 161; CHECK-NEXT: [[EXITCOND:%.*]] = icmp eq i64 [[J]], 99 162; CHECK-NEXT: br i1 [[EXITCOND]], label [[FOR1_INC10]], label [[FOR2]] 163; CHECK: for1.inc10: 164; CHECK-NEXT: [[EXITCOND26:%.*]] = icmp eq i64 [[J23]], 98 165; CHECK-NEXT: br i1 [[EXITCOND26]], label [[FOR_END12:%.*]], label [[FOR1_HEADER]] 166; CHECK: for.end12: 167; CHECK-NEXT: ret void 168; 169entry: 170 br label %for1.header 171 172for1.header: 173 %j23 = phi i64 [ 1, %entry ], [ %j.next24, %for1.inc10 ] 174 %j.next24 = add nuw nsw i64 %j23, 1 175 br label %for2 176 177for2: 178 %j = phi i64 [ %j.next, %for2 ], [ 1, %for1.header ] 179 %j.next = add nuw nsw i64 %j, 1 180 %arrayidx5 = getelementptr inbounds [100 x [100 x i64]], [100 x [100 x i64]]* @A, i64 0, i64 %j, i64 %j23 181 store i64 %j, i64* %arrayidx5 182 %arrayidx10 = getelementptr inbounds [100 x [100 x i64]], [100 x [100 x i64]]* @A, i64 0, i64 %j, i64 %j.next24 183 store i64 %j23, i64* %arrayidx10 184 %exitcond = icmp eq i64 %j, 99 185 br i1 %exitcond, label %for1.inc10, label %for2 186 187for1.inc10: 188 %exitcond26 = icmp eq i64 %j23, 98 189 br i1 %exitcond26, label %for.end12, label %for1.header 190 191for.end12: 192 ret void 193 194} 195