1; NOTE: Assertions have been autogenerated by utils/update_analyze_test_checks.py UTC_ARGS: --version 5 2; RUN: opt < %s -disable-output -passes="print<scalar-evolution>" \ 3; RUN: -scalar-evolution-classify-expressions=0 2>&1 | FileCheck %s 4 5declare void @llvm.experimental.guard(i1, ...) 6 7define void @test_1(i32 %n) nounwind { 8; Prove that (n > 1) ===> (n / 2 > 0). 9; CHECK-LABEL: 'test_1' 10; CHECK-NEXT: Determining loop execution counts for: @test_1 11; CHECK-NEXT: Loop %header: backedge-taken count is (-1 + %n.div.2)<nsw> 12; CHECK-NEXT: Loop %header: constant max backedge-taken count is i32 1073741822 13; CHECK-NEXT: Loop %header: symbolic max backedge-taken count is (-1 + %n.div.2)<nsw> 14; CHECK-NEXT: Loop %header: Trip multiple is 1 15; 16entry: 17 %cmp1 = icmp sgt i32 %n, 1 18 %n.div.2 = sdiv i32 %n, 2 19 call void(i1, ...) @llvm.experimental.guard(i1 %cmp1) [ "deopt"() ] 20 br label %header 21 22header: 23 %indvar = phi i32 [ %indvar.next, %header ], [ 0, %entry ] 24 %indvar.next = add i32 %indvar, 1 25 %exitcond = icmp sgt i32 %n.div.2, %indvar.next 26 br i1 %exitcond, label %header, label %exit 27 28exit: 29 ret void 30} 31 32define void @test_1neg(i32 %n) nounwind { 33; Prove that (n > 0) =\=> (n / 2 > 0). 34; CHECK-LABEL: 'test_1neg' 35; CHECK-NEXT: Determining loop execution counts for: @test_1neg 36; CHECK-NEXT: Loop %header: backedge-taken count is (-1 + (1 smax %n.div.2))<nsw> 37; CHECK-NEXT: Loop %header: constant max backedge-taken count is i32 1073741822 38; CHECK-NEXT: Loop %header: symbolic max backedge-taken count is (-1 + (1 smax %n.div.2))<nsw> 39; CHECK-NEXT: Loop %header: Trip multiple is 1 40; 41entry: 42 %cmp1 = icmp sgt i32 %n, 0 43 %n.div.2 = sdiv i32 %n, 2 44 call void(i1, ...) @llvm.experimental.guard(i1 %cmp1) [ "deopt"() ] 45 br label %header 46 47header: 48 %indvar = phi i32 [ %indvar.next, %header ], [ 0, %entry ] 49 %indvar.next = add i32 %indvar, 1 50 %exitcond = icmp sgt i32 %n.div.2, %indvar.next 51 br i1 %exitcond, label %header, label %exit 52 53exit: 54 ret void 55} 56 57define void @test_2(i32 %n) nounwind { 58; Prove that (n >= 2) ===> (n / 2 > 0). 59; CHECK-LABEL: 'test_2' 60; CHECK-NEXT: Determining loop execution counts for: @test_2 61; CHECK-NEXT: Loop %header: backedge-taken count is (-1 + %n.div.2)<nsw> 62; CHECK-NEXT: Loop %header: constant max backedge-taken count is i32 1073741822 63; CHECK-NEXT: Loop %header: symbolic max backedge-taken count is (-1 + %n.div.2)<nsw> 64; CHECK-NEXT: Loop %header: Trip multiple is 1 65; 66entry: 67 %cmp1 = icmp sge i32 %n, 2 68 %n.div.2 = sdiv i32 %n, 2 69 call void(i1, ...) @llvm.experimental.guard(i1 %cmp1) [ "deopt"() ] 70 br label %header 71 72header: 73 %indvar = phi i32 [ %indvar.next, %header ], [ 0, %entry ] 74 %indvar.next = add i32 %indvar, 1 75 %exitcond = icmp sgt i32 %n.div.2, %indvar.next 76 br i1 %exitcond, label %header, label %exit 77 78exit: 79 ret void 80} 81 82define void @test_2neg(i32 %n) nounwind { 83; Prove that (n >= 1) =\=> (n / 2 > 0). 84; CHECK-LABEL: 'test_2neg' 85; CHECK-NEXT: Determining loop execution counts for: @test_2neg 86; CHECK-NEXT: Loop %header: backedge-taken count is (-1 + (1 smax %n.div.2))<nsw> 87; CHECK-NEXT: Loop %header: constant max backedge-taken count is i32 1073741822 88; CHECK-NEXT: Loop %header: symbolic max backedge-taken count is (-1 + (1 smax %n.div.2))<nsw> 89; CHECK-NEXT: Loop %header: Trip multiple is 1 90; 91entry: 92 %cmp1 = icmp sge i32 %n, 1 93 %n.div.2 = sdiv i32 %n, 2 94 call void(i1, ...) @llvm.experimental.guard(i1 %cmp1) [ "deopt"() ] 95 br label %header 96 97header: 98 %indvar = phi i32 [ %indvar.next, %header ], [ 0, %entry ] 99 %indvar.next = add i32 %indvar, 1 100 %exitcond = icmp sgt i32 %n.div.2, %indvar.next 101 br i1 %exitcond, label %header, label %exit 102 103exit: 104 ret void 105} 106 107define void @test_3(i32 %n) nounwind { 108; Prove that (n > -2) ===> (n / 2 >= 0). 109; CHECK-LABEL: 'test_3' 110; CHECK-NEXT: Determining loop execution counts for: @test_3 111; CHECK-NEXT: Loop %header: backedge-taken count is (1 + %n.div.2)<nsw> 112; CHECK-NEXT: Loop %header: constant max backedge-taken count is i32 1073741824 113; CHECK-NEXT: Loop %header: symbolic max backedge-taken count is (1 + %n.div.2)<nsw> 114; CHECK-NEXT: Loop %header: Trip multiple is 1 115; 116entry: 117 %cmp1 = icmp sgt i32 %n, -2 118 %n.div.2 = sdiv i32 %n, 2 119 call void(i1, ...) @llvm.experimental.guard(i1 %cmp1) [ "deopt"() ] 120 br label %header 121 122header: 123 %indvar = phi i32 [ %indvar.next, %header ], [ 0, %entry ] 124 %indvar.next = add i32 %indvar, 1 125 %exitcond = icmp sge i32 %n.div.2, %indvar 126 br i1 %exitcond, label %header, label %exit 127 128exit: 129 ret void 130} 131 132define void @test_3neg(i32 %n) nounwind { 133; Prove that (n > -3) =\=> (n / 2 >= 0). 134; CHECK-LABEL: 'test_3neg' 135; CHECK-NEXT: Determining loop execution counts for: @test_3neg 136; CHECK-NEXT: Loop %header: backedge-taken count is (0 smax (1 + %n.div.2)<nsw>) 137; CHECK-NEXT: Loop %header: constant max backedge-taken count is i32 1073741824 138; CHECK-NEXT: Loop %header: symbolic max backedge-taken count is (0 smax (1 + %n.div.2)<nsw>) 139; CHECK-NEXT: Loop %header: Trip multiple is 1 140; 141entry: 142 %cmp1 = icmp sgt i32 %n, -3 143 %n.div.2 = sdiv i32 %n, 2 144 call void(i1, ...) @llvm.experimental.guard(i1 %cmp1) [ "deopt"() ] 145 br label %header 146 147header: 148 %indvar = phi i32 [ %indvar.next, %header ], [ 0, %entry ] 149 %indvar.next = add i32 %indvar, 1 150 %exitcond = icmp sge i32 %n.div.2, %indvar 151 br i1 %exitcond, label %header, label %exit 152 153exit: 154 ret void 155} 156 157define void @test_4(i32 %n) nounwind { 158; Prove that (n >= -1) ===> (n / 2 >= 0). 159; CHECK-LABEL: 'test_4' 160; CHECK-NEXT: Determining loop execution counts for: @test_4 161; CHECK-NEXT: Loop %header: backedge-taken count is (1 + %n.div.2)<nsw> 162; CHECK-NEXT: Loop %header: constant max backedge-taken count is i32 1073741824 163; CHECK-NEXT: Loop %header: symbolic max backedge-taken count is (1 + %n.div.2)<nsw> 164; CHECK-NEXT: Loop %header: Trip multiple is 1 165; 166entry: 167 %cmp1 = icmp sge i32 %n, -1 168 %n.div.2 = sdiv i32 %n, 2 169 call void(i1, ...) @llvm.experimental.guard(i1 %cmp1) [ "deopt"() ] 170 br label %header 171 172header: 173 %indvar = phi i32 [ %indvar.next, %header ], [ 0, %entry ] 174 %indvar.next = add i32 %indvar, 1 175 %exitcond = icmp sge i32 %n.div.2, %indvar 176 br i1 %exitcond, label %header, label %exit 177 178exit: 179 ret void 180} 181 182define void @test_4neg(i32 %n) nounwind { 183; Prove that (n >= -2) =\=> (n / 2 >= 0). 184; CHECK-LABEL: 'test_4neg' 185; CHECK-NEXT: Determining loop execution counts for: @test_4neg 186; CHECK-NEXT: Loop %header: backedge-taken count is (0 smax (1 + %n.div.2)<nsw>) 187; CHECK-NEXT: Loop %header: constant max backedge-taken count is i32 1073741824 188; CHECK-NEXT: Loop %header: symbolic max backedge-taken count is (0 smax (1 + %n.div.2)<nsw>) 189; CHECK-NEXT: Loop %header: Trip multiple is 1 190; 191entry: 192 %cmp1 = icmp sge i32 %n, -2 193 %n.div.2 = sdiv i32 %n, 2 194 call void(i1, ...) @llvm.experimental.guard(i1 %cmp1) [ "deopt"() ] 195 br label %header 196 197header: 198 %indvar = phi i32 [ %indvar.next, %header ], [ 0, %entry ] 199 %indvar.next = add i32 %indvar, 1 200 %exitcond = icmp sge i32 %n.div.2, %indvar 201 br i1 %exitcond, label %header, label %exit 202 203exit: 204 ret void 205} 206 207define void @test_ext_01(i32 %n) nounwind { 208; Prove that (n > 1) ===> (n / 2 > 0). 209; CHECK-LABEL: 'test_ext_01' 210; CHECK-NEXT: Determining loop execution counts for: @test_ext_01 211; CHECK-NEXT: Loop %header: backedge-taken count is (-1 + (sext i32 %n.div.2 to i64))<nsw> 212; CHECK-NEXT: Loop %header: constant max backedge-taken count is i64 1073741822 213; CHECK-NEXT: Loop %header: symbolic max backedge-taken count is (-1 + (sext i32 %n.div.2 to i64))<nsw> 214; CHECK-NEXT: Loop %header: Trip multiple is 1 215; 216entry: 217 %cmp1 = icmp sgt i32 %n, 1 218 %n.div.2 = sdiv i32 %n, 2 219 %n.div.2.ext = sext i32 %n.div.2 to i64 220 call void(i1, ...) @llvm.experimental.guard(i1 %cmp1) [ "deopt"() ] 221 br label %header 222 223header: 224 %indvar = phi i64 [ %indvar.next, %header ], [ 0, %entry ] 225 %indvar.next = add i64 %indvar, 1 226 %exitcond = icmp sgt i64 %n.div.2.ext, %indvar.next 227 br i1 %exitcond, label %header, label %exit 228 229exit: 230 ret void 231} 232 233define void @test_ext_01neg(i32 %n) nounwind { 234; Prove that (n > 0) =\=> (n / 2 > 0). 235; CHECK-LABEL: 'test_ext_01neg' 236; CHECK-NEXT: Determining loop execution counts for: @test_ext_01neg 237; CHECK-NEXT: Loop %header: backedge-taken count is (-1 + (1 smax (sext i32 %n.div.2 to i64)))<nsw> 238; CHECK-NEXT: Loop %header: constant max backedge-taken count is i64 1073741822 239; CHECK-NEXT: Loop %header: symbolic max backedge-taken count is (-1 + (1 smax (sext i32 %n.div.2 to i64)))<nsw> 240; CHECK-NEXT: Loop %header: Trip multiple is 1 241; 242entry: 243 %cmp1 = icmp sgt i32 %n, 0 244 %n.div.2 = sdiv i32 %n, 2 245 %n.div.2.ext = sext i32 %n.div.2 to i64 246 call void(i1, ...) @llvm.experimental.guard(i1 %cmp1) [ "deopt"() ] 247 br label %header 248 249header: 250 %indvar = phi i64 [ %indvar.next, %header ], [ 0, %entry ] 251 %indvar.next = add i64 %indvar, 1 252 %exitcond = icmp sgt i64 %n.div.2.ext, %indvar.next 253 br i1 %exitcond, label %header, label %exit 254 255exit: 256 ret void 257} 258 259define void @test_ext_02(i32 %n) nounwind { 260; Prove that (n >= 2) ===> (n / 2 > 0). 261; CHECK-LABEL: 'test_ext_02' 262; CHECK-NEXT: Determining loop execution counts for: @test_ext_02 263; CHECK-NEXT: Loop %header: backedge-taken count is (-1 + (sext i32 %n.div.2 to i64))<nsw> 264; CHECK-NEXT: Loop %header: constant max backedge-taken count is i64 1073741822 265; CHECK-NEXT: Loop %header: symbolic max backedge-taken count is (-1 + (sext i32 %n.div.2 to i64))<nsw> 266; CHECK-NEXT: Loop %header: Trip multiple is 1 267; 268entry: 269 %cmp1 = icmp sge i32 %n, 2 270 %n.div.2 = sdiv i32 %n, 2 271 %n.div.2.ext = sext i32 %n.div.2 to i64 272 call void(i1, ...) @llvm.experimental.guard(i1 %cmp1) [ "deopt"() ] 273 br label %header 274 275header: 276 %indvar = phi i64 [ %indvar.next, %header ], [ 0, %entry ] 277 %indvar.next = add i64 %indvar, 1 278 %exitcond = icmp sgt i64 %n.div.2.ext, %indvar.next 279 br i1 %exitcond, label %header, label %exit 280 281exit: 282 ret void 283} 284 285define void @test_ext_02neg(i32 %n) nounwind { 286; Prove that (n >= 1) =\=> (n / 2 > 0). 287; CHECK-LABEL: 'test_ext_02neg' 288; CHECK-NEXT: Determining loop execution counts for: @test_ext_02neg 289; CHECK-NEXT: Loop %header: backedge-taken count is (-1 + (1 smax (sext i32 %n.div.2 to i64)))<nsw> 290; CHECK-NEXT: Loop %header: constant max backedge-taken count is i64 1073741822 291; CHECK-NEXT: Loop %header: symbolic max backedge-taken count is (-1 + (1 smax (sext i32 %n.div.2 to i64)))<nsw> 292; CHECK-NEXT: Loop %header: Trip multiple is 1 293; 294entry: 295 %cmp1 = icmp sge i32 %n, 1 296 %n.div.2 = sdiv i32 %n, 2 297 %n.div.2.ext = sext i32 %n.div.2 to i64 298 call void(i1, ...) @llvm.experimental.guard(i1 %cmp1) [ "deopt"() ] 299 br label %header 300 301header: 302 %indvar = phi i64 [ %indvar.next, %header ], [ 0, %entry ] 303 %indvar.next = add i64 %indvar, 1 304 %exitcond = icmp sgt i64 %n.div.2.ext, %indvar.next 305 br i1 %exitcond, label %header, label %exit 306 307exit: 308 ret void 309} 310 311define void @test_ext_03(i32 %n) nounwind { 312; Prove that (n > -2) ===> (n / 2 >= 0). 313; CHECK-LABEL: 'test_ext_03' 314; CHECK-NEXT: Determining loop execution counts for: @test_ext_03 315; CHECK-NEXT: Loop %header: backedge-taken count is (1 + (sext i32 %n.div.2 to i64))<nsw> 316; CHECK-NEXT: Loop %header: constant max backedge-taken count is i64 1073741824 317; CHECK-NEXT: Loop %header: symbolic max backedge-taken count is (1 + (sext i32 %n.div.2 to i64))<nsw> 318; CHECK-NEXT: Loop %header: Trip multiple is 1 319; 320entry: 321 %cmp1 = icmp sgt i32 %n, -2 322 %n.div.2 = sdiv i32 %n, 2 323 %n.div.2.ext = sext i32 %n.div.2 to i64 324 call void(i1, ...) @llvm.experimental.guard(i1 %cmp1) [ "deopt"() ] 325 br label %header 326 327header: 328 %indvar = phi i64 [ %indvar.next, %header ], [ 0, %entry ] 329 %indvar.next = add i64 %indvar, 1 330 %exitcond = icmp sge i64 %n.div.2.ext, %indvar 331 br i1 %exitcond, label %header, label %exit 332 333exit: 334 ret void 335} 336 337define void @test_ext_03neg(i32 %n) nounwind { 338; Prove that (n > -3) =\=> (n / 2 >= 0). 339; CHECK-LABEL: 'test_ext_03neg' 340; CHECK-NEXT: Determining loop execution counts for: @test_ext_03neg 341; CHECK-NEXT: Loop %header: backedge-taken count is (0 smax (1 + (sext i32 %n.div.2 to i64))<nsw>) 342; CHECK-NEXT: Loop %header: constant max backedge-taken count is i64 1073741824 343; CHECK-NEXT: Loop %header: symbolic max backedge-taken count is (0 smax (1 + (sext i32 %n.div.2 to i64))<nsw>) 344; CHECK-NEXT: Loop %header: Trip multiple is 1 345; 346entry: 347 %cmp1 = icmp sgt i32 %n, -3 348 %n.div.2 = sdiv i32 %n, 2 349 %n.div.2.ext = sext i32 %n.div.2 to i64 350 call void(i1, ...) @llvm.experimental.guard(i1 %cmp1) [ "deopt"() ] 351 br label %header 352 353header: 354 %indvar = phi i64 [ %indvar.next, %header ], [ 0, %entry ] 355 %indvar.next = add i64 %indvar, 1 356 %exitcond = icmp sge i64 %n.div.2.ext, %indvar 357 br i1 %exitcond, label %header, label %exit 358 359exit: 360 ret void 361} 362 363define void @test_ext_04(i32 %n) nounwind { 364; Prove that (n >= -1) ===> (n / 2 >= 0). 365; CHECK-LABEL: 'test_ext_04' 366; CHECK-NEXT: Determining loop execution counts for: @test_ext_04 367; CHECK-NEXT: Loop %header: backedge-taken count is (1 + (sext i32 %n.div.2 to i64))<nsw> 368; CHECK-NEXT: Loop %header: constant max backedge-taken count is i64 1073741824 369; CHECK-NEXT: Loop %header: symbolic max backedge-taken count is (1 + (sext i32 %n.div.2 to i64))<nsw> 370; CHECK-NEXT: Loop %header: Trip multiple is 1 371; 372entry: 373 %cmp1 = icmp sge i32 %n, -1 374 %n.div.2 = sdiv i32 %n, 2 375 %n.div.2.ext = sext i32 %n.div.2 to i64 376 call void(i1, ...) @llvm.experimental.guard(i1 %cmp1) [ "deopt"() ] 377 br label %header 378 379header: 380 %indvar = phi i64 [ %indvar.next, %header ], [ 0, %entry ] 381 %indvar.next = add i64 %indvar, 1 382 %exitcond = icmp sge i64 %n.div.2.ext, %indvar 383 br i1 %exitcond, label %header, label %exit 384 385exit: 386 ret void 387} 388 389define void @test_ext_04neg(i32 %n) nounwind { 390; Prove that (n >= -2) =\=> (n / 2 >= 0). 391; CHECK-LABEL: 'test_ext_04neg' 392; CHECK-NEXT: Determining loop execution counts for: @test_ext_04neg 393; CHECK-NEXT: Loop %header: backedge-taken count is (0 smax (1 + (sext i32 %n.div.2 to i64))<nsw>) 394; CHECK-NEXT: Loop %header: constant max backedge-taken count is i64 1073741824 395; CHECK-NEXT: Loop %header: symbolic max backedge-taken count is (0 smax (1 + (sext i32 %n.div.2 to i64))<nsw>) 396; CHECK-NEXT: Loop %header: Trip multiple is 1 397; 398entry: 399 %cmp1 = icmp sge i32 %n, -2 400 %n.div.2 = sdiv i32 %n, 2 401 %n.div.2.ext = sext i32 %n.div.2 to i64 402 call void(i1, ...) @llvm.experimental.guard(i1 %cmp1) [ "deopt"() ] 403 br label %header 404 405header: 406 %indvar = phi i64 [ %indvar.next, %header ], [ 0, %entry ] 407 %indvar.next = add i64 %indvar, 1 408 %exitcond = icmp sge i64 %n.div.2.ext, %indvar 409 br i1 %exitcond, label %header, label %exit 410 411exit: 412 ret void 413} 414 415define void @swapped_predicate(i32 %n) { 416; Prove that (n s>= 1) ===> (0 s>= -n / 2). 417; CHECK-LABEL: 'swapped_predicate' 418; CHECK-NEXT: Determining loop execution counts for: @swapped_predicate 419; CHECK-NEXT: Loop %header: backedge-taken count is (1 + %n.div.2)<nuw><nsw> 420; CHECK-NEXT: Loop %header: constant max backedge-taken count is i32 1073741824 421; CHECK-NEXT: Loop %header: symbolic max backedge-taken count is (1 + %n.div.2)<nuw><nsw> 422; CHECK-NEXT: Loop %header: Trip multiple is 1 423; 424entry: 425 %cmp1 = icmp sge i32 %n, 1 426 %n.div.2 = sdiv i32 %n, 2 427 call void @llvm.assume(i1 %cmp1) 428 br label %header 429 430header: 431 %indvar = phi i32 [ %indvar.next, %header ], [ 0, %entry ] 432 %indvar.next = add i32 %indvar, 1 433 %minus.indvar = sub nsw i32 0, %indvar 434 %minus.n.div.2 = sub nsw i32 0, %n.div.2 435 %exitcond = icmp sge i32 %minus.indvar, %minus.n.div.2 436 br i1 %exitcond, label %header, label %exit 437 438exit: 439 ret void 440} 441 442define void @swapped_predicate_neg(i32 %n) { 443; Prove that (n s>= 1) =\=> (-n / 2 s>= 0). 444; CHECK-LABEL: 'swapped_predicate_neg' 445; CHECK-NEXT: Determining loop execution counts for: @swapped_predicate_neg 446; CHECK-NEXT: Loop %header: Unpredictable backedge-taken count. 447; CHECK-NEXT: Loop %header: Unpredictable constant max backedge-taken count. 448; CHECK-NEXT: Loop %header: Unpredictable symbolic max backedge-taken count. 449; 450entry: 451 %cmp1 = icmp sge i32 %n, 1 452 %n.div.2 = sdiv i32 %n, 2 453 call void @llvm.assume(i1 %cmp1) 454 br label %header 455 456header: 457 %indvar = phi i32 [ %indvar.next, %header ], [ 0, %entry ] 458 %indvar.next = add i32 %indvar, 1 459 %minus.indvar = sub nsw i32 0, %indvar 460 %minus.n.div.2 = sub nsw i32 0, %n.div.2 461 %exitcond = icmp sge i32 %minus.n.div.2, %minus.indvar 462 br i1 %exitcond, label %header, label %exit 463 464exit: 465 ret void 466} 467