1; NOTE: Assertions have been autogenerated by utils/update_test_checks.py 2; RUN: opt -verify-loop-info -irce-print-changed-loops -passes=irce -S < %s 2>&1 | FileCheck %s 3; RUN: opt -verify-loop-info -irce-print-changed-loops -passes='require<branch-prob>,irce' -S < %s 2>&1 | FileCheck %s 4 5; CHECK-NOT: irce: in function test_01: constrained Loop 6; CHECK-NOT: irce: in function test_02: constrained Loop 7; CHECK: irce: in function test_03: constrained Loop 8 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:%.*]], 0 14; 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]], 1 20; CHECK-NEXT: [[ABC:%.*]] = icmp slt i32 [[IDX]], -9 21; 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 4 25; 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 void 29; CHECK: exit.loopexit: 30; CHECK-NEXT: br label [[EXIT]] 31; CHECK: exit: 32; CHECK-NEXT: ret void 33; 34 35 entry: 36 %first.itr.check = icmp sgt i32 %n, 0 37 br i1 %first.itr.check, label %loop, label %exit 38 39 loop: 40 %idx = phi i32 [ 0, %entry ] , [ %idx.next, %in.bounds ] 41 %idx.next = add i32 %idx, 1 42 %abc = icmp slt i32 %idx, -9 43 br i1 %abc, label %in.bounds, label %out.of.bounds, !prof !0 44 45 in.bounds: 46 %addr = getelementptr i32, ptr %arr, i32 %idx 47 store i32 0, ptr %addr 48 %next = icmp slt i32 %idx.next, %n 49 br i1 %next, label %loop, label %exit 50 51 out.of.bounds: 52 ret void 53 54 exit: 55 ret void 56} 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:%.*]], 0 63; 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]], 1 69; CHECK-NEXT: [[ABC:%.*]] = icmp slt i32 [[IDX]], -9 70; 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 4 74; 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 void 78; CHECK: exit.loopexit: 79; CHECK-NEXT: br label [[EXIT]] 80; CHECK: exit: 81; CHECK-NEXT: ret void 82; 83 84 entry: 85 %first.itr.check = icmp sgt i32 %n, 0 86 br i1 %first.itr.check, label %loop, label %exit 87 88 loop: 89 %idx = phi i32 [ 0, %entry ] , [ %idx.next, %in.bounds ] 90 %idx.next = add i32 %idx, 1 91 %abc = icmp slt i32 %idx, -9 92 br i1 %abc, label %in.bounds, label %out.of.bounds, !prof !0 93 94 in.bounds: 95 %addr = getelementptr i32, ptr %arr, i32 %idx 96 store i32 0, ptr %addr 97 %next = icmp ult i32 %idx.next, %n 98 br i1 %next, label %loop, label %exit 99 100 out.of.bounds: 101 ret void 102 103 exit: 104 ret void 105} 106 107; RC against a value which is not known to be non-negative. Here we should 108; 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:%.*]], 0 113; CHECK-NEXT: br i1 [[FIRST_ITR_CHECK]], label [[LOOP_PREHEADER:%.*]], label [[EXIT:%.*]] 114; CHECK: loop.preheader: 115; CHECK-NEXT: [[TMP0:%.*]] = add i32 [[BOUND:%.*]], -2147483647 116; 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]], 1 121; 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]], 1 131; 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 4 136; 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 void 153; 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 void 159; 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]], 1 164; 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 4 169; 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, 0 175 br i1 %first.itr.check, label %loop, label %exit 176 177 loop: 178 %idx = phi i32 [ 0, %entry ] , [ %idx.next, %in.bounds ] 179 %idx.next = add i32 %idx, 1 180 %abc = icmp slt i32 %idx, %bound 181 br i1 %abc, label %in.bounds, label %out.of.bounds, !prof !0 182 183 in.bounds: 184 %addr = getelementptr i32, ptr %arr, i32 %idx 185 store i32 0, ptr %addr 186 %next = icmp slt i32 %idx.next, %n 187 br i1 %next, label %loop, label %exit 188 189 out.of.bounds: 190 ret void 191 192 exit: 193 ret void 194} 195 196; RC against a value which is not known to be non-negative. Here we should 197; 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:%.*]], 0 202; 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]], 1 208; 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]], 1 217; 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 4 222; 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 void 239; 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 void 245; 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]], 1 250; 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 4 255; 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, 0 261 br i1 %first.itr.check, label %loop, label %exit 262 263 loop: 264 %idx = phi i32 [ 0, %entry ] , [ %idx.next, %in.bounds ] 265 %idx.next = add i32 %idx, 1 266 %abc = icmp slt i32 %idx, %bound 267 br i1 %abc, label %in.bounds, label %out.of.bounds, !prof !0 268 269 in.bounds: 270 %addr = getelementptr i32, ptr %arr, i32 %idx 271 store i32 0, ptr %addr 272 %next = icmp ult i32 %idx.next, %n 273 br i1 %next, label %loop, label %exit 274 275 out.of.bounds: 276 ret void 277 278 exit: 279 ret void 280} 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 the 284; limintation we posed to fix the miscompile (see comments in the method 285; 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:%.*]], 0 290; 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]], 1 296; CHECK-NEXT: [[ABC:%.*]] = icmp ult i32 [[IDX]], -9 297; 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 4 301; 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 void 305; CHECK: exit.loopexit: 306; CHECK-NEXT: br label [[EXIT]] 307; CHECK: exit: 308; CHECK-NEXT: ret void 309; 310 entry: 311 %first.itr.check = icmp sgt i32 %n, 0 312 br i1 %first.itr.check, label %loop, label %exit 313 314 loop: 315 %idx = phi i32 [ 0, %entry ] , [ %idx.next, %in.bounds ] 316 %idx.next = add i32 %idx, 1 317 %abc = icmp ult i32 %idx, -9 318 br i1 %abc, label %in.bounds, label %out.of.bounds, !prof !0 319 320 in.bounds: 321 %addr = getelementptr i32, ptr %arr, i32 %idx 322 store i32 0, ptr %addr 323 %next = icmp slt i32 %idx.next, %n 324 br i1 %next, label %loop, label %exit 325 326 out.of.bounds: 327 ret void 328 329 exit: 330 ret void 331} 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 the 335; limintation we posed to fix the miscompile (see comments in the method 336; 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:%.*]], 0 341; 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]], 1 347; CHECK-NEXT: [[ABC:%.*]] = icmp ult i32 [[IDX]], -9 348; 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 4 352; 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 void 356; CHECK: exit.loopexit: 357; CHECK-NEXT: br label [[EXIT]] 358; CHECK: exit: 359; CHECK-NEXT: ret void 360; 361 entry: 362 %first.itr.check = icmp sgt i32 %n, 0 363 br i1 %first.itr.check, label %loop, label %exit 364 365 loop: 366 %idx = phi i32 [ 0, %entry ] , [ %idx.next, %in.bounds ] 367 %idx.next = add i32 %idx, 1 368 %abc = icmp ult i32 %idx, -9 369 br i1 %abc, label %in.bounds, label %out.of.bounds, !prof !0 370 371 in.bounds: 372 %addr = getelementptr i32, ptr %arr, i32 %idx 373 store i32 0, ptr %addr 374 %next = icmp ult i32 %idx.next, %n 375 br i1 %next, label %loop, label %exit 376 377 out.of.bounds: 378 ret void 379 380 exit: 381 ret void 382} 383 384; Same as test_03, unsigned range check. 385; FIXME: Currently we remove the check, but we will not execute the main loop if 386; %bound is negative (i.e. in [SINT_MAX + 1, UINT_MAX)). We should be able to 387; safely remove this check (see comments in the method 388; 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:%.*]], 0 393; CHECK-NEXT: br i1 [[FIRST_ITR_CHECK]], label [[LOOP_PREHEADER:%.*]], label [[EXIT:%.*]] 394; CHECK: loop.preheader: 395; CHECK-NEXT: [[TMP0:%.*]] = add i32 [[BOUND:%.*]], -2147483647 396; 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]], 1 401; 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]], 1 411; 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 4 416; 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 void 433; 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 void 439; 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]], 1 444; 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 4 449; 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, 0 454 br i1 %first.itr.check, label %loop, label %exit 455 456 loop: 457 %idx = phi i32 [ 0, %entry ] , [ %idx.next, %in.bounds ] 458 %idx.next = add i32 %idx, 1 459 %abc = icmp ult i32 %idx, %bound 460 br i1 %abc, label %in.bounds, label %out.of.bounds, !prof !0 461 462 in.bounds: 463 %addr = getelementptr i32, ptr %arr, i32 %idx 464 store i32 0, ptr %addr 465 %next = icmp slt i32 %idx.next, %n 466 br i1 %next, label %loop, label %exit 467 468 out.of.bounds: 469 ret void 470 471 exit: 472 ret void 473} 474 475; Same as test_04, unsigned range check. 476; FIXME: Currently we remove the check, but we will not execute the main loop if 477; %bound is negative (i.e. in [SINT_MAX + 1, UINT_MAX)). We should be able to 478; safely remove this check (see comments in the method 479; 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:%.*]], 0 484; 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]], 1 490; 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]], 1 499; 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 4 504; 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 void 521; 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 void 527; 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]], 1 532; 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 4 537; 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, 0 542 br i1 %first.itr.check, label %loop, label %exit 543 544 loop: 545 %idx = phi i32 [ 0, %entry ] , [ %idx.next, %in.bounds ] 546 %idx.next = add i32 %idx, 1 547 %abc = icmp ult i32 %idx, %bound 548 br i1 %abc, label %in.bounds, label %out.of.bounds, !prof !0 549 550 in.bounds: 551 %addr = getelementptr i32, ptr %arr, i32 %idx 552 store i32 0, ptr %addr 553 %next = icmp ult i32 %idx.next, %n 554 br i1 %next, label %loop, label %exit 555 556 out.of.bounds: 557 ret void 558 559 exit: 560 ret void 561} 562!0 = !{!"branch_weights", i32 64, i32 4} 563