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 7 define 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. 13 define void @test-add-nsw(float* %input, i32 %offset, i32 %numIterations) { 14 ; CHECK-LABEL: @test-add-nsw 15 entry: 16 br label %loop 17 loop: 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 34 exit: 35 ret void 36 } 37 38 ; Example where an add should get the nuw flag. 39 define void @test-add-nuw(float* %input, i32 %offset, i32 %numIterations) { 40 ; CHECK-LABEL: @test-add-nuw 41 entry: 42 br label %loop 43 loop: 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 56 exit: 57 ret void 58 } 59 60 ; With no load to trigger UB from poison, we cannot infer nsw. 61 define void @test-add-no-load(float* %input, i32 %offset, i32 %numIterations) { 62 ; CHECK-LABEL: @test-add-no-load 63 entry: 64 br label %loop 65 loop: 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 77 exit: 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. 84 define void @test-add-not-header(float* %input, i32 %offset, i32 %numIterations) { 85 ; CHECK-LABEL: @test-add-not-header 86 entry: 87 br label %loop 88 loop: 89 %i = phi i32 [ %nexti, %loop2 ], [ 0, %entry ] 90 br label %loop2 91 loop2: 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 102 exit: 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. 108 define void @test-add-not-header2(float* %input, i32 %offset, i32 %numIterations) { 109 ; CHECK-LABEL: @test-add-not-header2 110 entry: 111 br label %loop 112 loop: 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 122 loop2: 123 %f = load float, float* %ptr, align 4 124 %exitcond = icmp eq i32 %nexti, %numIterations 125 br i1 %exitcond, label %exit, label %loop 126 exit: 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. 133 define void @test-add-call(float* %input, i32 %offset, i32 %numIterations) { 134 ; CHECK-LABEL: @test-add-call 135 entry: 136 br label %loop 137 loop: 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 150 exit: 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. 156 define void @test-add-call2(float* %input, i32 %offset, i32 %numIterations) { 157 ; CHECK-LABEL: @test-add-call2 158 entry: 159 br label %loop 160 loop: 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 173 exit: 174 ret void 175 } 176 177 ; Without inbounds, GEP does not propagate poison in the very 178 ; conservative approach used here. 179 define void @test-add-no-inbounds(float* %input, i32 %offset, i32 %numIterations) { 180 ; CHECK-LABEL: @test-add-no-inbounds 181 entry: 182 br label %loop 183 loop: 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 195 exit: 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. 201 define void @test-add-mul-propagates(float* %input, i32 %offset, i32 %numIterations) { 202 ; CHECK-LABEL: @test-add-mul-propagates 203 entry: 204 br label %loop 205 loop: 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 218 exit: 219 ret void 220 } 221 222 ; Multiplication by a non-constant should not propagate poison in the 223 ; very conservative approach used here. 224 define void @test-add-mul-no-propagation(float* %input, i32 %offset, i32 %numIterations) { 225 ; CHECK-LABEL: @test-add-mul-no-propagation 226 entry: 227 br label %loop 228 loop: 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 241 exit: 242 ret void 243 } 244 245 ; Multiplication by a non-zero constant does not propagate poison 246 ; without a no-wrap flag. 247 define void @test-add-mul-no-propagation2(float* %input, i32 %offset, i32 %numIterations) { 248 ; CHECK-LABEL: @test-add-mul-no-propagation2 249 entry: 250 br label %loop 251 loop: 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 264 exit: 265 ret void 266 } 267 268 ; Division by poison triggers UB. 269 define void @test-add-div(float* %input, i32 %offset, i32 %numIterations) { 270 ; CHECK-LABEL: @test-add-div 271 entry: 272 br label %loop 273 loop: 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 284 exit: 285 ret void 286 } 287 288 ; Remainder of poison by non-poison divisor does not trigger UB. 289 define void @test-add-div2(float* %input, i32 %offset, i32 %numIterations) { 290 ; CHECK-LABEL: @test-add-div2 291 entry: 292 br label %loop 293 loop: 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 304 exit: 305 ret void 306 } 307 308 ; Store to poison address triggers UB. 309 define void @test-add-store(float* %input, i32 %offset, i32 %numIterations) { 310 ; CHECK-LABEL: @test-add-store 311 entry: 312 br label %loop 313 loop: 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 325 exit: 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. 333 define void @test-add-twice(float* %input, i32 %offset, i32 %numIterations) { 334 ; CHECK-LABEL: @test-add-twice 335 entry: 336 br label %loop 337 loop2: 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 344 loop: 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 356 exit: 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. 362 define void @test-mul-nsw(float* %input, i32 %stride, i32 %numIterations) { 363 ; CHECK-LABEL: @test-mul-nsw 364 entry: 365 br label %loop 366 loop: 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 382 exit: 383 ret void 384 } 385 386 ; Example where a mul should get the nuw flag. 387 define void @test-mul-nuw(float* %input, i32 %stride, i32 %numIterations) { 388 ; CHECK-LABEL: @test-mul-nuw 389 entry: 390 br label %loop 391 loop: 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 404 exit: 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. 410 define void @test-shl-nsw(float* %input, i32 %start, i32 %numIterations) { 411 ; CHECK-LABEL: @test-shl-nsw 412 entry: 413 br label %loop 414 loop: 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 430 exit: 431 ret void 432 } 433 434 ; Example where a shl should get the nuw flag. 435 define void @test-shl-nuw(float* %input, i32 %numIterations) { 436 ; CHECK-LABEL: @test-shl-nuw 437 entry: 438 br label %loop 439 loop: 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 452 exit: 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. 459 define void @test-sub-no-nsw(float* %input, i32 %start, i32 %sub, i32 %numIterations) { 460 ; CHECK-LABEL: @test-sub-no-nsw 461 entry: 462 br label %loop 463 loop: 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 476 exit: 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. 482 define void @test-sub-nsw(float* %input, i32 %start, i32 %sub, i32 %numIterations) { 483 ; CHECK-LABEL: @test-sub-nsw 484 entry: 485 %halfsub = ashr i32 %sub, 1 486 br label %loop 487 loop: 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 500 exit: 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. 506 define void @test-sub-nsw-lhs-non-negative(float* %input, i32 %sub, i32 %numIterations) { 507 ; CHECK-LABEL: @test-sub-nsw-lhs-non-negative 508 entry: 509 br label %loop 510 loop: 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 526 exit: 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. 534 define void @test-sub-with-add(float* %input, i32 %offset, i32 %numIterations) { 535 ; CHECK-LABEL: @test-sub-with-add 536 entry: 537 br label %loop 538 loop2: 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 545 loop: 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 557 exit: 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. 565 define void @subrecurrences(i32 %outer_l, i32 %inner_l, i32 %val) { 566 ; CHECK-LABEL: @subrecurrences 567 entry: 568 br label %outer 569 570 outer: 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 576 inner: 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 586 outer.be: 587 %cond3 = icmp eq i32 %o_idx, %outer_l 588 br i1 %cond3, label %exit, label %outer 589 590 exit: 591 ret void 592 } 593
