563 lines · plain
1; NOTE: Assertions have been autogenerated by utils/update_test_checks.py2; RUN: opt -verify-loop-info -irce-print-changed-loops -passes=irce -S < %s 2>&1 | FileCheck %s3; RUN: opt -verify-loop-info -irce-print-changed-loops -passes='require<branch-prob>,irce' -S < %s 2>&1 | FileCheck %s4 5; CHECK-NOT: irce: in function test_01: constrained Loop6; CHECK-NOT: irce: in function test_02: constrained Loop7; CHECK: irce: in function test_03: constrained Loop8 9; RC against known negative value. We should not do IRCE here.10define void @test_01(ptr %arr, i32 %n) {11; CHECK-LABEL: @test_01(12; CHECK-NEXT: entry:13; CHECK-NEXT: [[FIRST_ITR_CHECK:%.*]] = icmp sgt i32 [[N:%.*]], 014; CHECK-NEXT: br i1 [[FIRST_ITR_CHECK]], label [[LOOP_PREHEADER:%.*]], label [[EXIT:%.*]]15; CHECK: loop.preheader:16; CHECK-NEXT: br label [[LOOP:%.*]]17; CHECK: loop:18; CHECK-NEXT: [[IDX:%.*]] = phi i32 [ [[IDX_NEXT:%.*]], [[IN_BOUNDS:%.*]] ], [ 0, [[LOOP_PREHEADER]] ]19; CHECK-NEXT: [[IDX_NEXT]] = add i32 [[IDX]], 120; CHECK-NEXT: [[ABC:%.*]] = icmp slt i32 [[IDX]], -921; CHECK-NEXT: br i1 [[ABC]], label [[IN_BOUNDS]], label [[OUT_OF_BOUNDS:%.*]], !prof [[PROF0:![0-9]+]]22; CHECK: in.bounds:23; CHECK-NEXT: [[ADDR:%.*]] = getelementptr i32, ptr [[ARR:%.*]], i32 [[IDX]]24; CHECK-NEXT: store i32 0, ptr [[ADDR]], align 425; CHECK-NEXT: [[NEXT:%.*]] = icmp slt i32 [[IDX_NEXT]], [[N]]26; CHECK-NEXT: br i1 [[NEXT]], label [[LOOP]], label [[EXIT_LOOPEXIT:%.*]]27; CHECK: out.of.bounds:28; CHECK-NEXT: ret void29; CHECK: exit.loopexit:30; CHECK-NEXT: br label [[EXIT]]31; CHECK: exit:32; CHECK-NEXT: ret void33;34 35 entry:36 %first.itr.check = icmp sgt i32 %n, 037 br i1 %first.itr.check, label %loop, label %exit38 39 loop:40 %idx = phi i32 [ 0, %entry ] , [ %idx.next, %in.bounds ]41 %idx.next = add i32 %idx, 142 %abc = icmp slt i32 %idx, -943 br i1 %abc, label %in.bounds, label %out.of.bounds, !prof !044 45 in.bounds:46 %addr = getelementptr i32, ptr %arr, i32 %idx47 store i32 0, ptr %addr48 %next = icmp slt i32 %idx.next, %n49 br i1 %next, label %loop, label %exit50 51 out.of.bounds:52 ret void53 54 exit:55 ret void56}57 58; Same as test_01, but the latch condition is unsigned.59define void @test_02(ptr %arr, i32 %n) {60; CHECK-LABEL: @test_02(61; CHECK-NEXT: entry:62; CHECK-NEXT: [[FIRST_ITR_CHECK:%.*]] = icmp sgt i32 [[N:%.*]], 063; CHECK-NEXT: br i1 [[FIRST_ITR_CHECK]], label [[LOOP_PREHEADER:%.*]], label [[EXIT:%.*]]64; CHECK: loop.preheader:65; CHECK-NEXT: br label [[LOOP:%.*]]66; CHECK: loop:67; CHECK-NEXT: [[IDX:%.*]] = phi i32 [ [[IDX_NEXT:%.*]], [[IN_BOUNDS:%.*]] ], [ 0, [[LOOP_PREHEADER]] ]68; CHECK-NEXT: [[IDX_NEXT]] = add i32 [[IDX]], 169; CHECK-NEXT: [[ABC:%.*]] = icmp slt i32 [[IDX]], -970; CHECK-NEXT: br i1 [[ABC]], label [[IN_BOUNDS]], label [[OUT_OF_BOUNDS:%.*]], !prof [[PROF0]]71; CHECK: in.bounds:72; CHECK-NEXT: [[ADDR:%.*]] = getelementptr i32, ptr [[ARR:%.*]], i32 [[IDX]]73; CHECK-NEXT: store i32 0, ptr [[ADDR]], align 474; CHECK-NEXT: [[NEXT:%.*]] = icmp ult i32 [[IDX_NEXT]], [[N]]75; CHECK-NEXT: br i1 [[NEXT]], label [[LOOP]], label [[EXIT_LOOPEXIT:%.*]]76; CHECK: out.of.bounds:77; CHECK-NEXT: ret void78; CHECK: exit.loopexit:79; CHECK-NEXT: br label [[EXIT]]80; CHECK: exit:81; CHECK-NEXT: ret void82;83 84 entry:85 %first.itr.check = icmp sgt i32 %n, 086 br i1 %first.itr.check, label %loop, label %exit87 88 loop:89 %idx = phi i32 [ 0, %entry ] , [ %idx.next, %in.bounds ]90 %idx.next = add i32 %idx, 191 %abc = icmp slt i32 %idx, -992 br i1 %abc, label %in.bounds, label %out.of.bounds, !prof !093 94 in.bounds:95 %addr = getelementptr i32, ptr %arr, i32 %idx96 store i32 0, ptr %addr97 %next = icmp ult i32 %idx.next, %n98 br i1 %next, label %loop, label %exit99 100 out.of.bounds:101 ret void102 103 exit:104 ret void105}106 107; RC against a value which is not known to be non-negative. Here we should108; expand runtime checks against bound being positive or negative.109define void @test_03(ptr %arr, i32 %n, i32 %bound) {110; CHECK-LABEL: @test_03(111; CHECK-NEXT: entry:112; CHECK-NEXT: [[FIRST_ITR_CHECK:%.*]] = icmp sgt i32 [[N:%.*]], 0113; CHECK-NEXT: br i1 [[FIRST_ITR_CHECK]], label [[LOOP_PREHEADER:%.*]], label [[EXIT:%.*]]114; CHECK: loop.preheader:115; CHECK-NEXT: [[TMP0:%.*]] = add i32 [[BOUND:%.*]], -2147483647116; CHECK-NEXT: [[SMAX:%.*]] = call i32 @llvm.smax.i32(i32 [[TMP0]], i32 0)117; CHECK-NEXT: [[TMP1:%.*]] = sub i32 [[BOUND]], [[SMAX]]118; CHECK-NEXT: [[SMIN:%.*]] = call i32 @llvm.smin.i32(i32 [[BOUND]], i32 0)119; CHECK-NEXT: [[SMAX1:%.*]] = call i32 @llvm.smax.i32(i32 [[SMIN]], i32 -1)120; CHECK-NEXT: [[TMP2:%.*]] = add nsw i32 [[SMAX1]], 1121; CHECK-NEXT: [[TMP3:%.*]] = mul i32 [[TMP1]], [[TMP2]]122; CHECK-NEXT: [[SMIN2:%.*]] = call i32 @llvm.smin.i32(i32 [[N]], i32 [[TMP3]])123; CHECK-NEXT: [[EXIT_MAINLOOP_AT:%.*]] = call i32 @llvm.smax.i32(i32 [[SMIN2]], i32 0)124; CHECK-NEXT: [[TMP4:%.*]] = icmp slt i32 0, [[EXIT_MAINLOOP_AT]]125; CHECK-NEXT: br i1 [[TMP4]], label [[LOOP_PREHEADER4:%.*]], label [[MAIN_PSEUDO_EXIT:%.*]]126; CHECK: loop.preheader4:127; CHECK-NEXT: br label [[LOOP:%.*]]128; CHECK: loop:129; CHECK-NEXT: [[IDX:%.*]] = phi i32 [ [[IDX_NEXT:%.*]], [[IN_BOUNDS:%.*]] ], [ 0, [[LOOP_PREHEADER4]] ]130; CHECK-NEXT: [[IDX_NEXT]] = add nsw i32 [[IDX]], 1131; CHECK-NEXT: [[ABC:%.*]] = icmp slt i32 [[IDX]], [[BOUND]]132; CHECK-NEXT: br i1 true, label [[IN_BOUNDS]], label [[OUT_OF_BOUNDS_LOOPEXIT5:%.*]], !prof [[PROF0]]133; CHECK: in.bounds:134; CHECK-NEXT: [[ADDR:%.*]] = getelementptr i32, ptr [[ARR:%.*]], i32 [[IDX]]135; CHECK-NEXT: store i32 0, ptr [[ADDR]], align 4136; CHECK-NEXT: [[NEXT:%.*]] = icmp slt i32 [[IDX_NEXT]], [[N]]137; CHECK-NEXT: [[TMP5:%.*]] = icmp slt i32 [[IDX_NEXT]], [[EXIT_MAINLOOP_AT]]138; CHECK-NEXT: br i1 [[TMP5]], label [[LOOP]], label [[MAIN_EXIT_SELECTOR:%.*]]139; CHECK: main.exit.selector:140; CHECK-NEXT: [[IDX_NEXT_LCSSA:%.*]] = phi i32 [ [[IDX_NEXT]], [[IN_BOUNDS]] ]141; CHECK-NEXT: [[TMP6:%.*]] = icmp slt i32 [[IDX_NEXT_LCSSA]], [[N]]142; CHECK-NEXT: br i1 [[TMP6]], label [[MAIN_PSEUDO_EXIT]], label [[EXIT_LOOPEXIT:%.*]]143; CHECK: main.pseudo.exit:144; CHECK-NEXT: [[IDX_COPY:%.*]] = phi i32 [ 0, [[LOOP_PREHEADER]] ], [ [[IDX_NEXT_LCSSA]], [[MAIN_EXIT_SELECTOR]] ]145; CHECK-NEXT: [[INDVAR_END:%.*]] = phi i32 [ 0, [[LOOP_PREHEADER]] ], [ [[IDX_NEXT_LCSSA]], [[MAIN_EXIT_SELECTOR]] ]146; CHECK-NEXT: br label [[POSTLOOP:%.*]]147; CHECK: out.of.bounds.loopexit:148; CHECK-NEXT: br label [[OUT_OF_BOUNDS:%.*]]149; CHECK: out.of.bounds.loopexit5:150; CHECK-NEXT: br label [[OUT_OF_BOUNDS]]151; CHECK: out.of.bounds:152; CHECK-NEXT: ret void153; CHECK: exit.loopexit.loopexit:154; CHECK-NEXT: br label [[EXIT_LOOPEXIT]]155; CHECK: exit.loopexit:156; CHECK-NEXT: br label [[EXIT]]157; CHECK: exit:158; CHECK-NEXT: ret void159; CHECK: postloop:160; CHECK-NEXT: br label [[LOOP_POSTLOOP:%.*]]161; CHECK: loop.postloop:162; CHECK-NEXT: [[IDX_POSTLOOP:%.*]] = phi i32 [ [[IDX_NEXT_POSTLOOP:%.*]], [[IN_BOUNDS_POSTLOOP:%.*]] ], [ [[IDX_COPY]], [[POSTLOOP]] ]163; CHECK-NEXT: [[IDX_NEXT_POSTLOOP]] = add i32 [[IDX_POSTLOOP]], 1164; CHECK-NEXT: [[ABC_POSTLOOP:%.*]] = icmp slt i32 [[IDX_POSTLOOP]], [[BOUND]]165; CHECK-NEXT: br i1 [[ABC_POSTLOOP]], label [[IN_BOUNDS_POSTLOOP]], label [[OUT_OF_BOUNDS_LOOPEXIT:%.*]], !prof [[PROF0]]166; CHECK: in.bounds.postloop:167; CHECK-NEXT: [[ADDR_POSTLOOP:%.*]] = getelementptr i32, ptr [[ARR]], i32 [[IDX_POSTLOOP]]168; CHECK-NEXT: store i32 0, ptr [[ADDR_POSTLOOP]], align 4169; CHECK-NEXT: [[NEXT_POSTLOOP:%.*]] = icmp slt i32 [[IDX_NEXT_POSTLOOP]], [[N]]170; CHECK-NEXT: br i1 [[NEXT_POSTLOOP]], label [[LOOP_POSTLOOP]], label [[EXIT_LOOPEXIT_LOOPEXIT:%.*]], !llvm.loop [[LOOP1:![0-9]+]], !loop_constrainer.loop.clone [[META6:![0-9]+]]171;172 173 entry:174 %first.itr.check = icmp sgt i32 %n, 0175 br i1 %first.itr.check, label %loop, label %exit176 177 loop:178 %idx = phi i32 [ 0, %entry ] , [ %idx.next, %in.bounds ]179 %idx.next = add i32 %idx, 1180 %abc = icmp slt i32 %idx, %bound181 br i1 %abc, label %in.bounds, label %out.of.bounds, !prof !0182 183 in.bounds:184 %addr = getelementptr i32, ptr %arr, i32 %idx185 store i32 0, ptr %addr186 %next = icmp slt i32 %idx.next, %n187 br i1 %next, label %loop, label %exit188 189 out.of.bounds:190 ret void191 192 exit:193 ret void194}195 196; RC against a value which is not known to be non-negative. Here we should197; expand runtime checks against bound being positive or negative.198define void @test_04(ptr %arr, i32 %n, i32 %bound) {199; CHECK-LABEL: @test_04(200; CHECK-NEXT: entry:201; CHECK-NEXT: [[FIRST_ITR_CHECK:%.*]] = icmp sgt i32 [[N:%.*]], 0202; CHECK-NEXT: br i1 [[FIRST_ITR_CHECK]], label [[LOOP_PREHEADER:%.*]], label [[EXIT:%.*]]203; CHECK: loop.preheader:204; CHECK-NEXT: [[SMIN:%.*]] = call i32 @llvm.smin.i32(i32 [[BOUND:%.*]], i32 0)205; CHECK-NEXT: [[TMP0:%.*]] = sub i32 [[BOUND]], [[SMIN]]206; CHECK-NEXT: [[SMAX:%.*]] = call i32 @llvm.smax.i32(i32 [[SMIN]], i32 -1)207; CHECK-NEXT: [[TMP1:%.*]] = add nsw i32 [[SMAX]], 1208; CHECK-NEXT: [[TMP2:%.*]] = mul i32 [[TMP0]], [[TMP1]]209; CHECK-NEXT: [[EXIT_MAINLOOP_AT:%.*]] = call i32 @llvm.umin.i32(i32 [[N]], i32 [[TMP2]])210; CHECK-NEXT: [[TMP3:%.*]] = icmp ult i32 0, [[EXIT_MAINLOOP_AT]]211; CHECK-NEXT: br i1 [[TMP3]], label [[LOOP_PREHEADER1:%.*]], label [[MAIN_PSEUDO_EXIT:%.*]]212; CHECK: loop.preheader1:213; CHECK-NEXT: br label [[LOOP:%.*]]214; CHECK: loop:215; CHECK-NEXT: [[IDX:%.*]] = phi i32 [ [[IDX_NEXT:%.*]], [[IN_BOUNDS:%.*]] ], [ 0, [[LOOP_PREHEADER1]] ]216; CHECK-NEXT: [[IDX_NEXT]] = add i32 [[IDX]], 1217; CHECK-NEXT: [[ABC:%.*]] = icmp slt i32 [[IDX]], [[BOUND]]218; CHECK-NEXT: br i1 true, label [[IN_BOUNDS]], label [[OUT_OF_BOUNDS_LOOPEXIT2:%.*]], !prof [[PROF0]]219; CHECK: in.bounds:220; CHECK-NEXT: [[ADDR:%.*]] = getelementptr i32, ptr [[ARR:%.*]], i32 [[IDX]]221; CHECK-NEXT: store i32 0, ptr [[ADDR]], align 4222; CHECK-NEXT: [[NEXT:%.*]] = icmp ult i32 [[IDX_NEXT]], [[N]]223; CHECK-NEXT: [[TMP4:%.*]] = icmp ult i32 [[IDX_NEXT]], [[EXIT_MAINLOOP_AT]]224; CHECK-NEXT: br i1 [[TMP4]], label [[LOOP]], label [[MAIN_EXIT_SELECTOR:%.*]]225; CHECK: main.exit.selector:226; CHECK-NEXT: [[IDX_NEXT_LCSSA:%.*]] = phi i32 [ [[IDX_NEXT]], [[IN_BOUNDS]] ]227; CHECK-NEXT: [[TMP5:%.*]] = icmp ult i32 [[IDX_NEXT_LCSSA]], [[N]]228; CHECK-NEXT: br i1 [[TMP5]], label [[MAIN_PSEUDO_EXIT]], label [[EXIT_LOOPEXIT:%.*]]229; CHECK: main.pseudo.exit:230; CHECK-NEXT: [[IDX_COPY:%.*]] = phi i32 [ 0, [[LOOP_PREHEADER]] ], [ [[IDX_NEXT_LCSSA]], [[MAIN_EXIT_SELECTOR]] ]231; CHECK-NEXT: [[INDVAR_END:%.*]] = phi i32 [ 0, [[LOOP_PREHEADER]] ], [ [[IDX_NEXT_LCSSA]], [[MAIN_EXIT_SELECTOR]] ]232; CHECK-NEXT: br label [[POSTLOOP:%.*]]233; CHECK: out.of.bounds.loopexit:234; CHECK-NEXT: br label [[OUT_OF_BOUNDS:%.*]]235; CHECK: out.of.bounds.loopexit2:236; CHECK-NEXT: br label [[OUT_OF_BOUNDS]]237; CHECK: out.of.bounds:238; CHECK-NEXT: ret void239; CHECK: exit.loopexit.loopexit:240; CHECK-NEXT: br label [[EXIT_LOOPEXIT]]241; CHECK: exit.loopexit:242; CHECK-NEXT: br label [[EXIT]]243; CHECK: exit:244; CHECK-NEXT: ret void245; CHECK: postloop:246; CHECK-NEXT: br label [[LOOP_POSTLOOP:%.*]]247; CHECK: loop.postloop:248; CHECK-NEXT: [[IDX_POSTLOOP:%.*]] = phi i32 [ [[IDX_NEXT_POSTLOOP:%.*]], [[IN_BOUNDS_POSTLOOP:%.*]] ], [ [[IDX_COPY]], [[POSTLOOP]] ]249; CHECK-NEXT: [[IDX_NEXT_POSTLOOP]] = add i32 [[IDX_POSTLOOP]], 1250; CHECK-NEXT: [[ABC_POSTLOOP:%.*]] = icmp slt i32 [[IDX_POSTLOOP]], [[BOUND]]251; CHECK-NEXT: br i1 [[ABC_POSTLOOP]], label [[IN_BOUNDS_POSTLOOP]], label [[OUT_OF_BOUNDS_LOOPEXIT:%.*]], !prof [[PROF0]]252; CHECK: in.bounds.postloop:253; CHECK-NEXT: [[ADDR_POSTLOOP:%.*]] = getelementptr i32, ptr [[ARR]], i32 [[IDX_POSTLOOP]]254; CHECK-NEXT: store i32 0, ptr [[ADDR_POSTLOOP]], align 4255; CHECK-NEXT: [[NEXT_POSTLOOP:%.*]] = icmp ult i32 [[IDX_NEXT_POSTLOOP]], [[N]]256; CHECK-NEXT: br i1 [[NEXT_POSTLOOP]], label [[LOOP_POSTLOOP]], label [[EXIT_LOOPEXIT_LOOPEXIT:%.*]], !llvm.loop [[LOOP7:![0-9]+]], !loop_constrainer.loop.clone [[META6]]257;258 259 entry:260 %first.itr.check = icmp sgt i32 %n, 0261 br i1 %first.itr.check, label %loop, label %exit262 263 loop:264 %idx = phi i32 [ 0, %entry ] , [ %idx.next, %in.bounds ]265 %idx.next = add i32 %idx, 1266 %abc = icmp slt i32 %idx, %bound267 br i1 %abc, label %in.bounds, label %out.of.bounds, !prof !0268 269 in.bounds:270 %addr = getelementptr i32, ptr %arr, i32 %idx271 store i32 0, ptr %addr272 %next = icmp ult i32 %idx.next, %n273 br i1 %next, label %loop, label %exit274 275 out.of.bounds:276 ret void277 278 exit:279 ret void280}281 282; Same as test_01, unsigned range check.283; FIXME: We could remove the range check here, but it does not happen due to the284; limintation we posed to fix the miscompile (see comments in the method285; computeSafeIterationSpace).286define void @test_05(ptr %arr, i32 %n) {287; CHECK-LABEL: @test_05(288; CHECK-NEXT: entry:289; CHECK-NEXT: [[FIRST_ITR_CHECK:%.*]] = icmp sgt i32 [[N:%.*]], 0290; CHECK-NEXT: br i1 [[FIRST_ITR_CHECK]], label [[LOOP_PREHEADER:%.*]], label [[EXIT:%.*]]291; CHECK: loop.preheader:292; CHECK-NEXT: br label [[LOOP:%.*]]293; CHECK: loop:294; CHECK-NEXT: [[IDX:%.*]] = phi i32 [ [[IDX_NEXT:%.*]], [[IN_BOUNDS:%.*]] ], [ 0, [[LOOP_PREHEADER]] ]295; CHECK-NEXT: [[IDX_NEXT]] = add i32 [[IDX]], 1296; CHECK-NEXT: [[ABC:%.*]] = icmp ult i32 [[IDX]], -9297; CHECK-NEXT: br i1 [[ABC]], label [[IN_BOUNDS]], label [[OUT_OF_BOUNDS:%.*]], !prof [[PROF0]]298; CHECK: in.bounds:299; CHECK-NEXT: [[ADDR:%.*]] = getelementptr i32, ptr [[ARR:%.*]], i32 [[IDX]]300; CHECK-NEXT: store i32 0, ptr [[ADDR]], align 4301; CHECK-NEXT: [[NEXT:%.*]] = icmp slt i32 [[IDX_NEXT]], [[N]]302; CHECK-NEXT: br i1 [[NEXT]], label [[LOOP]], label [[EXIT_LOOPEXIT:%.*]]303; CHECK: out.of.bounds:304; CHECK-NEXT: ret void305; CHECK: exit.loopexit:306; CHECK-NEXT: br label [[EXIT]]307; CHECK: exit:308; CHECK-NEXT: ret void309;310 entry:311 %first.itr.check = icmp sgt i32 %n, 0312 br i1 %first.itr.check, label %loop, label %exit313 314 loop:315 %idx = phi i32 [ 0, %entry ] , [ %idx.next, %in.bounds ]316 %idx.next = add i32 %idx, 1317 %abc = icmp ult i32 %idx, -9318 br i1 %abc, label %in.bounds, label %out.of.bounds, !prof !0319 320 in.bounds:321 %addr = getelementptr i32, ptr %arr, i32 %idx322 store i32 0, ptr %addr323 %next = icmp slt i32 %idx.next, %n324 br i1 %next, label %loop, label %exit325 326 out.of.bounds:327 ret void328 329 exit:330 ret void331}332 333; Same as test_02, unsigned range check.334; FIXME: We could remove the range check here, but it does not happen due to the335; limintation we posed to fix the miscompile (see comments in the method336; computeSafeIterationSpace).337define void @test_06(ptr %arr, i32 %n) {338; CHECK-LABEL: @test_06(339; CHECK-NEXT: entry:340; CHECK-NEXT: [[FIRST_ITR_CHECK:%.*]] = icmp sgt i32 [[N:%.*]], 0341; CHECK-NEXT: br i1 [[FIRST_ITR_CHECK]], label [[LOOP_PREHEADER:%.*]], label [[EXIT:%.*]]342; CHECK: loop.preheader:343; CHECK-NEXT: br label [[LOOP:%.*]]344; CHECK: loop:345; CHECK-NEXT: [[IDX:%.*]] = phi i32 [ [[IDX_NEXT:%.*]], [[IN_BOUNDS:%.*]] ], [ 0, [[LOOP_PREHEADER]] ]346; CHECK-NEXT: [[IDX_NEXT]] = add i32 [[IDX]], 1347; CHECK-NEXT: [[ABC:%.*]] = icmp ult i32 [[IDX]], -9348; CHECK-NEXT: br i1 [[ABC]], label [[IN_BOUNDS]], label [[OUT_OF_BOUNDS:%.*]], !prof [[PROF0]]349; CHECK: in.bounds:350; CHECK-NEXT: [[ADDR:%.*]] = getelementptr i32, ptr [[ARR:%.*]], i32 [[IDX]]351; CHECK-NEXT: store i32 0, ptr [[ADDR]], align 4352; CHECK-NEXT: [[NEXT:%.*]] = icmp ult i32 [[IDX_NEXT]], [[N]]353; CHECK-NEXT: br i1 [[NEXT]], label [[LOOP]], label [[EXIT_LOOPEXIT:%.*]]354; CHECK: out.of.bounds:355; CHECK-NEXT: ret void356; CHECK: exit.loopexit:357; CHECK-NEXT: br label [[EXIT]]358; CHECK: exit:359; CHECK-NEXT: ret void360;361 entry:362 %first.itr.check = icmp sgt i32 %n, 0363 br i1 %first.itr.check, label %loop, label %exit364 365 loop:366 %idx = phi i32 [ 0, %entry ] , [ %idx.next, %in.bounds ]367 %idx.next = add i32 %idx, 1368 %abc = icmp ult i32 %idx, -9369 br i1 %abc, label %in.bounds, label %out.of.bounds, !prof !0370 371 in.bounds:372 %addr = getelementptr i32, ptr %arr, i32 %idx373 store i32 0, ptr %addr374 %next = icmp ult i32 %idx.next, %n375 br i1 %next, label %loop, label %exit376 377 out.of.bounds:378 ret void379 380 exit:381 ret void382}383 384; Same as test_03, unsigned range check.385; FIXME: Currently we remove the check, but we will not execute the main loop if386; %bound is negative (i.e. in [SINT_MAX + 1, UINT_MAX)). We should be able to387; safely remove this check (see comments in the method388; computeSafeIterationSpace).389define void @test_07(ptr %arr, i32 %n, i32 %bound) {390; CHECK-LABEL: @test_07(391; CHECK-NEXT: entry:392; CHECK-NEXT: [[FIRST_ITR_CHECK:%.*]] = icmp sgt i32 [[N:%.*]], 0393; CHECK-NEXT: br i1 [[FIRST_ITR_CHECK]], label [[LOOP_PREHEADER:%.*]], label [[EXIT:%.*]]394; CHECK: loop.preheader:395; CHECK-NEXT: [[TMP0:%.*]] = add i32 [[BOUND:%.*]], -2147483647396; CHECK-NEXT: [[SMAX:%.*]] = call i32 @llvm.smax.i32(i32 [[TMP0]], i32 0)397; CHECK-NEXT: [[TMP1:%.*]] = sub i32 [[BOUND]], [[SMAX]]398; CHECK-NEXT: [[SMIN:%.*]] = call i32 @llvm.smin.i32(i32 [[BOUND]], i32 0)399; CHECK-NEXT: [[SMAX1:%.*]] = call i32 @llvm.smax.i32(i32 [[SMIN]], i32 -1)400; CHECK-NEXT: [[TMP2:%.*]] = add nsw i32 [[SMAX1]], 1401; CHECK-NEXT: [[TMP3:%.*]] = mul i32 [[TMP1]], [[TMP2]]402; CHECK-NEXT: [[SMIN2:%.*]] = call i32 @llvm.smin.i32(i32 [[N]], i32 [[TMP3]])403; CHECK-NEXT: [[EXIT_MAINLOOP_AT:%.*]] = call i32 @llvm.smax.i32(i32 [[SMIN2]], i32 0)404; CHECK-NEXT: [[TMP4:%.*]] = icmp slt i32 0, [[EXIT_MAINLOOP_AT]]405; CHECK-NEXT: br i1 [[TMP4]], label [[LOOP_PREHEADER4:%.*]], label [[MAIN_PSEUDO_EXIT:%.*]]406; CHECK: loop.preheader4:407; CHECK-NEXT: br label [[LOOP:%.*]]408; CHECK: loop:409; CHECK-NEXT: [[IDX:%.*]] = phi i32 [ [[IDX_NEXT:%.*]], [[IN_BOUNDS:%.*]] ], [ 0, [[LOOP_PREHEADER4]] ]410; CHECK-NEXT: [[IDX_NEXT]] = add nsw i32 [[IDX]], 1411; CHECK-NEXT: [[ABC:%.*]] = icmp ult i32 [[IDX]], [[BOUND]]412; CHECK-NEXT: br i1 true, label [[IN_BOUNDS]], label [[OUT_OF_BOUNDS_LOOPEXIT5:%.*]], !prof [[PROF0]]413; CHECK: in.bounds:414; CHECK-NEXT: [[ADDR:%.*]] = getelementptr i32, ptr [[ARR:%.*]], i32 [[IDX]]415; CHECK-NEXT: store i32 0, ptr [[ADDR]], align 4416; CHECK-NEXT: [[NEXT:%.*]] = icmp slt i32 [[IDX_NEXT]], [[N]]417; CHECK-NEXT: [[TMP5:%.*]] = icmp slt i32 [[IDX_NEXT]], [[EXIT_MAINLOOP_AT]]418; CHECK-NEXT: br i1 [[TMP5]], label [[LOOP]], label [[MAIN_EXIT_SELECTOR:%.*]]419; CHECK: main.exit.selector:420; CHECK-NEXT: [[IDX_NEXT_LCSSA:%.*]] = phi i32 [ [[IDX_NEXT]], [[IN_BOUNDS]] ]421; CHECK-NEXT: [[TMP6:%.*]] = icmp slt i32 [[IDX_NEXT_LCSSA]], [[N]]422; CHECK-NEXT: br i1 [[TMP6]], label [[MAIN_PSEUDO_EXIT]], label [[EXIT_LOOPEXIT:%.*]]423; CHECK: main.pseudo.exit:424; CHECK-NEXT: [[IDX_COPY:%.*]] = phi i32 [ 0, [[LOOP_PREHEADER]] ], [ [[IDX_NEXT_LCSSA]], [[MAIN_EXIT_SELECTOR]] ]425; CHECK-NEXT: [[INDVAR_END:%.*]] = phi i32 [ 0, [[LOOP_PREHEADER]] ], [ [[IDX_NEXT_LCSSA]], [[MAIN_EXIT_SELECTOR]] ]426; CHECK-NEXT: br label [[POSTLOOP:%.*]]427; CHECK: out.of.bounds.loopexit:428; CHECK-NEXT: br label [[OUT_OF_BOUNDS:%.*]]429; CHECK: out.of.bounds.loopexit5:430; CHECK-NEXT: br label [[OUT_OF_BOUNDS]]431; CHECK: out.of.bounds:432; CHECK-NEXT: ret void433; CHECK: exit.loopexit.loopexit:434; CHECK-NEXT: br label [[EXIT_LOOPEXIT]]435; CHECK: exit.loopexit:436; CHECK-NEXT: br label [[EXIT]]437; CHECK: exit:438; CHECK-NEXT: ret void439; CHECK: postloop:440; CHECK-NEXT: br label [[LOOP_POSTLOOP:%.*]]441; CHECK: loop.postloop:442; CHECK-NEXT: [[IDX_POSTLOOP:%.*]] = phi i32 [ [[IDX_NEXT_POSTLOOP:%.*]], [[IN_BOUNDS_POSTLOOP:%.*]] ], [ [[IDX_COPY]], [[POSTLOOP]] ]443; CHECK-NEXT: [[IDX_NEXT_POSTLOOP]] = add i32 [[IDX_POSTLOOP]], 1444; CHECK-NEXT: [[ABC_POSTLOOP:%.*]] = icmp ult i32 [[IDX_POSTLOOP]], [[BOUND]]445; CHECK-NEXT: br i1 [[ABC_POSTLOOP]], label [[IN_BOUNDS_POSTLOOP]], label [[OUT_OF_BOUNDS_LOOPEXIT:%.*]], !prof [[PROF0]]446; CHECK: in.bounds.postloop:447; CHECK-NEXT: [[ADDR_POSTLOOP:%.*]] = getelementptr i32, ptr [[ARR]], i32 [[IDX_POSTLOOP]]448; CHECK-NEXT: store i32 0, ptr [[ADDR_POSTLOOP]], align 4449; CHECK-NEXT: [[NEXT_POSTLOOP:%.*]] = icmp slt i32 [[IDX_NEXT_POSTLOOP]], [[N]]450; CHECK-NEXT: br i1 [[NEXT_POSTLOOP]], label [[LOOP_POSTLOOP]], label [[EXIT_LOOPEXIT_LOOPEXIT:%.*]], !llvm.loop [[LOOP8:![0-9]+]], !loop_constrainer.loop.clone [[META6]]451;452 entry:453 %first.itr.check = icmp sgt i32 %n, 0454 br i1 %first.itr.check, label %loop, label %exit455 456 loop:457 %idx = phi i32 [ 0, %entry ] , [ %idx.next, %in.bounds ]458 %idx.next = add i32 %idx, 1459 %abc = icmp ult i32 %idx, %bound460 br i1 %abc, label %in.bounds, label %out.of.bounds, !prof !0461 462 in.bounds:463 %addr = getelementptr i32, ptr %arr, i32 %idx464 store i32 0, ptr %addr465 %next = icmp slt i32 %idx.next, %n466 br i1 %next, label %loop, label %exit467 468 out.of.bounds:469 ret void470 471 exit:472 ret void473}474 475; Same as test_04, unsigned range check.476; FIXME: Currently we remove the check, but we will not execute the main loop if477; %bound is negative (i.e. in [SINT_MAX + 1, UINT_MAX)). We should be able to478; safely remove this check (see comments in the method479; computeSafeIterationSpace).480define void @test_08(ptr %arr, i32 %n, i32 %bound) {481; CHECK-LABEL: @test_08(482; CHECK-NEXT: entry:483; CHECK-NEXT: [[FIRST_ITR_CHECK:%.*]] = icmp sgt i32 [[N:%.*]], 0484; CHECK-NEXT: br i1 [[FIRST_ITR_CHECK]], label [[LOOP_PREHEADER:%.*]], label [[EXIT:%.*]]485; CHECK: loop.preheader:486; CHECK-NEXT: [[SMIN:%.*]] = call i32 @llvm.smin.i32(i32 [[BOUND:%.*]], i32 0)487; CHECK-NEXT: [[TMP0:%.*]] = sub i32 [[BOUND]], [[SMIN]]488; CHECK-NEXT: [[SMAX:%.*]] = call i32 @llvm.smax.i32(i32 [[SMIN]], i32 -1)489; CHECK-NEXT: [[TMP1:%.*]] = add nsw i32 [[SMAX]], 1490; CHECK-NEXT: [[TMP2:%.*]] = mul i32 [[TMP0]], [[TMP1]]491; CHECK-NEXT: [[EXIT_MAINLOOP_AT:%.*]] = call i32 @llvm.umin.i32(i32 [[N]], i32 [[TMP2]])492; CHECK-NEXT: [[TMP3:%.*]] = icmp ult i32 0, [[EXIT_MAINLOOP_AT]]493; CHECK-NEXT: br i1 [[TMP3]], label [[LOOP_PREHEADER1:%.*]], label [[MAIN_PSEUDO_EXIT:%.*]]494; CHECK: loop.preheader1:495; CHECK-NEXT: br label [[LOOP:%.*]]496; CHECK: loop:497; CHECK-NEXT: [[IDX:%.*]] = phi i32 [ [[IDX_NEXT:%.*]], [[IN_BOUNDS:%.*]] ], [ 0, [[LOOP_PREHEADER1]] ]498; CHECK-NEXT: [[IDX_NEXT]] = add i32 [[IDX]], 1499; CHECK-NEXT: [[ABC:%.*]] = icmp ult i32 [[IDX]], [[BOUND]]500; CHECK-NEXT: br i1 true, label [[IN_BOUNDS]], label [[OUT_OF_BOUNDS_LOOPEXIT2:%.*]], !prof [[PROF0]]501; CHECK: in.bounds:502; CHECK-NEXT: [[ADDR:%.*]] = getelementptr i32, ptr [[ARR:%.*]], i32 [[IDX]]503; CHECK-NEXT: store i32 0, ptr [[ADDR]], align 4504; CHECK-NEXT: [[NEXT:%.*]] = icmp ult i32 [[IDX_NEXT]], [[N]]505; CHECK-NEXT: [[TMP4:%.*]] = icmp ult i32 [[IDX_NEXT]], [[EXIT_MAINLOOP_AT]]506; CHECK-NEXT: br i1 [[TMP4]], label [[LOOP]], label [[MAIN_EXIT_SELECTOR:%.*]]507; CHECK: main.exit.selector:508; CHECK-NEXT: [[IDX_NEXT_LCSSA:%.*]] = phi i32 [ [[IDX_NEXT]], [[IN_BOUNDS]] ]509; CHECK-NEXT: [[TMP5:%.*]] = icmp ult i32 [[IDX_NEXT_LCSSA]], [[N]]510; CHECK-NEXT: br i1 [[TMP5]], label [[MAIN_PSEUDO_EXIT]], label [[EXIT_LOOPEXIT:%.*]]511; CHECK: main.pseudo.exit:512; CHECK-NEXT: [[IDX_COPY:%.*]] = phi i32 [ 0, [[LOOP_PREHEADER]] ], [ [[IDX_NEXT_LCSSA]], [[MAIN_EXIT_SELECTOR]] ]513; CHECK-NEXT: [[INDVAR_END:%.*]] = phi i32 [ 0, [[LOOP_PREHEADER]] ], [ [[IDX_NEXT_LCSSA]], [[MAIN_EXIT_SELECTOR]] ]514; CHECK-NEXT: br label [[POSTLOOP:%.*]]515; CHECK: out.of.bounds.loopexit:516; CHECK-NEXT: br label [[OUT_OF_BOUNDS:%.*]]517; CHECK: out.of.bounds.loopexit2:518; CHECK-NEXT: br label [[OUT_OF_BOUNDS]]519; CHECK: out.of.bounds:520; CHECK-NEXT: ret void521; CHECK: exit.loopexit.loopexit:522; CHECK-NEXT: br label [[EXIT_LOOPEXIT]]523; CHECK: exit.loopexit:524; CHECK-NEXT: br label [[EXIT]]525; CHECK: exit:526; CHECK-NEXT: ret void527; CHECK: postloop:528; CHECK-NEXT: br label [[LOOP_POSTLOOP:%.*]]529; CHECK: loop.postloop:530; CHECK-NEXT: [[IDX_POSTLOOP:%.*]] = phi i32 [ [[IDX_NEXT_POSTLOOP:%.*]], [[IN_BOUNDS_POSTLOOP:%.*]] ], [ [[IDX_COPY]], [[POSTLOOP]] ]531; CHECK-NEXT: [[IDX_NEXT_POSTLOOP]] = add i32 [[IDX_POSTLOOP]], 1532; CHECK-NEXT: [[ABC_POSTLOOP:%.*]] = icmp ult i32 [[IDX_POSTLOOP]], [[BOUND]]533; CHECK-NEXT: br i1 [[ABC_POSTLOOP]], label [[IN_BOUNDS_POSTLOOP]], label [[OUT_OF_BOUNDS_LOOPEXIT:%.*]], !prof [[PROF0]]534; CHECK: in.bounds.postloop:535; CHECK-NEXT: [[ADDR_POSTLOOP:%.*]] = getelementptr i32, ptr [[ARR]], i32 [[IDX_POSTLOOP]]536; CHECK-NEXT: store i32 0, ptr [[ADDR_POSTLOOP]], align 4537; CHECK-NEXT: [[NEXT_POSTLOOP:%.*]] = icmp ult i32 [[IDX_NEXT_POSTLOOP]], [[N]]538; CHECK-NEXT: br i1 [[NEXT_POSTLOOP]], label [[LOOP_POSTLOOP]], label [[EXIT_LOOPEXIT_LOOPEXIT:%.*]], !llvm.loop [[LOOP9:![0-9]+]], !loop_constrainer.loop.clone [[META6]]539;540 entry:541 %first.itr.check = icmp sgt i32 %n, 0542 br i1 %first.itr.check, label %loop, label %exit543 544 loop:545 %idx = phi i32 [ 0, %entry ] , [ %idx.next, %in.bounds ]546 %idx.next = add i32 %idx, 1547 %abc = icmp ult i32 %idx, %bound548 br i1 %abc, label %in.bounds, label %out.of.bounds, !prof !0549 550 in.bounds:551 %addr = getelementptr i32, ptr %arr, i32 %idx552 store i32 0, ptr %addr553 %next = icmp ult i32 %idx.next, %n554 br i1 %next, label %loop, label %exit555 556 out.of.bounds:557 ret void558 559 exit:560 ret void561}562!0 = !{!"branch_weights", i32 64, i32 4}563