1; NOTE: Assertions have been autogenerated by utils/update_analyze_test_checks.py 2; RUN: opt < %s -disable-output "-passes=print<scalar-evolution>" -scalar-evolution-classify-expressions=0 2>&1 | FileCheck %s 3 4; A collection of tests that show we can use facts about an exit test to 5; infer tighter bounds on an IV, and thus refine an IV into an addrec. The 6; basic tactic being used is proving NW from exit structure and then 7; implying NUW/NSW. Once NSW/NUW is inferred, we can derive addrecs from 8; the zext/sext cases that we couldn't at initial SCEV construction. 9 10@G = external global i8 11 12define void @nw_implies_nuw(i16 %n) mustprogress { 13; CHECK-LABEL: 'nw_implies_nuw' 14; CHECK-NEXT: Determining loop execution counts for: @nw_implies_nuw 15; CHECK-NEXT: Loop %for.body: backedge-taken count is %n 16; CHECK-NEXT: Loop %for.body: constant max backedge-taken count is i16 -1 17; CHECK-NEXT: Loop %for.body: symbolic max backedge-taken count is %n 18; CHECK-NEXT: Loop %for.body: Trip multiple is 1 19; 20entry: 21 br label %for.body 22 23for.body: ; preds = %entry, %for.body 24 %iv = phi i8 [ %iv.next, %for.body ], [ 0, %entry ] 25 %iv.next = add i8 %iv, 1 26 %zext = zext i8 %iv to i16 27 %cmp = icmp ult i16 %zext, %n 28 br i1 %cmp, label %for.body, label %for.end 29 30for.end: ; preds = %for.body, %entry 31 ret void 32} 33 34define void @neg_nw_nuw(i16 %n) mustprogress { 35; CHECK-LABEL: 'neg_nw_nuw' 36; CHECK-NEXT: Determining loop execution counts for: @neg_nw_nuw 37; CHECK-NEXT: Loop %for.body: Unpredictable backedge-taken count. 38; CHECK-NEXT: Loop %for.body: Unpredictable constant max backedge-taken count. 39; CHECK-NEXT: Loop %for.body: Unpredictable symbolic max backedge-taken count. 40; 41entry: 42 br label %for.body 43 44for.body: ; preds = %entry, %for.body 45 %iv = phi i8 [ %iv.next, %for.body ], [ 0, %entry ] 46 %iv.next = add i8 %iv, -1 47 %zext = zext i8 %iv to i16 48 %cmp = icmp ult i16 %zext, %n 49 br i1 %cmp, label %for.body, label %for.end 50 51for.end: ; preds = %for.body, %entry 52 ret void 53} 54 55define void @nw_implies_nsw(i16 %n) mustprogress { 56; CHECK-LABEL: 'nw_implies_nsw' 57; CHECK-NEXT: Determining loop execution counts for: @nw_implies_nsw 58; CHECK-NEXT: Loop %for.body: Unpredictable backedge-taken count. 59; CHECK-NEXT: Loop %for.body: Unpredictable constant max backedge-taken count. 60; CHECK-NEXT: Loop %for.body: Unpredictable symbolic max backedge-taken count. 61; CHECK-NEXT: Loop %for.body: Predicated backedge-taken count is (128 + (-128 smax %n)) 62; CHECK-NEXT: Predicates: 63; CHECK-NEXT: {-128,+,1}<%for.body> Added Flags: <nssw> 64; CHECK-NEXT: Loop %for.body: Predicated constant max backedge-taken count is i16 -32641 65; CHECK-NEXT: Predicates: 66; CHECK-NEXT: {-128,+,1}<%for.body> Added Flags: <nssw> 67; CHECK-NEXT: Loop %for.body: Predicated symbolic max backedge-taken count is (128 + (-128 smax %n)) 68; CHECK-NEXT: Predicates: 69; CHECK-NEXT: {-128,+,1}<%for.body> Added Flags: <nssw> 70; 71entry: 72 br label %for.body 73 74for.body: ; preds = %entry, %for.body 75 %iv = phi i8 [ %iv.next, %for.body ], [ -128, %entry ] 76 %iv.next = add i8 %iv, 1 77 %zext = sext i8 %iv to i16 78 %cmp = icmp slt i16 %zext, %n 79 br i1 %cmp, label %for.body, label %for.end 80 81for.end: ; preds = %for.body, %entry 82 ret void 83} 84 85define void @neg_nw_nsw(i16 %n) mustprogress { 86; CHECK-LABEL: 'neg_nw_nsw' 87; CHECK-NEXT: Determining loop execution counts for: @neg_nw_nsw 88; CHECK-NEXT: Loop %for.body: Unpredictable backedge-taken count. 89; CHECK-NEXT: Loop %for.body: Unpredictable constant max backedge-taken count. 90; CHECK-NEXT: Loop %for.body: Unpredictable symbolic max backedge-taken count. 91; 92entry: 93 br label %for.body 94 95for.body: ; preds = %entry, %for.body 96 %iv = phi i8 [ %iv.next, %for.body ], [ -128, %entry ] 97 %iv.next = add i8 %iv, -1 98 %zext = sext i8 %iv to i16 99 %cmp = icmp slt i16 %zext, %n 100 br i1 %cmp, label %for.body, label %for.end 101 102for.end: ; preds = %for.body, %entry 103 ret void 104} 105 106 107define void @actually_infinite() { 108; CHECK-LABEL: 'actually_infinite' 109; CHECK-NEXT: Determining loop execution counts for: @actually_infinite 110; CHECK-NEXT: Loop %for.body: Unpredictable backedge-taken count. 111; CHECK-NEXT: Loop %for.body: Unpredictable constant max backedge-taken count. 112; CHECK-NEXT: Loop %for.body: Unpredictable symbolic max backedge-taken count. 113; CHECK-NEXT: Loop %for.body: Predicated backedge-taken count is i16 257 114; CHECK-NEXT: Predicates: 115; CHECK-NEXT: {0,+,1}<%for.body> Added Flags: <nusw> 116; CHECK-NEXT: Loop %for.body: Predicated constant max backedge-taken count is i16 257 117; CHECK-NEXT: Predicates: 118; CHECK-NEXT: {0,+,1}<%for.body> Added Flags: <nusw> 119; CHECK-NEXT: Loop %for.body: Predicated symbolic max backedge-taken count is i16 257 120; CHECK-NEXT: Predicates: 121; CHECK-NEXT: {0,+,1}<%for.body> Added Flags: <nusw> 122; 123entry: 124 br label %for.body 125 126for.body: ; preds = %entry, %for.body 127 %iv = phi i8 [ %iv.next, %for.body ], [ 0, %entry ] 128 store volatile i8 %iv, ptr @G 129 %iv.next = add i8 %iv, 1 130 %zext = zext i8 %iv to i16 131 %cmp = icmp ult i16 %zext, 257 132 br i1 %cmp, label %for.body, label %for.end 133 134for.end: ; preds = %for.body, %entry 135 ret void 136} 137 138define void @rhs_mustexit_1(i16 %n.raw) mustprogress { 139; CHECK-LABEL: 'rhs_mustexit_1' 140; CHECK-NEXT: Determining loop execution counts for: @rhs_mustexit_1 141; CHECK-NEXT: Loop %for.body: Unpredictable backedge-taken count. 142; CHECK-NEXT: Loop %for.body: Unpredictable constant max backedge-taken count. 143; CHECK-NEXT: Loop %for.body: Unpredictable symbolic max backedge-taken count. 144; CHECK-NEXT: Loop %for.body: Predicated backedge-taken count is (-1 + (1 umax (-1 + (zext i8 (trunc i16 %n.raw to i8) to i16))<nsw>)) 145; CHECK-NEXT: Predicates: 146; CHECK-NEXT: {1,+,1}<nw><%for.body> Added Flags: <nusw> 147; CHECK-NEXT: Loop %for.body: Predicated constant max backedge-taken count is i16 -2 148; CHECK-NEXT: Predicates: 149; CHECK-NEXT: {1,+,1}<nw><%for.body> Added Flags: <nusw> 150; CHECK-NEXT: Loop %for.body: Predicated symbolic max backedge-taken count is (-1 + (1 umax (-1 + (zext i8 (trunc i16 %n.raw to i8) to i16))<nsw>)) 151; CHECK-NEXT: Predicates: 152; CHECK-NEXT: {1,+,1}<nw><%for.body> Added Flags: <nusw> 153; 154entry: 155 %n.and = and i16 %n.raw, 255 156 %n = add nsw i16 %n.and, -1 157 br label %for.body 158 159for.body: ; preds = %entry, %for.body 160 %iv = phi i8 [ %iv.next, %for.body ], [ 0, %entry ] 161 %iv.next = add i8 %iv, 1 162 store i8 %iv, ptr @G 163 %zext = zext i8 %iv.next to i16 164 %cmp = icmp ult i16 %zext, %n 165 br i1 %cmp, label %for.body, label %for.end 166 167for.end: ; preds = %for.body, %entry 168 ret void 169} 170 171define void @rhs_mustexit_3(i16 %n.raw) mustprogress { 172; CHECK-LABEL: 'rhs_mustexit_3' 173; CHECK-NEXT: Determining loop execution counts for: @rhs_mustexit_3 174; CHECK-NEXT: Loop %for.body: Unpredictable backedge-taken count. 175; CHECK-NEXT: Loop %for.body: Unpredictable constant max backedge-taken count. 176; CHECK-NEXT: Loop %for.body: Unpredictable symbolic max backedge-taken count. 177; 178entry: 179 %n.and = and i16 %n.raw, 255 180 %n = add nsw i16 %n.and, -3 181 br label %for.body 182 183for.body: ; preds = %entry, %for.body 184 %iv = phi i8 [ %iv.next, %for.body ], [ 0, %entry ] 185 %iv.next = add i8 %iv, 3 186 store i8 %iv, ptr @G 187 %zext = zext i8 %iv.next to i16 188 %cmp = icmp ult i16 %zext, %n 189 br i1 %cmp, label %for.body, label %for.end 190 191for.end: ; preds = %for.body, %entry 192 ret void 193} 194 195; Unknown, but non-zero step 196define void @rhs_mustexit_nonzero_step(i16 %n.raw, i8 %step.raw) mustprogress { 197; CHECK-LABEL: 'rhs_mustexit_nonzero_step' 198; CHECK-NEXT: Determining loop execution counts for: @rhs_mustexit_nonzero_step 199; CHECK-NEXT: Loop %for.body: Unpredictable backedge-taken count. 200; CHECK-NEXT: Loop %for.body: Unpredictable constant max backedge-taken count. 201; CHECK-NEXT: Loop %for.body: Unpredictable symbolic max backedge-taken count. 202; 203entry: 204 %n.and = and i16 %n.raw, 255 205 %n = add nsw i16 %n.and, -3 206 %step = add nuw i8 %step.raw, 1 207 br label %for.body 208 209for.body: ; preds = %entry, %for.body 210 %iv = phi i8 [ %iv.next, %for.body ], [ 0, %entry ] 211 %iv.next = add i8 %iv, %step 212 store i8 %iv, ptr @G 213 %zext = zext i8 %iv.next to i16 214 %cmp = icmp ult i16 %zext, %n 215 br i1 %cmp, label %for.body, label %for.end 216 217for.end: ; preds = %for.body, %entry 218 ret void 219} 220 221define void @neg_maybe_zero_step(i16 %n.raw, i8 %step) mustprogress { 222; CHECK-LABEL: 'neg_maybe_zero_step' 223; CHECK-NEXT: Determining loop execution counts for: @neg_maybe_zero_step 224; CHECK-NEXT: Loop %for.body: Unpredictable backedge-taken count. 225; CHECK-NEXT: Loop %for.body: Unpredictable constant max backedge-taken count. 226; CHECK-NEXT: Loop %for.body: Unpredictable symbolic max backedge-taken count. 227; 228entry: 229 %n.and = and i16 %n.raw, 255 230 %n = add nsw i16 %n.and, -3 231 br label %for.body 232 233for.body: ; preds = %entry, %for.body 234 %iv = phi i8 [ %iv.next, %for.body ], [ 0, %entry ] 235 %iv.next = add i8 %iv, %step 236 store i8 %iv, ptr @G 237 %zext = zext i8 %iv.next to i16 238 %cmp = icmp ult i16 %zext, %n 239 br i1 %cmp, label %for.body, label %for.end 240 241for.end: ; preds = %for.body, %entry 242 ret void 243} 244 245define void @neg_rhs_wrong_range(i16 %n.raw) mustprogress { 246; CHECK-LABEL: 'neg_rhs_wrong_range' 247; CHECK-NEXT: Determining loop execution counts for: @neg_rhs_wrong_range 248; CHECK-NEXT: Loop %for.body: Unpredictable backedge-taken count. 249; CHECK-NEXT: Loop %for.body: Unpredictable constant max backedge-taken count. 250; CHECK-NEXT: Loop %for.body: Unpredictable symbolic max backedge-taken count. 251; 252entry: 253 %n.and = and i16 %n.raw, 255 254 %n = add nsw i16 %n.and, -1 255 br label %for.body 256 257for.body: ; preds = %entry, %for.body 258 %iv = phi i8 [ %iv.next, %for.body ], [ 0, %entry ] 259 %iv.next = add i8 %iv, 2 260 store i8 %iv, ptr @G 261 %zext = zext i8 %iv.next to i16 262 %cmp = icmp ult i16 %zext, %n 263 br i1 %cmp, label %for.body, label %for.end 264 265for.end: ; preds = %for.body, %entry 266 ret void 267} 268 269define void @neg_rhs_maybe_infinite(i16 %n.raw) { 270; CHECK-LABEL: 'neg_rhs_maybe_infinite' 271; CHECK-NEXT: Determining loop execution counts for: @neg_rhs_maybe_infinite 272; CHECK-NEXT: Loop %for.body: Unpredictable backedge-taken count. 273; CHECK-NEXT: Loop %for.body: Unpredictable constant max backedge-taken count. 274; CHECK-NEXT: Loop %for.body: Unpredictable symbolic max backedge-taken count. 275; CHECK-NEXT: Loop %for.body: Predicated backedge-taken count is (-1 + (1 umax (-1 + (zext i8 (trunc i16 %n.raw to i8) to i16))<nsw>)) 276; CHECK-NEXT: Predicates: 277; CHECK-NEXT: {1,+,1}<%for.body> Added Flags: <nusw> 278; CHECK-NEXT: Loop %for.body: Predicated constant max backedge-taken count is i16 -2 279; CHECK-NEXT: Predicates: 280; CHECK-NEXT: {1,+,1}<%for.body> Added Flags: <nusw> 281; CHECK-NEXT: Loop %for.body: Predicated symbolic max backedge-taken count is (-1 + (1 umax (-1 + (zext i8 (trunc i16 %n.raw to i8) to i16))<nsw>)) 282; CHECK-NEXT: Predicates: 283; CHECK-NEXT: {1,+,1}<%for.body> Added Flags: <nusw> 284; 285entry: 286 %n.and = and i16 %n.raw, 255 287 %n = add nsw i16 %n.and, -1 288 br label %for.body 289 290for.body: ; preds = %entry, %for.body 291 %iv = phi i8 [ %iv.next, %for.body ], [ 0, %entry ] 292 %iv.next = add i8 %iv, 1 293 store i8 %iv, ptr @G 294 %zext = zext i8 %iv.next to i16 295 %cmp = icmp ult i16 %zext, %n 296 br i1 %cmp, label %for.body, label %for.end 297 298for.end: ; preds = %for.body, %entry 299 ret void 300} 301 302; Because of the range on RHS including only values within i8, we don't need 303; the must exit property 304define void @rhs_narrow_range(i16 %n.raw) { 305; CHECK-LABEL: 'rhs_narrow_range' 306; CHECK-NEXT: Determining loop execution counts for: @rhs_narrow_range 307; CHECK-NEXT: Loop %for.body: backedge-taken count is (-1 + (1 umax (2 * (zext i7 (trunc i16 (%n.raw /u 2) to i7) to i16))<nuw><nsw>))<nsw> 308; CHECK-NEXT: Loop %for.body: constant max backedge-taken count is i16 253 309; CHECK-NEXT: Loop %for.body: symbolic max backedge-taken count is (-1 + (1 umax (2 * (zext i7 (trunc i16 (%n.raw /u 2) to i7) to i16))<nuw><nsw>))<nsw> 310; CHECK-NEXT: Loop %for.body: Trip multiple is 1 311; 312entry: 313 %n = and i16 %n.raw, 254 314 br label %for.body 315 316for.body: ; preds = %entry, %for.body 317 %iv = phi i8 [ %iv.next, %for.body ], [ 0, %entry ] 318 %iv.next = add i8 %iv, 1 319 store i8 %iv, ptr @G 320 %zext = zext i8 %iv.next to i16 321 %cmp = icmp ult i16 %zext, %n 322 br i1 %cmp, label %for.body, label %for.end 323 324for.end: ; preds = %for.body, %entry 325 ret void 326} 327 328define void @ugt_constant_rhs(i16 %n.raw, i8 %start) mustprogress { 329; 330; CHECK-LABEL: 'ugt_constant_rhs' 331; CHECK-NEXT: Determining loop execution counts for: @ugt_constant_rhs 332; CHECK-NEXT: Loop %for.body: Unpredictable backedge-taken count. 333; CHECK-NEXT: Loop %for.body: Unpredictable constant max backedge-taken count. 334; CHECK-NEXT: Loop %for.body: Unpredictable symbolic max backedge-taken count. 335; 336entry: 337 br label %for.body 338 339for.body: ; preds = %entry, %for.body 340 %iv = phi i8 [ %iv.next, %for.body ], [ %start, %entry ] 341 %iv.next = add i8 %iv, 1 342 %zext = zext i8 %iv.next to i16 343 %cmp = icmp ugt i16 %zext, 254 344 br i1 %cmp, label %for.body, label %for.end 345 346for.end: ; preds = %for.body, %entry 347 ret void 348} 349 350define void @ult_constant_rhs(i16 %n.raw, i8 %start) { 351; 352; CHECK-LABEL: 'ult_constant_rhs' 353; CHECK-NEXT: Determining loop execution counts for: @ult_constant_rhs 354; CHECK-NEXT: Loop %for.body: backedge-taken count is (255 + (-1 * (zext i8 (1 + %start) to i16))<nsw>)<nsw> 355; CHECK-NEXT: Loop %for.body: constant max backedge-taken count is i16 255 356; CHECK-NEXT: Loop %for.body: symbolic max backedge-taken count is (255 + (-1 * (zext i8 (1 + %start) to i16))<nsw>)<nsw> 357; CHECK-NEXT: Loop %for.body: Trip multiple is 1 358; 359entry: 360 br label %for.body 361 362for.body: ; preds = %entry, %for.body 363 %iv = phi i8 [ %iv.next, %for.body ], [ %start, %entry ] 364 %iv.next = add i8 %iv, 1 365 %zext = zext i8 %iv.next to i16 366 %cmp = icmp ult i16 %zext, 255 367 br i1 %cmp, label %for.body, label %for.end 368 369for.end: ; preds = %for.body, %entry 370 ret void 371} 372 373define void @ult_constant_rhs_stride2(i16 %n.raw, i8 %start) { 374; 375; CHECK-LABEL: 'ult_constant_rhs_stride2' 376; CHECK-NEXT: Determining loop execution counts for: @ult_constant_rhs_stride2 377; CHECK-NEXT: Loop %for.body: backedge-taken count is ((1 + (-1 * (zext i8 (2 + %start) to i16))<nsw> + (254 umax (zext i8 (2 + %start) to i16))) /u 2) 378; CHECK-NEXT: Loop %for.body: constant max backedge-taken count is i16 127 379; CHECK-NEXT: Loop %for.body: symbolic max backedge-taken count is ((1 + (-1 * (zext i8 (2 + %start) to i16))<nsw> + (254 umax (zext i8 (2 + %start) to i16))) /u 2) 380; CHECK-NEXT: Loop %for.body: Trip multiple is 1 381; 382entry: 383 br label %for.body 384 385for.body: ; preds = %entry, %for.body 386 %iv = phi i8 [ %iv.next, %for.body ], [ %start, %entry ] 387 %iv.next = add i8 %iv, 2 388 %zext = zext i8 %iv.next to i16 389 %cmp = icmp ult i16 %zext, 254 390 br i1 %cmp, label %for.body, label %for.end 391 392for.end: ; preds = %for.body, %entry 393 ret void 394} 395 396define void @ult_constant_rhs_stride2_neg(i16 %n.raw, i8 %start) { 397; 398; CHECK-LABEL: 'ult_constant_rhs_stride2_neg' 399; CHECK-NEXT: Determining loop execution counts for: @ult_constant_rhs_stride2_neg 400; CHECK-NEXT: Loop %for.body: Unpredictable backedge-taken count. 401; CHECK-NEXT: Loop %for.body: Unpredictable constant max backedge-taken count. 402; CHECK-NEXT: Loop %for.body: Unpredictable symbolic max backedge-taken count. 403; CHECK-NEXT: Loop %for.body: Predicated backedge-taken count is ((256 + (-1 * (zext i8 (2 + %start) to i16))<nsw>)<nsw> /u 2) 404; CHECK-NEXT: Predicates: 405; CHECK-NEXT: {(2 + %start),+,2}<%for.body> Added Flags: <nusw> 406; CHECK-NEXT: Loop %for.body: Predicated constant max backedge-taken count is i16 128 407; CHECK-NEXT: Predicates: 408; CHECK-NEXT: {(2 + %start),+,2}<%for.body> Added Flags: <nusw> 409; CHECK-NEXT: Loop %for.body: Predicated symbolic max backedge-taken count is ((256 + (-1 * (zext i8 (2 + %start) to i16))<nsw>)<nsw> /u 2) 410; CHECK-NEXT: Predicates: 411; CHECK-NEXT: {(2 + %start),+,2}<%for.body> Added Flags: <nusw> 412; 413entry: 414 br label %for.body 415 416for.body: ; preds = %entry, %for.body 417 %iv = phi i8 [ %iv.next, %for.body ], [ %start, %entry ] 418 %iv.next = add i8 %iv, 2 419 %zext = zext i8 %iv.next to i16 420 %cmp = icmp ult i16 %zext, 255 421 br i1 %cmp, label %for.body, label %for.end 422 423for.end: ; preds = %for.body, %entry 424 ret void 425} 426 427 428define void @ult_restricted_rhs(i16 %n.raw) { 429; CHECK-LABEL: 'ult_restricted_rhs' 430; CHECK-NEXT: Determining loop execution counts for: @ult_restricted_rhs 431; CHECK-NEXT: Loop %for.body: backedge-taken count is (-1 + (1 umax (zext i8 (trunc i16 %n.raw to i8) to i16)))<nsw> 432; CHECK-NEXT: Loop %for.body: constant max backedge-taken count is i16 254 433; CHECK-NEXT: Loop %for.body: symbolic max backedge-taken count is (-1 + (1 umax (zext i8 (trunc i16 %n.raw to i8) to i16)))<nsw> 434; CHECK-NEXT: Loop %for.body: Trip multiple is 1 435; 436entry: 437 %n = and i16 %n.raw, 255 438 br label %for.body 439 440for.body: ; preds = %entry, %for.body 441 %iv = phi i8 [ %iv.next, %for.body ], [ 0, %entry ] 442 %iv.next = add i8 %iv, 1 443 %zext = zext i8 %iv.next to i16 444 %cmp = icmp ult i16 %zext, %n 445 br i1 %cmp, label %for.body, label %for.end 446 447for.end: ; preds = %for.body, %entry 448 ret void 449} 450 451define void @ult_guarded_rhs(i16 %n) {; 452; CHECK-LABEL: 'ult_guarded_rhs' 453; CHECK-NEXT: Determining loop execution counts for: @ult_guarded_rhs 454; CHECK-NEXT: Loop %for.body: backedge-taken count is (-1 + (1 umax %n)) 455; CHECK-NEXT: Loop %for.body: constant max backedge-taken count is i16 -2 456; CHECK-NEXT: Loop %for.body: symbolic max backedge-taken count is (-1 + (1 umax %n)) 457; CHECK-NEXT: Loop %for.body: Trip multiple is 1 458; 459entry: 460 %in_range = icmp ult i16 %n, 256 461 br i1 %in_range, label %for.body, label %for.end 462 463for.body: ; preds = %entry, %for.body 464 %iv = phi i8 [ %iv.next, %for.body ], [ 0, %entry ] 465 %iv.next = add i8 %iv, 1 466 %zext = zext i8 %iv.next to i16 467 %cmp = icmp ult i16 %zext, %n 468 br i1 %cmp, label %for.body, label %for.end 469 470for.end: ; preds = %for.body, %entry 471 ret void 472} 473 474 475 476declare void @llvm.assume(i1) 477 478