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