1; NOTE: Assertions have been autogenerated by utils/update_test_checks.py 2; RUN: opt < %s -basicaa -loop-interchange -verify-dom-info -verify-loop-info -S | FileCheck %s 3 4target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" 5target triple = "x86_64-unknown-linux-gnu" 6 7@A = common global [100 x [100 x i64]] zeroinitializer 8@B = common global [100 x i64] zeroinitializer 9 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: [[INDVARS_IV23:%.*]] = phi i64 [ [[INDVARS_IV_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: [[INDVARS_IV:%.*]] = phi i64 [ [[INDVARS_IV_NEXT:%.*]], [[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]], [100 x [100 x i64]]* @A, i64 0, i64 [[INDVARS_IV]], i64 [[INDVARS_IV23]] 30; CHECK-NEXT: [[LV:%.*]] = load i64, i64* [[ARRAYIDX5]] 31; CHECK-NEXT: [[ADD:%.*]] = add nsw i64 [[LV]], [[K:%.*]] 32; CHECK-NEXT: store i64 [[ADD]], i64* [[ARRAYIDX5]] 33; CHECK-NEXT: br label [[FOR1_INC10]] 34; CHECK: for2.split: 35; CHECK-NEXT: [[INDVARS_IV_NEXT]] = add nuw nsw i64 [[INDVARS_IV]], 1 36; CHECK-NEXT: [[EXITCOND:%.*]] = icmp eq i64 [[INDVARS_IV]], 99 37; CHECK-NEXT: br i1 [[EXITCOND]], label [[FOR_END12:%.*]], label [[FOR2]] 38; CHECK: for1.inc10: 39; CHECK-NEXT: [[INDVARS_IV_NEXT24]] = add nuw nsw i64 [[INDVARS_IV23]], 1 40; CHECK-NEXT: [[EXITCOND26:%.*]] = icmp eq i64 [[INDVARS_IV23]], 99 41; CHECK-NEXT: br i1 [[EXITCOND26]], label [[FOR2_SPLIT]], label [[FOR1_HEADER]] 42; CHECK: for.end12: 43; CHECK-NEXT: ret void 44; 45entry: 46 br label %for1.header 47 48for1.header: 49 %j23 = phi i64 [ 0, %entry ], [ %j.next24, %for1.inc10 ] 50 br label %for2 51 52for2: 53 %j = phi i64 [ %j.next, %for2 ], [ 0, %for1.header ] 54 %arrayidx5 = getelementptr inbounds [100 x [100 x i64]], [100 x [100 x i64]]* @A, i64 0, i64 %j, i64 %j23 55 %lv = load i64, i64* %arrayidx5 56 %add = add nsw i64 %lv, %k 57 store i64 %add, i64* %arrayidx5 58 %j.next = add nuw nsw i64 %j, 1 59 %exitcond = icmp eq i64 %j, 99 60 br i1 %exitcond, label %for1.inc10, label %for2 61 62for1.inc10: 63 %j.next24 = add nuw nsw i64 %j23, 1 64 %exitcond26 = icmp eq i64 %j23, 99 65 br i1 %exitcond26, label %for.end12, label %for1.header 66 67for.end12: 68 ret void 69} 70 71;; for(int i=0;i<100;i++) 72;; for(int j=100;j>=0;j--) 73;; A[j][i] = A[j][i]+k; 74 75define void @interchange_02(i64 %k) { 76; CHECK-LABEL: @interchange_02( 77; CHECK-NEXT: entry: 78; CHECK-NEXT: br label [[FOR3_PREHEADER:%.*]] 79; CHECK: for1.header.preheader: 80; CHECK-NEXT: br label [[FOR1_HEADER:%.*]] 81; CHECK: for1.header: 82; CHECK-NEXT: [[INDVARS_IV19:%.*]] = phi i64 [ [[INDVARS_IV_NEXT20:%.*]], [[FOR1_INC10:%.*]] ], [ 0, [[FOR1_HEADER_PREHEADER:%.*]] ] 83; CHECK-NEXT: br label [[FOR3_SPLIT1:%.*]] 84; CHECK: for3.preheader: 85; CHECK-NEXT: br label [[FOR3:%.*]] 86; CHECK: for3: 87; CHECK-NEXT: [[INDVARS_IV:%.*]] = phi i64 [ [[INDVARS_IV_NEXT:%.*]], [[FOR3_SPLIT:%.*]] ], [ 100, [[FOR3_PREHEADER]] ] 88; CHECK-NEXT: br label [[FOR1_HEADER_PREHEADER]] 89; CHECK: for3.split1: 90; CHECK-NEXT: [[ARRAYIDX5:%.*]] = getelementptr inbounds [100 x [100 x i64]], [100 x [100 x i64]]* @A, i64 0, i64 [[INDVARS_IV]], i64 [[INDVARS_IV19]] 91; CHECK-NEXT: [[TMP0:%.*]] = load i64, i64* [[ARRAYIDX5]] 92; CHECK-NEXT: [[ADD:%.*]] = add nsw i64 [[TMP0]], [[K:%.*]] 93; CHECK-NEXT: store i64 [[ADD]], i64* [[ARRAYIDX5]] 94; CHECK-NEXT: br label [[FOR1_INC10]] 95; CHECK: for3.split: 96; CHECK-NEXT: [[INDVARS_IV_NEXT]] = add nsw i64 [[INDVARS_IV]], -1 97; CHECK-NEXT: [[CMP2:%.*]] = icmp sgt i64 [[INDVARS_IV]], 0 98; CHECK-NEXT: br i1 [[CMP2]], label [[FOR3]], label [[FOR_END11:%.*]] 99; CHECK: for1.inc10: 100; CHECK-NEXT: [[INDVARS_IV_NEXT20]] = add nuw nsw i64 [[INDVARS_IV19]], 1 101; CHECK-NEXT: [[EXITCOND:%.*]] = icmp eq i64 [[INDVARS_IV_NEXT20]], 100 102; CHECK-NEXT: br i1 [[EXITCOND]], label [[FOR3_SPLIT]], label [[FOR1_HEADER]] 103; CHECK: for.end11: 104; CHECK-NEXT: ret void 105; 106entry: 107 br label %for1.header 108 109for1.header: 110 %j19 = phi i64 [ 0, %entry ], [ %j.next20, %for1.inc10 ] 111 br label %for3 112 113for3: 114 %j = phi i64 [ 100, %for1.header ], [ %j.next, %for3 ] 115 %arrayidx5 = getelementptr inbounds [100 x [100 x i64]], [100 x [100 x i64]]* @A, i64 0, i64 %j, i64 %j19 116 %0 = load i64, i64* %arrayidx5 117 %add = add nsw i64 %0, %k 118 store i64 %add, i64* %arrayidx5 119 %j.next = add nsw i64 %j, -1 120 %cmp2 = icmp sgt i64 %j, 0 121 br i1 %cmp2, label %for3, label %for1.inc10 122 123for1.inc10: 124 %j.next20 = add nuw nsw i64 %j19, 1 125 %exitcond = icmp eq i64 %j.next20, 100 126 br i1 %exitcond, label %for.end11, label %for1.header 127 128for.end11: 129 ret void 130} 131 132;; Test to make sure we can handle output dependencies. 133;; 134;; for (int i = 1; i < 100; ++i) 135;; for(int j = 1; j < 99; ++j) { 136;; A[j][i] = i; 137;; A[j][i+1] = j; 138;; } 139;; FIXME: DA misses this case after D35430 140 141define void @interchange_10() { 142entry: 143 br label %for1.header 144 145for1.header: 146 %j23 = phi i64 [ 1, %entry ], [ %j.next24, %for1.inc10 ] 147 %j.next24 = add nuw nsw i64 %j23, 1 148 br label %for2 149 150for2: 151 %j = phi i64 [ %j.next, %for2 ], [ 1, %for1.header ] 152 %j.next = add nuw nsw i64 %j, 1 153 %arrayidx5 = getelementptr inbounds [100 x [100 x i64]], [100 x [100 x i64]]* @A, i64 0, i64 %j, i64 %j23 154 store i64 %j, i64* %arrayidx5 155 %arrayidx10 = getelementptr inbounds [100 x [100 x i64]], [100 x [100 x i64]]* @A, i64 0, i64 %j, i64 %j.next24 156 store i64 %j23, i64* %arrayidx10 157 %exitcond = icmp eq i64 %j, 99 158 br i1 %exitcond, label %for1.inc10, label %for2 159 160for1.inc10: 161 %exitcond26 = icmp eq i64 %j23, 98 162 br i1 %exitcond26, label %for.end12, label %for1.header 163 164for.end12: 165 ret void 166 167} 168