215 lines · plain
1; NOTE: Assertions have been autogenerated by utils/update_analyze_test_checks.py2; RUN: opt "-passes=print<scalar-evolution>" -disable-output < %s 2>&1 | FileCheck %s3;4; This checks if the min and max expressions are properly recognized by5; ScalarEvolution even though they the ICmpInst and SelectInst have different6; types.7;8; #define max(a, b) (a > b ? a : b)9; #define min(a, b) (a < b ? a : b)10;11; void f(int *A, int N) {12; for (int i = 0; i < N; i++) {13; A[max(0, i - 3)] = Aptr 2;14; }15; }16;17target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"18 19define void @f(ptr %A, i32 %N) {20; CHECK-LABEL: 'f'21; CHECK-NEXT: Classifying expressions for: @f22; CHECK-NEXT: %i.0 = phi i32 [ 0, %bb ], [ %tmp23, %bb2 ]23; CHECK-NEXT: --> {0,+,1}<nuw><nsw><%bb1> U: [0,-2147483648) S: [0,-2147483648) Exits: (0 smax %N) LoopDispositions: { %bb1: Computable }24; CHECK-NEXT: %i.0.1 = sext i32 %i.0 to i6425; CHECK-NEXT: --> {0,+,1}<nuw><nsw><%bb1> U: [0,2147483648) S: [0,2147483648) Exits: (zext i32 (0 smax %N) to i64) LoopDispositions: { %bb1: Computable }26; CHECK-NEXT: %tmp3 = add nuw nsw i32 %i.0, 327; CHECK-NEXT: --> {3,+,1}<nuw><%bb1> U: [3,-2147483645) S: [3,-2147483645) Exits: (3 + (0 smax %N))<nuw> LoopDispositions: { %bb1: Computable }28; CHECK-NEXT: %tmp5 = sext i32 %tmp3 to i6429; CHECK-NEXT: --> (sext i32 {3,+,1}<nuw><%bb1> to i64) U: [-2147483648,2147483648) S: [-2147483648,2147483648) Exits: (sext i32 (3 + (0 smax %N))<nuw> to i64) LoopDispositions: { %bb1: Computable }30; CHECK-NEXT: %tmp6 = sext i32 %N to i6431; CHECK-NEXT: --> (sext i32 %N to i64) U: [-2147483648,2147483648) S: [-2147483648,2147483648) Exits: (sext i32 %N to i64) LoopDispositions: { %bb1: Invariant }32; CHECK-NEXT: %tmp9 = select i1 %tmp4, i64 %tmp5, i64 %tmp633; CHECK-NEXT: --> ((sext i32 {3,+,1}<nuw><%bb1> to i64) smin (sext i32 %N to i64)) U: [-2147483648,2147483648) S: [-2147483648,2147483648) Exits: ((sext i32 (3 + (0 smax %N))<nuw> to i64) smin (sext i32 %N to i64)) LoopDispositions: { %bb1: Computable }34; CHECK-NEXT: %tmp11 = getelementptr inbounds i32, ptr %A, i64 %tmp935; CHECK-NEXT: --> ((4 * ((sext i32 {3,+,1}<nuw><%bb1> to i64) smin (sext i32 %N to i64)))<nsw> + %A) U: full-set S: full-set Exits: ((4 * ((sext i32 (3 + (0 smax %N))<nuw> to i64) smin (sext i32 %N to i64)))<nsw> + %A) LoopDispositions: { %bb1: Computable }36; CHECK-NEXT: %tmp12 = load i32, ptr %tmp11, align 437; CHECK-NEXT: --> %tmp12 U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %bb1: Variant }38; CHECK-NEXT: %tmp13 = shl nsw i32 %tmp12, 139; CHECK-NEXT: --> (2 * %tmp12) U: [0,-1) S: [-2147483648,2147483647) Exits: <<Unknown>> LoopDispositions: { %bb1: Variant }40; CHECK-NEXT: %tmp17 = add nsw i64 %i.0.1, -341; CHECK-NEXT: --> {-3,+,1}<nsw><%bb1> U: [-3,2147483645) S: [-3,2147483645) Exits: (-3 + (zext i32 (0 smax %N) to i64))<nsw> LoopDispositions: { %bb1: Computable }42; CHECK-NEXT: %tmp19 = select i1 %tmp14, i64 0, i64 %tmp1743; CHECK-NEXT: --> (-3 + (3 smax {0,+,1}<nuw><nsw><%bb1>))<nsw> U: [0,2147483645) S: [0,2147483645) Exits: (-3 + (3 smax (zext i32 (0 smax %N) to i64)))<nsw> LoopDispositions: { %bb1: Computable }44; CHECK-NEXT: %tmp21 = getelementptr inbounds i32, ptr %A, i64 %tmp1945; CHECK-NEXT: --> (-12 + (4 * (3 smax {0,+,1}<nuw><nsw><%bb1>))<nuw><nsw> + %A) U: full-set S: full-set Exits: (-12 + (4 * (3 smax (zext i32 (0 smax %N) to i64)))<nuw><nsw> + %A) LoopDispositions: { %bb1: Computable }46; CHECK-NEXT: %tmp23 = add nuw nsw i32 %i.0, 147; CHECK-NEXT: --> {1,+,1}<nuw><%bb1> U: [1,-2147483647) S: [1,-2147483647) Exits: (1 + (0 smax %N))<nuw> LoopDispositions: { %bb1: Computable }48; CHECK-NEXT: Determining loop execution counts for: @f49; CHECK-NEXT: Loop %bb1: backedge-taken count is (0 smax %N)50; CHECK-NEXT: Loop %bb1: constant max backedge-taken count is i32 214748364751; CHECK-NEXT: Loop %bb1: symbolic max backedge-taken count is (0 smax %N)52; CHECK-NEXT: Loop %bb1: Trip multiple is 153;54bb:55 br label %bb156 57bb1: ; preds = %bb2, %bb58 %i.0 = phi i32 [ 0, %bb ], [ %tmp23, %bb2 ]59 %i.0.1 = sext i32 %i.0 to i6460 %tmp = icmp slt i32 %i.0, %N61 br i1 %tmp, label %bb2, label %bb2462 63bb2: ; preds = %bb164 %tmp3 = add nuw nsw i32 %i.0, 365 %tmp4 = icmp slt i32 %tmp3, %N66 %tmp5 = sext i32 %tmp3 to i6467 %tmp6 = sext i32 %N to i6468 %tmp9 = select i1 %tmp4, i64 %tmp5, i64 %tmp669; min(N, i+3)70 %tmp11 = getelementptr inbounds i32, ptr %A, i64 %tmp971 %tmp12 = load i32, ptr %tmp11, align 472 %tmp13 = shl nsw i32 %tmp12, 173 %tmp14 = icmp sge i32 3, %i.074 %tmp17 = add nsw i64 %i.0.1, -375 %tmp19 = select i1 %tmp14, i64 0, i64 %tmp1776; max(0, i - 3)77 %tmp21 = getelementptr inbounds i32, ptr %A, i64 %tmp1978 store i32 %tmp13, ptr %tmp21, align 479 %tmp23 = add nuw nsw i32 %i.0, 180 br label %bb181 82bb24: ; preds = %bb183 ret void84}85 86define i8 @umax_basic_eq_off1(i8 %x, i8 %y) {87; CHECK-LABEL: 'umax_basic_eq_off1'88; CHECK-NEXT: Classifying expressions for: @umax_basic_eq_off189; CHECK-NEXT: %lhs = add i8 %y, 190; CHECK-NEXT: --> (1 + %y) U: full-set S: full-set91; CHECK-NEXT: %rhs = add i8 %x, %y92; CHECK-NEXT: --> (%x + %y) U: full-set S: full-set93; CHECK-NEXT: %r = select i1 %x.is.zero, i8 %lhs, i8 %rhs94; CHECK-NEXT: --> ((1 umax %x) + %y) U: full-set S: full-set95; CHECK-NEXT: Determining loop execution counts for: @umax_basic_eq_off196;97 %x.is.zero = icmp eq i8 %x, 098 %lhs = add i8 %y, 199 %rhs = add i8 %x, %y100 %r = select i1 %x.is.zero, i8 %lhs, i8 %rhs101 ret i8 %r102}103define i8 @umax_basic_ne_off1(i8 %x, i8 %y) {104; CHECK-LABEL: 'umax_basic_ne_off1'105; CHECK-NEXT: Classifying expressions for: @umax_basic_ne_off1106; CHECK-NEXT: %lhs = add i8 %y, 1107; CHECK-NEXT: --> (1 + %y) U: full-set S: full-set108; CHECK-NEXT: %rhs = add i8 %x, %y109; CHECK-NEXT: --> (%x + %y) U: full-set S: full-set110; CHECK-NEXT: %r = select i1 %x.is.zero, i8 %rhs, i8 %lhs111; CHECK-NEXT: --> ((1 umax %x) + %y) U: full-set S: full-set112; CHECK-NEXT: Determining loop execution counts for: @umax_basic_ne_off1113;114 %x.is.zero = icmp ne i8 %x, 0115 %lhs = add i8 %y, 1116 %rhs = add i8 %x, %y117 %r = select i1 %x.is.zero, i8 %rhs, i8 %lhs118 ret i8 %r119}120 121define i8 @umax_basic_eq_off0(i8 %x, i8 %y) {122; CHECK-LABEL: 'umax_basic_eq_off0'123; CHECK-NEXT: Classifying expressions for: @umax_basic_eq_off0124; CHECK-NEXT: %lhs = add i8 %y, 0125; CHECK-NEXT: --> %y U: full-set S: full-set126; CHECK-NEXT: %rhs = add i8 %x, %y127; CHECK-NEXT: --> (%x + %y) U: full-set S: full-set128; CHECK-NEXT: %r = select i1 %x.is.zero, i8 %lhs, i8 %rhs129; CHECK-NEXT: --> (%x + %y) U: full-set S: full-set130; CHECK-NEXT: Determining loop execution counts for: @umax_basic_eq_off0131;132 %x.is.zero = icmp eq i8 %x, 0133 %lhs = add i8 %y, 0134 %rhs = add i8 %x, %y135 %r = select i1 %x.is.zero, i8 %lhs, i8 %rhs136 ret i8 %r137}138 139define i8 @umax_basic_eq_off2(i8 %x, i8 %y) {140; CHECK-LABEL: 'umax_basic_eq_off2'141; CHECK-NEXT: Classifying expressions for: @umax_basic_eq_off2142; CHECK-NEXT: %lhs = add i8 %y, 2143; CHECK-NEXT: --> (2 + %y) U: full-set S: full-set144; CHECK-NEXT: %rhs = add i8 %x, %y145; CHECK-NEXT: --> (%x + %y) U: full-set S: full-set146; CHECK-NEXT: %r = select i1 %x.is.zero, i8 %lhs, i8 %rhs147; CHECK-NEXT: --> %r U: full-set S: full-set148; CHECK-NEXT: Determining loop execution counts for: @umax_basic_eq_off2149;150 %x.is.zero = icmp eq i8 %x, 0151 %lhs = add i8 %y, 2152 %rhs = add i8 %x, %y153 %r = select i1 %x.is.zero, i8 %lhs, i8 %rhs154 ret i8 %r155}156 157define i8 @umax_basic_eq_var_off(i8 %x, i8 %y, i8 %c) {158; CHECK-LABEL: 'umax_basic_eq_var_off'159; CHECK-NEXT: Classifying expressions for: @umax_basic_eq_var_off160; CHECK-NEXT: %lhs = add i8 %y, %c161; CHECK-NEXT: --> (%y + %c) U: full-set S: full-set162; CHECK-NEXT: %rhs = add i8 %x, %y163; CHECK-NEXT: --> (%x + %y) U: full-set S: full-set164; CHECK-NEXT: %r = select i1 %x.is.zero, i8 %lhs, i8 %rhs165; CHECK-NEXT: --> %r U: full-set S: full-set166; CHECK-NEXT: Determining loop execution counts for: @umax_basic_eq_var_off167;168 %x.is.zero = icmp eq i8 %x, 0169 %lhs = add i8 %y, %c170 %rhs = add i8 %x, %y171 %r = select i1 %x.is.zero, i8 %lhs, i8 %rhs172 ret i8 %r173}174 175define i8 @umax_basic_eq_narrow(i4 %x.narrow, i8 %y) {176; CHECK-LABEL: 'umax_basic_eq_narrow'177; CHECK-NEXT: Classifying expressions for: @umax_basic_eq_narrow178; CHECK-NEXT: %x = zext i4 %x.narrow to i8179; CHECK-NEXT: --> (zext i4 %x.narrow to i8) U: [0,16) S: [0,16)180; CHECK-NEXT: %lhs = add i8 %y, 1181; CHECK-NEXT: --> (1 + %y) U: full-set S: full-set182; CHECK-NEXT: %rhs = add i8 %x, %y183; CHECK-NEXT: --> ((zext i4 %x.narrow to i8) + %y) U: full-set S: full-set184; CHECK-NEXT: %r = select i1 %x.is.zero, i8 %lhs, i8 %rhs185; CHECK-NEXT: --> ((1 umax (zext i4 %x.narrow to i8)) + %y) U: full-set S: full-set186; CHECK-NEXT: Determining loop execution counts for: @umax_basic_eq_narrow187;188 %x = zext i4 %x.narrow to i8189 %x.is.zero = icmp eq i4 %x.narrow, 0190 %lhs = add i8 %y, 1191 %rhs = add i8 %x, %y192 %r = select i1 %x.is.zero, i8 %lhs, i8 %rhs193 ret i8 %r194}195define i8 @umax_basic_ne_narrow(i4 %x.narrow, i8 %y) {196; CHECK-LABEL: 'umax_basic_ne_narrow'197; CHECK-NEXT: Classifying expressions for: @umax_basic_ne_narrow198; CHECK-NEXT: %x = zext i4 %x.narrow to i8199; CHECK-NEXT: --> (zext i4 %x.narrow to i8) U: [0,16) S: [0,16)200; CHECK-NEXT: %lhs = add i8 %y, 1201; CHECK-NEXT: --> (1 + %y) U: full-set S: full-set202; CHECK-NEXT: %rhs = add i8 %x, %y203; CHECK-NEXT: --> ((zext i4 %x.narrow to i8) + %y) U: full-set S: full-set204; CHECK-NEXT: %r = select i1 %x.is.zero, i8 %rhs, i8 %lhs205; CHECK-NEXT: --> ((1 umax (zext i4 %x.narrow to i8)) + %y) U: full-set S: full-set206; CHECK-NEXT: Determining loop execution counts for: @umax_basic_ne_narrow207;208 %x = zext i4 %x.narrow to i8209 %x.is.zero = icmp ne i4 %x.narrow, 0210 %lhs = add i8 %y, 1211 %rhs = add i8 %x, %y212 %r = select i1 %x.is.zero, i8 %rhs, i8 %lhs213 ret i8 %r214}215