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