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(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; 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 %arg, label %exit, label %loop 22exit: 23 ret void 24} 25 26; Deliberate overflow doesn't change range 27define 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; 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 %arg, label %exit, label %loop 45exit: 46 ret void 47} 48 49 50define 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; 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 %arg, label %exit, label %loop 68exit: 69 ret void 70} 71 72define 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; 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 %arg, label %exit, label %loop 90exit: 91 ret void 92} 93 94; Same as previous, but swapped operands to phi 95define 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; 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 %arg, 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, 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; 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 %arg, 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, 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; 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 %arg, label %exit, label %loop 161exit: 162 ret void 163} 164 165 166define 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; 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 %arg, label %exit, label %loop 184exit: 185 ret void 186} 187 188; use trip count to refine 189define 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; 206entry: 207 br label %loop 208loop: 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 215exit: 216 ret void 217} 218 219; Variable shift with a tight upper bound 220define 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; 239entry: 240 %shiftamt = select i1 %c, i64 1, i64 0 241 br label %loop 242loop: 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 249exit: 250 ret void 251} 252 253; edge case on max value not overflowing 254define 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; 271entry: 272 br label %loop 273loop: 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 280exit: 281 ret void 282} 283 284; other side of edge case from previous test 285define 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; 302entry: 303 br label %loop 304loop: 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 311exit: 312 ret void 313} 314 315; Loop varying (but tightly bounded) shift amount 316define 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; 335entry: 336 br label %loop 337loop: 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 345exit: 346 ret void 347} 348 349; Unanalyzeable shift amount 350define 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; 367entry: 368 br label %loop 369loop: 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 376exit: 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). 382define 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; 391entry: 392 ret void 393 394unreachable1: 395 br label %unreachable_nonloop 396unreachable2: 397 br label %unreachable_nonloop 398unreachable_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). 406define 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; 418entry: 419 br label %header 420 421header: 422 br label %for.cond2295 423 424for.cond2295: 425 %p_58.addr.1 = phi i32 [ undef, %header ], [ %sub2629, %unreachable ] 426 br i1 %arg, label %if.then2321, label %header 427 428if.then2321: 429 ret void 430 431unreachable: 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. 439define 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; 448bb: 449 br label %bb1 450 451bb1: ; preds = %bb3, %bb 452 %tmp = phi i32 [ 2, %bb ], [ %tmp2, %bb3 ] 453 %tmp2 = add nuw nsw i32 %tmp, 1 454 ret void 455 456bb3: ; 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. 463define 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; 475bb: 476 br label %loop 477 478loop: 479 br label %bb1 480bb1: ; preds = %bb3, %loop 481 %tmp = phi i32 [ 2, %loop ], [ %tmp2, %bb3 ] 482 %tmp2 = add nuw nsw i32 %tmp, 1 483 br label %loop 484 485bb3: ; 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 493define 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; 510entry: 511 br label %loop 512loop: 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 519exit: 520 ret void 521} 522 523define 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; 540entry: 541 br label %loop 542loop: 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 549exit: 550 ret void 551} 552 553define 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; 572entry: 573 %start = sext i1 %a to i8 574 br label %loop 575loop: 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 582exit: 583 ret void 584} 585 586define 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; 603entry: 604 br label %loop 605loop: 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 612exit: 613 ret void 614} 615 616define 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; 633entry: 634 br label %loop 635loop: 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 642exit: 643 ret void 644} 645 646define 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; 663entry: 664 br label %loop 665loop: 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 672exit: 673 ret void 674} 675 676define 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; 695entry: 696 %start = sext i1 %a to i8 697 br label %loop 698loop: 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 705exit: 706 ret void 707} 708 709define 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; 726entry: 727 br label %loop 728loop: 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 735exit: 736 ret void 737} 738 739 740define 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; 757entry: 758 br label %loop 759loop: 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 766exit: 767 ret void 768} 769 770; Starting value is chosen not to be near power of 2 771define 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; 788entry: 789 br label %loop 790loop: 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 797exit: 798 ret void 799} 800 801define 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; 818entry: 819 br label %loop 820loop: 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 827exit: 828 ret void 829} 830