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