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

   1 ; NOTE: Assertions have been autogenerated by utils/update_analyze_test_checks.py
   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
   8 define void @foo() {
   9 ; CHECK-LABEL: 'foo'
  10 ; CHECK-NEXT:  Classifying expressions for: @foo
  11 ; CHECK-NEXT:  Determining loop execution counts for: @foo
  12 ;
  13   ret void
  14 }
  15
  16 ; Example where an add should get the nsw flag, so that a sext can be
  17 ; distributed over the add.
  18 define void @test-add-nsw(ptr %input, i32 %offset, i32 %numIterations) {
  19 ; CHECK-LABEL: 'test-add-nsw'
  20 ; CHECK-NEXT:  Classifying expressions for: @test-add-nsw
  21 ; CHECK-NEXT:    %i = phi i32 [ %nexti, %loop ], [ 0, %entry ]
  22 ; CHECK-NEXT:    --> {0,+,1}<nuw><nsw><%loop> U: [0,-2147483648) S: [0,-2147483648) Exits: (-1 + %numIterations) LoopDispositions: { %loop: Computable }
  23 ; CHECK-NEXT:    %index32 = add nsw i32 %i, %offset
  24 ; CHECK-NEXT:    --> {%offset,+,1}<nsw><%loop> U: full-set S: full-set Exits: (-1 + %offset + %numIterations) LoopDispositions: { %loop: Computable }
  25 ; CHECK-NEXT:    %index64 = sext i32 %index32 to i64
  26 ; CHECK-NEXT:    --> {(sext i32 %offset to i64),+,1}<nsw><%loop> U: [-2147483648,6442450943) S: [-2147483648,6442450943) Exits: ((zext i32 (-1 + %numIterations) to i64) + (sext i32 %offset to i64)) LoopDispositions: { %loop: Computable }
  27 ; CHECK-NEXT:    %ptr = getelementptr inbounds float, ptr %input, i64 %index64
  28 ; CHECK-NEXT:    --> {((4 * (sext i32 %offset to i64))<nsw> + %input),+,4}<nw><%loop> U: full-set S: full-set Exits: ((4 * (zext i32 (-1 + %numIterations) to i64))<nuw><nsw> + (4 * (sext i32 %offset to i64))<nsw> + %input) LoopDispositions: { %loop: Computable }
  29 ; CHECK-NEXT:    %nexti = add nsw i32 %i, 1
  30 ; CHECK-NEXT:    --> {1,+,1}<nuw><%loop> U: [1,0) S: [1,0) Exits: %numIterations LoopDispositions: { %loop: Computable }
  31 ; CHECK-NEXT:  Determining loop execution counts for: @test-add-nsw
  32 ; CHECK-NEXT:  Loop %loop: backedge-taken count is (-1 + %numIterations)
  33 ; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is i32 -1
  34 ; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is (-1 + %numIterations)
  35 ; CHECK-NEXT:  Loop %loop: Trip multiple is 1
  36 ;
  37 entry:
  38   br label %loop
  39 loop:
  40   %i = phi i32 [ %nexti, %loop ], [ 0, %entry ]
  41
  42   %index32 = add nsw i32 %i, %offset
  43
  44   %index64 = sext i32 %index32 to i64
  45
  46   %ptr = getelementptr inbounds float, ptr %input, i64 %index64
  47   %nexti = add nsw i32 %i, 1
  48   %f = load float, ptr %ptr, align 4
  49   call void @foo()
  50   %exitcond = icmp eq i32 %nexti, %numIterations
  51   br i1 %exitcond, label %exit, label %loop
  52 exit:
  53   ret void
  54 }
  55
  56 ; Example where an add should get the nuw flag.
  57 define void @test-add-nuw(ptr %input, i32 %offset, i32 %numIterations) {
  58 ; CHECK-LABEL: 'test-add-nuw'
  59 ; CHECK-NEXT:  Classifying expressions for: @test-add-nuw
  60 ; CHECK-NEXT:    %i = phi i32 [ %nexti, %loop ], [ 0, %entry ]
  61 ; CHECK-NEXT:    --> {0,+,1}<nuw><%loop> U: full-set S: full-set Exits: (-1 + %numIterations) LoopDispositions: { %loop: Computable }
  62 ; CHECK-NEXT:    %index32 = add nuw i32 %i, %offset
  63 ; CHECK-NEXT:    --> {%offset,+,1}<nuw><%loop> U: full-set S: full-set Exits: (-1 + %offset + %numIterations) LoopDispositions: { %loop: Computable }
  64 ; CHECK-NEXT:    %ptr = getelementptr inbounds float, ptr %input, i32 %index32
  65 ; CHECK-NEXT:    --> ((4 * (sext i32 {%offset,+,1}<nuw><%loop> to i64))<nsw> + %input) U: full-set S: full-set Exits: ((4 * (sext i32 (-1 + %offset + %numIterations) to i64))<nsw> + %input) LoopDispositions: { %loop: Computable }
  66 ; CHECK-NEXT:    %nexti = add nuw i32 %i, 1
  67 ; CHECK-NEXT:    --> {1,+,1}<nuw><%loop> U: [1,0) S: [1,0) Exits: %numIterations LoopDispositions: { %loop: Computable }
  68 ; CHECK-NEXT:  Determining loop execution counts for: @test-add-nuw
  69 ; CHECK-NEXT:  Loop %loop: backedge-taken count is (-1 + %numIterations)
  70 ; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is i32 -1
  71 ; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is (-1 + %numIterations)
  72 ; CHECK-NEXT:  Loop %loop: Trip multiple is 1
  73 ;
  74 entry:
  75   br label %loop
  76 loop:
  77   %i = phi i32 [ %nexti, %loop ], [ 0, %entry ]
  78
  79   %index32 = add nuw i32 %i, %offset
  80
  81   %ptr = getelementptr inbounds float, ptr %input, i32 %index32
  82   %nexti = add nuw i32 %i, 1
  83   %f = load float, ptr %ptr, align 4
  84   %exitcond = icmp eq i32 %nexti, %numIterations
  85   br i1 %exitcond, label %exit, label %loop
  86
  87 exit:
  88   ret void
  89 }
  90
  91 ; Case where we're checking to see if add flags are valid in defining scope
  92 ; and all operands (other than addrec) are invariant
  93 define void @test-add-scope-invariant(ptr %input, i32 %needle) {
  94 ; CHECK-LABEL: 'test-add-scope-invariant'
  95 ; CHECK-NEXT:  Classifying expressions for: @test-add-scope-invariant
  96 ; CHECK-NEXT:    %offset = load i32, ptr %input, align 4
  97 ; CHECK-NEXT:    --> %offset U: full-set S: full-set
  98 ; CHECK-NEXT:    %i = phi i32 [ %i.next, %loop ], [ 0, %entry ]
  99 ; CHECK-NEXT:    --> {0,+,1}<nuw><%loop> U: full-set S: full-set Exits: (-1 + (-1 * %offset) + %needle) LoopDispositions: { %loop: Computable }
 100 ; CHECK-NEXT:    %i.next = add nuw i32 %i, 1
 101 ; CHECK-NEXT:    --> {1,+,1}<nuw><%loop> U: [1,0) S: [1,0) Exits: ((-1 * %offset) + %needle) LoopDispositions: { %loop: Computable }
 102 ; CHECK-NEXT:    %of_interest = add nuw nsw i32 %i.next, %offset
 103 ; CHECK-NEXT:    --> {(1 + %offset)<nuw><nsw>,+,1}<nuw><%loop> U: [1,0) S: [1,0) Exits: %needle LoopDispositions: { %loop: Computable }
 104 ; CHECK-NEXT:    %gep2 = getelementptr i32, ptr %input, i32 %of_interest
 105 ; CHECK-NEXT:    --> ((4 * (sext i32 {(1 + %offset)<nuw><nsw>,+,1}<nuw><%loop> to i64))<nsw> + %input) U: full-set S: full-set Exits: ((4 * (sext i32 %needle to i64))<nsw> + %input) LoopDispositions: { %loop: Computable }
 106 ; CHECK-NEXT:  Determining loop execution counts for: @test-add-scope-invariant
 107 ; CHECK-NEXT:  Loop %loop: backedge-taken count is (-1 + (-1 * %offset) + %needle)
 108 ; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is i32 -1
 109 ; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is (-1 + (-1 * %offset) + %needle)
 110 ; CHECK-NEXT:  Loop %loop: Trip multiple is 1
 111 ;
 112 entry:
 113   %offset = load i32, ptr %input
 114   br label %loop
 115 loop:
 116   %i = phi i32 [ %i.next, %loop ], [ 0, %entry ]
 117   %i.next = add nuw i32 %i, 1
 118   %of_interest = add nuw nsw i32 %i.next, %offset
 119   %gep2 = getelementptr i32, ptr %input, i32 %of_interest
 120   store i32 0, ptr %gep2
 121   %exitcond = icmp eq i32 %of_interest, %needle
 122   br i1 %exitcond, label %exit, label %loop
 123
 124 exit:
 125   ret void
 126 }
 127
 128 ; Case where we're checking to see if add flags are valid in defining scope
 129 ; and other operands are *not* invariant.
 130 define void @test-add-scope-bound(ptr %input, i32 %needle) {
 131 ; CHECK-LABEL: 'test-add-scope-bound'
 132 ; CHECK-NEXT:  Classifying expressions for: @test-add-scope-bound
 133 ; CHECK-NEXT:    %i = phi i32 [ %i.next, %loop ], [ 0, %entry ]
 134 ; CHECK-NEXT:    --> {0,+,1}<nuw><%loop> U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Computable }
 135 ; CHECK-NEXT:    %gep = getelementptr i32, ptr %input, i32 %i
 136 ; CHECK-NEXT:    --> ((4 * (sext i32 {0,+,1}<nuw><%loop> to i64))<nsw> + %input) U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Computable }
 137 ; CHECK-NEXT:    %offset = load i32, ptr %gep, align 4
 138 ; CHECK-NEXT:    --> %offset U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
 139 ; CHECK-NEXT:    %i.next = add nuw i32 %i, 1
 140 ; CHECK-NEXT:    --> {1,+,1}<nuw><%loop> U: [1,0) S: [1,0) Exits: <<Unknown>> LoopDispositions: { %loop: Computable }
 141 ; CHECK-NEXT:    %of_interest = add nuw nsw i32 %i.next, %offset
 142 ; CHECK-NEXT:    --> ({1,+,1}<nuw><%loop> + %offset)<nuw><nsw> U: [1,0) S: [1,0) Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
 143 ; CHECK-NEXT:    %gep2 = getelementptr i32, ptr %input, i32 %of_interest
 144 ; CHECK-NEXT:    --> ((4 * ((sext i32 {1,+,1}<nuw><%loop> to i64) + (sext i32 %offset to i64))<nsw>)<nsw> + %input) U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
 145 ; CHECK-NEXT:  Determining loop execution counts for: @test-add-scope-bound
 146 ; CHECK-NEXT:  Loop %loop: Unpredictable backedge-taken count.
 147 ; CHECK-NEXT:  Loop %loop: Unpredictable constant max backedge-taken count.
 148 ; CHECK-NEXT:  Loop %loop: Unpredictable symbolic max backedge-taken count.
 149 ;
 150 entry:
 151   br label %loop
 152 loop:
 153   %i = phi i32 [ %i.next, %loop ], [ 0, %entry ]
 154   %gep = getelementptr i32, ptr %input, i32 %i
 155   %offset = load i32, ptr %gep
 156   %i.next = add nuw i32 %i, 1
 157   %of_interest = add nuw nsw i32 %i.next, %offset
 158   %gep2 = getelementptr i32, ptr %input, i32 %of_interest
 159   store i32 0, ptr %gep2
 160   %exitcond = icmp eq i32 %of_interest, %needle
 161   br i1 %exitcond, label %exit, label %loop
 162
 163 exit:
 164   ret void
 165 }
 166
 167 define void @test-add-scope-bound-unkn-preheader(ptr %input, i32 %needle) {
 168 ; CHECK-LABEL: 'test-add-scope-bound-unkn-preheader'
 169 ; CHECK-NEXT:  Classifying expressions for: @test-add-scope-bound-unkn-preheader
 170 ; CHECK-NEXT:    %offset = load i32, ptr %input, align 4
 171 ; CHECK-NEXT:    --> %offset U: full-set S: full-set
 172 ; CHECK-NEXT:    %i = phi i32 [ %i.next, %loop ], [ 0, %entry ]
 173 ; CHECK-NEXT:    --> {0,+,%offset}<nuw><%loop> U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Computable }
 174 ; CHECK-NEXT:    %i.next = add nuw i32 %i, %offset
 175 ; CHECK-NEXT:    --> {%offset,+,%offset}<nuw><%loop> U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Computable }
 176 ; CHECK-NEXT:    %gep2 = getelementptr i32, ptr %input, i32 %i.next
 177 ; CHECK-NEXT:    --> ((4 * (sext i32 {%offset,+,%offset}<nuw><%loop> to i64))<nsw> + %input) U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Computable }
 178 ; CHECK-NEXT:  Determining loop execution counts for: @test-add-scope-bound-unkn-preheader
 179 ; CHECK-NEXT:  Loop %loop: Unpredictable backedge-taken count.
 180 ; CHECK-NEXT:  Loop %loop: Unpredictable constant max backedge-taken count.
 181 ; CHECK-NEXT:  Loop %loop: Unpredictable symbolic max backedge-taken count.
 182 ;
 183 entry:
 184   %offset = load i32, ptr %input
 185   br label %loop
 186 loop:
 187   %i = phi i32 [ %i.next, %loop ], [ 0, %entry ]
 188   %i.next = add nuw i32 %i, %offset
 189   %gep2 = getelementptr i32, ptr %input, i32 %i.next
 190   store i32 0, ptr %gep2
 191   %exitcond = icmp eq i32 %i.next, %needle
 192   br i1 %exitcond, label %exit, label %loop
 193
 194 exit:
 195   ret void
 196 }
 197
 198 define void @test-add-scope-bound-unkn-preheader-neg1(ptr %input, i32 %needle) {
 199 ; CHECK-LABEL: 'test-add-scope-bound-unkn-preheader-neg1'
 200 ; CHECK-NEXT:  Classifying expressions for: @test-add-scope-bound-unkn-preheader-neg1
 201 ; CHECK-NEXT:    %offset = load i32, ptr %input, align 4
 202 ; CHECK-NEXT:    --> %offset U: full-set S: full-set
 203 ; CHECK-NEXT:    %i = phi i32 [ %i.next, %loop ], [ 0, %entry ]
 204 ; CHECK-NEXT:    --> {0,+,%offset}<nuw><%loop> U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Computable }
 205 ; CHECK-NEXT:    %i.next = add nuw i32 %i, %offset
 206 ; CHECK-NEXT:    --> {%offset,+,%offset}<nuw><%loop> U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Computable }
 207 ; CHECK-NEXT:    %gep2 = getelementptr i32, ptr %input, i32 %i.next
 208 ; CHECK-NEXT:    --> ((4 * (sext i32 {%offset,+,%offset}<nuw><%loop> to i64))<nsw> + %input) U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Computable }
 209 ; CHECK-NEXT:  Determining loop execution counts for: @test-add-scope-bound-unkn-preheader-neg1
 210 ; CHECK-NEXT:  Loop %loop: Unpredictable backedge-taken count.
 211 ; CHECK-NEXT:  Loop %loop: Unpredictable constant max backedge-taken count.
 212 ; CHECK-NEXT:  Loop %loop: Unpredictable symbolic max backedge-taken count.
 213 ;
 214 entry:
 215   %offset = load i32, ptr %input
 216   call void @foo()
 217   br label %loop
 218 loop:
 219   %i = phi i32 [ %i.next, %loop ], [ 0, %entry ]
 220   %i.next = add nuw i32 %i, %offset
 221   %gep2 = getelementptr i32, ptr %input, i32 %i.next
 222   store i32 0, ptr %gep2
 223   %exitcond = icmp eq i32 %i.next, %needle
 224   br i1 %exitcond, label %exit, label %loop
 225
 226 exit:
 227   ret void
 228 }
 229
 230 define void @test-add-scope-bound-unkn-preheader-neg2(ptr %input, i32 %needle) {
 231 ; CHECK-LABEL: 'test-add-scope-bound-unkn-preheader-neg2'
 232 ; CHECK-NEXT:  Classifying expressions for: @test-add-scope-bound-unkn-preheader-neg2
 233 ; CHECK-NEXT:    %offset = load i32, ptr %input, align 4
 234 ; CHECK-NEXT:    --> %offset U: full-set S: full-set
 235 ; CHECK-NEXT:    %i = phi i32 [ %i.next, %loop ], [ 0, %entry ]
 236 ; CHECK-NEXT:    --> {0,+,%offset}<nuw><%loop> U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Computable }
 237 ; CHECK-NEXT:    %i.next = add nuw i32 %i, %offset
 238 ; CHECK-NEXT:    --> {%offset,+,%offset}<nw><%loop> U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Computable }
 239 ; CHECK-NEXT:    %gep2 = getelementptr i32, ptr %input, i32 %i.next
 240 ; CHECK-NEXT:    --> ((4 * (sext i32 {%offset,+,%offset}<nw><%loop> to i64))<nsw> + %input) U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Computable }
 241 ; CHECK-NEXT:  Determining loop execution counts for: @test-add-scope-bound-unkn-preheader-neg2
 242 ; CHECK-NEXT:  Loop %loop: Unpredictable backedge-taken count.
 243 ; CHECK-NEXT:  Loop %loop: Unpredictable constant max backedge-taken count.
 244 ; CHECK-NEXT:  Loop %loop: Unpredictable symbolic max backedge-taken count.
 245 ;
 246 entry:
 247   %offset = load i32, ptr %input
 248   br label %loop
 249 loop:
 250   %i = phi i32 [ %i.next, %loop ], [ 0, %entry ]
 251   call void @foo()
 252   %i.next = add nuw i32 %i, %offset
 253   %gep2 = getelementptr i32, ptr %input, i32 %i.next
 254   store i32 0, ptr %gep2
 255   %exitcond = icmp eq i32 %i.next, %needle
 256   br i1 %exitcond, label %exit, label %loop
 257
 258 exit:
 259   ret void
 260 }
 261
 262
 263 define void @test-add-scope-bound-unkn-header(ptr %input, i32 %needle) {
 264 ; CHECK-LABEL: 'test-add-scope-bound-unkn-header'
 265 ; CHECK-NEXT:  Classifying expressions for: @test-add-scope-bound-unkn-header
 266 ; CHECK-NEXT:    %i = phi i32 [ %i.next, %loop ], [ 0, %entry ]
 267 ; CHECK-NEXT:    --> %i U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
 268 ; CHECK-NEXT:    %gep = getelementptr i32, ptr %input, i32 %i
 269 ; CHECK-NEXT:    --> ((4 * (sext i32 %i to i64))<nsw> + %input) U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
 270 ; CHECK-NEXT:    %offset = load i32, ptr %gep, align 4
 271 ; CHECK-NEXT:    --> %offset U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
 272 ; CHECK-NEXT:    %i.next = add nuw i32 %i, %offset
 273 ; CHECK-NEXT:    --> (%offset + %i)<nuw> U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
 274 ; CHECK-NEXT:    %gep2 = getelementptr i32, ptr %input, i32 %i.next
 275 ; CHECK-NEXT:    --> ((4 * (sext i32 (%offset + %i)<nuw> to i64))<nsw> + %input) U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
 276 ; CHECK-NEXT:  Determining loop execution counts for: @test-add-scope-bound-unkn-header
 277 ; CHECK-NEXT:  Loop %loop: Unpredictable backedge-taken count.
 278 ; CHECK-NEXT:  Loop %loop: Unpredictable constant max backedge-taken count.
 279 ; CHECK-NEXT:  Loop %loop: Unpredictable symbolic max backedge-taken count.
 280 ;
 281 entry:
 282   br label %loop
 283 loop:
 284   %i = phi i32 [ %i.next, %loop ], [ 0, %entry ]
 285   %gep = getelementptr i32, ptr %input, i32 %i
 286   %offset = load i32, ptr %gep
 287   %i.next = add nuw i32 %i, %offset
 288   %gep2 = getelementptr i32, ptr %input, i32 %i.next
 289   store i32 0, ptr %gep2
 290   %exitcond = icmp eq i32 %i.next, %needle
 291   br i1 %exitcond, label %exit, label %loop
 292
 293 exit:
 294   ret void
 295 }
 296
 297 define void @test-add-scope-bound-unkn-header2(ptr %input, i32 %needle) {
 298 ; CHECK-LABEL: 'test-add-scope-bound-unkn-header2'
 299 ; CHECK-NEXT:  Classifying expressions for: @test-add-scope-bound-unkn-header2
 300 ; CHECK-NEXT:    %i = phi i32 [ %i.next, %loop ], [ 0, %entry ]
 301 ; CHECK-NEXT:    --> %i U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
 302 ; CHECK-NEXT:    %gep = getelementptr i32, ptr %input, i32 %i
 303 ; CHECK-NEXT:    --> ((4 * (sext i32 %i to i64))<nsw> + %input) U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
 304 ; CHECK-NEXT:    %offset = load i32, ptr %gep, align 4
 305 ; CHECK-NEXT:    --> %offset U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
 306 ; CHECK-NEXT:    %i.next = add nuw i32 %i, %offset
 307 ; CHECK-NEXT:    --> (%offset + %i)<nuw> U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
 308 ; CHECK-NEXT:    %gep2 = getelementptr i32, ptr %input, i32 %i.next
 309 ; CHECK-NEXT:    --> ((4 * (sext i32 (%offset + %i)<nuw> to i64))<nsw> + %input) U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
 310 ; CHECK-NEXT:  Determining loop execution counts for: @test-add-scope-bound-unkn-header2
 311 ; CHECK-NEXT:  Loop %loop: Unpredictable backedge-taken count.
 312 ; CHECK-NEXT:  Loop %loop: Unpredictable constant max backedge-taken count.
 313 ; CHECK-NEXT:  Loop %loop: Unpredictable symbolic max backedge-taken count.
 314 ;
 315 entry:
 316   br label %loop
 317 loop:
 318   %i = phi i32 [ %i.next, %loop ], [ 0, %entry ]
 319   call void @foo()
 320   %gep = getelementptr i32, ptr %input, i32 %i
 321   %offset = load i32, ptr %gep
 322   %i.next = add nuw i32 %i, %offset
 323   %gep2 = getelementptr i32, ptr %input, i32 %i.next
 324   store i32 0, ptr %gep2
 325   %exitcond = icmp eq i32 %i.next, %needle
 326   br i1 %exitcond, label %exit, label %loop
 327
 328 exit:
 329   ret void
 330 }
 331
 332 define void @test-add-scope-bound-unkn-header-neg(ptr %input, i32 %needle) {
 333 ; CHECK-LABEL: 'test-add-scope-bound-unkn-header-neg'
 334 ; CHECK-NEXT:  Classifying expressions for: @test-add-scope-bound-unkn-header-neg
 335 ; CHECK-NEXT:    %i = phi i32 [ %i.next, %loop ], [ 0, %entry ]
 336 ; CHECK-NEXT:    --> %i U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
 337 ; CHECK-NEXT:    %gep = getelementptr i32, ptr %input, i32 %i
 338 ; CHECK-NEXT:    --> ((4 * (sext i32 %i to i64))<nsw> + %input) U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
 339 ; CHECK-NEXT:    %offset = load i32, ptr %gep, align 4
 340 ; CHECK-NEXT:    --> %offset U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
 341 ; CHECK-NEXT:    %i.next = add nuw i32 %i, %offset
 342 ; CHECK-NEXT:    --> (%offset + %i) U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
 343 ; CHECK-NEXT:    %gep2 = getelementptr i32, ptr %input, i32 %i.next
 344 ; CHECK-NEXT:    --> ((4 * (sext i32 (%offset + %i) to i64))<nsw> + %input) U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
 345 ; CHECK-NEXT:  Determining loop execution counts for: @test-add-scope-bound-unkn-header-neg
 346 ; CHECK-NEXT:  Loop %loop: Unpredictable backedge-taken count.
 347 ; CHECK-NEXT:  Loop %loop: Unpredictable constant max backedge-taken count.
 348 ; CHECK-NEXT:  Loop %loop: Unpredictable symbolic max backedge-taken count.
 349 ;
 350 entry:
 351   br label %loop
 352 loop:
 353   %i = phi i32 [ %i.next, %loop ], [ 0, %entry ]
 354   %gep = getelementptr i32, ptr %input, i32 %i
 355   %offset = load i32, ptr %gep
 356   call void @foo()
 357   %i.next = add nuw i32 %i, %offset
 358   %gep2 = getelementptr i32, ptr %input, i32 %i.next
 359   store i32 0, ptr %gep2
 360   %exitcond = icmp eq i32 %i.next, %needle
 361   br i1 %exitcond, label %exit, label %loop
 362
 363 exit:
 364   ret void
 365 }
 366
 367 define void @test-add-nuw-from-icmp(ptr %input, i32 %offset,
 368 ; CHECK-LABEL: 'test-add-nuw-from-icmp'
 369 ; CHECK-NEXT:  Classifying expressions for: @test-add-nuw-from-icmp
 370 ; CHECK-NEXT:    %i = phi i32 [ %nexti, %loop ], [ 0, %entry ]
 371 ; CHECK-NEXT:    --> {0,+,1}<nuw><%loop> U: full-set S: full-set Exits: (-1 + %numIterations) LoopDispositions: { %loop: Computable }
 372 ; CHECK-NEXT:    %index32 = add nuw i32 %i, %offset
 373 ; CHECK-NEXT:    --> {%offset,+,1}<nuw><%loop> U: full-set S: full-set Exits: (-1 + %offset + %numIterations) LoopDispositions: { %loop: Computable }
 374 ; CHECK-NEXT:    %cmp.idx = sext i1 %cmp to i32
 375 ; CHECK-NEXT:    --> (sext i1 %cmp to i32) U: [-1,1) S: [-1,1) Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
 376 ; CHECK-NEXT:    %ptr = getelementptr inbounds float, ptr %input, i32 %cmp.idx
 377 ; CHECK-NEXT:    --> ((4 * (sext i1 %cmp to i64))<nsw> + %input) U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
 378 ; CHECK-NEXT:    %nexti = add nuw i32 %i, 1
 379 ; CHECK-NEXT:    --> {1,+,1}<nuw><%loop> U: [1,0) S: [1,0) Exits: %numIterations LoopDispositions: { %loop: Computable }
 380 ; CHECK-NEXT:  Determining loop execution counts for: @test-add-nuw-from-icmp
 381 ; CHECK-NEXT:  Loop %loop: backedge-taken count is (-1 + %numIterations)
 382 ; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is i32 -1
 383 ; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is (-1 + %numIterations)
 384 ; CHECK-NEXT:  Loop %loop: Trip multiple is 1
 385 ;
 386   i32 %numIterations) {
 387 entry:
 388   br label %loop
 389 loop:
 390   %i = phi i32 [ %nexti, %loop ], [ 0, %entry ]
 391
 392   %index32 = add nuw i32 %i, %offset
 393   %cmp = icmp sgt i32 %index32, 0
 394   %cmp.idx = sext i1 %cmp to i32
 395
 396   %ptr = getelementptr inbounds float, ptr %input, i32 %cmp.idx
 397   %nexti = add nuw i32 %i, 1
 398   %f = load float, ptr %ptr, align 4
 399   %exitcond = icmp eq i32 %nexti, %numIterations
 400   br i1 %exitcond, label %exit, label %loop
 401
 402 exit:
 403   ret void
 404 }
 405
 406 ; With no load to trigger UB from poison, we cannot infer nsw.
 407 define void @test-add-no-load(ptr %input, i32 %offset, i32 %numIterations) {
 408 ; CHECK-LABEL: 'test-add-no-load'
 409 ; CHECK-NEXT:  Classifying expressions for: @test-add-no-load
 410 ; CHECK-NEXT:    %i = phi i32 [ %nexti, %loop ], [ 0, %entry ]
 411 ; CHECK-NEXT:    --> {0,+,1}<nuw><%loop> U: full-set S: full-set Exits: (-1 + %numIterations) LoopDispositions: { %loop: Computable }
 412 ; CHECK-NEXT:    %index32 = add nsw i32 %i, %offset
 413 ; CHECK-NEXT:    --> {%offset,+,1}<nw><%loop> U: full-set S: full-set Exits: (-1 + %offset + %numIterations) LoopDispositions: { %loop: Computable }
 414 ; CHECK-NEXT:    %ptr = getelementptr inbounds float, ptr %input, i32 %index32
 415 ; CHECK-NEXT:    --> ((4 * (sext i32 {%offset,+,1}<nw><%loop> to i64))<nsw> + %input) U: full-set S: full-set Exits: ((4 * (sext i32 (-1 + %offset + %numIterations) to i64))<nsw> + %input) LoopDispositions: { %loop: Computable }
 416 ; CHECK-NEXT:    %nexti = add nuw i32 %i, 1
 417 ; CHECK-NEXT:    --> {1,+,1}<nuw><%loop> U: [1,0) S: [1,0) Exits: %numIterations LoopDispositions: { %loop: Computable }
 418 ; CHECK-NEXT:  Determining loop execution counts for: @test-add-no-load
 419 ; CHECK-NEXT:  Loop %loop: backedge-taken count is (-1 + %numIterations)
 420 ; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is i32 -1
 421 ; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is (-1 + %numIterations)
 422 ; CHECK-NEXT:  Loop %loop: Trip multiple is 1
 423 ;
 424 entry:
 425   br label %loop
 426 loop:
 427   %i = phi i32 [ %nexti, %loop ], [ 0, %entry ]
 428
 429   %index32 = add nsw i32 %i, %offset
 430
 431   %ptr = getelementptr inbounds float, ptr %input, i32 %index32
 432   %nexti = add nuw i32 %i, 1
 433   %exitcond = icmp eq i32 %nexti, %numIterations
 434   br i1 %exitcond, label %exit, label %loop
 435
 436 exit:
 437   ret void
 438 }
 439
 440 ; The current code is only supposed to look at the loop header, so
 441 ; it should not infer nsw in this case, as that would require looking
 442 ; outside the loop header.
 443 define void @test-add-not-header(ptr %input, i32 %offset, i32 %numIterations) {
 444 ; CHECK-LABEL: 'test-add-not-header'
 445 ; CHECK-NEXT:  Classifying expressions for: @test-add-not-header
 446 ; CHECK-NEXT:    %i = phi i32 [ %nexti, %loop2 ], [ 0, %entry ]
 447 ; CHECK-NEXT:    --> {0,+,1}<nuw><nsw><%loop> U: [0,-2147483648) S: [0,-2147483648) Exits: (-1 + %numIterations) LoopDispositions: { %loop: Computable }
 448 ; CHECK-NEXT:    %index32 = add nsw i32 %i, %offset
 449 ; CHECK-NEXT:    --> {%offset,+,1}<nw><%loop> U: full-set S: full-set Exits: (-1 + %offset + %numIterations) LoopDispositions: { %loop: Computable }
 450 ; CHECK-NEXT:    %ptr = getelementptr inbounds float, ptr %input, i32 %index32
 451 ; CHECK-NEXT:    --> ((4 * (sext i32 {%offset,+,1}<nw><%loop> to i64))<nsw> + %input) U: full-set S: full-set Exits: ((4 * (sext i32 (-1 + %offset + %numIterations) to i64))<nsw> + %input) LoopDispositions: { %loop: Computable }
 452 ; CHECK-NEXT:    %nexti = add nsw i32 %i, 1
 453 ; CHECK-NEXT:    --> {1,+,1}<nuw><nsw><%loop> U: [1,-2147483648) S: [1,-2147483648) Exits: %numIterations LoopDispositions: { %loop: Computable }
 454 ; CHECK-NEXT:  Determining loop execution counts for: @test-add-not-header
 455 ; CHECK-NEXT:  Loop %loop: backedge-taken count is (-1 + %numIterations)
 456 ; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is i32 -1
 457 ; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is (-1 + %numIterations)
 458 ; CHECK-NEXT:  Loop %loop: Trip multiple is 1
 459 ;
 460 entry:
 461   br label %loop
 462 loop:
 463   %i = phi i32 [ %nexti, %loop2 ], [ 0, %entry ]
 464   br label %loop2
 465 loop2:
 466
 467   %index32 = add nsw i32 %i, %offset
 468
 469   %ptr = getelementptr inbounds float, ptr %input, i32 %index32
 470   %nexti = add nsw i32 %i, 1
 471   %f = load float, ptr %ptr, align 4
 472   %exitcond = icmp eq i32 %nexti, %numIterations
 473   br i1 %exitcond, label %exit, label %loop
 474 exit:
 475   ret void
 476 }
 477
 478 ; Same thing as test-add-not-header, but in this case only the load
 479 ; instruction is outside the loop header.
 480 define void @test-add-not-header2(ptr %input, i32 %offset, i32 %numIterations) {
 481 ; CHECK-LABEL: 'test-add-not-header2'
 482 ; CHECK-NEXT:  Classifying expressions for: @test-add-not-header2
 483 ; CHECK-NEXT:    %i = phi i32 [ %nexti, %loop2 ], [ 0, %entry ]
 484 ; CHECK-NEXT:    --> {0,+,1}<nuw><nsw><%loop> U: [0,-2147483648) S: [0,-2147483648) Exits: (-1 + %numIterations) LoopDispositions: { %loop: Computable }
 485 ; CHECK-NEXT:    %index32 = add nsw i32 %i, %offset
 486 ; CHECK-NEXT:    --> {%offset,+,1}<nsw><%loop> U: full-set S: full-set Exits: (-1 + %offset + %numIterations) LoopDispositions: { %loop: Computable }
 487 ; CHECK-NEXT:    %ptr = getelementptr inbounds float, ptr %input, i32 %index32
 488 ; CHECK-NEXT:    --> {((4 * (sext i32 %offset to i64))<nsw> + %input),+,4}<nw><%loop> U: full-set S: full-set Exits: ((4 * (zext i32 (-1 + %numIterations) to i64))<nuw><nsw> + (4 * (sext i32 %offset to i64))<nsw> + %input) LoopDispositions: { %loop: Computable }
 489 ; CHECK-NEXT:    %nexti = add nsw i32 %i, 1
 490 ; CHECK-NEXT:    --> {1,+,1}<nuw><nsw><%loop> U: [1,-2147483648) S: [1,-2147483648) Exits: %numIterations LoopDispositions: { %loop: Computable }
 491 ; CHECK-NEXT:  Determining loop execution counts for: @test-add-not-header2
 492 ; CHECK-NEXT:  Loop %loop: backedge-taken count is (-1 + %numIterations)
 493 ; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is i32 -1
 494 ; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is (-1 + %numIterations)
 495 ; CHECK-NEXT:  Loop %loop: Trip multiple is 1
 496 ;
 497 entry:
 498   br label %loop
 499 loop:
 500   %i = phi i32 [ %nexti, %loop2 ], [ 0, %entry ]
 501
 502   %index32 = add nsw i32 %i, %offset
 503
 504   %ptr = getelementptr inbounds float, ptr %input, i32 %index32
 505   %nexti = add nsw i32 %i, 1
 506   br label %loop2
 507 loop2:
 508   %f = load float, ptr %ptr, align 4
 509   %exitcond = icmp eq i32 %nexti, %numIterations
 510   br i1 %exitcond, label %exit, label %loop
 511 exit:
 512   ret void
 513 }
 514
 515 ; Similar to test-add-not-header, but in this case the load
 516 ; instruction may not be executed.
 517 define void @test-add-not-header3(ptr %input, i32 %offset, i32 %numIterations,
 518 ; CHECK-LABEL: 'test-add-not-header3'
 519 ; CHECK-NEXT:  Classifying expressions for: @test-add-not-header3
 520 ; CHECK-NEXT:    %i = phi i32 [ %nexti, %loop2 ], [ 0, %entry ]
 521 ; CHECK-NEXT:    --> {0,+,1}<nuw><nsw><%loop> U: [0,-2147483648) S: [0,-2147483648) Exits: <<Unknown>> LoopDispositions: { %loop: Computable }
 522 ; CHECK-NEXT:    %index32 = add nsw i32 %i, %offset
 523 ; CHECK-NEXT:    --> {%offset,+,1}<nw><%loop> U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Computable }
 524 ; CHECK-NEXT:    %ptr = getelementptr inbounds float, ptr %input, i32 %index32
 525 ; CHECK-NEXT:    --> ((4 * (sext i32 {%offset,+,1}<nw><%loop> to i64))<nsw> + %input) U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Computable }
 526 ; CHECK-NEXT:    %nexti = add nsw i32 %i, 1
 527 ; CHECK-NEXT:    --> {1,+,1}<nuw><%loop> U: [1,0) S: [1,0) Exits: <<Unknown>> LoopDispositions: { %loop: Computable }
 528 ; CHECK-NEXT:    %cond = load volatile i1, ptr %cond_buf, align 1
 529 ; CHECK-NEXT:    --> %cond U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
 530 ; CHECK-NEXT:  Determining loop execution counts for: @test-add-not-header3
 531 ; CHECK-NEXT:  Loop %loop: <multiple exits> Unpredictable backedge-taken count.
 532 ; CHECK-NEXT:    exit count for loop: ***COULDNOTCOMPUTE***
 533 ; CHECK-NEXT:    exit count for loop2: (-1 + %numIterations)
 534 ; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is i32 -1
 535 ; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is (-1 + %numIterations)
 536 ; CHECK-NEXT:    symbolic max exit count for loop: ***COULDNOTCOMPUTE***
 537 ; CHECK-NEXT:    symbolic max exit count for loop2: (-1 + %numIterations)
 538 ;
 539   ptr %cond_buf) {
 540 entry:
 541   br label %loop
 542 loop:
 543   %i = phi i32 [ %nexti, %loop2 ], [ 0, %entry ]
 544
 545   %index32 = add nsw i32 %i, %offset
 546
 547   %ptr = getelementptr inbounds float, ptr %input, i32 %index32
 548   %nexti = add nsw i32 %i, 1
 549   %cond = load volatile i1, ptr %cond_buf
 550   br i1 %cond, label %loop2, label %exit
 551 loop2:
 552   %f = load float, ptr %ptr, align 4
 553   %exitcond = icmp eq i32 %nexti, %numIterations
 554   br i1 %exitcond, label %exit, label %loop
 555 exit:
 556   ret void
 557 }
 558
 559 ; Same thing as test-add-not-header2, except we have a few extra
 560 ; blocks.
 561 define void @test-add-not-header4(ptr %input, i32 %offset, i32 %numIterations) {
 562 ; CHECK-LABEL: 'test-add-not-header4'
 563 ; CHECK-NEXT:  Classifying expressions for: @test-add-not-header4
 564 ; CHECK-NEXT:    %i = phi i32 [ %nexti, %loop2 ], [ 0, %entry ]
 565 ; CHECK-NEXT:    --> {0,+,1}<nuw><nsw><%loop> U: [0,-2147483648) S: [0,-2147483648) Exits: (-1 + %numIterations) LoopDispositions: { %loop: Computable }
 566 ; CHECK-NEXT:    %index32 = add nsw i32 %i, %offset
 567 ; CHECK-NEXT:    --> {%offset,+,1}<nsw><%loop> U: full-set S: full-set Exits: (-1 + %offset + %numIterations) LoopDispositions: { %loop: Computable }
 568 ; CHECK-NEXT:    %ptr = getelementptr inbounds float, ptr %input, i32 %index32
 569 ; CHECK-NEXT:    --> {((4 * (sext i32 %offset to i64))<nsw> + %input),+,4}<nw><%loop> U: full-set S: full-set Exits: ((4 * (zext i32 (-1 + %numIterations) to i64))<nuw><nsw> + (4 * (sext i32 %offset to i64))<nsw> + %input) LoopDispositions: { %loop: Computable }
 570 ; CHECK-NEXT:    %nexti = add nsw i32 %i, 1
 571 ; CHECK-NEXT:    --> {1,+,1}<nuw><nsw><%loop> U: [1,-2147483648) S: [1,-2147483648) Exits: %numIterations LoopDispositions: { %loop: Computable }
 572 ; CHECK-NEXT:  Determining loop execution counts for: @test-add-not-header4
 573 ; CHECK-NEXT:  Loop %loop: backedge-taken count is (-1 + %numIterations)
 574 ; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is i32 -1
 575 ; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is (-1 + %numIterations)
 576 ; CHECK-NEXT:  Loop %loop: Trip multiple is 1
 577 ;
 578 entry:
 579   br label %loop
 580 loop:
 581   %i = phi i32 [ %nexti, %loop2 ], [ 0, %entry ]
 582
 583   %index32 = add nsw i32 %i, %offset
 584
 585   %ptr = getelementptr inbounds float, ptr %input, i32 %index32
 586   %nexti = add nsw i32 %i, 1
 587   br label %loop3
 588 loop3:
 589   br label %loop4
 590 loop4:
 591   br label %loop2
 592 loop2:
 593   %f = load float, ptr %ptr, align 4
 594   %exitcond = icmp eq i32 %nexti, %numIterations
 595   br i1 %exitcond, label %exit, label %loop
 596 exit:
 597   ret void
 598 }
 599
 600 ; Demonstrate why we need a Visited set in llvm::programUndefinedIfPoison.
 601 define void @test-add-not-header5(ptr %input, i32 %offset) {
 602 ; CHECK-LABEL: 'test-add-not-header5'
 603 ; CHECK-NEXT:  Classifying expressions for: @test-add-not-header5
 604 ; CHECK-NEXT:    %i = phi i32 [ %nexti, %loop ], [ 0, %entry ]
 605 ; CHECK-NEXT:    --> {0,+,1}<nuw><nsw><%loop> U: [0,-2147483648) S: [0,-2147483648) Exits: <<Unknown>> LoopDispositions: { %loop: Computable }
 606 ; CHECK-NEXT:    %index32 = add nsw i32 %i, %offset
 607 ; CHECK-NEXT:    --> {%offset,+,1}<nw><%loop> U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Computable }
 608 ; CHECK-NEXT:    %ptr = getelementptr inbounds float, ptr %input, i32 %index32
 609 ; CHECK-NEXT:    --> ((4 * (sext i32 {%offset,+,1}<nw><%loop> to i64))<nsw> + %input) U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Computable }
 610 ; CHECK-NEXT:    %nexti = add nsw i32 %i, 1
 611 ; CHECK-NEXT:    --> {1,+,1}<nuw><%loop> U: [1,0) S: [1,0) Exits: <<Unknown>> LoopDispositions: { %loop: Computable }
 612 ; CHECK-NEXT:  Determining loop execution counts for: @test-add-not-header5
 613 ; CHECK-NEXT:  Loop %loop: <multiple exits> Unpredictable backedge-taken count.
 614 ; CHECK-NEXT:  Loop %loop: Unpredictable constant max backedge-taken count.
 615 ; CHECK-NEXT:  Loop %loop: Unpredictable symbolic max backedge-taken count.
 616 ;
 617 entry:
 618   br label %loop
 619 loop:
 620   %i = phi i32 [ %nexti, %loop ], [ 0, %entry ]
 621
 622   %index32 = add nsw i32 %i, %offset
 623
 624   %ptr = getelementptr inbounds float, ptr %input, i32 %index32
 625   %nexti = add nsw i32 %i, 1
 626   br label %loop
 627
 628 exit:
 629   ret void
 630 }
 631
 632 ; Variant where a separate IV is used for the load.
 633 define void @test-add-not-header6(ptr %input, i32 %offset, i32 %numIterations) {
 634 ; CHECK-LABEL: 'test-add-not-header6'
 635 ; CHECK-NEXT:  Classifying expressions for: @test-add-not-header6
 636 ; CHECK-NEXT:    %i = phi i32 [ %nexti, %loop2 ], [ 0, %entry ]
 637 ; CHECK-NEXT:    --> {0,+,1}<nuw><nsw><%loop> U: [0,-2147483648) S: [0,-2147483648) Exits: (-1 + %numIterations) LoopDispositions: { %loop: Computable }
 638 ; CHECK-NEXT:    %i2 = phi i32 [ %nexti2, %loop2 ], [ %offset, %entry ]
 639 ; CHECK-NEXT:    --> {%offset,+,1}<nsw><%loop> U: full-set S: full-set Exits: (-1 + %offset + %numIterations) LoopDispositions: { %loop: Computable }
 640 ; CHECK-NEXT:    %nexti = add nsw i32 %i, 1
 641 ; CHECK-NEXT:    --> {1,+,1}<nuw><nsw><%loop> U: [1,-2147483648) S: [1,-2147483648) Exits: %numIterations LoopDispositions: { %loop: Computable }
 642 ; CHECK-NEXT:    %nexti2 = add nsw i32 %i2, 1
 643 ; CHECK-NEXT:    --> {(1 + %offset),+,1}<nsw><%loop> U: full-set S: full-set Exits: (%offset + %numIterations) LoopDispositions: { %loop: Computable }
 644 ; CHECK-NEXT:    %ptr = getelementptr inbounds float, ptr %input, i32 %nexti2
 645 ; CHECK-NEXT:    --> {((4 * (sext i32 (1 + %offset) to i64))<nsw> + %input),+,4}<nw><%loop> U: full-set S: full-set Exits: ((4 * (zext i32 (-1 + %numIterations) to i64))<nuw><nsw> + (4 * (sext i32 (1 + %offset) to i64))<nsw> + %input) LoopDispositions: { %loop: Computable }
 646 ; CHECK-NEXT:  Determining loop execution counts for: @test-add-not-header6
 647 ; CHECK-NEXT:  Loop %loop: backedge-taken count is (-1 + %numIterations)
 648 ; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is i32 -1
 649 ; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is (-1 + %numIterations)
 650 ; CHECK-NEXT:  Loop %loop: Trip multiple is 1
 651 ;
 652 entry:
 653   br label %loop
 654 loop:
 655   %i = phi i32 [ %nexti, %loop2 ], [ 0, %entry ]
 656   %i2 = phi i32 [ %nexti2, %loop2 ], [ %offset, %entry ]
 657   br label %loop2
 658 loop2:
 659   %nexti = add nsw i32 %i, 1
 660   %nexti2 = add nsw i32 %i2, 1
 661   %ptr = getelementptr inbounds float, ptr %input, i32 %nexti2
 662   %f = load float, ptr %ptr, align 4
 663   %exitcond = icmp eq i32 %nexti, %numIterations
 664   br i1 %exitcond, label %exit, label %loop
 665 exit:
 666   ret void
 667 }
 668
 669 ; Variant where the loop latch is not exiting.
 670 define void @test-add-not-header7(ptr %input, i32 %offset, i32 %numIterations) {
 671 ; CHECK-LABEL: 'test-add-not-header7'
 672 ; CHECK-NEXT:  Classifying expressions for: @test-add-not-header7
 673 ; CHECK-NEXT:    %i = phi i32 [ %nexti, %loop.latch ], [ 0, %entry ]
 674 ; CHECK-NEXT:    --> {0,+,1}<nuw><nsw><%loop> U: [0,-2147483648) S: [0,-2147483648) Exits: (-1 + %numIterations) LoopDispositions: { %loop: Computable }
 675 ; CHECK-NEXT:    %i2 = phi i32 [ %nexti2, %loop.latch ], [ %offset, %entry ]
 676 ; CHECK-NEXT:    --> {%offset,+,1}<nsw><%loop> U: full-set S: full-set Exits: (-1 + %offset + %numIterations) LoopDispositions: { %loop: Computable }
 677 ; CHECK-NEXT:    %nexti = add nsw i32 %i, 1
 678 ; CHECK-NEXT:    --> {1,+,1}<nuw><nsw><%loop> U: [1,-2147483648) S: [1,-2147483648) Exits: %numIterations LoopDispositions: { %loop: Computable }
 679 ; CHECK-NEXT:    %nexti2 = add nsw i32 %i2, 1
 680 ; CHECK-NEXT:    --> {(1 + %offset),+,1}<nsw><%loop> U: full-set S: full-set Exits: (%offset + %numIterations) LoopDispositions: { %loop: Computable }
 681 ; CHECK-NEXT:    %ptr = getelementptr inbounds float, ptr %input, i32 %nexti2
 682 ; CHECK-NEXT:    --> {((4 * (sext i32 (1 + %offset) to i64))<nsw> + %input),+,4}<nw><%loop> U: full-set S: full-set Exits: ((4 * (zext i32 (-1 + %numIterations) to i64))<nuw><nsw> + (4 * (sext i32 (1 + %offset) to i64))<nsw> + %input) LoopDispositions: { %loop: Computable }
 683 ; CHECK-NEXT:  Determining loop execution counts for: @test-add-not-header7
 684 ; CHECK-NEXT:  Loop %loop: backedge-taken count is (-1 + %numIterations)
 685 ; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is i32 -1
 686 ; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is (-1 + %numIterations)
 687 ; CHECK-NEXT:  Loop %loop: Trip multiple is 1
 688 ;
 689 entry:
 690   br label %loop
 691 loop:
 692   %i = phi i32 [ %nexti, %loop.latch ], [ 0, %entry ]
 693   %i2 = phi i32 [ %nexti2, %loop.latch ], [ %offset, %entry ]
 694   br label %loop2
 695 loop2:
 696   %nexti = add nsw i32 %i, 1
 697   %nexti2 = add nsw i32 %i2, 1
 698   %ptr = getelementptr inbounds float, ptr %input, i32 %nexti2
 699   %f = load float, ptr %ptr, align 4
 700   %exitcond = icmp eq i32 %nexti, %numIterations
 701   br i1 %exitcond, label %exit, label %loop.latch
 702 loop.latch:
 703   br label %loop
 704 exit:
 705   ret void
 706 }
 707
 708 ; Variant where the load is after the exit.
 709 define void @test-add-not-header8(ptr %input, i32 %offset, i32 %numIterations) {
 710 ; CHECK-LABEL: 'test-add-not-header8'
 711 ; CHECK-NEXT:  Classifying expressions for: @test-add-not-header8
 712 ; CHECK-NEXT:    %i = phi i32 [ %nexti, %loop.latch ], [ 0, %entry ]
 713 ; CHECK-NEXT:    --> {0,+,1}<nuw><nsw><%loop> U: [0,-2147483648) S: [0,-2147483648) Exits: (-1 + %numIterations) LoopDispositions: { %loop: Computable }
 714 ; CHECK-NEXT:    %i2 = phi i32 [ %nexti2, %loop.latch ], [ %offset, %entry ]
 715 ; CHECK-NEXT:    --> {%offset,+,1}<nsw><%loop> U: full-set S: full-set Exits: (-1 + %offset + %numIterations) LoopDispositions: { %loop: Computable }
 716 ; CHECK-NEXT:    %nexti = add nsw i32 %i, 1
 717 ; CHECK-NEXT:    --> {1,+,1}<nuw><nsw><%loop> U: [1,-2147483648) S: [1,-2147483648) Exits: %numIterations LoopDispositions: { %loop: Computable }
 718 ; CHECK-NEXT:    %nexti2 = add nsw i32 %i2, 1
 719 ; CHECK-NEXT:    --> {(1 + %offset),+,1}<nw><%loop> U: full-set S: full-set Exits: (%offset + %numIterations) LoopDispositions: { %loop: Computable }
 720 ; CHECK-NEXT:    %ptr = getelementptr inbounds float, ptr %input, i32 %nexti2
 721 ; CHECK-NEXT:    --> ((4 * (sext i32 {(1 + %offset),+,1}<nw><%loop> to i64))<nsw> + %input) U: full-set S: full-set Exits: ((4 * (sext i32 (%offset + %numIterations) to i64))<nsw> + %input) LoopDispositions: { %loop: Computable }
 722 ; CHECK-NEXT:  Determining loop execution counts for: @test-add-not-header8
 723 ; CHECK-NEXT:  Loop %loop: backedge-taken count is (-1 + %numIterations)
 724 ; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is i32 -1
 725 ; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is (-1 + %numIterations)
 726 ; CHECK-NEXT:  Loop %loop: Trip multiple is 1
 727 ;
 728 entry:
 729   br label %loop
 730 loop:
 731   %i = phi i32 [ %nexti, %loop.latch ], [ 0, %entry ]
 732   %i2 = phi i32 [ %nexti2, %loop.latch ], [ %offset, %entry ]
 733   br label %loop2
 734 loop2:
 735   %nexti = add nsw i32 %i, 1
 736   %nexti2 = add nsw i32 %i2, 1
 737   %exitcond = icmp eq i32 %nexti, %numIterations
 738   br i1 %exitcond, label %exit, label %loop.latch
 739 loop.latch:
 740   %ptr = getelementptr inbounds float, ptr %input, i32 %nexti2
 741   %f = load float, ptr %ptr, align 4
 742   br label %loop
 743 exit:
 744   ret void
 745 }
 746
 747 ; The call instruction makes it not guaranteed that the add will be
 748 ; executed, since it could run forever or throw an exception, so we
 749 ; cannot assume that the UB is realized.
 750 define void @test-add-call(ptr %input, i32 %offset, i32 %numIterations) {
 751 ; CHECK-LABEL: 'test-add-call'
 752 ; CHECK-NEXT:  Classifying expressions for: @test-add-call
 753 ; CHECK-NEXT:    %i = phi i32 [ %nexti, %loop ], [ 0, %entry ]
 754 ; CHECK-NEXT:    --> {0,+,1}<nuw><nsw><%loop> U: [0,-2147483648) S: [0,-2147483648) Exits: (-1 + %numIterations) LoopDispositions: { %loop: Computable }
 755 ; CHECK-NEXT:    %index32 = add nsw i32 %i, %offset
 756 ; CHECK-NEXT:    --> {%offset,+,1}<nw><%loop> U: full-set S: full-set Exits: (-1 + %offset + %numIterations) LoopDispositions: { %loop: Computable }
 757 ; CHECK-NEXT:    %ptr = getelementptr inbounds float, ptr %input, i32 %index32
 758 ; CHECK-NEXT:    --> ((4 * (sext i32 {%offset,+,1}<nw><%loop> to i64))<nsw> + %input) U: full-set S: full-set Exits: ((4 * (sext i32 (-1 + %offset + %numIterations) to i64))<nsw> + %input) LoopDispositions: { %loop: Computable }
 759 ; CHECK-NEXT:    %nexti = add nsw i32 %i, 1
 760 ; CHECK-NEXT:    --> {1,+,1}<nuw><%loop> U: [1,0) S: [1,0) Exits: %numIterations LoopDispositions: { %loop: Computable }
 761 ; CHECK-NEXT:  Determining loop execution counts for: @test-add-call
 762 ; CHECK-NEXT:  Loop %loop: backedge-taken count is (-1 + %numIterations)
 763 ; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is i32 -1
 764 ; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is (-1 + %numIterations)
 765 ; CHECK-NEXT:  Loop %loop: Trip multiple is 1
 766 ;
 767 entry:
 768   br label %loop
 769 loop:
 770   %i = phi i32 [ %nexti, %loop ], [ 0, %entry ]
 771
 772   call void @foo()
 773   %index32 = add nsw i32 %i, %offset
 774
 775   %ptr = getelementptr inbounds float, ptr %input, i32 %index32
 776   %nexti = add nsw i32 %i, 1
 777   %f = load float, ptr %ptr, align 4
 778   %exitcond = icmp eq i32 %nexti, %numIterations
 779   br i1 %exitcond, label %exit, label %loop
 780 exit:
 781   ret void
 782 }
 783
 784 ; Same issue as test-add-call, but this time the call is between the
 785 ; producer of poison and the load that consumes it.
 786 define void @test-add-call2(ptr %input, i32 %offset, i32 %numIterations) {
 787 ; CHECK-LABEL: 'test-add-call2'
 788 ; CHECK-NEXT:  Classifying expressions for: @test-add-call2
 789 ; CHECK-NEXT:    %i = phi i32 [ %nexti, %loop ], [ 0, %entry ]
 790 ; CHECK-NEXT:    --> {0,+,1}<nuw><nsw><%loop> U: [0,-2147483648) S: [0,-2147483648) Exits: (-1 + %numIterations) LoopDispositions: { %loop: Computable }
 791 ; CHECK-NEXT:    %index32 = add nsw i32 %i, %offset
 792 ; CHECK-NEXT:    --> {%offset,+,1}<nw><%loop> U: full-set S: full-set Exits: (-1 + %offset + %numIterations) LoopDispositions: { %loop: Computable }
 793 ; CHECK-NEXT:    %ptr = getelementptr inbounds float, ptr %input, i32 %index32
 794 ; CHECK-NEXT:    --> ((4 * (sext i32 {%offset,+,1}<nw><%loop> to i64))<nsw> + %input) U: full-set S: full-set Exits: ((4 * (sext i32 (-1 + %offset + %numIterations) to i64))<nsw> + %input) LoopDispositions: { %loop: Computable }
 795 ; CHECK-NEXT:    %nexti = add nsw i32 %i, 1
 796 ; CHECK-NEXT:    --> {1,+,1}<nuw><%loop> U: [1,0) S: [1,0) Exits: %numIterations LoopDispositions: { %loop: Computable }
 797 ; CHECK-NEXT:  Determining loop execution counts for: @test-add-call2
 798 ; CHECK-NEXT:  Loop %loop: backedge-taken count is (-1 + %numIterations)
 799 ; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is i32 -1
 800 ; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is (-1 + %numIterations)
 801 ; CHECK-NEXT:  Loop %loop: Trip multiple is 1
 802 ;
 803 entry:
 804   br label %loop
 805 loop:
 806   %i = phi i32 [ %nexti, %loop ], [ 0, %entry ]
 807
 808   %index32 = add nsw i32 %i, %offset
 809
 810   %ptr = getelementptr inbounds float, ptr %input, i32 %index32
 811   %nexti = add nsw i32 %i, 1
 812   call void @foo()
 813   %f = load float, ptr %ptr, align 4
 814   %exitcond = icmp eq i32 %nexti, %numIterations
 815   br i1 %exitcond, label %exit, label %loop
 816 exit:
 817   ret void
 818 }
 819
 820 ; Any poison input makes getelementptr produce poison
 821 define void @test-gep-propagates-poison(ptr %input, i32 %offset, i32 %numIterations) {
 822 ; CHECK-LABEL: 'test-gep-propagates-poison'
 823 ; CHECK-NEXT:  Classifying expressions for: @test-gep-propagates-poison
 824 ; CHECK-NEXT:    %i = phi i32 [ %nexti, %loop ], [ 0, %entry ]
 825 ; CHECK-NEXT:    --> {0,+,1}<nuw><nsw><%loop> U: [0,-2147483648) S: [0,-2147483648) Exits: (-1 + %numIterations) LoopDispositions: { %loop: Computable }
 826 ; CHECK-NEXT:    %index32 = add nsw i32 %i, %offset
 827 ; CHECK-NEXT:    --> {%offset,+,1}<nsw><%loop> U: full-set S: full-set Exits: (-1 + %offset + %numIterations) LoopDispositions: { %loop: Computable }
 828 ; CHECK-NEXT:    %ptr = getelementptr float, ptr %input, i32 %index32
 829 ; CHECK-NEXT:    --> {((4 * (sext i32 %offset to i64))<nsw> + %input),+,4}<nw><%loop> U: full-set S: full-set Exits: ((4 * (zext i32 (-1 + %numIterations) to i64))<nuw><nsw> + (4 * (sext i32 %offset to i64))<nsw> + %input) LoopDispositions: { %loop: Computable }
 830 ; CHECK-NEXT:    %nexti = add nsw i32 %i, 1
 831 ; CHECK-NEXT:    --> {1,+,1}<nuw><nsw><%loop> U: [1,-2147483648) S: [1,-2147483648) Exits: %numIterations LoopDispositions: { %loop: Computable }
 832 ; CHECK-NEXT:  Determining loop execution counts for: @test-gep-propagates-poison
 833 ; CHECK-NEXT:  Loop %loop: backedge-taken count is (-1 + %numIterations)
 834 ; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is i32 -1
 835 ; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is (-1 + %numIterations)
 836 ; CHECK-NEXT:  Loop %loop: Trip multiple is 1
 837 ;
 838 entry:
 839   br label %loop
 840 loop:
 841   %i = phi i32 [ %nexti, %loop ], [ 0, %entry ]
 842
 843   %index32 = add nsw i32 %i, %offset
 844
 845   %ptr = getelementptr float, ptr %input, i32 %index32
 846   %nexti = add nsw i32 %i, 1
 847   %f = load float, ptr %ptr, align 4
 848   %exitcond = icmp eq i32 %nexti, %numIterations
 849   br i1 %exitcond, label %exit, label %loop
 850 exit:
 851   ret void
 852 }
 853
 854 ; Multiplication by a non-zero constant propagates poison if there is
 855 ; a nuw or nsw flag on the multiplication.
 856 define void @test-add-mul-propagates(ptr %input, i32 %offset, i32 %numIterations) {
 857 ; CHECK-LABEL: 'test-add-mul-propagates'
 858 ; CHECK-NEXT:  Classifying expressions for: @test-add-mul-propagates
 859 ; CHECK-NEXT:    %i = phi i32 [ %nexti, %loop ], [ 0, %entry ]
 860 ; CHECK-NEXT:    --> {0,+,1}<nuw><nsw><%loop> U: [0,-2147483648) S: [0,-2147483648) Exits: (-1 + %numIterations) LoopDispositions: { %loop: Computable }
 861 ; CHECK-NEXT:    %index32 = add nsw i32 %i, %offset
 862 ; CHECK-NEXT:    --> {%offset,+,1}<nsw><%loop> U: full-set S: full-set Exits: (-1 + %offset + %numIterations) LoopDispositions: { %loop: Computable }
 863 ; CHECK-NEXT:    %indexmul = mul nuw i32 %index32, 2
 864 ; CHECK-NEXT:    --> {(2 * %offset),+,2}<%loop> U: [0,-1) S: [-2147483648,2147483647) Exits: (-2 + (2 * %offset) + (2 * %numIterations)) LoopDispositions: { %loop: Computable }
 865 ; CHECK-NEXT:    %ptr = getelementptr inbounds float, ptr %input, i32 %indexmul
 866 ; CHECK-NEXT:    --> ((4 * (sext i32 {(2 * %offset),+,2}<%loop> to i64))<nsw> + %input) U: full-set S: full-set Exits: ((4 * (sext i32 (-2 + (2 * %offset) + (2 * %numIterations)) to i64))<nsw> + %input) LoopDispositions: { %loop: Computable }
 867 ; CHECK-NEXT:    %nexti = add nsw i32 %i, 1
 868 ; CHECK-NEXT:    --> {1,+,1}<nuw><nsw><%loop> U: [1,-2147483648) S: [1,-2147483648) Exits: %numIterations LoopDispositions: { %loop: Computable }
 869 ; CHECK-NEXT:  Determining loop execution counts for: @test-add-mul-propagates
 870 ; CHECK-NEXT:  Loop %loop: backedge-taken count is (-1 + %numIterations)
 871 ; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is i32 -1
 872 ; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is (-1 + %numIterations)
 873 ; CHECK-NEXT:  Loop %loop: Trip multiple is 1
 874 ;
 875 entry:
 876   br label %loop
 877 loop:
 878   %i = phi i32 [ %nexti, %loop ], [ 0, %entry ]
 879
 880   %index32 = add nsw i32 %i, %offset
 881
 882   %indexmul = mul nuw i32 %index32, 2
 883   %ptr = getelementptr inbounds float, ptr %input, i32 %indexmul
 884   %nexti = add nsw i32 %i, 1
 885   %f = load float, ptr %ptr, align 4
 886   %exitcond = icmp eq i32 %nexti, %numIterations
 887   br i1 %exitcond, label %exit, label %loop
 888 exit:
 889   ret void
 890 }
 891
 892 ; Any poison input to multiplication propages poison.
 893 define void @test-mul-propagates-poison(ptr %input, i32 %offset, i32 %numIterations) {
 894 ; CHECK-LABEL: 'test-mul-propagates-poison'
 895 ; CHECK-NEXT:  Classifying expressions for: @test-mul-propagates-poison
 896 ; CHECK-NEXT:    %i = phi i32 [ %nexti, %loop ], [ 0, %entry ]
 897 ; CHECK-NEXT:    --> {0,+,1}<nuw><nsw><%loop> U: [0,-2147483648) S: [0,-2147483648) Exits: (-1 + %numIterations) LoopDispositions: { %loop: Computable }
 898 ; CHECK-NEXT:    %index32 = add nsw i32 %i, %offset
 899 ; CHECK-NEXT:    --> {%offset,+,1}<nsw><%loop> U: full-set S: full-set Exits: (-1 + %offset + %numIterations) LoopDispositions: { %loop: Computable }
 900 ; CHECK-NEXT:    %indexmul = mul nsw i32 %index32, %offset
 901 ; CHECK-NEXT:    --> {(%offset * %offset),+,%offset}<%loop> U: full-set S: full-set Exits: ((-1 + %offset + %numIterations) * %offset) LoopDispositions: { %loop: Computable }
 902 ; CHECK-NEXT:    %ptr = getelementptr inbounds float, ptr %input, i32 %indexmul
 903 ; CHECK-NEXT:    --> ((4 * (sext i32 {(%offset * %offset),+,%offset}<%loop> to i64))<nsw> + %input) U: full-set S: full-set Exits: ((4 * (sext i32 ((-1 + %offset + %numIterations) * %offset) to i64))<nsw> + %input) LoopDispositions: { %loop: Computable }
 904 ; CHECK-NEXT:    %nexti = add nsw i32 %i, 1
 905 ; CHECK-NEXT:    --> {1,+,1}<nuw><nsw><%loop> U: [1,-2147483648) S: [1,-2147483648) Exits: %numIterations LoopDispositions: { %loop: Computable }
 906 ; CHECK-NEXT:  Determining loop execution counts for: @test-mul-propagates-poison
 907 ; CHECK-NEXT:  Loop %loop: backedge-taken count is (-1 + %numIterations)
 908 ; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is i32 -1
 909 ; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is (-1 + %numIterations)
 910 ; CHECK-NEXT:  Loop %loop: Trip multiple is 1
 911 ;
 912 entry:
 913   br label %loop
 914 loop:
 915   %i = phi i32 [ %nexti, %loop ], [ 0, %entry ]
 916
 917   %index32 = add nsw i32 %i, %offset
 918
 919   %indexmul = mul nsw i32 %index32, %offset
 920   %ptr = getelementptr inbounds float, ptr %input, i32 %indexmul
 921   %nexti = add nsw i32 %i, 1
 922   %f = load float, ptr %ptr, align 4
 923   %exitcond = icmp eq i32 %nexti, %numIterations
 924   br i1 %exitcond, label %exit, label %loop
 925 exit:
 926   ret void
 927 }
 928
 929 define void @test-mul-propagates-poison-2(ptr %input, i32 %offset, i32 %numIterations) {
 930 ; CHECK-LABEL: 'test-mul-propagates-poison-2'
 931 ; CHECK-NEXT:  Classifying expressions for: @test-mul-propagates-poison-2
 932 ; CHECK-NEXT:    %i = phi i32 [ %nexti, %loop ], [ 0, %entry ]
 933 ; CHECK-NEXT:    --> {0,+,1}<nuw><nsw><%loop> U: [0,-2147483648) S: [0,-2147483648) Exits: (-1 + %numIterations) LoopDispositions: { %loop: Computable }
 934 ; CHECK-NEXT:    %index32 = add nsw i32 %i, %offset
 935 ; CHECK-NEXT:    --> {%offset,+,1}<nsw><%loop> U: full-set S: full-set Exits: (-1 + %offset + %numIterations) LoopDispositions: { %loop: Computable }
 936 ; CHECK-NEXT:    %indexmul = mul i32 %index32, 2
 937 ; CHECK-NEXT:    --> {(2 * %offset),+,2}<%loop> U: [0,-1) S: [-2147483648,2147483647) Exits: (-2 + (2 * %offset) + (2 * %numIterations)) LoopDispositions: { %loop: Computable }
 938 ; CHECK-NEXT:    %ptr = getelementptr inbounds float, ptr %input, i32 %indexmul
 939 ; CHECK-NEXT:    --> ((4 * (sext i32 {(2 * %offset),+,2}<%loop> to i64))<nsw> + %input) U: full-set S: full-set Exits: ((4 * (sext i32 (-2 + (2 * %offset) + (2 * %numIterations)) to i64))<nsw> + %input) LoopDispositions: { %loop: Computable }
 940 ; CHECK-NEXT:    %nexti = add nsw i32 %i, 1
 941 ; CHECK-NEXT:    --> {1,+,1}<nuw><nsw><%loop> U: [1,-2147483648) S: [1,-2147483648) Exits: %numIterations LoopDispositions: { %loop: Computable }
 942 ; CHECK-NEXT:  Determining loop execution counts for: @test-mul-propagates-poison-2
 943 ; CHECK-NEXT:  Loop %loop: backedge-taken count is (-1 + %numIterations)
 944 ; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is i32 -1
 945 ; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is (-1 + %numIterations)
 946 ; CHECK-NEXT:  Loop %loop: Trip multiple is 1
 947 ;
 948 entry:
 949   br label %loop
 950 loop:
 951   %i = phi i32 [ %nexti, %loop ], [ 0, %entry ]
 952
 953   %index32 = add nsw i32 %i, %offset
 954
 955   %indexmul = mul i32 %index32, 2
 956   %ptr = getelementptr inbounds float, ptr %input, i32 %indexmul
 957   %nexti = add nsw i32 %i, 1
 958   %f = load float, ptr %ptr, align 4
 959   %exitcond = icmp eq i32 %nexti, %numIterations
 960   br i1 %exitcond, label %exit, label %loop
 961 exit:
 962   ret void
 963 }
 964
 965 ; Division by poison triggers UB.
 966 define void @test-add-div(ptr %input, i32 %offset, i32 %numIterations) {
 967 ; CHECK-LABEL: 'test-add-div'
 968 ; CHECK-NEXT:  Classifying expressions for: @test-add-div
 969 ; CHECK-NEXT:    %i = phi i32 [ %nexti, %loop ], [ 0, %entry ]
 970 ; CHECK-NEXT:    --> {0,+,1}<nuw><nsw><%loop> U: [0,-2147483648) S: [0,-2147483648) Exits: (-1 + %numIterations) LoopDispositions: { %loop: Computable }
 971 ; CHECK-NEXT:    %j = add nsw i32 %i, %offset
 972 ; CHECK-NEXT:    --> {%offset,+,1}<nsw><%loop> U: full-set S: full-set Exits: (-1 + %offset + %numIterations) LoopDispositions: { %loop: Computable }
 973 ; CHECK-NEXT:    %q = sdiv i32 %numIterations, %j
 974 ; CHECK-NEXT:    --> %q U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
 975 ; CHECK-NEXT:    %nexti = add nsw i32 %i, 1
 976 ; CHECK-NEXT:    --> {1,+,1}<nuw><nsw><%loop> U: [1,-2147483648) S: [1,-2147483648) Exits: %numIterations LoopDispositions: { %loop: Computable }
 977 ; CHECK-NEXT:  Determining loop execution counts for: @test-add-div
 978 ; CHECK-NEXT:  Loop %loop: backedge-taken count is (-1 + %numIterations)
 979 ; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is i32 -1
 980 ; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is (-1 + %numIterations)
 981 ; CHECK-NEXT:  Loop %loop: Trip multiple is 1
 982 ;
 983 entry:
 984   br label %loop
 985 loop:
 986   %i = phi i32 [ %nexti, %loop ], [ 0, %entry ]
 987
 988   %j = add nsw i32 %i, %offset
 989
 990   %q = sdiv i32 %numIterations, %j
 991   %nexti = add nsw i32 %i, 1
 992   %exitcond = icmp eq i32 %nexti, %numIterations
 993   br i1 %exitcond, label %exit, label %loop
 994 exit:
 995   ret void
 996 }
 997
 998 ; Remainder of poison by non-poison divisor does not trigger UB.
 999 define void @test-add-div2(ptr %input, i32 %offset, i32 %numIterations) {
1000 ; CHECK-LABEL: 'test-add-div2'
1001 ; CHECK-NEXT:  Classifying expressions for: @test-add-div2
1002 ; CHECK-NEXT:    %i = phi i32 [ %nexti, %loop ], [ 0, %entry ]
1003 ; CHECK-NEXT:    --> {0,+,1}<nuw><nsw><%loop> U: [0,-2147483648) S: [0,-2147483648) Exits: (-1 + %numIterations) LoopDispositions: { %loop: Computable }
1004 ; CHECK-NEXT:    %j = add nsw i32 %i, %offset
1005 ; CHECK-NEXT:    --> {%offset,+,1}<nw><%loop> U: full-set S: full-set Exits: (-1 + %offset + %numIterations) LoopDispositions: { %loop: Computable }
1006 ; CHECK-NEXT:    %q = sdiv i32 %j, %numIterations
1007 ; CHECK-NEXT:    --> %q U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
1008 ; CHECK-NEXT:    %nexti = add nsw i32 %i, 1
1009 ; CHECK-NEXT:    --> {1,+,1}<nuw><nsw><%loop> U: [1,-2147483648) S: [1,-2147483648) Exits: %numIterations LoopDispositions: { %loop: Computable }
1010 ; CHECK-NEXT:  Determining loop execution counts for: @test-add-div2
1011 ; CHECK-NEXT:  Loop %loop: backedge-taken count is (-1 + %numIterations)
1012 ; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is i32 -1
1013 ; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is (-1 + %numIterations)
1014 ; CHECK-NEXT:  Loop %loop: Trip multiple is 1
1015 ;
1016 entry:
1017   br label %loop
1018 loop:
1019   %i = phi i32 [ %nexti, %loop ], [ 0, %entry ]
1020
1021   %j = add nsw i32 %i, %offset
1022
1023   %q = sdiv i32 %j, %numIterations
1024   %nexti = add nsw i32 %i, 1
1025   %exitcond = icmp eq i32 %nexti, %numIterations
1026   br i1 %exitcond, label %exit, label %loop
1027 exit:
1028   ret void
1029 }
1030
1031 ; Store to poison address triggers UB.
1032 define void @test-add-store(ptr %input, i32 %offset, i32 %numIterations) {
1033 ; CHECK-LABEL: 'test-add-store'
1034 ; CHECK-NEXT:  Classifying expressions for: @test-add-store
1035 ; CHECK-NEXT:    %i = phi i32 [ %nexti, %loop ], [ 0, %entry ]
1036 ; CHECK-NEXT:    --> {0,+,1}<nuw><nsw><%loop> U: [0,-2147483648) S: [0,-2147483648) Exits: (-1 + %numIterations) LoopDispositions: { %loop: Computable }
1037 ; CHECK-NEXT:    %index32 = add nsw i32 %i, %offset
1038 ; CHECK-NEXT:    --> {%offset,+,1}<nsw><%loop> U: full-set S: full-set Exits: (-1 + %offset + %numIterations) LoopDispositions: { %loop: Computable }
1039 ; CHECK-NEXT:    %ptr = getelementptr inbounds float, ptr %input, i32 %index32
1040 ; CHECK-NEXT:    --> {((4 * (sext i32 %offset to i64))<nsw> + %input),+,4}<nw><%loop> U: full-set S: full-set Exits: ((4 * (zext i32 (-1 + %numIterations) to i64))<nuw><nsw> + (4 * (sext i32 %offset to i64))<nsw> + %input) LoopDispositions: { %loop: Computable }
1041 ; CHECK-NEXT:    %nexti = add nsw i32 %i, 1
1042 ; CHECK-NEXT:    --> {1,+,1}<nuw><nsw><%loop> U: [1,-2147483648) S: [1,-2147483648) Exits: %numIterations LoopDispositions: { %loop: Computable }
1043 ; CHECK-NEXT:  Determining loop execution counts for: @test-add-store
1044 ; CHECK-NEXT:  Loop %loop: backedge-taken count is (-1 + %numIterations)
1045 ; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is i32 -1
1046 ; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is (-1 + %numIterations)
1047 ; CHECK-NEXT:  Loop %loop: Trip multiple is 1
1048 ;
1049 entry:
1050   br label %loop
1051 loop:
1052   %i = phi i32 [ %nexti, %loop ], [ 0, %entry ]
1053
1054   %index32 = add nsw i32 %i, %offset
1055
1056   %ptr = getelementptr inbounds float, ptr %input, i32 %index32
1057   %nexti = add nsw i32 %i, 1
1058   store float 1.0, ptr %ptr, align 4
1059   %exitcond = icmp eq i32 %nexti, %numIterations
1060   br i1 %exitcond, label %exit, label %loop
1061 exit:
1062   ret void
1063 }
1064
1065 ; Three sequential adds where the middle add should have nsw. There is
1066 ; a special case for sequential adds and this test covers that. We have to
1067 ; put the final add first in the program since otherwise the special case
1068 ; is not triggered, hence the strange basic block ordering.
1069 define void @test-add-twice(ptr %input, i32 %offset, i32 %numIterations) {
1070 ; CHECK-LABEL: 'test-add-twice'
1071 ; CHECK-NEXT:  Classifying expressions for: @test-add-twice
1072 ; CHECK-NEXT:    %seq = add nuw nsw i32 %index32, 1
1073 ; CHECK-NEXT:    --> {(2 + %offset),+,1}<nw><%loop> U: full-set S: full-set Exits: (1 + %offset + %numIterations) LoopDispositions: { %loop: Computable }
1074 ; CHECK-NEXT:    %i = phi i32 [ %nexti, %loop2 ], [ 0, %entry ]
1075 ; CHECK-NEXT:    --> {0,+,1}<nuw><nsw><%loop> U: [0,-2147483648) S: [0,-2147483648) Exits: (-1 + %numIterations) LoopDispositions: { %loop: Computable }
1076 ; CHECK-NEXT:    %j = add nsw i32 %i, 1
1077 ; CHECK-NEXT:    --> {1,+,1}<nuw><nsw><%loop> U: [1,-2147483648) S: [1,-2147483648) Exits: %numIterations LoopDispositions: { %loop: Computable }
1078 ; CHECK-NEXT:    %index32 = add nsw i32 %j, %offset
1079 ; CHECK-NEXT:    --> {(1 + %offset)<nsw>,+,1}<nsw><%loop> U: [-2147483647,-2147483648) S: [-2147483647,-2147483648) Exits: (%offset + %numIterations) LoopDispositions: { %loop: Computable }
1080 ; CHECK-NEXT:    %ptr = getelementptr inbounds float, ptr %input, i32 %index32
1081 ; CHECK-NEXT:    --> {(4 + (4 * (sext i32 %offset to i64))<nsw> + %input),+,4}<nw><%loop> U: full-set S: full-set Exits: (4 + (4 * (zext i32 (-1 + %numIterations) to i64))<nuw><nsw> + (4 * (sext i32 %offset to i64))<nsw> + %input) LoopDispositions: { %loop: Computable }
1082 ; CHECK-NEXT:    %nexti = add nsw i32 %i, 1
1083 ; CHECK-NEXT:    --> {1,+,1}<nuw><nsw><%loop> U: [1,-2147483648) S: [1,-2147483648) Exits: %numIterations LoopDispositions: { %loop: Computable }
1084 ; CHECK-NEXT:  Determining loop execution counts for: @test-add-twice
1085 ; CHECK-NEXT:  Loop %loop: backedge-taken count is (-1 + %numIterations)
1086 ; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is i32 -1
1087 ; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is (-1 + %numIterations)
1088 ; CHECK-NEXT:  Loop %loop: Trip multiple is 1
1089 ;
1090 entry:
1091   br label %loop
1092 loop2:
1093   %seq = add nsw nuw i32 %index32, 1
1094   %exitcond = icmp eq i32 %nexti, %numIterations
1095   br i1 %exitcond, label %exit, label %loop
1096
1097 loop:
1098   %i = phi i32 [ %nexti, %loop2 ], [ 0, %entry ]
1099
1100   %j = add nsw i32 %i, 1
1101   %index32 = add nsw i32 %j, %offset
1102
1103   %ptr = getelementptr inbounds float, ptr %input, i32 %index32
1104   %nexti = add nsw i32 %i, 1
1105   store float 1.0, ptr %ptr, align 4
1106   br label %loop2
1107 exit:
1108   ret void
1109 }
1110
1111 ; Example where a mul should get the nsw flag, so that a sext can be
1112 ; distributed over the mul.
1113 define void @test-mul-nsw(ptr %input, i32 %stride, i32 %numIterations) {
1114 ; CHECK-LABEL: 'test-mul-nsw'
1115 ; CHECK-NEXT:  Classifying expressions for: @test-mul-nsw
1116 ; CHECK-NEXT:    %i = phi i32 [ %nexti, %loop ], [ 0, %entry ]
1117 ; CHECK-NEXT:    --> {0,+,1}<nuw><nsw><%loop> U: [0,-2147483648) S: [0,-2147483648) Exits: (-1 + %numIterations) LoopDispositions: { %loop: Computable }
1118 ; CHECK-NEXT:    %index32 = mul nsw i32 %i, %stride
1119 ; CHECK-NEXT:    --> {0,+,%stride}<nsw><%loop> U: full-set S: full-set Exits: ((-1 + %numIterations) * %stride) LoopDispositions: { %loop: Computable }
1120 ; CHECK-NEXT:    %index64 = sext i32 %index32 to i64
1121 ; CHECK-NEXT:    --> {0,+,(sext i32 %stride to i64)}<nsw><%loop> U: [-9223372034707292160,9223372030412324866) S: [-9223372034707292160,9223372030412324866) Exits: ((zext i32 (-1 + %numIterations) to i64) * (sext i32 %stride to i64)) LoopDispositions: { %loop: Computable }
1122 ; CHECK-NEXT:    %ptr = getelementptr inbounds float, ptr %input, i64 %index64
1123 ; CHECK-NEXT:    --> {%input,+,(4 * (sext i32 %stride to i64))<nsw>}<nw><%loop> U: full-set S: full-set Exits: ((4 * (zext i32 (-1 + %numIterations) to i64) * (sext i32 %stride to i64)) + %input) LoopDispositions: { %loop: Computable }
1124 ; CHECK-NEXT:    %nexti = add nsw i32 %i, 1
1125 ; CHECK-NEXT:    --> {1,+,1}<nuw><nsw><%loop> U: [1,-2147483648) S: [1,-2147483648) Exits: %numIterations LoopDispositions: { %loop: Computable }
1126 ; CHECK-NEXT:  Determining loop execution counts for: @test-mul-nsw
1127 ; CHECK-NEXT:  Loop %loop: backedge-taken count is (-1 + %numIterations)
1128 ; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is i32 -1
1129 ; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is (-1 + %numIterations)
1130 ; CHECK-NEXT:  Loop %loop: Trip multiple is 1
1131 ;
1132 entry:
1133   br label %loop
1134 loop:
1135   %i = phi i32 [ %nexti, %loop ], [ 0, %entry ]
1136
1137   %index32 = mul nsw i32 %i, %stride
1138
1139   %index64 = sext i32 %index32 to i64
1140
1141   %ptr = getelementptr inbounds float, ptr %input, i64 %index64
1142   %nexti = add nsw i32 %i, 1
1143   %f = load float, ptr %ptr, align 4
1144   %exitcond = icmp eq i32 %nexti, %numIterations
1145   br i1 %exitcond, label %exit, label %loop
1146 exit:
1147   ret void
1148 }
1149
1150 ; Example where a mul should get the nuw flag.
1151 define void @test-mul-nuw(ptr %input, i32 %stride, i32 %numIterations) {
1152 ; CHECK-LABEL: 'test-mul-nuw'
1153 ; CHECK-NEXT:  Classifying expressions for: @test-mul-nuw
1154 ; CHECK-NEXT:    %i = phi i32 [ %nexti, %loop ], [ 0, %entry ]
1155 ; CHECK-NEXT:    --> {0,+,1}<nuw><%loop> U: full-set S: full-set Exits: (-1 + %numIterations) LoopDispositions: { %loop: Computable }
1156 ; CHECK-NEXT:    %index32 = mul nuw i32 %i, %stride
1157 ; CHECK-NEXT:    --> {0,+,%stride}<nuw><%loop> U: full-set S: full-set Exits: ((-1 + %numIterations) * %stride) LoopDispositions: { %loop: Computable }
1158 ; CHECK-NEXT:    %ptr = getelementptr inbounds float, ptr %input, i32 %index32
1159 ; CHECK-NEXT:    --> ((4 * (sext i32 {0,+,%stride}<nuw><%loop> to i64))<nsw> + %input) U: full-set S: full-set Exits: ((4 * (sext i32 ((-1 + %numIterations) * %stride) to i64))<nsw> + %input) LoopDispositions: { %loop: Computable }
1160 ; CHECK-NEXT:    %nexti = add nuw i32 %i, 1
1161 ; CHECK-NEXT:    --> {1,+,1}<nuw><%loop> U: [1,0) S: [1,0) Exits: %numIterations LoopDispositions: { %loop: Computable }
1162 ; CHECK-NEXT:  Determining loop execution counts for: @test-mul-nuw
1163 ; CHECK-NEXT:  Loop %loop: backedge-taken count is (-1 + %numIterations)
1164 ; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is i32 -1
1165 ; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is (-1 + %numIterations)
1166 ; CHECK-NEXT:  Loop %loop: Trip multiple is 1
1167 ;
1168 entry:
1169   br label %loop
1170 loop:
1171   %i = phi i32 [ %nexti, %loop ], [ 0, %entry ]
1172
1173   %index32 = mul nuw i32 %i, %stride
1174
1175   %ptr = getelementptr inbounds float, ptr %input, i32 %index32
1176   %nexti = add nuw i32 %i, 1
1177   %f = load float, ptr %ptr, align 4
1178   %exitcond = icmp eq i32 %nexti, %numIterations
1179   br i1 %exitcond, label %exit, label %loop
1180
1181 exit:
1182   ret void
1183 }
1184
1185 ; Example where a shl should get the nsw flag, so that a sext can be
1186 ; distributed over the shl.
1187 define void @test-shl-nsw(ptr %input, i32 %start, i32 %numIterations) {
1188 ; CHECK-LABEL: 'test-shl-nsw'
1189 ; CHECK-NEXT:  Classifying expressions for: @test-shl-nsw
1190 ; CHECK-NEXT:    %i = phi i32 [ %nexti, %loop ], [ %start, %entry ]
1191 ; CHECK-NEXT:    --> {%start,+,1}<nsw><%loop> U: full-set S: full-set Exits: (-1 + %numIterations) LoopDispositions: { %loop: Computable }
1192 ; CHECK-NEXT:    %index32 = shl nsw i32 %i, 8
1193 ; CHECK-NEXT:    --> {(256 * %start),+,256}<%loop> U: [0,-255) S: [-2147483648,2147483393) Exits: (-256 + (256 * %numIterations)) LoopDispositions: { %loop: Computable }
1194 ; CHECK-NEXT:    %index64 = sext i32 %index32 to i64
1195 ; CHECK-NEXT:    --> (sext i32 {(256 * %start),+,256}<%loop> to i64) U: [0,-255) S: [-2147483648,2147483393) Exits: (sext i32 (-256 + (256 * %numIterations)) to i64) LoopDispositions: { %loop: Computable }
1196 ; CHECK-NEXT:    %ptr = getelementptr inbounds float, ptr %input, i64 %index64
1197 ; CHECK-NEXT:    --> ((4 * (sext i32 {(256 * %start),+,256}<%loop> to i64))<nsw> + %input) U: full-set S: full-set Exits: ((4 * (sext i32 (-256 + (256 * %numIterations)) to i64))<nsw> + %input) LoopDispositions: { %loop: Computable }
1198 ; CHECK-NEXT:    %nexti = add nsw i32 %i, 1
1199 ; CHECK-NEXT:    --> {(1 + %start)<nsw>,+,1}<nsw><%loop> U: [-2147483647,-2147483648) S: [-2147483647,-2147483648) Exits: %numIterations LoopDispositions: { %loop: Computable }
1200 ; CHECK-NEXT:  Determining loop execution counts for: @test-shl-nsw
1201 ; CHECK-NEXT:  Loop %loop: backedge-taken count is (-1 + (-1 * %start) + %numIterations)
1202 ; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is i32 -1
1203 ; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is (-1 + (-1 * %start) + %numIterations)
1204 ; CHECK-NEXT:  Loop %loop: Trip multiple is 1
1205 ;
1206 entry:
1207   br label %loop
1208 loop:
1209   %i = phi i32 [ %nexti, %loop ], [ %start, %entry ]
1210
1211   %index32 = shl nsw i32 %i, 8
1212
1213   %index64 = sext i32 %index32 to i64
1214
1215   %ptr = getelementptr inbounds float, ptr %input, i64 %index64
1216   %nexti = add nsw i32 %i, 1
1217   %f = load float, ptr %ptr, align 4
1218   %exitcond = icmp eq i32 %nexti, %numIterations
1219   br i1 %exitcond, label %exit, label %loop
1220 exit:
1221   ret void
1222 }
1223
1224 ; Example where a shl should get the nuw flag
1225 define void @test-shl-nuw-edgecase(ptr %input, i32 %start, i32 %numIterations) {
1226 ; CHECK-LABEL: 'test-shl-nuw-edgecase'
1227 ; CHECK-NEXT:  Classifying expressions for: @test-shl-nuw-edgecase
1228 ; CHECK-NEXT:    %i = phi i32 [ %nexti, %loop ], [ %start, %entry ]
1229 ; CHECK-NEXT:    --> {%start,+,1}<nsw><%loop> U: full-set S: full-set Exits: (-1 + %numIterations) LoopDispositions: { %loop: Computable }
1230 ; CHECK-NEXT:    %index32 = shl nuw i32 %i, 31
1231 ; CHECK-NEXT:    --> {(-2147483648 * %start),+,-2147483648}<%loop> U: [0,-2147483647) S: [-2147483648,1) Exits: (-2147483648 + (-2147483648 * %numIterations)) LoopDispositions: { %loop: Computable }
1232 ; CHECK-NEXT:    %index64 = sext i32 %index32 to i64
1233 ; CHECK-NEXT:    --> (sext i32 {(-2147483648 * %start),+,-2147483648}<%loop> to i64) U: [0,-2147483647) S: [-2147483648,1) Exits: (sext i32 (-2147483648 + (-2147483648 * %numIterations)) to i64) LoopDispositions: { %loop: Computable }
1234 ; CHECK-NEXT:    %ptr = getelementptr inbounds float, ptr %input, i64 %index64
1235 ; CHECK-NEXT:    --> ((4 * (sext i32 {(-2147483648 * %start),+,-2147483648}<%loop> to i64))<nsw> + %input) U: full-set S: full-set Exits: ((4 * (sext i32 (-2147483648 + (-2147483648 * %numIterations)) to i64))<nsw> + %input) LoopDispositions: { %loop: Computable }
1236 ; CHECK-NEXT:    %nexti = add nsw i32 %i, 1
1237 ; CHECK-NEXT:    --> {(1 + %start)<nsw>,+,1}<nsw><%loop> U: [-2147483647,-2147483648) S: [-2147483647,-2147483648) Exits: %numIterations LoopDispositions: { %loop: Computable }
1238 ; CHECK-NEXT:  Determining loop execution counts for: @test-shl-nuw-edgecase
1239 ; CHECK-NEXT:  Loop %loop: backedge-taken count is (-1 + (-1 * %start) + %numIterations)
1240 ; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is i32 -1
1241 ; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is (-1 + (-1 * %start) + %numIterations)
1242 ; CHECK-NEXT:  Loop %loop: Trip multiple is 1
1243 ;
1244 entry:
1245   br label %loop
1246 loop:
1247   %i = phi i32 [ %nexti, %loop ], [ %start, %entry ]
1248
1249   %index32 = shl nuw i32 %i, 31
1250
1251   %index64 = sext i32 %index32 to i64
1252
1253   %ptr = getelementptr inbounds float, ptr %input, i64 %index64
1254   %nexti = add nsw i32 %i, 1
1255   %f = load float, ptr %ptr, align 4
1256   %exitcond = icmp eq i32 %nexti, %numIterations
1257   br i1 %exitcond, label %exit, label %loop
1258 exit:
1259   ret void
1260 }
1261
1262 ; Example where a shl should get the nuw flag
1263 define void @test-shl-nuw-nsw(ptr %input, i32 %start, i32 %numIterations) {
1264 ; CHECK-LABEL: 'test-shl-nuw-nsw'
1265 ; CHECK-NEXT:  Classifying expressions for: @test-shl-nuw-nsw
1266 ; CHECK-NEXT:    %i = phi i32 [ %nexti, %loop ], [ %start, %entry ]
1267 ; CHECK-NEXT:    --> {%start,+,1}<nsw><%loop> U: full-set S: full-set Exits: (-1 + %numIterations) LoopDispositions: { %loop: Computable }
1268 ; CHECK-NEXT:    %index32 = shl nuw nsw i32 %i, 31
1269 ; CHECK-NEXT:    --> {(-2147483648 * %start),+,-2147483648}<%loop> U: [0,-2147483647) S: [-2147483648,1) Exits: (-2147483648 + (-2147483648 * %numIterations)) LoopDispositions: { %loop: Computable }
1270 ; CHECK-NEXT:    %index64 = sext i32 %index32 to i64
1271 ; CHECK-NEXT:    --> (sext i32 {(-2147483648 * %start),+,-2147483648}<%loop> to i64) U: [0,-2147483647) S: [-2147483648,1) Exits: (sext i32 (-2147483648 + (-2147483648 * %numIterations)) to i64) LoopDispositions: { %loop: Computable }
1272 ; CHECK-NEXT:    %ptr = getelementptr inbounds float, ptr %input, i64 %index64
1273 ; CHECK-NEXT:    --> ((4 * (sext i32 {(-2147483648 * %start),+,-2147483648}<%loop> to i64))<nsw> + %input) U: full-set S: full-set Exits: ((4 * (sext i32 (-2147483648 + (-2147483648 * %numIterations)) to i64))<nsw> + %input) LoopDispositions: { %loop: Computable }
1274 ; CHECK-NEXT:    %nexti = add nsw i32 %i, 1
1275 ; CHECK-NEXT:    --> {(1 + %start)<nsw>,+,1}<nsw><%loop> U: [-2147483647,-2147483648) S: [-2147483647,-2147483648) Exits: %numIterations LoopDispositions: { %loop: Computable }
1276 ; CHECK-NEXT:  Determining loop execution counts for: @test-shl-nuw-nsw
1277 ; CHECK-NEXT:  Loop %loop: backedge-taken count is (-1 + (-1 * %start) + %numIterations)
1278 ; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is i32 -1
1279 ; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is (-1 + (-1 * %start) + %numIterations)
1280 ; CHECK-NEXT:  Loop %loop: Trip multiple is 1
1281 ;
1282 entry:
1283   br label %loop
1284 loop:
1285   %i = phi i32 [ %nexti, %loop ], [ %start, %entry ]
1286
1287   %index32 = shl nuw nsw i32 %i, 31
1288
1289   %index64 = sext i32 %index32 to i64
1290
1291   %ptr = getelementptr inbounds float, ptr %input, i64 %index64
1292   %nexti = add nsw i32 %i, 1
1293   %f = load float, ptr %ptr, align 4
1294   %exitcond = icmp eq i32 %nexti, %numIterations
1295   br i1 %exitcond, label %exit, label %loop
1296 exit:
1297   ret void
1298 }
1299
1300 ; Example where a shl should not get the nsw flag
1301 define void @test-shl-no-nsw(ptr %input, i32 %start, i32 %numIterations) {
1302 ; CHECK-LABEL: 'test-shl-no-nsw'
1303 ; CHECK-NEXT:  Classifying expressions for: @test-shl-no-nsw
1304 ; CHECK-NEXT:    %i = phi i32 [ %nexti, %loop ], [ %start, %entry ]
1305 ; CHECK-NEXT:    --> {%start,+,1}<nsw><%loop> U: full-set S: full-set Exits: (-1 + %numIterations) LoopDispositions: { %loop: Computable }
1306 ; CHECK-NEXT:    %index32 = shl nsw i32 %i, 31
1307 ; CHECK-NEXT:    --> {(-2147483648 * %start),+,-2147483648}<%loop> U: [0,-2147483647) S: [-2147483648,1) Exits: (-2147483648 + (-2147483648 * %numIterations)) LoopDispositions: { %loop: Computable }
1308 ; CHECK-NEXT:    %index64 = sext i32 %index32 to i64
1309 ; CHECK-NEXT:    --> (sext i32 {(-2147483648 * %start),+,-2147483648}<%loop> to i64) U: [0,-2147483647) S: [-2147483648,1) Exits: (sext i32 (-2147483648 + (-2147483648 * %numIterations)) to i64) LoopDispositions: { %loop: Computable }
1310 ; CHECK-NEXT:    %ptr = getelementptr inbounds float, ptr %input, i64 %index64
1311 ; CHECK-NEXT:    --> ((4 * (sext i32 {(-2147483648 * %start),+,-2147483648}<%loop> to i64))<nsw> + %input) U: full-set S: full-set Exits: ((4 * (sext i32 (-2147483648 + (-2147483648 * %numIterations)) to i64))<nsw> + %input) LoopDispositions: { %loop: Computable }
1312 ; CHECK-NEXT:    %nexti = add nsw i32 %i, 1
1313 ; CHECK-NEXT:    --> {(1 + %start)<nsw>,+,1}<nsw><%loop> U: [-2147483647,-2147483648) S: [-2147483647,-2147483648) Exits: %numIterations LoopDispositions: { %loop: Computable }
1314 ; CHECK-NEXT:  Determining loop execution counts for: @test-shl-no-nsw
1315 ; CHECK-NEXT:  Loop %loop: backedge-taken count is (-1 + (-1 * %start) + %numIterations)
1316 ; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is i32 -1
1317 ; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is (-1 + (-1 * %start) + %numIterations)
1318 ; CHECK-NEXT:  Loop %loop: Trip multiple is 1
1319 ;
1320 entry:
1321   br label %loop
1322 loop:
1323   %i = phi i32 [ %nexti, %loop ], [ %start, %entry ]
1324
1325   %index32 = shl nsw i32 %i, 31
1326
1327   %index64 = sext i32 %index32 to i64
1328
1329   %ptr = getelementptr inbounds float, ptr %input, i64 %index64
1330   %nexti = add nsw i32 %i, 1
1331   %f = load float, ptr %ptr, align 4
1332   %exitcond = icmp eq i32 %nexti, %numIterations
1333   br i1 %exitcond, label %exit, label %loop
1334 exit:
1335   ret void
1336 }
1337
1338 ; Example where a shl should get the nsw flag.
1339 define void @test-shl-nsw-edgecase(ptr %input, i32 %start, i32 %numIterations) {
1340 ; CHECK-LABEL: 'test-shl-nsw-edgecase'
1341 ; CHECK-NEXT:  Classifying expressions for: @test-shl-nsw-edgecase
1342 ; CHECK-NEXT:    %i = phi i32 [ %nexti, %loop ], [ %start, %entry ]
1343 ; CHECK-NEXT:    --> {%start,+,1}<nsw><%loop> U: full-set S: full-set Exits: (-1 + %numIterations) LoopDispositions: { %loop: Computable }
1344 ; CHECK-NEXT:    %index32 = shl nsw i32 %i, 30
1345 ; CHECK-NEXT:    --> {(1073741824 * %start),+,1073741824}<%loop> U: [0,-1073741823) S: [-2147483648,1073741825) Exits: (-1073741824 + (1073741824 * %numIterations)) LoopDispositions: { %loop: Computable }
1346 ; CHECK-NEXT:    %index64 = sext i32 %index32 to i64
1347 ; CHECK-NEXT:    --> (sext i32 {(1073741824 * %start),+,1073741824}<%loop> to i64) U: [0,-1073741823) S: [-2147483648,1073741825) Exits: (sext i32 (-1073741824 + (1073741824 * %numIterations)) to i64) LoopDispositions: { %loop: Computable }
1348 ; CHECK-NEXT:    %ptr = getelementptr inbounds float, ptr %input, i64 %index64
1349 ; CHECK-NEXT:    --> ((4 * (sext i32 {(1073741824 * %start),+,1073741824}<%loop> to i64))<nsw> + %input) U: full-set S: full-set Exits: ((4 * (sext i32 (-1073741824 + (1073741824 * %numIterations)) to i64))<nsw> + %input) LoopDispositions: { %loop: Computable }
1350 ; CHECK-NEXT:    %nexti = add nsw i32 %i, 1
1351 ; CHECK-NEXT:    --> {(1 + %start)<nsw>,+,1}<nsw><%loop> U: [-2147483647,-2147483648) S: [-2147483647,-2147483648) Exits: %numIterations LoopDispositions: { %loop: Computable }
1352 ; CHECK-NEXT:  Determining loop execution counts for: @test-shl-nsw-edgecase
1353 ; CHECK-NEXT:  Loop %loop: backedge-taken count is (-1 + (-1 * %start) + %numIterations)
1354 ; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is i32 -1
1355 ; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is (-1 + (-1 * %start) + %numIterations)
1356 ; CHECK-NEXT:  Loop %loop: Trip multiple is 1
1357 ;
1358 entry:
1359   br label %loop
1360 loop:
1361   %i = phi i32 [ %nexti, %loop ], [ %start, %entry ]
1362
1363   %index32 = shl nsw i32 %i, 30
1364
1365   %index64 = sext i32 %index32 to i64
1366
1367   %ptr = getelementptr inbounds float, ptr %input, i64 %index64
1368   %nexti = add nsw i32 %i, 1
1369   %f = load float, ptr %ptr, align 4
1370   %exitcond = icmp eq i32 %nexti, %numIterations
1371   br i1 %exitcond, label %exit, label %loop
1372 exit:
1373   ret void
1374 }
1375
1376 ; Example where a shl should get the nuw flag.
1377 define void @test-shl-nuw(ptr %input, i32 %numIterations) {
1378 ; CHECK-LABEL: 'test-shl-nuw'
1379 ; CHECK-NEXT:  Classifying expressions for: @test-shl-nuw
1380 ; CHECK-NEXT:    %i = phi i32 [ %nexti, %loop ], [ 0, %entry ]
1381 ; CHECK-NEXT:    --> {0,+,1}<nuw><%loop> U: full-set S: full-set Exits: (-1 + %numIterations) LoopDispositions: { %loop: Computable }
1382 ; CHECK-NEXT:    %index32 = shl nuw i32 %i, 9
1383 ; CHECK-NEXT:    --> {0,+,512}<nuw><%loop> U: [0,-511) S: [-2147483648,2147483137) Exits: (-512 + (512 * %numIterations)) LoopDispositions: { %loop: Computable }
1384 ; CHECK-NEXT:    %ptr = getelementptr inbounds float, ptr %input, i32 %index32
1385 ; CHECK-NEXT:    --> ((4 * (sext i32 {0,+,512}<nuw><%loop> to i64))<nsw> + %input) U: full-set S: full-set Exits: ((4 * (sext i32 (-512 + (512 * %numIterations)) to i64))<nsw> + %input) LoopDispositions: { %loop: Computable }
1386 ; CHECK-NEXT:    %nexti = add nuw i32 %i, 1
1387 ; CHECK-NEXT:    --> {1,+,1}<nuw><%loop> U: [1,0) S: [1,0) Exits: %numIterations LoopDispositions: { %loop: Computable }
1388 ; CHECK-NEXT:  Determining loop execution counts for: @test-shl-nuw
1389 ; CHECK-NEXT:  Loop %loop: backedge-taken count is (-1 + %numIterations)
1390 ; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is i32 -1
1391 ; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is (-1 + %numIterations)
1392 ; CHECK-NEXT:  Loop %loop: Trip multiple is 1
1393 ;
1394 entry:
1395   br label %loop
1396 loop:
1397   %i = phi i32 [ %nexti, %loop ], [ 0, %entry ]
1398
1399   %index32 = shl nuw i32 %i, 9
1400
1401   %ptr = getelementptr inbounds float, ptr %input, i32 %index32
1402   %nexti = add nuw i32 %i, 1
1403   %f = load float, ptr %ptr, align 4
1404   %exitcond = icmp eq i32 %nexti, %numIterations
1405   br i1 %exitcond, label %exit, label %loop
1406
1407 exit:
1408   ret void
1409 }
1410
1411 ; Example where a sub should *not* get the nsw flag, because of how
1412 ; scalar evolution represents A - B as A + (-B) and -B can wrap even
1413 ; in cases where A - B does not.
1414 define void @test-sub-no-nsw(ptr %input, i32 %start, i32 %sub, i32 %numIterations) {
1415 ; CHECK-LABEL: 'test-sub-no-nsw'
1416 ; CHECK-NEXT:  Classifying expressions for: @test-sub-no-nsw
1417 ; CHECK-NEXT:    %i = phi i32 [ %nexti, %loop ], [ %start, %entry ]
1418 ; CHECK-NEXT:    --> {%start,+,1}<nsw><%loop> U: full-set S: full-set Exits: (-1 + %numIterations) LoopDispositions: { %loop: Computable }
1419 ; CHECK-NEXT:    %index32 = sub nsw i32 %i, %sub
1420 ; CHECK-NEXT:    --> {((-1 * %sub) + %start),+,1}<nw><%loop> U: full-set S: full-set Exits: (-1 + (-1 * %sub) + %numIterations) LoopDispositions: { %loop: Computable }
1421 ; CHECK-NEXT:    %index64 = sext i32 %index32 to i64
1422 ; CHECK-NEXT:    --> {((sext i32 %start to i64) + (-1 * (sext i32 %sub to i64))<nsw>)<nsw>,+,1}<nsw><%loop> U: [-4294967295,8589934591) S: [-4294967295,8589934591) Exits: ((zext i32 (-1 + (-1 * %start) + %numIterations) to i64) + (sext i32 %start to i64) + (-1 * (sext i32 %sub to i64))<nsw>) LoopDispositions: { %loop: Computable }
1423 ; CHECK-NEXT:    %ptr = getelementptr inbounds float, ptr %input, i64 %index64
1424 ; CHECK-NEXT:    --> {((4 * (sext i32 %start to i64))<nsw> + (-4 * (sext i32 %sub to i64))<nsw> + %input),+,4}<nw><%loop> U: full-set S: full-set Exits: ((4 * (zext i32 (-1 + (-1 * %start) + %numIterations) to i64))<nuw><nsw> + (4 * (sext i32 %start to i64))<nsw> + (-4 * (sext i32 %sub to i64))<nsw> + %input) LoopDispositions: { %loop: Computable }
1425 ; CHECK-NEXT:    %nexti = add nsw i32 %i, 1
1426 ; CHECK-NEXT:    --> {(1 + %start)<nsw>,+,1}<nsw><%loop> U: [-2147483647,-2147483648) S: [-2147483647,-2147483648) Exits: %numIterations LoopDispositions: { %loop: Computable }
1427 ; CHECK-NEXT:  Determining loop execution counts for: @test-sub-no-nsw
1428 ; CHECK-NEXT:  Loop %loop: backedge-taken count is (-1 + (-1 * %start) + %numIterations)
1429 ; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is i32 -1
1430 ; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is (-1 + (-1 * %start) + %numIterations)
1431 ; CHECK-NEXT:  Loop %loop: Trip multiple is 1
1432 ;
1433 entry:
1434   br label %loop
1435 loop:
1436   %i = phi i32 [ %nexti, %loop ], [ %start, %entry ]
1437
1438   %index32 = sub nsw i32 %i, %sub
1439   %index64 = sext i32 %index32 to i64
1440
1441   %ptr = getelementptr inbounds float, ptr %input, i64 %index64
1442   %nexti = add nsw i32 %i, 1
1443   %f = load float, ptr %ptr, align 4
1444   %exitcond = icmp eq i32 %nexti, %numIterations
1445   br i1 %exitcond, label %exit, label %loop
1446 exit:
1447   ret void
1448 }
1449
1450 ; Example where a sub should get the nsw flag as the RHS cannot be the
1451 ; minimal signed value.
1452 define void @test-sub-nsw(ptr %input, i32 %start, i32 %sub, i32 %numIterations) {
1453 ; CHECK-LABEL: 'test-sub-nsw'
1454 ; CHECK-NEXT:  Classifying expressions for: @test-sub-nsw
1455 ; CHECK-NEXT:    %halfsub = ashr i32 %sub, 1
1456 ; CHECK-NEXT:    --> %halfsub U: [-1073741824,1073741824) S: [-1073741824,1073741824)
1457 ; CHECK-NEXT:    %i = phi i32 [ %nexti, %loop ], [ %start, %entry ]
1458 ; CHECK-NEXT:    --> {%start,+,1}<nsw><%loop> U: full-set S: full-set Exits: (-1 + %numIterations) LoopDispositions: { %loop: Computable }
1459 ; CHECK-NEXT:    %index32 = sub nsw i32 %i, %halfsub
1460 ; CHECK-NEXT:    --> {((-1 * %halfsub)<nsw> + %start)<nsw>,+,1}<nsw><%loop> U: full-set S: full-set Exits: (-1 + (-1 * %halfsub)<nsw> + %numIterations) LoopDispositions: { %loop: Computable }
1461 ; CHECK-NEXT:    %index64 = sext i32 %index32 to i64
1462 ; CHECK-NEXT:    --> {((sext i32 %start to i64) + (-1 * (sext i32 %halfsub to i64))<nsw>)<nsw>,+,1}<nsw><%loop> U: [-3221225471,7516192767) S: [-3221225471,7516192767) Exits: ((zext i32 (-1 + (-1 * %start) + %numIterations) to i64) + (sext i32 %start to i64) + (-1 * (sext i32 %halfsub to i64))<nsw>) LoopDispositions: { %loop: Computable }
1463 ; CHECK-NEXT:    %ptr = getelementptr inbounds float, ptr %input, i64 %index64
1464 ; CHECK-NEXT:    --> {((4 * (sext i32 %start to i64))<nsw> + (-4 * (sext i32 %halfsub to i64))<nsw> + %input),+,4}<nw><%loop> U: full-set S: full-set Exits: ((4 * (zext i32 (-1 + (-1 * %start) + %numIterations) to i64))<nuw><nsw> + (4 * (sext i32 %start to i64))<nsw> + (-4 * (sext i32 %halfsub to i64))<nsw> + %input) LoopDispositions: { %loop: Computable }
1465 ; CHECK-NEXT:    %nexti = add nsw i32 %i, 1
1466 ; CHECK-NEXT:    --> {(1 + %start)<nsw>,+,1}<nsw><%loop> U: [-2147483647,-2147483648) S: [-2147483647,-2147483648) Exits: %numIterations LoopDispositions: { %loop: Computable }
1467 ; CHECK-NEXT:  Determining loop execution counts for: @test-sub-nsw
1468 ; CHECK-NEXT:  Loop %loop: backedge-taken count is (-1 + (-1 * %start) + %numIterations)
1469 ; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is i32 -1
1470 ; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is (-1 + (-1 * %start) + %numIterations)
1471 ; CHECK-NEXT:  Loop %loop: Trip multiple is 1
1472 ;
1473 entry:
1474   %halfsub = ashr i32 %sub, 1
1475   br label %loop
1476 loop:
1477   %i = phi i32 [ %nexti, %loop ], [ %start, %entry ]
1478
1479   %index32 = sub nsw i32 %i, %halfsub
1480   %index64 = sext i32 %index32 to i64
1481
1482   %ptr = getelementptr inbounds float, ptr %input, i64 %index64
1483   %nexti = add nsw i32 %i, 1
1484   %f = load float, ptr %ptr, align 4
1485   %exitcond = icmp eq i32 %nexti, %numIterations
1486   br i1 %exitcond, label %exit, label %loop
1487 exit:
1488   ret void
1489 }
1490
1491 ; Example where a sub should get the nsw flag, since the LHS is non-negative,
1492 ; which implies that the RHS cannot be the minimal signed value.
1493 define void @test-sub-nsw-lhs-non-negative(ptr %input, i32 %sub, i32 %numIterations) {
1494 ; CHECK-LABEL: 'test-sub-nsw-lhs-non-negative'
1495 ; CHECK-NEXT:  Classifying expressions for: @test-sub-nsw-lhs-non-negative
1496 ; CHECK-NEXT:    %i = phi i32 [ %nexti, %loop ], [ 0, %entry ]
1497 ; CHECK-NEXT:    --> {0,+,1}<nuw><nsw><%loop> U: [0,-2147483648) S: [0,-2147483648) Exits: (-1 + %numIterations) LoopDispositions: { %loop: Computable }
1498 ; CHECK-NEXT:    %index32 = sub nsw i32 %i, %sub
1499 ; CHECK-NEXT:    --> {(-1 * %sub),+,1}<nsw><%loop> U: full-set S: full-set Exits: (-1 + (-1 * %sub) + %numIterations) LoopDispositions: { %loop: Computable }
1500 ; CHECK-NEXT:    %index64 = sext i32 %index32 to i64
1501 ; CHECK-NEXT:    --> {(-1 * (sext i32 %sub to i64))<nsw>,+,1}<nsw><%loop> U: [-2147483647,6442450944) S: [-2147483647,6442450944) Exits: ((zext i32 (-1 + %numIterations) to i64) + (-1 * (sext i32 %sub to i64))<nsw>) LoopDispositions: { %loop: Computable }
1502 ; CHECK-NEXT:    %ptr = getelementptr inbounds float, ptr %input, i64 %index64
1503 ; CHECK-NEXT:    --> {((-4 * (sext i32 %sub to i64))<nsw> + %input),+,4}<nw><%loop> U: full-set S: full-set Exits: ((4 * (zext i32 (-1 + %numIterations) to i64))<nuw><nsw> + (-4 * (sext i32 %sub to i64))<nsw> + %input) LoopDispositions: { %loop: Computable }
1504 ; CHECK-NEXT:    %nexti = add nsw i32 %i, 1
1505 ; CHECK-NEXT:    --> {1,+,1}<nuw><nsw><%loop> U: [1,-2147483648) S: [1,-2147483648) Exits: %numIterations LoopDispositions: { %loop: Computable }
1506 ; CHECK-NEXT:  Determining loop execution counts for: @test-sub-nsw-lhs-non-negative
1507 ; CHECK-NEXT:  Loop %loop: backedge-taken count is (-1 + %numIterations)
1508 ; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is i32 -1
1509 ; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is (-1 + %numIterations)
1510 ; CHECK-NEXT:  Loop %loop: Trip multiple is 1
1511 ;
1512 entry:
1513   br label %loop
1514 loop:
1515   %i = phi i32 [ %nexti, %loop ], [ 0, %entry ]
1516
1517   %index32 = sub nsw i32 %i, %sub
1518
1519   %index64 = sext i32 %index32 to i64
1520
1521   %ptr = getelementptr inbounds float, ptr %input, i64 %index64
1522   %nexti = add nsw i32 %i, 1
1523   %f = load float, ptr %ptr, align 4
1524   %exitcond = icmp eq i32 %nexti, %numIterations
1525   br i1 %exitcond, label %exit, label %loop
1526 exit:
1527   ret void
1528 }
1529
1530 ; Example checking that a sext is pushed onto a sub's operands if the sub is an
1531 ; overflow intrinsic.
1532 define void @test-sext-sub(ptr %input, i32 %sub, i32 %numIterations) {
1533 ; CHECK-LABEL: 'test-sext-sub'
1534 ; CHECK-NEXT:  Classifying expressions for: @test-sext-sub
1535 ; CHECK-NEXT:    %i = phi i32 [ %nexti, %cont ], [ 0, %entry ]
1536 ; CHECK-NEXT:    --> {0,+,1}<nuw><nsw><%loop> U: [0,-2147483648) S: [0,-2147483648) Exits: <<Unknown>> LoopDispositions: { %loop: Computable }
1537 ; CHECK-NEXT:    %val = extractvalue { i32, i1 } %ssub, 0
1538 ; CHECK-NEXT:    --> {(-1 * %sub),+,1}<nw><%loop> U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Computable }
1539 ; CHECK-NEXT:    %ovfl = extractvalue { i32, i1 } %ssub, 1
1540 ; CHECK-NEXT:    --> %ovfl U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
1541 ; CHECK-NEXT:    %index64 = sext i32 %val to i64
1542 ; CHECK-NEXT:    --> {(-1 * (sext i32 %sub to i64))<nsw>,+,1}<nsw><%loop> U: [-2147483647,6442450944) S: [-2147483647,6442450944) Exits: <<Unknown>> LoopDispositions: { %loop: Computable }
1543 ; CHECK-NEXT:    %ptr = getelementptr inbounds float, ptr %input, i64 %index64
1544 ; CHECK-NEXT:    --> {((-4 * (sext i32 %sub to i64))<nsw> + %input),+,4}<nw><%loop> U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Computable }
1545 ; CHECK-NEXT:    %nexti = add nsw i32 %i, 1
1546 ; CHECK-NEXT:    --> {1,+,1}<nuw><%loop> U: [1,0) S: [1,0) Exits: <<Unknown>> LoopDispositions: { %loop: Computable }
1547 ; CHECK-NEXT:  Determining loop execution counts for: @test-sext-sub
1548 ; CHECK-NEXT:  Loop %loop: <multiple exits> Unpredictable backedge-taken count.
1549 ; CHECK-NEXT:    exit count for loop: ***COULDNOTCOMPUTE***
1550 ; CHECK-NEXT:    exit count for cont: (-1 + %numIterations)
1551 ; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is i32 -1
1552 ; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is (-1 + %numIterations)
1553 ; CHECK-NEXT:    symbolic max exit count for loop: ***COULDNOTCOMPUTE***
1554 ; CHECK-NEXT:    symbolic max exit count for cont: (-1 + %numIterations)
1555 ;
1556 entry:
1557   br label %loop
1558 loop:
1559   %i = phi i32 [ %nexti, %cont ], [ 0, %entry ]
1560
1561   %ssub = tail call { i32, i1 } @llvm.ssub.with.overflow.i32(i32 %i, i32 %sub)
1562   %val = extractvalue { i32, i1 } %ssub, 0
1563   %ovfl = extractvalue { i32, i1 } %ssub, 1
1564   br i1 %ovfl, label %trap, label %cont
1565
1566 trap:
1567   tail call void @llvm.trap()
1568   unreachable
1569
1570 cont:
1571   %index64 = sext i32 %val to i64
1572
1573   %ptr = getelementptr inbounds float, ptr %input, i64 %index64
1574   %nexti = add nsw i32 %i, 1
1575   %f = load float, ptr %ptr, align 4
1576   %exitcond = icmp eq i32 %nexti, %numIterations
1577   br i1 %exitcond, label %exit, label %loop
1578 exit:
1579   ret void
1580 }
1581
1582 ; Two adds with a sub in the middle and the sub should have nsw. There is
1583 ; a special case for sequential adds/subs and this test covers that. We have to
1584 ; put the final add first in the program since otherwise the special case
1585 ; is not triggered, hence the strange basic block ordering.
1586 define void @test-sub-with-add(ptr %input, i32 %offset, i32 %numIterations) {
1587 ; CHECK-LABEL: 'test-sub-with-add'
1588 ; CHECK-NEXT:  Classifying expressions for: @test-sub-with-add
1589 ; CHECK-NEXT:    %seq = add nuw nsw i32 %index32, 1
1590 ; CHECK-NEXT:    --> {(2 + (-1 * %offset)),+,1}<nw><%loop> U: full-set S: full-set Exits: (1 + (-1 * %offset) + %numIterations) LoopDispositions: { %loop: Computable }
1591 ; CHECK-NEXT:    %i = phi i32 [ %nexti, %loop2 ], [ 0, %entry ]
1592 ; CHECK-NEXT:    --> {0,+,1}<nuw><nsw><%loop> U: [0,-2147483648) S: [0,-2147483648) Exits: (-1 + %numIterations) LoopDispositions: { %loop: Computable }
1593 ; CHECK-NEXT:    %j = add nsw i32 %i, 1
1594 ; CHECK-NEXT:    --> {1,+,1}<nuw><nsw><%loop> U: [1,-2147483648) S: [1,-2147483648) Exits: %numIterations LoopDispositions: { %loop: Computable }
1595 ; CHECK-NEXT:    %index32 = sub nsw i32 %j, %offset
1596 ; CHECK-NEXT:    --> {(1 + (-1 * %offset))<nsw>,+,1}<nsw><%loop> U: [-2147483647,-2147483648) S: [-2147483647,-2147483648) Exits: ((-1 * %offset) + %numIterations) LoopDispositions: { %loop: Computable }
1597 ; CHECK-NEXT:    %ptr = getelementptr inbounds float, ptr %input, i32 %index32
1598 ; CHECK-NEXT:    --> {(4 + (4 * (sext i32 (-1 * %offset) to i64))<nsw> + %input),+,4}<nw><%loop> U: full-set S: full-set Exits: (4 + (4 * (zext i32 (-1 + %numIterations) to i64))<nuw><nsw> + (4 * (sext i32 (-1 * %offset) to i64))<nsw> + %input) LoopDispositions: { %loop: Computable }
1599 ; CHECK-NEXT:    %nexti = add nsw i32 %i, 1
1600 ; CHECK-NEXT:    --> {1,+,1}<nuw><nsw><%loop> U: [1,-2147483648) S: [1,-2147483648) Exits: %numIterations LoopDispositions: { %loop: Computable }
1601 ; CHECK-NEXT:  Determining loop execution counts for: @test-sub-with-add
1602 ; CHECK-NEXT:  Loop %loop: backedge-taken count is (-1 + %numIterations)
1603 ; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is i32 -1
1604 ; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is (-1 + %numIterations)
1605 ; CHECK-NEXT:  Loop %loop: Trip multiple is 1
1606 ;
1607 entry:
1608   br label %loop
1609 loop2:
1610   %seq = add nsw nuw i32 %index32, 1
1611   %exitcond = icmp eq i32 %nexti, %numIterations
1612   br i1 %exitcond, label %exit, label %loop
1613
1614 loop:
1615   %i = phi i32 [ %nexti, %loop2 ], [ 0, %entry ]
1616
1617   %j = add nsw i32 %i, 1
1618   %index32 = sub nsw i32 %j, %offset
1619
1620   %ptr = getelementptr inbounds float, ptr %input, i32 %index32
1621   %nexti = add nsw i32 %i, 1
1622   store float 1.0, ptr %ptr, align 4
1623   br label %loop2
1624 exit:
1625   ret void
1626 }
1627
1628 ; PR28932: Don't assert on non-SCEV-able value %2.
1629 %struct.anon = type { ptr }
1630 @a = common global ptr null, align 8
1631 @b = common global i32 0, align 4
1632 declare { i32, i1 } @llvm.ssub.with.overflow.i32(i32, i32)
1633 declare void @llvm.trap()
1634 define i32 @pr28932() {
1635 ; CHECK-LABEL: 'pr28932'
1636 ; CHECK-NEXT:  Classifying expressions for: @pr28932
1637 ; CHECK-NEXT:    %pre = load ptr, ptr @a, align 8
1638 ; CHECK-NEXT:    --> %pre U: full-set S: full-set
1639 ; CHECK-NEXT:    %pre7 = load i32, ptr @b, align 4
1640 ; CHECK-NEXT:    --> %pre7 U: full-set S: full-set
1641 ; CHECK-NEXT:    %i = phi i32 [ %i3, %cont6 ], [ %pre7, %entry ]
1642 ; CHECK-NEXT:    --> {%pre7,+,-1}<%for.cond> U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %for.cond: Computable }
1643 ; CHECK-NEXT:    %i1 = phi ptr [ %ph, %cont6 ], [ %pre, %entry ]
1644 ; CHECK-NEXT:    --> %i1 U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %for.cond: Variant }
1645 ; CHECK-NEXT:    %i3 = extractvalue { i32, i1 } %i2, 0
1646 ; CHECK-NEXT:    --> {(-1 + %pre7),+,-1}<%for.cond> U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %for.cond: Computable }
1647 ; CHECK-NEXT:    %i4 = extractvalue { i32, i1 } %i2, 1
1648 ; CHECK-NEXT:    --> %i4 U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %for.cond: Variant }
1649 ; CHECK-NEXT:    %idxprom = sext i32 %i3 to i64
1650 ; CHECK-NEXT:    --> (sext i32 {(-1 + %pre7),+,-1}<%for.cond> to i64) U: [-2147483648,2147483648) S: [-2147483648,2147483648) Exits: <<Unknown>> LoopDispositions: { %for.cond: Computable }
1651 ; CHECK-NEXT:    %i6 = load ptr, ptr %i1, align 8
1652 ; CHECK-NEXT:    --> %i6 U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %for.cond: Variant }
1653 ; CHECK-NEXT:    %i7 = getelementptr inbounds i8, ptr %i6, i64 %idxprom
1654 ; CHECK-NEXT:    --> ((sext i32 {(-1 + %pre7),+,-1}<%for.cond> to i64) + %i6) U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %for.cond: Variant }
1655 ; CHECK-NEXT:    %i8 = load i8, ptr %i7, align 1
1656 ; CHECK-NEXT:    --> %i8 U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %for.cond: Variant }
1657 ; CHECK-NEXT:    %conv5 = sext i8 %i8 to i64
1658 ; CHECK-NEXT:    --> (sext i8 %i8 to i64) U: [-128,128) S: [-128,128) Exits: <<Unknown>> LoopDispositions: { %for.cond: Variant }
1659 ; CHECK-NEXT:    %i9 = inttoptr i64 %conv5 to ptr
1660 ; CHECK-NEXT:    --> %i9 U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %for.cond: Variant }
1661 ; CHECK-NEXT:    %ph = phi ptr [ %i9, %cont1 ], [ %i1, %if.then ]
1662 ; CHECK-NEXT:    --> %ph U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %for.cond: Variant }
1663 ; CHECK-NEXT:  Determining loop execution counts for: @pr28932
1664 ; CHECK-NEXT:  Loop %for.cond: <multiple exits> Unpredictable backedge-taken count.
1665 ; CHECK-NEXT:    exit count for if.then: ***COULDNOTCOMPUTE***
1666 ; CHECK-NEXT:    exit count for if.else: ***COULDNOTCOMPUTE***
1667 ; CHECK-NEXT:  Loop %for.cond: Unpredictable constant max backedge-taken count.
1668 ; CHECK-NEXT:  Loop %for.cond: Unpredictable symbolic max backedge-taken count.
1669 ; CHECK-NEXT:    symbolic max exit count for if.then: ***COULDNOTCOMPUTE***
1670 ; CHECK-NEXT:    symbolic max exit count for if.else: ***COULDNOTCOMPUTE***
1671 ;
1672 entry:
1673   %pre = load ptr, ptr @a, align 8
1674   %pre7 = load i32, ptr @b, align 4
1675   br label %for.cond
1676
1677 for.cond:                                         ; preds = %cont6, %entry
1678   %i = phi i32 [ %i3, %cont6 ], [ %pre7, %entry ]
1679   %i1 = phi ptr [ %ph, %cont6 ], [ %pre, %entry ]
1680   %tobool = icmp eq ptr %i1, null
1681   %i2 = tail call { i32, i1 } @llvm.ssub.with.overflow.i32(i32 %i, i32 1)
1682   %i3 = extractvalue { i32, i1 } %i2, 0
1683   %i4 = extractvalue { i32, i1 } %i2, 1
1684   %idxprom = sext i32 %i3 to i64
1685   %i6 = load ptr, ptr %i1, align 8
1686   %i7 = getelementptr inbounds i8, ptr %i6, i64 %idxprom
1687   %i8 = load i8, ptr %i7, align 1
1688   br i1 %tobool, label %if.else, label %if.then
1689
1690 if.then:                                          ; preds = %for.cond
1691   br i1 %i4, label %trap, label %cont6
1692
1693 trap:                                             ; preds = %if.else, %if.then
1694   tail call void @llvm.trap()
1695   unreachable
1696
1697 if.else:                                          ; preds = %for.cond
1698   br i1 %i4, label %trap, label %cont1
1699
1700 cont1:                                            ; preds = %if.else
1701   %conv5 = sext i8 %i8 to i64
1702   %i9 = inttoptr i64 %conv5 to ptr
1703   store ptr %i9, ptr @a, align 8
1704   br label %cont6
1705
1706 cont6:                                            ; preds = %cont1, %if.then
1707   %ph = phi ptr [ %i9, %cont1 ], [ %i1, %if.then ]
1708   store i32 %i3, ptr @b, align 4
1709   br label %for.cond
1710 }
1711
1712 define noundef i32 @add-basic(i32 %a, i32 %b) {
1713 ; CHECK-LABEL: 'add-basic'
1714 ; CHECK-NEXT:  Classifying expressions for: @add-basic
1715 ; CHECK-NEXT:    %res = add nuw nsw i32 %a, %b
1716 ; CHECK-NEXT:    --> (%a + %b)<nuw><nsw> U: full-set S: full-set
1717 ; CHECK-NEXT:  Determining loop execution counts for: @add-basic
1718 ;
1719   %res = add nuw nsw i32 %a, %b
1720   ret i32 %res
1721 }
1722
1723 define noundef i32 @sub-basic(i32 %a, i32 %b) {
1724 ; CHECK-LABEL: 'sub-basic'
1725 ; CHECK-NEXT:  Classifying expressions for: @sub-basic
1726 ; CHECK-NEXT:    %res = sub nuw nsw i32 %a, %b
1727 ; CHECK-NEXT:    --> ((-1 * %b) + %a) U: full-set S: full-set
1728 ; CHECK-NEXT:  Determining loop execution counts for: @sub-basic
1729 ;
1730   %res = sub nuw nsw i32 %a, %b
1731   ret i32 %res
1732 }
1733
1734 define noundef i32 @mul-basic(i32 %a, i32 %b) {
1735 ; CHECK-LABEL: 'mul-basic'
1736 ; CHECK-NEXT:  Classifying expressions for: @mul-basic
1737 ; CHECK-NEXT:    %res = mul nuw nsw i32 %a, %b
1738 ; CHECK-NEXT:    --> (%a * %b)<nuw><nsw> U: full-set S: full-set
1739 ; CHECK-NEXT:  Determining loop execution counts for: @mul-basic
1740 ;
1741   %res = mul nuw nsw i32 %a, %b
1742   ret i32 %res
1743 }
1744
1745 define noundef i32 @udiv-basic(i32 %a, i32 %b) {
1746 ; CHECK-LABEL: 'udiv-basic'
1747 ; CHECK-NEXT:  Classifying expressions for: @udiv-basic
1748 ; CHECK-NEXT:    %res = udiv exact i32 %a, %b
1749 ; CHECK-NEXT:    --> (%a /u %b) U: full-set S: full-set
1750 ; CHECK-NEXT:  Determining loop execution counts for: @udiv-basic
1751 ;
1752   %res = udiv exact i32 %a, %b
1753   ret i32 %res
1754 }
1755
1756 @gA = external global i32
1757 @gB = external global i32
1758 @gC = external global i32
1759 @gD = external global i32
1760
1761 define noundef i64 @add-zext-recurse(i64 %arg) {
1762 ; CHECK-LABEL: 'add-zext-recurse'
1763 ; CHECK-NEXT:  Classifying expressions for: @add-zext-recurse
1764 ; CHECK-NEXT:    %a = load i32, ptr @gA, align 4
1765 ; CHECK-NEXT:    --> %a U: full-set S: full-set
1766 ; CHECK-NEXT:    %x = zext i32 %a to i64
1767 ; CHECK-NEXT:    --> (zext i32 %a to i64) U: [0,4294967296) S: [0,4294967296)
1768 ; CHECK-NEXT:    %res = add nuw i64 %x, %arg
1769 ; CHECK-NEXT:    --> ((zext i32 %a to i64) + %arg)<nuw> U: full-set S: full-set
1770 ; CHECK-NEXT:  Determining loop execution counts for: @add-zext-recurse
1771 ;
1772   call void @foo()
1773   %a = load i32, ptr @gA
1774   %x = zext i32 %a to i64
1775   %res = add nuw i64 %x, %arg
1776   ret i64 %res
1777 }
1778
1779 define noundef i64 @add-sext-recurse(i64 %arg) {
1780 ; CHECK-LABEL: 'add-sext-recurse'
1781 ; CHECK-NEXT:  Classifying expressions for: @add-sext-recurse
1782 ; CHECK-NEXT:    %a = load i32, ptr @gA, align 4
1783 ; CHECK-NEXT:    --> %a U: full-set S: full-set
1784 ; CHECK-NEXT:    %x = sext i32 %a to i64
1785 ; CHECK-NEXT:    --> (sext i32 %a to i64) U: [-2147483648,2147483648) S: [-2147483648,2147483648)
1786 ; CHECK-NEXT:    %res = add nuw i64 %x, %arg
1787 ; CHECK-NEXT:    --> ((sext i32 %a to i64) + %arg)<nuw> U: full-set S: full-set
1788 ; CHECK-NEXT:  Determining loop execution counts for: @add-sext-recurse
1789 ;
1790   call void @foo()
1791   %a = load i32, ptr @gA
1792   %x = sext i32 %a to i64
1793   %res = add nuw i64 %x, %arg
1794   ret i64 %res
1795 }
1796
1797 define noundef i16 @add-trunc-recurse() {
1798 ; CHECK-LABEL: 'add-trunc-recurse'
1799 ; CHECK-NEXT:  Classifying expressions for: @add-trunc-recurse
1800 ; CHECK-NEXT:    %a = load i32, ptr @gA, align 4
1801 ; CHECK-NEXT:    --> %a U: full-set S: full-set
1802 ; CHECK-NEXT:    %x = trunc i32 %a to i16
1803 ; CHECK-NEXT:    --> (trunc i32 %a to i16) U: full-set S: full-set
1804 ; CHECK-NEXT:    %res = add nuw i16 %x, 1
1805 ; CHECK-NEXT:    --> (1 + (trunc i32 %a to i16))<nuw> U: [1,0) S: [1,0)
1806 ; CHECK-NEXT:  Determining loop execution counts for: @add-trunc-recurse
1807 ;
1808   call void @foo()
1809   %a = load i32, ptr @gA
1810   %x = trunc i32 %a to i16
1811   %res = add nuw i16 %x, 1
1812   ret i16 %res
1813 }
1814
1815 define noundef i32 @add-udiv-recurse(i32 %arg) {
1816 ; CHECK-LABEL: 'add-udiv-recurse'
1817 ; CHECK-NEXT:  Classifying expressions for: @add-udiv-recurse
1818 ; CHECK-NEXT:    %a = load i32, ptr @gA, align 4
1819 ; CHECK-NEXT:    --> %a U: full-set S: full-set
1820 ; CHECK-NEXT:    %x = udiv i32 %a, %arg
1821 ; CHECK-NEXT:    --> (%a /u %arg) U: full-set S: full-set
1822 ; CHECK-NEXT:    %res = add nuw i32 %x, 1
1823 ; CHECK-NEXT:    --> (1 + (%a /u %arg))<nuw> U: [1,0) S: [1,0)
1824 ; CHECK-NEXT:  Determining loop execution counts for: @add-udiv-recurse
1825 ;
1826   call void @foo()
1827   %a = load i32, ptr @gA
1828   %x = udiv i32 %a, %arg
1829   %res = add nuw i32 %x, 1
1830   ret i32 %res
1831 }
1832
1833 define noundef i32 @add-mul-recurse() {
1834 ; CHECK-LABEL: 'add-mul-recurse'
1835 ; CHECK-NEXT:  Classifying expressions for: @add-mul-recurse
1836 ; CHECK-NEXT:    %a = load i32, ptr @gA, align 4
1837 ; CHECK-NEXT:    --> %a U: full-set S: full-set
1838 ; CHECK-NEXT:    %x = mul i32 %a, 3
1839 ; CHECK-NEXT:    --> (3 * %a) U: full-set S: full-set
1840 ; CHECK-NEXT:    %res = add nuw i32 %x, 1
1841 ; CHECK-NEXT:    --> (1 + (3 * %a))<nuw> U: [1,0) S: [1,0)
1842 ; CHECK-NEXT:  Determining loop execution counts for: @add-mul-recurse
1843 ;
1844   call void @foo()
1845   %a = load i32, ptr @gA
1846   %x = mul i32 %a, 3
1847   %res = add nuw i32 %x, 1
1848   ret i32 %res
1849 }
1850
1851 declare i32 @llvm.smin.i32(i32, i32)
1852 declare i32 @llvm.smax.i32(i32, i32)
1853 declare i32 @llvm.umin.i32(i32, i32)
1854 declare i32 @llvm.umax.i32(i32, i32)
1855
1856 define noundef i32 @add-smin-recurse(i32 %arg) {
1857 ; CHECK-LABEL: 'add-smin-recurse'
1858 ; CHECK-NEXT:  Classifying expressions for: @add-smin-recurse
1859 ; CHECK-NEXT:    %a = load i32, ptr @gA, align 4
1860 ; CHECK-NEXT:    --> %a U: full-set S: full-set
1861 ; CHECK-NEXT:    %x = call i32 @llvm.smin.i32(i32 %a, i32 %arg)
1862 ; CHECK-NEXT:    --> (%arg smin %a) U: full-set S: full-set
1863 ; CHECK-NEXT:    %res = add nuw i32 %x, 1
1864 ; CHECK-NEXT:    --> (1 + (%arg smin %a))<nuw> U: [1,0) S: [1,0)
1865 ; CHECK-NEXT:  Determining loop execution counts for: @add-smin-recurse
1866 ;
1867   call void @foo()
1868   %a = load i32, ptr @gA
1869   %x = call i32 @llvm.smin.i32(i32 %a, i32 %arg)
1870   %res = add nuw i32 %x, 1
1871   ret i32 %res
1872 }
1873
1874 define noundef i32 @add-smax-recurse(i32 %arg) {
1875 ; CHECK-LABEL: 'add-smax-recurse'
1876 ; CHECK-NEXT:  Classifying expressions for: @add-smax-recurse
1877 ; CHECK-NEXT:    %a = load i32, ptr @gA, align 4
1878 ; CHECK-NEXT:    --> %a U: full-set S: full-set
1879 ; CHECK-NEXT:    %x = call i32 @llvm.smax.i32(i32 %a, i32 %arg)
1880 ; CHECK-NEXT:    --> (%arg smax %a) U: full-set S: full-set
1881 ; CHECK-NEXT:    %res = add nuw i32 %x, 1
1882 ; CHECK-NEXT:    --> (1 + (%arg smax %a))<nuw> U: [1,0) S: [1,0)
1883 ; CHECK-NEXT:  Determining loop execution counts for: @add-smax-recurse
1884 ;
1885   call void @foo()
1886   %a = load i32, ptr @gA
1887   %x = call i32 @llvm.smax.i32(i32 %a, i32 %arg)
1888   %res = add nuw i32 %x, 1
1889   ret i32 %res
1890 }
1891
1892 define noundef i32 @add-umin-recurse(i32 %arg) {
1893 ; CHECK-LABEL: 'add-umin-recurse'
1894 ; CHECK-NEXT:  Classifying expressions for: @add-umin-recurse
1895 ; CHECK-NEXT:    %a = load i32, ptr @gA, align 4
1896 ; CHECK-NEXT:    --> %a U: full-set S: full-set
1897 ; CHECK-NEXT:    %x = call i32 @llvm.umin.i32(i32 %a, i32 %arg)
1898 ; CHECK-NEXT:    --> (%arg umin %a) U: full-set S: full-set
1899 ; CHECK-NEXT:    %res = add nuw i32 %x, 1
1900 ; CHECK-NEXT:    --> (1 + (%arg umin %a))<nuw> U: [1,0) S: [1,0)
1901 ; CHECK-NEXT:  Determining loop execution counts for: @add-umin-recurse
1902 ;
1903   call void @foo()
1904   %a = load i32, ptr @gA
1905   %x = call i32 @llvm.umin.i32(i32 %a, i32 %arg)
1906   %res = add nuw i32 %x, 1
1907   ret i32 %res
1908 }
1909
1910 define noundef i32 @add-umax-recurse(i32 %arg) {
1911 ; CHECK-LABEL: 'add-umax-recurse'
1912 ; CHECK-NEXT:  Classifying expressions for: @add-umax-recurse
1913 ; CHECK-NEXT:    %a = load i32, ptr @gA, align 4
1914 ; CHECK-NEXT:    --> %a U: full-set S: full-set
1915 ; CHECK-NEXT:    %x = call i32 @llvm.umax.i32(i32 %a, i32 %arg)
1916 ; CHECK-NEXT:    --> (%arg umax %a) U: full-set S: full-set
1917 ; CHECK-NEXT:    %res = add nuw i32 %x, 1
1918 ; CHECK-NEXT:    --> (1 + (%arg umax %a))<nuw> U: [1,0) S: [1,0)
1919 ; CHECK-NEXT:  Determining loop execution counts for: @add-umax-recurse
1920 ;
1921   call void @foo()
1922   %a = load i32, ptr @gA
1923   %x = call i32 @llvm.umax.i32(i32 %a, i32 %arg)
1924   %res = add nuw i32 %x, 1
1925   ret i32 %res
1926 }
1927
1928
1929 define noundef i32 @add-recurse-inline() {
1930 ; CHECK-LABEL: 'add-recurse-inline'
1931 ; CHECK-NEXT:  Classifying expressions for: @add-recurse-inline
1932 ; CHECK-NEXT:    %a = load i32, ptr @gA, align 4
1933 ; CHECK-NEXT:    --> %a U: full-set S: full-set
1934 ; CHECK-NEXT:    %b = load i32, ptr @gB, align 4
1935 ; CHECK-NEXT:    --> %b U: full-set S: full-set
1936 ; CHECK-NEXT:    %c = load i32, ptr @gC, align 4
1937 ; CHECK-NEXT:    --> %c U: full-set S: full-set
1938 ; CHECK-NEXT:    %d = load i32, ptr @gD, align 4
1939 ; CHECK-NEXT:    --> %d U: full-set S: full-set
1940 ; CHECK-NEXT:    %x = add nuw i32 %a, %b
1941 ; CHECK-NEXT:    --> (%a + %b)<nuw> U: full-set S: full-set
1942 ; CHECK-NEXT:    %y = add nuw i32 %c, %d
1943 ; CHECK-NEXT:    --> (%c + %d)<nuw> U: full-set S: full-set
1944 ; CHECK-NEXT:    %res = add nuw i32 %x, %y
1945 ; CHECK-NEXT:    --> (%a + %b + %c + %d)<nuw> U: full-set S: full-set
1946 ; CHECK-NEXT:  Determining loop execution counts for: @add-recurse-inline
1947 ;
1948   call void @foo()
1949   %a = load i32, ptr @gA
1950   %b = load i32, ptr @gB
1951   %c = load i32, ptr @gC
1952   %d = load i32, ptr @gD
1953
1954   %x = add nuw i32 %a, %b
1955   %y = add nuw i32 %c, %d
1956   %res = add nuw i32 %x, %y
1957   ret i32 %res
1958 }
1959
1960 define noundef ptr @gep_inbounds(ptr %p, i64 %index) {
1961 ; CHECK-LABEL: 'gep_inbounds'
1962 ; CHECK-NEXT:  Classifying expressions for: @gep_inbounds
1963 ; CHECK-NEXT:    %gep = getelementptr inbounds i32, ptr %p, i64 %index
1964 ; CHECK-NEXT:    --> ((4 * %index)<nsw> + %p) U: full-set S: full-set
1965 ; CHECK-NEXT:  Determining loop execution counts for: @gep_inbounds
1966 ;
1967   %gep = getelementptr inbounds i32, ptr %p, i64 %index
1968   ret ptr %gep
1969 }
1970
1971 define noundef ptr @gep_inbounds_nneg(ptr %p, i32 %index) {
1972 ; CHECK-LABEL: 'gep_inbounds_nneg'
1973 ; CHECK-NEXT:  Classifying expressions for: @gep_inbounds_nneg
1974 ; CHECK-NEXT:    %index.ext = zext i32 %index to i64
1975 ; CHECK-NEXT:    --> (zext i32 %index to i64) U: [0,4294967296) S: [0,4294967296)
1976 ; CHECK-NEXT:    %gep = getelementptr inbounds i32, ptr %p, i64 %index.ext
1977 ; CHECK-NEXT:    --> ((4 * (zext i32 %index to i64))<nuw><nsw> + %p)<nuw> U: full-set S: full-set
1978 ; CHECK-NEXT:  Determining loop execution counts for: @gep_inbounds_nneg
1979 ;
1980   %index.ext = zext i32 %index to i64
1981   %gep = getelementptr inbounds i32, ptr %p, i64 %index.ext
1982   ret ptr %gep
1983 }
1984
1985 define noundef ptr @gep_nusw(ptr %p, i64 %index) {
1986 ; CHECK-LABEL: 'gep_nusw'
1987 ; CHECK-NEXT:  Classifying expressions for: @gep_nusw
1988 ; CHECK-NEXT:    %gep = getelementptr nusw i32, ptr %p, i64 %index
1989 ; CHECK-NEXT:    --> ((4 * %index)<nsw> + %p) U: full-set S: full-set
1990 ; CHECK-NEXT:  Determining loop execution counts for: @gep_nusw
1991 ;
1992   %gep = getelementptr nusw i32, ptr %p, i64 %index
1993   ret ptr %gep
1994 }
1995
1996 define noundef ptr @gep_nusw_nneg(ptr %p, i32 %index) {
1997 ; CHECK-LABEL: 'gep_nusw_nneg'
1998 ; CHECK-NEXT:  Classifying expressions for: @gep_nusw_nneg
1999 ; CHECK-NEXT:    %index.ext = zext i32 %index to i64
2000 ; CHECK-NEXT:    --> (zext i32 %index to i64) U: [0,4294967296) S: [0,4294967296)
2001 ; CHECK-NEXT:    %gep = getelementptr nusw i32, ptr %p, i64 %index.ext
2002 ; CHECK-NEXT:    --> ((4 * (zext i32 %index to i64))<nuw><nsw> + %p)<nuw> U: full-set S: full-set
2003 ; CHECK-NEXT:  Determining loop execution counts for: @gep_nusw_nneg
2004 ;
2005   %index.ext = zext i32 %index to i64
2006   %gep = getelementptr nusw i32, ptr %p, i64 %index.ext
2007   ret ptr %gep
2008 }
2009
2010 define noundef ptr @gep_nuw(ptr %p, i64 %index) {
2011 ; CHECK-LABEL: 'gep_nuw'
2012 ; CHECK-NEXT:  Classifying expressions for: @gep_nuw
2013 ; CHECK-NEXT:    %gep = getelementptr nuw i32, ptr %p, i64 %index
2014 ; CHECK-NEXT:    --> ((4 * %index)<nuw> + %p)<nuw> U: full-set S: full-set
2015 ; CHECK-NEXT:  Determining loop execution counts for: @gep_nuw
2016 ;
2017   %gep = getelementptr nuw i32, ptr %p, i64 %index
2018   ret ptr %gep
2019 }
2020
2021 define noundef ptr @gep_nusw_nuw(ptr %p, i64 %index) {
2022 ; CHECK-LABEL: 'gep_nusw_nuw'
2023 ; CHECK-NEXT:  Classifying expressions for: @gep_nusw_nuw
2024 ; CHECK-NEXT:    %gep = getelementptr nusw nuw i32, ptr %p, i64 %index
2025 ; CHECK-NEXT:    --> ((4 * %index)<nuw><nsw> + %p)<nuw> U: full-set S: full-set
2026 ; CHECK-NEXT:  Determining loop execution counts for: @gep_nusw_nuw
2027 ;
2028   %gep = getelementptr nusw nuw i32, ptr %p, i64 %index
2029   ret ptr %gep
2030 }
2031
2032 define ptr @gep_nusw_nuw_missing_noundef(ptr %p, i64 %index) {
2033 ; CHECK-LABEL: 'gep_nusw_nuw_missing_noundef'
2034 ; CHECK-NEXT:  Classifying expressions for: @gep_nusw_nuw_missing_noundef
2035 ; CHECK-NEXT:    %gep = getelementptr nusw nuw i32, ptr %p, i64 %index
2036 ; CHECK-NEXT:    --> ((4 * %index) + %p) U: full-set S: full-set
2037 ; CHECK-NEXT:  Determining loop execution counts for: @gep_nusw_nuw_missing_noundef
2038 ;
2039   %gep = getelementptr nusw nuw i32, ptr %p, i64 %index
2040   ret ptr %gep
2041 }
2042
2043 define void @addrec_gep_inbounds_nneg(ptr %p, ptr %end) {
2044 ; CHECK-LABEL: 'addrec_gep_inbounds_nneg'
2045 ; CHECK-NEXT:  Classifying expressions for: @addrec_gep_inbounds_nneg
2046 ; CHECK-NEXT:    %iv = phi ptr [ %p, %entry ], [ %iv.next, %loop ]
2047 ; CHECK-NEXT:    --> {%p,+,4}<nuw><%loop> U: full-set S: full-set Exits: ((4 * ((-4 + (-1 * (ptrtoint ptr %p to i64)) + (ptrtoint ptr %end to i64)) /u 4))<nuw> + %p) LoopDispositions: { %loop: Computable }
2048 ; CHECK-NEXT:    %iv.next = getelementptr inbounds i32, ptr %iv, i64 1
2049 ; CHECK-NEXT:    --> {(4 + %p)<nuw>,+,4}<nuw><%loop> U: [4,0) S: [4,0) Exits: (4 + (4 * ((-4 + (-1 * (ptrtoint ptr %p to i64)) + (ptrtoint ptr %end to i64)) /u 4))<nuw> + %p) LoopDispositions: { %loop: Computable }
2050 ; CHECK-NEXT:  Determining loop execution counts for: @addrec_gep_inbounds_nneg
2051 ; CHECK-NEXT:  Loop %loop: backedge-taken count is ((-4 + (-1 * (ptrtoint ptr %p to i64)) + (ptrtoint ptr %end to i64)) /u 4)
2052 ; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is i64 4611686018427387903
2053 ; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is ((-4 + (-1 * (ptrtoint ptr %p to i64)) + (ptrtoint ptr %end to i64)) /u 4)
2054 ; CHECK-NEXT:  Loop %loop: Trip multiple is 1
2055 ;
2056 entry:
2057   br label %loop
2058 loop:
2059   %iv = phi ptr [ %p, %entry], [ %iv.next, %loop ]
2060   %iv.next = getelementptr inbounds i32, ptr %iv, i64 1
2061   %cmp = icmp ne ptr %iv.next, %end
2062   br i1 %cmp, label %loop, label %exit
2063 exit:
2064   ret void
2065 }
2066
2067 define void @addrec_gep_inbounds_neg(ptr %p, ptr %end) {
2068 ; CHECK-LABEL: 'addrec_gep_inbounds_neg'
2069 ; CHECK-NEXT:  Classifying expressions for: @addrec_gep_inbounds_neg
2070 ; CHECK-NEXT:    %iv = phi ptr [ %p, %entry ], [ %iv.next, %loop ]
2071 ; CHECK-NEXT:    --> {%p,+,-4}<nw><%loop> U: full-set S: full-set Exits: ((-4 * ((-4 + (-1 * (ptrtoint ptr %end to i64)) + (ptrtoint ptr %p to i64)) /u 4)) + %p) LoopDispositions: { %loop: Computable }
2072 ; CHECK-NEXT:    %iv.next = getelementptr inbounds i32, ptr %iv, i64 -1
2073 ; CHECK-NEXT:    --> {(-4 + %p),+,-4}<nw><%loop> U: full-set S: full-set Exits: (-4 + (-4 * ((-4 + (-1 * (ptrtoint ptr %end to i64)) + (ptrtoint ptr %p to i64)) /u 4)) + %p) LoopDispositions: { %loop: Computable }
2074 ; CHECK-NEXT:  Determining loop execution counts for: @addrec_gep_inbounds_neg
2075 ; CHECK-NEXT:  Loop %loop: backedge-taken count is ((-4 + (-1 * (ptrtoint ptr %end to i64)) + (ptrtoint ptr %p to i64)) /u 4)
2076 ; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is i64 4611686018427387903
2077 ; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is ((-4 + (-1 * (ptrtoint ptr %end to i64)) + (ptrtoint ptr %p to i64)) /u 4)
2078 ; CHECK-NEXT:  Loop %loop: Trip multiple is 1
2079 ;
2080 entry:
2081   br label %loop
2082 loop:
2083   %iv = phi ptr [ %p, %entry], [ %iv.next, %loop ]
2084   %iv.next = getelementptr inbounds i32, ptr %iv, i64 -1
2085   %cmp = icmp ne ptr %iv.next, %end
2086   br i1 %cmp, label %loop, label %exit
2087 exit:
2088   ret void
2089 }
2090
2091 define void @addrec_gep_nusw_nneg(ptr %p, ptr %end) {
2092 ; CHECK-LABEL: 'addrec_gep_nusw_nneg'
2093 ; CHECK-NEXT:  Classifying expressions for: @addrec_gep_nusw_nneg
2094 ; CHECK-NEXT:    %iv = phi ptr [ %p, %entry ], [ %iv.next, %loop ]
2095 ; CHECK-NEXT:    --> {%p,+,4}<nuw><%loop> U: full-set S: full-set Exits: ((4 * ((-4 + (-1 * (ptrtoint ptr %p to i64)) + (ptrtoint ptr %end to i64)) /u 4))<nuw> + %p) LoopDispositions: { %loop: Computable }
2096 ; CHECK-NEXT:    %iv.next = getelementptr nusw i32, ptr %iv, i64 1
2097 ; CHECK-NEXT:    --> {(4 + %p)<nuw>,+,4}<nuw><%loop> U: [4,0) S: [4,0) Exits: (4 + (4 * ((-4 + (-1 * (ptrtoint ptr %p to i64)) + (ptrtoint ptr %end to i64)) /u 4))<nuw> + %p) LoopDispositions: { %loop: Computable }
2098 ; CHECK-NEXT:  Determining loop execution counts for: @addrec_gep_nusw_nneg
2099 ; CHECK-NEXT:  Loop %loop: backedge-taken count is ((-4 + (-1 * (ptrtoint ptr %p to i64)) + (ptrtoint ptr %end to i64)) /u 4)
2100 ; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is i64 4611686018427387903
2101 ; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is ((-4 + (-1 * (ptrtoint ptr %p to i64)) + (ptrtoint ptr %end to i64)) /u 4)
2102 ; CHECK-NEXT:  Loop %loop: Trip multiple is 1
2103 ;
2104 entry:
2105   br label %loop
2106 loop:
2107   %iv = phi ptr [ %p, %entry], [ %iv.next, %loop ]
2108   %iv.next = getelementptr nusw i32, ptr %iv, i64 1
2109   %cmp = icmp ne ptr %iv.next, %end
2110   br i1 %cmp, label %loop, label %exit
2111 exit:
2112   ret void
2113 }
2114
2115 define void @addrec_gep_nusw_neg(ptr %p, ptr %end) {
2116 ; CHECK-LABEL: 'addrec_gep_nusw_neg'
2117 ; CHECK-NEXT:  Classifying expressions for: @addrec_gep_nusw_neg
2118 ; CHECK-NEXT:    %iv = phi ptr [ %p, %entry ], [ %iv.next, %loop ]
2119 ; CHECK-NEXT:    --> {%p,+,-4}<nw><%loop> U: full-set S: full-set Exits: ((-4 * ((-4 + (-1 * (ptrtoint ptr %end to i64)) + (ptrtoint ptr %p to i64)) /u 4)) + %p) LoopDispositions: { %loop: Computable }
2120 ; CHECK-NEXT:    %iv.next = getelementptr nusw i32, ptr %iv, i64 -1
2121 ; CHECK-NEXT:    --> {(-4 + %p),+,-4}<nw><%loop> U: full-set S: full-set Exits: (-4 + (-4 * ((-4 + (-1 * (ptrtoint ptr %end to i64)) + (ptrtoint ptr %p to i64)) /u 4)) + %p) LoopDispositions: { %loop: Computable }
2122 ; CHECK-NEXT:  Determining loop execution counts for: @addrec_gep_nusw_neg
2123 ; CHECK-NEXT:  Loop %loop: backedge-taken count is ((-4 + (-1 * (ptrtoint ptr %end to i64)) + (ptrtoint ptr %p to i64)) /u 4)
2124 ; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is i64 4611686018427387903
2125 ; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is ((-4 + (-1 * (ptrtoint ptr %end to i64)) + (ptrtoint ptr %p to i64)) /u 4)
2126 ; CHECK-NEXT:  Loop %loop: Trip multiple is 1
2127 ;
2128 entry:
2129   br label %loop
2130 loop:
2131   %iv = phi ptr [ %p, %entry], [ %iv.next, %loop ]
2132   %iv.next = getelementptr nusw i32, ptr %iv, i64 -1
2133   %cmp = icmp ne ptr %iv.next, %end
2134   br i1 %cmp, label %loop, label %exit
2135 exit:
2136   ret void
2137 }
2138
2139 define void @addrec_gep_nuw(ptr %p, ptr %end, i64 %step) {
2140 ; CHECK-LABEL: 'addrec_gep_nuw'
2141 ; CHECK-NEXT:  Classifying expressions for: @addrec_gep_nuw
2142 ; CHECK-NEXT:    %iv = phi ptr [ %p, %entry ], [ %iv.next, %loop ]
2143 ; CHECK-NEXT:    --> {%p,+,(4 * %step)<nuw>}<nuw><%loop> U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Computable }
2144 ; CHECK-NEXT:    %iv.next = getelementptr nuw i32, ptr %iv, i64 %step
2145 ; CHECK-NEXT:    --> {((4 * %step)<nuw> + %p)<nuw>,+,(4 * %step)<nuw>}<nuw><%loop> U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Computable }
2146 ; CHECK-NEXT:  Determining loop execution counts for: @addrec_gep_nuw
2147 ; CHECK-NEXT:  Loop %loop: Unpredictable backedge-taken count.
2148 ; CHECK-NEXT:  Loop %loop: Unpredictable constant max backedge-taken count.
2149 ; CHECK-NEXT:  Loop %loop: Unpredictable symbolic max backedge-taken count.
2150 ;
2151 entry:
2152   br label %loop
2153 loop:
2154   %iv = phi ptr [ %p, %entry], [ %iv.next, %loop ]
2155   %iv.next = getelementptr nuw i32, ptr %iv, i64 %step
2156   %cmp = icmp ne ptr %iv.next, %end
2157   br i1 %cmp, label %loop, label %exit
2158 exit:
2159   ret void
2160 }
2161
2162 define void @addrec_gep_nusw_nuw(ptr %p, ptr %end, i64 %step) {
2163 ; CHECK-LABEL: 'addrec_gep_nusw_nuw'
2164 ; CHECK-NEXT:  Classifying expressions for: @addrec_gep_nusw_nuw
2165 ; CHECK-NEXT:    %iv = phi ptr [ %p, %entry ], [ %iv.next, %loop ]
2166 ; CHECK-NEXT:    --> {%p,+,(4 * %step)<nuw><nsw>}<nuw><%loop> U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Computable }
2167 ; CHECK-NEXT:    %iv.next = getelementptr nusw nuw i32, ptr %iv, i64 %step
2168 ; CHECK-NEXT:    --> {((4 * %step)<nuw><nsw> + %p)<nuw>,+,(4 * %step)<nuw><nsw>}<nuw><%loop> U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Computable }
2169 ; CHECK-NEXT:  Determining loop execution counts for: @addrec_gep_nusw_nuw
2170 ; CHECK-NEXT:  Loop %loop: Unpredictable backedge-taken count.
2171 ; CHECK-NEXT:  Loop %loop: Unpredictable constant max backedge-taken count.
2172 ; CHECK-NEXT:  Loop %loop: Unpredictable symbolic max backedge-taken count.
2173 ;
2174 entry:
2175   br label %loop
2176 loop:
2177   %iv = phi ptr [ %p, %entry], [ %iv.next, %loop ]
2178   %iv.next = getelementptr nusw nuw i32, ptr %iv, i64 %step
2179   %cmp = icmp ne ptr %iv.next, %end
2180   br i1 %cmp, label %loop, label %exit
2181 exit:
2182   ret void
2183 }