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