200 lines · plain
1; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --version 32; RUN: opt -passes=irce < %s -S | FileCheck %s3 4; if (K > 0 && M > 0)5; for (i = 0; i < min(K, M); i++) {...}6;7; TODO: Loop bounds are safe according to loop guards. IRCE is allowed.8define void @incrementing_loop(ptr %arr, ptr %len_ptr, i32 %K, i32 %M) {9; CHECK-LABEL: define void @incrementing_loop(10; CHECK-SAME: ptr [[ARR:%.*]], ptr [[LEN_PTR:%.*]], i32 [[K:%.*]], i32 [[M:%.*]]) {11; CHECK-NEXT: entry:12; CHECK-NEXT: [[LEN:%.*]] = load i32, ptr [[LEN_PTR]], align 4, !range [[RNG0:![0-9]+]]13; CHECK-NEXT: [[CHECK0:%.*]] = icmp sgt i32 [[K]], 014; CHECK-NEXT: [[CHECK1:%.*]] = icmp sgt i32 [[M]], 015; CHECK-NEXT: [[AND:%.*]] = and i1 [[CHECK0]], [[CHECK1]]16; CHECK-NEXT: br i1 [[AND]], label [[PREHEADER:%.*]], label [[EXIT:%.*]]17; CHECK: preheader:18; CHECK-NEXT: [[SMIN:%.*]] = call i32 @llvm.smin.i32(i32 [[K]], i32 [[M]])19; CHECK-NEXT: [[SMIN1:%.*]] = call i32 @llvm.smin.i32(i32 [[LEN]], i32 [[M]])20; CHECK-NEXT: [[SMIN2:%.*]] = call i32 @llvm.smin.i32(i32 [[SMIN1]], i32 [[K]])21; CHECK-NEXT: [[EXIT_MAINLOOP_AT:%.*]] = call i32 @llvm.smax.i32(i32 [[SMIN2]], i32 0)22; CHECK-NEXT: [[TMP0:%.*]] = icmp slt i32 0, [[EXIT_MAINLOOP_AT]]23; CHECK-NEXT: br i1 [[TMP0]], label [[LOOP_PREHEADER:%.*]], label [[MAIN_PSEUDO_EXIT:%.*]]24; CHECK: loop.preheader:25; CHECK-NEXT: br label [[LOOP:%.*]]26; CHECK: loop:27; CHECK-NEXT: [[IDX:%.*]] = phi i32 [ [[IDX_NEXT:%.*]], [[IN_BOUNDS:%.*]] ], [ 0, [[LOOP_PREHEADER]] ]28; CHECK-NEXT: [[IDX_NEXT]] = add nsw i32 [[IDX]], 129; CHECK-NEXT: [[GUARD:%.*]] = icmp slt i32 [[IDX]], [[LEN]]30; CHECK-NEXT: br i1 true, label [[IN_BOUNDS]], label [[OUT_OF_BOUNDS_LOOPEXIT3:%.*]]31; CHECK: in.bounds:32; CHECK-NEXT: [[ADDR:%.*]] = getelementptr i32, ptr [[ARR]], i32 [[IDX]]33; CHECK-NEXT: store i32 0, ptr [[ADDR]], align 434; CHECK-NEXT: [[NEXT:%.*]] = icmp slt i32 [[IDX_NEXT]], [[SMIN]]35; CHECK-NEXT: [[TMP1:%.*]] = icmp slt i32 [[IDX_NEXT]], [[EXIT_MAINLOOP_AT]]36; CHECK-NEXT: br i1 [[TMP1]], label [[LOOP]], label [[MAIN_EXIT_SELECTOR:%.*]]37; CHECK: main.exit.selector:38; CHECK-NEXT: [[IDX_NEXT_LCSSA:%.*]] = phi i32 [ [[IDX_NEXT]], [[IN_BOUNDS]] ]39; CHECK-NEXT: [[TMP2:%.*]] = icmp slt i32 [[IDX_NEXT_LCSSA]], [[SMIN]]40; CHECK-NEXT: br i1 [[TMP2]], label [[MAIN_PSEUDO_EXIT]], label [[EXIT_LOOPEXIT:%.*]]41; CHECK: main.pseudo.exit:42; CHECK-NEXT: [[IDX_COPY:%.*]] = phi i32 [ 0, [[PREHEADER]] ], [ [[IDX_NEXT_LCSSA]], [[MAIN_EXIT_SELECTOR]] ]43; CHECK-NEXT: [[INDVAR_END:%.*]] = phi i32 [ 0, [[PREHEADER]] ], [ [[IDX_NEXT_LCSSA]], [[MAIN_EXIT_SELECTOR]] ]44; CHECK-NEXT: br label [[POSTLOOP:%.*]]45; CHECK: out.of.bounds.loopexit:46; CHECK-NEXT: br label [[OUT_OF_BOUNDS:%.*]]47; CHECK: out.of.bounds.loopexit3:48; CHECK-NEXT: br label [[OUT_OF_BOUNDS]]49; CHECK: out.of.bounds:50; CHECK-NEXT: ret void51; CHECK: exit.loopexit.loopexit:52; CHECK-NEXT: br label [[EXIT_LOOPEXIT]]53; CHECK: exit.loopexit:54; CHECK-NEXT: br label [[EXIT]]55; CHECK: exit:56; CHECK-NEXT: ret void57; CHECK: postloop:58; CHECK-NEXT: br label [[LOOP_POSTLOOP:%.*]]59; CHECK: loop.postloop:60; CHECK-NEXT: [[IDX_POSTLOOP:%.*]] = phi i32 [ [[IDX_COPY]], [[POSTLOOP]] ], [ [[IDX_NEXT_POSTLOOP:%.*]], [[IN_BOUNDS_POSTLOOP:%.*]] ]61; CHECK-NEXT: [[IDX_NEXT_POSTLOOP]] = add i32 [[IDX_POSTLOOP]], 162; CHECK-NEXT: [[GUARD_POSTLOOP:%.*]] = icmp slt i32 [[IDX_POSTLOOP]], [[LEN]]63; CHECK-NEXT: br i1 [[GUARD_POSTLOOP]], label [[IN_BOUNDS_POSTLOOP]], label [[OUT_OF_BOUNDS_LOOPEXIT:%.*]]64; CHECK: in.bounds.postloop:65; CHECK-NEXT: [[ADDR_POSTLOOP:%.*]] = getelementptr i32, ptr [[ARR]], i32 [[IDX_POSTLOOP]]66; CHECK-NEXT: store i32 0, ptr [[ADDR_POSTLOOP]], align 467; CHECK-NEXT: [[NEXT_POSTLOOP:%.*]] = icmp slt i32 [[IDX_NEXT_POSTLOOP]], [[SMIN]]68; CHECK-NEXT: br i1 [[NEXT_POSTLOOP]], label [[LOOP_POSTLOOP]], label [[EXIT_LOOPEXIT_LOOPEXIT:%.*]], !llvm.loop [[LOOP1:![0-9]+]], !loop_constrainer.loop.clone !669;70entry:71 %len = load i32, ptr %len_ptr, !range !072 %check0 = icmp sgt i32 %K, 073 %check1 = icmp sgt i32 %M, 074 %and = and i1 %check0, %check175 br i1 %and, label %preheader, label %exit76 77preheader:78 %smin = call i32 @llvm.smin.i32(i32 %K, i32 %M)79 br label %loop80 81loop:82 %idx = phi i32 [ 0, %preheader ], [ %idx.next, %in.bounds ]83 %idx.next = add i32 %idx, 184 %guard = icmp slt i32 %idx, %len85 br i1 %guard, label %in.bounds, label %out.of.bounds86 87in.bounds:88 %addr = getelementptr i32, ptr %arr, i32 %idx89 store i32 0, ptr %addr90 %next = icmp slt i32 %idx.next, %smin91 br i1 %next, label %loop, label %exit92 93out.of.bounds:94 ret void95 96exit:97 ret void98}99 100; if (K > 0 && M > 0)101; for (i = min(K, M); i >= 0; i--) {...}102;103; TODO: Loop bounds are safe according to loop guards. IRCE is allowed.104define void @decrementing_loop(ptr %arr, ptr %len_ptr, i32 %K, i32 %M) {105; CHECK-LABEL: define void @decrementing_loop(106; CHECK-SAME: ptr [[ARR:%.*]], ptr [[LEN_PTR:%.*]], i32 [[K:%.*]], i32 [[M:%.*]]) {107; CHECK-NEXT: entry:108; CHECK-NEXT: [[LEN:%.*]] = load i32, ptr [[LEN_PTR]], align 4, !range [[RNG0]]109; CHECK-NEXT: [[CHECK0:%.*]] = icmp sgt i32 [[K]], 0110; CHECK-NEXT: [[CHECK1:%.*]] = icmp sgt i32 [[M]], 0111; CHECK-NEXT: [[AND:%.*]] = and i1 [[CHECK0]], [[CHECK1]]112; CHECK-NEXT: br i1 [[AND]], label [[PREHEADER:%.*]], label [[EXIT:%.*]]113; CHECK: preheader:114; CHECK-NEXT: [[INDVAR_START:%.*]] = call i32 @llvm.smin.i32(i32 [[K]], i32 [[M]])115; CHECK-NEXT: [[TMP0:%.*]] = add i32 [[INDVAR_START]], 1116; CHECK-NEXT: [[SMIN:%.*]] = call i32 @llvm.smin.i32(i32 [[LEN]], i32 [[TMP0]])117; CHECK-NEXT: [[SMAX:%.*]] = call i32 @llvm.smax.i32(i32 [[SMIN]], i32 0)118; CHECK-NEXT: [[EXIT_PRELOOP_AT:%.*]] = add nsw i32 [[SMAX]], -1119; CHECK-NEXT: [[TMP1:%.*]] = icmp sgt i32 [[INDVAR_START]], [[EXIT_PRELOOP_AT]]120; CHECK-NEXT: br i1 [[TMP1]], label [[LOOP_PRELOOP_PREHEADER:%.*]], label [[PRELOOP_PSEUDO_EXIT:%.*]]121; CHECK: loop.preloop.preheader:122; CHECK-NEXT: br label [[LOOP_PRELOOP:%.*]]123; CHECK: mainloop:124; CHECK-NEXT: br label [[LOOP:%.*]]125; CHECK: loop:126; CHECK-NEXT: [[IDX:%.*]] = phi i32 [ [[IDX_PRELOOP_COPY:%.*]], [[MAINLOOP:%.*]] ], [ [[IDX_DEC:%.*]], [[IN_BOUNDS:%.*]] ]127; CHECK-NEXT: [[IDX_DEC]] = sub nsw i32 [[IDX]], 1128; CHECK-NEXT: [[GUARD:%.*]] = icmp slt i32 [[IDX]], [[LEN]]129; CHECK-NEXT: br i1 true, label [[IN_BOUNDS]], label [[OUT_OF_BOUNDS_LOOPEXIT1:%.*]]130; CHECK: in.bounds:131; CHECK-NEXT: [[ADDR:%.*]] = getelementptr i32, ptr [[ARR]], i32 [[IDX]]132; CHECK-NEXT: store i32 0, ptr [[ADDR]], align 4133; CHECK-NEXT: [[NEXT:%.*]] = icmp sgt i32 [[IDX_DEC]], -1134; CHECK-NEXT: br i1 [[NEXT]], label [[LOOP]], label [[EXIT_LOOPEXIT_LOOPEXIT:%.*]]135; CHECK: out.of.bounds.loopexit:136; CHECK-NEXT: br label [[OUT_OF_BOUNDS:%.*]]137; CHECK: out.of.bounds.loopexit1:138; CHECK-NEXT: br label [[OUT_OF_BOUNDS]]139; CHECK: out.of.bounds:140; CHECK-NEXT: ret void141; CHECK: exit.loopexit.loopexit:142; CHECK-NEXT: br label [[EXIT_LOOPEXIT:%.*]]143; CHECK: exit.loopexit:144; CHECK-NEXT: br label [[EXIT]]145; CHECK: exit:146; CHECK-NEXT: ret void147; CHECK: loop.preloop:148; CHECK-NEXT: [[IDX_PRELOOP:%.*]] = phi i32 [ [[IDX_DEC_PRELOOP:%.*]], [[IN_BOUNDS_PRELOOP:%.*]] ], [ [[INDVAR_START]], [[LOOP_PRELOOP_PREHEADER]] ]149; CHECK-NEXT: [[IDX_DEC_PRELOOP]] = sub i32 [[IDX_PRELOOP]], 1150; CHECK-NEXT: [[GUARD_PRELOOP:%.*]] = icmp slt i32 [[IDX_PRELOOP]], [[LEN]]151; CHECK-NEXT: br i1 [[GUARD_PRELOOP]], label [[IN_BOUNDS_PRELOOP]], label [[OUT_OF_BOUNDS_LOOPEXIT:%.*]]152; CHECK: in.bounds.preloop:153; CHECK-NEXT: [[ADDR_PRELOOP:%.*]] = getelementptr i32, ptr [[ARR]], i32 [[IDX_PRELOOP]]154; CHECK-NEXT: store i32 0, ptr [[ADDR_PRELOOP]], align 4155; CHECK-NEXT: [[NEXT_PRELOOP:%.*]] = icmp sgt i32 [[IDX_DEC_PRELOOP]], -1156; CHECK-NEXT: [[TMP2:%.*]] = icmp sgt i32 [[IDX_DEC_PRELOOP]], [[EXIT_PRELOOP_AT]]157; CHECK-NEXT: br i1 [[TMP2]], label [[LOOP_PRELOOP]], label [[PRELOOP_EXIT_SELECTOR:%.*]], !llvm.loop [[LOOP7:![0-9]+]], !loop_constrainer.loop.clone !6158; CHECK: preloop.exit.selector:159; CHECK-NEXT: [[IDX_DEC_PRELOOP_LCSSA:%.*]] = phi i32 [ [[IDX_DEC_PRELOOP]], [[IN_BOUNDS_PRELOOP]] ]160; CHECK-NEXT: [[TMP3:%.*]] = icmp sgt i32 [[IDX_DEC_PRELOOP_LCSSA]], -1161; CHECK-NEXT: br i1 [[TMP3]], label [[PRELOOP_PSEUDO_EXIT]], label [[EXIT_LOOPEXIT]]162; CHECK: preloop.pseudo.exit:163; CHECK-NEXT: [[IDX_PRELOOP_COPY]] = phi i32 [ [[INDVAR_START]], [[PREHEADER]] ], [ [[IDX_DEC_PRELOOP_LCSSA]], [[PRELOOP_EXIT_SELECTOR]] ]164; CHECK-NEXT: [[INDVAR_END:%.*]] = phi i32 [ [[INDVAR_START]], [[PREHEADER]] ], [ [[IDX_DEC_PRELOOP_LCSSA]], [[PRELOOP_EXIT_SELECTOR]] ]165; CHECK-NEXT: br label [[MAINLOOP]]166;167 entry:168 %len = load i32, ptr %len_ptr, !range !0169 %check0 = icmp sgt i32 %K, 0170 %check1 = icmp sgt i32 %M, 0171 %and = and i1 %check0, %check1172 br i1 %and, label %preheader, label %exit173 174 preheader:175 %smin = call i32 @llvm.smin.i32(i32 %K, i32 %M)176 br label %loop177 178 loop:179 %idx = phi i32 [ %smin, %preheader ] , [ %idx.dec, %in.bounds ]180 %idx.dec = sub i32 %idx, 1181 %guard = icmp slt i32 %idx, %len182 br i1 %guard, label %in.bounds, label %out.of.bounds183 184 in.bounds:185 %addr = getelementptr i32, ptr %arr, i32 %idx186 store i32 0, ptr %addr187 %next = icmp sgt i32 %idx.dec, -1188 br i1 %next, label %loop, label %exit189 190 out.of.bounds:191 ret void192 193 exit:194 ret void195}196 197declare i32 @llvm.smin.i32(i32, i32)198 199!0 = !{i32 0, i32 2147483647}200