test/Analysis/ScalarEvolution/flags-from-poison.ll

   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 define void @test-add-nuw-from-icmp(float* %input, i32 %offset,
  61                                     i32 %numIterations) {
  62 ; CHECK-LABEL: @test-add-nuw-from-icmp
  63 entry:
  64   br label %loop
  65 loop:
  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
  80 exit:
  81   ret void
  82 }
  83
  84 ; With no load to trigger UB from poison, we cannot infer nsw.
  85 define void @test-add-no-load(float* %input, i32 %offset, i32 %numIterations) {
  86 ; CHECK-LABEL: @test-add-no-load
  87 entry:
  88   br label %loop
  89 loop:
  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
 101 exit:
 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.
 108 define void @test-add-not-header(float* %input, i32 %offset, i32 %numIterations) {
 109 ; CHECK-LABEL: @test-add-not-header
 110 entry:
 111   br label %loop
 112 loop:
 113   %i = phi i32 [ %nexti, %loop2 ], [ 0, %entry ]
 114   br label %loop2
 115 loop2:
 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
 126 exit:
 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.
 132 define void @test-add-not-header2(float* %input, i32 %offset, i32 %numIterations) {
 133 ; CHECK-LABEL: @test-add-not-header2
 134 entry:
 135   br label %loop
 136 loop:
 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
 146 loop2:
 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 ; Similar to test-add-not-header, but in this case the load
 155 ; instruction may not be executed.
 156 define void @test-add-not-header3(float* %input, i32 %offset, i32 %numIterations,
 157                                  i1* %cond_buf) {
 158 ; CHECK-LABEL: @test-add-not-header3
 159 entry:
 160   br label %loop
 161 loop:
 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
 172 loop2:
 173   %f = load float, float* %ptr, align 4
 174   %exitcond = icmp eq i32 %nexti, %numIterations
 175   br i1 %exitcond, label %exit, label %loop
 176 exit:
 177   ret void
 178 }
 179
 180 ; Same thing as test-add-not-header2, except we have a few extra
 181 ; blocks.
 182 define void @test-add-not-header4(float* %input, i32 %offset, i32 %numIterations) {
 183 ; CHECK-LABEL: @test-add-not-header4
 184 entry:
 185   br label %loop
 186 loop:
 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
 196 loop3:
 197   br label %loop4
 198 loop4:
 199   br label %loop2
 200 loop2:
 201   %f = load float, float* %ptr, align 4
 202   %exitcond = icmp eq i32 %nexti, %numIterations
 203   br i1 %exitcond, label %exit, label %loop
 204 exit:
 205   ret void
 206 }
 207
 208 ; Demonstrate why we need a Visited set in llvm::programUndefinedIfFullPoison.
 209 define void @test-add-not-header5(float* %input, i32 %offset) {
 210 ; CHECK-LABEL: @test-add-not-header5
 211 entry:
 212   br label %loop
 213 loop:
 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
 224 exit:
 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.
 231 define void @test-add-call(float* %input, i32 %offset, i32 %numIterations) {
 232 ; CHECK-LABEL: @test-add-call
 233 entry:
 234   br label %loop
 235 loop:
 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
 248 exit:
 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.
 254 define void @test-add-call2(float* %input, i32 %offset, i32 %numIterations) {
 255 ; CHECK-LABEL: @test-add-call2
 256 entry:
 257   br label %loop
 258 loop:
 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
 271 exit:
 272   ret void
 273 }
 274
 275 ; Any poison input makes getelementptr produce poison
 276 define void @test-gep-propagates-poison(float* %input, i32 %offset, i32 %numIterations) {
 277 ; CHECK-LABEL: @test-gep-propagates-poison
 278 entry:
 279   br label %loop
 280 loop:
 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
 292 exit:
 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.
 298 define void @test-add-mul-propagates(float* %input, i32 %offset, i32 %numIterations) {
 299 ; CHECK-LABEL: @test-add-mul-propagates
 300 entry:
 301   br label %loop
 302 loop:
 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
 315 exit:
 316   ret void
 317 }
 318
 319 ; Any poison input to multiplication propages poison.
 320 define void @test-mul-propagates-poison(float* %input, i32 %offset, i32 %numIterations) {
 321 ; CHECK-LABEL: @test-mul-propagates-poison
 322 entry:
 323   br label %loop
 324 loop:
 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
 337 exit:
 338   ret void
 339 }
 340
 341 define void @test-mul-propagates-poison-2(float* %input, i32 %offset, i32 %numIterations) {
 342 ; CHECK-LABEL: @test-mul-propagates-poison-2
 343 entry:
 344   br label %loop
 345 loop:
 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
 358 exit:
 359   ret void
 360 }
 361
 362 ; Division by poison triggers UB.
 363 define void @test-add-div(float* %input, i32 %offset, i32 %numIterations) {
 364 ; CHECK-LABEL: @test-add-div
 365 entry:
 366   br label %loop
 367 loop:
 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
 378 exit:
 379   ret void
 380 }
 381
 382 ; Remainder of poison by non-poison divisor does not trigger UB.
 383 define void @test-add-div2(float* %input, i32 %offset, i32 %numIterations) {
 384 ; CHECK-LABEL: @test-add-div2
 385 entry:
 386   br label %loop
 387 loop:
 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
 398 exit:
 399   ret void
 400 }
 401
 402 ; Store to poison address triggers UB.
 403 define void @test-add-store(float* %input, i32 %offset, i32 %numIterations) {
 404 ; CHECK-LABEL: @test-add-store
 405 entry:
 406   br label %loop
 407 loop:
 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
 419 exit:
 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.
 427 define void @test-add-twice(float* %input, i32 %offset, i32 %numIterations) {
 428 ; CHECK-LABEL: @test-add-twice
 429 entry:
 430   br label %loop
 431 loop2:
 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
 438 loop:
 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
 450 exit:
 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.
 456 define void @test-mul-nsw(float* %input, i32 %stride, i32 %numIterations) {
 457 ; CHECK-LABEL: @test-mul-nsw
 458 entry:
 459   br label %loop
 460 loop:
 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
 476 exit:
 477   ret void
 478 }
 479
 480 ; Example where a mul should get the nuw flag.
 481 define void @test-mul-nuw(float* %input, i32 %stride, i32 %numIterations) {
 482 ; CHECK-LABEL: @test-mul-nuw
 483 entry:
 484   br label %loop
 485 loop:
 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
 498 exit:
 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.
 504 define void @test-shl-nsw(float* %input, i32 %start, i32 %numIterations) {
 505 ; CHECK-LABEL: @test-shl-nsw
 506 entry:
 507   br label %loop
 508 loop:
 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
 524 exit:
 525   ret void
 526 }
 527
 528 ; Example where a shl should get the nuw flag.
 529 define void @test-shl-nuw(float* %input, i32 %numIterations) {
 530 ; CHECK-LABEL: @test-shl-nuw
 531 entry:
 532   br label %loop
 533 loop:
 534   %i = phi i32 [ %nexti, %loop ], [ 0, %entry ]
 535
 536 ; CHECK: %index32 =
 537 ; CHECK: --> {0,+,512}<nuw>
 538   %index32 = shl nuw i32 %i, 9
 539
 540   %ptr = getelementptr inbounds float, float* %input, i32 %index32
 541   %nexti = add nuw i32 %i, 1
 542   %f = load float, float* %ptr, align 4
 543   %exitcond = icmp eq i32 %nexti, %numIterations
 544   br i1 %exitcond, label %exit, label %loop
 545
 546 exit:
 547   ret void
 548 }
 549
 550 ; Example where a sub should *not* get the nsw flag, because of how
 551 ; scalar evolution represents A - B as A + (-B) and -B can wrap even
 552 ; in cases where A - B does not.
 553 define void @test-sub-no-nsw(float* %input, i32 %start, i32 %sub, i32 %numIterations) {
 554 ; CHECK-LABEL: @test-sub-no-nsw
 555 entry:
 556   br label %loop
 557 loop:
 558   %i = phi i32 [ %nexti, %loop ], [ %start, %entry ]
 559
 560 ; CHECK: %index32 =
 561 ; CHECK: --> {((-1 * %sub) + %start),+,1}<nw>
 562   %index32 = sub nsw i32 %i, %sub
 563   %index64 = sext i32 %index32 to i64
 564
 565   %ptr = getelementptr inbounds float, float* %input, i64 %index64
 566   %nexti = add nsw i32 %i, 1
 567   %f = load float, float* %ptr, align 4
 568   %exitcond = icmp eq i32 %nexti, %numIterations
 569   br i1 %exitcond, label %exit, label %loop
 570 exit:
 571   ret void
 572 }
 573
 574 ; Example where a sub should get the nsw flag as the RHS cannot be the
 575 ; minimal signed value.
 576 define void @test-sub-nsw(float* %input, i32 %start, i32 %sub, i32 %numIterations) {
 577 ; CHECK-LABEL: @test-sub-nsw
 578 entry:
 579   %halfsub = ashr i32 %sub, 1
 580   br label %loop
 581 loop:
 582   %i = phi i32 [ %nexti, %loop ], [ %start, %entry ]
 583
 584 ; CHECK: %index32 =
 585 ; CHECK: --> {((-1 * %halfsub)<nsw> + %start)<nsw>,+,1}<nsw>
 586   %index32 = sub nsw i32 %i, %halfsub
 587   %index64 = sext i32 %index32 to i64
 588
 589   %ptr = getelementptr inbounds float, float* %input, i64 %index64
 590   %nexti = add nsw i32 %i, 1
 591   %f = load float, float* %ptr, align 4
 592   %exitcond = icmp eq i32 %nexti, %numIterations
 593   br i1 %exitcond, label %exit, label %loop
 594 exit:
 595   ret void
 596 }
 597
 598 ; Example where a sub should get the nsw flag, since the LHS is non-negative,
 599 ; which implies that the RHS cannot be the minimal signed value.
 600 define void @test-sub-nsw-lhs-non-negative(float* %input, i32 %sub, i32 %numIterations) {
 601 ; CHECK-LABEL: @test-sub-nsw-lhs-non-negative
 602 entry:
 603   br label %loop
 604 loop:
 605   %i = phi i32 [ %nexti, %loop ], [ 0, %entry ]
 606
 607 ; CHECK: %index32 =
 608 ; CHECK: --> {(-1 * %sub),+,1}<nsw>
 609   %index32 = sub nsw i32 %i, %sub
 610
 611 ; CHECK: %index64 =
 612 ; CHECK: --> {(-1 * (sext i32 %sub to i64))<nsw>,+,1}<nsw
 613   %index64 = sext i32 %index32 to i64
 614
 615   %ptr = getelementptr inbounds float, float* %input, i64 %index64
 616   %nexti = add nsw i32 %i, 1
 617   %f = load float, float* %ptr, align 4
 618   %exitcond = icmp eq i32 %nexti, %numIterations
 619   br i1 %exitcond, label %exit, label %loop
 620 exit:
 621   ret void
 622 }
 623
 624 ; Example checking that a sext is pushed onto a sub's operands if the sub is an
 625 ; overflow intrinsic.
 626 define void @test-sext-sub(float* %input, i32 %sub, i32 %numIterations) {
 627 ; CHECK-LABEL: @test-sext-sub
 628 entry:
 629   br label %loop
 630 loop:
 631   %i = phi i32 [ %nexti, %cont ], [ 0, %entry ]
 632
 633 ; CHECK: %val = extractvalue { i32, i1 } %ssub, 0
 634 ; CHECK: --> {(-1 * %sub),+,1}<nw>
 635   %ssub = tail call { i32, i1 } @llvm.ssub.with.overflow.i32(i32 %i, i32 %sub)
 636   %val = extractvalue { i32, i1 } %ssub, 0
 637   %ovfl = extractvalue { i32, i1 } %ssub, 1
 638   br i1 %ovfl, label %trap, label %cont
 639
 640 trap:
 641   tail call void @llvm.trap()
 642   unreachable
 643
 644 cont:
 645 ; CHECK: %index64 =
 646 ; CHECK: --> {(-1 * (sext i32 %sub to i64))<nsw>,+,1}<nsw
 647   %index64 = sext i32 %val to i64
 648
 649   %ptr = getelementptr inbounds float, float* %input, i64 %index64
 650   %nexti = add nsw i32 %i, 1
 651   %f = load float, float* %ptr, align 4
 652   %exitcond = icmp eq i32 %nexti, %numIterations
 653   br i1 %exitcond, label %exit, label %loop
 654 exit:
 655   ret void
 656 }
 657
 658 ; Two adds with a sub in the middle and the sub should have nsw. There is
 659 ; a special case for sequential adds/subs and this test covers that. We have to
 660 ; put the final add first in the program since otherwise the special case
 661 ; is not triggered, hence the strange basic block ordering.
 662 define void @test-sub-with-add(float* %input, i32 %offset, i32 %numIterations) {
 663 ; CHECK-LABEL: @test-sub-with-add
 664 entry:
 665   br label %loop
 666 loop2:
 667 ; CHECK: %seq =
 668 ; CHECK: --> {(2 + (-1 * %offset)),+,1}<nw>
 669   %seq = add nsw nuw i32 %index32, 1
 670   %exitcond = icmp eq i32 %nexti, %numIterations
 671   br i1 %exitcond, label %exit, label %loop
 672
 673 loop:
 674   %i = phi i32 [ %nexti, %loop2 ], [ 0, %entry ]
 675
 676   %j = add nsw i32 %i, 1
 677 ; CHECK: %index32 =
 678 ; CHECK: --> {(1 + (-1 * %offset))<nsw>,+,1}<nsw>
 679   %index32 = sub nsw i32 %j, %offset
 680
 681   %ptr = getelementptr inbounds float, float* %input, i32 %index32
 682   %nexti = add nsw i32 %i, 1
 683   store float 1.0, float* %ptr, align 4
 684   br label %loop2
 685 exit:
 686   ret void
 687 }
 688
 689
 690 ; Subtraction of two recurrences. The addition in the SCEV that this
 691 ; maps to is NSW, but the negation of the RHS does not since that
 692 ; recurrence could be the most negative representable value.
 693 define void @subrecurrences(i32 %outer_l, i32 %inner_l, i32 %val) {
 694 ; CHECK-LABEL: @subrecurrences
 695  entry:
 696   br label %outer
 697
 698 outer:
 699   %o_idx = phi i32 [ 0, %entry ], [ %o_idx.inc, %outer.be ]
 700   %o_idx.inc = add nsw i32 %o_idx, 1
 701   %cond = icmp eq i32 %o_idx, %val
 702   br i1 %cond, label %inner, label %outer.be
 703
 704 inner:
 705   %i_idx = phi i32 [ 0, %outer ], [ %i_idx.inc, %inner ]
 706   %i_idx.inc = add nsw i32 %i_idx, 1
 707 ; CHECK: %v =
 708 ; CHECK-NEXT: --> {{[{][{]}}-1,+,-1}<nw><%outer>,+,1}<nsw><%inner>
 709   %v = sub nsw i32 %i_idx, %o_idx.inc
 710   %forub = udiv i32 1, %v
 711   %cond2 = icmp eq i32 %i_idx, %inner_l
 712   br i1 %cond2, label %outer.be, label %inner
 713
 714 outer.be:
 715   %cond3 = icmp eq i32 %o_idx, %outer_l
 716   br i1 %cond3, label %exit, label %outer
 717
 718 exit:
 719   ret void
 720 }
 721
 722
 723 ; PR28932: Don't assert on non-SCEV-able value %2.
 724 %struct.anon = type { i8* }
 725 @a = common global %struct.anon* null, align 8
 726 @b = common global i32 0, align 4
 727 declare { i32, i1 } @llvm.ssub.with.overflow.i32(i32, i32)
 728 declare void @llvm.trap()
 729 define i32 @pr28932() {
 730 entry:
 731   %.pre = load %struct.anon*, %struct.anon** @a, align 8
 732   %.pre7 = load i32, i32* @b, align 4
 733   br label %for.cond
 734
 735 for.cond:                                         ; preds = %cont6, %entry
 736   %0 = phi i32 [ %3, %cont6 ], [ %.pre7, %entry ]
 737   %1 = phi %struct.anon* [ %.ph, %cont6 ], [ %.pre, %entry ]
 738   %tobool = icmp eq %struct.anon* %1, null
 739   %2 = tail call { i32, i1 } @llvm.ssub.with.overflow.i32(i32 %0, i32 1)
 740   %3 = extractvalue { i32, i1 } %2, 0
 741   %4 = extractvalue { i32, i1 } %2, 1
 742   %idxprom = sext i32 %3 to i64
 743   %5 = getelementptr inbounds %struct.anon, %struct.anon* %1, i64 0, i32 0
 744   %6 = load i8*, i8** %5, align 8
 745   %7 = getelementptr inbounds i8, i8* %6, i64 %idxprom
 746   %8 = load i8, i8* %7, align 1
 747   br i1 %tobool, label %if.else, label %if.then
 748
 749 if.then:                                          ; preds = %for.cond
 750   br i1 %4, label %trap, label %cont6
 751
 752 trap:                                             ; preds = %if.else, %if.then
 753   tail call void @llvm.trap()
 754   unreachable
 755
 756 if.else:                                          ; preds = %for.cond
 757   br i1 %4, label %trap, label %cont1
 758
 759 cont1:                                            ; preds = %if.else
 760   %conv5 = sext i8 %8 to i64
 761   %9 = inttoptr i64 %conv5 to %struct.anon*
 762   store %struct.anon* %9, %struct.anon** @a, align 8
 763   br label %cont6
 764
 765 cont6:                                            ; preds = %cont1, %if.then
 766   %.ph = phi %struct.anon* [ %9, %cont1 ], [ %1, %if.then ]
 767   store i32 %3, i32* @b, align 4
 768   br label %for.cond
 769 }