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 4 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" 5 target 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 12 declare 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 19 define void @interchange_01(i32 %k, i32 %N) { 20 entry: 21 %cmp21 = icmp sgt i32 %N, 0 22 br i1 %cmp21, label %for.cond1.preheader.lr.ph, label %for.end12 23 24 for.cond1.preheader.lr.ph: 25 %cmp219 = icmp sgt i32 %N, 1 26 %0 = add i32 %N, -1 27 br label %for.cond1.preheader 28 29 for.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 33 for.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 44 for.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 50 for.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 99 define void @interchange_02(i32 %k) { 100 entry: 101 br label %for.cond1.preheader 102 103 for.cond1.preheader: 104 %indvars.iv19 = phi i64 [ 0, %entry ], [ %indvars.iv.next20, %for.inc10 ] 105 br label %for.body3 106 107 for.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 117 for.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 122 for.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 162 define void @interchange_03(i32 %k) { 163 entry: 164 br label %for.cond1.preheader 165 166 for.cond1.preheader: 167 %indvars.iv21 = phi i64 [ 0, %entry ], [ %indvars.iv.next22, %for.inc10 ] 168 br label %for.body3 169 170 for.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 180 for.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 185 for.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 222 define void @interchange_04(i32 %k){ 223 entry: 224 br label %for.cond1.preheader 225 226 for.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 231 for.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 242 for.inc12: 243 %exitcond25 = icmp eq i64 %indvars.iv.next24, 99 244 br i1 %exitcond25, label %for.end14, label %for.cond1.preheader 245 246 for.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 283 define void @interchange_05(i32 %k, i32 %N){ 284 entry: 285 %cmp30 = icmp sgt i32 %N, 0 286 br i1 %cmp30, label %for.body.lr.ph, label %for.end17 287 288 for.body.lr.ph: 289 %0 = add i32 %N, -1 290 %1 = zext i32 %k to i64 291 br label %for.body 292 293 for.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 301 for.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 312 for.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 318 for.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 368 define void @interchange_06(i32 %k, i32 %N) { 369 entry: 370 %cmp22 = icmp sgt i32 %N, 0 371 br i1 %cmp22, label %for.body.lr.ph, label %for.end12 372 373 for.body.lr.ph: 374 %0 = add i32 %N, -1 375 br label %for.body 376 377 for.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 382 for.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 393 for.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 399 for.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 418 define void @interchange_07(i32 %N, i32 %M){ 419 entry: 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 424 for.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 435 for.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 439 for.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 454 for.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 460 for.cond.for.end16_crit_edge: 461 store i32 %inc.lcssa23, i32* @gj 462 store i32 %smax, i32* @gi 463 br label %for.end16 464 465 for.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 484 define void @interchange_08(i32 %t){ 485 entry: 486 br label %for.cond1.preheader 487 488 for.cond1.preheader: ; preds = %for.inc15, %entry 489 %i.028 = phi i32 [ 0, %entry ], [ %inc16, %for.inc15 ] 490 br label %for.cond4.preheader 491 492 for.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 496 for.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 506 for.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 511 for.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 516 for.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
