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 4define 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; 16entry: 17 br label %loop 18loop: 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 22exit: 23 ret void 24} 25 26; Deliberate overflow doesn't change range 27define 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; 39entry: 40 br label %loop 41loop: 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 45exit: 46 ret void 47} 48 49 50define 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; 62entry: 63 br label %loop 64loop: 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 68exit: 69 ret void 70} 71 72define 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; 84entry: 85 br label %loop 86loop: 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 90exit: 91 ret void 92} 93 94; Same as previous, but swapped operands to phi 95define 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; 107entry: 108 br label %loop 109loop: 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 113exit: 114 ret void 115} 116 117 118; negative case for when start is unknown 119define 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; 131entry: 132 br label %loop 133loop: 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 137exit: 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.) 143define 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; 155entry: 156 br label %loop 157loop: 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 161exit: 162 ret void 163} 164 165 166define 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; 178entry: 179 br label %loop 180loop: 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 184exit: 185 ret void 186} 187 188; use trip count to refine 189define 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; 207entry: 208 br label %loop 209loop: 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 216exit: 217 ret void 218} 219 220; Variable shift with a tight upper bound 221define 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; 241entry: 242 %shiftamt = select i1 %c, i64 1, i64 0 243 br label %loop 244loop: 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 251exit: 252 ret void 253} 254 255; edge case on max value not overflowing 256define 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; 274entry: 275 br label %loop 276loop: 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 283exit: 284 ret void 285} 286 287; other side of edge case from previous test 288define 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; 306entry: 307 br label %loop 308loop: 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 315exit: 316 ret void 317} 318 319; Loop varying (but tightly bounded) shift amount 320define 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; 340entry: 341 br label %loop 342loop: 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 350exit: 351 ret void 352} 353 354; Unanalyzeable shift amount 355define 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; 373entry: 374 br label %loop 375loop: 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 382exit: 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). 388define 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; 397entry: 398 ret void 399 400unreachable1: 401 br label %unreachable_nonloop 402unreachable2: 403 br label %unreachable_nonloop 404unreachable_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). 412define 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; 424entry: 425 br label %header 426 427header: 428 br label %for.cond2295 429 430for.cond2295: 431 %p_58.addr.1 = phi i32 [ undef, %header ], [ %sub2629, %unreachable ] 432 br i1 undef, label %if.then2321, label %header 433 434if.then2321: 435 ret void 436 437unreachable: 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. 445define 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; 454bb: 455 br label %bb1 456 457bb1: ; preds = %bb3, %bb 458 %tmp = phi i32 [ 2, %bb ], [ %tmp2, %bb3 ] 459 %tmp2 = add nuw nsw i32 %tmp, 1 460 ret void 461 462bb3: ; 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. 469define 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; 481bb: 482 br label %loop 483 484loop: 485 br label %bb1 486bb1: ; preds = %bb3, %loop 487 %tmp = phi i32 [ 2, %loop ], [ %tmp2, %bb3 ] 488 %tmp2 = add nuw nsw i32 %tmp, 1 489 br label %loop 490 491bb3: ; 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 499define 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; 517entry: 518 br label %loop 519loop: 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 526exit: 527 ret void 528} 529 530define 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; 548entry: 549 br label %loop 550loop: 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 557exit: 558 ret void 559} 560 561define 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; 581entry: 582 %start = sext i1 %a to i8 583 br label %loop 584loop: 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 591exit: 592 ret void 593} 594 595define 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; 613entry: 614 br label %loop 615loop: 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 622exit: 623 ret void 624} 625 626define 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; 644entry: 645 br label %loop 646loop: 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 653exit: 654 ret void 655} 656 657define 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; 675entry: 676 br label %loop 677loop: 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 684exit: 685 ret void 686} 687 688define 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; 708entry: 709 %start = sext i1 %a to i8 710 br label %loop 711loop: 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 718exit: 719 ret void 720} 721 722define 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; 740entry: 741 br label %loop 742loop: 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 749exit: 750 ret void 751} 752 753 754define 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; 772entry: 773 br label %loop 774loop: 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 781exit: 782 ret void 783} 784 785; Starting value is chosen not to be near power of 2 786define 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; 804entry: 805 br label %loop 806loop: 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 813exit: 814 ret void 815} 816 817define 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; 835entry: 836 br label %loop 837loop: 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 844exit: 845 ret void 846} 847