470 lines · plain
1; RUN: opt < %s -passes='print<loopnest>' -disable-output 2>&1 | FileCheck %s2 3; Test a perfect 2-dim loop nest of the form:4; for(i=0; i<nx; ++i)5; for(j=0; j<nx; ++j)6; y[i][j] = x[i][j];7 8define void @perf_nest_2D_1(ptr %y, ptr %x, i64 signext %nx, i64 signext %ny) {9; CHECK-LABEL: IsPerfect=true, Depth=1, OutermostLoop: perf_nest_2D_1_loop_j, Loops: ( perf_nest_2D_1_loop_j )10; CHECK-LABEL: IsPerfect=true, Depth=2, OutermostLoop: perf_nest_2D_1_loop_i, Loops: ( perf_nest_2D_1_loop_i perf_nest_2D_1_loop_j )11entry:12 br label %perf_nest_2D_1_loop_i13 14perf_nest_2D_1_loop_i:15 %i = phi i64 [ 0, %entry ], [ %inc13, %inc_i ]16 %cmp21 = icmp slt i64 0, %ny17 br i1 %cmp21, label %perf_nest_2D_1_loop_j, label %inc_i18 19perf_nest_2D_1_loop_j:20 %j = phi i64 [ 0, %perf_nest_2D_1_loop_i ], [ %inc, %inc_j ]21 %arrayidx = getelementptr inbounds ptr, ptr %x, i64 %j22 %0 = load ptr, ptr %arrayidx, align 823 %arrayidx6 = getelementptr inbounds i32, ptr %0, i64 %j24 %1 = load i32, ptr %arrayidx6, align 425 %arrayidx8 = getelementptr inbounds ptr, ptr %y, i64 %j26 %2 = load ptr, ptr %arrayidx8, align 827 %arrayidx11 = getelementptr inbounds i32, ptr %2, i64 %i28 store i32 %1, ptr %arrayidx11, align 429 br label %inc_j30 31inc_j:32 %inc = add nsw i64 %j, 133 %cmp2 = icmp slt i64 %inc, %ny34 br i1 %cmp2, label %perf_nest_2D_1_loop_j, label %inc_i35 36inc_i:37 %inc13 = add nsw i64 %i, 138 %cmp = icmp slt i64 %inc13, %nx39 br i1 %cmp, label %perf_nest_2D_1_loop_i, label %perf_nest_2D_1_loop_i_end40 41perf_nest_2D_1_loop_i_end:42 ret void43}44 45; Test a perfect 2-dim loop nest of the form:46; for (i=0; i<100; ++i)47; for (j=0; j<100; ++j)48; y[i][j] = x[i][j];49define void @perf_nest_2D_2(ptr %y, ptr %x) {50; CHECK-LABEL: IsPerfect=true, Depth=1, OutermostLoop: perf_nest_2D_2_loop_j, Loops: ( perf_nest_2D_2_loop_j )51; CHECK-LABEL: IsPerfect=true, Depth=2, OutermostLoop: perf_nest_2D_2_loop_i, Loops: ( perf_nest_2D_2_loop_i perf_nest_2D_2_loop_j )52entry:53 br label %perf_nest_2D_2_loop_i54 55perf_nest_2D_2_loop_i:56 %i = phi i64 [ 0, %entry ], [ %inc13, %inc_i ]57 br label %perf_nest_2D_2_loop_j58 59perf_nest_2D_2_loop_j:60 %j = phi i64 [ 0, %perf_nest_2D_2_loop_i ], [ %inc, %inc_j ]61 %arrayidx = getelementptr inbounds ptr, ptr %x, i64 %j62 %0 = load ptr, ptr %arrayidx, align 863 %arrayidx6 = getelementptr inbounds i32, ptr %0, i64 %j64 %1 = load i32, ptr %arrayidx6, align 465 %arrayidx8 = getelementptr inbounds ptr, ptr %y, i64 %j66 %2 = load ptr, ptr %arrayidx8, align 867 %arrayidx11 = getelementptr inbounds i32, ptr %2, i64 %i68 store i32 %1, ptr %arrayidx11, align 469 br label %inc_j70 71inc_j:72 %inc = add nsw i64 %j, 173 %cmp2 = icmp slt i64 %inc, 10074 br i1 %cmp2, label %perf_nest_2D_2_loop_j, label %loop_j_end75 76loop_j_end:77 br label %inc_i78 79inc_i:80 %inc13 = add nsw i64 %i, 181 %cmp = icmp slt i64 %inc13, 10082 br i1 %cmp, label %perf_nest_2D_2_loop_i, label %perf_nest_2D_2_loop_i_end83 84perf_nest_2D_2_loop_i_end:85 ret void86}87 88define void @perf_nest_2D_3(ptr %y, ptr %x, i64 signext %nx, i64 signext %ny) {89; CHECK-LABEL: IsPerfect=true, Depth=1, OutermostLoop: perf_nest_2D_3_loop_j, Loops: ( perf_nest_2D_3_loop_j )90; CHECK-LABEL: IsPerfect=true, Depth=2, OutermostLoop: perf_nest_2D_3_loop_i, Loops: ( perf_nest_2D_3_loop_i perf_nest_2D_3_loop_j )91entry:92 br label %perf_nest_2D_3_loop_i93 94perf_nest_2D_3_loop_i:95 %i = phi i64 [ 0, %entry ], [ %inc13, %inc_i ]96 %cmp21 = icmp slt i64 0, %ny97 br label %singleSucc98 99singleSucc:100 br i1 %cmp21, label %preheader.j, label %for.end101 102preheader.j:103 br label %perf_nest_2D_3_loop_j104 105perf_nest_2D_3_loop_j:106 %j = phi i64 [ 0, %preheader.j ], [ %inc, %inc_j ]107 %arrayidx = getelementptr inbounds ptr, ptr %x, i64 %j108 %0 = load ptr, ptr %arrayidx, align 8109 %arrayidx6 = getelementptr inbounds i32, ptr %0, i64 %j110 %1 = load i32, ptr %arrayidx6, align 4111 %arrayidx8 = getelementptr inbounds ptr, ptr %y, i64 %j112 %2 = load ptr, ptr %arrayidx8, align 8113 %arrayidx11 = getelementptr inbounds i32, ptr %2, i64 %i114 store i32 %1, ptr %arrayidx11, align 4115 br label %inc_j116 117inc_j:118 %inc = add nsw i64 %j, 1119 %cmp2 = icmp slt i64 %inc, %ny120 br i1 %cmp2, label %perf_nest_2D_3_loop_j, label %for.exit121 122for.exit:123 br label %for.end124 125for.end:126 br label %inc_i127 128inc_i:129 %inc13 = add nsw i64 %i, 1130 %cmp = icmp slt i64 %inc13, %nx131 br i1 %cmp, label %perf_nest_2D_3_loop_i, label %perf_nest_2D_3_loop_i_end132 133perf_nest_2D_3_loop_i_end:134 ret void135}136 137; Test a perfect 3-dim loop nest of the form:138; for (i=0; i<nx; ++i)139; for (j=0; j<ny; ++j)140; for (k=0; j<nk; ++k)141; y[j][j][k] = x[i][j][k];142;143 144define void @perf_nest_3D_1(ptr %y, ptr %x, i32 signext %nx, i32 signext %ny, i32 signext %nk) {145; CHECK-LABEL: IsPerfect=true, Depth=1, OutermostLoop: perf_nest_3D_1_loop_k, Loops: ( perf_nest_3D_1_loop_k )146; CHECK-NEXT: IsPerfect=true, Depth=2, OutermostLoop: perf_nest_3D_1_loop_j, Loops: ( perf_nest_3D_1_loop_j perf_nest_3D_1_loop_k )147; CHECK-NEXT: IsPerfect=true, Depth=3, OutermostLoop: perf_nest_3D_1_loop_i, Loops: ( perf_nest_3D_1_loop_i perf_nest_3D_1_loop_j perf_nest_3D_1_loop_k )148entry:149 br label %perf_nest_3D_1_loop_i150 151perf_nest_3D_1_loop_i:152 %i = phi i32 [ 0, %entry ], [ %inci, %for.inci ]153 %cmp21 = icmp slt i32 0, %ny154 br i1 %cmp21, label %perf_nest_3D_1_loop_j, label %for.inci155 156perf_nest_3D_1_loop_j:157 %j = phi i32 [ 0, %perf_nest_3D_1_loop_i ], [ %incj, %for.incj ]158 %cmp22 = icmp slt i32 0, %nk159 br i1 %cmp22, label %perf_nest_3D_1_loop_k, label %for.incj160 161perf_nest_3D_1_loop_k:162 %k = phi i32 [ 0, %perf_nest_3D_1_loop_j ], [ %inck, %for.inck ]163 %idxprom = sext i32 %i to i64164 %arrayidx = getelementptr inbounds ptr, ptr %x, i64 %idxprom165 %0 = load ptr, ptr %arrayidx, align 8166 %idxprom7 = sext i32 %j to i64167 %arrayidx8 = getelementptr inbounds ptr, ptr %0, i64 %idxprom7168 %1 = load ptr, ptr %arrayidx8, align 8169 %idxprom9 = sext i32 %k to i64170 %arrayidx10 = getelementptr inbounds i32, ptr %1, i64 %idxprom9171 %2 = load i32, ptr %arrayidx10, align 4172 %idxprom11 = sext i32 %j to i64173 %arrayidx12 = getelementptr inbounds ptr, ptr %y, i64 %idxprom11174 %3 = load ptr, ptr %arrayidx12, align 8175 %idxprom13 = sext i32 %j to i64176 %arrayidx14 = getelementptr inbounds ptr, ptr %3, i64 %idxprom13177 %4 = load ptr, ptr %arrayidx14, align 8178 %idxprom15 = sext i32 %k to i64179 %arrayidx16 = getelementptr inbounds i32, ptr %4, i64 %idxprom15180 store i32 %2, ptr %arrayidx16, align 4181 br label %for.inck182 183for.inck:184 %inck = add nsw i32 %k, 1185 %cmp5 = icmp slt i32 %inck, %nk186 br i1 %cmp5, label %perf_nest_3D_1_loop_k, label %for.incj187 188for.incj:189 %incj = add nsw i32 %j, 1190 %cmp2 = icmp slt i32 %incj, %ny191 br i1 %cmp2, label %perf_nest_3D_1_loop_j, label %for.inci192 193for.inci:194 %inci = add nsw i32 %i, 1195 %cmp = icmp slt i32 %inci, %nx196 br i1 %cmp, label %perf_nest_3D_1_loop_i, label %perf_nest_3D_1_loop_i_end197 198perf_nest_3D_1_loop_i_end:199 ret void200}201 202; Test a perfect 3-dim loop nest of the form:203; for (i=0; i<100; ++i)204; for (j=0; j<100; ++j)205; for (k=0; j<100; ++k)206; y[j][j][k] = x[i][j][k];207;208 209define void @perf_nest_3D_2(ptr %y, ptr %x) {210; CHECK-LABEL: IsPerfect=true, Depth=1, OutermostLoop: perf_nest_3D_2_loop_k, Loops: ( perf_nest_3D_2_loop_k )211; CHECK-NEXT: IsPerfect=true, Depth=2, OutermostLoop: perf_nest_3D_2_loop_j, Loops: ( perf_nest_3D_2_loop_j perf_nest_3D_2_loop_k )212; CHECK-NEXT: IsPerfect=true, Depth=3, OutermostLoop: perf_nest_3D_2_loop_i, Loops: ( perf_nest_3D_2_loop_i perf_nest_3D_2_loop_j perf_nest_3D_2_loop_k )213entry:214 br label %perf_nest_3D_2_loop_i215 216perf_nest_3D_2_loop_i:217 %i = phi i32 [ 0, %entry ], [ %inci, %for.inci ]218 br label %perf_nest_3D_2_loop_j219 220perf_nest_3D_2_loop_j:221 %j = phi i32 [ 0, %perf_nest_3D_2_loop_i ], [ %incj, %for.incj ]222 br label %perf_nest_3D_2_loop_k223 224perf_nest_3D_2_loop_k:225 %k = phi i32 [ 0, %perf_nest_3D_2_loop_j ], [ %inck, %for.inck ]226 %idxprom = sext i32 %i to i64227 %arrayidx = getelementptr inbounds ptr, ptr %x, i64 %idxprom228 %0 = load ptr, ptr %arrayidx, align 8229 %idxprom7 = sext i32 %j to i64230 %arrayidx8 = getelementptr inbounds ptr, ptr %0, i64 %idxprom7231 %1 = load ptr, ptr %arrayidx8, align 8232 %idxprom9 = sext i32 %k to i64233 %arrayidx10 = getelementptr inbounds i32, ptr %1, i64 %idxprom9234 %2 = load i32, ptr %arrayidx10, align 4235 %idxprom11 = sext i32 %j to i64236 %arrayidx12 = getelementptr inbounds ptr, ptr %y, i64 %idxprom11237 %3 = load ptr, ptr %arrayidx12, align 8238 %idxprom13 = sext i32 %j to i64239 %arrayidx14 = getelementptr inbounds ptr, ptr %3, i64 %idxprom13240 %4 = load ptr, ptr %arrayidx14, align 8241 %idxprom15 = sext i32 %k to i64242 %arrayidx16 = getelementptr inbounds i32, ptr %4, i64 %idxprom15243 store i32 %2, ptr %arrayidx16, align 4244 br label %for.inck245 246for.inck:247 %inck = add nsw i32 %k, 1248 %cmp5 = icmp slt i32 %inck, 100249 br i1 %cmp5, label %perf_nest_3D_2_loop_k, label %loop_k_end250 251loop_k_end:252 br label %for.incj253 254for.incj:255 %incj = add nsw i32 %j, 1256 %cmp2 = icmp slt i32 %incj, 100257 br i1 %cmp2, label %perf_nest_3D_2_loop_j, label %loop_j_end258 259loop_j_end:260 br label %for.inci261 262for.inci:263 %inci = add nsw i32 %i, 1264 %cmp = icmp slt i32 %inci, 100265 br i1 %cmp, label %perf_nest_3D_2_loop_i, label %perf_nest_3D_2_loop_i_end266 267perf_nest_3D_2_loop_i_end:268 ret void269}270 271; Test a perfect loop nest with a live out reduction:272; for (i = 0; i<ni; ++i)273; if (0<nj) { // guard branch for the j-loop274; for (j=0; j<nj; j+=1)275; x+=(i+j);276; }277; return x;278 279define signext i32 @perf_nest_live_out(i32 signext %x, i32 signext %ni, i32 signext %nj) {280; CHECK-LABEL: IsPerfect=true, Depth=1, OutermostLoop: perf_nest_live_out_loop_j, Loops: ( perf_nest_live_out_loop_j )281; CHECK-LABEL: IsPerfect=true, Depth=2, OutermostLoop: perf_nest_live_out_loop_i, Loops: ( perf_nest_live_out_loop_i perf_nest_live_out_loop_j )282entry:283 %cmp4 = icmp slt i32 0, %ni284 br i1 %cmp4, label %perf_nest_live_out_loop_i.lr.ph, label %for.end7285 286perf_nest_live_out_loop_i.lr.ph:287 br label %perf_nest_live_out_loop_i288 289perf_nest_live_out_loop_i:290 %x.addr.06 = phi i32 [ %x, %perf_nest_live_out_loop_i.lr.ph ], [ %x.addr.1.lcssa, %for.inc5 ]291 %i.05 = phi i32 [ 0, %perf_nest_live_out_loop_i.lr.ph ], [ %inc6, %for.inc5 ]292 %cmp21 = icmp slt i32 0, %nj293 br i1 %cmp21, label %perf_nest_live_out_loop_j.lr.ph, label %for.inc5294 295perf_nest_live_out_loop_j.lr.ph:296 br label %perf_nest_live_out_loop_j297 298perf_nest_live_out_loop_j:299 %x.addr.13 = phi i32 [ %x.addr.06, %perf_nest_live_out_loop_j.lr.ph ], [ %add4, %perf_nest_live_out_loop_j ]300 %j.02 = phi i32 [ 0, %perf_nest_live_out_loop_j.lr.ph ], [ %inc, %perf_nest_live_out_loop_j ]301 %add = add nsw i32 %i.05, %j.02302 %add4 = add nsw i32 %x.addr.13, %add303 %inc = add nsw i32 %j.02, 1304 %cmp2 = icmp slt i32 %inc, %nj305 br i1 %cmp2, label %perf_nest_live_out_loop_j, label %for.cond1.for.inc5_crit_edge306 307for.cond1.for.inc5_crit_edge:308 %split = phi i32 [ %add4, %perf_nest_live_out_loop_j ]309 br label %for.inc5310 311for.inc5:312 %x.addr.1.lcssa = phi i32 [ %split, %for.cond1.for.inc5_crit_edge ], [ %x.addr.06, %perf_nest_live_out_loop_i ]313 %inc6 = add nsw i32 %i.05, 1314 %cmp = icmp slt i32 %inc6, %ni315 br i1 %cmp, label %perf_nest_live_out_loop_i, label %for.cond.for.end7_crit_edge316 317for.cond.for.end7_crit_edge:318 %split7 = phi i32 [ %x.addr.1.lcssa, %for.inc5 ]319 br label %for.end7320 321for.end7:322 %x.addr.0.lcssa = phi i32 [ %split7, %for.cond.for.end7_crit_edge ], [ %x, %entry ]323 ret i32 %x.addr.0.lcssa324}325 326; Test a perfect loop nest of the form:327; for (int i = 0; i < nx; ++i)328; if (i < ny) { // guard branch for the j-loop329; for (int j=i; j < ny; j+=1)330; y[j][i] = x[i][j] + j;331; }332define double @perf_nest_guard_branch(ptr %y, ptr %x, i32 signext %nx, i32 signext %ny) {333; CHECK-LABEL: IsPerfect=true, Depth=1, OutermostLoop: test6Loop2, Loops: ( test6Loop2 )334; CHECK-LABEL: IsPerfect=true, Depth=2, OutermostLoop: test6Loop1, Loops: ( test6Loop1 test6Loop2 )335entry:336 %cmp2 = icmp slt i32 0, %nx337 br i1 %cmp2, label %test6Loop1.lr.ph, label %for.end13338 339test6Loop1.lr.ph: ; preds = %entry340 br label %test6Loop1341 342test6Loop1: ; preds = %test6Loop1.lr.ph, %for.inc11343 %i.0 = phi i32 [ 0, %test6Loop1.lr.ph ], [ %inc12, %for.inc11 ]344 %cmp1 = icmp slt i32 %i.0, %ny345 br i1 %cmp1, label %test6Loop2.lr.ph, label %if.end346 347test6Loop2.lr.ph: ; preds = %if.then348 br label %test6Loop2349 350test6Loop2: ; preds = %test6Loop2.lr.ph, %for.inc351 %j.0 = phi i32 [ %i.0, %test6Loop2.lr.ph ], [ %inc, %for.inc ]352 %idxprom = sext i32 %i.0 to i64353 %arrayidx = getelementptr inbounds ptr, ptr %x, i64 %idxprom354 %0 = load ptr, ptr %arrayidx, align 8355 %idxprom5 = sext i32 %j.0 to i64356 %arrayidx6 = getelementptr inbounds i32, ptr %0, i64 %idxprom5357 %1 = load i32, ptr %arrayidx6, align 4358 %add = add nsw i32 %1, %j.0359 %idxprom7 = sext i32 %j.0 to i64360 %arrayidx8 = getelementptr inbounds ptr, ptr %y, i64 %idxprom7361 %2 = load ptr, ptr %arrayidx8, align 8362 %idxprom9 = sext i32 %i.0 to i64363 %arrayidx10 = getelementptr inbounds i32, ptr %2, i64 %idxprom9364 store i32 %add, ptr %arrayidx10, align 4365 br label %for.inc366 367for.inc: ; preds = %test6Loop2368 %inc = add nsw i32 %j.0, 1369 %cmp3 = icmp slt i32 %inc, %ny370 br i1 %cmp3, label %test6Loop2, label %for.cond2.for.end_crit_edge371 372for.cond2.for.end_crit_edge: ; preds = %for.inc373 br label %for.end374 375for.end: ; preds = %for.cond2.for.end_crit_edge, %if.then376 br label %if.end377 378if.end: ; preds = %for.end, %test6Loop1379 br label %for.inc11380 381for.inc11: ; preds = %if.end382 %inc12 = add nsw i32 %i.0, 1383 %cmp = icmp slt i32 %inc12, %nx384 br i1 %cmp, label %test6Loop1, label %for.cond.for.end13_crit_edge385 386for.cond.for.end13_crit_edge: ; preds = %for.inc11387 br label %for.end13388 389for.end13: ; preds = %for.cond.for.end13_crit_edge, %entry390 %arrayidx14 = getelementptr inbounds ptr, ptr %y, i64 0391 %3 = load ptr, ptr %arrayidx14, align 8392 %arrayidx15 = getelementptr inbounds i32, ptr %3, i64 0393 %4 = load i32, ptr %arrayidx15, align 4394 %conv = sitofp i32 %4 to double395 ret double %conv396}397 398; Test a perfect loop nest of the form:399; for (int i = 0; i < nx; ++i)400; if (i < ny) { // guard branch for the j-loop401; for (int j=i; j < ny; j+=1)402; y[j][i] = x[i][j] + j;403; }404 405define double @test6(ptr %y, ptr %x, i32 signext %nx, i32 signext %ny) {406; CHECK-LABEL: IsPerfect=true, Depth=1, OutermostLoop: test6Loop2, Loops: ( test6Loop2 )407; CHECK-LABEL: IsPerfect=true, Depth=2, OutermostLoop: test6Loop1, Loops: ( test6Loop1 test6Loop2 )408entry:409 %cmp2 = icmp slt i32 0, %nx410 br i1 %cmp2, label %test6Loop1.lr.ph, label %for.end13411 412test6Loop1.lr.ph: ; preds = %entry413 br label %test6Loop1414 415test6Loop1: ; preds = %test6Loop1.lr.ph, %for.inc11416 %i.0 = phi i32 [ 0, %test6Loop1.lr.ph ], [ %inc12, %for.inc11 ]417 %cmp1 = icmp slt i32 %i.0, %ny418 br i1 %cmp1, label %test6Loop2.lr.ph, label %if.end419 420test6Loop2.lr.ph: ; preds = %if.then421 br label %test6Loop2422 423test6Loop2: ; preds = %test6Loop2.lr.ph, %for.inc424 %j.0 = phi i32 [ %i.0, %test6Loop2.lr.ph ], [ %inc, %for.inc ]425 %idxprom = sext i32 %i.0 to i64426 %arrayidx = getelementptr inbounds ptr, ptr %x, i64 %idxprom427 %0 = load ptr, ptr %arrayidx, align 8428 %idxprom5 = sext i32 %j.0 to i64429 %arrayidx6 = getelementptr inbounds i32, ptr %0, i64 %idxprom5430 %1 = load i32, ptr %arrayidx6, align 4431 %add = add nsw i32 %1, %j.0432 %idxprom7 = sext i32 %j.0 to i64433 %arrayidx8 = getelementptr inbounds ptr, ptr %y, i64 %idxprom7434 %2 = load ptr, ptr %arrayidx8, align 8435 %idxprom9 = sext i32 %i.0 to i64436 %arrayidx10 = getelementptr inbounds i32, ptr %2, i64 %idxprom9437 store i32 %add, ptr %arrayidx10, align 4438 br label %for.inc439 440for.inc: ; preds = %test6Loop2441 %inc = add nsw i32 %j.0, 1442 %cmp3 = icmp slt i32 %inc, %ny443 br i1 %cmp3, label %test6Loop2, label %for.cond2.for.end_crit_edge444 445for.cond2.for.end_crit_edge: ; preds = %for.inc446 br label %for.end447 448for.end: ; preds = %for.cond2.for.end_crit_edge, %if.then449 br label %if.end450 451if.end: ; preds = %for.end, %test6Loop1452 br label %for.inc11453 454for.inc11: ; preds = %if.end455 %inc12 = add nsw i32 %i.0, 1456 %cmp = icmp slt i32 %inc12, %nx457 br i1 %cmp, label %test6Loop1, label %for.cond.for.end13_crit_edge458 459for.cond.for.end13_crit_edge: ; preds = %for.inc11460 br label %for.end13461 462for.end13: ; preds = %for.cond.for.end13_crit_edge, %entry463 %arrayidx14 = getelementptr inbounds ptr, ptr %y, i64 0464 %3 = load ptr, ptr %arrayidx14, align 8465 %arrayidx15 = getelementptr inbounds i32, ptr %3, i64 0466 %4 = load i32, ptr %arrayidx15, align 4467 %conv = sitofp i32 %4 to double468 ret double %conv469}470