llvm/test/Analysis/ScalarEvolution/shift-recurrences.ll

   1 ; NOTE: Assertions have been autogenerated by utils/update_analyze_test_checks.py
   2 ; RUN: opt -disable-output "-passes=print<scalar-evolution>" < %s 2>&1 | FileCheck %s
   3
   4 define void @test_lshr() {
   5 ; CHECK-LABEL: 'test_lshr'
   6 ; CHECK-NEXT:  Classifying expressions for: @test_lshr
   7 ; CHECK-NEXT:    %iv.lshr = phi i64 [ 1023, %entry ], [ %iv.lshr.next, %loop ]
   8 ; CHECK-NEXT:    --> %iv.lshr U: [0,1024) S: [0,1024) Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
   9 ; CHECK-NEXT:    %iv.lshr.next = lshr i64 %iv.lshr, 1
  10 ; CHECK-NEXT:    --> (%iv.lshr /u 2) U: [0,512) S: [0,512) Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
  11 ; CHECK-NEXT:  Determining loop execution counts for: @test_lshr
  12 ; CHECK-NEXT:  Loop %loop: Unpredictable backedge-taken count.
  13 ; CHECK-NEXT:  Loop %loop: Unpredictable constant max backedge-taken count.
  14 ; CHECK-NEXT:  Loop %loop: Unpredictable symbolic max backedge-taken count.
  15 ; CHECK-NEXT:  Loop %loop: Unpredictable predicated backedge-taken count.
  16 ;
  17 entry:
  18   br label %loop
  19 loop:
  20   %iv.lshr = phi i64 [1023, %entry], [%iv.lshr.next, %loop]
  21   %iv.lshr.next = lshr i64 %iv.lshr, 1
  22   br i1 undef, label %exit, label %loop
  23 exit:
  24   ret void
  25 }
  26
  27 ; Deliberate overflow doesn't change range
  28 define void @test_lshr2() {
  29 ; CHECK-LABEL: 'test_lshr2'
  30 ; CHECK-NEXT:  Classifying expressions for: @test_lshr2
  31 ; CHECK-NEXT:    %iv.lshr = phi i64 [ 1023, %entry ], [ %iv.lshr.next, %loop ]
  32 ; CHECK-NEXT:    --> %iv.lshr U: [0,1024) S: [0,1024) Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
  33 ; CHECK-NEXT:    %iv.lshr.next = lshr i64 %iv.lshr, 4
  34 ; CHECK-NEXT:    --> (%iv.lshr /u 16) U: [0,64) S: [0,64) Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
  35 ; CHECK-NEXT:  Determining loop execution counts for: @test_lshr2
  36 ; CHECK-NEXT:  Loop %loop: Unpredictable backedge-taken count.
  37 ; CHECK-NEXT:  Loop %loop: Unpredictable constant max backedge-taken count.
  38 ; CHECK-NEXT:  Loop %loop: Unpredictable symbolic max backedge-taken count.
  39 ; CHECK-NEXT:  Loop %loop: Unpredictable predicated backedge-taken count.
  40 ;
  41 entry:
  42   br label %loop
  43 loop:
  44   %iv.lshr = phi i64 [1023, %entry], [%iv.lshr.next, %loop]
  45   %iv.lshr.next = lshr i64 %iv.lshr, 4
  46   br i1 undef, label %exit, label %loop
  47 exit:
  48   ret void
  49 }
  50
  51
  52 define void @test_ashr_zeros() {
  53 ; CHECK-LABEL: 'test_ashr_zeros'
  54 ; CHECK-NEXT:  Classifying expressions for: @test_ashr_zeros
  55 ; CHECK-NEXT:    %iv.ashr = phi i64 [ 1023, %entry ], [ %iv.ashr.next, %loop ]
  56 ; CHECK-NEXT:    --> %iv.ashr U: [0,1024) S: [0,1024) Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
  57 ; CHECK-NEXT:    %iv.ashr.next = ashr i64 %iv.ashr, 1
  58 ; CHECK-NEXT:    --> %iv.ashr.next U: [0,512) S: [0,512) Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
  59 ; CHECK-NEXT:  Determining loop execution counts for: @test_ashr_zeros
  60 ; CHECK-NEXT:  Loop %loop: Unpredictable backedge-taken count.
  61 ; CHECK-NEXT:  Loop %loop: Unpredictable constant max backedge-taken count.
  62 ; CHECK-NEXT:  Loop %loop: Unpredictable symbolic max backedge-taken count.
  63 ; CHECK-NEXT:  Loop %loop: Unpredictable predicated backedge-taken count.
  64 ;
  65 entry:
  66   br label %loop
  67 loop:
  68   %iv.ashr = phi i64 [1023, %entry], [%iv.ashr.next, %loop]
  69   %iv.ashr.next = ashr i64 %iv.ashr, 1
  70   br i1 undef, label %exit, label %loop
  71 exit:
  72   ret void
  73 }
  74
  75 define void @test_ashr_ones() {
  76 ; CHECK-LABEL: 'test_ashr_ones'
  77 ; CHECK-NEXT:  Classifying expressions for: @test_ashr_ones
  78 ; CHECK-NEXT:    %iv.ashr = phi i64 [ -1023, %entry ], [ %iv.ashr.next, %loop ]
  79 ; CHECK-NEXT:    --> %iv.ashr U: [-1023,0) S: [-1023,0) Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
  80 ; CHECK-NEXT:    %iv.ashr.next = ashr i64 %iv.ashr, 1
  81 ; CHECK-NEXT:    --> %iv.ashr.next U: [-512,0) S: [-512,0) Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
  82 ; CHECK-NEXT:  Determining loop execution counts for: @test_ashr_ones
  83 ; CHECK-NEXT:  Loop %loop: Unpredictable backedge-taken count.
  84 ; CHECK-NEXT:  Loop %loop: Unpredictable constant max backedge-taken count.
  85 ; CHECK-NEXT:  Loop %loop: Unpredictable symbolic max backedge-taken count.
  86 ; CHECK-NEXT:  Loop %loop: Unpredictable predicated backedge-taken count.
  87 ;
  88 entry:
  89   br label %loop
  90 loop:
  91   %iv.ashr = phi i64 [-1023, %entry], [%iv.ashr.next, %loop]
  92   %iv.ashr.next = ashr i64 %iv.ashr, 1
  93   br i1 undef, label %exit, label %loop
  94 exit:
  95   ret void
  96 }
  97
  98 ; Same as previous, but swapped operands to phi
  99 define void @test_ashr_ones2() {
 100 ; CHECK-LABEL: 'test_ashr_ones2'
 101 ; CHECK-NEXT:  Classifying expressions for: @test_ashr_ones2
 102 ; CHECK-NEXT:    %iv.ashr = phi i64 [ %iv.ashr.next, %loop ], [ -1023, %entry ]
 103 ; CHECK-NEXT:    --> %iv.ashr U: [-1023,0) S: [-1023,0) Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
 104 ; CHECK-NEXT:    %iv.ashr.next = ashr i64 %iv.ashr, 1
 105 ; CHECK-NEXT:    --> %iv.ashr.next U: [-512,0) S: [-512,0) Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
 106 ; CHECK-NEXT:  Determining loop execution counts for: @test_ashr_ones2
 107 ; CHECK-NEXT:  Loop %loop: Unpredictable backedge-taken count.
 108 ; CHECK-NEXT:  Loop %loop: Unpredictable constant max backedge-taken count.
 109 ; CHECK-NEXT:  Loop %loop: Unpredictable symbolic max backedge-taken count.
 110 ; CHECK-NEXT:  Loop %loop: Unpredictable predicated backedge-taken count.
 111 ;
 112 entry:
 113   br label %loop
 114 loop:
 115   %iv.ashr = phi i64 [%iv.ashr.next, %loop], [-1023, %entry]
 116   %iv.ashr.next = ashr i64 %iv.ashr, 1
 117   br i1 undef, label %exit, label %loop
 118 exit:
 119   ret void
 120 }
 121
 122
 123 ; negative case for when start is unknown
 124 define void @test_ashr_unknown(i64 %start) {
 125 ; CHECK-LABEL: 'test_ashr_unknown'
 126 ; CHECK-NEXT:  Classifying expressions for: @test_ashr_unknown
 127 ; CHECK-NEXT:    %iv.ashr = phi i64 [ %start, %entry ], [ %iv.ashr.next, %loop ]
 128 ; CHECK-NEXT:    --> %iv.ashr U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
 129 ; CHECK-NEXT:    %iv.ashr.next = ashr i64 %iv.ashr, 1
 130 ; CHECK-NEXT:    --> %iv.ashr.next U: [-4611686018427387904,4611686018427387904) S: [-4611686018427387904,4611686018427387904) Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
 131 ; CHECK-NEXT:  Determining loop execution counts for: @test_ashr_unknown
 132 ; CHECK-NEXT:  Loop %loop: Unpredictable backedge-taken count.
 133 ; CHECK-NEXT:  Loop %loop: Unpredictable constant max backedge-taken count.
 134 ; CHECK-NEXT:  Loop %loop: Unpredictable symbolic max backedge-taken count.
 135 ; CHECK-NEXT:  Loop %loop: Unpredictable predicated backedge-taken count.
 136 ;
 137 entry:
 138   br label %loop
 139 loop:
 140   %iv.ashr = phi i64 [%start, %entry], [%iv.ashr.next, %loop]
 141   %iv.ashr.next = ashr i64 %iv.ashr, 1
 142   br i1 undef, label %exit, label %loop
 143 exit:
 144   ret void
 145 }
 146
 147 ; Negative case where we don't have a (shift) recurrence because the operands
 148 ; of the ashr are swapped.  (This does end up being a divide recurrence.)
 149 define void @test_ashr_wrong_op(i64 %start) {
 150 ; CHECK-LABEL: 'test_ashr_wrong_op'
 151 ; CHECK-NEXT:  Classifying expressions for: @test_ashr_wrong_op
 152 ; CHECK-NEXT:    %iv.ashr = phi i64 [ %start, %entry ], [ %iv.ashr.next, %loop ]
 153 ; CHECK-NEXT:    --> %iv.ashr U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
 154 ; CHECK-NEXT:    %iv.ashr.next = ashr i64 1, %iv.ashr
 155 ; CHECK-NEXT:    --> %iv.ashr.next U: [0,2) S: [0,2) Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
 156 ; CHECK-NEXT:  Determining loop execution counts for: @test_ashr_wrong_op
 157 ; CHECK-NEXT:  Loop %loop: Unpredictable backedge-taken count.
 158 ; CHECK-NEXT:  Loop %loop: Unpredictable constant max backedge-taken count.
 159 ; CHECK-NEXT:  Loop %loop: Unpredictable symbolic max backedge-taken count.
 160 ; CHECK-NEXT:  Loop %loop: Unpredictable predicated backedge-taken count.
 161 ;
 162 entry:
 163   br label %loop
 164 loop:
 165   %iv.ashr = phi i64 [%start, %entry], [%iv.ashr.next, %loop]
 166   %iv.ashr.next = ashr i64 1, %iv.ashr
 167   br i1 undef, label %exit, label %loop
 168 exit:
 169   ret void
 170 }
 171
 172
 173 define void @test_shl() {
 174 ; CHECK-LABEL: 'test_shl'
 175 ; CHECK-NEXT:  Classifying expressions for: @test_shl
 176 ; CHECK-NEXT:    %iv.shl = phi i64 [ 8, %entry ], [ %iv.shl.next, %loop ]
 177 ; CHECK-NEXT:    --> %iv.shl U: [0,-7) S: [-9223372036854775808,9223372036854775793) Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
 178 ; CHECK-NEXT:    %iv.shl.next = shl i64 %iv.shl, 1
 179 ; CHECK-NEXT:    --> (2 * %iv.shl) U: [0,-15) S: [-9223372036854775808,9223372036854775793) Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
 180 ; CHECK-NEXT:  Determining loop execution counts for: @test_shl
 181 ; CHECK-NEXT:  Loop %loop: Unpredictable backedge-taken count.
 182 ; CHECK-NEXT:  Loop %loop: Unpredictable constant max backedge-taken count.
 183 ; CHECK-NEXT:  Loop %loop: Unpredictable symbolic max backedge-taken count.
 184 ; CHECK-NEXT:  Loop %loop: Unpredictable predicated backedge-taken count.
 185 ;
 186 entry:
 187   br label %loop
 188 loop:
 189   %iv.shl = phi i64 [8, %entry], [%iv.shl.next, %loop]
 190   %iv.shl.next = shl i64 %iv.shl, 1
 191   br i1 undef, label %exit, label %loop
 192 exit:
 193   ret void
 194 }
 195
 196 ; use trip count to refine
 197 define void @test_shl2() {
 198 ; CHECK-LABEL: 'test_shl2'
 199 ; CHECK-NEXT:  Classifying expressions for: @test_shl2
 200 ; CHECK-NEXT:    %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop ]
 201 ; CHECK-NEXT:    --> {0,+,1}<nuw><nsw><%loop> U: [0,5) S: [0,5) Exits: 4 LoopDispositions: { %loop: Computable }
 202 ; CHECK-NEXT:    %iv.shl = phi i64 [ 4, %entry ], [ %iv.shl.next, %loop ]
 203 ; CHECK-NEXT:    --> %iv.shl U: [4,65) S: [4,65) Exits: 64 LoopDispositions: { %loop: Variant }
 204 ; CHECK-NEXT:    %iv.next = add i64 %iv, 1
 205 ; CHECK-NEXT:    --> {1,+,1}<nuw><nsw><%loop> U: [1,6) S: [1,6) Exits: 5 LoopDispositions: { %loop: Computable }
 206 ; CHECK-NEXT:    %iv.shl.next = shl i64 %iv.shl, 1
 207 ; CHECK-NEXT:    --> (2 * %iv.shl)<nuw><nsw> U: [8,129) S: [8,129) Exits: 128 LoopDispositions: { %loop: Variant }
 208 ; CHECK-NEXT:  Determining loop execution counts for: @test_shl2
 209 ; CHECK-NEXT:  Loop %loop: backedge-taken count is 4
 210 ; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is 4
 211 ; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is 4
 212 ; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is 4
 213 ; CHECK-NEXT:   Predicates:
 214 ; CHECK-NEXT:  Loop %loop: Trip multiple is 5
 215 ;
 216 entry:
 217   br label %loop
 218 loop:
 219   %iv = phi i64 [0, %entry], [%iv.next, %loop]
 220   %iv.shl = phi i64 [4, %entry], [%iv.shl.next, %loop]
 221   %iv.next = add i64 %iv, 1
 222   %iv.shl.next = shl i64 %iv.shl, 1
 223   %cmp = icmp eq i64 %iv, 4
 224   br i1 %cmp, label %exit, label %loop
 225 exit:
 226   ret void
 227 }
 228
 229 ; Variable shift with a tight upper bound
 230 define void @test_shl3(i1 %c) {
 231 ; CHECK-LABEL: 'test_shl3'
 232 ; CHECK-NEXT:  Classifying expressions for: @test_shl3
 233 ; CHECK-NEXT:    %shiftamt = select i1 %c, i64 1, i64 0
 234 ; CHECK-NEXT:    --> %shiftamt U: [0,2) S: [0,2)
 235 ; CHECK-NEXT:    %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop ]
 236 ; CHECK-NEXT:    --> {0,+,1}<nuw><nsw><%loop> U: [0,5) S: [0,5) Exits: 4 LoopDispositions: { %loop: Computable }
 237 ; CHECK-NEXT:    %iv.shl = phi i64 [ 4, %entry ], [ %iv.shl.next, %loop ]
 238 ; CHECK-NEXT:    --> %iv.shl U: [4,65) S: [4,65) Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
 239 ; CHECK-NEXT:    %iv.next = add i64 %iv, 1
 240 ; CHECK-NEXT:    --> {1,+,1}<nuw><nsw><%loop> U: [1,6) S: [1,6) Exits: 5 LoopDispositions: { %loop: Computable }
 241 ; CHECK-NEXT:    %iv.shl.next = shl i64 %iv.shl, %shiftamt
 242 ; CHECK-NEXT:    --> %iv.shl.next U: [0,-3) S: [-9223372036854775808,9223372036854775805) Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
 243 ; CHECK-NEXT:  Determining loop execution counts for: @test_shl3
 244 ; CHECK-NEXT:  Loop %loop: backedge-taken count is 4
 245 ; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is 4
 246 ; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is 4
 247 ; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is 4
 248 ; CHECK-NEXT:   Predicates:
 249 ; CHECK-NEXT:  Loop %loop: Trip multiple is 5
 250 ;
 251 entry:
 252   %shiftamt = select i1 %c, i64 1, i64 0
 253   br label %loop
 254 loop:
 255   %iv = phi i64 [0, %entry], [%iv.next, %loop]
 256   %iv.shl = phi i64 [4, %entry], [%iv.shl.next, %loop]
 257   %iv.next = add i64 %iv, 1
 258   %iv.shl.next = shl i64 %iv.shl, %shiftamt
 259   %cmp = icmp eq i64 %iv, 4
 260   br i1 %cmp, label %exit, label %loop
 261 exit:
 262   ret void
 263 }
 264
 265 ; edge case on max value not overflowing
 266 define void @test_shl4() {
 267 ; CHECK-LABEL: 'test_shl4'
 268 ; CHECK-NEXT:  Classifying expressions for: @test_shl4
 269 ; CHECK-NEXT:    %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop ]
 270 ; CHECK-NEXT:    --> {0,+,1}<nuw><nsw><%loop> U: [0,61) S: [0,61) Exits: 60 LoopDispositions: { %loop: Computable }
 271 ; CHECK-NEXT:    %iv.shl = phi i64 [ 4, %entry ], [ %iv.shl.next, %loop ]
 272 ; CHECK-NEXT:    --> %iv.shl U: [4,4611686018427387905) S: [4,4611686018427387905) Exits: 4611686018427387904 LoopDispositions: { %loop: Variant }
 273 ; CHECK-NEXT:    %iv.next = add i64 %iv, 1
 274 ; CHECK-NEXT:    --> {1,+,1}<nuw><nsw><%loop> U: [1,62) S: [1,62) Exits: 61 LoopDispositions: { %loop: Computable }
 275 ; CHECK-NEXT:    %iv.shl.next = shl i64 %iv.shl, 1
 276 ; CHECK-NEXT:    --> (2 * %iv.shl)<nuw> U: [8,-9223372036854775807) S: [-9223372036854775808,9223372036854775801) Exits: -9223372036854775808 LoopDispositions: { %loop: Variant }
 277 ; CHECK-NEXT:  Determining loop execution counts for: @test_shl4
 278 ; CHECK-NEXT:  Loop %loop: backedge-taken count is 60
 279 ; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is 60
 280 ; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is 60
 281 ; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is 60
 282 ; CHECK-NEXT:   Predicates:
 283 ; CHECK-NEXT:  Loop %loop: Trip multiple is 61
 284 ;
 285 entry:
 286   br label %loop
 287 loop:
 288   %iv = phi i64 [0, %entry], [%iv.next, %loop]
 289   %iv.shl = phi i64 [4, %entry], [%iv.shl.next, %loop]
 290   %iv.next = add i64 %iv, 1
 291   %iv.shl.next = shl i64 %iv.shl, 1
 292   %cmp = icmp eq i64 %iv, 60
 293   br i1 %cmp, label %exit, label %loop
 294 exit:
 295   ret void
 296 }
 297
 298 ; other side of edge case from previous test
 299 define void @test_shl5() {
 300 ; CHECK-LABEL: 'test_shl5'
 301 ; CHECK-NEXT:  Classifying expressions for: @test_shl5
 302 ; CHECK-NEXT:    %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop ]
 303 ; CHECK-NEXT:    --> {0,+,1}<nuw><nsw><%loop> U: [0,62) S: [0,62) Exits: 61 LoopDispositions: { %loop: Computable }
 304 ; CHECK-NEXT:    %iv.shl = phi i64 [ 4, %entry ], [ %iv.shl.next, %loop ]
 305 ; CHECK-NEXT:    --> %iv.shl U: [0,-3) S: [-9223372036854775808,9223372036854775801) Exits: -9223372036854775808 LoopDispositions: { %loop: Variant }
 306 ; CHECK-NEXT:    %iv.next = add i64 %iv, 1
 307 ; CHECK-NEXT:    --> {1,+,1}<nuw><nsw><%loop> U: [1,63) S: [1,63) Exits: 62 LoopDispositions: { %loop: Computable }
 308 ; CHECK-NEXT:    %iv.shl.next = shl i64 %iv.shl, 1
 309 ; CHECK-NEXT:    --> (2 * %iv.shl) U: [0,-7) S: [-9223372036854775808,9223372036854775801) Exits: 0 LoopDispositions: { %loop: Variant }
 310 ; CHECK-NEXT:  Determining loop execution counts for: @test_shl5
 311 ; CHECK-NEXT:  Loop %loop: backedge-taken count is 61
 312 ; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is 61
 313 ; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is 61
 314 ; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is 61
 315 ; CHECK-NEXT:   Predicates:
 316 ; CHECK-NEXT:  Loop %loop: Trip multiple is 62
 317 ;
 318 entry:
 319   br label %loop
 320 loop:
 321   %iv = phi i64 [0, %entry], [%iv.next, %loop]
 322   %iv.shl = phi i64 [4, %entry], [%iv.shl.next, %loop]
 323   %iv.next = add i64 %iv, 1
 324   %iv.shl.next = shl i64 %iv.shl, 1
 325   %cmp = icmp eq i64 %iv, 61
 326   br i1 %cmp, label %exit, label %loop
 327 exit:
 328   ret void
 329 }
 330
 331 ; Loop varying (but tightly bounded) shift amount
 332 define void @test_shl6(i1 %c) {
 333 ; CHECK-LABEL: 'test_shl6'
 334 ; CHECK-NEXT:  Classifying expressions for: @test_shl6
 335 ; CHECK-NEXT:    %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop ]
 336 ; CHECK-NEXT:    --> {0,+,1}<nuw><nsw><%loop> U: [0,5) S: [0,5) Exits: 4 LoopDispositions: { %loop: Computable }
 337 ; CHECK-NEXT:    %iv.shl = phi i64 [ 4, %entry ], [ %iv.shl.next, %loop ]
 338 ; CHECK-NEXT:    --> %iv.shl U: [4,65) S: [4,65) Exits: 16 LoopDispositions: { %loop: Variant }
 339 ; CHECK-NEXT:    %iv.next = add i64 %iv, 1
 340 ; CHECK-NEXT:    --> {1,+,1}<nuw><nsw><%loop> U: [1,6) S: [1,6) Exits: 5 LoopDispositions: { %loop: Computable }
 341 ; CHECK-NEXT:    %shiftamt = and i64 %iv, 1
 342 ; CHECK-NEXT:    --> (zext i1 {false,+,true}<%loop> to i64) U: [0,2) S: [0,2) Exits: 0 LoopDispositions: { %loop: Computable }
 343 ; CHECK-NEXT:    %iv.shl.next = shl i64 %iv.shl, %shiftamt
 344 ; CHECK-NEXT:    --> %iv.shl.next U: [0,-3) S: [-9223372036854775808,9223372036854775805) Exits: 16 LoopDispositions: { %loop: Variant }
 345 ; CHECK-NEXT:  Determining loop execution counts for: @test_shl6
 346 ; CHECK-NEXT:  Loop %loop: backedge-taken count is 4
 347 ; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is 4
 348 ; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is 4
 349 ; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is 4
 350 ; CHECK-NEXT:   Predicates:
 351 ; CHECK-NEXT:  Loop %loop: Trip multiple is 5
 352 ;
 353 entry:
 354   br label %loop
 355 loop:
 356   %iv = phi i64 [0, %entry], [%iv.next, %loop]
 357   %iv.shl = phi i64 [4, %entry], [%iv.shl.next, %loop]
 358   %iv.next = add i64 %iv, 1
 359   %shiftamt = and i64 %iv, 1
 360   %iv.shl.next = shl i64 %iv.shl, %shiftamt
 361   %cmp = icmp eq i64 %iv, 4
 362   br i1 %cmp, label %exit, label %loop
 363 exit:
 364   ret void
 365 }
 366
 367 ; Unanalyzeable shift amount
 368 define void @test_shl7(i1 %c, i64 %shiftamt) {
 369 ; CHECK-LABEL: 'test_shl7'
 370 ; CHECK-NEXT:  Classifying expressions for: @test_shl7
 371 ; CHECK-NEXT:    %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop ]
 372 ; CHECK-NEXT:    --> {0,+,1}<nuw><nsw><%loop> U: [0,5) S: [0,5) Exits: 4 LoopDispositions: { %loop: Computable }
 373 ; CHECK-NEXT:    %iv.shl = phi i64 [ 4, %entry ], [ %iv.shl.next, %loop ]
 374 ; CHECK-NEXT:    --> %iv.shl U: [0,-3) S: [-9223372036854775808,9223372036854775805) Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
 375 ; CHECK-NEXT:    %iv.next = add i64 %iv, 1
 376 ; CHECK-NEXT:    --> {1,+,1}<nuw><nsw><%loop> U: [1,6) S: [1,6) Exits: 5 LoopDispositions: { %loop: Computable }
 377 ; CHECK-NEXT:    %iv.shl.next = shl i64 %iv.shl, %shiftamt
 378 ; CHECK-NEXT:    --> %iv.shl.next U: [0,-3) S: [-9223372036854775808,9223372036854775805) Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
 379 ; CHECK-NEXT:  Determining loop execution counts for: @test_shl7
 380 ; CHECK-NEXT:  Loop %loop: backedge-taken count is 4
 381 ; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is 4
 382 ; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is 4
 383 ; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is 4
 384 ; CHECK-NEXT:   Predicates:
 385 ; CHECK-NEXT:  Loop %loop: Trip multiple is 5
 386 ;
 387 entry:
 388   br label %loop
 389 loop:
 390   %iv = phi i64 [0, %entry], [%iv.next, %loop]
 391   %iv.shl = phi i64 [4, %entry], [%iv.shl.next, %loop]
 392   %iv.next = add i64 %iv, 1
 393   %iv.shl.next = shl i64 %iv.shl, %shiftamt
 394   %cmp = icmp eq i64 %iv, 4
 395   br i1 %cmp, label %exit, label %loop
 396 exit:
 397   ret void
 398 }
 399
 400 ; Corner case where phi is not in a loop because it is in unreachable
 401 ; code (which loopinfo ignores, but simple recurrence matching does not).
 402 define void @unreachable_phi() {
 403 ; CHECK-LABEL: 'unreachable_phi'
 404 ; CHECK-NEXT:  Classifying expressions for: @unreachable_phi
 405 ; CHECK-NEXT:    %p_58.addr.1 = phi i32 [ undef, %unreachable1 ], [ %sub2629, %unreachable2 ]
 406 ; CHECK-NEXT:    --> poison U: full-set S: full-set
 407 ; CHECK-NEXT:    %sub2629 = sub i32 %p_58.addr.1, 1
 408 ; CHECK-NEXT:    --> poison U: full-set S: full-set
 409 ; CHECK-NEXT:  Determining loop execution counts for: @unreachable_phi
 410 ;
 411 entry:
 412   ret void
 413
 414 unreachable1:
 415   br label %unreachable_nonloop
 416 unreachable2:
 417   br label %unreachable_nonloop
 418 unreachable_nonloop:
 419   %p_58.addr.1 = phi i32 [ undef, %unreachable1 ], [ %sub2629, %unreachable2 ]
 420   %sub2629 = sub i32 %p_58.addr.1, 1
 421   unreachable
 422 }
 423
 424 ; Corner case where phi is not in loop header because binop is in unreachable
 425 ; code (which loopinfo ignores, but simple recurrence matching does not).
 426 define void @unreachable_binop() {
 427 ; CHECK-LABEL: 'unreachable_binop'
 428 ; CHECK-NEXT:  Classifying expressions for: @unreachable_binop
 429 ; CHECK-NEXT:    %p_58.addr.1 = phi i32 [ undef, %header ], [ %sub2629, %unreachable ]
 430 ; CHECK-NEXT:    --> %p_58.addr.1 U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %header: Variant }
 431 ; CHECK-NEXT:    %sub2629 = sub i32 %p_58.addr.1, 1
 432 ; CHECK-NEXT:    --> poison U: full-set S: full-set
 433 ; CHECK-NEXT:  Determining loop execution counts for: @unreachable_binop
 434 ; CHECK-NEXT:  Loop %header: Unpredictable backedge-taken count.
 435 ; CHECK-NEXT:  Loop %header: Unpredictable constant max backedge-taken count.
 436 ; CHECK-NEXT:  Loop %header: Unpredictable symbolic max backedge-taken count.
 437 ; CHECK-NEXT:  Loop %header: Unpredictable predicated backedge-taken count.
 438 ;
 439 entry:
 440   br label %header
 441
 442 header:
 443   br label %for.cond2295
 444
 445 for.cond2295:
 446   %p_58.addr.1 = phi i32 [ undef, %header ], [ %sub2629, %unreachable ]
 447   br i1 undef, label %if.then2321, label %header
 448
 449 if.then2321:
 450   ret void
 451
 452 unreachable:
 453   %sub2629 = sub i32 %p_58.addr.1, 1
 454   br label %for.cond2295
 455 }
 456
 457 ; Was pr49856.  We can match the recurrence without a loop
 458 ; since dominance collapses in unreachable code.  Conceptually,
 459 ; this is a recurrence which only executes one iteration.
 460 define void @nonloop_recurrence() {
 461 ; CHECK-LABEL: 'nonloop_recurrence'
 462 ; CHECK-NEXT:  Classifying expressions for: @nonloop_recurrence
 463 ; CHECK-NEXT:    %tmp = phi i32 [ 2, %bb ], [ %tmp2, %bb3 ]
 464 ; CHECK-NEXT:    --> %tmp U: [1,-2147483648) S: [0,-2147483648)
 465 ; CHECK-NEXT:    %tmp2 = add nuw nsw i32 %tmp, 1
 466 ; CHECK-NEXT:    --> (1 + %tmp)<nuw> U: [1,-2147483647) S: [1,-2147483647)
 467 ; CHECK-NEXT:  Determining loop execution counts for: @nonloop_recurrence
 468 ;
 469 bb:
 470   br label %bb1
 471
 472 bb1:                                              ; preds = %bb3, %bb
 473   %tmp = phi i32 [ 2, %bb ], [ %tmp2, %bb3 ]
 474   %tmp2 = add nuw nsw i32 %tmp, 1
 475   ret void
 476
 477 bb3:                                              ; No predecessors!
 478   br label %bb1
 479 }
 480
 481 ; Tweak of pr49856 test case - analogous, but there is a loop
 482 ; it's trip count simply doesn't relate to the single iteration
 483 ; "recurrence" we found.
 484 define void @nonloop_recurrence_2() {
 485 ; CHECK-LABEL: 'nonloop_recurrence_2'
 486 ; CHECK-NEXT:  Classifying expressions for: @nonloop_recurrence_2
 487 ; CHECK-NEXT:    %tmp = phi i32 [ 2, %loop ], [ %tmp2, %bb3 ]
 488 ; CHECK-NEXT:    --> %tmp U: [1,-2147483648) S: [0,-2147483648) Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
 489 ; CHECK-NEXT:    %tmp2 = add nuw nsw i32 %tmp, 1
 490 ; CHECK-NEXT:    --> (1 + %tmp)<nuw> U: [1,-2147483647) S: [1,-2147483647) Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
 491 ; CHECK-NEXT:  Determining loop execution counts for: @nonloop_recurrence_2
 492 ; CHECK-NEXT:  Loop %loop: <multiple exits> Unpredictable backedge-taken count.
 493 ; CHECK-NEXT:  Loop %loop: Unpredictable constant max backedge-taken count.
 494 ; CHECK-NEXT:  Loop %loop: Unpredictable symbolic max backedge-taken count.
 495 ; CHECK-NEXT:  Loop %loop: Unpredictable predicated backedge-taken count.
 496 ;
 497 bb:
 498   br label %loop
 499
 500 loop:
 501   br label %bb1
 502 bb1:                                              ; preds = %bb3, %loop
 503   %tmp = phi i32 [ 2, %loop ], [ %tmp2, %bb3 ]
 504   %tmp2 = add nuw nsw i32 %tmp, 1
 505   br label %loop
 506
 507 bb3:                                              ; No predecessors!
 508   br label %bb1
 509 }
 510
 511
 512 ; Next batch of tests show where we can get tighter ranges on ashr/lshr
 513 ; by using the trip count information on the loop.
 514
 515 define void @test_ashr_tc_positive() {
 516 ; CHECK-LABEL: 'test_ashr_tc_positive'
 517 ; CHECK-NEXT:  Classifying expressions for: @test_ashr_tc_positive
 518 ; CHECK-NEXT:    %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop ]
 519 ; CHECK-NEXT:    --> {0,+,1}<nuw><nsw><%loop> U: [0,5) S: [0,5) Exits: 4 LoopDispositions: { %loop: Computable }
 520 ; CHECK-NEXT:    %iv.ashr = phi i64 [ 1023, %entry ], [ %iv.ashr.next, %loop ]
 521 ; CHECK-NEXT:    --> %iv.ashr U: [63,1024) S: [63,1024) Exits: 63 LoopDispositions: { %loop: Variant }
 522 ; CHECK-NEXT:    %iv.next = add i64 %iv, 1
 523 ; CHECK-NEXT:    --> {1,+,1}<nuw><nsw><%loop> U: [1,6) S: [1,6) Exits: 5 LoopDispositions: { %loop: Computable }
 524 ; CHECK-NEXT:    %iv.ashr.next = ashr i64 %iv.ashr, 1
 525 ; CHECK-NEXT:    --> %iv.ashr.next U: [0,512) S: [0,512) Exits: 31 LoopDispositions: { %loop: Variant }
 526 ; CHECK-NEXT:  Determining loop execution counts for: @test_ashr_tc_positive
 527 ; CHECK-NEXT:  Loop %loop: backedge-taken count is 4
 528 ; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is 4
 529 ; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is 4
 530 ; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is 4
 531 ; CHECK-NEXT:   Predicates:
 532 ; CHECK-NEXT:  Loop %loop: Trip multiple is 5
 533 ;
 534 entry:
 535   br label %loop
 536 loop:
 537   %iv = phi i64 [0, %entry], [%iv.next, %loop]
 538   %iv.ashr = phi i64 [1023, %entry], [%iv.ashr.next, %loop]
 539   %iv.next = add i64 %iv, 1
 540   %iv.ashr.next = ashr i64 %iv.ashr, 1
 541   %cmp = icmp eq i64 %iv, 4
 542   br i1 %cmp, label %exit, label %loop
 543 exit:
 544   ret void
 545 }
 546
 547 define void @test_ashr_tc_negative() {
 548 ; CHECK-LABEL: 'test_ashr_tc_negative'
 549 ; CHECK-NEXT:  Classifying expressions for: @test_ashr_tc_negative
 550 ; CHECK-NEXT:    %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop ]
 551 ; CHECK-NEXT:    --> {0,+,1}<nuw><nsw><%loop> U: [0,5) S: [0,5) Exits: 4 LoopDispositions: { %loop: Computable }
 552 ; CHECK-NEXT:    %iv.ashr = phi i8 [ -128, %entry ], [ %iv.ashr.next, %loop ]
 553 ; CHECK-NEXT:    --> %iv.ashr U: [-128,-7) S: [-128,-7) Exits: -8 LoopDispositions: { %loop: Variant }
 554 ; CHECK-NEXT:    %iv.next = add i64 %iv, 1
 555 ; CHECK-NEXT:    --> {1,+,1}<nuw><nsw><%loop> U: [1,6) S: [1,6) Exits: 5 LoopDispositions: { %loop: Computable }
 556 ; CHECK-NEXT:    %iv.ashr.next = ashr i8 %iv.ashr, 1
 557 ; CHECK-NEXT:    --> %iv.ashr.next U: [-64,0) S: [-64,0) Exits: -4 LoopDispositions: { %loop: Variant }
 558 ; CHECK-NEXT:  Determining loop execution counts for: @test_ashr_tc_negative
 559 ; CHECK-NEXT:  Loop %loop: backedge-taken count is 4
 560 ; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is 4
 561 ; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is 4
 562 ; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is 4
 563 ; CHECK-NEXT:   Predicates:
 564 ; CHECK-NEXT:  Loop %loop: Trip multiple is 5
 565 ;
 566 entry:
 567   br label %loop
 568 loop:
 569   %iv = phi i64 [0, %entry], [%iv.next, %loop]
 570   %iv.ashr = phi i8 [128, %entry], [%iv.ashr.next, %loop]
 571   %iv.next = add i64 %iv, 1
 572   %iv.ashr.next = ashr i8 %iv.ashr, 1
 573   %cmp = icmp eq i64 %iv, 4
 574   br i1 %cmp, label %exit, label %loop
 575 exit:
 576   ret void
 577 }
 578
 579 define void @test_ashr_tc_either(i1 %a) {
 580 ; CHECK-LABEL: 'test_ashr_tc_either'
 581 ; CHECK-NEXT:  Classifying expressions for: @test_ashr_tc_either
 582 ; CHECK-NEXT:    %start = sext i1 %a to i8
 583 ; CHECK-NEXT:    --> (sext i1 %a to i8) U: [-1,1) S: [-1,1)
 584 ; CHECK-NEXT:    %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop ]
 585 ; CHECK-NEXT:    --> {0,+,1}<nuw><nsw><%loop> U: [0,61) S: [0,61) Exits: 60 LoopDispositions: { %loop: Computable }
 586 ; CHECK-NEXT:    %iv.ashr = phi i8 [ %start, %entry ], [ %iv.ashr.next, %loop ]
 587 ; CHECK-NEXT:    --> %iv.ashr U: [-16,16) S: [-16,16) Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
 588 ; CHECK-NEXT:    %iv.next = add i64 %iv, 1
 589 ; CHECK-NEXT:    --> {1,+,1}<nuw><nsw><%loop> U: [1,62) S: [1,62) Exits: 61 LoopDispositions: { %loop: Computable }
 590 ; CHECK-NEXT:    %iv.ashr.next = ashr i8 %iv.ashr, 1
 591 ; CHECK-NEXT:    --> %iv.ashr.next U: [-16,16) S: [-16,16) Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
 592 ; CHECK-NEXT:  Determining loop execution counts for: @test_ashr_tc_either
 593 ; CHECK-NEXT:  Loop %loop: backedge-taken count is 60
 594 ; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is 60
 595 ; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is 60
 596 ; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is 60
 597 ; CHECK-NEXT:   Predicates:
 598 ; CHECK-NEXT:  Loop %loop: Trip multiple is 61
 599 ;
 600 entry:
 601   %start = sext i1 %a to i8
 602   br label %loop
 603 loop:
 604   %iv = phi i64 [0, %entry], [%iv.next, %loop]
 605   %iv.ashr = phi i8 [%start, %entry], [%iv.ashr.next, %loop]
 606   %iv.next = add i64 %iv, 1
 607   %iv.ashr.next = ashr i8 %iv.ashr, 1
 608   %cmp = icmp eq i64 %iv, 60
 609   br i1 %cmp, label %exit, label %loop
 610 exit:
 611   ret void
 612 }
 613
 614 define void @test_ashr_zero_shift() {
 615 ; CHECK-LABEL: 'test_ashr_zero_shift'
 616 ; CHECK-NEXT:  Classifying expressions for: @test_ashr_zero_shift
 617 ; CHECK-NEXT:    %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop ]
 618 ; CHECK-NEXT:    --> {0,+,1}<nuw><nsw><%loop> U: [0,5) S: [0,5) Exits: 4 LoopDispositions: { %loop: Computable }
 619 ; CHECK-NEXT:    %iv.ashr = phi i64 [ 1023, %entry ], [ %iv.ashr.next, %loop ]
 620 ; CHECK-NEXT:    --> %iv.ashr U: [1023,1024) S: [1023,1024) Exits: 1023 LoopDispositions: { %loop: Variant }
 621 ; CHECK-NEXT:    %iv.next = add i64 %iv, 1
 622 ; CHECK-NEXT:    --> {1,+,1}<nuw><nsw><%loop> U: [1,6) S: [1,6) Exits: 5 LoopDispositions: { %loop: Computable }
 623 ; CHECK-NEXT:    %iv.ashr.next = ashr i64 %iv.ashr, 0
 624 ; CHECK-NEXT:    --> %iv.ashr U: [1023,1024) S: [1023,1024) Exits: 1023 LoopDispositions: { %loop: Variant }
 625 ; CHECK-NEXT:  Determining loop execution counts for: @test_ashr_zero_shift
 626 ; CHECK-NEXT:  Loop %loop: backedge-taken count is 4
 627 ; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is 4
 628 ; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is 4
 629 ; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is 4
 630 ; CHECK-NEXT:   Predicates:
 631 ; CHECK-NEXT:  Loop %loop: Trip multiple is 5
 632 ;
 633 entry:
 634   br label %loop
 635 loop:
 636   %iv = phi i64 [0, %entry], [%iv.next, %loop]
 637   %iv.ashr = phi i64 [1023, %entry], [%iv.ashr.next, %loop]
 638   %iv.next = add i64 %iv, 1
 639   %iv.ashr.next = ashr i64 %iv.ashr, 0
 640   %cmp = icmp eq i64 %iv, 4
 641   br i1 %cmp, label %exit, label %loop
 642 exit:
 643   ret void
 644 }
 645
 646 define void @test_lshr_tc_positive() {
 647 ; CHECK-LABEL: 'test_lshr_tc_positive'
 648 ; CHECK-NEXT:  Classifying expressions for: @test_lshr_tc_positive
 649 ; CHECK-NEXT:    %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop ]
 650 ; CHECK-NEXT:    --> {0,+,1}<nuw><nsw><%loop> U: [0,5) S: [0,5) Exits: 4 LoopDispositions: { %loop: Computable }
 651 ; CHECK-NEXT:    %iv.lshr = phi i64 [ 1023, %entry ], [ %iv.lshr.next, %loop ]
 652 ; CHECK-NEXT:    --> %iv.lshr U: [63,1024) S: [63,1024) Exits: 63 LoopDispositions: { %loop: Variant }
 653 ; CHECK-NEXT:    %iv.next = add i64 %iv, 1
 654 ; CHECK-NEXT:    --> {1,+,1}<nuw><nsw><%loop> U: [1,6) S: [1,6) Exits: 5 LoopDispositions: { %loop: Computable }
 655 ; CHECK-NEXT:    %iv.lshr.next = lshr i64 %iv.lshr, 1
 656 ; CHECK-NEXT:    --> (%iv.lshr /u 2) U: [31,512) S: [31,512) Exits: 31 LoopDispositions: { %loop: Variant }
 657 ; CHECK-NEXT:  Determining loop execution counts for: @test_lshr_tc_positive
 658 ; CHECK-NEXT:  Loop %loop: backedge-taken count is 4
 659 ; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is 4
 660 ; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is 4
 661 ; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is 4
 662 ; CHECK-NEXT:   Predicates:
 663 ; CHECK-NEXT:  Loop %loop: Trip multiple is 5
 664 ;
 665 entry:
 666   br label %loop
 667 loop:
 668   %iv = phi i64 [0, %entry], [%iv.next, %loop]
 669   %iv.lshr = phi i64 [1023, %entry], [%iv.lshr.next, %loop]
 670   %iv.next = add i64 %iv, 1
 671   %iv.lshr.next = lshr i64 %iv.lshr, 1
 672   %cmp = icmp eq i64 %iv, 4
 673   br i1 %cmp, label %exit, label %loop
 674 exit:
 675   ret void
 676 }
 677
 678 define void @test_lshr_tc_negative() {
 679 ; CHECK-LABEL: 'test_lshr_tc_negative'
 680 ; CHECK-NEXT:  Classifying expressions for: @test_lshr_tc_negative
 681 ; CHECK-NEXT:    %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop ]
 682 ; CHECK-NEXT:    --> {0,+,1}<nuw><nsw><%loop> U: [0,5) S: [0,5) Exits: 4 LoopDispositions: { %loop: Computable }
 683 ; CHECK-NEXT:    %iv.lshr = phi i8 [ -1, %entry ], [ %iv.lshr.next, %loop ]
 684 ; CHECK-NEXT:    --> %iv.lshr U: [15,0) S: [-1,-128) Exits: 15 LoopDispositions: { %loop: Variant }
 685 ; CHECK-NEXT:    %iv.next = add i64 %iv, 1
 686 ; CHECK-NEXT:    --> {1,+,1}<nuw><nsw><%loop> U: [1,6) S: [1,6) Exits: 5 LoopDispositions: { %loop: Computable }
 687 ; CHECK-NEXT:    %iv.lshr.next = lshr i8 %iv.lshr, 1
 688 ; CHECK-NEXT:    --> (%iv.lshr /u 2) U: [7,-128) S: [7,-128) Exits: 7 LoopDispositions: { %loop: Variant }
 689 ; CHECK-NEXT:  Determining loop execution counts for: @test_lshr_tc_negative
 690 ; CHECK-NEXT:  Loop %loop: backedge-taken count is 4
 691 ; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is 4
 692 ; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is 4
 693 ; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is 4
 694 ; CHECK-NEXT:   Predicates:
 695 ; CHECK-NEXT:  Loop %loop: Trip multiple is 5
 696 ;
 697 entry:
 698   br label %loop
 699 loop:
 700   %iv = phi i64 [0, %entry], [%iv.next, %loop]
 701   %iv.lshr = phi i8 [-1, %entry], [%iv.lshr.next, %loop]
 702   %iv.next = add i64 %iv, 1
 703   %iv.lshr.next = lshr i8 %iv.lshr, 1
 704   %cmp = icmp eq i64 %iv, 4
 705   br i1 %cmp, label %exit, label %loop
 706 exit:
 707   ret void
 708 }
 709
 710 define void @test_lshr_tc_either(i1 %a) {
 711 ; CHECK-LABEL: 'test_lshr_tc_either'
 712 ; CHECK-NEXT:  Classifying expressions for: @test_lshr_tc_either
 713 ; CHECK-NEXT:    %start = sext i1 %a to i8
 714 ; CHECK-NEXT:    --> (sext i1 %a to i8) U: [-1,1) S: [-1,1)
 715 ; CHECK-NEXT:    %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop ]
 716 ; CHECK-NEXT:    --> {0,+,1}<nuw><nsw><%loop> U: [0,5) S: [0,5) Exits: 4 LoopDispositions: { %loop: Computable }
 717 ; CHECK-NEXT:    %iv.lshr = phi i8 [ %start, %entry ], [ %iv.lshr.next, %loop ]
 718 ; CHECK-NEXT:    --> %iv.lshr U: [-1,-128) S: [-1,-128) Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
 719 ; CHECK-NEXT:    %iv.next = add i64 %iv, 1
 720 ; CHECK-NEXT:    --> {1,+,1}<nuw><nsw><%loop> U: [1,6) S: [1,6) Exits: 5 LoopDispositions: { %loop: Computable }
 721 ; CHECK-NEXT:    %iv.lshr.next = lshr i8 %iv.lshr, 1
 722 ; CHECK-NEXT:    --> (%iv.lshr /u 2) U: [0,-128) S: [0,-128) Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
 723 ; CHECK-NEXT:  Determining loop execution counts for: @test_lshr_tc_either
 724 ; CHECK-NEXT:  Loop %loop: backedge-taken count is 4
 725 ; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is 4
 726 ; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is 4
 727 ; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is 4
 728 ; CHECK-NEXT:   Predicates:
 729 ; CHECK-NEXT:  Loop %loop: Trip multiple is 5
 730 ;
 731 entry:
 732   %start = sext i1 %a to i8
 733   br label %loop
 734 loop:
 735   %iv = phi i64 [0, %entry], [%iv.next, %loop]
 736   %iv.lshr = phi i8 [%start, %entry], [%iv.lshr.next, %loop]
 737   %iv.next = add i64 %iv, 1
 738   %iv.lshr.next = lshr i8 %iv.lshr, 1
 739   %cmp = icmp eq i64 %iv, 4
 740   br i1 %cmp, label %exit, label %loop
 741 exit:
 742   ret void
 743 }
 744
 745 define void @test_lshr_zero_shift() {
 746 ; CHECK-LABEL: 'test_lshr_zero_shift'
 747 ; CHECK-NEXT:  Classifying expressions for: @test_lshr_zero_shift
 748 ; CHECK-NEXT:    %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop ]
 749 ; CHECK-NEXT:    --> {0,+,1}<nuw><nsw><%loop> U: [0,5) S: [0,5) Exits: 4 LoopDispositions: { %loop: Computable }
 750 ; CHECK-NEXT:    %iv.lshr = phi i64 [ 1023, %entry ], [ %iv.lshr.next, %loop ]
 751 ; CHECK-NEXT:    --> %iv.lshr U: [1023,1024) S: [1023,1024) Exits: 1023 LoopDispositions: { %loop: Variant }
 752 ; CHECK-NEXT:    %iv.next = add i64 %iv, 1
 753 ; CHECK-NEXT:    --> {1,+,1}<nuw><nsw><%loop> U: [1,6) S: [1,6) Exits: 5 LoopDispositions: { %loop: Computable }
 754 ; CHECK-NEXT:    %iv.lshr.next = lshr i64 %iv.lshr, 0
 755 ; CHECK-NEXT:    --> %iv.lshr U: [1023,1024) S: [1023,1024) Exits: 1023 LoopDispositions: { %loop: Variant }
 756 ; CHECK-NEXT:  Determining loop execution counts for: @test_lshr_zero_shift
 757 ; CHECK-NEXT:  Loop %loop: backedge-taken count is 4
 758 ; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is 4
 759 ; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is 4
 760 ; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is 4
 761 ; CHECK-NEXT:   Predicates:
 762 ; CHECK-NEXT:  Loop %loop: Trip multiple is 5
 763 ;
 764 entry:
 765   br label %loop
 766 loop:
 767   %iv = phi i64 [0, %entry], [%iv.next, %loop]
 768   %iv.lshr = phi i64 [1023, %entry], [%iv.lshr.next, %loop]
 769   %iv.next = add i64 %iv, 1
 770   %iv.lshr.next = lshr i64 %iv.lshr, 0
 771   %cmp = icmp eq i64 %iv, 4
 772   br i1 %cmp, label %exit, label %loop
 773 exit:
 774   ret void
 775 }
 776
 777
 778 define void @test_lshr_power_of_2_start() {
 779 ; CHECK-LABEL: 'test_lshr_power_of_2_start'
 780 ; CHECK-NEXT:  Classifying expressions for: @test_lshr_power_of_2_start
 781 ; CHECK-NEXT:    %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop ]
 782 ; CHECK-NEXT:    --> {0,+,1}<nuw><nsw><%loop> U: [0,5) S: [0,5) Exits: 4 LoopDispositions: { %loop: Computable }
 783 ; CHECK-NEXT:    %iv.lshr = phi i64 [ 1024, %entry ], [ %iv.lshr.next, %loop ]
 784 ; CHECK-NEXT:    --> %iv.lshr U: [4,1025) S: [4,1025) Exits: 4 LoopDispositions: { %loop: Variant }
 785 ; CHECK-NEXT:    %iv.next = add i64 %iv, 1
 786 ; CHECK-NEXT:    --> {1,+,1}<nuw><nsw><%loop> U: [1,6) S: [1,6) Exits: 5 LoopDispositions: { %loop: Computable }
 787 ; CHECK-NEXT:    %iv.lshr.next = lshr i64 %iv.lshr, 2
 788 ; CHECK-NEXT:    --> (%iv.lshr /u 4) U: [1,257) S: [1,257) Exits: 1 LoopDispositions: { %loop: Variant }
 789 ; CHECK-NEXT:  Determining loop execution counts for: @test_lshr_power_of_2_start
 790 ; CHECK-NEXT:  Loop %loop: backedge-taken count is 4
 791 ; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is 4
 792 ; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is 4
 793 ; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is 4
 794 ; CHECK-NEXT:   Predicates:
 795 ; CHECK-NEXT:  Loop %loop: Trip multiple is 5
 796 ;
 797 entry:
 798   br label %loop
 799 loop:
 800   %iv = phi i64 [0, %entry], [%iv.next, %loop]
 801   %iv.lshr = phi i64 [1024, %entry], [%iv.lshr.next, %loop]
 802   %iv.next = add i64 %iv, 1
 803   %iv.lshr.next = lshr i64 %iv.lshr, 2
 804   %cmp = icmp eq i64 %iv, 4
 805   br i1 %cmp, label %exit, label %loop
 806 exit:
 807   ret void
 808 }
 809
 810 ; Starting value is chosen not to be near power of 2
 811 define void @test_lshr_arbitrary_start() {
 812 ; CHECK-LABEL: 'test_lshr_arbitrary_start'
 813 ; CHECK-NEXT:  Classifying expressions for: @test_lshr_arbitrary_start
 814 ; CHECK-NEXT:    %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop ]
 815 ; CHECK-NEXT:    --> {0,+,1}<nuw><nsw><%loop> U: [0,5) S: [0,5) Exits: 4 LoopDispositions: { %loop: Computable }
 816 ; CHECK-NEXT:    %iv.lshr = phi i64 [ 957, %entry ], [ %iv.lshr.next, %loop ]
 817 ; CHECK-NEXT:    --> %iv.lshr U: [3,958) S: [3,958) Exits: 3 LoopDispositions: { %loop: Variant }
 818 ; CHECK-NEXT:    %iv.next = add i64 %iv, 1
 819 ; CHECK-NEXT:    --> {1,+,1}<nuw><nsw><%loop> U: [1,6) S: [1,6) Exits: 5 LoopDispositions: { %loop: Computable }
 820 ; CHECK-NEXT:    %iv.lshr.next = lshr i64 %iv.lshr, 2
 821 ; CHECK-NEXT:    --> (%iv.lshr /u 4) U: [0,240) S: [0,240) Exits: 0 LoopDispositions: { %loop: Variant }
 822 ; CHECK-NEXT:  Determining loop execution counts for: @test_lshr_arbitrary_start
 823 ; CHECK-NEXT:  Loop %loop: backedge-taken count is 4
 824 ; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is 4
 825 ; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is 4
 826 ; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is 4
 827 ; CHECK-NEXT:   Predicates:
 828 ; CHECK-NEXT:  Loop %loop: Trip multiple is 5
 829 ;
 830 entry:
 831   br label %loop
 832 loop:
 833   %iv = phi i64 [0, %entry], [%iv.next, %loop]
 834   %iv.lshr = phi i64 [957, %entry], [%iv.lshr.next, %loop]
 835   %iv.next = add i64 %iv, 1
 836   %iv.lshr.next = lshr i64 %iv.lshr, 2
 837   %cmp = icmp eq i64 %iv, 4
 838   br i1 %cmp, label %exit, label %loop
 839 exit:
 840   ret void
 841 }
 842
 843 define void @test_lshr_start_power_of_2_plus_one() {
 844 ; CHECK-LABEL: 'test_lshr_start_power_of_2_plus_one'
 845 ; CHECK-NEXT:  Classifying expressions for: @test_lshr_start_power_of_2_plus_one
 846 ; CHECK-NEXT:    %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop ]
 847 ; CHECK-NEXT:    --> {0,+,1}<nuw><nsw><%loop> U: [0,5) S: [0,5) Exits: 4 LoopDispositions: { %loop: Computable }
 848 ; CHECK-NEXT:    %iv.lshr = phi i64 [ 1025, %entry ], [ %iv.lshr.next, %loop ]
 849 ; CHECK-NEXT:    --> %iv.lshr U: [4,1026) S: [4,1026) Exits: 4 LoopDispositions: { %loop: Variant }
 850 ; CHECK-NEXT:    %iv.next = add i64 %iv, 1
 851 ; CHECK-NEXT:    --> {1,+,1}<nuw><nsw><%loop> U: [1,6) S: [1,6) Exits: 5 LoopDispositions: { %loop: Computable }
 852 ; CHECK-NEXT:    %iv.lshr.next = lshr i64 %iv.lshr, 2
 853 ; CHECK-NEXT:    --> (%iv.lshr /u 4) U: [1,257) S: [1,257) Exits: 1 LoopDispositions: { %loop: Variant }
 854 ; CHECK-NEXT:  Determining loop execution counts for: @test_lshr_start_power_of_2_plus_one
 855 ; CHECK-NEXT:  Loop %loop: backedge-taken count is 4
 856 ; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is 4
 857 ; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is 4
 858 ; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is 4
 859 ; CHECK-NEXT:   Predicates:
 860 ; CHECK-NEXT:  Loop %loop: Trip multiple is 5
 861 ;
 862 entry:
 863   br label %loop
 864 loop:
 865   %iv = phi i64 [0, %entry], [%iv.next, %loop]
 866   %iv.lshr = phi i64 [1025, %entry], [%iv.lshr.next, %loop]
 867   %iv.next = add i64 %iv, 1
 868   %iv.lshr.next = lshr i64 %iv.lshr, 2
 869   %cmp = icmp eq i64 %iv, 4
 870   br i1 %cmp, label %exit, label %loop
 871 exit:
 872   ret void
 873 }