508 lines · plain
1; NOTE: Assertions have been autogenerated by utils/update_analyze_test_checks.py2; RUN: opt -disable-output "-passes=print<scalar-evolution>" -S -scalar-evolution-classify-expressions=0 < %s 2>&1 | FileCheck %s3 4; Every combination of5; - starting at 0, 1, or %x6; - steping by 1 or 27; - stopping at %n or ptr28; - using nsw, or not9 10; Some of these represent missed opportunities.11 12define void @foo(i4 %n) {13; CHECK-LABEL: 'foo'14; CHECK-NEXT: Determining loop execution counts for: @foo15; CHECK-NEXT: Loop %loop: backedge-taken count is (-1 + %n)16; CHECK-NEXT: Loop %loop: constant max backedge-taken count is i4 617; CHECK-NEXT: Loop %loop: symbolic max backedge-taken count is (-1 + %n)18; CHECK-NEXT: Loop %loop: Trip multiple is 119;20entry:21 %s = icmp sgt i4 %n, 022 br i1 %s, label %loop, label %exit23loop:24 %i = phi i4 [ 0, %entry ], [ %i.next, %loop ]25 %i.next = add i4 %i, 126 %t = icmp slt i4 %i.next, %n27 br i1 %t, label %loop, label %exit28exit:29 ret void30}31 32define void @step2(i4 %n) {33; CHECK-LABEL: 'step2'34; CHECK-NEXT: Determining loop execution counts for: @step235; CHECK-NEXT: Loop %loop: Unpredictable backedge-taken count.36; CHECK-NEXT: Loop %loop: Unpredictable constant max backedge-taken count.37; CHECK-NEXT: Loop %loop: Unpredictable symbolic max backedge-taken count.38;39entry:40 %s = icmp sgt i4 %n, 041 br i1 %s, label %loop, label %exit42loop:43 %i = phi i4 [ 0, %entry ], [ %i.next, %loop ]44 %i.next = add i4 %i, 245 %t = icmp slt i4 %i.next, %n46 br i1 %t, label %loop, label %exit47exit:48 ret void49}50 51define void @start1(i4 %n) {52; CHECK-LABEL: 'start1'53; CHECK-NEXT: Determining loop execution counts for: @start154; CHECK-NEXT: Loop %loop: backedge-taken count is (-2 + (2 smax %n))<nsw>55; CHECK-NEXT: Loop %loop: constant max backedge-taken count is i4 556; CHECK-NEXT: Loop %loop: symbolic max backedge-taken count is (-2 + (2 smax %n))<nsw>57; CHECK-NEXT: Loop %loop: Trip multiple is 158;59entry:60 %s = icmp sgt i4 %n, 061 br i1 %s, label %loop, label %exit62loop:63 %i = phi i4 [ 1, %entry ], [ %i.next, %loop ]64 %i.next = add i4 %i, 165 %t = icmp slt i4 %i.next, %n66 br i1 %t, label %loop, label %exit67exit:68 ret void69}70 71define void @start1_step2(i4 %n) {72; CHECK-LABEL: 'start1_step2'73; CHECK-NEXT: Determining loop execution counts for: @start1_step274; CHECK-NEXT: Loop %loop: Unpredictable backedge-taken count.75; CHECK-NEXT: Loop %loop: Unpredictable constant max backedge-taken count.76; CHECK-NEXT: Loop %loop: Unpredictable symbolic max backedge-taken count.77;78entry:79 %s = icmp sgt i4 %n, 080 br i1 %s, label %loop, label %exit81loop:82 %i = phi i4 [ 1, %entry ], [ %i.next, %loop ]83 %i.next = add i4 %i, 284 %t = icmp slt i4 %i.next, %n85 br i1 %t, label %loop, label %exit86exit:87 ret void88}89 90define void @startx(i4 %n, i4 %x) {91; CHECK-LABEL: 'startx'92; CHECK-NEXT: Determining loop execution counts for: @startx93; CHECK-NEXT: Loop %loop: backedge-taken count is (-1 + (-1 * %x) + ((1 + %x) smax %n))94; CHECK-NEXT: Loop %loop: constant max backedge-taken count is i4 -195; CHECK-NEXT: Loop %loop: symbolic max backedge-taken count is (-1 + (-1 * %x) + ((1 + %x) smax %n))96; CHECK-NEXT: Loop %loop: Trip multiple is 197;98entry:99 %s = icmp sgt i4 %n, 0100 br i1 %s, label %loop, label %exit101loop:102 %i = phi i4 [ %x, %entry ], [ %i.next, %loop ]103 %i.next = add i4 %i, 1104 %t = icmp slt i4 %i.next, %n105 br i1 %t, label %loop, label %exit106exit:107 ret void108}109 110define void @startx_step2(i4 %n, i4 %x) {111; CHECK-LABEL: 'startx_step2'112; CHECK-NEXT: Determining loop execution counts for: @startx_step2113; CHECK-NEXT: Loop %loop: Unpredictable backedge-taken count.114; CHECK-NEXT: Loop %loop: Unpredictable constant max backedge-taken count.115; CHECK-NEXT: Loop %loop: Unpredictable symbolic max backedge-taken count.116;117entry:118 %s = icmp sgt i4 %n, 0119 br i1 %s, label %loop, label %exit120loop:121 %i = phi i4 [ %x, %entry ], [ %i.next, %loop ]122 %i.next = add i4 %i, 2123 %t = icmp slt i4 %i.next, %n124 br i1 %t, label %loop, label %exit125exit:126 ret void127}128 129define void @nsw(i4 %n) {130; CHECK-LABEL: 'nsw'131; CHECK-NEXT: Determining loop execution counts for: @nsw132; CHECK-NEXT: Loop %loop: backedge-taken count is (-1 + %n)133; CHECK-NEXT: Loop %loop: constant max backedge-taken count is i4 6134; CHECK-NEXT: Loop %loop: symbolic max backedge-taken count is (-1 + %n)135; CHECK-NEXT: Loop %loop: Trip multiple is 1136;137entry:138 %s = icmp sgt i4 %n, 0139 br i1 %s, label %loop, label %exit140loop:141 %i = phi i4 [ 0, %entry ], [ %i.next, %loop ]142 %i.next = add nsw i4 %i, 1143 %t = icmp slt i4 %i.next, %n144 br i1 %t, label %loop, label %exit145exit:146 ret void147}148 149; If %n is INT4_MAX, %i.next will wrap. The nsw bit says that the150; result is undefined. Therefore, after the loop's second iteration,151; we are free to assume that the loop exits. This is valid because:152; (a) %i.next is a poison value after the second iteration, which can153; also be considered an undef value.154; (b) the return instruction enacts a side effect that is control155; dependent on the poison value.156;157define void @nsw_step2(i4 %n) {158; CHECK-LABEL: 'nsw_step2'159; CHECK-NEXT: Determining loop execution counts for: @nsw_step2160; CHECK-NEXT: Loop %loop: backedge-taken count is ((-1 + %n) /u 2)161; CHECK-NEXT: Loop %loop: constant max backedge-taken count is i4 2162; CHECK-NEXT: Loop %loop: symbolic max backedge-taken count is ((-1 + %n) /u 2)163; CHECK-NEXT: Loop %loop: Trip multiple is 1164;165entry:166 %s = icmp sgt i4 %n, 0167 br i1 %s, label %loop, label %exit168loop:169 %i = phi i4 [ 0, %entry ], [ %i.next, %loop ]170 %i.next = add nsw i4 %i, 2171 %t = icmp slt i4 %i.next, %n172 br i1 %t, label %loop, label %exit173exit:174 ret void175}176 177define void @nsw_start1(i4 %n) {178; CHECK-LABEL: 'nsw_start1'179; CHECK-NEXT: Determining loop execution counts for: @nsw_start1180; CHECK-NEXT: Loop %loop: backedge-taken count is (-2 + (2 smax %n))<nsw>181; CHECK-NEXT: Loop %loop: constant max backedge-taken count is i4 5182; CHECK-NEXT: Loop %loop: symbolic max backedge-taken count is (-2 + (2 smax %n))<nsw>183; CHECK-NEXT: Loop %loop: Trip multiple is 1184;185entry:186 %s = icmp sgt i4 %n, 0187 br i1 %s, label %loop, label %exit188loop:189 %i = phi i4 [ 1, %entry ], [ %i.next, %loop ]190 %i.next = add nsw i4 %i, 1191 %t = icmp slt i4 %i.next, %n192 br i1 %t, label %loop, label %exit193exit:194 ret void195}196 197define void @nsw_start1_step2(i4 %n) {198; CHECK-LABEL: 'nsw_start1_step2'199; CHECK-NEXT: Determining loop execution counts for: @nsw_start1_step2200; CHECK-NEXT: Loop %loop: backedge-taken count is ((-2 + (3 smax %n))<nsw> /u 2)201; CHECK-NEXT: Loop %loop: constant max backedge-taken count is i4 2202; CHECK-NEXT: Loop %loop: symbolic max backedge-taken count is ((-2 + (3 smax %n))<nsw> /u 2)203; CHECK-NEXT: Loop %loop: Trip multiple is 1204;205entry:206 %s = icmp sgt i4 %n, 0207 br i1 %s, label %loop, label %exit208loop:209 %i = phi i4 [ 1, %entry ], [ %i.next, %loop ]210 %i.next = add nsw i4 %i, 2211 %t = icmp slt i4 %i.next, %n212 br i1 %t, label %loop, label %exit213exit:214 ret void215}216 217define void @nsw_startx(i4 %n, i4 %x) {218; CHECK-LABEL: 'nsw_startx'219; CHECK-NEXT: Determining loop execution counts for: @nsw_startx220; CHECK-NEXT: Loop %loop: backedge-taken count is (-1 + (-1 * %x) + ((1 + %x) smax %n))221; CHECK-NEXT: Loop %loop: constant max backedge-taken count is i4 -1222; CHECK-NEXT: Loop %loop: symbolic max backedge-taken count is (-1 + (-1 * %x) + ((1 + %x) smax %n))223; CHECK-NEXT: Loop %loop: Trip multiple is 1224;225entry:226 %s = icmp sgt i4 %n, 0227 br i1 %s, label %loop, label %exit228loop:229 %i = phi i4 [ %x, %entry ], [ %i.next, %loop ]230 %i.next = add nsw i4 %i, 1231 %t = icmp slt i4 %i.next, %n232 br i1 %t, label %loop, label %exit233exit:234 ret void235}236 237define void @nsw_startx_step2(i4 %n, i4 %x) {238; CHECK-LABEL: 'nsw_startx_step2'239; CHECK-NEXT: Determining loop execution counts for: @nsw_startx_step2240; CHECK-NEXT: Loop %loop: backedge-taken count is ((-1 + (-1 * %x) + ((2 + %x) smax %n)) /u 2)241; CHECK-NEXT: Loop %loop: constant max backedge-taken count is i4 7242; CHECK-NEXT: Loop %loop: symbolic max backedge-taken count is ((-1 + (-1 * %x) + ((2 + %x) smax %n)) /u 2)243; CHECK-NEXT: Loop %loop: Trip multiple is 1244;245entry:246 %s = icmp sgt i4 %n, 0247 br i1 %s, label %loop, label %exit248loop:249 %i = phi i4 [ %x, %entry ], [ %i.next, %loop ]250 %i.next = add nsw i4 %i, 2251 %t = icmp slt i4 %i.next, %n252 br i1 %t, label %loop, label %exit253exit:254 ret void255}256 257define void @even(i4 %n) {258; CHECK-LABEL: 'even'259; CHECK-NEXT: Determining loop execution counts for: @even260; CHECK-NEXT: Loop %loop: backedge-taken count is (-1 + (2 * %n))261; CHECK-NEXT: Loop %loop: constant max backedge-taken count is i4 5262; CHECK-NEXT: Loop %loop: symbolic max backedge-taken count is (-1 + (2 * %n))263; CHECK-NEXT: Loop %loop: Trip multiple is 2264;265entry:266 %m = shl i4 %n, 1267 %s = icmp sgt i4 %m, 0268 br i1 %s, label %loop, label %exit269loop:270 %i = phi i4 [ 0, %entry ], [ %i.next, %loop ]271 %i.next = add i4 %i, 1272 %t = icmp slt i4 %i.next, %m273 br i1 %t, label %loop, label %exit274exit:275 ret void276}277 278define void @even_step2(i4 %n) {279; CHECK-LABEL: 'even_step2'280; CHECK-NEXT: Determining loop execution counts for: @even_step2281; CHECK-NEXT: Loop %loop: backedge-taken count is ((-1 + (2 * %n)) /u 2)282; CHECK-NEXT: Loop %loop: constant max backedge-taken count is i4 2283; CHECK-NEXT: Loop %loop: symbolic max backedge-taken count is ((-1 + (2 * %n)) /u 2)284; CHECK-NEXT: Loop %loop: Trip multiple is 1285;286entry:287 %m = shl i4 %n, 1288 %s = icmp sgt i4 %m, 0289 br i1 %s, label %loop, label %exit290loop:291 %i = phi i4 [ 0, %entry ], [ %i.next, %loop ]292 %i.next = add i4 %i, 2293 %t = icmp slt i4 %i.next, %m294 br i1 %t, label %loop, label %exit295exit:296 ret void297}298 299define void @even_start1(i4 %n) {300; CHECK-LABEL: 'even_start1'301; CHECK-NEXT: Determining loop execution counts for: @even_start1302; CHECK-NEXT: Loop %loop: backedge-taken count is (-2 + (2 * %n))303; CHECK-NEXT: Loop %loop: constant max backedge-taken count is i4 4304; CHECK-NEXT: Loop %loop: symbolic max backedge-taken count is (-2 + (2 * %n))305; CHECK-NEXT: Loop %loop: Trip multiple is 1306;307entry:308 %m = shl i4 %n, 1309 %s = icmp sgt i4 %m, 0310 br i1 %s, label %loop, label %exit311loop:312 %i = phi i4 [ 1, %entry ], [ %i.next, %loop ]313 %i.next = add i4 %i, 1314 %t = icmp slt i4 %i.next, %m315 br i1 %t, label %loop, label %exit316exit:317 ret void318}319 320define void @even_start1_step2(i4 %n) {321; CHECK-LABEL: 'even_start1_step2'322; CHECK-NEXT: Determining loop execution counts for: @even_start1_step2323; CHECK-NEXT: Loop %loop: backedge-taken count is ((-2 + (2 * %n)) /u 2)324; CHECK-NEXT: Loop %loop: constant max backedge-taken count is i4 2325; CHECK-NEXT: Loop %loop: symbolic max backedge-taken count is ((-2 + (2 * %n)) /u 2)326; CHECK-NEXT: Loop %loop: Trip multiple is 1327;328entry:329 %m = shl i4 %n, 1330 %s = icmp sgt i4 %m, 0331 br i1 %s, label %loop, label %exit332loop:333 %i = phi i4 [ 1, %entry ], [ %i.next, %loop ]334 %i.next = add i4 %i, 2335 %t = icmp slt i4 %i.next, %m336 br i1 %t, label %loop, label %exit337exit:338 ret void339}340 341define void @even_startx(i4 %n, i4 %x) {342; CHECK-LABEL: 'even_startx'343; CHECK-NEXT: Determining loop execution counts for: @even_startx344; CHECK-NEXT: Loop %loop: backedge-taken count is (-1 + (-1 * %x) + ((1 + %x) smax (2 * %n)))345; CHECK-NEXT: Loop %loop: constant max backedge-taken count is i4 -2346; CHECK-NEXT: Loop %loop: symbolic max backedge-taken count is (-1 + (-1 * %x) + ((1 + %x) smax (2 * %n)))347; CHECK-NEXT: Loop %loop: Trip multiple is 1348;349entry:350 %m = shl i4 %n, 1351 %s = icmp sgt i4 %m, 0352 br i1 %s, label %loop, label %exit353loop:354 %i = phi i4 [ %x, %entry ], [ %i.next, %loop ]355 %i.next = add i4 %i, 1356 %t = icmp slt i4 %i.next, %m357 br i1 %t, label %loop, label %exit358exit:359 ret void360}361 362define void @even_startx_step2(i4 %n, i4 %x) {363; CHECK-LABEL: 'even_startx_step2'364; CHECK-NEXT: Determining loop execution counts for: @even_startx_step2365; CHECK-NEXT: Loop %loop: backedge-taken count is ((-1 + (-1 * %x) + ((2 + %x) smax (2 * %n))) /u 2)366; CHECK-NEXT: Loop %loop: constant max backedge-taken count is i4 7367; CHECK-NEXT: Loop %loop: symbolic max backedge-taken count is ((-1 + (-1 * %x) + ((2 + %x) smax (2 * %n))) /u 2)368; CHECK-NEXT: Loop %loop: Trip multiple is 1369;370entry:371 %m = shl i4 %n, 1372 %s = icmp sgt i4 %m, 0373 br i1 %s, label %loop, label %exit374loop:375 %i = phi i4 [ %x, %entry ], [ %i.next, %loop ]376 %i.next = add i4 %i, 2377 %t = icmp slt i4 %i.next, %m378 br i1 %t, label %loop, label %exit379exit:380 ret void381}382 383define void @even_nsw(i4 %n) {384; CHECK-LABEL: 'even_nsw'385; CHECK-NEXT: Determining loop execution counts for: @even_nsw386; CHECK-NEXT: Loop %loop: backedge-taken count is (-1 + (2 * %n))387; CHECK-NEXT: Loop %loop: constant max backedge-taken count is i4 5388; CHECK-NEXT: Loop %loop: symbolic max backedge-taken count is (-1 + (2 * %n))389; CHECK-NEXT: Loop %loop: Trip multiple is 2390;391entry:392 %m = shl i4 %n, 1393 %s = icmp sgt i4 %m, 0394 br i1 %s, label %loop, label %exit395loop:396 %i = phi i4 [ 0, %entry ], [ %i.next, %loop ]397 %i.next = add nsw i4 %i, 1398 %t = icmp slt i4 %i.next, %m399 br i1 %t, label %loop, label %exit400exit:401 ret void402}403 404define void @even_nsw_step2(i4 %n) {405; CHECK-LABEL: 'even_nsw_step2'406; CHECK-NEXT: Determining loop execution counts for: @even_nsw_step2407; CHECK-NEXT: Loop %loop: backedge-taken count is ((-1 + (2 * %n)) /u 2)408; CHECK-NEXT: Loop %loop: constant max backedge-taken count is i4 2409; CHECK-NEXT: Loop %loop: symbolic max backedge-taken count is ((-1 + (2 * %n)) /u 2)410; CHECK-NEXT: Loop %loop: Trip multiple is 1411;412entry:413 %m = shl i4 %n, 1414 %s = icmp sgt i4 %m, 0415 br i1 %s, label %loop, label %exit416loop:417 %i = phi i4 [ 0, %entry ], [ %i.next, %loop ]418 %i.next = add nsw i4 %i, 2419 %t = icmp slt i4 %i.next, %m420 br i1 %t, label %loop, label %exit421exit:422 ret void423}424 425define void @even_nsw_start1(i4 %n) {426; CHECK-LABEL: 'even_nsw_start1'427; CHECK-NEXT: Determining loop execution counts for: @even_nsw_start1428; CHECK-NEXT: Loop %loop: backedge-taken count is (-2 + (2 * %n))429; CHECK-NEXT: Loop %loop: constant max backedge-taken count is i4 4430; CHECK-NEXT: Loop %loop: symbolic max backedge-taken count is (-2 + (2 * %n))431; CHECK-NEXT: Loop %loop: Trip multiple is 1432;433entry:434 %m = shl i4 %n, 1435 %s = icmp sgt i4 %m, 0436 br i1 %s, label %loop, label %exit437loop:438 %i = phi i4 [ 1, %entry ], [ %i.next, %loop ]439 %i.next = add nsw i4 %i, 1440 %t = icmp slt i4 %i.next, %m441 br i1 %t, label %loop, label %exit442exit:443 ret void444}445 446define void @even_nsw_start1_step2(i4 %n) {447; CHECK-LABEL: 'even_nsw_start1_step2'448; CHECK-NEXT: Determining loop execution counts for: @even_nsw_start1_step2449; CHECK-NEXT: Loop %loop: backedge-taken count is ((-2 + (2 * %n)) /u 2)450; CHECK-NEXT: Loop %loop: constant max backedge-taken count is i4 2451; CHECK-NEXT: Loop %loop: symbolic max backedge-taken count is ((-2 + (2 * %n)) /u 2)452; CHECK-NEXT: Loop %loop: Trip multiple is 1453;454entry:455 %m = shl i4 %n, 1456 %s = icmp sgt i4 %m, 0457 br i1 %s, label %loop, label %exit458loop:459 %i = phi i4 [ 1, %entry ], [ %i.next, %loop ]460 %i.next = add nsw i4 %i, 2461 %t = icmp slt i4 %i.next, %m462 br i1 %t, label %loop, label %exit463exit:464 ret void465}466 467define void @even_nsw_startx(i4 %n, i4 %x) {468; CHECK-LABEL: 'even_nsw_startx'469; CHECK-NEXT: Determining loop execution counts for: @even_nsw_startx470; CHECK-NEXT: Loop %loop: backedge-taken count is (-1 + (-1 * %x) + ((1 + %x) smax (2 * %n)))471; CHECK-NEXT: Loop %loop: constant max backedge-taken count is i4 -2472; CHECK-NEXT: Loop %loop: symbolic max backedge-taken count is (-1 + (-1 * %x) + ((1 + %x) smax (2 * %n)))473; CHECK-NEXT: Loop %loop: Trip multiple is 1474;475entry:476 %m = shl i4 %n, 1477 %s = icmp sgt i4 %m, 0478 br i1 %s, label %loop, label %exit479loop:480 %i = phi i4 [ %x, %entry ], [ %i.next, %loop ]481 %i.next = add nsw i4 %i, 1482 %t = icmp slt i4 %i.next, %m483 br i1 %t, label %loop, label %exit484exit:485 ret void486}487 488define void @even_nsw_startx_step2(i4 %n, i4 %x) {489; CHECK-LABEL: 'even_nsw_startx_step2'490; CHECK-NEXT: Determining loop execution counts for: @even_nsw_startx_step2491; CHECK-NEXT: Loop %loop: backedge-taken count is ((-1 + (-1 * %x) + ((2 + %x) smax (2 * %n))) /u 2)492; CHECK-NEXT: Loop %loop: constant max backedge-taken count is i4 7493; CHECK-NEXT: Loop %loop: symbolic max backedge-taken count is ((-1 + (-1 * %x) + ((2 + %x) smax (2 * %n))) /u 2)494; CHECK-NEXT: Loop %loop: Trip multiple is 1495;496entry:497 %m = shl i4 %n, 1498 %s = icmp sgt i4 %m, 0499 br i1 %s, label %loop, label %exit500loop:501 %i = phi i4 [ %x, %entry ], [ %i.next, %loop ]502 %i.next = add nsw i4 %i, 2503 %t = icmp slt i4 %i.next, %m504 br i1 %t, label %loop, label %exit505exit:506 ret void507}508