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