427 lines · plain
1; RUN: opt < %s -passes='print<loopnest>' -disable-output 2>&1 | FileCheck %s2 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 i6414 %1 = zext i32 %nx to i6415 %2 = mul nuw i64 %0, %116 %vla = alloca double, i64 %2, align 817 %3 = zext i32 %ny to i6418 %vla1 = alloca double, i64 %3, align 819 br label %imperf_nest_1_loop_i20 21imperf_nest_1_loop_i:22 %i2.0 = phi i32 [ 0, %entry ], [ %inc16, %for.inc15 ]23 %cmp = icmp slt i32 %i2.0, %nx24 br i1 %cmp, label %for.body, label %for.end1725 26for.body:27 %conv = sitofp i32 %i2.0 to double28 %idxprom = sext i32 %i2.0 to i6429 %arrayidx = getelementptr inbounds double, ptr %vla1, i64 %idxprom30 store double %conv, ptr %arrayidx, align 831 br label %imperf_nest_1_loop_j32 33imperf_nest_1_loop_j:34 %j3.0 = phi i32 [ 0, %for.body ], [ %inc, %for.inc ]35 %cmp5 = icmp slt i32 %j3.0, %ny36 br i1 %cmp5, label %for.body7, label %for.end37 38for.body7:39 %idxprom8 = sext i32 %i2.0 to i6440 %arrayidx9 = getelementptr inbounds double, ptr %vla1, i64 %idxprom841 %4 = load double, ptr %arrayidx9, align 842 %conv10 = sitofp i32 %j3.0 to double43 %add = fadd double %4, %conv1044 %idxprom11 = sext i32 %j3.0 to i6445 %5 = mul nsw i64 %idxprom11, %146 %arrayidx12 = getelementptr inbounds double, ptr %vla, i64 %547 %idxprom13 = sext i32 %i2.0 to i6448 %arrayidx14 = getelementptr inbounds double, ptr %arrayidx12, i64 %idxprom1349 store double %add, ptr %arrayidx14, align 850 br label %for.inc51 52for.inc:53 %inc = add nsw i32 %j3.0, 154 br label %imperf_nest_1_loop_j55 56for.end:57 br label %for.inc1558 59for.inc15:60 %inc16 = add nsw i32 %i2.0, 161 br label %imperf_nest_1_loop_i62 63for.end17:64 ret void65}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 i6478 %1 = zext i32 %nx to i6479 %2 = mul nuw i64 %0, %180 %vla = alloca double, i64 %2, align 881 %3 = zext i32 %ny to i6482 %vla1 = alloca double, i64 %3, align 883 br label %imperf_nest_2_loop_i84 85imperf_nest_2_loop_i:86 %i2.0 = phi i32 [ 0, %entry ], [ %inc17, %for.inc16 ]87 %cmp = icmp slt i32 %i2.0, %nx88 br i1 %cmp, label %for.body, label %for.end1889 90for.body:91 br label %imperf_nest_2_loop_j92 93imperf_nest_2_loop_j:94 %j3.0 = phi i32 [ 0, %for.body ], [ %inc, %for.inc ]95 %cmp5 = icmp slt i32 %j3.0, %ny96 br i1 %cmp5, label %for.body6, label %for.end97 98for.body6:99 %idxprom = sext i32 %i2.0 to i64100 %arrayidx = getelementptr inbounds double, ptr %vla1, i64 %idxprom101 %4 = load double, ptr %arrayidx, align 8102 %conv = sitofp i32 %j3.0 to double103 %add = fadd double %4, %conv104 %idxprom7 = sext i32 %j3.0 to i64105 %5 = mul nsw i64 %idxprom7, %1106 %arrayidx8 = getelementptr inbounds double, ptr %vla, i64 %5107 %idxprom9 = sext i32 %i2.0 to i64108 %arrayidx10 = getelementptr inbounds double, ptr %arrayidx8, i64 %idxprom9109 store double %add, ptr %arrayidx10, align 8110 br label %for.inc111 112for.inc:113 %inc = add nsw i32 %j3.0, 1114 br label %imperf_nest_2_loop_j115 116for.end:117 %conv11 = sitofp i32 %i2.0 to double118 %6 = mul nsw i64 0, %1119 %arrayidx12 = getelementptr inbounds double, ptr %vla, i64 %6120 %idxprom13 = sext i32 %i2.0 to i64121 %arrayidx14 = getelementptr inbounds double, ptr %arrayidx12, i64 %idxprom13122 %7 = load double, ptr %arrayidx14, align 8123 %add15 = fadd double %7, %conv11124 store double %add15, ptr %arrayidx14, align 8125 br label %for.inc16126 127for.inc16:128 %inc17 = add nsw i32 %i2.0, 1129 br label %imperf_nest_2_loop_i130 131for.end18:132 ret void133}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 i64147 %1 = zext i32 %ny to i64148 %2 = mul nuw i64 %0, %1149 %vla = alloca double, i64 %2, align 8150 %3 = zext i32 %ny to i64151 %vla1 = alloca double, i64 %3, align 8152 br label %imperf_nest_3_loop_i153 154imperf_nest_3_loop_i: ; preds = %for.inc25, %entry155 %i.0 = phi i32 [ 0, %entry ], [ %inc26, %for.inc25 ]156 %cmp = icmp slt i32 %i.0, %nx157 br i1 %cmp, label %for.body, label %for.end27158 159for.body: ; preds = %for.cond160 br label %imperf_nest_3_loop_j161 162imperf_nest_3_loop_j: ; preds = %for.inc, %for.body163 %j.0 = phi i32 [ 0, %for.body ], [ %inc, %for.inc ]164 %sub = sub nsw i32 %ny, %nk165 %cmp3 = icmp slt i32 %j.0, %sub166 br i1 %cmp3, label %for.body4, label %for.end167 168for.body4: ; preds = %imperf_nest_3_loop_j169 %idxprom = sext i32 %i.0 to i64170 %arrayidx = getelementptr inbounds double, ptr %vla1, i64 %idxprom171 %4 = load double, ptr %arrayidx, align 8172 %conv = sitofp i32 %j.0 to double173 %add = fadd double %4, %conv174 %idxprom5 = sext i32 %i.0 to i64175 %5 = mul nsw i64 %idxprom5, %1176 %arrayidx6 = getelementptr inbounds double, ptr %vla, i64 %5177 %idxprom7 = sext i32 %j.0 to i64178 %arrayidx8 = getelementptr inbounds double, ptr %arrayidx6, i64 %idxprom7179 store double %add, ptr %arrayidx8, align 8180 br label %for.inc181 182for.inc: ; preds = %for.body4183 %inc = add nsw i32 %j.0, 1184 br label %imperf_nest_3_loop_j185 186for.end: ; preds = %imperf_nest_3_loop_j187 %sub9 = sub nsw i32 %ny, %nk188 br label %imperf_nest_3_loop_k189 190imperf_nest_3_loop_k: ; preds = %for.inc22, %for.end191 %j.1 = phi i32 [ %sub9, %for.end ], [ %inc23, %for.inc22 ]192 %cmp11 = icmp slt i32 %j.1, %ny193 br i1 %cmp11, label %for.body13, label %for.end24194 195for.body13: ; preds = %imperf_nest_3_loop_k196 %idxprom14 = sext i32 %i.0 to i64197 %arrayidx15 = getelementptr inbounds double, ptr %vla1, i64 %idxprom14198 %6 = load double, ptr %arrayidx15, align 8199 %conv16 = sitofp i32 %j.1 to double200 %sub17 = fsub double %6, %conv16201 %idxprom18 = sext i32 %i.0 to i64202 %7 = mul nsw i64 %idxprom18, %1203 %arrayidx19 = getelementptr inbounds double, ptr %vla, i64 %7204 %idxprom20 = sext i32 %j.1 to i64205 %arrayidx21 = getelementptr inbounds double, ptr %arrayidx19, i64 %idxprom20206 store double %sub17, ptr %arrayidx21, align 8207 br label %for.inc22208 209for.inc22: ; preds = %for.body13210 %inc23 = add nsw i32 %j.1, 1211 br label %imperf_nest_3_loop_k212 213for.end24: ; preds = %imperf_nest_3_loop_k214 br label %for.inc25215 216for.inc25: ; preds = %for.end24217 %inc26 = add nsw i32 %i.0, 1218 br label %imperf_nest_3_loop_i219 220for.end27: ; preds = %for.cond221 ret void222}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 i64238 %1 = zext i32 %ny to i64239 %2 = zext i32 %nk to i64240 %3 = mul nuw i64 %0, %1241 %4 = mul nuw i64 %3, %2242 %vla = alloca double, i64 %4, align 8243 %5 = zext i32 %ny to i64244 %vla1 = alloca double, i64 %5, align 8245 %cmp5 = icmp slt i32 0, %nx246 br i1 %cmp5, label %imperf_nest_4_loop_i.lr.ph, label %for.end37247 248imperf_nest_4_loop_i.lr.ph:249 br label %imperf_nest_4_loop_i250 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, %nk254 %cmp33 = icmp slt i32 0, %sub2255 br i1 %cmp33, label %imperf_nest_4_loop_j.lr.ph, label %for.end17256 257imperf_nest_4_loop_j.lr.ph:258 br label %imperf_nest_4_loop_j259 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, %nk263 br i1 %cmp61, label %imperf_nest_4_loop_k.lr.ph, label %for.end264 265imperf_nest_4_loop_k.lr.ph:266 br label %imperf_nest_4_loop_k267 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.0271 %idxprom = sext i32 %add to i64272 %arrayidx = getelementptr inbounds double, ptr %vla1, i64 %idxprom273 %6 = load double, ptr %arrayidx, align 8274 %conv = sitofp i32 %k.0 to double275 %add8 = fadd double %6, %conv276 %idxprom9 = sext i32 %i.0 to i64277 %7 = mul nuw i64 %1, %2278 %8 = mul nsw i64 %idxprom9, %7279 %arrayidx10 = getelementptr inbounds double, ptr %vla, i64 %8280 %idxprom11 = sext i32 %j.0 to i64281 %9 = mul nsw i64 %idxprom11, %2282 %arrayidx12 = getelementptr inbounds double, ptr %arrayidx10, i64 %9283 %idxprom13 = sext i32 %k.0 to i64284 %arrayidx14 = getelementptr inbounds double, ptr %arrayidx12, i64 %idxprom13285 store double %add8, ptr %arrayidx14, align 8286 br label %for.inc287 288for.inc:289 %inc = add nsw i32 %k.0, 1290 %cmp6 = icmp slt i32 %inc, %nk291 br i1 %cmp6, label %imperf_nest_4_loop_k, label %for.cond5.for.end_crit_edge292 293for.cond5.for.end_crit_edge:294 br label %for.end295 296for.end:297 br label %for.inc15298 299for.inc15:300 %inc16 = add nsw i32 %j.0, 1301 %sub = sub nsw i32 %ny, %nk302 %cmp3 = icmp slt i32 %inc16, %sub303 br i1 %cmp3, label %imperf_nest_4_loop_j, label %for.cond2.for.end17_crit_edge304 305for.cond2.for.end17_crit_edge:306 br label %for.end17307 308for.end17:309 %sub18 = sub nsw i32 %ny, %nk310 %cmp204 = icmp slt i32 %sub18, %ny311 br i1 %cmp204, label %imperf_nest_4_loop_j2.lr.ph, label %for.end34312 313imperf_nest_4_loop_j2.lr.ph:314 br label %imperf_nest_4_loop_j2315 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 i64319 %arrayidx24 = getelementptr inbounds double, ptr %vla1, i64 %idxprom23320 %10 = load double, ptr %arrayidx24, align 8321 %conv25 = sitofp i32 %j.1 to double322 %sub26 = fsub double %10, %conv25323 %idxprom27 = sext i32 %i.0 to i64324 %idxprom29 = sext i32 %j.1 to i64325 %11 = mul nsw i64 %idxprom29, %2326 %12 = mul nuw i64 %1, %2327 %13 = mul nsw i64 %idxprom27, %12328 %arrayidx28 = getelementptr inbounds double, ptr %vla, i64 %13329 %arrayidx30 = getelementptr inbounds double, ptr %arrayidx28, i64 %11330 %arrayidx31 = getelementptr inbounds double, ptr %arrayidx30, i64 0331 store double %sub26, ptr %arrayidx31, align 8332 br label %for.inc32333 334for.inc32:335 %inc33 = add nsw i32 %j.1, 1336 %cmp20 = icmp slt i32 %inc33, %ny337 br i1 %cmp20, label %imperf_nest_4_loop_j2, label %for.cond19.for.end34_crit_edge338 339for.cond19.for.end34_crit_edge:340 br label %for.end34341 342for.end34: 343 br label %for.inc35344 345for.inc35: 346 %inc36 = add nsw i32 %i.0, 1347 %cmp = icmp slt i32 %inc36, %nx348 br i1 %cmp, label %imperf_nest_4_loop_i, label %for.cond.for.end37_crit_edge349 350for.cond.for.end37_crit_edge:351 br label %for.end37352 353for.end37:354 ret void355}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(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 )366entry:367 %cmp2 = icmp slt i32 0, %nx368 br i1 %cmp2, label %imperf_nest_5_loop_i.lr.ph, label %for.end13369 370imperf_nest_5_loop_i.lr.ph:371 br label %imperf_nest_5_loop_i372 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, 5376 br i1 %cmp1, label %if.then, label %if.end377 378if.then: 379 %cmp31 = icmp slt i32 0, %ny380 br i1 %cmp31, label %imperf_nest_5_loop_j.lr.ph, label %for.end381 382imperf_nest_5_loop_j.lr.ph:383 br label %imperf_nest_5_loop_j384 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 i64388 %arrayidx = getelementptr inbounds ptr, ptr %x, i64 %idxprom389 %0 = load ptr, ptr %arrayidx, align 8390 %idxprom5 = sext i32 %j.0 to i64391 %arrayidx6 = getelementptr inbounds i32, ptr %0, i64 %idxprom5392 %1 = load i32, ptr %arrayidx6, align 4393 %add = add nsw i32 %1, %j.0394 %idxprom7 = sext i32 %j.0 to i64395 %arrayidx8 = getelementptr inbounds ptr, ptr %y, i64 %idxprom7396 %2 = load ptr, ptr %arrayidx8, align 8397 %idxprom9 = sext i32 %i.0 to i64398 %arrayidx10 = getelementptr inbounds i32, ptr %2, i64 %idxprom9399 store i32 %add, ptr %arrayidx10, align 4400 br label %for.inc401 402for.inc:403 %inc = add nsw i32 %j.0, 1404 %cmp3 = icmp slt i32 %inc, %ny405 br i1 %cmp3, label %imperf_nest_5_loop_j, label %for.cond2.for.end_crit_edge406 407for.cond2.for.end_crit_edge:408 br label %for.end409 410for.end: 411 br label %if.end412 413if.end: 414 br label %for.inc11415 416for.inc11: 417 %inc12 = add nsw i32 %i.0, 1418 %cmp = icmp slt i32 %inc12, %nx419 br i1 %cmp, label %imperf_nest_5_loop_i, label %for.cond.for.end13_crit_edge420 421for.cond.for.end13_crit_edge:422 br label %for.end13423 424for.end13: 425 ret void426}427