test/Transforms/LoopInterchange/interchange.ll

   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