1; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --version 3 2; RUN: opt -passes=irce < %s -S | FileCheck %s 3 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]], 0 14; CHECK-NEXT: [[CHECK1:%.*]] = icmp sgt i32 [[M]], 0 15; 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]], 1 29; 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 4 34; 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 void 51; 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 void 57; 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]], 1 62; 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 4 67; 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 !6 69; 70entry: 71 %len = load i32, ptr %len_ptr, !range !0 72 %check0 = icmp sgt i32 %K, 0 73 %check1 = icmp sgt i32 %M, 0 74 %and = and i1 %check0, %check1 75 br i1 %and, label %preheader, label %exit 76 77preheader: 78 %smin = call i32 @llvm.smin.i32(i32 %K, i32 %M) 79 br label %loop 80 81loop: 82 %idx = phi i32 [ 0, %preheader ], [ %idx.next, %in.bounds ] 83 %idx.next = add i32 %idx, 1 84 %guard = icmp slt i32 %idx, %len 85 br i1 %guard, label %in.bounds, label %out.of.bounds 86 87in.bounds: 88 %addr = getelementptr i32, ptr %arr, i32 %idx 89 store i32 0, ptr %addr 90 %next = icmp slt i32 %idx.next, %smin 91 br i1 %next, label %loop, label %exit 92 93out.of.bounds: 94 ret void 95 96exit: 97 ret void 98} 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]], 0 110; CHECK-NEXT: [[CHECK1:%.*]] = icmp sgt i32 [[M]], 0 111; 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]], 1 116; 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]], -1 119; 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]], 1 128; 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 4 133; CHECK-NEXT: [[NEXT:%.*]] = icmp sgt i32 [[IDX_DEC]], -1 134; 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 void 141; 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 void 147; 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]], 1 150; 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 4 155; CHECK-NEXT: [[NEXT_PRELOOP:%.*]] = icmp sgt i32 [[IDX_DEC_PRELOOP]], -1 156; 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 !6 158; 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]], -1 161; 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 !0 169 %check0 = icmp sgt i32 %K, 0 170 %check1 = icmp sgt i32 %M, 0 171 %and = and i1 %check0, %check1 172 br i1 %and, label %preheader, label %exit 173 174 preheader: 175 %smin = call i32 @llvm.smin.i32(i32 %K, i32 %M) 176 br label %loop 177 178 loop: 179 %idx = phi i32 [ %smin, %preheader ] , [ %idx.dec, %in.bounds ] 180 %idx.dec = sub i32 %idx, 1 181 %guard = icmp slt i32 %idx, %len 182 br i1 %guard, label %in.bounds, label %out.of.bounds 183 184 in.bounds: 185 %addr = getelementptr i32, ptr %arr, i32 %idx 186 store i32 0, ptr %addr 187 %next = icmp sgt i32 %idx.dec, -1 188 br i1 %next, label %loop, label %exit 189 190 out.of.bounds: 191 ret void 192 193 exit: 194 ret void 195} 196 197declare i32 @llvm.smin.i32(i32, i32) 198 199!0 = !{i32 0, i32 2147483647} 200