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 10define 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 ) 12entry: 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 21imperf_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 26for.body: 27 %conv = sitofp i32 %i2.0 to double 28 %idxprom = sext i32 %i2.0 to i64 29 %arrayidx = getelementptr inbounds double, double* %vla1, i64 %idxprom 30 store double %conv, double* %arrayidx, align 8 31 br label %imperf_nest_1_loop_j 32 33imperf_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 38for.body7: 39 %idxprom8 = sext i32 %i2.0 to i64 40 %arrayidx9 = getelementptr inbounds double, double* %vla1, i64 %idxprom8 41 %4 = load double, double* %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, double* %vla, i64 %5 47 %idxprom13 = sext i32 %i2.0 to i64 48 %arrayidx14 = getelementptr inbounds double, double* %arrayidx12, i64 %idxprom13 49 store double %add, double* %arrayidx14, align 8 50 br label %for.inc 51 52for.inc: 53 %inc = add nsw i32 %j3.0, 1 54 br label %imperf_nest_1_loop_j 55 56for.end: 57 br label %for.inc15 58 59for.inc15: 60 %inc16 = add nsw i32 %i2.0, 1 61 br label %imperf_nest_1_loop_i 62 63for.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 74define 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 ) 76entry: 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 85imperf_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 90for.body: 91 br label %imperf_nest_2_loop_j 92 93imperf_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 98for.body6: 99 %idxprom = sext i32 %i2.0 to i64 100 %arrayidx = getelementptr inbounds double, double* %vla1, i64 %idxprom 101 %4 = load double, double* %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, double* %vla, i64 %5 107 %idxprom9 = sext i32 %i2.0 to i64 108 %arrayidx10 = getelementptr inbounds double, double* %arrayidx8, i64 %idxprom9 109 store double %add, double* %arrayidx10, align 8 110 br label %for.inc 111 112for.inc: 113 %inc = add nsw i32 %j3.0, 1 114 br label %imperf_nest_2_loop_j 115 116for.end: 117 %conv11 = sitofp i32 %i2.0 to double 118 %6 = mul nsw i64 0, %1 119 %arrayidx12 = getelementptr inbounds double, double* %vla, i64 %6 120 %idxprom13 = sext i32 %i2.0 to i64 121 %arrayidx14 = getelementptr inbounds double, double* %arrayidx12, i64 %idxprom13 122 %7 = load double, double* %arrayidx14, align 8 123 %add15 = fadd double %7, %conv11 124 store double %add15, double* %arrayidx14, align 8 125 br label %for.inc16 126 127for.inc16: 128 %inc17 = add nsw i32 %i2.0, 1 129 br label %imperf_nest_2_loop_i 130 131for.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 143define 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 ) 145entry: 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 154imperf_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 159for.body: ; preds = %for.cond 160 br label %imperf_nest_3_loop_j 161 162imperf_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 168for.body4: ; preds = %imperf_nest_3_loop_j 169 %idxprom = sext i32 %i.0 to i64 170 %arrayidx = getelementptr inbounds double, double* %vla1, i64 %idxprom 171 %4 = load double, double* %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, double* %vla, i64 %5 177 %idxprom7 = sext i32 %j.0 to i64 178 %arrayidx8 = getelementptr inbounds double, double* %arrayidx6, i64 %idxprom7 179 store double %add, double* %arrayidx8, align 8 180 br label %for.inc 181 182for.inc: ; preds = %for.body4 183 %inc = add nsw i32 %j.0, 1 184 br label %imperf_nest_3_loop_j 185 186for.end: ; preds = %imperf_nest_3_loop_j 187 %sub9 = sub nsw i32 %ny, %nk 188 br label %imperf_nest_3_loop_k 189 190imperf_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 195for.body13: ; preds = %imperf_nest_3_loop_k 196 %idxprom14 = sext i32 %i.0 to i64 197 %arrayidx15 = getelementptr inbounds double, double* %vla1, i64 %idxprom14 198 %6 = load double, double* %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, double* %vla, i64 %7 204 %idxprom20 = sext i32 %j.1 to i64 205 %arrayidx21 = getelementptr inbounds double, double* %arrayidx19, i64 %idxprom20 206 store double %sub17, double* %arrayidx21, align 8 207 br label %for.inc22 208 209for.inc22: ; preds = %for.body13 210 %inc23 = add nsw i32 %j.1, 1 211 br label %imperf_nest_3_loop_k 212 213for.end24: ; preds = %imperf_nest_3_loop_k 214 br label %for.inc25 215 216for.inc25: ; preds = %for.end24 217 %inc26 = add nsw i32 %i.0, 1 218 br label %imperf_nest_3_loop_i 219 220for.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 233define 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 ) 236entry: 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 248imperf_nest_4_loop_i.lr.ph: 249 br label %imperf_nest_4_loop_i 250 251imperf_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 257imperf_nest_4_loop_j.lr.ph: 258 br label %imperf_nest_4_loop_j 259 260imperf_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 265imperf_nest_4_loop_k.lr.ph: 266 br label %imperf_nest_4_loop_k 267 268imperf_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, double* %vla1, i64 %idxprom 273 %6 = load double, double* %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, double* %vla, i64 %8 280 %idxprom11 = sext i32 %j.0 to i64 281 %9 = mul nsw i64 %idxprom11, %2 282 %arrayidx12 = getelementptr inbounds double, double* %arrayidx10, i64 %9 283 %idxprom13 = sext i32 %k.0 to i64 284 %arrayidx14 = getelementptr inbounds double, double* %arrayidx12, i64 %idxprom13 285 store double %add8, double* %arrayidx14, align 8 286 br label %for.inc 287 288for.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 293for.cond5.for.end_crit_edge: 294 br label %for.end 295 296for.end: 297 br label %for.inc15 298 299for.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 305for.cond2.for.end17_crit_edge: 306 br label %for.end17 307 308for.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 313imperf_nest_4_loop_j2.lr.ph: 314 br label %imperf_nest_4_loop_j2 315 316imperf_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, double* %vla1, i64 %idxprom23 320 %10 = load double, double* %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, double* %vla, i64 %13 329 %arrayidx30 = getelementptr inbounds double, double* %arrayidx28, i64 %11 330 %arrayidx31 = getelementptr inbounds double, double* %arrayidx30, i64 0 331 store double %sub26, double* %arrayidx31, align 8 332 br label %for.inc32 333 334for.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 339for.cond19.for.end34_crit_edge: 340 br label %for.end34 341 342for.end34: 343 br label %for.inc35 344 345for.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 350for.cond.for.end37_crit_edge: 351 br label %for.end37 352 353for.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 364define void @imperf_nest_5(i32** %y, i32** %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 ) 366entry: 367 %cmp2 = icmp slt i32 0, %nx 368 br i1 %cmp2, label %imperf_nest_5_loop_i.lr.ph, label %for.end13 369 370imperf_nest_5_loop_i.lr.ph: 371 br label %imperf_nest_5_loop_i 372 373imperf_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 378if.then: 379 %cmp31 = icmp slt i32 0, %ny 380 br i1 %cmp31, label %imperf_nest_5_loop_j.lr.ph, label %for.end 381 382imperf_nest_5_loop_j.lr.ph: 383 br label %imperf_nest_5_loop_j 384 385imperf_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 i32*, i32** %x, i64 %idxprom 389 %0 = load i32*, i32** %arrayidx, align 8 390 %idxprom5 = sext i32 %j.0 to i64 391 %arrayidx6 = getelementptr inbounds i32, i32* %0, i64 %idxprom5 392 %1 = load i32, i32* %arrayidx6, align 4 393 %add = add nsw i32 %1, %j.0 394 %idxprom7 = sext i32 %j.0 to i64 395 %arrayidx8 = getelementptr inbounds i32*, i32** %y, i64 %idxprom7 396 %2 = load i32*, i32** %arrayidx8, align 8 397 %idxprom9 = sext i32 %i.0 to i64 398 %arrayidx10 = getelementptr inbounds i32, i32* %2, i64 %idxprom9 399 store i32 %add, i32* %arrayidx10, align 4 400 br label %for.inc 401 402for.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 407for.cond2.for.end_crit_edge: 408 br label %for.end 409 410for.end: 411 br label %if.end 412 413if.end: 414 br label %for.inc11 415 416for.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 421for.cond.for.end13_crit_edge: 422 br label %for.end13 423 424for.end13: 425 ret void 426} 427 428; Test an imperfect loop nest of the form: 429; for (int i = 0; i < nx; ++i) 430; if (i > 5) { // user branch 431; for (int j = 1; j <= 5; j+=2) 432; y[j][i] = x[i][j] + j; 433; } 434 435define void @imperf_nest_6(i32** %y, i32** %x, i32 signext %nx, i32 signext %ny) { 436; CHECK-LABEL: IsPerfect=false, Depth=2, OutermostLoop: imperf_nest_6_loop_i, Loops: ( imperf_nest_6_loop_i imperf_nest_6_loop_j ) 437entry: 438 %cmp2 = icmp slt i32 0, %nx 439 br i1 %cmp2, label %imperf_nest_6_loop_i.lr.ph, label %for.end13 440 441imperf_nest_6_loop_i.lr.ph: 442 br label %imperf_nest_6_loop_i 443 444imperf_nest_6_loop_i: 445 %i.0 = phi i32 [ 0, %imperf_nest_6_loop_i.lr.ph ], [ %inc12, %for.inc11 ] 446 %cmp1 = icmp sgt i32 %i.0, 5 447 br i1 %cmp1, label %imperf_nest_6_loop_j.lr.ph, label %if.end 448 449imperf_nest_6_loop_j.lr.ph: 450 br label %imperf_nest_6_loop_j 451 452imperf_nest_6_loop_j: 453 %j.0 = phi i32 [ 1, %imperf_nest_6_loop_j.lr.ph ], [ %inc, %for.inc ] 454 %idxprom = sext i32 %i.0 to i64 455 %arrayidx = getelementptr inbounds i32*, i32** %x, i64 %idxprom 456 %0 = load i32*, i32** %arrayidx, align 8 457 %idxprom5 = sext i32 %j.0 to i64 458 %arrayidx6 = getelementptr inbounds i32, i32* %0, i64 %idxprom5 459 %1 = load i32, i32* %arrayidx6, align 4 460 %add = add nsw i32 %1, %j.0 461 %idxprom7 = sext i32 %j.0 to i64 462 %arrayidx8 = getelementptr inbounds i32*, i32** %y, i64 %idxprom7 463 %2 = load i32*, i32** %arrayidx8, align 8 464 %idxprom9 = sext i32 %i.0 to i64 465 %arrayidx10 = getelementptr inbounds i32, i32* %2, i64 %idxprom9 466 store i32 %add, i32* %arrayidx10, align 4 467 br label %for.inc 468 469for.inc: 470 %inc = add nsw i32 %j.0, 2 471 %cmp3 = icmp sle i32 %inc, 5 472 br i1 %cmp3, label %imperf_nest_6_loop_j, label %for.cond2.for.end_crit_edge 473 474for.cond2.for.end_crit_edge: 475 br label %for.end 476 477for.end: 478 br label %if.end 479 480if.end: 481 br label %for.inc11 482 483for.inc11: 484 %inc12 = add nsw i32 %i.0, 1 485 %cmp = icmp slt i32 %inc12, %nx 486 br i1 %cmp, label %imperf_nest_6_loop_i, label %for.cond.for.end13_crit_edge 487 488for.cond.for.end13_crit_edge: 489 br label %for.end13 490 491for.end13: 492 ret void 493} 494