1; RUN: opt < %s -basicaa -loop-interchange -S | FileCheck %s 2;; We test the complete .ll for adjustment in outer loop header/latch and inner loop header/latch. 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 i32]] zeroinitializer 8@B = common global [100 x i32] zeroinitializer 9@C = common global [100 x [100 x i32]] zeroinitializer 10@D = common global [100 x [100 x [100 x i32]]] zeroinitializer 11 12declare void @foo(...) 13 14;;--------------------------------------Test case 01------------------------------------ 15;; for(int i=0;i<N;i++) 16;; for(int j=1;j<N;j++) 17;; A[j][i] = A[j][i]+k; 18 19define void @interchange_01(i32 %k, i32 %N) { 20entry: 21 %cmp21 = icmp sgt i32 %N, 0 22 br i1 %cmp21, label %for.cond1.preheader.lr.ph, label %for.end12 23 24for.cond1.preheader.lr.ph: 25 %cmp219 = icmp sgt i32 %N, 1 26 %0 = add i32 %N, -1 27 br label %for.cond1.preheader 28 29for.cond1.preheader: 30 %indvars.iv23 = phi i64 [ 0, %for.cond1.preheader.lr.ph ], [ %indvars.iv.next24, %for.inc10 ] 31 br i1 %cmp219, label %for.body3, label %for.inc10 32 33for.body3: 34 %indvars.iv = phi i64 [ %indvars.iv.next, %for.body3 ], [ 1, %for.cond1.preheader ] 35 %arrayidx5 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @A, i64 0, i64 %indvars.iv, i64 %indvars.iv23 36 %1 = load i32, i32* %arrayidx5 37 %add = add nsw i32 %1, %k 38 store i32 %add, i32* %arrayidx5 39 %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1 40 %lftr.wideiv = trunc i64 %indvars.iv to i32 41 %exitcond = icmp eq i32 %lftr.wideiv, %0 42 br i1 %exitcond, label %for.inc10, label %for.body3 43 44for.inc10: 45 %indvars.iv.next24 = add nuw nsw i64 %indvars.iv23, 1 46 %lftr.wideiv25 = trunc i64 %indvars.iv23 to i32 47 %exitcond26 = icmp eq i32 %lftr.wideiv25, %0 48 br i1 %exitcond26, label %for.end12, label %for.cond1.preheader 49 50for.end12: 51 ret void 52} 53 54; CHECK-LABEL: @interchange_01 55; CHECK: entry: 56; CHECK: %cmp21 = icmp sgt i32 %N, 0 57; CHECK: br i1 %cmp21, label %for.body3.preheader, label %for.end12 58; CHECK: for.cond1.preheader.lr.ph: 59; CHECK: br label %for.cond1.preheader 60; CHECK: for.cond1.preheader: 61; CHECK: %indvars.iv23 = phi i64 [ 0, %for.cond1.preheader.lr.ph ], [ %indvars.iv.next24, %for.inc10 ] 62; CHECK: br i1 %cmp219, label %for.body3.split1, label %for.end12.loopexit 63; CHECK: for.body3.preheader: 64; CHECK: %cmp219 = icmp sgt i32 %N, 1 65; CHECK: %0 = add i32 %N, -1 66; CHECK: br label %for.body3 67; CHECK: for.body3: 68; CHECK: %indvars.iv = phi i64 [ %indvars.iv.next, %for.body3.split ], [ 1, %for.body3.preheader ] 69; CHECK: br label %for.cond1.preheader.lr.ph 70; CHECK: for.body3.split1: 71; CHECK: %arrayidx5 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @A, i64 0, i64 %indvars.iv, i64 %indvars.iv23 72; CHECK: %1 = load i32, i32* %arrayidx5 73; CHECK: %add = add nsw i32 %1, %k 74; CHECK: store i32 %add, i32* %arrayidx5 75; CHECK: br label %for.inc10.loopexit 76; CHECK: for.body3.split: 77; CHECK: %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1 78; CHECK: %lftr.wideiv = trunc i64 %indvars.iv to i32 79; CHECK: %exitcond = icmp eq i32 %lftr.wideiv, %0 80; CHECK: br i1 %exitcond, label %for.end12.loopexit, label %for.body3 81; CHECK: for.inc10.loopexit: 82; CHECK: br label %for.inc10 83; CHECK: for.inc10: 84; CHECK: %indvars.iv.next24 = add nuw nsw i64 %indvars.iv23, 1 85; CHECK: %lftr.wideiv25 = trunc i64 %indvars.iv23 to i32 86; CHECK: %exitcond26 = icmp eq i32 %lftr.wideiv25, %0 87; CHECK: br i1 %exitcond26, label %for.body3.split, label %for.cond1.preheader 88; CHECK: for.end12.loopexit: 89; CHECK: br label %for.end12 90; CHECK: for.end12: 91; CHECK: ret void 92 93;;--------------------------------------Test case 02------------------------------------- 94 95;; for(int i=0;i<100;i++) 96;; for(int j=100;j>=0;j--) 97;; A[j][i] = A[j][i]+k; 98 99define void @interchange_02(i32 %k) { 100entry: 101 br label %for.cond1.preheader 102 103for.cond1.preheader: 104 %indvars.iv19 = phi i64 [ 0, %entry ], [ %indvars.iv.next20, %for.inc10 ] 105 br label %for.body3 106 107for.body3: 108 %indvars.iv = phi i64 [ 100, %for.cond1.preheader ], [ %indvars.iv.next, %for.body3 ] 109 %arrayidx5 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @A, i64 0, i64 %indvars.iv, i64 %indvars.iv19 110 %0 = load i32, i32* %arrayidx5 111 %add = add nsw i32 %0, %k 112 store i32 %add, i32* %arrayidx5 113 %indvars.iv.next = add nsw i64 %indvars.iv, -1 114 %cmp2 = icmp sgt i64 %indvars.iv, 0 115 br i1 %cmp2, label %for.body3, label %for.inc10 116 117for.inc10: 118 %indvars.iv.next20 = add nuw nsw i64 %indvars.iv19, 1 119 %exitcond = icmp eq i64 %indvars.iv.next20, 100 120 br i1 %exitcond, label %for.end11, label %for.cond1.preheader 121 122for.end11: 123 ret void 124} 125 126; CHECK-LABEL: @interchange_02 127; CHECK: entry: 128; CHECK: br label %for.body3.preheader 129; CHECK: for.cond1.preheader.preheader: 130; CHECK: br label %for.cond1.preheader 131; CHECK: for.cond1.preheader: 132; CHECK: %indvars.iv19 = phi i64 [ %indvars.iv.next20, %for.inc10 ], [ 0, %for.cond1.preheader.preheader ] 133; CHECK: br label %for.body3.split1 134; CHECK: for.body3.preheader: 135; CHECK: br label %for.body3 136; CHECK: for.body3: 137; CHECK: %indvars.iv = phi i64 [ %indvars.iv.next, %for.body3.split ], [ 100, %for.body3.preheader ] 138; CHECK: br label %for.cond1.preheader.preheader 139; CHECK: for.body3.split1: ; preds = %for.cond1.preheader 140; CHECK: %arrayidx5 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @A, i64 0, i64 %indvars.iv, i64 %indvars.iv19 141; CHECK: %0 = load i32, i32* %arrayidx5 142; CHECK: %add = add nsw i32 %0, %k 143; CHECK: store i32 %add, i32* %arrayidx5 144; CHECK: br label %for.inc10 145; CHECK: for.body3.split: 146; CHECK: %indvars.iv.next = add nsw i64 %indvars.iv, -1 147; CHECK: %cmp2 = icmp sgt i64 %indvars.iv, 0 148; CHECK: br i1 %cmp2, label %for.body3, label %for.end11 149; CHECK: for.inc10: 150; CHECK: %indvars.iv.next20 = add nuw nsw i64 %indvars.iv19, 1 151; CHECK: %exitcond = icmp eq i64 %indvars.iv.next20, 100 152; CHECK: br i1 %exitcond, label %for.body3.split, label %for.cond1.preheader 153; CHECK: for.end11: 154; CHECK: ret void 155 156;;--------------------------------------Test case 03------------------------------------- 157;; Loops should not be interchanged in this case as it is not profitable. 158;; for(int i=0;i<100;i++) 159;; for(int j=0;j<100;j++) 160;; A[i][j] = A[i][j]+k; 161 162define void @interchange_03(i32 %k) { 163entry: 164 br label %for.cond1.preheader 165 166for.cond1.preheader: 167 %indvars.iv21 = phi i64 [ 0, %entry ], [ %indvars.iv.next22, %for.inc10 ] 168 br label %for.body3 169 170for.body3: 171 %indvars.iv = phi i64 [ 0, %for.cond1.preheader ], [ %indvars.iv.next, %for.body3 ] 172 %arrayidx5 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @A, i64 0, i64 %indvars.iv21, i64 %indvars.iv 173 %0 = load i32, i32* %arrayidx5 174 %add = add nsw i32 %0, %k 175 store i32 %add, i32* %arrayidx5 176 %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1 177 %exitcond = icmp eq i64 %indvars.iv.next, 100 178 br i1 %exitcond, label %for.inc10, label %for.body3 179 180for.inc10: 181 %indvars.iv.next22 = add nuw nsw i64 %indvars.iv21, 1 182 %exitcond23 = icmp eq i64 %indvars.iv.next22, 100 183 br i1 %exitcond23, label %for.end12, label %for.cond1.preheader 184 185for.end12: 186 ret void 187} 188 189; CHECK-LABEL: @interchange_03 190; CHECK: entry: 191; CHECK: br label %for.cond1.preheader.preheader 192; CHECK: for.cond1.preheader.preheader: ; preds = %entry 193; CHECK: br label %for.cond1.preheader 194; CHECK: for.cond1.preheader: ; preds = %for.cond1.preheader.preheader, %for.inc10 195; CHECK: %indvars.iv21 = phi i64 [ %indvars.iv.next22, %for.inc10 ], [ 0, %for.cond1.preheader.preheader ] 196; CHECK: br label %for.body3.preheader 197; CHECK: for.body3.preheader: ; preds = %for.cond1.preheader 198; CHECK: br label %for.body3 199; CHECK: for.body3: ; preds = %for.body3.preheader, %for.body3 200; CHECK: %indvars.iv = phi i64 [ %indvars.iv.next, %for.body3 ], [ 0, %for.body3.preheader ] 201; CHECK: %arrayidx5 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @A, i64 0, i64 %indvars.iv21, i64 %indvars.iv 202; CHECK: %0 = load i32, i32* %arrayidx5 203; CHECK: %add = add nsw i32 %0, %k 204; CHECK: store i32 %add, i32* %arrayidx5 205; CHECK: %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1 206; CHECK: %exitcond = icmp eq i64 %indvars.iv.next, 100 207; CHECK: br i1 %exitcond, label %for.inc10, label %for.body3 208; CHECK: for.inc10: ; preds = %for.body3 209; CHECK: %indvars.iv.next22 = add nuw nsw i64 %indvars.iv21, 1 210; CHECK: %exitcond23 = icmp eq i64 %indvars.iv.next22, 100 211; CHECK: br i1 %exitcond23, label %for.end12, label %for.cond1.preheader 212; CHECK: for.end12: ; preds = %for.inc10 213; CHECK: ret void 214 215 216;;--------------------------------------Test case 04------------------------------------- 217;; Loops should not be interchanged in this case as it is not legal due to dependency. 218;; for(int j=0;j<99;j++) 219;; for(int i=0;i<99;i++) 220;; A[j][i+1] = A[j+1][i]+k; 221 222define void @interchange_04(i32 %k){ 223entry: 224 br label %for.cond1.preheader 225 226for.cond1.preheader: 227 %indvars.iv23 = phi i64 [ 0, %entry ], [ %indvars.iv.next24, %for.inc12 ] 228 %indvars.iv.next24 = add nuw nsw i64 %indvars.iv23, 1 229 br label %for.body3 230 231for.body3: 232 %indvars.iv = phi i64 [ 0, %for.cond1.preheader ], [ %indvars.iv.next, %for.body3 ] 233 %arrayidx5 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @A, i64 0, i64 %indvars.iv.next24, i64 %indvars.iv 234 %0 = load i32, i32* %arrayidx5 235 %add6 = add nsw i32 %0, %k 236 %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1 237 %arrayidx11 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @A, i64 0, i64 %indvars.iv23, i64 %indvars.iv.next 238 store i32 %add6, i32* %arrayidx11 239 %exitcond = icmp eq i64 %indvars.iv.next, 99 240 br i1 %exitcond, label %for.inc12, label %for.body3 241 242for.inc12: 243 %exitcond25 = icmp eq i64 %indvars.iv.next24, 99 244 br i1 %exitcond25, label %for.end14, label %for.cond1.preheader 245 246for.end14: 247 ret void 248} 249 250; CHECK-LABEL: @interchange_04 251; CHECK: entry: 252; CHECK: br label %for.cond1.preheader 253; CHECK: for.cond1.preheader: ; preds = %for.inc12, %entry 254; CHECK: %indvars.iv23 = phi i64 [ 0, %entry ], [ %indvars.iv.next24, %for.inc12 ] 255; CHECK: %indvars.iv.next24 = add nuw nsw i64 %indvars.iv23, 1 256; CHECK: br label %for.body3 257; CHECK: for.body3: ; preds = %for.body3, %for.cond1.preheader 258; CHECK: %indvars.iv = phi i64 [ 0, %for.cond1.preheader ], [ %indvars.iv.next, %for.body3 ] 259; CHECK: %arrayidx5 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @A, i64 0, i64 %indvars.iv.next24, i64 %indvars.iv 260; CHECK: %0 = load i32, i32* %arrayidx5 261; CHECK: %add6 = add nsw i32 %0, %k 262; CHECK: %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1 263; CHECK: %arrayidx11 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @A, i64 0, i64 %indvars.iv23, i64 %indvars.iv.next 264; CHECK: store i32 %add6, i32* %arrayidx11 265; CHECK: %exitcond = icmp eq i64 %indvars.iv.next, 99 266; CHECK: br i1 %exitcond, label %for.inc12, label %for.body3 267; CHECK: for.inc12: ; preds = %for.body3 268; CHECK: %exitcond25 = icmp eq i64 %indvars.iv.next24, 99 269; CHECK: br i1 %exitcond25, label %for.end14, label %for.cond1.preheader 270; CHECK: for.end14: ; preds = %for.inc12 271; CHECK: ret void 272 273 274 275;;--------------------------------------Test case 05------------------------------------- 276;; Loops not tightly nested are not interchanged 277;; for(int j=0;j<N;j++) { 278;; B[j] = j+k; 279;; for(int i=0;i<N;i++) 280;; A[j][i] = A[j][i]+B[j]; 281;; } 282 283define void @interchange_05(i32 %k, i32 %N){ 284entry: 285 %cmp30 = icmp sgt i32 %N, 0 286 br i1 %cmp30, label %for.body.lr.ph, label %for.end17 287 288for.body.lr.ph: 289 %0 = add i32 %N, -1 290 %1 = zext i32 %k to i64 291 br label %for.body 292 293for.body: 294 %indvars.iv32 = phi i64 [ 0, %for.body.lr.ph ], [ %indvars.iv.next33, %for.inc15 ] 295 %2 = add nsw i64 %indvars.iv32, %1 296 %arrayidx = getelementptr inbounds [100 x i32], [100 x i32]* @B, i64 0, i64 %indvars.iv32 297 %3 = trunc i64 %2 to i32 298 store i32 %3, i32* %arrayidx 299 br label %for.body3 300 301for.body3: 302 %indvars.iv = phi i64 [ 0, %for.body ], [ %indvars.iv.next, %for.body3 ] 303 %arrayidx7 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @A, i64 0, i64 %indvars.iv32, i64 %indvars.iv 304 %4 = load i32, i32* %arrayidx7 305 %add10 = add nsw i32 %3, %4 306 store i32 %add10, i32* %arrayidx7 307 %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1 308 %lftr.wideiv = trunc i64 %indvars.iv to i32 309 %exitcond = icmp eq i32 %lftr.wideiv, %0 310 br i1 %exitcond, label %for.inc15, label %for.body3 311 312for.inc15: 313 %indvars.iv.next33 = add nuw nsw i64 %indvars.iv32, 1 314 %lftr.wideiv35 = trunc i64 %indvars.iv32 to i32 315 %exitcond36 = icmp eq i32 %lftr.wideiv35, %0 316 br i1 %exitcond36, label %for.end17, label %for.body 317 318for.end17: 319 ret void 320} 321 322; CHECK-LABEL: @interchange_05 323; CHECK: entry: 324; CHECK: %cmp30 = icmp sgt i32 %N, 0 325; CHECK: br i1 %cmp30, label %for.body.lr.ph, label %for.end17 326; CHECK: for.body.lr.ph: 327; CHECK: %0 = add i32 %N, -1 328; CHECK: %1 = zext i32 %k to i64 329; CHECK: br label %for.body 330; CHECK: for.body: 331; CHECK: %indvars.iv32 = phi i64 [ 0, %for.body.lr.ph ], [ %indvars.iv.next33, %for.inc15 ] 332; CHECK: %2 = add nsw i64 %indvars.iv32, %1 333; CHECK: %arrayidx = getelementptr inbounds [100 x i32], [100 x i32]* @B, i64 0, i64 %indvars.iv32 334; CHECK: %3 = trunc i64 %2 to i32 335; CHECK: store i32 %3, i32* %arrayidx 336; CHECK: br label %for.body3.preheader 337; CHECK: for.body3.preheader: 338; CHECK: br label %for.body3 339; CHECK: for.body3: 340; CHECK: %indvars.iv = phi i64 [ %indvars.iv.next, %for.body3 ], [ 0, %for.body3.preheader ] 341; CHECK: %arrayidx7 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @A, i64 0, i64 %indvars.iv32, i64 %indvars.iv 342; CHECK: %4 = load i32, i32* %arrayidx7 343; CHECK: %add10 = add nsw i32 %3, %4 344; CHECK: store i32 %add10, i32* %arrayidx7 345; CHECK: %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1 346; CHECK: %lftr.wideiv = trunc i64 %indvars.iv to i32 347; CHECK: %exitcond = icmp eq i32 %lftr.wideiv, %0 348; CHECK: br i1 %exitcond, label %for.inc15, label %for.body3 349; CHECK: for.inc15: 350; CHECK: %indvars.iv.next33 = add nuw nsw i64 %indvars.iv32, 1 351; CHECK: %lftr.wideiv35 = trunc i64 %indvars.iv32 to i32 352; CHECK: %exitcond36 = icmp eq i32 %lftr.wideiv35, %0 353; CHECK: br i1 %exitcond36, label %for.end17.loopexit, label %for.body 354; CHECK: for.end17.loopexit: 355; CHECK: br label %for.end17 356; CHECK: for.end17: 357; CHECK: ret void 358 359 360;;--------------------------------------Test case 06------------------------------------- 361;; Loops not tightly nested are not interchanged 362;; for(int j=0;j<N;j++) { 363;; foo(); 364;; for(int i=2;i<N;i++) 365;; A[j][i] = A[j][i]+k; 366;; } 367 368define void @interchange_06(i32 %k, i32 %N) { 369entry: 370 %cmp22 = icmp sgt i32 %N, 0 371 br i1 %cmp22, label %for.body.lr.ph, label %for.end12 372 373for.body.lr.ph: 374 %0 = add i32 %N, -1 375 br label %for.body 376 377for.body: 378 %indvars.iv24 = phi i64 [ 0, %for.body.lr.ph ], [ %indvars.iv.next25, %for.inc10 ] 379 tail call void (...) @foo() 380 br label %for.body3 381 382for.body3: 383 %indvars.iv = phi i64 [ %indvars.iv.next, %for.body3 ], [ 2, %for.body ] 384 %arrayidx5 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @A, i64 0, i64 %indvars.iv24, i64 %indvars.iv 385 %1 = load i32, i32* %arrayidx5 386 %add = add nsw i32 %1, %k 387 store i32 %add, i32* %arrayidx5 388 %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1 389 %lftr.wideiv = trunc i64 %indvars.iv to i32 390 %exitcond = icmp eq i32 %lftr.wideiv, %0 391 br i1 %exitcond, label %for.inc10, label %for.body3 392 393for.inc10: 394 %indvars.iv.next25 = add nuw nsw i64 %indvars.iv24, 1 395 %lftr.wideiv26 = trunc i64 %indvars.iv24 to i32 396 %exitcond27 = icmp eq i32 %lftr.wideiv26, %0 397 br i1 %exitcond27, label %for.end12, label %for.body 398 399for.end12: 400 ret void 401} 402;; Here we are checking if the inner phi is not split then we have not interchanged. 403; CHECK-LABEL: @interchange_06 404; CHECK: phi i64 [ %indvars.iv.next, %for.body3 ], [ 2, %for.body3.preheader ] 405; CHECK-NEXT: getelementptr 406; CHECK-NEXT: %1 = load 407 408;;--------------------------------------Test case 07------------------------------------- 409;; FIXME: 410;; Test for interchange when we have an lcssa phi. This should ideally be interchanged but it is currently not supported. 411;; for(gi=1;gi<N;gi++) 412;; for(gj=1;gj<M;gj++) 413;; A[gj][gi] = A[gj - 1][gi] + C[gj][gi]; 414 415@gi = common global i32 0 416@gj = common global i32 0 417 418define void @interchange_07(i32 %N, i32 %M){ 419entry: 420 store i32 1, i32* @gi 421 %cmp21 = icmp sgt i32 %N, 1 422 br i1 %cmp21, label %for.cond1.preheader.lr.ph, label %for.end16 423 424for.cond1.preheader.lr.ph: 425 %cmp218 = icmp sgt i32 %M, 1 426 %gi.promoted = load i32, i32* @gi 427 %0 = add i32 %M, -1 428 %1 = sext i32 %gi.promoted to i64 429 %2 = sext i32 %N to i64 430 %3 = add i32 %gi.promoted, 1 431 %4 = icmp slt i32 %3, %N 432 %smax = select i1 %4, i32 %N, i32 %3 433 br label %for.cond1.preheader 434 435for.cond1.preheader: 436 %indvars.iv25 = phi i64 [ %1, %for.cond1.preheader.lr.ph ], [ %indvars.iv.next26, %for.inc14 ] 437 br i1 %cmp218, label %for.body3, label %for.inc14 438 439for.body3: 440 %indvars.iv = phi i64 [ %indvars.iv.next, %for.body3 ], [ 1, %for.cond1.preheader ] 441 %5 = add nsw i64 %indvars.iv, -1 442 %arrayidx5 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @A, i64 0, i64 %5, i64 %indvars.iv25 443 %6 = load i32, i32* %arrayidx5 444 %arrayidx9 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @C, i64 0, i64 %indvars.iv, i64 %indvars.iv25 445 %7 = load i32, i32* %arrayidx9 446 %add = add nsw i32 %7, %6 447 %arrayidx13 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @A, i64 0, i64 %indvars.iv, i64 %indvars.iv25 448 store i32 %add, i32* %arrayidx13 449 %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1 450 %lftr.wideiv = trunc i64 %indvars.iv to i32 451 %exitcond = icmp eq i32 %lftr.wideiv, %0 452 br i1 %exitcond, label %for.inc14, label %for.body3 453 454for.inc14: 455 %inc.lcssa23 = phi i32 [ 1, %for.cond1.preheader ], [ %M, %for.body3 ] 456 %indvars.iv.next26 = add nsw i64 %indvars.iv25, 1 457 %cmp = icmp slt i64 %indvars.iv.next26, %2 458 br i1 %cmp, label %for.cond1.preheader, label %for.cond.for.end16_crit_edge 459 460for.cond.for.end16_crit_edge: 461 store i32 %inc.lcssa23, i32* @gj 462 store i32 %smax, i32* @gi 463 br label %for.end16 464 465for.end16: 466 ret void 467} 468 469; CHECK-LABEL: @interchange_07 470; CHECK: for.body3: ; preds = %for.body3.preheader, %for.body3 471; CHECK: %indvars.iv = phi i64 [ %indvars.iv.next, %for.body3 ], [ 1, %for.body3.preheader ] 472; CHECK: %5 = add nsw i64 %indvars.iv, -1 473; CHECK: %arrayidx5 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @A, i64 0, i64 %5, i64 %indvars.iv25 474; CHECK: %6 = load i32, i32* %arrayidx5 475; CHECK: %arrayidx9 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @C, i64 0, i64 %indvars.iv, i64 %indvars.iv25 476 477;;------------------------------------------------Test case 08------------------------------- 478;; Test for interchange in loop nest greater than 2. 479;; for(int i=0;i<100;i++) 480;; for(int j=0;j<100;j++) 481;; for(int k=0;k<100;k++) 482;; D[i][k][j] = D[i][k][j]+t; 483 484define void @interchange_08(i32 %t){ 485entry: 486 br label %for.cond1.preheader 487 488for.cond1.preheader: ; preds = %for.inc15, %entry 489 %i.028 = phi i32 [ 0, %entry ], [ %inc16, %for.inc15 ] 490 br label %for.cond4.preheader 491 492for.cond4.preheader: ; preds = %for.inc12, %for.cond1.preheader 493 %j.027 = phi i32 [ 0, %for.cond1.preheader ], [ %inc13, %for.inc12 ] 494 br label %for.body6 495 496for.body6: ; preds = %for.body6, %for.cond4.preheader 497 %k.026 = phi i32 [ 0, %for.cond4.preheader ], [ %inc, %for.body6 ] 498 %arrayidx8 = getelementptr inbounds [100 x [100 x [100 x i32]]], [100 x [100 x [100 x i32]]]* @D, i32 0, i32 %i.028, i32 %k.026, i32 %j.027 499 %0 = load i32, i32* %arrayidx8 500 %add = add nsw i32 %0, %t 501 store i32 %add, i32* %arrayidx8 502 %inc = add nuw nsw i32 %k.026, 1 503 %exitcond = icmp eq i32 %inc, 100 504 br i1 %exitcond, label %for.inc12, label %for.body6 505 506for.inc12: ; preds = %for.body6 507 %inc13 = add nuw nsw i32 %j.027, 1 508 %exitcond29 = icmp eq i32 %inc13, 100 509 br i1 %exitcond29, label %for.inc15, label %for.cond4.preheader 510 511for.inc15: ; preds = %for.inc12 512 %inc16 = add nuw nsw i32 %i.028, 1 513 %exitcond30 = icmp eq i32 %inc16, 100 514 br i1 %exitcond30, label %for.end17, label %for.cond1.preheader 515 516for.end17: ; preds = %for.inc15 517 ret void 518} 519; CHECK-LABEL: @interchange_08 520; CHECK: entry: 521; CHECK: br label %for.cond1.preheader.preheader 522; CHECK: for.cond1.preheader.preheader: ; preds = %entry 523; CHECK: br label %for.cond1.preheader 524; CHECK: for.cond1.preheader: ; preds = %for.cond1.preheader.preheader, %for.inc15 525; CHECK: %i.028 = phi i32 [ %inc16, %for.inc15 ], [ 0, %for.cond1.preheader.preheader ] 526; CHECK: br label %for.body6.preheader 527; CHECK: for.cond4.preheader.preheader: ; preds = %for.body6 528; CHECK: br label %for.cond4.preheader 529; CHECK: for.cond4.preheader: ; preds = %for.cond4.preheader.preheader, %for.inc12 530; CHECK: %j.027 = phi i32 [ %inc13, %for.inc12 ], [ 0, %for.cond4.preheader.preheader ] 531; CHECK: br label %for.body6.split1 532; CHECK: for.body6.preheader: ; preds = %for.cond1.preheader 533; CHECK: br label %for.body6 534; CHECK: for.body6: ; preds = %for.body6.preheader, %for.body6.split 535; CHECK: %k.026 = phi i32 [ %inc, %for.body6.split ], [ 0, %for.body6.preheader ] 536; CHECK: br label %for.cond4.preheader.preheader 537; CHECK: for.body6.split1: ; preds = %for.cond4.preheader 538; CHECK: %arrayidx8 = getelementptr inbounds [100 x [100 x [100 x i32]]], [100 x [100 x [100 x i32]]]* @D, i32 0, i32 %i.028, i32 %k.026, i32 %j.027 539; CHECK: %0 = load i32, i32* %arrayidx8 540; CHECK: %add = add nsw i32 %0, %t 541; CHECK: store i32 %add, i32* %arrayidx8 542; CHECK: br label %for.inc12 543; CHECK: for.body6.split: ; preds = %for.inc12 544; CHECK: %inc = add nuw nsw i32 %k.026, 1 545; CHECK: %exitcond = icmp eq i32 %inc, 100 546; CHECK: br i1 %exitcond, label %for.inc15, label %for.body6 547; CHECK: for.inc12: ; preds = %for.body6.split1 548; CHECK: %inc13 = add nuw nsw i32 %j.027, 1 549; CHECK: %exitcond29 = icmp eq i32 %inc13, 100 550; CHECK: br i1 %exitcond29, label %for.body6.split, label %for.cond4.preheader 551; CHECK: for.inc15: ; preds = %for.body6.split 552; CHECK: %inc16 = add nuw nsw i32 %i.028, 1 553; CHECK: %exitcond30 = icmp eq i32 %inc16, 100 554; CHECK: br i1 %exitcond30, label %for.end17, label %for.cond1.preheader 555; CHECK: for.end17: ; preds = %for.inc15 556; CHECK: ret void 557 558