864 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; Test cases that require rewriting zext SCEV expression with infomration from5; the loop guards.6 7define void @rewrite_zext(i32 %n) {8; CHECK-LABEL: 'rewrite_zext'9; CHECK-NEXT: Classifying expressions for: @rewrite_zext10; CHECK-NEXT: %ext = zext i32 %n to i6411; CHECK-NEXT: --> (zext i32 %n to i64) U: [0,4294967296) S: [0,4294967296)12; CHECK-NEXT: %n.vec = and i64 %ext, -813; CHECK-NEXT: --> (8 * ((zext i32 %n to i64) /u 8))<nuw><nsw> U: [0,4294967289) S: [0,4294967289)14; CHECK-NEXT: %index = phi i64 [ 0, %check ], [ %index.next, %loop ]15; CHECK-NEXT: --> {0,+,8}<nuw><nsw><%loop> U: [0,17) S: [0,17) Exits: (-8 + (8 * ((zext i32 %n to i64) /u 8))<nuw><nsw>)<nsw> LoopDispositions: { %loop: Computable }16; CHECK-NEXT: %index.next = add nuw nsw i64 %index, 817; CHECK-NEXT: --> {8,+,8}<nuw><nsw><%loop> U: [8,25) S: [8,25) Exits: (8 * ((zext i32 %n to i64) /u 8))<nuw><nsw> LoopDispositions: { %loop: Computable }18; CHECK-NEXT: Determining loop execution counts for: @rewrite_zext19; CHECK-NEXT: Loop %loop: backedge-taken count is ((-8 + (8 * ((zext i32 %n to i64) /u 8))<nuw><nsw>)<nsw> /u 8)20; CHECK-NEXT: Loop %loop: constant max backedge-taken count is i64 221; CHECK-NEXT: Loop %loop: symbolic max backedge-taken count is ((-8 + (8 * ((zext i32 %n to i64) /u 8))<nuw><nsw>)<nsw> /u 8)22; CHECK-NEXT: Loop %loop: Trip multiple is 123;24entry:25 %ext = zext i32 %n to i6426 %cmp5 = icmp ule i64 %ext, 2427 br i1 %cmp5, label %check, label %exit28 29check: ; preds = %entry30 %min.iters.check = icmp ult i64 %ext, 831 %n.vec = and i64 %ext, -832 br i1 %min.iters.check, label %exit, label %loop33 34loop:35 %index = phi i64 [ 0, %check ], [ %index.next, %loop ]36 %index.next = add nuw nsw i64 %index, 837 %ec = icmp eq i64 %index.next, %n.vec38 br i1 %ec, label %exit, label %loop39 40exit:41 ret void42}43 44; Test case from PR40961.45define i32 @rewrite_zext_min_max(i32 %N, ptr %arr) {46; CHECK-LABEL: 'rewrite_zext_min_max'47; CHECK-NEXT: Classifying expressions for: @rewrite_zext_min_max48; CHECK-NEXT: %umin = call i32 @llvm.umin.i32(i32 %N, i32 16)49; CHECK-NEXT: --> (16 umin %N) U: [0,17) S: [0,17)50; CHECK-NEXT: %ext = zext i32 %umin to i6451; CHECK-NEXT: --> (16 umin (zext i32 %N to i64)) U: [0,17) S: [0,17)52; CHECK-NEXT: %n.vec = and i64 %ext, 2853; CHECK-NEXT: --> (4 * ((16 umin (zext i32 %N to i64)) /u 4))<nuw><nsw> U: [0,17) S: [0,17)54; CHECK-NEXT: %index = phi i64 [ 0, %loop.ph ], [ %index.next, %loop ]55; CHECK-NEXT: --> {0,+,4}<nuw><nsw><%loop> U: [0,13) S: [0,13) Exits: (-4 + (4 * ((16 umin (zext i32 %N to i64)) /u 4))<nuw><nsw>)<nsw> LoopDispositions: { %loop: Computable }56; CHECK-NEXT: %gep = getelementptr inbounds i32, ptr %arr, i64 %index57; CHECK-NEXT: --> {%arr,+,16}<nuw><%loop> U: full-set S: full-set Exits: ((16 * ((-4 + (4 * ((16 umin (zext i32 %N to i64)) /u 4))<nuw><nsw>)<nsw> /u 4)) + %arr) LoopDispositions: { %loop: Computable }58; CHECK-NEXT: %index.next = add nuw i64 %index, 459; CHECK-NEXT: --> {4,+,4}<nuw><nsw><%loop> U: [4,17) S: [4,17) Exits: (4 * ((16 umin (zext i32 %N to i64)) /u 4))<nuw><nsw> LoopDispositions: { %loop: Computable }60; CHECK-NEXT: Determining loop execution counts for: @rewrite_zext_min_max61; CHECK-NEXT: Loop %loop: backedge-taken count is ((-4 + (4 * ((16 umin (zext i32 %N to i64)) /u 4))<nuw><nsw>)<nsw> /u 4)62; CHECK-NEXT: Loop %loop: constant max backedge-taken count is i64 363; CHECK-NEXT: Loop %loop: symbolic max backedge-taken count is ((-4 + (4 * ((16 umin (zext i32 %N to i64)) /u 4))<nuw><nsw>)<nsw> /u 4)64; CHECK-NEXT: Loop %loop: Trip multiple is 165;66entry:67 %umin = call i32 @llvm.umin.i32(i32 %N, i32 16)68 %ext = zext i32 %umin to i6469 %min.iters.check = icmp ult i64 %ext, 470 br i1 %min.iters.check, label %exit, label %loop.ph71 72loop.ph:73 %n.vec = and i64 %ext, 2874 br label %loop75 76; %n.vec is [4, 16) and a multiple of 4.77loop:78 %index = phi i64 [ 0, %loop.ph ], [ %index.next, %loop ]79 %gep = getelementptr inbounds i32, ptr %arr, i64 %index80 store i32 0, ptr %gep81 %index.next = add nuw i64 %index, 482 %ec = icmp eq i64 %index.next, %n.vec83 br i1 %ec, label %exit, label %loop84 85exit:86 ret i32 087}88 89; This is same as rewrite_zext_min_max, but zext and umin are swapped.90; It should be able to prove the same exit count.91define i32 @rewrite_min_max_zext(i32 %N, ptr %arr) {92; CHECK-LABEL: 'rewrite_min_max_zext'93; CHECK-NEXT: Classifying expressions for: @rewrite_min_max_zext94; CHECK-NEXT: %N.wide = zext i32 %N to i6495; CHECK-NEXT: --> (zext i32 %N to i64) U: [0,4294967296) S: [0,4294967296)96; CHECK-NEXT: %umin = call i64 @llvm.umin.i64(i64 %N.wide, i64 16)97; CHECK-NEXT: --> (16 umin (zext i32 %N to i64)) U: [0,17) S: [0,17)98; CHECK-NEXT: %n.vec = and i64 %umin, 2899; CHECK-NEXT: --> (4 * ((16 umin (zext i32 %N to i64)) /u 4))<nuw><nsw> U: [0,17) S: [0,17)100; CHECK-NEXT: %index = phi i64 [ 0, %loop.ph ], [ %index.next, %loop ]101; CHECK-NEXT: --> {0,+,4}<nuw><nsw><%loop> U: [0,13) S: [0,13) Exits: (-4 + (4 * ((16 umin (zext i32 %N to i64)) /u 4))<nuw><nsw>)<nsw> LoopDispositions: { %loop: Computable }102; CHECK-NEXT: %gep = getelementptr inbounds i32, ptr %arr, i64 %index103; CHECK-NEXT: --> {%arr,+,16}<nuw><%loop> U: full-set S: full-set Exits: ((16 * ((-4 + (4 * ((16 umin (zext i32 %N to i64)) /u 4))<nuw><nsw>)<nsw> /u 4)) + %arr) LoopDispositions: { %loop: Computable }104; CHECK-NEXT: %index.next = add nuw i64 %index, 4105; CHECK-NEXT: --> {4,+,4}<nuw><nsw><%loop> U: [4,17) S: [4,17) Exits: (4 * ((16 umin (zext i32 %N to i64)) /u 4))<nuw><nsw> LoopDispositions: { %loop: Computable }106; CHECK-NEXT: Determining loop execution counts for: @rewrite_min_max_zext107; CHECK-NEXT: Loop %loop: backedge-taken count is ((-4 + (4 * ((16 umin (zext i32 %N to i64)) /u 4))<nuw><nsw>)<nsw> /u 4)108; CHECK-NEXT: Loop %loop: constant max backedge-taken count is i64 3109; CHECK-NEXT: Loop %loop: symbolic max backedge-taken count is ((-4 + (4 * ((16 umin (zext i32 %N to i64)) /u 4))<nuw><nsw>)<nsw> /u 4)110; CHECK-NEXT: Loop %loop: Trip multiple is 1111;112entry:113 %N.wide = zext i32 %N to i64114 %umin = call i64 @llvm.umin.i64(i64 %N.wide, i64 16)115 %min.iters.check = icmp ult i64 %umin, 4116 br i1 %min.iters.check, label %exit, label %loop.ph117 118loop.ph:119 %n.vec = and i64 %umin, 28120 br label %loop121 122; %n.vec is [4, 16) and a multiple of 4.123loop:124 %index = phi i64 [ 0, %loop.ph ], [ %index.next, %loop ]125 %gep = getelementptr inbounds i32, ptr %arr, i64 %index126 store i32 0, ptr %gep127 %index.next = add nuw i64 %index, 4128 %ec = icmp eq i64 %index.next, %n.vec129 br i1 %ec, label %exit, label %loop130 131exit:132 ret i32 0133}134 135; same as rewrite_zext_min_max, but everything is signed.136; It should be able to prove the same exit count.137define i32 @rewrite_sext_min_max(i32 %N, ptr %arr) {138; CHECK-LABEL: 'rewrite_sext_min_max'139; CHECK-NEXT: Classifying expressions for: @rewrite_sext_min_max140; CHECK-NEXT: %smin = call i32 @llvm.smin.i32(i32 %N, i32 16)141; CHECK-NEXT: --> (16 smin %N) U: [-2147483648,17) S: [-2147483648,17)142; CHECK-NEXT: %ext = sext i32 %smin to i64143; CHECK-NEXT: --> (16 smin (sext i32 %N to i64)) U: [-2147483648,17) S: [-2147483648,17)144; CHECK-NEXT: %n.vec = and i64 %ext, 28145; CHECK-NEXT: --> (4 * (zext i3 (trunc i64 ((16 smin (sext i32 %N to i64)) /u 4) to i3) to i64))<nuw><nsw> U: [0,29) S: [0,29)146; CHECK-NEXT: %index = phi i64 [ 0, %loop.ph ], [ %index.next, %loop ]147; CHECK-NEXT: --> {0,+,4}<nuw><nsw><%loop> U: [0,13) S: [0,13) Exits: (-4 + (4 * (zext i3 (trunc i64 ((16 smin (sext i32 %N to i64)) /u 4) to i3) to i64))<nuw><nsw>)<nsw> LoopDispositions: { %loop: Computable }148; CHECK-NEXT: %gep = getelementptr inbounds i32, ptr %arr, i64 %index149; CHECK-NEXT: --> {%arr,+,16}<nuw><%loop> U: full-set S: full-set Exits: ((16 * ((-4 + (4 * (zext i3 (trunc i64 ((16 smin (sext i32 %N to i64)) /u 4) to i3) to i64))<nuw><nsw>)<nsw> /u 4)) + %arr) LoopDispositions: { %loop: Computable }150; CHECK-NEXT: %index.next = add nsw i64 %index, 4151; CHECK-NEXT: --> {4,+,4}<nuw><nsw><%loop> U: [4,17) S: [4,17) Exits: (4 * (zext i3 (trunc i64 ((16 smin (sext i32 %N to i64)) /u 4) to i3) to i64))<nuw><nsw> LoopDispositions: { %loop: Computable }152; CHECK-NEXT: Determining loop execution counts for: @rewrite_sext_min_max153; CHECK-NEXT: Loop %loop: backedge-taken count is ((-4 + (4 * (zext i3 (trunc i64 ((16 smin (sext i32 %N to i64)) /u 4) to i3) to i64))<nuw><nsw>)<nsw> /u 4)154; CHECK-NEXT: Loop %loop: constant max backedge-taken count is i64 3155; CHECK-NEXT: Loop %loop: symbolic max backedge-taken count is ((-4 + (4 * (zext i3 (trunc i64 ((16 smin (sext i32 %N to i64)) /u 4) to i3) to i64))<nuw><nsw>)<nsw> /u 4)156; CHECK-NEXT: Loop %loop: Trip multiple is 1157;158entry:159 %smin = call i32 @llvm.smin.i32(i32 %N, i32 16)160 %ext = sext i32 %smin to i64161 %min.iters.check = icmp slt i64 %ext, 4162 br i1 %min.iters.check, label %exit, label %loop.ph163 164loop.ph:165 %n.vec = and i64 %ext, 28166 br label %loop167 168; %n.vec is [4, 16) and a multiple of 4.169loop:170 %index = phi i64 [ 0, %loop.ph ], [ %index.next, %loop ]171 %gep = getelementptr inbounds i32, ptr %arr, i64 %index172 store i32 0, ptr %gep173 %index.next = add nsw i64 %index, 4174 %ec = icmp eq i64 %index.next, %n.vec175 br i1 %ec, label %exit, label %loop176 177exit:178 ret i32 0179}180 181; This is a signed version of rewrite_min_max_zext.182; It should be able to prove the same exit count.183define i32 @rewrite_min_max_sext(i32 %N, ptr %arr) {184; CHECK-LABEL: 'rewrite_min_max_sext'185; CHECK-NEXT: Classifying expressions for: @rewrite_min_max_sext186; CHECK-NEXT: %N.wide = sext i32 %N to i64187; CHECK-NEXT: --> (sext i32 %N to i64) U: [-2147483648,2147483648) S: [-2147483648,2147483648)188; CHECK-NEXT: %smin = call i64 @llvm.smin.i64(i64 %N.wide, i64 16)189; CHECK-NEXT: --> (16 smin (sext i32 %N to i64)) U: [-2147483648,17) S: [-2147483648,17)190; CHECK-NEXT: %n.vec = and i64 %smin, 28191; CHECK-NEXT: --> (4 * (zext i3 (trunc i64 ((16 smin (sext i32 %N to i64)) /u 4) to i3) to i64))<nuw><nsw> U: [0,29) S: [0,29)192; CHECK-NEXT: %index = phi i64 [ 0, %loop.ph ], [ %index.next, %loop ]193; CHECK-NEXT: --> {0,+,4}<nuw><nsw><%loop> U: [0,13) S: [0,13) Exits: (-4 + (4 * (zext i3 (trunc i64 ((16 smin (sext i32 %N to i64)) /u 4) to i3) to i64))<nuw><nsw>)<nsw> LoopDispositions: { %loop: Computable }194; CHECK-NEXT: %gep = getelementptr inbounds i32, ptr %arr, i64 %index195; CHECK-NEXT: --> {%arr,+,16}<nuw><%loop> U: full-set S: full-set Exits: ((16 * ((-4 + (4 * (zext i3 (trunc i64 ((16 smin (sext i32 %N to i64)) /u 4) to i3) to i64))<nuw><nsw>)<nsw> /u 4)) + %arr) LoopDispositions: { %loop: Computable }196; CHECK-NEXT: %index.next = add nsw i64 %index, 4197; CHECK-NEXT: --> {4,+,4}<nuw><nsw><%loop> U: [4,17) S: [4,17) Exits: (4 * (zext i3 (trunc i64 ((16 smin (sext i32 %N to i64)) /u 4) to i3) to i64))<nuw><nsw> LoopDispositions: { %loop: Computable }198; CHECK-NEXT: Determining loop execution counts for: @rewrite_min_max_sext199; CHECK-NEXT: Loop %loop: backedge-taken count is ((-4 + (4 * (zext i3 (trunc i64 ((16 smin (sext i32 %N to i64)) /u 4) to i3) to i64))<nuw><nsw>)<nsw> /u 4)200; CHECK-NEXT: Loop %loop: constant max backedge-taken count is i64 3201; CHECK-NEXT: Loop %loop: symbolic max backedge-taken count is ((-4 + (4 * (zext i3 (trunc i64 ((16 smin (sext i32 %N to i64)) /u 4) to i3) to i64))<nuw><nsw>)<nsw> /u 4)202; CHECK-NEXT: Loop %loop: Trip multiple is 1203;204entry:205 %N.wide = sext i32 %N to i64206 %smin = call i64 @llvm.smin.i64(i64 %N.wide, i64 16)207 %min.iters.check = icmp slt i64 %smin, 4208 br i1 %min.iters.check, label %exit, label %loop.ph209 210loop.ph:211 %n.vec = and i64 %smin, 28212 br label %loop213 214; %n.vec is [4, 16) and a multiple of 4.215loop:216 %index = phi i64 [ 0, %loop.ph ], [ %index.next, %loop ]217 %gep = getelementptr inbounds i32, ptr %arr, i64 %index218 store i32 0, ptr %gep219 %index.next = add nsw i64 %index, 4220 %ec = icmp eq i64 %index.next, %n.vec221 br i1 %ec, label %exit, label %loop222 223exit:224 ret i32 0225}226 227; Test case from PR52464. applyLoopGuards needs to apply information about %and228; to %ext, which requires rewriting the zext.229define i32 @rewrite_zext_with_info_from_icmp_ne(i32 %N) {230; CHECK-LABEL: 'rewrite_zext_with_info_from_icmp_ne'231; CHECK-NEXT: Classifying expressions for: @rewrite_zext_with_info_from_icmp_ne232; CHECK-NEXT: %and = and i32 %N, 3233; CHECK-NEXT: --> (zext i2 (trunc i32 %N to i2) to i32) U: [0,4) S: [0,4)234; CHECK-NEXT: %and.sub.1 = add nsw i32 %and, -1235; CHECK-NEXT: --> (-1 + (zext i2 (trunc i32 %N to i2) to i32))<nsw> U: [-1,3) S: [-1,3)236; CHECK-NEXT: %ext = zext i32 %and.sub.1 to i64237; CHECK-NEXT: --> (zext i32 (-1 + (zext i2 (trunc i32 %N to i2) to i32))<nsw> to i64) U: [0,4294967296) S: [0,4294967296)238; CHECK-NEXT: %n.rnd.up = add nuw nsw i64 %ext, 4239; CHECK-NEXT: --> (4 + (zext i32 (-1 + (zext i2 (trunc i32 %N to i2) to i32))<nsw> to i64))<nuw><nsw> U: [4,4294967300) S: [4,4294967300)240; CHECK-NEXT: %n.vec = and i64 %n.rnd.up, 8589934588241; CHECK-NEXT: --> (4 * ((4 + (zext i32 (-1 + (zext i2 (trunc i32 %N to i2) to i32))<nsw> to i64))<nuw><nsw> /u 4))<nuw><nsw> U: [4,4294967297) S: [4,4294967297)242; CHECK-NEXT: %iv = phi i64 [ 0, %loop.ph ], [ %iv.next, %loop ]243; CHECK-NEXT: --> {0,+,4}<nuw><nsw><%loop> U: [0,1) S: [0,1) Exits: 0 LoopDispositions: { %loop: Computable }244; CHECK-NEXT: %iv.next = add i64 %iv, 4245; CHECK-NEXT: --> {4,+,4}<nuw><nsw><%loop> U: [4,5) S: [4,5) Exits: 4 LoopDispositions: { %loop: Computable }246; CHECK-NEXT: Determining loop execution counts for: @rewrite_zext_with_info_from_icmp_ne247; CHECK-NEXT: Loop %loop: backedge-taken count is i64 0248; CHECK-NEXT: Loop %loop: constant max backedge-taken count is i64 0249; CHECK-NEXT: Loop %loop: symbolic max backedge-taken count is i64 0250; CHECK-NEXT: Loop %loop: Trip multiple is 1251;252entry:253 %and = and i32 %N, 3254 %cmp6.not = icmp eq i32 %and, 0255 br i1 %cmp6.not, label %exit, label %loop.ph256 257loop.ph:258 %and.sub.1 = add nsw i32 %and, -1259 %ext = zext i32 %and.sub.1 to i64260 %n.rnd.up = add nuw nsw i64 %ext, 4261 %n.vec = and i64 %n.rnd.up, 8589934588262 br label %loop263 264loop:265 %iv = phi i64 [ 0, %loop.ph ], [ %iv.next, %loop ]266 %iv.next = add i64 %iv, 4267 call void @use(i64 %iv.next)268 %ec = icmp eq i64 %iv.next, %n.vec269 br i1 %ec, label %exit, label %loop270 271exit:272 ret i32 0273}274 275; Similar to @rewrite_zext_with_info_from_icmp_ne, but the loop is not guarded by %and != 0,276; hence the subsequent subtraction may yield a negative number.277define i32 @rewrite_zext_no_icmp_ne(i32 %N) {278; CHECK-LABEL: 'rewrite_zext_no_icmp_ne'279; CHECK-NEXT: Classifying expressions for: @rewrite_zext_no_icmp_ne280; CHECK-NEXT: %and = and i32 %N, 3281; CHECK-NEXT: --> (zext i2 (trunc i32 %N to i2) to i32) U: [0,4) S: [0,4)282; CHECK-NEXT: %and.sub.1 = add nsw i32 %and, -1283; CHECK-NEXT: --> (-1 + (zext i2 (trunc i32 %N to i2) to i32))<nsw> U: [-1,3) S: [-1,3)284; CHECK-NEXT: %ext = zext i32 %and.sub.1 to i64285; CHECK-NEXT: --> (zext i32 (-1 + (zext i2 (trunc i32 %N to i2) to i32))<nsw> to i64) U: [0,4294967296) S: [0,4294967296)286; CHECK-NEXT: %n.rnd.up = add nuw nsw i64 %ext, 4287; CHECK-NEXT: --> (4 + (zext i32 (-1 + (zext i2 (trunc i32 %N to i2) to i32))<nsw> to i64))<nuw><nsw> U: [4,4294967300) S: [4,4294967300)288; CHECK-NEXT: %n.vec = and i64 %n.rnd.up, 8589934588289; CHECK-NEXT: --> (4 * ((4 + (zext i32 (-1 + (zext i2 (trunc i32 %N to i2) to i32))<nsw> to i64))<nuw><nsw> /u 4))<nuw><nsw> U: [4,4294967297) S: [4,4294967297)290; CHECK-NEXT: %iv = phi i64 [ 0, %loop.ph ], [ %iv.next, %loop ]291; CHECK-NEXT: --> {0,+,4}<nuw><nsw><%loop> U: [0,4294967293) S: [0,4294967293) Exits: (-4 + (4 * ((4 + (zext i32 (-1 + (zext i2 (trunc i32 %N to i2) to i32))<nsw> to i64))<nuw><nsw> /u 4))<nuw><nsw>)<nsw> LoopDispositions: { %loop: Computable }292; CHECK-NEXT: %iv.next = add i64 %iv, 4293; CHECK-NEXT: --> {4,+,4}<nuw><nsw><%loop> U: [4,4294967297) S: [4,4294967297) Exits: (4 * ((4 + (zext i32 (-1 + (zext i2 (trunc i32 %N to i2) to i32))<nsw> to i64))<nuw><nsw> /u 4))<nuw><nsw> LoopDispositions: { %loop: Computable }294; CHECK-NEXT: Determining loop execution counts for: @rewrite_zext_no_icmp_ne295; CHECK-NEXT: Loop %loop: backedge-taken count is ((-4 + (4 * ((4 + (zext i32 (-1 + (zext i2 (trunc i32 %N to i2) to i32))<nsw> to i64))<nuw><nsw> /u 4))<nuw><nsw>)<nsw> /u 4)296; CHECK-NEXT: Loop %loop: constant max backedge-taken count is i64 1073741823297; CHECK-NEXT: Loop %loop: symbolic max backedge-taken count is ((-4 + (4 * ((4 + (zext i32 (-1 + (zext i2 (trunc i32 %N to i2) to i32))<nsw> to i64))<nuw><nsw> /u 4))<nuw><nsw>)<nsw> /u 4)298; CHECK-NEXT: Loop %loop: Trip multiple is 1299;300entry:301 %and = and i32 %N, 3302 br label %loop.ph303 304loop.ph:305 %and.sub.1 = add nsw i32 %and, -1306 %ext = zext i32 %and.sub.1 to i64307 %n.rnd.up = add nuw nsw i64 %ext, 4308 %n.vec = and i64 %n.rnd.up, 8589934588309 br label %loop310 311loop:312 %iv = phi i64 [ 0, %loop.ph ], [ %iv.next, %loop ]313 %iv.next = add i64 %iv, 4314 call void @use(i64 %iv.next)315 %ec = icmp eq i64 %iv.next, %n.vec316 br i1 %ec, label %exit, label %loop317 318exit:319 ret i32 0320}321 322; Make sure no information is lost for conditions on both %n and (zext %n).323define void @rewrite_zext_and_base_1(i32 %n) {324; CHECK-LABEL: 'rewrite_zext_and_base_1'325; CHECK-NEXT: Classifying expressions for: @rewrite_zext_and_base_1326; CHECK-NEXT: %ext = zext i32 %n to i64327; CHECK-NEXT: --> (zext i32 %n to i64) U: [0,4294967296) S: [0,4294967296)328; CHECK-NEXT: %n.vec = and i64 %ext, -8329; CHECK-NEXT: --> (8 * ((zext i32 %n to i64) /u 8))<nuw><nsw> U: [0,4294967289) S: [0,4294967289)330; CHECK-NEXT: %index = phi i64 [ 0, %check ], [ %index.next, %loop ]331; CHECK-NEXT: --> {0,+,8}<nuw><nsw><%loop> U: [0,25) S: [0,25) Exits: (-8 + (8 * ((zext i32 %n to i64) /u 8))<nuw><nsw>)<nsw> LoopDispositions: { %loop: Computable }332; CHECK-NEXT: %index.next = add nuw nsw i64 %index, 8333; CHECK-NEXT: --> {8,+,8}<nuw><nsw><%loop> U: [8,33) S: [8,33) Exits: (8 * ((zext i32 %n to i64) /u 8))<nuw><nsw> LoopDispositions: { %loop: Computable }334; CHECK-NEXT: Determining loop execution counts for: @rewrite_zext_and_base_1335; CHECK-NEXT: Loop %loop: backedge-taken count is ((-8 + (8 * ((zext i32 %n to i64) /u 8))<nuw><nsw>)<nsw> /u 8)336; CHECK-NEXT: Loop %loop: constant max backedge-taken count is i64 3337; CHECK-NEXT: Loop %loop: symbolic max backedge-taken count is ((-8 + (8 * ((zext i32 %n to i64) /u 8))<nuw><nsw>)<nsw> /u 8)338; CHECK-NEXT: Loop %loop: Trip multiple is 1339;340entry:341 %ext = zext i32 %n to i64342 %cmp5 = icmp ule i64 %ext, 48343 br i1 %cmp5, label %check.1, label %exit344 345check.1:346 %cmp.2 = icmp ule i32 %n, 32347 br i1 %cmp.2, label %check, label %exit348 349 350check: ; preds = %entry351 %min.iters.check = icmp ult i64 %ext, 8352 %n.vec = and i64 %ext, -8353 br i1 %min.iters.check, label %exit, label %loop354 355loop:356 %index = phi i64 [ 0, %check ], [ %index.next, %loop ]357 %index.next = add nuw nsw i64 %index, 8358 %ec = icmp eq i64 %index.next, %n.vec359 br i1 %ec, label %exit, label %loop360 361exit:362 ret void363}364 365; Make sure no information is lost for conditions on both %n and (zext %n).366define void @rewrite_zext_and_base_2(i32 %n) {367; CHECK-LABEL: 'rewrite_zext_and_base_2'368; CHECK-NEXT: Classifying expressions for: @rewrite_zext_and_base_2369; CHECK-NEXT: %ext = zext i32 %n to i64370; CHECK-NEXT: --> (zext i32 %n to i64) U: [0,4294967296) S: [0,4294967296)371; CHECK-NEXT: %n.vec = and i64 %ext, -8372; CHECK-NEXT: --> (8 * ((zext i32 %n to i64) /u 8))<nuw><nsw> U: [0,4294967289) S: [0,4294967289)373; CHECK-NEXT: %index = phi i64 [ 0, %check ], [ %index.next, %loop ]374; CHECK-NEXT: --> {0,+,8}<nuw><nsw><%loop> U: [0,25) S: [0,25) Exits: (-8 + (8 * ((zext i32 %n to i64) /u 8))<nuw><nsw>)<nsw> LoopDispositions: { %loop: Computable }375; CHECK-NEXT: %index.next = add nuw nsw i64 %index, 8376; CHECK-NEXT: --> {8,+,8}<nuw><nsw><%loop> U: [8,33) S: [8,33) Exits: (8 * ((zext i32 %n to i64) /u 8))<nuw><nsw> LoopDispositions: { %loop: Computable }377; CHECK-NEXT: Determining loop execution counts for: @rewrite_zext_and_base_2378; CHECK-NEXT: Loop %loop: backedge-taken count is ((-8 + (8 * ((zext i32 %n to i64) /u 8))<nuw><nsw>)<nsw> /u 8)379; CHECK-NEXT: Loop %loop: constant max backedge-taken count is i64 3380; CHECK-NEXT: Loop %loop: symbolic max backedge-taken count is ((-8 + (8 * ((zext i32 %n to i64) /u 8))<nuw><nsw>)<nsw> /u 8)381; CHECK-NEXT: Loop %loop: Trip multiple is 1382;383entry:384 %ext = zext i32 %n to i64385 %cmp5 = icmp ule i64 %ext, 32386 br i1 %cmp5, label %check.1, label %exit387 388check.1:389 %cmp.2 = icmp ule i32 %n, 48390 br i1 %cmp.2, label %check, label %exit391 392check: ; preds = %entry393 %min.iters.check = icmp ult i64 %ext, 8394 %n.vec = and i64 %ext, -8395 br i1 %min.iters.check, label %exit, label %loop396 397loop:398 %index = phi i64 [ 0, %check ], [ %index.next, %loop ]399 %index.next = add nuw nsw i64 %index, 8400 %ec = icmp eq i64 %index.next, %n.vec401 br i1 %ec, label %exit, label %loop402 403exit:404 ret void405}406 407define void @guard_pessimizes_analysis_step2(i1 %c, i32 %N) {408; CHECK-LABEL: 'guard_pessimizes_analysis_step2'409; CHECK-NEXT: Classifying expressions for: @guard_pessimizes_analysis_step2410; CHECK-NEXT: %N.ext = zext i32 %N to i64411; CHECK-NEXT: --> (zext i32 %N to i64) U: [0,4294967296) S: [0,4294967296)412; CHECK-NEXT: %init = phi i64 [ 2, %entry ], [ 4, %bb1 ]413; CHECK-NEXT: --> %init U: [2,5) S: [2,5)414; CHECK-NEXT: %iv = phi i64 [ %iv.next, %loop ], [ %init, %loop.ph ]415; CHECK-NEXT: --> {%init,+,2}<nuw><nsw><%loop> U: [2,17) S: [2,17) Exits: 14 LoopDispositions: { %loop: Computable }416; CHECK-NEXT: %iv.next = add i64 %iv, 2417; CHECK-NEXT: --> {(2 + %init)<nuw><nsw>,+,2}<nuw><nsw><%loop> U: [4,19) S: [4,19) Exits: 16 LoopDispositions: { %loop: Computable }418; CHECK-NEXT: Determining loop execution counts for: @guard_pessimizes_analysis_step2419; CHECK-NEXT: Loop %loop: backedge-taken count is ((14 + (-1 * %init)<nsw>)<nsw> /u 2)420; CHECK-NEXT: Loop %loop: constant max backedge-taken count is i64 6421; CHECK-NEXT: Loop %loop: symbolic max backedge-taken count is ((14 + (-1 * %init)<nsw>)<nsw> /u 2)422; CHECK-NEXT: Loop %loop: Trip multiple is 1423;424entry:425 %N.ext = zext i32 %N to i64426 br i1 %c, label %bb1, label %guard427 428bb1:429 br label %guard430 431guard:432 %init = phi i64 [ 2, %entry ], [ 4, %bb1 ]433 %c.1 = icmp ult i64 %init, %N.ext434 br i1 %c.1, label %loop.ph, label %exit435 436loop.ph:437 br label %loop438 439loop:440 %iv = phi i64 [ %iv.next, %loop ], [ %init, %loop.ph ]441 %iv.next = add i64 %iv, 2442 %exitcond = icmp eq i64 %iv.next, 16443 br i1 %exitcond, label %exit, label %loop444 445exit:446 ret void447}448 449define i32 @rewrite_sext_slt_narrow_check(i32 %N, ptr %arr) {450; CHECK-LABEL: 'rewrite_sext_slt_narrow_check'451; CHECK-NEXT: Classifying expressions for: @rewrite_sext_slt_narrow_check452; CHECK-NEXT: %smin = call i32 @llvm.smax.i32(i32 %N, i32 4)453; CHECK-NEXT: --> (4 smax %N) U: [4,-2147483648) S: [4,-2147483648)454; CHECK-NEXT: %ext = sext i32 %smin to i64455; CHECK-NEXT: --> (zext i32 (4 smax %N) to i64) U: [4,2147483648) S: [4,2147483648)456; CHECK-NEXT: %n.vec = and i64 %ext, 28457; CHECK-NEXT: --> (4 * (zext i3 (trunc i64 ((zext i32 (4 smax %N) to i64) /u 4) to i3) to i64))<nuw><nsw> U: [0,29) S: [0,29)458; CHECK-NEXT: %index = phi i64 [ 0, %loop.ph ], [ %index.next, %loop ]459; CHECK-NEXT: --> {0,+,4}<nuw><nsw><%loop> U: [0,13) S: [0,13) Exits: (-4 + (4 * (zext i3 (trunc i64 ((zext i32 (4 smax %N) to i64) /u 4) to i3) to i64))<nuw><nsw>)<nsw> LoopDispositions: { %loop: Computable }460; CHECK-NEXT: %gep = getelementptr inbounds i32, ptr %arr, i64 %index461; CHECK-NEXT: --> {%arr,+,16}<nuw><%loop> U: full-set S: full-set Exits: ((16 * ((-4 + (4 * (zext i3 (trunc i64 ((zext i32 (4 smax %N) to i64) /u 4) to i3) to i64))<nuw><nsw>)<nsw> /u 4)) + %arr) LoopDispositions: { %loop: Computable }462; CHECK-NEXT: %index.next = add nuw i64 %index, 4463; CHECK-NEXT: --> {4,+,4}<nuw><nsw><%loop> U: [4,17) S: [4,17) Exits: (4 * (zext i3 (trunc i64 ((zext i32 (4 smax %N) to i64) /u 4) to i3) to i64))<nuw><nsw> LoopDispositions: { %loop: Computable }464; CHECK-NEXT: Determining loop execution counts for: @rewrite_sext_slt_narrow_check465; CHECK-NEXT: Loop %loop: backedge-taken count is ((-4 + (4 * (zext i3 (trunc i64 ((zext i32 (4 smax %N) to i64) /u 4) to i3) to i64))<nuw><nsw>)<nsw> /u 4)466; CHECK-NEXT: Loop %loop: constant max backedge-taken count is i64 3467; CHECK-NEXT: Loop %loop: symbolic max backedge-taken count is ((-4 + (4 * (zext i3 (trunc i64 ((zext i32 (4 smax %N) to i64) /u 4) to i3) to i64))<nuw><nsw>)<nsw> /u 4)468; CHECK-NEXT: Loop %loop: Trip multiple is 1469;470entry:471 %smin = call i32 @llvm.smax.i32(i32 %N, i32 4)472 %ext = sext i32 %smin to i64473 %min.iters.check = icmp slt i32 %smin, 17474 br i1 %min.iters.check, label %loop.ph, label %exit475 476loop.ph:477 %n.vec = and i64 %ext, 28478 br label %loop479 480; %n.vec is [4, 16] and a multiple of 4.481loop:482 %index = phi i64 [ 0, %loop.ph ], [ %index.next, %loop ]483 %gep = getelementptr inbounds i32, ptr %arr, i64 %index484 store i32 0, ptr %gep485 %index.next = add nuw i64 %index, 4486 %ec = icmp eq i64 %index.next, %n.vec487 br i1 %ec, label %exit, label %loop488 489exit:490 ret i32 0491}492 493define i32 @rewrite_zext_ult_narrow_check(i32 %N, ptr %arr) {494; CHECK-LABEL: 'rewrite_zext_ult_narrow_check'495; CHECK-NEXT: Classifying expressions for: @rewrite_zext_ult_narrow_check496; CHECK-NEXT: %umin = call i32 @llvm.umax.i32(i32 %N, i32 4)497; CHECK-NEXT: --> (4 umax %N) U: [4,0) S: [4,0)498; CHECK-NEXT: %ext = zext i32 %umin to i64499; CHECK-NEXT: --> (4 umax (zext i32 %N to i64)) U: [4,4294967296) S: [4,4294967296)500; CHECK-NEXT: %n.vec = and i64 %ext, 28501; CHECK-NEXT: --> (4 * (zext i3 (trunc i64 ((4 umax (zext i32 %N to i64)) /u 4) to i3) to i64))<nuw><nsw> U: [0,29) S: [0,29)502; CHECK-NEXT: %index = phi i64 [ 0, %loop.ph ], [ %index.next, %loop ]503; CHECK-NEXT: --> {0,+,4}<nuw><nsw><%loop> U: [0,13) S: [0,13) Exits: (-4 + (4 * (zext i3 (trunc i64 ((4 umax (zext i32 %N to i64)) /u 4) to i3) to i64))<nuw><nsw>)<nsw> LoopDispositions: { %loop: Computable }504; CHECK-NEXT: %gep = getelementptr inbounds i32, ptr %arr, i64 %index505; CHECK-NEXT: --> {%arr,+,16}<nuw><%loop> U: full-set S: full-set Exits: ((16 * ((-4 + (4 * (zext i3 (trunc i64 ((4 umax (zext i32 %N to i64)) /u 4) to i3) to i64))<nuw><nsw>)<nsw> /u 4)) + %arr) LoopDispositions: { %loop: Computable }506; CHECK-NEXT: %index.next = add nuw i64 %index, 4507; CHECK-NEXT: --> {4,+,4}<nuw><nsw><%loop> U: [4,17) S: [4,17) Exits: (4 * (zext i3 (trunc i64 ((4 umax (zext i32 %N to i64)) /u 4) to i3) to i64))<nuw><nsw> LoopDispositions: { %loop: Computable }508; CHECK-NEXT: Determining loop execution counts for: @rewrite_zext_ult_narrow_check509; CHECK-NEXT: Loop %loop: backedge-taken count is ((-4 + (4 * (zext i3 (trunc i64 ((4 umax (zext i32 %N to i64)) /u 4) to i3) to i64))<nuw><nsw>)<nsw> /u 4)510; CHECK-NEXT: Loop %loop: constant max backedge-taken count is i64 3511; CHECK-NEXT: Loop %loop: symbolic max backedge-taken count is ((-4 + (4 * (zext i3 (trunc i64 ((4 umax (zext i32 %N to i64)) /u 4) to i3) to i64))<nuw><nsw>)<nsw> /u 4)512; CHECK-NEXT: Loop %loop: Trip multiple is 1513;514entry:515 %umin = call i32 @llvm.umax.i32(i32 %N, i32 4)516 %ext = zext i32 %umin to i64517 %min.iters.check = icmp ult i32 %umin, 17518 br i1 %min.iters.check, label %loop.ph, label %exit519 520loop.ph:521 %n.vec = and i64 %ext, 28522 br label %loop523 524; %n.vec is [4, 16] and a multiple of 4.525loop:526 %index = phi i64 [ 0, %loop.ph ], [ %index.next, %loop ]527 %gep = getelementptr inbounds i32, ptr %arr, i64 %index528 store i32 0, ptr %gep529 %index.next = add nuw i64 %index, 4530 %ec = icmp eq i64 %index.next, %n.vec531 br i1 %ec, label %exit, label %loop532 533exit:534 ret i32 0535}536 537define i32 @rewrite_zext_ule_narrow_check(i32 %N, ptr %arr) {538; CHECK-LABEL: 'rewrite_zext_ule_narrow_check'539; CHECK-NEXT: Classifying expressions for: @rewrite_zext_ule_narrow_check540; CHECK-NEXT: %umin = call i32 @llvm.umax.i32(i32 %N, i32 4)541; CHECK-NEXT: --> (4 umax %N) U: [4,0) S: [4,0)542; CHECK-NEXT: %ext = zext i32 %umin to i64543; CHECK-NEXT: --> (4 umax (zext i32 %N to i64)) U: [4,4294967296) S: [4,4294967296)544; CHECK-NEXT: %n.vec = and i64 %ext, 28545; CHECK-NEXT: --> (4 * (zext i3 (trunc i64 ((4 umax (zext i32 %N to i64)) /u 4) to i3) to i64))<nuw><nsw> U: [0,29) S: [0,29)546; CHECK-NEXT: %index = phi i64 [ 0, %loop.ph ], [ %index.next, %loop ]547; CHECK-NEXT: --> {0,+,4}<nuw><nsw><%loop> U: [0,13) S: [0,13) Exits: (-4 + (4 * (zext i3 (trunc i64 ((4 umax (zext i32 %N to i64)) /u 4) to i3) to i64))<nuw><nsw>)<nsw> LoopDispositions: { %loop: Computable }548; CHECK-NEXT: %gep = getelementptr inbounds i32, ptr %arr, i64 %index549; CHECK-NEXT: --> {%arr,+,16}<nuw><%loop> U: full-set S: full-set Exits: ((16 * ((-4 + (4 * (zext i3 (trunc i64 ((4 umax (zext i32 %N to i64)) /u 4) to i3) to i64))<nuw><nsw>)<nsw> /u 4)) + %arr) LoopDispositions: { %loop: Computable }550; CHECK-NEXT: %index.next = add nuw i64 %index, 4551; CHECK-NEXT: --> {4,+,4}<nuw><nsw><%loop> U: [4,17) S: [4,17) Exits: (4 * (zext i3 (trunc i64 ((4 umax (zext i32 %N to i64)) /u 4) to i3) to i64))<nuw><nsw> LoopDispositions: { %loop: Computable }552; CHECK-NEXT: Determining loop execution counts for: @rewrite_zext_ule_narrow_check553; CHECK-NEXT: Loop %loop: backedge-taken count is ((-4 + (4 * (zext i3 (trunc i64 ((4 umax (zext i32 %N to i64)) /u 4) to i3) to i64))<nuw><nsw>)<nsw> /u 4)554; CHECK-NEXT: Loop %loop: constant max backedge-taken count is i64 3555; CHECK-NEXT: Loop %loop: symbolic max backedge-taken count is ((-4 + (4 * (zext i3 (trunc i64 ((4 umax (zext i32 %N to i64)) /u 4) to i3) to i64))<nuw><nsw>)<nsw> /u 4)556; CHECK-NEXT: Loop %loop: Trip multiple is 1557;558entry:559 %umin = call i32 @llvm.umax.i32(i32 %N, i32 4)560 %ext = zext i32 %umin to i64561 %min.iters.check = icmp ule i32 %umin, 16562 br i1 %min.iters.check, label %loop.ph, label %exit563 564loop.ph:565 %n.vec = and i64 %ext, 28566 br label %loop567 568; %n.vec is [4, 16] and a multiple of 4.569loop:570 %index = phi i64 [ 0, %loop.ph ], [ %index.next, %loop ]571 %gep = getelementptr inbounds i32, ptr %arr, i64 %index572 store i32 0, ptr %gep573 %index.next = add nuw i64 %index, 4574 %ec = icmp eq i64 %index.next, %n.vec575 br i1 %ec, label %exit, label %loop576 577exit:578 ret i32 0579}580 581define i32 @rewrite_zext_sle_narrow_check(i32 %N, ptr %arr) {582; CHECK-LABEL: 'rewrite_zext_sle_narrow_check'583; CHECK-NEXT: Classifying expressions for: @rewrite_zext_sle_narrow_check584; CHECK-NEXT: %smin = call i32 @llvm.smax.i32(i32 %N, i32 4)585; CHECK-NEXT: --> (4 smax %N) U: [4,-2147483648) S: [4,-2147483648)586; CHECK-NEXT: %ext = sext i32 %smin to i64587; CHECK-NEXT: --> (zext i32 (4 smax %N) to i64) U: [4,2147483648) S: [4,2147483648)588; CHECK-NEXT: %n.vec = and i64 %ext, 28589; CHECK-NEXT: --> (4 * (zext i3 (trunc i64 ((zext i32 (4 smax %N) to i64) /u 4) to i3) to i64))<nuw><nsw> U: [0,29) S: [0,29)590; CHECK-NEXT: %index = phi i64 [ 0, %loop.ph ], [ %index.next, %loop ]591; CHECK-NEXT: --> {0,+,4}<nuw><nsw><%loop> U: [0,13) S: [0,13) Exits: (-4 + (4 * (zext i3 (trunc i64 ((zext i32 (4 smax %N) to i64) /u 4) to i3) to i64))<nuw><nsw>)<nsw> LoopDispositions: { %loop: Computable }592; CHECK-NEXT: %gep = getelementptr inbounds i32, ptr %arr, i64 %index593; CHECK-NEXT: --> {%arr,+,16}<nuw><%loop> U: full-set S: full-set Exits: ((16 * ((-4 + (4 * (zext i3 (trunc i64 ((zext i32 (4 smax %N) to i64) /u 4) to i3) to i64))<nuw><nsw>)<nsw> /u 4)) + %arr) LoopDispositions: { %loop: Computable }594; CHECK-NEXT: %index.next = add nuw i64 %index, 4595; CHECK-NEXT: --> {4,+,4}<nuw><nsw><%loop> U: [4,17) S: [4,17) Exits: (4 * (zext i3 (trunc i64 ((zext i32 (4 smax %N) to i64) /u 4) to i3) to i64))<nuw><nsw> LoopDispositions: { %loop: Computable }596; CHECK-NEXT: Determining loop execution counts for: @rewrite_zext_sle_narrow_check597; CHECK-NEXT: Loop %loop: backedge-taken count is ((-4 + (4 * (zext i3 (trunc i64 ((zext i32 (4 smax %N) to i64) /u 4) to i3) to i64))<nuw><nsw>)<nsw> /u 4)598; CHECK-NEXT: Loop %loop: constant max backedge-taken count is i64 3599; CHECK-NEXT: Loop %loop: symbolic max backedge-taken count is ((-4 + (4 * (zext i3 (trunc i64 ((zext i32 (4 smax %N) to i64) /u 4) to i3) to i64))<nuw><nsw>)<nsw> /u 4)600; CHECK-NEXT: Loop %loop: Trip multiple is 1601;602entry:603 %smin = call i32 @llvm.smax.i32(i32 %N, i32 4)604 %ext = sext i32 %smin to i64605 %min.iters.check = icmp sle i32 %smin, 17606 br i1 %min.iters.check, label %loop.ph, label %exit607 608loop.ph:609 %n.vec = and i64 %ext, 28610 br label %loop611 612; %n.vec is [4, 16] and a multiple of 4.613loop:614 %index = phi i64 [ 0, %loop.ph ], [ %index.next, %loop ]615 %gep = getelementptr inbounds i32, ptr %arr, i64 %index616 store i32 0, ptr %gep617 %index.next = add nuw i64 %index, 4618 %ec = icmp eq i64 %index.next, %n.vec619 br i1 %ec, label %exit, label %loop620 621exit:622 ret i32 0623}624 625define i32 @rewrite_zext_uge_narrow_check(i32 %N, ptr %arr) {626; CHECK-LABEL: 'rewrite_zext_uge_narrow_check'627; CHECK-NEXT: Classifying expressions for: @rewrite_zext_uge_narrow_check628; CHECK-NEXT: %umin = call i32 @llvm.umin.i32(i32 %N, i32 16)629; CHECK-NEXT: --> (16 umin %N) U: [0,17) S: [0,17)630; CHECK-NEXT: %ext = zext i32 %umin to i64631; CHECK-NEXT: --> (16 umin (zext i32 %N to i64)) U: [0,17) S: [0,17)632; CHECK-NEXT: %n.vec = and i64 %ext, 28633; CHECK-NEXT: --> (4 * ((16 umin (zext i32 %N to i64)) /u 4))<nuw><nsw> U: [0,17) S: [0,17)634; CHECK-NEXT: %index = phi i64 [ 0, %loop.ph ], [ %index.next, %loop ]635; CHECK-NEXT: --> {0,+,4}<nuw><nsw><%loop> U: [0,13) S: [0,13) Exits: (-4 + (4 * ((16 umin (zext i32 %N to i64)) /u 4))<nuw><nsw>)<nsw> LoopDispositions: { %loop: Computable }636; CHECK-NEXT: %gep = getelementptr inbounds i32, ptr %arr, i64 %index637; CHECK-NEXT: --> {%arr,+,16}<nuw><%loop> U: full-set S: full-set Exits: ((16 * ((-4 + (4 * ((16 umin (zext i32 %N to i64)) /u 4))<nuw><nsw>)<nsw> /u 4)) + %arr) LoopDispositions: { %loop: Computable }638; CHECK-NEXT: %index.next = add nuw i64 %index, 4639; CHECK-NEXT: --> {4,+,4}<nuw><nsw><%loop> U: [4,17) S: [4,17) Exits: (4 * ((16 umin (zext i32 %N to i64)) /u 4))<nuw><nsw> LoopDispositions: { %loop: Computable }640; CHECK-NEXT: Determining loop execution counts for: @rewrite_zext_uge_narrow_check641; CHECK-NEXT: Loop %loop: backedge-taken count is ((-4 + (4 * ((16 umin (zext i32 %N to i64)) /u 4))<nuw><nsw>)<nsw> /u 4)642; CHECK-NEXT: Loop %loop: constant max backedge-taken count is i64 3643; CHECK-NEXT: Loop %loop: symbolic max backedge-taken count is ((-4 + (4 * ((16 umin (zext i32 %N to i64)) /u 4))<nuw><nsw>)<nsw> /u 4)644; CHECK-NEXT: Loop %loop: Trip multiple is 1645;646entry:647 %umin = call i32 @llvm.umin.i32(i32 %N, i32 16)648 %ext = zext i32 %umin to i64649 %min.iters.check = icmp uge i32 %umin, 4650 br i1 %min.iters.check, label %loop.ph, label %exit651 652loop.ph:653 %n.vec = and i64 %ext, 28654 br label %loop655 656; %n.vec is [4, 16] and a multiple of 4.657loop:658 %index = phi i64 [ 0, %loop.ph ], [ %index.next, %loop ]659 %gep = getelementptr inbounds i32, ptr %arr, i64 %index660 store i32 0, ptr %gep661 %index.next = add nuw i64 %index, 4662 %ec = icmp eq i64 %index.next, %n.vec663 br i1 %ec, label %exit, label %loop664 665exit:666 ret i32 0667}668 669define i32 @rewrite_sext_sge_narrow_check(i32 %N, ptr %arr) {670; CHECK-LABEL: 'rewrite_sext_sge_narrow_check'671; CHECK-NEXT: Classifying expressions for: @rewrite_sext_sge_narrow_check672; CHECK-NEXT: %smin = call i32 @llvm.smin.i32(i32 %N, i32 16)673; CHECK-NEXT: --> (16 smin %N) U: [-2147483648,17) S: [-2147483648,17)674; CHECK-NEXT: %ext = sext i32 %smin to i64675; CHECK-NEXT: --> (16 smin (sext i32 %N to i64)) U: [-2147483648,17) S: [-2147483648,17)676; CHECK-NEXT: %n.vec = and i64 %ext, 28677; CHECK-NEXT: --> (4 * (zext i3 (trunc i64 ((16 smin (sext i32 %N to i64)) /u 4) to i3) to i64))<nuw><nsw> U: [0,29) S: [0,29)678; CHECK-NEXT: %index = phi i64 [ 0, %loop.ph ], [ %index.next, %loop ]679; CHECK-NEXT: --> {0,+,4}<nuw><nsw><%loop> U: [0,13) S: [0,13) Exits: (-4 + (4 * (zext i3 (trunc i64 ((16 smin (sext i32 %N to i64)) /u 4) to i3) to i64))<nuw><nsw>)<nsw> LoopDispositions: { %loop: Computable }680; CHECK-NEXT: %gep = getelementptr inbounds i32, ptr %arr, i64 %index681; CHECK-NEXT: --> {%arr,+,16}<nuw><%loop> U: full-set S: full-set Exits: ((16 * ((-4 + (4 * (zext i3 (trunc i64 ((16 smin (sext i32 %N to i64)) /u 4) to i3) to i64))<nuw><nsw>)<nsw> /u 4)) + %arr) LoopDispositions: { %loop: Computable }682; CHECK-NEXT: %index.next = add nuw i64 %index, 4683; CHECK-NEXT: --> {4,+,4}<nuw><nsw><%loop> U: [4,17) S: [4,17) Exits: (4 * (zext i3 (trunc i64 ((16 smin (sext i32 %N to i64)) /u 4) to i3) to i64))<nuw><nsw> LoopDispositions: { %loop: Computable }684; CHECK-NEXT: Determining loop execution counts for: @rewrite_sext_sge_narrow_check685; CHECK-NEXT: Loop %loop: backedge-taken count is ((-4 + (4 * (zext i3 (trunc i64 ((16 smin (sext i32 %N to i64)) /u 4) to i3) to i64))<nuw><nsw>)<nsw> /u 4)686; CHECK-NEXT: Loop %loop: constant max backedge-taken count is i64 3687; CHECK-NEXT: Loop %loop: symbolic max backedge-taken count is ((-4 + (4 * (zext i3 (trunc i64 ((16 smin (sext i32 %N to i64)) /u 4) to i3) to i64))<nuw><nsw>)<nsw> /u 4)688; CHECK-NEXT: Loop %loop: Trip multiple is 1689;690entry:691 %smin = call i32 @llvm.smin.i32(i32 %N, i32 16)692 %ext = sext i32 %smin to i64693 %min.iters.check = icmp sge i32 %smin, 4694 br i1 %min.iters.check, label %loop.ph, label %exit695 696loop.ph:697 %n.vec = and i64 %ext, 28698 br label %loop699 700; %n.vec is [4, 16] and a multiple of 4.701loop:702 %index = phi i64 [ 0, %loop.ph ], [ %index.next, %loop ]703 %gep = getelementptr inbounds i32, ptr %arr, i64 %index704 store i32 0, ptr %gep705 %index.next = add nuw i64 %index, 4706 %ec = icmp eq i64 %index.next, %n.vec707 br i1 %ec, label %exit, label %loop708 709exit:710 ret i32 0711}712 713define i32 @rewrite_zext_ugt_narrow_check(i32 %N, ptr %arr) {714; CHECK-LABEL: 'rewrite_zext_ugt_narrow_check'715; CHECK-NEXT: Classifying expressions for: @rewrite_zext_ugt_narrow_check716; CHECK-NEXT: %umin = call i32 @llvm.umin.i32(i32 %N, i32 16)717; CHECK-NEXT: --> (16 umin %N) U: [0,17) S: [0,17)718; CHECK-NEXT: %ext = zext i32 %umin to i64719; CHECK-NEXT: --> (16 umin (zext i32 %N to i64)) U: [0,17) S: [0,17)720; CHECK-NEXT: %n.vec = and i64 %ext, 28721; CHECK-NEXT: --> (4 * ((16 umin (zext i32 %N to i64)) /u 4))<nuw><nsw> U: [0,17) S: [0,17)722; CHECK-NEXT: %index = phi i64 [ 0, %loop.ph ], [ %index.next, %loop ]723; CHECK-NEXT: --> {0,+,4}<nuw><nsw><%loop> U: [0,13) S: [0,13) Exits: (-4 + (4 * ((16 umin (zext i32 %N to i64)) /u 4))<nuw><nsw>)<nsw> LoopDispositions: { %loop: Computable }724; CHECK-NEXT: %gep = getelementptr inbounds i32, ptr %arr, i64 %index725; CHECK-NEXT: --> {%arr,+,16}<nuw><%loop> U: full-set S: full-set Exits: ((16 * ((-4 + (4 * ((16 umin (zext i32 %N to i64)) /u 4))<nuw><nsw>)<nsw> /u 4)) + %arr) LoopDispositions: { %loop: Computable }726; CHECK-NEXT: %index.next = add nuw i64 %index, 4727; CHECK-NEXT: --> {4,+,4}<nuw><nsw><%loop> U: [4,17) S: [4,17) Exits: (4 * ((16 umin (zext i32 %N to i64)) /u 4))<nuw><nsw> LoopDispositions: { %loop: Computable }728; CHECK-NEXT: Determining loop execution counts for: @rewrite_zext_ugt_narrow_check729; CHECK-NEXT: Loop %loop: backedge-taken count is ((-4 + (4 * ((16 umin (zext i32 %N to i64)) /u 4))<nuw><nsw>)<nsw> /u 4)730; CHECK-NEXT: Loop %loop: constant max backedge-taken count is i64 3731; CHECK-NEXT: Loop %loop: symbolic max backedge-taken count is ((-4 + (4 * ((16 umin (zext i32 %N to i64)) /u 4))<nuw><nsw>)<nsw> /u 4)732; CHECK-NEXT: Loop %loop: Trip multiple is 1733;734entry:735 %umin = call i32 @llvm.umin.i32(i32 %N, i32 16)736 %ext = zext i32 %umin to i64737 %min.iters.check = icmp ugt i32 %umin, 3738 br i1 %min.iters.check, label %loop.ph, label %exit739 740loop.ph:741 %n.vec = and i64 %ext, 28742 br label %loop743 744; %n.vec is [4, 16] and a multiple of 4.745loop:746 %index = phi i64 [ 0, %loop.ph ], [ %index.next, %loop ]747 %gep = getelementptr inbounds i32, ptr %arr, i64 %index748 store i32 0, ptr %gep749 %index.next = add nuw i64 %index, 4750 %ec = icmp eq i64 %index.next, %n.vec751 br i1 %ec, label %exit, label %loop752 753exit:754 ret i32 0755}756 757define i32 @rewrite_sext_sgt_narrow_check(i32 %N, ptr %arr) {758; CHECK-LABEL: 'rewrite_sext_sgt_narrow_check'759; CHECK-NEXT: Classifying expressions for: @rewrite_sext_sgt_narrow_check760; CHECK-NEXT: %smin = call i32 @llvm.smin.i32(i32 %N, i32 16)761; CHECK-NEXT: --> (16 smin %N) U: [-2147483648,17) S: [-2147483648,17)762; CHECK-NEXT: %ext = sext i32 %smin to i64763; CHECK-NEXT: --> (16 smin (sext i32 %N to i64)) U: [-2147483648,17) S: [-2147483648,17)764; CHECK-NEXT: %n.vec = and i64 %ext, 28765; CHECK-NEXT: --> (4 * (zext i3 (trunc i64 ((16 smin (sext i32 %N to i64)) /u 4) to i3) to i64))<nuw><nsw> U: [0,29) S: [0,29)766; CHECK-NEXT: %index = phi i64 [ 0, %loop.ph ], [ %index.next, %loop ]767; CHECK-NEXT: --> {0,+,4}<nuw><nsw><%loop> U: [0,13) S: [0,13) Exits: (-4 + (4 * (zext i3 (trunc i64 ((16 smin (sext i32 %N to i64)) /u 4) to i3) to i64))<nuw><nsw>)<nsw> LoopDispositions: { %loop: Computable }768; CHECK-NEXT: %gep = getelementptr inbounds i32, ptr %arr, i64 %index769; CHECK-NEXT: --> {%arr,+,16}<nuw><%loop> U: full-set S: full-set Exits: ((16 * ((-4 + (4 * (zext i3 (trunc i64 ((16 smin (sext i32 %N to i64)) /u 4) to i3) to i64))<nuw><nsw>)<nsw> /u 4)) + %arr) LoopDispositions: { %loop: Computable }770; CHECK-NEXT: %index.next = add nuw i64 %index, 4771; CHECK-NEXT: --> {4,+,4}<nuw><nsw><%loop> U: [4,17) S: [4,17) Exits: (4 * (zext i3 (trunc i64 ((16 smin (sext i32 %N to i64)) /u 4) to i3) to i64))<nuw><nsw> LoopDispositions: { %loop: Computable }772; CHECK-NEXT: Determining loop execution counts for: @rewrite_sext_sgt_narrow_check773; CHECK-NEXT: Loop %loop: backedge-taken count is ((-4 + (4 * (zext i3 (trunc i64 ((16 smin (sext i32 %N to i64)) /u 4) to i3) to i64))<nuw><nsw>)<nsw> /u 4)774; CHECK-NEXT: Loop %loop: constant max backedge-taken count is i64 3775; CHECK-NEXT: Loop %loop: symbolic max backedge-taken count is ((-4 + (4 * (zext i3 (trunc i64 ((16 smin (sext i32 %N to i64)) /u 4) to i3) to i64))<nuw><nsw>)<nsw> /u 4)776; CHECK-NEXT: Loop %loop: Trip multiple is 1777;778entry:779 %smin = call i32 @llvm.smin.i32(i32 %N, i32 16)780 %ext = sext i32 %smin to i64781 %min.iters.check = icmp sgt i32 %smin, 3782 br i1 %min.iters.check, label %loop.ph, label %exit783 784loop.ph:785 %n.vec = and i64 %ext, 28786 br label %loop787 788; %n.vec is [4, 16) and a multiple of 4.789loop:790 %index = phi i64 [ 0, %loop.ph ], [ %index.next, %loop ]791 %gep = getelementptr inbounds i32, ptr %arr, i64 %index792 store i32 0, ptr %gep793 %index.next = add nuw i64 %index, 4794 %ec = icmp eq i64 %index.next, %n.vec795 br i1 %ec, label %exit, label %loop796 797exit:798 ret i32 0799}800 801define void @rewrite_add_rec() {802; CHECK-LABEL: 'rewrite_add_rec'803; CHECK-NEXT: Classifying expressions for: @rewrite_add_rec804; CHECK-NEXT: %iv = phi i64 [ 0, %entry ], [ %iv.next, %outer.latch ]805; CHECK-NEXT: --> {0,+,1}<nuw><nsw><%outer.header> U: [0,10) S: [0,10) Exits: 9 LoopDispositions: { %outer.header: Computable, %inner: Invariant }806; CHECK-NEXT: %sub = sub i64 9, %iv807; CHECK-NEXT: --> {9,+,-1}<nsw><%outer.header> U: [0,10) S: [0,10) Exits: 0 LoopDispositions: { %outer.header: Computable, %inner: Invariant }808; CHECK-NEXT: %n.vec = and i64 %sub, -2809; CHECK-NEXT: --> (2 * ({9,+,-1}<nsw><%outer.header> /u 2))<nuw><nsw> U: [0,9) S: [0,9) Exits: 0 LoopDispositions: { %outer.header: Computable, %inner: Invariant }810; CHECK-NEXT: %inner.iv = phi i64 [ 0, %inner.ph ], [ %inner.iv.next, %inner ]811; CHECK-NEXT: --> {0,+,2}<%inner> U: [0,-1) S: [-9223372036854775808,9223372036854775807) Exits: (-2 + (2 * ({9,+,-1}<nsw><%outer.header> /u 2))<nuw><nsw>)<nsw> LoopDispositions: { %inner: Computable, %outer.header: Variant }812; CHECK-NEXT: %inner.iv.next = add i64 %inner.iv, 2813; CHECK-NEXT: --> {2,+,2}<%inner> U: [0,-1) S: [-9223372036854775808,9223372036854775807) Exits: (2 * ({9,+,-1}<nsw><%outer.header> /u 2))<nuw><nsw> LoopDispositions: { %inner: Computable, %outer.header: Variant }814; CHECK-NEXT: %iv.next = add i64 %iv, 1815; CHECK-NEXT: --> {1,+,1}<nuw><nsw><%outer.header> U: [1,11) S: [1,11) Exits: 10 LoopDispositions: { %outer.header: Computable, %inner: Invariant }816; CHECK-NEXT: Determining loop execution counts for: @rewrite_add_rec817; CHECK-NEXT: Loop %inner: backedge-taken count is ((-2 + (2 * ({9,+,-1}<nsw><%outer.header> /u 2))<nuw><nsw>)<nsw> /u 2)818; CHECK-NEXT: Loop %inner: constant max backedge-taken count is i64 9223372036854775807819; CHECK-NEXT: Loop %inner: symbolic max backedge-taken count is ((-2 + (2 * ({9,+,-1}<nsw><%outer.header> /u 2))<nuw><nsw>)<nsw> /u 2)820; CHECK-NEXT: Loop %inner: Trip multiple is 1821; CHECK-NEXT: Loop %outer.header: backedge-taken count is i64 9822; CHECK-NEXT: Loop %outer.header: constant max backedge-taken count is i64 9823; CHECK-NEXT: Loop %outer.header: symbolic max backedge-taken count is i64 9824; CHECK-NEXT: Loop %outer.header: Trip multiple is 10825;826entry:827 br label %outer.header828 829outer.header:830 %iv = phi i64 [ 0, %entry ], [ %iv.next, %outer.latch ]831 %sub = sub i64 9, %iv832 %min.iters.check = icmp ult i64 %sub, 2833 br i1 %min.iters.check, label %outer.latch, label %inner.ph834 835inner.ph:836 %n.vec = and i64 %sub, -2837 br label %inner838 839inner:840 %inner.iv = phi i64 [ 0, %inner.ph ], [ %inner.iv.next, %inner ]841 %inner.iv.next = add i64 %inner.iv, 2842 call void @use(i64 %inner.iv)843 %ec.inner = icmp eq i64 %inner.iv.next, %n.vec844 br i1 %ec.inner, label %outer.latch, label %inner845 846outer.latch:847 %iv.next = add i64 %iv, 1848 %ec.outer = icmp eq i64 %iv.next, 10849 br i1 %ec.outer, label %exit, label %outer.header850 851exit:852 ret void853}854 855declare void @use(i64)856 857declare i32 @llvm.umin.i32(i32, i32)858declare i64 @llvm.umin.i64(i64, i64)859declare i32 @llvm.smin.i32(i32, i32)860declare i64 @llvm.smin.i64(i64, i64)861 862declare i32 @llvm.umax.i32(i32, i32)863declare i32 @llvm.smax.i32(i32, i32)864