1; RUN: opt < %s -S -analyze -enable-new-pm=0 -scalar-evolution | FileCheck %s 2; RUN: opt < %s -S -disable-output "-passes=print<scalar-evolution>" 2>&1 | FileCheck %s 3 4; Positive and negative tests for inferring flags like nsw from 5; reasoning about how a poison value from overflow would trigger 6; undefined behavior. 7 8define void @foo() { 9 ret void 10} 11 12; Example where an add should get the nsw flag, so that a sext can be 13; distributed over the add. 14define void @test-add-nsw(float* %input, i32 %offset, i32 %numIterations) { 15; CHECK-LABEL: @test-add-nsw 16entry: 17 br label %loop 18loop: 19 %i = phi i32 [ %nexti, %loop ], [ 0, %entry ] 20 21; CHECK: %index32 = 22; CHECK: --> {%offset,+,1}<nsw> 23 %index32 = add nsw i32 %i, %offset 24 25; CHECK: %index64 = 26; CHECK: --> {(sext i32 %offset to i64),+,1}<nsw> 27 %index64 = sext i32 %index32 to i64 28 29 %ptr = getelementptr inbounds float, float* %input, i64 %index64 30 %nexti = add nsw i32 %i, 1 31 %f = load float, float* %ptr, align 4 32 call void @foo() 33 %exitcond = icmp eq i32 %nexti, %numIterations 34 br i1 %exitcond, label %exit, label %loop 35exit: 36 ret void 37} 38 39; Example where an add should get the nuw flag. 40define void @test-add-nuw(float* %input, i32 %offset, i32 %numIterations) { 41; CHECK-LABEL: @test-add-nuw 42entry: 43 br label %loop 44loop: 45 %i = phi i32 [ %nexti, %loop ], [ 0, %entry ] 46 47; CHECK: %index32 = 48; CHECK: --> {%offset,+,1}<nuw> 49 %index32 = add nuw i32 %i, %offset 50 51 %ptr = getelementptr inbounds float, float* %input, i32 %index32 52 %nexti = add nuw i32 %i, 1 53 %f = load float, float* %ptr, align 4 54 %exitcond = icmp eq i32 %nexti, %numIterations 55 br i1 %exitcond, label %exit, label %loop 56 57exit: 58 ret void 59} 60 61define void @test-add-nuw-from-icmp(float* %input, i32 %offset, 62 i32 %numIterations) { 63; CHECK-LABEL: @test-add-nuw-from-icmp 64entry: 65 br label %loop 66loop: 67 %i = phi i32 [ %nexti, %loop ], [ 0, %entry ] 68 69; CHECK: %index32 = 70; CHECK: --> {%offset,+,1}<nuw> 71 %index32 = add nuw i32 %i, %offset 72 %cmp = icmp sgt i32 %index32, 0 73 %cmp.idx = sext i1 %cmp to i32 74 75 %ptr = getelementptr inbounds float, float* %input, i32 %cmp.idx 76 %nexti = add nuw i32 %i, 1 77 %f = load float, float* %ptr, align 4 78 %exitcond = icmp eq i32 %nexti, %numIterations 79 br i1 %exitcond, label %exit, label %loop 80 81exit: 82 ret void 83} 84 85; With no load to trigger UB from poison, we cannot infer nsw. 86define void @test-add-no-load(float* %input, i32 %offset, i32 %numIterations) { 87; CHECK-LABEL: @test-add-no-load 88entry: 89 br label %loop 90loop: 91 %i = phi i32 [ %nexti, %loop ], [ 0, %entry ] 92 93; CHECK: %index32 = 94; CHECK: --> {%offset,+,1}<nw> 95 %index32 = add nsw i32 %i, %offset 96 97 %ptr = getelementptr inbounds float, float* %input, i32 %index32 98 %nexti = add nuw i32 %i, 1 99 %exitcond = icmp eq i32 %nexti, %numIterations 100 br i1 %exitcond, label %exit, label %loop 101 102exit: 103 ret void 104} 105 106; The current code is only supposed to look at the loop header, so 107; it should not infer nsw in this case, as that would require looking 108; outside the loop header. 109define void @test-add-not-header(float* %input, i32 %offset, i32 %numIterations) { 110; CHECK-LABEL: @test-add-not-header 111entry: 112 br label %loop 113loop: 114 %i = phi i32 [ %nexti, %loop2 ], [ 0, %entry ] 115 br label %loop2 116loop2: 117 118; CHECK: %index32 = 119; CHECK: --> {%offset,+,1}<nw> 120 %index32 = add nsw i32 %i, %offset 121 122 %ptr = getelementptr inbounds float, float* %input, i32 %index32 123 %nexti = add nsw i32 %i, 1 124 %f = load float, float* %ptr, align 4 125 %exitcond = icmp eq i32 %nexti, %numIterations 126 br i1 %exitcond, label %exit, label %loop 127exit: 128 ret void 129} 130 131; Same thing as test-add-not-header, but in this case only the load 132; instruction is outside the loop header. 133define void @test-add-not-header2(float* %input, i32 %offset, i32 %numIterations) { 134; CHECK-LABEL: @test-add-not-header2 135entry: 136 br label %loop 137loop: 138 %i = phi i32 [ %nexti, %loop2 ], [ 0, %entry ] 139 140; CHECK: %index32 = 141; CHECK: --> {%offset,+,1}<nsw> 142 %index32 = add nsw i32 %i, %offset 143 144 %ptr = getelementptr inbounds float, float* %input, i32 %index32 145 %nexti = add nsw i32 %i, 1 146 br label %loop2 147loop2: 148 %f = load float, float* %ptr, align 4 149 %exitcond = icmp eq i32 %nexti, %numIterations 150 br i1 %exitcond, label %exit, label %loop 151exit: 152 ret void 153} 154 155; Similar to test-add-not-header, but in this case the load 156; instruction may not be executed. 157define void @test-add-not-header3(float* %input, i32 %offset, i32 %numIterations, 158 i1* %cond_buf) { 159; CHECK-LABEL: @test-add-not-header3 160entry: 161 br label %loop 162loop: 163 %i = phi i32 [ %nexti, %loop2 ], [ 0, %entry ] 164 165; CHECK: %index32 = 166; CHECK: --> {%offset,+,1}<nw> 167 %index32 = add nsw i32 %i, %offset 168 169 %ptr = getelementptr inbounds float, float* %input, i32 %index32 170 %nexti = add nsw i32 %i, 1 171 %cond = load volatile i1, i1* %cond_buf 172 br i1 %cond, label %loop2, label %exit 173loop2: 174 %f = load float, float* %ptr, align 4 175 %exitcond = icmp eq i32 %nexti, %numIterations 176 br i1 %exitcond, label %exit, label %loop 177exit: 178 ret void 179} 180 181; Same thing as test-add-not-header2, except we have a few extra 182; blocks. 183define void @test-add-not-header4(float* %input, i32 %offset, i32 %numIterations) { 184; CHECK-LABEL: @test-add-not-header4 185entry: 186 br label %loop 187loop: 188 %i = phi i32 [ %nexti, %loop2 ], [ 0, %entry ] 189 190; CHECK: %index32 = 191; CHECK: --> {%offset,+,1}<nsw> 192 %index32 = add nsw i32 %i, %offset 193 194 %ptr = getelementptr inbounds float, float* %input, i32 %index32 195 %nexti = add nsw i32 %i, 1 196 br label %loop3 197loop3: 198 br label %loop4 199loop4: 200 br label %loop2 201loop2: 202 %f = load float, float* %ptr, align 4 203 %exitcond = icmp eq i32 %nexti, %numIterations 204 br i1 %exitcond, label %exit, label %loop 205exit: 206 ret void 207} 208 209; Demonstrate why we need a Visited set in llvm::programUndefinedIfPoison. 210define void @test-add-not-header5(float* %input, i32 %offset) { 211; CHECK-LABEL: @test-add-not-header5 212entry: 213 br label %loop 214loop: 215 %i = phi i32 [ %nexti, %loop ], [ 0, %entry ] 216 217; CHECK: %index32 = 218; CHECK: --> {%offset,+,1}<nw> 219 %index32 = add nsw i32 %i, %offset 220 221 %ptr = getelementptr inbounds float, float* %input, i32 %index32 222 %nexti = add nsw i32 %i, 1 223 br label %loop 224 225exit: 226 ret void 227} 228 229; The call instruction makes it not guaranteed that the add will be 230; executed, since it could run forever or throw an exception, so we 231; cannot assume that the UB is realized. 232define void @test-add-call(float* %input, i32 %offset, i32 %numIterations) { 233; CHECK-LABEL: @test-add-call 234entry: 235 br label %loop 236loop: 237 %i = phi i32 [ %nexti, %loop ], [ 0, %entry ] 238 239; CHECK: %index32 = 240; CHECK: --> {%offset,+,1}<nw> 241 call void @foo() 242 %index32 = add nsw i32 %i, %offset 243 244 %ptr = getelementptr inbounds float, float* %input, i32 %index32 245 %nexti = add nsw i32 %i, 1 246 %f = load float, float* %ptr, align 4 247 %exitcond = icmp eq i32 %nexti, %numIterations 248 br i1 %exitcond, label %exit, label %loop 249exit: 250 ret void 251} 252 253; Same issue as test-add-call, but this time the call is between the 254; producer of poison and the load that consumes it. 255define void @test-add-call2(float* %input, i32 %offset, i32 %numIterations) { 256; CHECK-LABEL: @test-add-call2 257entry: 258 br label %loop 259loop: 260 %i = phi i32 [ %nexti, %loop ], [ 0, %entry ] 261 262; CHECK: %index32 = 263; CHECK: --> {%offset,+,1}<nw> 264 %index32 = add nsw i32 %i, %offset 265 266 %ptr = getelementptr inbounds float, float* %input, i32 %index32 267 %nexti = add nsw i32 %i, 1 268 call void @foo() 269 %f = load float, float* %ptr, align 4 270 %exitcond = icmp eq i32 %nexti, %numIterations 271 br i1 %exitcond, label %exit, label %loop 272exit: 273 ret void 274} 275 276; Any poison input makes getelementptr produce poison 277define void @test-gep-propagates-poison(float* %input, i32 %offset, i32 %numIterations) { 278; CHECK-LABEL: @test-gep-propagates-poison 279entry: 280 br label %loop 281loop: 282 %i = phi i32 [ %nexti, %loop ], [ 0, %entry ] 283 284; CHECK: %index32 = 285; CHECK: --> {%offset,+,1}<nsw> 286 %index32 = add nsw i32 %i, %offset 287 288 %ptr = getelementptr float, float* %input, i32 %index32 289 %nexti = add nsw i32 %i, 1 290 %f = load float, float* %ptr, align 4 291 %exitcond = icmp eq i32 %nexti, %numIterations 292 br i1 %exitcond, label %exit, label %loop 293exit: 294 ret void 295} 296 297; Multiplication by a non-zero constant propagates poison if there is 298; a nuw or nsw flag on the multiplication. 299define void @test-add-mul-propagates(float* %input, i32 %offset, i32 %numIterations) { 300; CHECK-LABEL: @test-add-mul-propagates 301entry: 302 br label %loop 303loop: 304 %i = phi i32 [ %nexti, %loop ], [ 0, %entry ] 305 306; CHECK: %index32 = 307; CHECK: --> {%offset,+,1}<nsw> 308 %index32 = add nsw i32 %i, %offset 309 310 %indexmul = mul nuw i32 %index32, 2 311 %ptr = getelementptr inbounds float, float* %input, i32 %indexmul 312 %nexti = add nsw i32 %i, 1 313 %f = load float, float* %ptr, align 4 314 %exitcond = icmp eq i32 %nexti, %numIterations 315 br i1 %exitcond, label %exit, label %loop 316exit: 317 ret void 318} 319 320; Any poison input to multiplication propages poison. 321define void @test-mul-propagates-poison(float* %input, i32 %offset, i32 %numIterations) { 322; CHECK-LABEL: @test-mul-propagates-poison 323entry: 324 br label %loop 325loop: 326 %i = phi i32 [ %nexti, %loop ], [ 0, %entry ] 327 328; CHECK: %index32 = 329; CHECK: --> {%offset,+,1}<nsw> 330 %index32 = add nsw i32 %i, %offset 331 332 %indexmul = mul nsw i32 %index32, %offset 333 %ptr = getelementptr inbounds float, float* %input, i32 %indexmul 334 %nexti = add nsw i32 %i, 1 335 %f = load float, float* %ptr, align 4 336 %exitcond = icmp eq i32 %nexti, %numIterations 337 br i1 %exitcond, label %exit, label %loop 338exit: 339 ret void 340} 341 342define void @test-mul-propagates-poison-2(float* %input, i32 %offset, i32 %numIterations) { 343; CHECK-LABEL: @test-mul-propagates-poison-2 344entry: 345 br label %loop 346loop: 347 %i = phi i32 [ %nexti, %loop ], [ 0, %entry ] 348 349; CHECK: %index32 = 350; CHECK: --> {%offset,+,1}<nsw> 351 %index32 = add nsw i32 %i, %offset 352 353 %indexmul = mul i32 %index32, 2 354 %ptr = getelementptr inbounds float, float* %input, i32 %indexmul 355 %nexti = add nsw i32 %i, 1 356 %f = load float, float* %ptr, align 4 357 %exitcond = icmp eq i32 %nexti, %numIterations 358 br i1 %exitcond, label %exit, label %loop 359exit: 360 ret void 361} 362 363; Division by poison triggers UB. 364define void @test-add-div(float* %input, i32 %offset, i32 %numIterations) { 365; CHECK-LABEL: @test-add-div 366entry: 367 br label %loop 368loop: 369 %i = phi i32 [ %nexti, %loop ], [ 0, %entry ] 370 371; CHECK: %j = 372; CHECK: --> {%offset,+,1}<nsw> 373 %j = add nsw i32 %i, %offset 374 375 %q = sdiv i32 %numIterations, %j 376 %nexti = add nsw i32 %i, 1 377 %exitcond = icmp eq i32 %nexti, %numIterations 378 br i1 %exitcond, label %exit, label %loop 379exit: 380 ret void 381} 382 383; Remainder of poison by non-poison divisor does not trigger UB. 384define void @test-add-div2(float* %input, i32 %offset, i32 %numIterations) { 385; CHECK-LABEL: @test-add-div2 386entry: 387 br label %loop 388loop: 389 %i = phi i32 [ %nexti, %loop ], [ 0, %entry ] 390 391; CHECK: %j = 392; CHECK: --> {%offset,+,1}<nw> 393 %j = add nsw i32 %i, %offset 394 395 %q = sdiv i32 %j, %numIterations 396 %nexti = add nsw i32 %i, 1 397 %exitcond = icmp eq i32 %nexti, %numIterations 398 br i1 %exitcond, label %exit, label %loop 399exit: 400 ret void 401} 402 403; Store to poison address triggers UB. 404define void @test-add-store(float* %input, i32 %offset, i32 %numIterations) { 405; CHECK-LABEL: @test-add-store 406entry: 407 br label %loop 408loop: 409 %i = phi i32 [ %nexti, %loop ], [ 0, %entry ] 410 411; CHECK: %index32 = 412; CHECK: --> {%offset,+,1}<nsw> 413 %index32 = add nsw i32 %i, %offset 414 415 %ptr = getelementptr inbounds float, float* %input, i32 %index32 416 %nexti = add nsw i32 %i, 1 417 store float 1.0, float* %ptr, align 4 418 %exitcond = icmp eq i32 %nexti, %numIterations 419 br i1 %exitcond, label %exit, label %loop 420exit: 421 ret void 422} 423 424; Three sequential adds where the middle add should have nsw. There is 425; a special case for sequential adds and this test covers that. We have to 426; put the final add first in the program since otherwise the special case 427; is not triggered, hence the strange basic block ordering. 428define void @test-add-twice(float* %input, i32 %offset, i32 %numIterations) { 429; CHECK-LABEL: @test-add-twice 430entry: 431 br label %loop 432loop2: 433; CHECK: %seq = 434; CHECK: --> {(2 + %offset),+,1}<nw> 435 %seq = add nsw nuw i32 %index32, 1 436 %exitcond = icmp eq i32 %nexti, %numIterations 437 br i1 %exitcond, label %exit, label %loop 438 439loop: 440 %i = phi i32 [ %nexti, %loop2 ], [ 0, %entry ] 441 442 %j = add nsw i32 %i, 1 443; CHECK: %index32 = 444; CHECK: --> {(1 + %offset)<nsw>,+,1}<nsw> 445 %index32 = add nsw i32 %j, %offset 446 447 %ptr = getelementptr inbounds float, float* %input, i32 %index32 448 %nexti = add nsw i32 %i, 1 449 store float 1.0, float* %ptr, align 4 450 br label %loop2 451exit: 452 ret void 453} 454 455; Example where a mul should get the nsw flag, so that a sext can be 456; distributed over the mul. 457define void @test-mul-nsw(float* %input, i32 %stride, i32 %numIterations) { 458; CHECK-LABEL: @test-mul-nsw 459entry: 460 br label %loop 461loop: 462 %i = phi i32 [ %nexti, %loop ], [ 0, %entry ] 463 464; CHECK: %index32 = 465; CHECK: --> {0,+,%stride}<nsw> 466 %index32 = mul nsw i32 %i, %stride 467 468; CHECK: %index64 = 469; CHECK: --> {0,+,(sext i32 %stride to i64)}<nsw> 470 %index64 = sext i32 %index32 to i64 471 472 %ptr = getelementptr inbounds float, float* %input, i64 %index64 473 %nexti = add nsw i32 %i, 1 474 %f = load float, float* %ptr, align 4 475 %exitcond = icmp eq i32 %nexti, %numIterations 476 br i1 %exitcond, label %exit, label %loop 477exit: 478 ret void 479} 480 481; Example where a mul should get the nuw flag. 482define void @test-mul-nuw(float* %input, i32 %stride, i32 %numIterations) { 483; CHECK-LABEL: @test-mul-nuw 484entry: 485 br label %loop 486loop: 487 %i = phi i32 [ %nexti, %loop ], [ 0, %entry ] 488 489; CHECK: %index32 = 490; CHECK: --> {0,+,%stride}<nuw> 491 %index32 = mul nuw i32 %i, %stride 492 493 %ptr = getelementptr inbounds float, float* %input, i32 %index32 494 %nexti = add nuw i32 %i, 1 495 %f = load float, float* %ptr, align 4 496 %exitcond = icmp eq i32 %nexti, %numIterations 497 br i1 %exitcond, label %exit, label %loop 498 499exit: 500 ret void 501} 502 503; Example where a shl should get the nsw flag, so that a sext can be 504; distributed over the shl. 505define void @test-shl-nsw(float* %input, i32 %start, i32 %numIterations) { 506; CHECK-LABEL: @test-shl-nsw 507entry: 508 br label %loop 509loop: 510 %i = phi i32 [ %nexti, %loop ], [ %start, %entry ] 511 512; CHECK: %index32 = 513; CHECK: --> {(256 * %start),+,256}<nsw> 514 %index32 = shl nsw i32 %i, 8 515 516; CHECK: %index64 = 517; CHECK: --> {(sext i32 (256 * %start) to i64),+,256}<nsw> 518 %index64 = sext i32 %index32 to i64 519 520 %ptr = getelementptr inbounds float, float* %input, i64 %index64 521 %nexti = add nsw i32 %i, 1 522 %f = load float, float* %ptr, align 4 523 %exitcond = icmp eq i32 %nexti, %numIterations 524 br i1 %exitcond, label %exit, label %loop 525exit: 526 ret void 527} 528 529; Example where a shl should get the nuw flag 530define void @test-shl-nuw-edgecase(float* %input, i32 %start, i32 %numIterations) { 531; CHECK-LABEL: @test-shl-nuw-edgecase 532entry: 533 br label %loop 534loop: 535 %i = phi i32 [ %nexti, %loop ], [ %start, %entry ] 536 537; CHECK: %index32 = 538; CHECK: --> {(-2147483648 * %start),+,-2147483648}<%loop> 539 %index32 = shl nuw i32 %i, 31 540 541; CHECK: %index64 = 542; CHECK: --> (sext i32 {(-2147483648 * %start),+,-2147483648}<%loop> 543 %index64 = sext i32 %index32 to i64 544 545 %ptr = getelementptr inbounds float, float* %input, i64 %index64 546 %nexti = add nsw i32 %i, 1 547 %f = load float, float* %ptr, align 4 548 %exitcond = icmp eq i32 %nexti, %numIterations 549 br i1 %exitcond, label %exit, label %loop 550exit: 551 ret void 552} 553 554; Example where a shl should get the nuw flag 555define void @test-shl-nuw-nsw(float* %input, i32 %start, i32 %numIterations) { 556; CHECK-LABEL: @test-shl-nuw-nsw 557entry: 558 br label %loop 559loop: 560 %i = phi i32 [ %nexti, %loop ], [ %start, %entry ] 561 562; CHECK: %index32 = 563; CHECK: --> {(-2147483648 * %start),+,-2147483648}<nsw><%loop> 564 %index32 = shl nuw nsw i32 %i, 31 565 566; CHECK: %index64 = 567; CHECK: --> {(sext i32 (-2147483648 * %start) to i64),+,-2147483648}<nsw><%loop> 568 %index64 = sext i32 %index32 to i64 569 570 %ptr = getelementptr inbounds float, float* %input, i64 %index64 571 %nexti = add nsw i32 %i, 1 572 %f = load float, float* %ptr, align 4 573 %exitcond = icmp eq i32 %nexti, %numIterations 574 br i1 %exitcond, label %exit, label %loop 575exit: 576 ret void 577} 578 579; Example where a shl should not get the nsw flag 580define void @test-shl-no-nsw(float* %input, i32 %start, i32 %numIterations) { 581; CHECK-LABEL: @test-shl-no-nsw 582entry: 583 br label %loop 584loop: 585 %i = phi i32 [ %nexti, %loop ], [ %start, %entry ] 586 587; CHECK: %index32 = 588; CHECK: --> {(-2147483648 * %start),+,-2147483648}<%loop> 589 %index32 = shl nsw i32 %i, 31 590 591; CHECK: %index64 = 592; CHECK: --> (sext i32 {(-2147483648 * %start),+,-2147483648}<%loop> 593 %index64 = sext i32 %index32 to i64 594 595 %ptr = getelementptr inbounds float, float* %input, i64 %index64 596 %nexti = add nsw i32 %i, 1 597 %f = load float, float* %ptr, align 4 598 %exitcond = icmp eq i32 %nexti, %numIterations 599 br i1 %exitcond, label %exit, label %loop 600exit: 601 ret void 602} 603 604; Example where a shl should get the nsw flag. 605define void @test-shl-nsw-edgecase(float* %input, i32 %start, i32 %numIterations) { 606; CHECK-LABEL: @test-shl-nsw-edgecase 607entry: 608 br label %loop 609loop: 610 %i = phi i32 [ %nexti, %loop ], [ %start, %entry ] 611 612; CHECK: %index32 = 613; CHECK: --> {(1073741824 * %start),+,1073741824}<nsw><%loop> 614 %index32 = shl nsw i32 %i, 30 615 616; CHECK: %index64 = 617; CHECK: --> {(sext i32 (1073741824 * %start) to i64),+,1073741824}<nsw><%loop> 618 %index64 = sext i32 %index32 to i64 619 620 %ptr = getelementptr inbounds float, float* %input, i64 %index64 621 %nexti = add nsw i32 %i, 1 622 %f = load float, float* %ptr, align 4 623 %exitcond = icmp eq i32 %nexti, %numIterations 624 br i1 %exitcond, label %exit, label %loop 625exit: 626 ret void 627} 628 629; Example where a shl should get the nuw flag. 630define void @test-shl-nuw(float* %input, i32 %numIterations) { 631; CHECK-LABEL: @test-shl-nuw 632entry: 633 br label %loop 634loop: 635 %i = phi i32 [ %nexti, %loop ], [ 0, %entry ] 636 637; CHECK: %index32 = 638; CHECK: --> {0,+,512}<nuw> 639 %index32 = shl nuw i32 %i, 9 640 641 %ptr = getelementptr inbounds float, float* %input, i32 %index32 642 %nexti = add nuw i32 %i, 1 643 %f = load float, float* %ptr, align 4 644 %exitcond = icmp eq i32 %nexti, %numIterations 645 br i1 %exitcond, label %exit, label %loop 646 647exit: 648 ret void 649} 650 651; Example where a sub should *not* get the nsw flag, because of how 652; scalar evolution represents A - B as A + (-B) and -B can wrap even 653; in cases where A - B does not. 654define void @test-sub-no-nsw(float* %input, i32 %start, i32 %sub, i32 %numIterations) { 655; CHECK-LABEL: @test-sub-no-nsw 656entry: 657 br label %loop 658loop: 659 %i = phi i32 [ %nexti, %loop ], [ %start, %entry ] 660 661; CHECK: %index32 = 662; CHECK: --> {((-1 * %sub) + %start),+,1}<nw> 663 %index32 = sub nsw i32 %i, %sub 664 %index64 = sext i32 %index32 to i64 665 666 %ptr = getelementptr inbounds float, float* %input, i64 %index64 667 %nexti = add nsw i32 %i, 1 668 %f = load float, float* %ptr, align 4 669 %exitcond = icmp eq i32 %nexti, %numIterations 670 br i1 %exitcond, label %exit, label %loop 671exit: 672 ret void 673} 674 675; Example where a sub should get the nsw flag as the RHS cannot be the 676; minimal signed value. 677define void @test-sub-nsw(float* %input, i32 %start, i32 %sub, i32 %numIterations) { 678; CHECK-LABEL: @test-sub-nsw 679entry: 680 %halfsub = ashr i32 %sub, 1 681 br label %loop 682loop: 683 %i = phi i32 [ %nexti, %loop ], [ %start, %entry ] 684 685; CHECK: %index32 = 686; CHECK: --> {((-1 * %halfsub)<nsw> + %start)<nsw>,+,1}<nsw> 687 %index32 = sub nsw i32 %i, %halfsub 688 %index64 = sext i32 %index32 to i64 689 690 %ptr = getelementptr inbounds float, float* %input, i64 %index64 691 %nexti = add nsw i32 %i, 1 692 %f = load float, float* %ptr, align 4 693 %exitcond = icmp eq i32 %nexti, %numIterations 694 br i1 %exitcond, label %exit, label %loop 695exit: 696 ret void 697} 698 699; Example where a sub should get the nsw flag, since the LHS is non-negative, 700; which implies that the RHS cannot be the minimal signed value. 701define void @test-sub-nsw-lhs-non-negative(float* %input, i32 %sub, i32 %numIterations) { 702; CHECK-LABEL: @test-sub-nsw-lhs-non-negative 703entry: 704 br label %loop 705loop: 706 %i = phi i32 [ %nexti, %loop ], [ 0, %entry ] 707 708; CHECK: %index32 = 709; CHECK: --> {(-1 * %sub),+,1}<nsw> 710 %index32 = sub nsw i32 %i, %sub 711 712; CHECK: %index64 = 713; CHECK: --> {(-1 * (sext i32 %sub to i64))<nsw>,+,1}<nsw 714 %index64 = sext i32 %index32 to i64 715 716 %ptr = getelementptr inbounds float, float* %input, i64 %index64 717 %nexti = add nsw i32 %i, 1 718 %f = load float, float* %ptr, align 4 719 %exitcond = icmp eq i32 %nexti, %numIterations 720 br i1 %exitcond, label %exit, label %loop 721exit: 722 ret void 723} 724 725; Example checking that a sext is pushed onto a sub's operands if the sub is an 726; overflow intrinsic. 727define void @test-sext-sub(float* %input, i32 %sub, i32 %numIterations) { 728; CHECK-LABEL: @test-sext-sub 729entry: 730 br label %loop 731loop: 732 %i = phi i32 [ %nexti, %cont ], [ 0, %entry ] 733 734; CHECK: %val = extractvalue { i32, i1 } %ssub, 0 735; CHECK: --> {(-1 * %sub),+,1}<nw> 736 %ssub = tail call { i32, i1 } @llvm.ssub.with.overflow.i32(i32 %i, i32 %sub) 737 %val = extractvalue { i32, i1 } %ssub, 0 738 %ovfl = extractvalue { i32, i1 } %ssub, 1 739 br i1 %ovfl, label %trap, label %cont 740 741trap: 742 tail call void @llvm.trap() 743 unreachable 744 745cont: 746; CHECK: %index64 = 747; CHECK: --> {(-1 * (sext i32 %sub to i64))<nsw>,+,1}<nsw 748 %index64 = sext i32 %val to i64 749 750 %ptr = getelementptr inbounds float, float* %input, i64 %index64 751 %nexti = add nsw i32 %i, 1 752 %f = load float, float* %ptr, align 4 753 %exitcond = icmp eq i32 %nexti, %numIterations 754 br i1 %exitcond, label %exit, label %loop 755exit: 756 ret void 757} 758 759; Two adds with a sub in the middle and the sub should have nsw. There is 760; a special case for sequential adds/subs and this test covers that. We have to 761; put the final add first in the program since otherwise the special case 762; is not triggered, hence the strange basic block ordering. 763define void @test-sub-with-add(float* %input, i32 %offset, i32 %numIterations) { 764; CHECK-LABEL: @test-sub-with-add 765entry: 766 br label %loop 767loop2: 768; CHECK: %seq = 769; CHECK: --> {(2 + (-1 * %offset)),+,1}<nw> 770 %seq = add nsw nuw i32 %index32, 1 771 %exitcond = icmp eq i32 %nexti, %numIterations 772 br i1 %exitcond, label %exit, label %loop 773 774loop: 775 %i = phi i32 [ %nexti, %loop2 ], [ 0, %entry ] 776 777 %j = add nsw i32 %i, 1 778; CHECK: %index32 = 779; CHECK: --> {(1 + (-1 * %offset))<nsw>,+,1}<nsw> 780 %index32 = sub nsw i32 %j, %offset 781 782 %ptr = getelementptr inbounds float, float* %input, i32 %index32 783 %nexti = add nsw i32 %i, 1 784 store float 1.0, float* %ptr, align 4 785 br label %loop2 786exit: 787 ret void 788} 789 790 791; Subtraction of two recurrences. The addition in the SCEV that this 792; maps to is NSW, but the negation of the RHS does not since that 793; recurrence could be the most negative representable value. 794define void @subrecurrences(i32 %outer_l, i32 %inner_l, i32 %val) { 795; CHECK-LABEL: @subrecurrences 796 entry: 797 br label %outer 798 799outer: 800 %o_idx = phi i32 [ 0, %entry ], [ %o_idx.inc, %outer.be ] 801 %o_idx.inc = add nsw i32 %o_idx, 1 802 %cond = icmp eq i32 %o_idx, %val 803 br i1 %cond, label %inner, label %outer.be 804 805inner: 806 %i_idx = phi i32 [ 0, %outer ], [ %i_idx.inc, %inner ] 807 %i_idx.inc = add nsw i32 %i_idx, 1 808; CHECK: %v = 809; CHECK-NEXT: --> {{[{][{]}}-1,+,-1}<nw><%outer>,+,1}<nsw><%inner> 810 %v = sub nsw i32 %i_idx, %o_idx.inc 811 %forub = udiv i32 1, %v 812 %cond2 = icmp eq i32 %i_idx, %inner_l 813 br i1 %cond2, label %outer.be, label %inner 814 815outer.be: 816 %cond3 = icmp eq i32 %o_idx, %outer_l 817 br i1 %cond3, label %exit, label %outer 818 819exit: 820 ret void 821} 822 823 824; PR28932: Don't assert on non-SCEV-able value %2. 825%struct.anon = type { i8* } 826@a = common global %struct.anon* null, align 8 827@b = common global i32 0, align 4 828declare { i32, i1 } @llvm.ssub.with.overflow.i32(i32, i32) 829declare void @llvm.trap() 830define i32 @pr28932() { 831entry: 832 %.pre = load %struct.anon*, %struct.anon** @a, align 8 833 %.pre7 = load i32, i32* @b, align 4 834 br label %for.cond 835 836for.cond: ; preds = %cont6, %entry 837 %0 = phi i32 [ %3, %cont6 ], [ %.pre7, %entry ] 838 %1 = phi %struct.anon* [ %.ph, %cont6 ], [ %.pre, %entry ] 839 %tobool = icmp eq %struct.anon* %1, null 840 %2 = tail call { i32, i1 } @llvm.ssub.with.overflow.i32(i32 %0, i32 1) 841 %3 = extractvalue { i32, i1 } %2, 0 842 %4 = extractvalue { i32, i1 } %2, 1 843 %idxprom = sext i32 %3 to i64 844 %5 = getelementptr inbounds %struct.anon, %struct.anon* %1, i64 0, i32 0 845 %6 = load i8*, i8** %5, align 8 846 %7 = getelementptr inbounds i8, i8* %6, i64 %idxprom 847 %8 = load i8, i8* %7, align 1 848 br i1 %tobool, label %if.else, label %if.then 849 850if.then: ; preds = %for.cond 851 br i1 %4, label %trap, label %cont6 852 853trap: ; preds = %if.else, %if.then 854 tail call void @llvm.trap() 855 unreachable 856 857if.else: ; preds = %for.cond 858 br i1 %4, label %trap, label %cont1 859 860cont1: ; preds = %if.else 861 %conv5 = sext i8 %8 to i64 862 %9 = inttoptr i64 %conv5 to %struct.anon* 863 store %struct.anon* %9, %struct.anon** @a, align 8 864 br label %cont6 865 866cont6: ; preds = %cont1, %if.then 867 %.ph = phi %struct.anon* [ %9, %cont1 ], [ %1, %if.then ] 868 store i32 %3, i32* @b, align 4 869 br label %for.cond 870} 871