llvm/test/Analysis/ScalarEvolution/mul-udiv-folds.ll

; NOTE: Assertions have been autogenerated by utils/update_analyze_test_checks.py UTC_ARGS: --version 5
; RUN: opt -passes='print<scalar-evolution>' -disable-output %s 2>&1 | FileCheck %s

declare void @use(ptr)

define void @udiv4_and_udiv2(i1 %c, ptr %A) {
; CHECK-LABEL: 'udiv4_and_udiv2'
; CHECK-NEXT:  Classifying expressions for: @udiv4_and_udiv2
; CHECK-NEXT:    %start = select i1 %c, i32 512, i32 0
; CHECK-NEXT:    --> %start U: [0,513) S: [0,513)
; CHECK-NEXT:    %div.2 = lshr i32 %start, 1
; CHECK-NEXT:    --> (%start /u 2) U: [0,257) S: [0,257)
; CHECK-NEXT:    %div.4 = lshr i32 %start, 2
; CHECK-NEXT:    --> (%start /u 4) U: [0,129) S: [0,129)
; CHECK-NEXT:    %iv.start = zext i32 %div.4 to i64
; CHECK-NEXT:    --> ((zext i32 %start to i64) /u 4) U: [0,129) S: [0,129)
; CHECK-NEXT:    %wide.trip.count = zext i32 %div.2 to i64
; CHECK-NEXT:    --> ((zext i32 %start to i64) /u 2) U: [0,257) S: [0,257)
; CHECK-NEXT:    %iv = phi i64 [ %iv.start, %entry ], [ %iv.next, %loop ]
; CHECK-NEXT:    --> {((zext i32 %start to i64) /u 4),+,1}<%loop> U: full-set S: full-set Exits: ((zext i32 %start to i64) /u 2) LoopDispositions: { %loop: Computable }
; CHECK-NEXT:    %gep.8 = getelementptr i8, ptr %A, i64 %iv
; CHECK-NEXT:    --> {(((zext i32 %start to i64) /u 4) + %A),+,1}<%loop> U: full-set S: full-set Exits: (((zext i32 %start to i64) /u 2) + %A) LoopDispositions: { %loop: Computable }
; CHECK-NEXT:    %gep.16 = getelementptr i16, ptr %A, i64 %iv
; CHECK-NEXT:    --> {(((zext i32 %start to i64) /u 2) + %A),+,2}<%loop> U: full-set S: full-set Exits: ((zext i32 %start to i64) + %A) LoopDispositions: { %loop: Computable }
; CHECK-NEXT:    %gep.32 = getelementptr i32, ptr %A, i64 %iv
; CHECK-NEXT:    --> {((zext i32 %start to i64) + %A),+,4}<%loop> U: full-set S: full-set Exits: ((2 * (zext i32 %start to i64))<nuw><nsw> + %A) LoopDispositions: { %loop: Computable }
; CHECK-NEXT:    %gep.40 = getelementptr <{ i32, i8 }>, ptr %A, i64 %iv
; CHECK-NEXT:    --> {((5 * ((zext i32 %start to i64) /u 4))<nuw><nsw> + %A),+,5}<%loop> U: full-set S: full-set Exits: ((5 * ((zext i32 %start to i64) /u 2))<nuw><nsw> + %A) LoopDispositions: { %loop: Computable }
; CHECK-NEXT:    %gep.48 = getelementptr <{ i32, i16 }>, ptr %A, i64 %iv
; CHECK-NEXT:    --> {((6 * ((zext i32 %start to i64) /u 4))<nuw><nsw> + %A),+,6}<%loop> U: full-set S: full-set Exits: ((6 * ((zext i32 %start to i64) /u 2))<nuw><nsw> + %A) LoopDispositions: { %loop: Computable }
; CHECK-NEXT:    %iv.next = add i64 %iv, 1
; CHECK-NEXT:    --> {(1 + ((zext i32 %start to i64) /u 4))<nuw><nsw>,+,1}<%loop> U: full-set S: full-set Exits: (1 + ((zext i32 %start to i64) /u 2))<nuw><nsw> LoopDispositions: { %loop: Computable }
; CHECK-NEXT:  Determining loop execution counts for: @udiv4_and_udiv2
; CHECK-NEXT:  Loop %loop: backedge-taken count is ((-1 * ((zext i32 %start to i64) /u 4))<nsw> + ((zext i32 %start to i64) /u 2))
; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is i64 -1
; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is ((-1 * ((zext i32 %start to i64) /u 4))<nsw> + ((zext i32 %start to i64) /u 2))
; CHECK-NEXT:  Loop %loop: Trip multiple is 1
;
entry:
  %start = select i1 %c, i32 512, i32 0
  %div.2 = lshr i32 %start, 1
  %div.4 = lshr i32 %start, 2
  %iv.start = zext i32 %div.4 to i64
  %wide.trip.count = zext i32 %div.2 to i64
  br label %loop

loop:
  %iv = phi i64 [ %iv.start, %entry ], [ %iv.next, %loop ]
  %gep.8 = getelementptr i8, ptr %A, i64 %iv
  call void @use(ptr %gep.8)
  %gep.16 = getelementptr i16, ptr %A, i64 %iv
  call void @use(ptr %gep.16)
  %gep.32 = getelementptr i32, ptr %A, i64 %iv
  call void @use(ptr %gep.32)
  %gep.40 = getelementptr <{i32, i8}>, ptr %A, i64 %iv
  call void @use(ptr %gep.40)
  %gep.48 = getelementptr <{i32, i16}>, ptr %A, i64 %iv
  call void @use(ptr %gep.48)
  %iv.next = add i64 %iv, 1
  %ec = icmp eq i64 %iv, %wide.trip.count
  br i1 %ec, label %exit, label %loop

exit:
  ret void
}
define void @udiv3_and_udiv5_mul_4(i1 %c, ptr %A) {
; CHECK-LABEL: 'udiv3_and_udiv5_mul_4'
; CHECK-NEXT:  Classifying expressions for: @udiv3_and_udiv5_mul_4
; CHECK-NEXT:    %start = select i1 %c, i32 512, i32 0
; CHECK-NEXT:    --> %start U: [0,513) S: [0,513)
; CHECK-NEXT:    %div.3 = udiv i32 %start, 3
; CHECK-NEXT:    --> (%start /u 3) U: [0,171) S: [0,171)
; CHECK-NEXT:    %div.5 = udiv i32 %start, 5
; CHECK-NEXT:    --> (%start /u 5) U: [0,103) S: [0,103)
; CHECK-NEXT:    %iv.start = zext i32 %div.5 to i64
; CHECK-NEXT:    --> ((zext i32 %start to i64) /u 5) U: [0,103) S: [0,103)
; CHECK-NEXT:    %wide.trip.count = zext i32 %div.3 to i64
; CHECK-NEXT:    --> ((zext i32 %start to i64) /u 3) U: [0,171) S: [0,171)
; CHECK-NEXT:    %iv = phi i64 [ %iv.start, %entry ], [ %iv.next, %loop ]
; CHECK-NEXT:    --> {((zext i32 %start to i64) /u 5),+,1}<%loop> U: full-set S: full-set Exits: ((zext i32 %start to i64) /u 3) LoopDispositions: { %loop: Computable }
; CHECK-NEXT:    %gep.8 = getelementptr i8, ptr %A, i64 %iv
; CHECK-NEXT:    --> {(((zext i32 %start to i64) /u 5) + %A),+,1}<%loop> U: full-set S: full-set Exits: (((zext i32 %start to i64) /u 3) + %A) LoopDispositions: { %loop: Computable }
; CHECK-NEXT:    %gep.16 = getelementptr i16, ptr %A, i64 %iv
; CHECK-NEXT:    --> {((2 * ((zext i32 %start to i64) /u 5))<nuw><nsw> + %A),+,2}<%loop> U: full-set S: full-set Exits: ((2 * ((zext i32 %start to i64) /u 3))<nuw><nsw> + %A) LoopDispositions: { %loop: Computable }
; CHECK-NEXT:    %gep.32 = getelementptr i32, ptr %A, i64 %iv
; CHECK-NEXT:    --> {((4 * ((zext i32 %start to i64) /u 5))<nuw><nsw> + %A),+,4}<%loop> U: full-set S: full-set Exits: ((4 * ((zext i32 %start to i64) /u 3))<nuw><nsw> + %A) LoopDispositions: { %loop: Computable }
; CHECK-NEXT:    %gep.40 = getelementptr <{ i32, i8 }>, ptr %A, i64 %iv
; CHECK-NEXT:    --> {((5 * ((zext i32 %start to i64) /u 5))<nuw><nsw> + %A),+,5}<%loop> U: full-set S: full-set Exits: ((5 * ((zext i32 %start to i64) /u 3))<nuw><nsw> + %A) LoopDispositions: { %loop: Computable }
; CHECK-NEXT:    %gep.48 = getelementptr <{ i32, i16 }>, ptr %A, i64 %iv
; CHECK-NEXT:    --> {((6 * ((zext i32 %start to i64) /u 5))<nuw><nsw> + %A),+,6}<%loop> U: full-set S: full-set Exits: ((6 * ((zext i32 %start to i64) /u 3))<nuw><nsw> + %A) LoopDispositions: { %loop: Computable }
; CHECK-NEXT:    %iv.next = add i64 %iv, 1
; CHECK-NEXT:    --> {(1 + ((zext i32 %start to i64) /u 5))<nuw><nsw>,+,1}<%loop> U: full-set S: full-set Exits: (1 + ((zext i32 %start to i64) /u 3))<nuw><nsw> LoopDispositions: { %loop: Computable }
; CHECK-NEXT:  Determining loop execution counts for: @udiv3_and_udiv5_mul_4
; CHECK-NEXT:  Loop %loop: backedge-taken count is ((-1 * ((zext i32 %start to i64) /u 5))<nsw> + ((zext i32 %start to i64) /u 3))
; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is i64 -1
; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is ((-1 * ((zext i32 %start to i64) /u 5))<nsw> + ((zext i32 %start to i64) /u 3))
; CHECK-NEXT:  Loop %loop: Trip multiple is 1
;
entry:
  %start = select i1 %c, i32 512, i32 0
  %div.3 = udiv i32 %start, 3
  %div.5 = udiv i32 %start, 5
  %iv.start = zext i32 %div.5 to i64
  %wide.trip.count = zext i32 %div.3 to i64
  br label %loop

loop:
  %iv = phi i64 [ %iv.start, %entry ], [ %iv.next, %loop ]
  %gep.8 = getelementptr i8, ptr %A, i64 %iv
  call void @use(ptr %gep.8)
  %gep.16 = getelementptr i16, ptr %A, i64 %iv
  call void @use(ptr %gep.16)
  %gep.32 = getelementptr i32, ptr %A, i64 %iv
  call void @use(ptr %gep.32)
  %gep.40 = getelementptr <{i32, i8}>, ptr %A, i64 %iv
  call void @use(ptr %gep.40)
  %gep.48 = getelementptr <{i32, i16}>, ptr %A, i64 %iv
  call void @use(ptr %gep.48)
  %iv.next = add i64 %iv, 1
  %ec = icmp eq i64 %iv, %wide.trip.count
  br i1 %ec, label %exit, label %loop

exit:
  ret void
}

declare void @use.i64(i64)

define void @dividend_not_known_multiple_of_divisor(i64 %x) {
; CHECK-LABEL: 'dividend_not_known_multiple_of_divisor'
; CHECK-NEXT:  Classifying expressions for: @dividend_not_known_multiple_of_divisor
; CHECK-NEXT:    %mul.2 = shl i64 %x, 1
; CHECK-NEXT:    --> (2 * %x) U: [0,-1) S: [-9223372036854775808,9223372036854775807)
; CHECK-NEXT:    %div.16 = lshr exact i64 %mul.2, 4
; CHECK-NEXT:    --> ((2 * %x) /u 16) U: [0,1152921504606846976) S: [0,1152921504606846976)
; CHECK-NEXT:    %m2 = and i64 %div.16, 1152921504606846974
; CHECK-NEXT:    --> (2 * ((2 * %x) /u 32))<nuw><nsw> U: [0,1152921504606846975) S: [0,1152921504606846975)
; CHECK-NEXT:    %m3 = mul i64 %div.16, 2
; CHECK-NEXT:    --> (2 * ((2 * %x) /u 16))<nuw><nsw> U: [0,2305843009213693951) S: [0,2305843009213693951)
; CHECK-NEXT:    %m4 = udiv i64 %m3, 4
; CHECK-NEXT:    --> ((2 * ((2 * %x) /u 16))<nuw><nsw> /u 4) U: [0,576460752303423488) S: [0,576460752303423488)
; CHECK-NEXT:  Determining loop execution counts for: @dividend_not_known_multiple_of_divisor
;
entry:
  %mul.2 = shl i64 %x, 1
  %div.16 = lshr exact i64 %mul.2, 4
  %m2 = and i64 %div.16, 1152921504606846974
  call void @use.i64(i64 %m2)

  %m3 = mul i64 %div.16, 2
  %m4 = udiv i64 %m3, 4
  call void @use.i64(i64 %m4)
  ret void
}

define void @btc_depends_on_div_mul(i64 %x) {
; CHECK-LABEL: 'btc_depends_on_div_mul'
; CHECK-NEXT:  Classifying expressions for: @btc_depends_on_div_mul
; CHECK-NEXT:    %mul.2 = shl i64 %x, 1
; CHECK-NEXT:    --> (2 * %x) U: [0,-1) S: [-9223372036854775808,9223372036854775807)
; CHECK-NEXT:    %div.16 = lshr exact i64 %mul.2, 4
; CHECK-NEXT:    --> ((2 * %x) /u 16) U: [0,1152921504606846976) S: [0,1152921504606846976)
; CHECK-NEXT:    %masked = and i64 %div.16, 1152921504606846974
; CHECK-NEXT:    --> (2 * ((2 * %x) /u 32))<nuw><nsw> U: [0,1152921504606846975) S: [0,1152921504606846975)
; CHECK-NEXT:    %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop ]
; CHECK-NEXT:    --> {0,+,2}<%loop> U: [0,-1) S: [-9223372036854775808,9223372036854775807) Exits: (-2 + (2 * ((2 * %x) /u 32))<nuw><nsw>)<nsw> LoopDispositions: { %loop: Computable }
; CHECK-NEXT:    %iv.next = add i64 %iv, 2
; CHECK-NEXT:    --> {2,+,2}<%loop> U: [0,-1) S: [-9223372036854775808,9223372036854775807) Exits: (2 * ((2 * %x) /u 32))<nuw><nsw> LoopDispositions: { %loop: Computable }
; CHECK-NEXT:  Determining loop execution counts for: @btc_depends_on_div_mul
; CHECK-NEXT:  Loop %loop: backedge-taken count is ((-2 + (2 * ((2 * %x) /u 32))<nuw><nsw>)<nsw> /u 2)
; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is i64 9223372036854775807
; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is ((-2 + (2 * ((2 * %x) /u 32))<nuw><nsw>)<nsw> /u 2)
; CHECK-NEXT:  Loop %loop: Trip multiple is 1
;
entry:
  %mul.2 = shl i64 %x, 1
  %div.16 = lshr exact i64 %mul.2, 4
  %masked = and i64 %div.16, 1152921504606846974
  br label %loop

loop:
  %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop ]
  call void @use.i64(i64 %iv)
  %iv.next = add i64 %iv, 2
  %ec = icmp eq i64 %iv.next, %masked
  br i1 %ec, label %exit, label %loop

exit:
  ret void
}

define noundef i64 @udiv_mul_common_vscale_factor(i64 %a, i64 %b) {
; CHECK-LABEL: 'udiv_mul_common_vscale_factor'
; CHECK-NEXT:  Classifying expressions for: @udiv_mul_common_vscale_factor
; CHECK-NEXT:    %vs = call i64 @llvm.vscale.i64()
; CHECK-NEXT:    --> vscale U: [1,0) S: [1,0)
; CHECK-NEXT:    %a.vs = mul i64 %a, %vs
; CHECK-NEXT:    --> (vscale * %a) U: full-set S: full-set
; CHECK-NEXT:    %b.vs = mul i64 %b, %vs
; CHECK-NEXT:    --> (vscale * %b) U: full-set S: full-set
; CHECK-NEXT:    %div = udiv i64 %a.vs, %b.vs
; CHECK-NEXT:    --> ((vscale * %a) /u (vscale * %b)) U: full-set S: full-set
; CHECK-NEXT:  Determining loop execution counts for: @udiv_mul_common_vscale_factor
;
  %vs = call i64 @llvm.vscale()
  %a.vs = mul i64 %a, %vs
  %b.vs = mul i64 %b, %vs
  %div = udiv i64 %a.vs, %b.vs
  ret i64 %div
}

define noundef i64 @udiv_mul_nuw_common_vscale_factor(i64 %a, i64 %b) {
; CHECK-LABEL: 'udiv_mul_nuw_common_vscale_factor'
; CHECK-NEXT:  Classifying expressions for: @udiv_mul_nuw_common_vscale_factor
; CHECK-NEXT:    %vs = call i64 @llvm.vscale.i64()
; CHECK-NEXT:    --> vscale U: [1,0) S: [1,0)
; CHECK-NEXT:    %a.vs = mul nuw i64 %a, %vs
; CHECK-NEXT:    --> (vscale * %a)<nuw> U: full-set S: full-set
; CHECK-NEXT:    %b.vs = mul nuw i64 %b, %vs
; CHECK-NEXT:    --> (vscale * %b)<nuw> U: full-set S: full-set
; CHECK-NEXT:    %div = udiv i64 %a.vs, %b.vs
; CHECK-NEXT:    --> (%a /u %b) U: full-set S: full-set
; CHECK-NEXT:  Determining loop execution counts for: @udiv_mul_nuw_common_vscale_factor
;
  %vs = call i64 @llvm.vscale()
  %a.vs = mul nuw i64 %a, %vs
  %b.vs = mul nuw i64 %b, %vs
  %div = udiv i64 %a.vs, %b.vs
  ret i64 %div
}