llvm/test/Transforms/LoopInterchange/not-interchanged-tightly-nested.ll

   1 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --version 5
   2 ; RUN: opt < %s -passes=loop-interchange -verify-dom-info -verify-loop-info -S 2>&1 | FileCheck %s
   3
   4 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
   5
   6 @A = common global [100 x [100 x i32]] zeroinitializer
   7 @B = common global [100 x i32] zeroinitializer
   8 @C = common global [100 x [100 x i32]] zeroinitializer
   9 @D = common global [100 x [100 x [100 x i32]]] zeroinitializer
  10
  11 ; Loops not tightly nested are not interchanged
  12 ;
  13 ;  for(int j=0;j<N;j++) {
  14 ;    B[j] = j+k;
  15 ;    for(int i=0;i<N;i++)
  16 ;      A[j][i] = A[j][i]+B[j];
  17 ;  }
  18 ;
  19 define void @interchange_05(i32 %k, i32 %N){
  20 ; CHECK-LABEL: define void @interchange_05(
  21 ; CHECK-SAME: i32 [[K:%.*]], i32 [[N:%.*]]) {
  22 ; CHECK-NEXT:  [[ENTRY:.*:]]
  23 ; CHECK-NEXT:    [[CMP30:%.*]] = icmp sgt i32 [[N]], 0
  24 ; CHECK-NEXT:    br i1 [[CMP30]], label %[[FOR_BODY_LR_PH:.*]], label %[[FOR_END17:.*]]
  25 ; CHECK:       [[FOR_BODY_LR_PH]]:
  26 ; CHECK-NEXT:    [[TMP0:%.*]] = add i32 [[N]], -1
  27 ; CHECK-NEXT:    [[TMP1:%.*]] = zext i32 [[K]] to i64
  28 ; CHECK-NEXT:    br label %[[FOR_BODY:.*]]
  29 ; CHECK:       [[FOR_BODY]]:
  30 ; CHECK-NEXT:    [[INDVARS_IV32:%.*]] = phi i64 [ 0, %[[FOR_BODY_LR_PH]] ], [ [[INDVARS_IV_NEXT33:%.*]], %[[FOR_INC15:.*]] ]
  31 ; CHECK-NEXT:    [[TMP2:%.*]] = add nsw i64 [[INDVARS_IV32]], [[TMP1]]
  32 ; CHECK-NEXT:    [[ARRAYIDX:%.*]] = getelementptr inbounds [100 x i32], ptr @B, i64 0, i64 [[INDVARS_IV32]]
  33 ; CHECK-NEXT:    [[TMP3:%.*]] = trunc i64 [[TMP2]] to i32
  34 ; CHECK-NEXT:    store i32 [[TMP3]], ptr [[ARRAYIDX]], align 4
  35 ; CHECK-NEXT:    br label %[[FOR_BODY3:.*]]
  36 ; CHECK:       [[FOR_BODY3]]:
  37 ; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ 0, %[[FOR_BODY]] ], [ [[INDVARS_IV_NEXT:%.*]], %[[FOR_BODY3]] ]
  38 ; CHECK-NEXT:    [[ARRAYIDX7:%.*]] = getelementptr inbounds [100 x [100 x i32]], ptr @A, i64 0, i64 [[INDVARS_IV32]], i64 [[INDVARS_IV]]
  39 ; CHECK-NEXT:    [[TMP4:%.*]] = load i32, ptr [[ARRAYIDX7]], align 4
  40 ; CHECK-NEXT:    [[ADD10:%.*]] = add nsw i32 [[TMP3]], [[TMP4]]
  41 ; CHECK-NEXT:    store i32 [[ADD10]], ptr [[ARRAYIDX7]], align 4
  42 ; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nuw nsw i64 [[INDVARS_IV]], 1
  43 ; CHECK-NEXT:    [[LFTR_WIDEIV:%.*]] = trunc i64 [[INDVARS_IV]] to i32
  44 ; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp eq i32 [[LFTR_WIDEIV]], [[TMP0]]
  45 ; CHECK-NEXT:    br i1 [[EXITCOND]], label %[[FOR_INC15]], label %[[FOR_BODY3]]
  46 ; CHECK:       [[FOR_INC15]]:
  47 ; CHECK-NEXT:    [[INDVARS_IV_NEXT33]] = add nuw nsw i64 [[INDVARS_IV32]], 1
  48 ; CHECK-NEXT:    [[LFTR_WIDEIV35:%.*]] = trunc i64 [[INDVARS_IV32]] to i32
  49 ; CHECK-NEXT:    [[EXITCOND36:%.*]] = icmp eq i32 [[LFTR_WIDEIV35]], [[TMP0]]
  50 ; CHECK-NEXT:    br i1 [[EXITCOND36]], label %[[FOR_END17_LOOPEXIT:.*]], label %[[FOR_BODY]]
  51 ; CHECK:       [[FOR_END17_LOOPEXIT]]:
  52 ; CHECK-NEXT:    br label %[[FOR_END17]]
  53 ; CHECK:       [[FOR_END17]]:
  54 ; CHECK-NEXT:    ret void
  55 ;
  56 entry:
  57   %cmp30 = icmp sgt i32 %N, 0
  58   br i1 %cmp30, label %for.body.lr.ph, label %for.end17
  59
  60 for.body.lr.ph:
  61   %0 = add i32 %N, -1
  62   %1 = zext i32 %k to i64
  63   br label %for.body
  64
  65 for.body:
  66   %indvars.iv32 = phi i64 [ 0, %for.body.lr.ph ], [ %indvars.iv.next33, %for.inc15 ]
  67   %2 = add nsw i64 %indvars.iv32, %1
  68   %arrayidx = getelementptr inbounds [100 x i32], ptr @B, i64 0, i64 %indvars.iv32
  69   %3 = trunc i64 %2 to i32
  70   store i32 %3, ptr %arrayidx
  71   br label %for.body3
  72
  73 for.body3:
  74   %indvars.iv = phi i64 [ 0, %for.body ], [ %indvars.iv.next, %for.body3 ]
  75   %arrayidx7 = getelementptr inbounds [100 x [100 x i32]], ptr @A, i64 0, i64 %indvars.iv32, i64 %indvars.iv
  76   %4 = load i32, ptr %arrayidx7
  77   %add10 = add nsw i32 %3, %4
  78   store i32 %add10, ptr %arrayidx7
  79   %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
  80   %lftr.wideiv = trunc i64 %indvars.iv to i32
  81   %exitcond = icmp eq i32 %lftr.wideiv, %0
  82   br i1 %exitcond, label %for.inc15, label %for.body3
  83
  84 for.inc15:
  85   %indvars.iv.next33 = add nuw nsw i64 %indvars.iv32, 1
  86   %lftr.wideiv35 = trunc i64 %indvars.iv32 to i32
  87   %exitcond36 = icmp eq i32 %lftr.wideiv35, %0
  88   br i1 %exitcond36, label %for.end17, label %for.body
  89
  90 for.end17:
  91   ret void
  92 }
  93
  94 declare void @foo(...) readnone
  95
  96 ; Loops not tightly nested are not interchanged
  97 ;  for(int j=0;j<N;j++) {
  98 ;    foo();
  99 ;    for(int i=2;i<N;i++)
 100 ;      A[j][i] = A[j][i]+k;
 101 ;  }
 102 ;
 103 define void @interchange_06(i32 %k, i32 %N) {
 104 ; CHECK-LABEL: define void @interchange_06(
 105 ; CHECK-SAME: i32 [[K:%.*]], i32 [[N:%.*]]) {
 106 ; CHECK-NEXT:  [[ENTRY:.*:]]
 107 ; CHECK-NEXT:    [[CMP22:%.*]] = icmp sgt i32 [[N]], 0
 108 ; CHECK-NEXT:    br i1 [[CMP22]], label %[[FOR_BODY_LR_PH:.*]], label %[[FOR_END12:.*]]
 109 ; CHECK:       [[FOR_BODY_LR_PH]]:
 110 ; CHECK-NEXT:    [[TMP0:%.*]] = add i32 [[N]], -1
 111 ; CHECK-NEXT:    br label %[[FOR_BODY:.*]]
 112 ; CHECK:       [[FOR_BODY]]:
 113 ; CHECK-NEXT:    [[INDVARS_IV24:%.*]] = phi i64 [ 0, %[[FOR_BODY_LR_PH]] ], [ [[INDVARS_IV_NEXT25:%.*]], %[[FOR_INC10:.*]] ]
 114 ; CHECK-NEXT:    tail call void (...) @foo()
 115 ; CHECK-NEXT:    br label %[[FOR_BODY3:.*]]
 116 ; CHECK:       [[FOR_BODY3]]:
 117 ; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ [[INDVARS_IV_NEXT:%.*]], %[[FOR_BODY3]] ], [ 2, %[[FOR_BODY]] ]
 118 ; CHECK-NEXT:    [[ARRAYIDX5:%.*]] = getelementptr inbounds [100 x [100 x i32]], ptr @A, i64 0, i64 [[INDVARS_IV24]], i64 [[INDVARS_IV]]
 119 ; CHECK-NEXT:    [[TMP1:%.*]] = load i32, ptr [[ARRAYIDX5]], align 4
 120 ; CHECK-NEXT:    [[ADD:%.*]] = add nsw i32 [[TMP1]], [[K]]
 121 ; CHECK-NEXT:    store i32 [[ADD]], ptr [[ARRAYIDX5]], align 4
 122 ; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nuw nsw i64 [[INDVARS_IV]], 1
 123 ; CHECK-NEXT:    [[LFTR_WIDEIV:%.*]] = trunc i64 [[INDVARS_IV]] to i32
 124 ; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp eq i32 [[LFTR_WIDEIV]], [[TMP0]]
 125 ; CHECK-NEXT:    br i1 [[EXITCOND]], label %[[FOR_INC10]], label %[[FOR_BODY3]]
 126 ; CHECK:       [[FOR_INC10]]:
 127 ; CHECK-NEXT:    [[INDVARS_IV_NEXT25]] = add nuw nsw i64 [[INDVARS_IV24]], 1
 128 ; CHECK-NEXT:    [[LFTR_WIDEIV26:%.*]] = trunc i64 [[INDVARS_IV24]] to i32
 129 ; CHECK-NEXT:    [[EXITCOND27:%.*]] = icmp eq i32 [[LFTR_WIDEIV26]], [[TMP0]]
 130 ; CHECK-NEXT:    br i1 [[EXITCOND27]], label %[[FOR_END12_LOOPEXIT:.*]], label %[[FOR_BODY]]
 131 ; CHECK:       [[FOR_END12_LOOPEXIT]]:
 132 ; CHECK-NEXT:    br label %[[FOR_END12]]
 133 ; CHECK:       [[FOR_END12]]:
 134 ; CHECK-NEXT:    ret void
 135 ;
 136 entry:
 137   %cmp22 = icmp sgt i32 %N, 0
 138   br i1 %cmp22, label %for.body.lr.ph, label %for.end12
 139
 140 for.body.lr.ph:
 141   %0 = add i32 %N, -1
 142   br label %for.body
 143
 144 for.body:
 145   %indvars.iv24 = phi i64 [ 0, %for.body.lr.ph ], [ %indvars.iv.next25, %for.inc10 ]
 146   tail call void (...) @foo()
 147   br label %for.body3
 148
 149 for.body3:
 150   %indvars.iv = phi i64 [ %indvars.iv.next, %for.body3 ], [ 2, %for.body ]
 151   %arrayidx5 = getelementptr inbounds [100 x [100 x i32]], ptr @A, i64 0, i64 %indvars.iv24, i64 %indvars.iv
 152   %1 = load i32, ptr %arrayidx5
 153   %add = add nsw i32 %1, %k
 154   store i32 %add, ptr %arrayidx5
 155   %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
 156   %lftr.wideiv = trunc i64 %indvars.iv to i32
 157   %exitcond = icmp eq i32 %lftr.wideiv, %0
 158   br i1 %exitcond, label %for.inc10, label %for.body3
 159
 160 for.inc10:
 161   %indvars.iv.next25 = add nuw nsw i64 %indvars.iv24, 1
 162   %lftr.wideiv26 = trunc i64 %indvars.iv24 to i32
 163   %exitcond27 = icmp eq i32 %lftr.wideiv26, %0
 164   br i1 %exitcond27, label %for.end12, label %for.body
 165
 166 for.end12:
 167   ret void
 168 }
 169
 170 ; The following Loop is not considered tightly nested and is not interchanged.
 171 ; The outer loop header does not branch to the inner loop preheader, or the
 172 ; inner loop header, or the outer loop latch.
 173 ;
 174 define void @interchange_07(i32 %k, i32 %N, i64 %ny) {
 175 ; CHECK-LABEL: define void @interchange_07(
 176 ; CHECK-SAME: i32 [[K:%.*]], i32 [[N:%.*]], i64 [[NY:%.*]]) {
 177 ; CHECK-NEXT:  [[ENTRY:.*]]:
 178 ; CHECK-NEXT:    br label %[[FOR1_HEADER:.*]]
 179 ; CHECK:       [[FOR1_HEADER]]:
 180 ; CHECK-NEXT:    [[J23:%.*]] = phi i64 [ 0, %[[ENTRY]] ], [ [[J_NEXT24:%.*]], %[[FOR1_INC10:.*]] ]
 181 ; CHECK-NEXT:    [[CMP21:%.*]] = icmp slt i64 0, [[NY]]
 182 ; CHECK-NEXT:    br label %[[SINGLESUCC:.*]]
 183 ; CHECK:       [[SINGLESUCC]]:
 184 ; CHECK-NEXT:    br i1 [[CMP21]], label %[[PREHEADER_J:.*]], label %[[FOR1_INC10]]
 185 ; CHECK:       [[PREHEADER_J]]:
 186 ; CHECK-NEXT:    br label %[[FOR2:.*]]
 187 ; CHECK:       [[FOR2]]:
 188 ; CHECK-NEXT:    [[J:%.*]] = phi i64 [ [[J_NEXT:%.*]], %[[FOR2]] ], [ 0, %[[PREHEADER_J]] ]
 189 ; CHECK-NEXT:    [[ARRAYIDX5:%.*]] = getelementptr inbounds [100 x [100 x i32]], ptr @A, i64 0, i64 [[J]], i64 [[J23]]
 190 ; CHECK-NEXT:    [[LV:%.*]] = load i32, ptr [[ARRAYIDX5]], align 4
 191 ; CHECK-NEXT:    [[ADD:%.*]] = add nsw i32 [[LV]], [[K]]
 192 ; CHECK-NEXT:    store i32 [[ADD]], ptr [[ARRAYIDX5]], align 4
 193 ; CHECK-NEXT:    [[J_NEXT]] = add nuw nsw i64 [[J]], 1
 194 ; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp eq i64 [[J]], 99
 195 ; CHECK-NEXT:    br i1 [[EXITCOND]], label %[[FOR1_INC10_LOOPEXIT:.*]], label %[[FOR2]]
 196 ; CHECK:       [[FOR1_INC10_LOOPEXIT]]:
 197 ; CHECK-NEXT:    br label %[[FOR1_INC10]]
 198 ; CHECK:       [[FOR1_INC10]]:
 199 ; CHECK-NEXT:    [[J_NEXT24]] = add nuw nsw i64 [[J23]], 1
 200 ; CHECK-NEXT:    [[EXITCOND26:%.*]] = icmp eq i64 [[J23]], 99
 201 ; CHECK-NEXT:    br i1 [[EXITCOND26]], label %[[FOR_END12:.*]], label %[[FOR1_HEADER]]
 202 ; CHECK:       [[FOR_END12]]:
 203 ; CHECK-NEXT:    ret void
 204 ;
 205 entry:
 206   br label %for1.header
 207
 208 for1.header:
 209   %j23 = phi i64 [ 0, %entry ], [ %j.next24, %for1.inc10 ]
 210   %cmp21 = icmp slt i64 0, %ny
 211   br label %singleSucc
 212
 213 singleSucc:
 214   br i1 %cmp21, label %preheader.j, label %for1.inc10
 215
 216 preheader.j:
 217   br label %for2
 218
 219 for2:
 220   %j = phi i64 [ %j.next, %for2 ], [ 0, %preheader.j ]
 221   %arrayidx5 = getelementptr inbounds [100 x [100 x i32]], ptr @A, i64 0, i64 %j, i64 %j23
 222   %lv = load i32, ptr %arrayidx5
 223   %add = add nsw i32 %lv, %k
 224   store i32 %add, ptr %arrayidx5
 225   %j.next = add nuw nsw i64 %j, 1
 226   %exitcond = icmp eq i64 %j, 99
 227   br i1 %exitcond, label %for1.inc10, label %for2
 228
 229 for1.inc10:
 230   %j.next24 = add nuw nsw i64 %j23, 1
 231   %exitcond26 = icmp eq i64 %j23, 99
 232   br i1 %exitcond26, label %for.end12, label %for1.header
 233
 234 for.end12:
 235   ret void
 236 }