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

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