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 60; With no load to trigger UB from poison, we cannot infer nsw. 61define void @test-add-no-load(float* %input, i32 %offset, i32 %numIterations) { 62; CHECK-LABEL: @test-add-no-load 63entry: 64 br label %loop 65loop: 66 %i = phi i32 [ %nexti, %loop ], [ 0, %entry ] 67 68; CHECK: %index32 = 69; CHECK: --> {%offset,+,1}<nw> 70 %index32 = add nsw i32 %i, %offset 71 72 %ptr = getelementptr inbounds float, float* %input, i32 %index32 73 %nexti = add nuw i32 %i, 1 74 %exitcond = icmp eq i32 %nexti, %numIterations 75 br i1 %exitcond, label %exit, label %loop 76 77exit: 78 ret void 79} 80 81; The current code is only supposed to look at the loop header, so 82; it should not infer nsw in this case, as that would require looking 83; outside the loop header. 84define void @test-add-not-header(float* %input, i32 %offset, i32 %numIterations) { 85; CHECK-LABEL: @test-add-not-header 86entry: 87 br label %loop 88loop: 89 %i = phi i32 [ %nexti, %loop2 ], [ 0, %entry ] 90 br label %loop2 91loop2: 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 nsw i32 %i, 1 99 %f = load float, float* %ptr, align 4 100 %exitcond = icmp eq i32 %nexti, %numIterations 101 br i1 %exitcond, label %exit, label %loop 102exit: 103 ret void 104} 105 106; Same thing as test-add-not-header, but in this case only the load 107; instruction is outside the loop header. 108define void @test-add-not-header2(float* %input, i32 %offset, i32 %numIterations) { 109; CHECK-LABEL: @test-add-not-header2 110entry: 111 br label %loop 112loop: 113 %i = phi i32 [ %nexti, %loop2 ], [ 0, %entry ] 114 115; CHECK: %index32 = 116; CHECK: --> {%offset,+,1}<nw> 117 %index32 = add nsw i32 %i, %offset 118 119 %ptr = getelementptr inbounds float, float* %input, i32 %index32 120 %nexti = add nsw i32 %i, 1 121 br label %loop2 122loop2: 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; The call instruction makes it not guaranteed that the add will be 131; executed, since it could run forever or throw an exception, so we 132; cannot assume that the UB is realized. 133define void @test-add-call(float* %input, i32 %offset, i32 %numIterations) { 134; CHECK-LABEL: @test-add-call 135entry: 136 br label %loop 137loop: 138 %i = phi i32 [ %nexti, %loop ], [ 0, %entry ] 139 140; CHECK: %index32 = 141; CHECK: --> {%offset,+,1}<nw> 142 call void @foo() 143 %index32 = add nsw i32 %i, %offset 144 145 %ptr = getelementptr inbounds float, float* %input, i32 %index32 146 %nexti = add nsw i32 %i, 1 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; Same issue as test-add-call, but this time the call is between the 155; producer of poison and the load that consumes it. 156define void @test-add-call2(float* %input, i32 %offset, i32 %numIterations) { 157; CHECK-LABEL: @test-add-call2 158entry: 159 br label %loop 160loop: 161 %i = phi i32 [ %nexti, %loop ], [ 0, %entry ] 162 163; CHECK: %index32 = 164; CHECK: --> {%offset,+,1}<nw> 165 %index32 = add nsw i32 %i, %offset 166 167 %ptr = getelementptr inbounds float, float* %input, i32 %index32 168 %nexti = add nsw i32 %i, 1 169 call void @foo() 170 %f = load float, float* %ptr, align 4 171 %exitcond = icmp eq i32 %nexti, %numIterations 172 br i1 %exitcond, label %exit, label %loop 173exit: 174 ret void 175} 176 177; Without inbounds, GEP does not propagate poison in the very 178; conservative approach used here. 179define void @test-add-no-inbounds(float* %input, i32 %offset, i32 %numIterations) { 180; CHECK-LABEL: @test-add-no-inbounds 181entry: 182 br label %loop 183loop: 184 %i = phi i32 [ %nexti, %loop ], [ 0, %entry ] 185 186; CHECK: %index32 = 187; CHECK: --> {%offset,+,1}<nw> 188 %index32 = add nsw i32 %i, %offset 189 190 %ptr = getelementptr float, float* %input, i32 %index32 191 %nexti = add nsw i32 %i, 1 192 %f = load float, float* %ptr, align 4 193 %exitcond = icmp eq i32 %nexti, %numIterations 194 br i1 %exitcond, label %exit, label %loop 195exit: 196 ret void 197} 198 199; Multiplication by a non-zero constant propagates poison if there is 200; a nuw or nsw flag on the multiplication. 201define void @test-add-mul-propagates(float* %input, i32 %offset, i32 %numIterations) { 202; CHECK-LABEL: @test-add-mul-propagates 203entry: 204 br label %loop 205loop: 206 %i = phi i32 [ %nexti, %loop ], [ 0, %entry ] 207 208; CHECK: %index32 = 209; CHECK: --> {%offset,+,1}<nsw> 210 %index32 = add nsw i32 %i, %offset 211 212 %indexmul = mul nuw i32 %index32, 2 213 %ptr = getelementptr inbounds float, float* %input, i32 %indexmul 214 %nexti = add nsw i32 %i, 1 215 %f = load float, float* %ptr, align 4 216 %exitcond = icmp eq i32 %nexti, %numIterations 217 br i1 %exitcond, label %exit, label %loop 218exit: 219 ret void 220} 221 222; Multiplication by a non-constant should not propagate poison in the 223; very conservative approach used here. 224define void @test-add-mul-no-propagation(float* %input, i32 %offset, i32 %numIterations) { 225; CHECK-LABEL: @test-add-mul-no-propagation 226entry: 227 br label %loop 228loop: 229 %i = phi i32 [ %nexti, %loop ], [ 0, %entry ] 230 231; CHECK: %index32 = 232; CHECK: --> {%offset,+,1}<nw> 233 %index32 = add nsw i32 %i, %offset 234 235 %indexmul = mul nsw i32 %index32, %offset 236 %ptr = getelementptr inbounds float, float* %input, i32 %indexmul 237 %nexti = add nsw i32 %i, 1 238 %f = load float, float* %ptr, align 4 239 %exitcond = icmp eq i32 %nexti, %numIterations 240 br i1 %exitcond, label %exit, label %loop 241exit: 242 ret void 243} 244 245; Multiplication by a non-zero constant does not propagate poison 246; without a no-wrap flag. 247define void @test-add-mul-no-propagation2(float* %input, i32 %offset, i32 %numIterations) { 248; CHECK-LABEL: @test-add-mul-no-propagation2 249entry: 250 br label %loop 251loop: 252 %i = phi i32 [ %nexti, %loop ], [ 0, %entry ] 253 254; CHECK: %index32 = 255; CHECK: --> {%offset,+,1}<nw> 256 %index32 = add nsw i32 %i, %offset 257 258 %indexmul = mul i32 %index32, 2 259 %ptr = getelementptr inbounds float, float* %input, i32 %indexmul 260 %nexti = add nsw i32 %i, 1 261 %f = load float, float* %ptr, align 4 262 %exitcond = icmp eq i32 %nexti, %numIterations 263 br i1 %exitcond, label %exit, label %loop 264exit: 265 ret void 266} 267 268; Division by poison triggers UB. 269define void @test-add-div(float* %input, i32 %offset, i32 %numIterations) { 270; CHECK-LABEL: @test-add-div 271entry: 272 br label %loop 273loop: 274 %i = phi i32 [ %nexti, %loop ], [ 0, %entry ] 275 276; CHECK: %j = 277; CHECK: --> {%offset,+,1}<nsw> 278 %j = add nsw i32 %i, %offset 279 280 %q = sdiv i32 %numIterations, %j 281 %nexti = add nsw i32 %i, 1 282 %exitcond = icmp eq i32 %nexti, %numIterations 283 br i1 %exitcond, label %exit, label %loop 284exit: 285 ret void 286} 287 288; Remainder of poison by non-poison divisor does not trigger UB. 289define void @test-add-div2(float* %input, i32 %offset, i32 %numIterations) { 290; CHECK-LABEL: @test-add-div2 291entry: 292 br label %loop 293loop: 294 %i = phi i32 [ %nexti, %loop ], [ 0, %entry ] 295 296; CHECK: %j = 297; CHECK: --> {%offset,+,1}<nw> 298 %j = add nsw i32 %i, %offset 299 300 %q = sdiv i32 %j, %numIterations 301 %nexti = add nsw i32 %i, 1 302 %exitcond = icmp eq i32 %nexti, %numIterations 303 br i1 %exitcond, label %exit, label %loop 304exit: 305 ret void 306} 307 308; Store to poison address triggers UB. 309define void @test-add-store(float* %input, i32 %offset, i32 %numIterations) { 310; CHECK-LABEL: @test-add-store 311entry: 312 br label %loop 313loop: 314 %i = phi i32 [ %nexti, %loop ], [ 0, %entry ] 315 316; CHECK: %index32 = 317; CHECK: --> {%offset,+,1}<nsw> 318 %index32 = add nsw i32 %i, %offset 319 320 %ptr = getelementptr inbounds float, float* %input, i32 %index32 321 %nexti = add nsw i32 %i, 1 322 store float 1.0, float* %ptr, align 4 323 %exitcond = icmp eq i32 %nexti, %numIterations 324 br i1 %exitcond, label %exit, label %loop 325exit: 326 ret void 327} 328 329; Three sequential adds where the middle add should have nsw. There is 330; a special case for sequential adds and this test covers that. We have to 331; put the final add first in the program since otherwise the special case 332; is not triggered, hence the strange basic block ordering. 333define void @test-add-twice(float* %input, i32 %offset, i32 %numIterations) { 334; CHECK-LABEL: @test-add-twice 335entry: 336 br label %loop 337loop2: 338; CHECK: %seq = 339; CHECK: --> {(2 + %offset),+,1}<nw> 340 %seq = add nsw nuw i32 %index32, 1 341 %exitcond = icmp eq i32 %nexti, %numIterations 342 br i1 %exitcond, label %exit, label %loop 343 344loop: 345 %i = phi i32 [ %nexti, %loop2 ], [ 0, %entry ] 346 347 %j = add nsw i32 %i, 1 348; CHECK: %index32 = 349; CHECK: --> {(1 + %offset),+,1}<nsw> 350 %index32 = add nsw i32 %j, %offset 351 352 %ptr = getelementptr inbounds float, float* %input, i32 %index32 353 %nexti = add nsw i32 %i, 1 354 store float 1.0, float* %ptr, align 4 355 br label %loop2 356exit: 357 ret void 358} 359 360; Example where a mul should get the nsw flag, so that a sext can be 361; distributed over the mul. 362define void @test-mul-nsw(float* %input, i32 %stride, i32 %numIterations) { 363; CHECK-LABEL: @test-mul-nsw 364entry: 365 br label %loop 366loop: 367 %i = phi i32 [ %nexti, %loop ], [ 0, %entry ] 368 369; CHECK: %index32 = 370; CHECK: --> {0,+,%stride}<nsw> 371 %index32 = mul nsw i32 %i, %stride 372 373; CHECK: %index64 = 374; CHECK: --> {0,+,(sext i32 %stride to i64)}<nsw> 375 %index64 = sext i32 %index32 to i64 376 377 %ptr = getelementptr inbounds float, float* %input, i64 %index64 378 %nexti = add nsw i32 %i, 1 379 %f = load float, float* %ptr, align 4 380 %exitcond = icmp eq i32 %nexti, %numIterations 381 br i1 %exitcond, label %exit, label %loop 382exit: 383 ret void 384} 385 386; Example where a mul should get the nuw flag. 387define void @test-mul-nuw(float* %input, i32 %stride, i32 %numIterations) { 388; CHECK-LABEL: @test-mul-nuw 389entry: 390 br label %loop 391loop: 392 %i = phi i32 [ %nexti, %loop ], [ 0, %entry ] 393 394; CHECK: %index32 = 395; CHECK: --> {0,+,%stride}<nuw> 396 %index32 = mul nuw i32 %i, %stride 397 398 %ptr = getelementptr inbounds float, float* %input, i32 %index32 399 %nexti = add nuw i32 %i, 1 400 %f = load float, float* %ptr, align 4 401 %exitcond = icmp eq i32 %nexti, %numIterations 402 br i1 %exitcond, label %exit, label %loop 403 404exit: 405 ret void 406} 407 408; Example where a shl should get the nsw flag, so that a sext can be 409; distributed over the shl. 410define void @test-shl-nsw(float* %input, i32 %start, i32 %numIterations) { 411; CHECK-LABEL: @test-shl-nsw 412entry: 413 br label %loop 414loop: 415 %i = phi i32 [ %nexti, %loop ], [ %start, %entry ] 416 417; CHECK: %index32 = 418; CHECK: --> {(256 * %start),+,256}<nsw> 419 %index32 = shl nsw i32 %i, 8 420 421; CHECK: %index64 = 422; CHECK: --> {(sext i32 (256 * %start) to i64),+,256}<nsw> 423 %index64 = sext i32 %index32 to i64 424 425 %ptr = getelementptr inbounds float, float* %input, i64 %index64 426 %nexti = add nsw i32 %i, 1 427 %f = load float, float* %ptr, align 4 428 %exitcond = icmp eq i32 %nexti, %numIterations 429 br i1 %exitcond, label %exit, label %loop 430exit: 431 ret void 432} 433 434; Example where a shl should get the nuw flag. 435define void @test-shl-nuw(float* %input, i32 %numIterations) { 436; CHECK-LABEL: @test-shl-nuw 437entry: 438 br label %loop 439loop: 440 %i = phi i32 [ %nexti, %loop ], [ 0, %entry ] 441 442; CHECK: %index32 = 443; CHECK: --> {0,+,512}<nuw> 444 %index32 = shl nuw i32 %i, 9 445 446 %ptr = getelementptr inbounds float, float* %input, i32 %index32 447 %nexti = add nuw i32 %i, 1 448 %f = load float, float* %ptr, align 4 449 %exitcond = icmp eq i32 %nexti, %numIterations 450 br i1 %exitcond, label %exit, label %loop 451 452exit: 453 ret void 454} 455 456; Example where a sub should *not* get the nsw flag, because of how 457; scalar evolution represents A - B as A + (-B) and -B can wrap even 458; in cases where A - B does not. 459define void @test-sub-no-nsw(float* %input, i32 %start, i32 %sub, i32 %numIterations) { 460; CHECK-LABEL: @test-sub-no-nsw 461entry: 462 br label %loop 463loop: 464 %i = phi i32 [ %nexti, %loop ], [ %start, %entry ] 465 466; CHECK: %index32 = 467; CHECK: --> {((-1 * %sub) + %start),+,1}<nw> 468 %index32 = sub nsw i32 %i, %sub 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 sub should get the nsw flag as the RHS cannot be the 481; minimal signed value. 482define void @test-sub-nsw(float* %input, i32 %start, i32 %sub, i32 %numIterations) { 483; CHECK-LABEL: @test-sub-nsw 484entry: 485 %halfsub = ashr i32 %sub, 1 486 br label %loop 487loop: 488 %i = phi i32 [ %nexti, %loop ], [ %start, %entry ] 489 490; CHECK: %index32 = 491; CHECK: --> {((-1 * %halfsub)<nsw> + %start),+,1}<nsw> 492 %index32 = sub nsw i32 %i, %halfsub 493 %index64 = sext i32 %index32 to i64 494 495 %ptr = getelementptr inbounds float, float* %input, i64 %index64 496 %nexti = add nsw i32 %i, 1 497 %f = load float, float* %ptr, align 4 498 %exitcond = icmp eq i32 %nexti, %numIterations 499 br i1 %exitcond, label %exit, label %loop 500exit: 501 ret void 502} 503 504; Example where a sub should get the nsw flag, since the LHS is non-negative, 505; which implies that the RHS cannot be the minimal signed value. 506define void @test-sub-nsw-lhs-non-negative(float* %input, i32 %sub, i32 %numIterations) { 507; CHECK-LABEL: @test-sub-nsw-lhs-non-negative 508entry: 509 br label %loop 510loop: 511 %i = phi i32 [ %nexti, %loop ], [ 0, %entry ] 512 513; CHECK: %index32 = 514; CHECK: --> {(-1 * %sub),+,1}<nsw> 515 %index32 = sub nsw i32 %i, %sub 516 517; CHECK: %index64 = 518; CHECK: --> {(sext i32 (-1 * %sub) to i64),+,1}<nsw> 519 %index64 = sext i32 %index32 to i64 520 521 %ptr = getelementptr inbounds float, float* %input, i64 %index64 522 %nexti = add nsw i32 %i, 1 523 %f = load float, float* %ptr, align 4 524 %exitcond = icmp eq i32 %nexti, %numIterations 525 br i1 %exitcond, label %exit, label %loop 526exit: 527 ret void 528} 529 530; Two adds with a sub in the middle and the sub should have nsw. There is 531; a special case for sequential adds/subs and this test covers that. We have to 532; put the final add first in the program since otherwise the special case 533; is not triggered, hence the strange basic block ordering. 534define void @test-sub-with-add(float* %input, i32 %offset, i32 %numIterations) { 535; CHECK-LABEL: @test-sub-with-add 536entry: 537 br label %loop 538loop2: 539; CHECK: %seq = 540; CHECK: --> {(2 + (-1 * %offset)),+,1}<nw> 541 %seq = add nsw nuw i32 %index32, 1 542 %exitcond = icmp eq i32 %nexti, %numIterations 543 br i1 %exitcond, label %exit, label %loop 544 545loop: 546 %i = phi i32 [ %nexti, %loop2 ], [ 0, %entry ] 547 548 %j = add nsw i32 %i, 1 549; CHECK: %index32 = 550; CHECK: --> {(1 + (-1 * %offset)),+,1}<nsw> 551 %index32 = sub nsw i32 %j, %offset 552 553 %ptr = getelementptr inbounds float, float* %input, i32 %index32 554 %nexti = add nsw i32 %i, 1 555 store float 1.0, float* %ptr, align 4 556 br label %loop2 557exit: 558 ret void 559} 560 561 562; Subtraction of two recurrences. The addition in the SCEV that this 563; maps to is NSW, but the negation of the RHS does not since that 564; recurrence could be the most negative representable value. 565define void @subrecurrences(i32 %outer_l, i32 %inner_l, i32 %val) { 566; CHECK-LABEL: @subrecurrences 567 entry: 568 br label %outer 569 570outer: 571 %o_idx = phi i32 [ 0, %entry ], [ %o_idx.inc, %outer.be ] 572 %o_idx.inc = add nsw i32 %o_idx, 1 573 %cond = icmp eq i32 %o_idx, %val 574 br i1 %cond, label %inner, label %outer.be 575 576inner: 577 %i_idx = phi i32 [ 0, %outer ], [ %i_idx.inc, %inner ] 578 %i_idx.inc = add nsw i32 %i_idx, 1 579; CHECK: %v = 580; CHECK-NEXT: --> {{[{][{]}}-1,+,-1}<nw><%outer>,+,1}<nsw><%inner> 581 %v = sub nsw i32 %i_idx, %o_idx.inc 582 %forub = udiv i32 1, %v 583 %cond2 = icmp eq i32 %i_idx, %inner_l 584 br i1 %cond2, label %outer.be, label %inner 585 586outer.be: 587 %cond3 = icmp eq i32 %o_idx, %outer_l 588 br i1 %cond3, label %exit, label %outer 589 590exit: 591 ret void 592} 593