231 lines · plain
1; NOTE: Assertions have been autogenerated by utils/update_analyze_test_checks.py UTC_ARGS: --version 52; RUN: opt -passes='print<scalar-evolution>' -disable-output %s 2>&1 | FileCheck %s3 4declare void @use(ptr)5 6define void @udiv4_and_udiv2(i1 %c, ptr %A) {7; CHECK-LABEL: 'udiv4_and_udiv2'8; CHECK-NEXT: Classifying expressions for: @udiv4_and_udiv29; CHECK-NEXT: %start = select i1 %c, i32 512, i32 010; CHECK-NEXT: --> %start U: [0,513) S: [0,513)11; CHECK-NEXT: %div.2 = lshr i32 %start, 112; CHECK-NEXT: --> (%start /u 2) U: [0,257) S: [0,257)13; CHECK-NEXT: %div.4 = lshr i32 %start, 214; CHECK-NEXT: --> (%start /u 4) U: [0,129) S: [0,129)15; CHECK-NEXT: %iv.start = zext i32 %div.4 to i6416; CHECK-NEXT: --> ((zext i32 %start to i64) /u 4) U: [0,129) S: [0,129)17; CHECK-NEXT: %wide.trip.count = zext i32 %div.2 to i6418; CHECK-NEXT: --> ((zext i32 %start to i64) /u 2) U: [0,257) S: [0,257)19; CHECK-NEXT: %iv = phi i64 [ %iv.start, %entry ], [ %iv.next, %loop ]20; 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 }21; CHECK-NEXT: %gep.8 = getelementptr i8, ptr %A, i64 %iv22; 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 }23; CHECK-NEXT: %gep.16 = getelementptr i16, ptr %A, i64 %iv24; 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 }25; CHECK-NEXT: %gep.32 = getelementptr i32, ptr %A, i64 %iv26; 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 }27; CHECK-NEXT: %gep.40 = getelementptr <{ i32, i8 }>, ptr %A, i64 %iv28; 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 }29; CHECK-NEXT: %gep.48 = getelementptr <{ i32, i16 }>, ptr %A, i64 %iv30; 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 }31; CHECK-NEXT: %iv.next = add i64 %iv, 132; 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 }33; CHECK-NEXT: Determining loop execution counts for: @udiv4_and_udiv234; CHECK-NEXT: Loop %loop: backedge-taken count is ((-1 * ((zext i32 %start to i64) /u 4))<nsw> + ((zext i32 %start to i64) /u 2))35; CHECK-NEXT: Loop %loop: constant max backedge-taken count is i64 -136; 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))37; CHECK-NEXT: Loop %loop: Trip multiple is 138;39entry:40 %start = select i1 %c, i32 512, i32 041 %div.2 = lshr i32 %start, 142 %div.4 = lshr i32 %start, 243 %iv.start = zext i32 %div.4 to i6444 %wide.trip.count = zext i32 %div.2 to i6445 br label %loop46 47loop:48 %iv = phi i64 [ %iv.start, %entry ], [ %iv.next, %loop ]49 %gep.8 = getelementptr i8, ptr %A, i64 %iv50 call void @use(ptr %gep.8)51 %gep.16 = getelementptr i16, ptr %A, i64 %iv52 call void @use(ptr %gep.16)53 %gep.32 = getelementptr i32, ptr %A, i64 %iv54 call void @use(ptr %gep.32)55 %gep.40 = getelementptr <{i32, i8}>, ptr %A, i64 %iv56 call void @use(ptr %gep.40)57 %gep.48 = getelementptr <{i32, i16}>, ptr %A, i64 %iv58 call void @use(ptr %gep.48)59 %iv.next = add i64 %iv, 160 %ec = icmp eq i64 %iv, %wide.trip.count61 br i1 %ec, label %exit, label %loop62 63exit:64 ret void65}66define void @udiv3_and_udiv5_mul_4(i1 %c, ptr %A) {67; CHECK-LABEL: 'udiv3_and_udiv5_mul_4'68; CHECK-NEXT: Classifying expressions for: @udiv3_and_udiv5_mul_469; CHECK-NEXT: %start = select i1 %c, i32 512, i32 070; CHECK-NEXT: --> %start U: [0,513) S: [0,513)71; CHECK-NEXT: %div.3 = udiv i32 %start, 372; CHECK-NEXT: --> (%start /u 3) U: [0,171) S: [0,171)73; CHECK-NEXT: %div.5 = udiv i32 %start, 574; CHECK-NEXT: --> (%start /u 5) U: [0,103) S: [0,103)75; CHECK-NEXT: %iv.start = zext i32 %div.5 to i6476; CHECK-NEXT: --> ((zext i32 %start to i64) /u 5) U: [0,103) S: [0,103)77; CHECK-NEXT: %wide.trip.count = zext i32 %div.3 to i6478; CHECK-NEXT: --> ((zext i32 %start to i64) /u 3) U: [0,171) S: [0,171)79; CHECK-NEXT: %iv = phi i64 [ %iv.start, %entry ], [ %iv.next, %loop ]80; 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 }81; CHECK-NEXT: %gep.8 = getelementptr i8, ptr %A, i64 %iv82; 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 }83; CHECK-NEXT: %gep.16 = getelementptr i16, ptr %A, i64 %iv84; 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 }85; CHECK-NEXT: %gep.32 = getelementptr i32, ptr %A, i64 %iv86; 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 }87; CHECK-NEXT: %gep.40 = getelementptr <{ i32, i8 }>, ptr %A, i64 %iv88; 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 }89; CHECK-NEXT: %gep.48 = getelementptr <{ i32, i16 }>, ptr %A, i64 %iv90; 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 }91; CHECK-NEXT: %iv.next = add i64 %iv, 192; 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 }93; CHECK-NEXT: Determining loop execution counts for: @udiv3_and_udiv5_mul_494; CHECK-NEXT: Loop %loop: backedge-taken count is ((-1 * ((zext i32 %start to i64) /u 5))<nsw> + ((zext i32 %start to i64) /u 3))95; CHECK-NEXT: Loop %loop: constant max backedge-taken count is i64 -196; 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))97; CHECK-NEXT: Loop %loop: Trip multiple is 198;99entry:100 %start = select i1 %c, i32 512, i32 0101 %div.3 = udiv i32 %start, 3102 %div.5 = udiv i32 %start, 5103 %iv.start = zext i32 %div.5 to i64104 %wide.trip.count = zext i32 %div.3 to i64105 br label %loop106 107loop:108 %iv = phi i64 [ %iv.start, %entry ], [ %iv.next, %loop ]109 %gep.8 = getelementptr i8, ptr %A, i64 %iv110 call void @use(ptr %gep.8)111 %gep.16 = getelementptr i16, ptr %A, i64 %iv112 call void @use(ptr %gep.16)113 %gep.32 = getelementptr i32, ptr %A, i64 %iv114 call void @use(ptr %gep.32)115 %gep.40 = getelementptr <{i32, i8}>, ptr %A, i64 %iv116 call void @use(ptr %gep.40)117 %gep.48 = getelementptr <{i32, i16}>, ptr %A, i64 %iv118 call void @use(ptr %gep.48)119 %iv.next = add i64 %iv, 1120 %ec = icmp eq i64 %iv, %wide.trip.count121 br i1 %ec, label %exit, label %loop122 123exit:124 ret void125}126 127declare void @use.i64(i64)128 129define void @dividend_not_known_multiple_of_divisor(i64 %x) {130; CHECK-LABEL: 'dividend_not_known_multiple_of_divisor'131; CHECK-NEXT: Classifying expressions for: @dividend_not_known_multiple_of_divisor132; CHECK-NEXT: %mul.2 = shl i64 %x, 1133; CHECK-NEXT: --> (2 * %x) U: [0,-1) S: [-9223372036854775808,9223372036854775807)134; CHECK-NEXT: %div.16 = lshr exact i64 %mul.2, 4135; CHECK-NEXT: --> ((2 * %x) /u 16) U: [0,1152921504606846976) S: [0,1152921504606846976)136; CHECK-NEXT: %m2 = and i64 %div.16, 1152921504606846974137; CHECK-NEXT: --> (2 * ((2 * %x) /u 32))<nuw><nsw> U: [0,1152921504606846975) S: [0,1152921504606846975)138; CHECK-NEXT: %m3 = mul i64 %div.16, 2139; CHECK-NEXT: --> (2 * ((2 * %x) /u 16))<nuw><nsw> U: [0,2305843009213693951) S: [0,2305843009213693951)140; CHECK-NEXT: %m4 = udiv i64 %m3, 4141; CHECK-NEXT: --> ((2 * ((2 * %x) /u 16))<nuw><nsw> /u 4) U: [0,576460752303423488) S: [0,576460752303423488)142; CHECK-NEXT: Determining loop execution counts for: @dividend_not_known_multiple_of_divisor143;144entry:145 %mul.2 = shl i64 %x, 1146 %div.16 = lshr exact i64 %mul.2, 4147 %m2 = and i64 %div.16, 1152921504606846974148 call void @use.i64(i64 %m2)149 150 %m3 = mul i64 %div.16, 2151 %m4 = udiv i64 %m3, 4152 call void @use.i64(i64 %m4)153 ret void154}155 156define void @btc_depends_on_div_mul(i64 %x) {157; CHECK-LABEL: 'btc_depends_on_div_mul'158; CHECK-NEXT: Classifying expressions for: @btc_depends_on_div_mul159; CHECK-NEXT: %mul.2 = shl i64 %x, 1160; CHECK-NEXT: --> (2 * %x) U: [0,-1) S: [-9223372036854775808,9223372036854775807)161; CHECK-NEXT: %div.16 = lshr exact i64 %mul.2, 4162; CHECK-NEXT: --> ((2 * %x) /u 16) U: [0,1152921504606846976) S: [0,1152921504606846976)163; CHECK-NEXT: %masked = and i64 %div.16, 1152921504606846974164; CHECK-NEXT: --> (2 * ((2 * %x) /u 32))<nuw><nsw> U: [0,1152921504606846975) S: [0,1152921504606846975)165; CHECK-NEXT: %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop ]166; CHECK-NEXT: --> {0,+,2}<%loop> U: [0,-1) S: [-9223372036854775808,9223372036854775807) Exits: (-2 + (2 * ((2 * %x) /u 32))<nuw><nsw>)<nsw> LoopDispositions: { %loop: Computable }167; CHECK-NEXT: %iv.next = add i64 %iv, 2168; CHECK-NEXT: --> {2,+,2}<%loop> U: [0,-1) S: [-9223372036854775808,9223372036854775807) Exits: (2 * ((2 * %x) /u 32))<nuw><nsw> LoopDispositions: { %loop: Computable }169; CHECK-NEXT: Determining loop execution counts for: @btc_depends_on_div_mul170; CHECK-NEXT: Loop %loop: backedge-taken count is ((-2 + (2 * ((2 * %x) /u 32))<nuw><nsw>)<nsw> /u 2)171; CHECK-NEXT: Loop %loop: constant max backedge-taken count is i64 9223372036854775807172; CHECK-NEXT: Loop %loop: symbolic max backedge-taken count is ((-2 + (2 * ((2 * %x) /u 32))<nuw><nsw>)<nsw> /u 2)173; CHECK-NEXT: Loop %loop: Trip multiple is 1174;175entry:176 %mul.2 = shl i64 %x, 1177 %div.16 = lshr exact i64 %mul.2, 4178 %masked = and i64 %div.16, 1152921504606846974179 br label %loop180 181loop:182 %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop ]183 call void @use.i64(i64 %iv)184 %iv.next = add i64 %iv, 2185 %ec = icmp eq i64 %iv.next, %masked186 br i1 %ec, label %exit, label %loop187 188exit:189 ret void190}191 192define noundef i64 @udiv_mul_common_vscale_factor(i64 %a, i64 %b) {193; CHECK-LABEL: 'udiv_mul_common_vscale_factor'194; CHECK-NEXT: Classifying expressions for: @udiv_mul_common_vscale_factor195; CHECK-NEXT: %vs = call i64 @llvm.vscale.i64()196; CHECK-NEXT: --> vscale U: [1,0) S: [1,0)197; CHECK-NEXT: %a.vs = mul i64 %a, %vs198; CHECK-NEXT: --> (vscale * %a) U: full-set S: full-set199; CHECK-NEXT: %b.vs = mul i64 %b, %vs200; CHECK-NEXT: --> (vscale * %b) U: full-set S: full-set201; CHECK-NEXT: %div = udiv i64 %a.vs, %b.vs202; CHECK-NEXT: --> ((vscale * %a) /u (vscale * %b)) U: full-set S: full-set203; CHECK-NEXT: Determining loop execution counts for: @udiv_mul_common_vscale_factor204;205 %vs = call i64 @llvm.vscale()206 %a.vs = mul i64 %a, %vs207 %b.vs = mul i64 %b, %vs208 %div = udiv i64 %a.vs, %b.vs209 ret i64 %div210}211 212define noundef i64 @udiv_mul_nuw_common_vscale_factor(i64 %a, i64 %b) {213; CHECK-LABEL: 'udiv_mul_nuw_common_vscale_factor'214; CHECK-NEXT: Classifying expressions for: @udiv_mul_nuw_common_vscale_factor215; CHECK-NEXT: %vs = call i64 @llvm.vscale.i64()216; CHECK-NEXT: --> vscale U: [1,0) S: [1,0)217; CHECK-NEXT: %a.vs = mul nuw i64 %a, %vs218; CHECK-NEXT: --> (vscale * %a)<nuw> U: full-set S: full-set219; CHECK-NEXT: %b.vs = mul nuw i64 %b, %vs220; CHECK-NEXT: --> (vscale * %b)<nuw> U: full-set S: full-set221; CHECK-NEXT: %div = udiv i64 %a.vs, %b.vs222; CHECK-NEXT: --> (%a /u %b) U: full-set S: full-set223; CHECK-NEXT: Determining loop execution counts for: @udiv_mul_nuw_common_vscale_factor224;225 %vs = call i64 @llvm.vscale()226 %a.vs = mul nuw i64 %a, %vs227 %b.vs = mul nuw i64 %b, %vs228 %div = udiv i64 %a.vs, %b.vs229 ret i64 %div230}231