llvm/test/Analysis/LoopNestAnalysis/imperfectnest.ll

   1 ; RUN: opt < %s -passes='print<loopnest>' -disable-output 2>&1 | FileCheck %s
   2
   3 ; Test an imperfect 2-dim loop nest of the form:
   4 ;   for (int i = 0; i < nx; ++i) {
   5 ;     x[i] = i;
   6 ;     for (int j = 0; j < ny; ++j)
   7 ;       y[j][i] = x[i] + j;
   8 ;   }
   9
  10 define void @imperf_nest_1(i32 signext %nx, i32 signext %ny) {
  11 ; CHECK-LABEL: IsPerfect=false, Depth=2, OutermostLoop: imperf_nest_1_loop_i, Loops: ( imperf_nest_1_loop_i imperf_nest_1_loop_j )
  12 entry:
  13   %0 = zext i32 %ny to i64
  14   %1 = zext i32 %nx to i64
  15   %2 = mul nuw i64 %0, %1
  16   %vla = alloca double, i64 %2, align 8
  17   %3 = zext i32 %ny to i64
  18   %vla1 = alloca double, i64 %3, align 8
  19   br label %imperf_nest_1_loop_i
  20
  21 imperf_nest_1_loop_i:
  22   %i2.0 = phi i32 [ 0, %entry ], [ %inc16, %for.inc15 ]
  23   %cmp = icmp slt i32 %i2.0, %nx
  24   br i1 %cmp, label %for.body, label %for.end17
  25
  26 for.body:
  27   %conv = sitofp i32 %i2.0 to double
  28   %idxprom = sext i32 %i2.0 to i64
  29   %arrayidx = getelementptr inbounds double, ptr %vla1, i64 %idxprom
  30   store double %conv, ptr %arrayidx, align 8
  31   br label %imperf_nest_1_loop_j
  32
  33 imperf_nest_1_loop_j:
  34   %j3.0 = phi i32 [ 0, %for.body ], [ %inc, %for.inc ]
  35   %cmp5 = icmp slt i32 %j3.0, %ny
  36   br i1 %cmp5, label %for.body7, label %for.end
  37
  38 for.body7:
  39   %idxprom8 = sext i32 %i2.0 to i64
  40   %arrayidx9 = getelementptr inbounds double, ptr %vla1, i64 %idxprom8
  41   %4 = load double, ptr %arrayidx9, align 8
  42   %conv10 = sitofp i32 %j3.0 to double
  43   %add = fadd double %4, %conv10
  44   %idxprom11 = sext i32 %j3.0 to i64
  45   %5 = mul nsw i64 %idxprom11, %1
  46   %arrayidx12 = getelementptr inbounds double, ptr %vla, i64 %5
  47   %idxprom13 = sext i32 %i2.0 to i64
  48   %arrayidx14 = getelementptr inbounds double, ptr %arrayidx12, i64 %idxprom13
  49   store double %add, ptr %arrayidx14, align 8
  50   br label %for.inc
  51
  52 for.inc:
  53   %inc = add nsw i32 %j3.0, 1
  54   br label %imperf_nest_1_loop_j
  55
  56 for.end:
  57   br label %for.inc15
  58
  59 for.inc15:
  60   %inc16 = add nsw i32 %i2.0, 1
  61   br label %imperf_nest_1_loop_i
  62
  63 for.end17:
  64   ret void
  65 }
  66
  67 ; Test an imperfect 2-dim loop nest of the form:
  68 ;   for (int i = 0; i < nx; ++i) {
  69 ;     for (int j = 0; j < ny; ++j)
  70 ;       y[j][i] = x[i] + j;
  71 ;     y[0][i] += i;
  72 ;   }
  73
  74 define void @imperf_nest_2(i32 signext %nx, i32 signext %ny) {
  75 ; CHECK-LABEL: IsPerfect=false, Depth=2, OutermostLoop: imperf_nest_2_loop_i, Loops: ( imperf_nest_2_loop_i imperf_nest_2_loop_j )
  76 entry:
  77   %0 = zext i32 %ny to i64
  78   %1 = zext i32 %nx to i64
  79   %2 = mul nuw i64 %0, %1
  80   %vla = alloca double, i64 %2, align 8
  81   %3 = zext i32 %ny to i64
  82   %vla1 = alloca double, i64 %3, align 8
  83   br label %imperf_nest_2_loop_i
  84
  85 imperf_nest_2_loop_i:
  86   %i2.0 = phi i32 [ 0, %entry ], [ %inc17, %for.inc16 ]
  87   %cmp = icmp slt i32 %i2.0, %nx
  88   br i1 %cmp, label %for.body, label %for.end18
  89
  90 for.body:
  91   br label %imperf_nest_2_loop_j
  92
  93 imperf_nest_2_loop_j:
  94   %j3.0 = phi i32 [ 0, %for.body ], [ %inc, %for.inc ]
  95   %cmp5 = icmp slt i32 %j3.0, %ny
  96   br i1 %cmp5, label %for.body6, label %for.end
  97
  98 for.body6:
  99   %idxprom = sext i32 %i2.0 to i64
 100   %arrayidx = getelementptr inbounds double, ptr %vla1, i64 %idxprom
 101   %4 = load double, ptr %arrayidx, align 8
 102   %conv = sitofp i32 %j3.0 to double
 103   %add = fadd double %4, %conv
 104   %idxprom7 = sext i32 %j3.0 to i64
 105   %5 = mul nsw i64 %idxprom7, %1
 106   %arrayidx8 = getelementptr inbounds double, ptr %vla, i64 %5
 107   %idxprom9 = sext i32 %i2.0 to i64
 108   %arrayidx10 = getelementptr inbounds double, ptr %arrayidx8, i64 %idxprom9
 109   store double %add, ptr %arrayidx10, align 8
 110   br label %for.inc
 111
 112 for.inc:
 113   %inc = add nsw i32 %j3.0, 1
 114   br label %imperf_nest_2_loop_j
 115
 116 for.end:
 117   %conv11 = sitofp i32 %i2.0 to double
 118   %6 = mul nsw i64 0, %1
 119   %arrayidx12 = getelementptr inbounds double, ptr %vla, i64 %6
 120   %idxprom13 = sext i32 %i2.0 to i64
 121   %arrayidx14 = getelementptr inbounds double, ptr %arrayidx12, i64 %idxprom13
 122   %7 = load double, ptr %arrayidx14, align 8
 123   %add15 = fadd double %7, %conv11
 124   store double %add15, ptr %arrayidx14, align 8
 125   br label %for.inc16
 126
 127 for.inc16:
 128   %inc17 = add nsw i32 %i2.0, 1
 129   br label %imperf_nest_2_loop_i
 130
 131 for.end18:
 132   ret void
 133 }
 134
 135 ; Test an imperfect 2-dim loop nest of the form:
 136 ;   for (i = 0; i < nx; ++i) {
 137 ;     for (j = 0; j < ny-nk; ++j)
 138 ;       y[i][j] = x[i] + j;
 139 ;     for (j = ny-nk; j < ny; ++j)
 140 ;       y[i][j] = x[i] - j;
 141 ;   }
 142
 143 define void @imperf_nest_3(i32 signext %nx, i32 signext %ny, i32 signext %nk) {
 144 ; CHECK-LABEL: IsPerfect=false, Depth=2, OutermostLoop: imperf_nest_3_loop_i, Loops: ( imperf_nest_3_loop_i imperf_nest_3_loop_j imperf_nest_3_loop_k )
 145 entry:
 146   %0 = zext i32 %nx to i64
 147   %1 = zext i32 %ny to i64
 148   %2 = mul nuw i64 %0, %1
 149   %vla = alloca double, i64 %2, align 8
 150   %3 = zext i32 %ny to i64
 151   %vla1 = alloca double, i64 %3, align 8
 152   br label %imperf_nest_3_loop_i
 153
 154 imperf_nest_3_loop_i:                                         ; preds = %for.inc25, %entry
 155   %i.0 = phi i32 [ 0, %entry ], [ %inc26, %for.inc25 ]
 156   %cmp = icmp slt i32 %i.0, %nx
 157   br i1 %cmp, label %for.body, label %for.end27
 158
 159 for.body:                                         ; preds = %for.cond
 160   br label %imperf_nest_3_loop_j
 161
 162 imperf_nest_3_loop_j:                                        ; preds = %for.inc, %for.body
 163   %j.0 = phi i32 [ 0, %for.body ], [ %inc, %for.inc ]
 164   %sub = sub nsw i32 %ny, %nk
 165   %cmp3 = icmp slt i32 %j.0, %sub
 166   br i1 %cmp3, label %for.body4, label %for.end
 167
 168 for.body4:                                        ; preds = %imperf_nest_3_loop_j
 169   %idxprom = sext i32 %i.0 to i64
 170   %arrayidx = getelementptr inbounds double, ptr %vla1, i64 %idxprom
 171   %4 = load double, ptr %arrayidx, align 8
 172   %conv = sitofp i32 %j.0 to double
 173   %add = fadd double %4, %conv
 174   %idxprom5 = sext i32 %i.0 to i64
 175   %5 = mul nsw i64 %idxprom5, %1
 176   %arrayidx6 = getelementptr inbounds double, ptr %vla, i64 %5
 177   %idxprom7 = sext i32 %j.0 to i64
 178   %arrayidx8 = getelementptr inbounds double, ptr %arrayidx6, i64 %idxprom7
 179   store double %add, ptr %arrayidx8, align 8
 180   br label %for.inc
 181
 182 for.inc:                                          ; preds = %for.body4
 183   %inc = add nsw i32 %j.0, 1
 184   br label %imperf_nest_3_loop_j
 185
 186 for.end:                                          ; preds = %imperf_nest_3_loop_j
 187   %sub9 = sub nsw i32 %ny, %nk
 188   br label %imperf_nest_3_loop_k
 189
 190 imperf_nest_3_loop_k:                                       ; preds = %for.inc22, %for.end
 191   %j.1 = phi i32 [ %sub9, %for.end ], [ %inc23, %for.inc22 ]
 192   %cmp11 = icmp slt i32 %j.1, %ny
 193   br i1 %cmp11, label %for.body13, label %for.end24
 194
 195 for.body13:                                       ; preds = %imperf_nest_3_loop_k
 196   %idxprom14 = sext i32 %i.0 to i64
 197   %arrayidx15 = getelementptr inbounds double, ptr %vla1, i64 %idxprom14
 198   %6 = load double, ptr %arrayidx15, align 8
 199   %conv16 = sitofp i32 %j.1 to double
 200   %sub17 = fsub double %6, %conv16
 201   %idxprom18 = sext i32 %i.0 to i64
 202   %7 = mul nsw i64 %idxprom18, %1
 203   %arrayidx19 = getelementptr inbounds double, ptr %vla, i64 %7
 204   %idxprom20 = sext i32 %j.1 to i64
 205   %arrayidx21 = getelementptr inbounds double, ptr %arrayidx19, i64 %idxprom20
 206   store double %sub17, ptr %arrayidx21, align 8
 207   br label %for.inc22
 208
 209 for.inc22:                                        ; preds = %for.body13
 210   %inc23 = add nsw i32 %j.1, 1
 211   br label %imperf_nest_3_loop_k
 212
 213 for.end24:                                        ; preds = %imperf_nest_3_loop_k
 214   br label %for.inc25
 215
 216 for.inc25:                                        ; preds = %for.end24
 217   %inc26 = add nsw i32 %i.0, 1
 218   br label %imperf_nest_3_loop_i
 219
 220 for.end27:                                        ; preds = %for.cond
 221   ret void
 222 }
 223
 224 ; Test an imperfect loop nest of the form:
 225 ;   for (i = 0; i < nx; ++i) {
 226 ;     for (j = 0; j < ny-nk; ++j)
 227 ;       for (k = 0; k < nk; ++k)
 228 ;         y[i][j][k] = x[i+j] + k;
 229 ;     for (j = ny-nk; j < ny; ++j)
 230 ;       y[i][j][0] = x[i] - j;
 231 ;   }
 232
 233 define void @imperf_nest_4(i32 signext %nx, i32 signext %ny, i32 signext %nk) {
 234 ; CHECK-LABEL: IsPerfect=false, Depth=2, OutermostLoop: imperf_nest_4_loop_j, Loops: ( imperf_nest_4_loop_j imperf_nest_4_loop_k )
 235 ; CHECK-LABEL: IsPerfect=false, Depth=3, OutermostLoop: imperf_nest_4_loop_i, Loops: ( imperf_nest_4_loop_i imperf_nest_4_loop_j imperf_nest_4_loop_j2 imperf_nest_4_loop_k )
 236 entry:
 237   %0 = zext i32 %nx to i64
 238   %1 = zext i32 %ny to i64
 239   %2 = zext i32 %nk to i64
 240   %3 = mul nuw i64 %0, %1
 241   %4 = mul nuw i64 %3, %2
 242   %vla = alloca double, i64 %4, align 8
 243   %5 = zext i32 %ny to i64
 244   %vla1 = alloca double, i64 %5, align 8
 245   %cmp5 = icmp slt i32 0, %nx
 246   br i1 %cmp5, label %imperf_nest_4_loop_i.lr.ph, label %for.end37
 247
 248 imperf_nest_4_loop_i.lr.ph:
 249   br label %imperf_nest_4_loop_i
 250
 251 imperf_nest_4_loop_i:
 252   %i.0 = phi i32 [ 0, %imperf_nest_4_loop_i.lr.ph ], [ %inc36, %for.inc35 ]
 253   %sub2 = sub nsw i32 %ny, %nk
 254   %cmp33 = icmp slt i32 0, %sub2
 255   br i1 %cmp33, label %imperf_nest_4_loop_j.lr.ph, label %for.end17
 256
 257 imperf_nest_4_loop_j.lr.ph:
 258   br label %imperf_nest_4_loop_j
 259
 260 imperf_nest_4_loop_j:
 261   %j.0 = phi i32 [ 0, %imperf_nest_4_loop_j.lr.ph ], [ %inc16, %for.inc15 ]
 262   %cmp61 = icmp slt i32 0, %nk
 263   br i1 %cmp61, label %imperf_nest_4_loop_k.lr.ph, label %for.end
 264
 265 imperf_nest_4_loop_k.lr.ph:
 266   br label %imperf_nest_4_loop_k
 267
 268 imperf_nest_4_loop_k:
 269   %k.0 = phi i32 [ 0, %imperf_nest_4_loop_k.lr.ph ], [ %inc, %for.inc ]
 270   %add = add nsw i32 %i.0, %j.0
 271   %idxprom = sext i32 %add to i64
 272   %arrayidx = getelementptr inbounds double, ptr %vla1, i64 %idxprom
 273   %6 = load double, ptr %arrayidx, align 8
 274   %conv = sitofp i32 %k.0 to double
 275   %add8 = fadd double %6, %conv
 276   %idxprom9 = sext i32 %i.0 to i64
 277   %7 = mul nuw i64 %1, %2
 278   %8 = mul nsw i64 %idxprom9, %7
 279   %arrayidx10 = getelementptr inbounds double, ptr %vla, i64 %8
 280   %idxprom11 = sext i32 %j.0 to i64
 281   %9 = mul nsw i64 %idxprom11, %2
 282   %arrayidx12 = getelementptr inbounds double, ptr %arrayidx10, i64 %9
 283   %idxprom13 = sext i32 %k.0 to i64
 284   %arrayidx14 = getelementptr inbounds double, ptr %arrayidx12, i64 %idxprom13
 285   store double %add8, ptr %arrayidx14, align 8
 286   br label %for.inc
 287
 288 for.inc:
 289   %inc = add nsw i32 %k.0, 1
 290   %cmp6 = icmp slt i32 %inc, %nk
 291   br i1 %cmp6, label %imperf_nest_4_loop_k, label %for.cond5.for.end_crit_edge
 292
 293 for.cond5.for.end_crit_edge:
 294   br label %for.end
 295
 296 for.end:
 297   br label %for.inc15
 298
 299 for.inc15:
 300   %inc16 = add nsw i32 %j.0, 1
 301   %sub = sub nsw i32 %ny, %nk
 302   %cmp3 = icmp slt i32 %inc16, %sub
 303   br i1 %cmp3, label %imperf_nest_4_loop_j, label %for.cond2.for.end17_crit_edge
 304
 305 for.cond2.for.end17_crit_edge:
 306   br label %for.end17
 307
 308 for.end17:
 309   %sub18 = sub nsw i32 %ny, %nk
 310   %cmp204 = icmp slt i32 %sub18, %ny
 311   br i1 %cmp204, label %imperf_nest_4_loop_j2.lr.ph, label %for.end34
 312
 313 imperf_nest_4_loop_j2.lr.ph:
 314   br label %imperf_nest_4_loop_j2
 315
 316 imperf_nest_4_loop_j2:
 317   %j.1 = phi i32 [ %sub18, %imperf_nest_4_loop_j2.lr.ph ], [ %inc33, %for.inc32 ]
 318   %idxprom23 = sext i32 %i.0 to i64
 319   %arrayidx24 = getelementptr inbounds double, ptr %vla1, i64 %idxprom23
 320   %10 = load double, ptr %arrayidx24, align 8
 321   %conv25 = sitofp i32 %j.1 to double
 322   %sub26 = fsub double %10, %conv25
 323   %idxprom27 = sext i32 %i.0 to i64
 324   %idxprom29 = sext i32 %j.1 to i64
 325   %11 = mul nsw i64 %idxprom29, %2
 326   %12 = mul nuw i64 %1, %2
 327   %13 = mul nsw i64 %idxprom27, %12
 328   %arrayidx28 = getelementptr inbounds double, ptr %vla, i64 %13
 329   %arrayidx30 = getelementptr inbounds double, ptr %arrayidx28, i64 %11
 330   %arrayidx31 = getelementptr inbounds double, ptr %arrayidx30, i64 0
 331   store double %sub26, ptr %arrayidx31, align 8
 332   br label %for.inc32
 333
 334 for.inc32:
 335   %inc33 = add nsw i32 %j.1, 1
 336   %cmp20 = icmp slt i32 %inc33, %ny
 337   br i1 %cmp20, label %imperf_nest_4_loop_j2, label %for.cond19.for.end34_crit_edge
 338
 339 for.cond19.for.end34_crit_edge:
 340   br label %for.end34
 341
 342 for.end34:
 343   br label %for.inc35
 344
 345 for.inc35:
 346   %inc36 = add nsw i32 %i.0, 1
 347   %cmp = icmp slt i32 %inc36, %nx
 348   br i1 %cmp, label %imperf_nest_4_loop_i, label %for.cond.for.end37_crit_edge
 349
 350 for.cond.for.end37_crit_edge:
 351   br label %for.end37
 352
 353 for.end37:
 354   ret void
 355 }
 356
 357 ; Test an imperfect loop nest of the form:
 358 ;   for (int i = 0; i < nx; ++i)
 359 ;     if (i > 5) {
 360 ;       for (int j = 0; j < ny; ++j)
 361 ;         y[j][i] = x[i][j] + j;
 362 ;     }
 363
 364 define void @imperf_nest_5(ptr %y, ptr %x, i32 signext %nx, i32 signext %ny) {
 365 ; CHECK-LABEL: IsPerfect=false, Depth=2, OutermostLoop: imperf_nest_5_loop_i, Loops: ( imperf_nest_5_loop_i imperf_nest_5_loop_j )
 366 entry:
 367   %cmp2 = icmp slt i32 0, %nx
 368   br i1 %cmp2, label %imperf_nest_5_loop_i.lr.ph, label %for.end13
 369
 370 imperf_nest_5_loop_i.lr.ph:
 371   br label %imperf_nest_5_loop_i
 372
 373 imperf_nest_5_loop_i:
 374   %i.0 = phi i32 [ 0, %imperf_nest_5_loop_i.lr.ph ], [ %inc12, %for.inc11 ]
 375   %cmp1 = icmp sgt i32 %i.0, 5
 376   br i1 %cmp1, label %if.then, label %if.end
 377
 378 if.then:
 379   %cmp31 = icmp slt i32 0, %ny
 380   br i1 %cmp31, label %imperf_nest_5_loop_j.lr.ph, label %for.end
 381
 382 imperf_nest_5_loop_j.lr.ph:
 383   br label %imperf_nest_5_loop_j
 384
 385 imperf_nest_5_loop_j:
 386   %j.0 = phi i32 [ 0, %imperf_nest_5_loop_j.lr.ph ], [ %inc, %for.inc ]
 387   %idxprom = sext i32 %i.0 to i64
 388   %arrayidx = getelementptr inbounds ptr, ptr %x, i64 %idxprom
 389   %0 = load ptr, ptr %arrayidx, align 8
 390   %idxprom5 = sext i32 %j.0 to i64
 391   %arrayidx6 = getelementptr inbounds i32, ptr %0, i64 %idxprom5
 392   %1 = load i32, ptr %arrayidx6, align 4
 393   %add = add nsw i32 %1, %j.0
 394   %idxprom7 = sext i32 %j.0 to i64
 395   %arrayidx8 = getelementptr inbounds ptr, ptr %y, i64 %idxprom7
 396   %2 = load ptr, ptr %arrayidx8, align 8
 397   %idxprom9 = sext i32 %i.0 to i64
 398   %arrayidx10 = getelementptr inbounds i32, ptr %2, i64 %idxprom9
 399   store i32 %add, ptr %arrayidx10, align 4
 400   br label %for.inc
 401
 402 for.inc:
 403   %inc = add nsw i32 %j.0, 1
 404   %cmp3 = icmp slt i32 %inc, %ny
 405   br i1 %cmp3, label %imperf_nest_5_loop_j, label %for.cond2.for.end_crit_edge
 406
 407 for.cond2.for.end_crit_edge:
 408   br label %for.end
 409
 410 for.end:
 411   br label %if.end
 412
 413 if.end:
 414   br label %for.inc11
 415
 416 for.inc11:
 417   %inc12 = add nsw i32 %i.0, 1
 418   %cmp = icmp slt i32 %inc12, %nx
 419   br i1 %cmp, label %imperf_nest_5_loop_i, label %for.cond.for.end13_crit_edge
 420
 421 for.cond.for.end13_crit_edge:
 422   br label %for.end13
 423
 424 for.end13:
 425   ret void
 426 }