llvm/test/Analysis/ScalarEvolution/zext-add-nsw-fold.ll

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

declare i32 @llvm.smax.i32(i32, i32)
declare i32 @llvm.umax.i32(i32, i32)

define i64 @smax_fold_basic(i32 %x) {
; CHECK-LABEL: 'smax_fold_basic'
; CHECK-NEXT:  Classifying expressions for: @smax_fold_basic
; CHECK-NEXT:    %smax = call i32 @llvm.smax.i32(i32 %x, i32 5)
; CHECK-NEXT:    --> (5 smax %x) U: [5,-2147483648) S: [5,-2147483648)
; CHECK-NEXT:    %add = add nsw i32 -5, %smax
; CHECK-NEXT:    --> (-5 + (5 smax %x))<nsw> U: [0,2147483643) S: [0,2147483643)
; CHECK-NEXT:    %ext = zext i32 %add to i64
; CHECK-NEXT:    --> (zext i32 (-5 + (5 smax %x))<nsw> to i64) U: [0,2147483643) S: [0,2147483643)
; CHECK-NEXT:  Determining loop execution counts for: @smax_fold_basic
;
  %smax = call i32 @llvm.smax.i32(i32 %x, i32 5)
  %add = add nsw i32 -5, %smax
  %ext = zext i32 %add to i64
  ret i64 %ext
}

define i64 @smax_fold_larger_k(i32 %x) {
; CHECK-LABEL: 'smax_fold_larger_k'
; CHECK-NEXT:  Classifying expressions for: @smax_fold_larger_k
; CHECK-NEXT:    %smax = call i32 @llvm.smax.i32(i32 %x, i32 10)
; CHECK-NEXT:    --> (10 smax %x) U: [10,-2147483648) S: [10,-2147483648)
; CHECK-NEXT:    %add = add nsw i32 -3, %smax
; CHECK-NEXT:    --> (-3 + (10 smax %x))<nsw> U: [7,2147483645) S: [7,2147483645)
; CHECK-NEXT:    %ext = zext i32 %add to i64
; CHECK-NEXT:    --> (zext i32 (-3 + (10 smax %x))<nsw> to i64) U: [7,2147483645) S: [7,2147483645)
; CHECK-NEXT:  Determining loop execution counts for: @smax_fold_larger_k
;
  %smax = call i32 @llvm.smax.i32(i32 %x, i32 10)
  %add = add nsw i32 -3, %smax
  %ext = zext i32 %add to i64
  ret i64 %ext
}

define i64 @smax_no_fold_k_too_small(i32 %x) {
; CHECK-LABEL: 'smax_no_fold_k_too_small'
; CHECK-NEXT:  Classifying expressions for: @smax_no_fold_k_too_small
; CHECK-NEXT:    %smax = call i32 @llvm.smax.i32(i32 %x, i32 4)
; CHECK-NEXT:    --> (4 smax %x) U: [4,-2147483648) S: [4,-2147483648)
; CHECK-NEXT:    %add = add nsw i32 -5, %smax
; CHECK-NEXT:    --> (-5 + (4 smax %x))<nsw> U: [-1,2147483643) S: [-1,2147483643)
; CHECK-NEXT:    %ext = zext i32 %add to i64
; CHECK-NEXT:    --> (zext i32 (-5 + (4 smax %x))<nsw> to i64) U: [0,4294967296) S: [0,4294967296)
; CHECK-NEXT:  Determining loop execution counts for: @smax_no_fold_k_too_small
;
  %smax = call i32 @llvm.smax.i32(i32 %x, i32 4)
  %add = add nsw i32 -5, %smax
  %ext = zext i32 %add to i64
  ret i64 %ext
}

define i64 @smax_no_fold_k_negative(i32 %x) {
; CHECK-LABEL: 'smax_no_fold_k_negative'
; CHECK-NEXT:  Classifying expressions for: @smax_no_fold_k_negative
; CHECK-NEXT:    %smax = call i32 @llvm.smax.i32(i32 %x, i32 -1)
; CHECK-NEXT:    --> (-1 smax %x) U: [-1,-2147483648) S: [-1,-2147483648)
; CHECK-NEXT:    %add = add nsw i32 -5, %smax
; CHECK-NEXT:    --> (-5 + (-1 smax %x))<nsw> U: [-6,2147483643) S: [-6,2147483643)
; CHECK-NEXT:    %ext = zext i32 %add to i64
; CHECK-NEXT:    --> (zext i32 (-5 + (-1 smax %x))<nsw> to i64) U: [0,4294967296) S: [0,4294967296)
; CHECK-NEXT:  Determining loop execution counts for: @smax_no_fold_k_negative
;
  %smax = call i32 @llvm.smax.i32(i32 %x, i32 -1)
  %add = add nsw i32 -5, %smax
  %ext = zext i32 %add to i64
  ret i64 %ext
}

define i64 @mul_umax_fold(i8 %x) {
; CHECK-LABEL: 'mul_umax_fold'
; CHECK-NEXT:  Classifying expressions for: @mul_umax_fold
; CHECK-NEXT:    %zx = zext i8 %x to i32
; CHECK-NEXT:    --> (zext i8 %x to i32) U: [0,256) S: [0,256)
; CHECK-NEXT:    %umax = call i32 @llvm.umax.i32(i32 %zx, i32 3)
; CHECK-NEXT:    --> (3 umax (zext i8 %x to i32)) U: [3,256) S: [3,256)
; CHECK-NEXT:    %mul = mul nuw nsw i32 4, %umax
; CHECK-NEXT:    --> (4 * (3 umax (zext i8 %x to i32)))<nuw><nsw> U: [12,1021) S: [12,1021)
; CHECK-NEXT:    %add = add nsw i32 -12, %mul
; CHECK-NEXT:    --> (-12 + (4 * (3 umax (zext i8 %x to i32)))<nuw><nsw>)<nsw> U: [0,1009) S: [0,1009)
; CHECK-NEXT:    %ext = zext i32 %add to i64
; CHECK-NEXT:    --> (zext i32 (-12 + (4 * (3 umax (zext i8 %x to i32)))<nuw><nsw>)<nsw> to i64) U: [0,1009) S: [0,1009)
; CHECK-NEXT:  Determining loop execution counts for: @mul_umax_fold
;
  %zx = zext i8 %x to i32
  %umax = call i32 @llvm.umax.i32(i32 %zx, i32 3)
  %mul = mul nuw nsw i32 4, %umax
  %add = add nsw i32 -12, %mul
  %ext = zext i32 %add to i64
  ret i64 %ext
}

define i64 @mul_umax_fold_round_up(i8 %x) {
; CHECK-LABEL: 'mul_umax_fold_round_up'
; CHECK-NEXT:  Classifying expressions for: @mul_umax_fold_round_up
; CHECK-NEXT:    %zx = zext i8 %x to i32
; CHECK-NEXT:    --> (zext i8 %x to i32) U: [0,256) S: [0,256)
; CHECK-NEXT:    %umax = call i32 @llvm.umax.i32(i32 %zx, i32 3)
; CHECK-NEXT:    --> (3 umax (zext i8 %x to i32)) U: [3,256) S: [3,256)
; CHECK-NEXT:    %mul = mul nuw nsw i32 4, %umax
; CHECK-NEXT:    --> (4 * (3 umax (zext i8 %x to i32)))<nuw><nsw> U: [12,1021) S: [12,1021)
; CHECK-NEXT:    %add = add nsw i32 -10, %mul
; CHECK-NEXT:    --> (-10 + (4 * (3 umax (zext i8 %x to i32)))<nuw><nsw>)<nsw> U: [2,1011) S: [2,1011)
; CHECK-NEXT:    %ext = zext i32 %add to i64
; CHECK-NEXT:    --> (2 + (zext i32 (-12 + (4 * (3 umax (zext i8 %x to i32)))<nuw><nsw>)<nsw> to i64))<nuw><nsw> U: [2,1011) S: [2,1011)
; CHECK-NEXT:  Determining loop execution counts for: @mul_umax_fold_round_up
;
  %zx = zext i8 %x to i32
  %umax = call i32 @llvm.umax.i32(i32 %zx, i32 3)
  %mul = mul nuw nsw i32 4, %umax
  %add = add nsw i32 -10, %mul
  %ext = zext i32 %add to i64
  ret i64 %ext
}

define i64 @mul_umax_no_fold_bound_not_met(i8 %x) {
; CHECK-LABEL: 'mul_umax_no_fold_bound_not_met'
; CHECK-NEXT:  Classifying expressions for: @mul_umax_no_fold_bound_not_met
; CHECK-NEXT:    %zx = zext i8 %x to i32
; CHECK-NEXT:    --> (zext i8 %x to i32) U: [0,256) S: [0,256)
; CHECK-NEXT:    %umax = call i32 @llvm.umax.i32(i32 %zx, i32 3)
; CHECK-NEXT:    --> (3 umax (zext i8 %x to i32)) U: [3,256) S: [3,256)
; CHECK-NEXT:    %mul = mul nuw nsw i32 4, %umax
; CHECK-NEXT:    --> (4 * (3 umax (zext i8 %x to i32)))<nuw><nsw> U: [12,1021) S: [12,1021)
; CHECK-NEXT:    %add = add nsw i32 -13, %mul
; CHECK-NEXT:    --> (-13 + (4 * (3 umax (zext i8 %x to i32)))<nuw><nsw>)<nsw> U: [-1,1008) S: [-1,1008)
; CHECK-NEXT:    %ext = zext i32 %add to i64
; CHECK-NEXT:    --> (3 + (zext i32 (-16 + (4 * (3 umax (zext i8 %x to i32)))<nuw><nsw>)<nsw> to i64))<nuw><nsw> U: [3,4294967296) S: [3,4294967299)
; CHECK-NEXT:  Determining loop execution counts for: @mul_umax_no_fold_bound_not_met
;
  %zx = zext i8 %x to i32
  %umax = call i32 @llvm.umax.i32(i32 %zx, i32 3)
  %mul = mul nuw nsw i32 4, %umax
  %add = add nsw i32 -13, %mul
  %ext = zext i32 %add to i64
  ret i64 %ext
}

define i64 @mul_smax_fold(i8 %x) {
; CHECK-LABEL: 'mul_smax_fold'
; CHECK-NEXT:  Classifying expressions for: @mul_smax_fold
; CHECK-NEXT:    %zx = zext i8 %x to i32
; CHECK-NEXT:    --> (zext i8 %x to i32) U: [0,256) S: [0,256)
; CHECK-NEXT:    %smax = call i32 @llvm.smax.i32(i32 %zx, i32 3)
; CHECK-NEXT:    --> (3 smax (zext i8 %x to i32)) U: [3,256) S: [3,256)
; CHECK-NEXT:    %mul = mul nuw nsw i32 4, %smax
; CHECK-NEXT:    --> (4 * (3 smax (zext i8 %x to i32)))<nuw><nsw> U: [12,1021) S: [12,1021)
; CHECK-NEXT:    %add = add nsw i32 -8, %mul
; CHECK-NEXT:    --> (-8 + (4 * (3 smax (zext i8 %x to i32)))<nuw><nsw>)<nsw> U: [4,1013) S: [4,1013)
; CHECK-NEXT:    %ext = zext i32 %add to i64
; CHECK-NEXT:    --> (zext i32 (-8 + (4 * (3 smax (zext i8 %x to i32)))<nuw><nsw>)<nsw> to i64) U: [4,1013) S: [4,1013)
; CHECK-NEXT:  Determining loop execution counts for: @mul_smax_fold
;
  %zx = zext i8 %x to i32
  %smax = call i32 @llvm.smax.i32(i32 %zx, i32 3)
  %mul = mul nuw nsw i32 4, %smax
  %add = add nsw i32 -8, %mul
  %ext = zext i32 %add to i64
  ret i64 %ext
}

define i64 @const_fold_exact() {
; CHECK-LABEL: 'const_fold_exact'
; CHECK-NEXT:  Classifying expressions for: @const_fold_exact
; CHECK-NEXT:    %add = add nsw i32 -5, 5
; CHECK-NEXT:    --> 0 U: [0,1) S: [0,1)
; CHECK-NEXT:    %ext = zext i32 %add to i64
; CHECK-NEXT:    --> 0 U: [0,1) S: [0,1)
; CHECK-NEXT:  Determining loop execution counts for: @const_fold_exact
;
  %add = add nsw i32 -5, 5
  %ext = zext i32 %add to i64
  ret i64 %ext
}

define i64 @const_fold_larger() {
; CHECK-LABEL: 'const_fold_larger'
; CHECK-NEXT:  Classifying expressions for: @const_fold_larger
; CHECK-NEXT:    %add = add nsw i32 -3, 100
; CHECK-NEXT:    --> 97 U: [97,98) S: [97,98)
; CHECK-NEXT:    %ext = zext i32 %add to i64
; CHECK-NEXT:    --> 97 U: [97,98) S: [97,98)
; CHECK-NEXT:  Determining loop execution counts for: @const_fold_larger
;
  %add = add nsw i32 -3, 100
  %ext = zext i32 %add to i64
  ret i64 %ext
}

define i64 @umax_no_mul_no_fold(i32 %x) {
; CHECK-LABEL: 'umax_no_mul_no_fold'
; CHECK-NEXT:  Classifying expressions for: @umax_no_mul_no_fold
; CHECK-NEXT:    %umax = call i32 @llvm.umax.i32(i32 %x, i32 5)
; CHECK-NEXT:    --> (5 umax %x) U: [5,0) S: [5,0)
; CHECK-NEXT:    %add = add nsw i32 -5, %umax
; CHECK-NEXT:    --> (-5 + (5 umax %x)) U: [0,-5) S: [0,-5)
; CHECK-NEXT:    %ext = zext i32 %add to i64
; CHECK-NEXT:    --> (zext i32 (-5 + (5 umax %x)) to i64) U: [0,4294967291) S: [0,4294967291)
; CHECK-NEXT:  Determining loop execution counts for: @umax_no_mul_no_fold
;
  %umax = call i32 @llvm.umax.i32(i32 %x, i32 5)
  %add = add nsw i32 -5, %umax
  %ext = zext i32 %add to i64
  ret i64 %ext
}

define i64 @umax_zext_fold(i8 %x) {
; CHECK-LABEL: 'umax_zext_fold'
; CHECK-NEXT:  Classifying expressions for: @umax_zext_fold
; CHECK-NEXT:    %zx = zext i8 %x to i32
; CHECK-NEXT:    --> (zext i8 %x to i32) U: [0,256) S: [0,256)
; CHECK-NEXT:    %umax = call i32 @llvm.umax.i32(i32 %zx, i32 5)
; CHECK-NEXT:    --> (5 umax (zext i8 %x to i32)) U: [5,256) S: [5,256)
; CHECK-NEXT:    %add = add nsw i32 -5, %umax
; CHECK-NEXT:    --> (-5 + (5 umax (zext i8 %x to i32)))<nsw> U: [0,251) S: [0,251)
; CHECK-NEXT:    %ext = zext i32 %add to i64
; CHECK-NEXT:    --> (zext i32 (-5 + (5 umax (zext i8 %x to i32)))<nsw> to i64) U: [0,251) S: [0,251)
; CHECK-NEXT:  Determining loop execution counts for: @umax_zext_fold
;
  %zx = zext i8 %x to i32
  %umax = call i32 @llvm.umax.i32(i32 %zx, i32 5)
  %add = add nsw i32 -5, %umax
  %ext = zext i32 %add to i64
  ret i64 %ext
}

define i64 @zext_op_fold_positive_c(i8 %x) {
; CHECK-LABEL: 'zext_op_fold_positive_c'
; CHECK-NEXT:  Classifying expressions for: @zext_op_fold_positive_c
; CHECK-NEXT:    %zx = zext i8 %x to i32
; CHECK-NEXT:    --> (zext i8 %x to i32) U: [0,256) S: [0,256)
; CHECK-NEXT:    %add = add nsw i32 3, %zx
; CHECK-NEXT:    --> (3 + (zext i8 %x to i32))<nuw><nsw> U: [3,259) S: [3,259)
; CHECK-NEXT:    %ext = zext i32 %add to i64
; CHECK-NEXT:    --> (3 + (zext i8 %x to i64))<nuw><nsw> U: [3,259) S: [3,259)
; CHECK-NEXT:  Determining loop execution counts for: @zext_op_fold_positive_c
;
  %zx = zext i8 %x to i32
  %add = add nsw i32 3, %zx
  %ext = zext i32 %add to i64
  ret i64 %ext
}

define i64 @zext_op_no_fold_negative_c(i16 %x) {
; CHECK-LABEL: 'zext_op_no_fold_negative_c'
; CHECK-NEXT:  Classifying expressions for: @zext_op_no_fold_negative_c
; CHECK-NEXT:    %zx = zext i16 %x to i32
; CHECK-NEXT:    --> (zext i16 %x to i32) U: [0,65536) S: [0,65536)
; CHECK-NEXT:    %add = add nsw i32 -5, %zx
; CHECK-NEXT:    --> (-5 + (zext i16 %x to i32))<nsw> U: [-5,65531) S: [-5,65531)
; CHECK-NEXT:    %ext = zext i32 %add to i64
; CHECK-NEXT:    --> (zext i32 (-5 + (zext i16 %x to i32))<nsw> to i64) U: [0,4294967296) S: [0,4294967296)
; CHECK-NEXT:  Determining loop execution counts for: @zext_op_no_fold_negative_c
;
; No fold: C = -5 is negative and zext has min 0, so -5 + 0 < 0.
  %zx = zext i16 %x to i32
  %add = add nsw i32 -5, %zx
  %ext = zext i32 %add to i64
  ret i64 %ext
}

define i64 @mul_zext_fold_positive_c(i8 %x) {
; CHECK-LABEL: 'mul_zext_fold_positive_c'
; CHECK-NEXT:  Classifying expressions for: @mul_zext_fold_positive_c
; CHECK-NEXT:    %zx = zext i8 %x to i32
; CHECK-NEXT:    --> (zext i8 %x to i32) U: [0,256) S: [0,256)
; CHECK-NEXT:    %mul = mul nuw nsw i32 4, %zx
; CHECK-NEXT:    --> (4 * (zext i8 %x to i32))<nuw><nsw> U: [0,1021) S: [0,1021)
; CHECK-NEXT:    %add = add nsw i32 2, %mul
; CHECK-NEXT:    --> (2 + (4 * (zext i8 %x to i32))<nuw><nsw>)<nuw><nsw> U: [2,1023) S: [2,1023)
; CHECK-NEXT:    %ext = zext i32 %add to i64
; CHECK-NEXT:    --> (2 + (4 * (zext i8 %x to i64))<nuw><nsw>)<nuw><nsw> U: [2,1023) S: [2,1023)
; CHECK-NEXT:  Determining loop execution counts for: @mul_zext_fold_positive_c
;
  %zx = zext i8 %x to i32
  %mul = mul nuw nsw i32 4, %zx
  %add = add nsw i32 2, %mul
  %ext = zext i32 %add to i64
  ret i64 %ext
}