1; RUN: opt -verify-loop-info -irce-print-changed-loops -irce -S < %s 2>&1 | FileCheck %s 2; RUN: opt -verify-loop-info -irce-print-changed-loops -passes='require<branch-prob>,irce' -S < %s 2>&1 | FileCheck %s 3 4; CHECK: irce: in function test_01: constrained Loop at depth 1 containing: %loop<header><exiting>,%in.bounds<latch><exiting> 5; CHECK: irce: in function test_02: constrained Loop at depth 1 containing: %loop<header><exiting>,%in.bounds<latch><exiting> 6; CHECK: irce: in function test_03: constrained Loop at depth 1 containing: %loop<header><exiting>,%in.bounds<latch><exiting> 7; CHECK: irce: in function test_04: constrained Loop at depth 1 containing: %loop<header><exiting>,%in.bounds<latch><exiting> 8; CHECK: irce: in function test_05: constrained Loop at depth 1 containing: %loop<header><exiting>,%in.bounds<latch><exiting> 9; CHECK: irce: in function test_06: constrained Loop at depth 1 containing: %loop<header><exiting>,%in.bounds<latch><exiting> 10; CHECK-NOT: irce: in function test_07: constrained Loop at depth 1 containing: %loop<header><exiting>,%in.bounds<latch><exiting> 11; CHECK: irce: in function test_08: constrained Loop at depth 1 containing: %loop<header><exiting>,%in.bounds<latch><exiting> 12; CHECK-NOT: irce: in function test_09: constrained Loop at depth 1 containing: %loop<header><exiting>,%in.bounds<latch><exiting> 13 14; ULT condition for increasing loop. 15define void @test_01(i32* %arr, i32* %a_len_ptr) #0 { 16 17; CHECK: test_01 18; CHECK: entry: 19; CHECK-NEXT: %exit.mainloop.at = load i32, i32* %a_len_ptr, align 4, !range !0 20; CHECK-NEXT: [[COND:%[^ ]+]] = icmp ult i32 0, %exit.mainloop.at 21; CHECK-NEXT: br i1 [[COND]], label %loop.preheader, label %main.pseudo.exit 22; CHECK: loop: 23; CHECK-NEXT: %idx = phi i32 [ %idx.next, %in.bounds ], [ 0, %loop.preheader ] 24; CHECK-NEXT: %idx.next = add nuw nsw i32 %idx, 1 25; CHECK-NEXT: %abc = icmp ult i32 %idx, %exit.mainloop.at 26; CHECK-NEXT: br i1 true, label %in.bounds, label %out.of.bounds.loopexit1 27; CHECK-NOT: loop.preloop: 28; CHECK: loop.postloop: 29; CHECK-NEXT: %idx.postloop = phi i32 [ %idx.copy, %postloop ], [ %idx.next.postloop, %in.bounds.postloop ] 30; CHECK-NEXT: %idx.next.postloop = add nuw nsw i32 %idx.postloop, 1 31; CHECK-NEXT: %abc.postloop = icmp ult i32 %idx.postloop, %exit.mainloop.at 32; CHECK-NEXT: br i1 %abc.postloop, label %in.bounds.postloop, label %out.of.bounds.loopexit 33 34entry: 35 %len = load i32, i32* %a_len_ptr, !range !0 36 br label %loop 37 38loop: 39 %idx = phi i32 [ 0, %entry ], [ %idx.next, %in.bounds ] 40 %idx.next = add nsw nuw i32 %idx, 1 41 %abc = icmp ult i32 %idx, %len 42 br i1 %abc, label %in.bounds, label %out.of.bounds 43 44in.bounds: 45 %addr = getelementptr i32, i32* %arr, i32 %idx 46 store i32 0, i32* %addr 47 %next = icmp ult i32 %idx.next, 100 48 br i1 %next, label %loop, label %exit 49 50out.of.bounds: 51 ret void 52 53exit: 54 ret void 55} 56 57; ULT condition for decreasing loops. 58define void @test_02(i32* %arr, i32* %a_len_ptr) #0 { 59 60; CHECK: test_02( 61; CHECK: entry: 62; CHECK-NEXT: %len = load i32, i32* %a_len_ptr, align 4, !range !0 63; CHECK-NEXT: [[COND1:%[^ ]+]] = icmp ugt i32 %len, 1 64; CHECK-NEXT: [[UMIN:%[^ ]+]] = select i1 [[COND1]], i32 %len, i32 1 65; CHECK-NEXT: %exit.preloop.at = add nsw i32 [[UMIN]], -1 66; CHECK-NEXT: [[COND2:%[^ ]+]] = icmp ugt i32 100, %exit.preloop.at 67; CHECK-NEXT: br i1 [[COND2]], label %loop.preloop.preheader, label %preloop.pseudo.exit 68; CHECK: mainloop: 69; CHECK-NEXT: br label %loop 70; CHECK: loop: 71; CHECK-NEXT: %idx = phi i32 [ %idx.preloop.copy, %mainloop ], [ %idx.next, %in.bounds ] 72; CHECK-NEXT: %idx.next = add i32 %idx, -1 73; CHECK-NEXT: %abc = icmp ult i32 %idx, %len 74; CHECK-NEXT: br i1 true, label %in.bounds, label %out.of.bounds.loopexit1 75; CHECK-NOT: loop.postloop: 76; CHECK: loop.preloop: 77; CHECK-NEXT: %idx.preloop = phi i32 [ %idx.next.preloop, %in.bounds.preloop ], [ 100, %loop.preloop.preheader ] 78; CHECK-NEXT: %idx.next.preloop = add i32 %idx.preloop, -1 79; CHECK-NEXT: %abc.preloop = icmp ult i32 %idx.preloop, %len 80; CHECK-NEXT: br i1 %abc.preloop, label %in.bounds.preloop, label %out.of.bounds.loopexit 81 82entry: 83 %len = load i32, i32* %a_len_ptr, !range !0 84 br label %loop 85 86loop: 87 %idx = phi i32 [ 100, %entry ], [ %idx.next, %in.bounds ] 88 %idx.next = add i32 %idx, -1 89 %abc = icmp ult i32 %idx, %len 90 br i1 %abc, label %in.bounds, label %out.of.bounds 91 92in.bounds: 93 %addr = getelementptr i32, i32* %arr, i32 %idx 94 store i32 0, i32* %addr 95 %next = icmp ult i32 %idx.next, 1 96 br i1 %next, label %exit, label %loop 97 98out.of.bounds: 99 ret void 100 101exit: 102 ret void 103} 104 105; Check SINT_MAX. 106define void @test_03(i32* %arr, i32* %a_len_ptr) #0 { 107 108; CHECK: test_03 109; CHECK: entry: 110; CHECK-NEXT: %exit.mainloop.at = load i32, i32* %a_len_ptr, align 4, !range !0 111; CHECK-NEXT: [[COND:%[^ ]+]] = icmp ult i32 0, %exit.mainloop.at 112; CHECK-NEXT: br i1 [[COND]], label %loop.preheader, label %main.pseudo.exit 113; CHECK: loop: 114; CHECK-NEXT: %idx = phi i32 [ %idx.next, %in.bounds ], [ 0, %loop.preheader ] 115; CHECK-NEXT: %idx.next = add nuw nsw i32 %idx, 1 116; CHECK-NEXT: %abc = icmp ult i32 %idx, %exit.mainloop.at 117; CHECK-NEXT: br i1 true, label %in.bounds, label %out.of.bounds.loopexit1 118; CHECK-NOT: loop.preloop: 119; CHECK: loop.postloop: 120; CHECK-NEXT: %idx.postloop = phi i32 [ %idx.copy, %postloop ], [ %idx.next.postloop, %in.bounds.postloop ] 121; CHECK-NEXT: %idx.next.postloop = add nuw nsw i32 %idx.postloop, 1 122; CHECK-NEXT: %abc.postloop = icmp ult i32 %idx.postloop, %exit.mainloop.at 123; CHECK-NEXT: br i1 %abc.postloop, label %in.bounds.postloop, label %out.of.bounds.loopexit 124 125entry: 126 %len = load i32, i32* %a_len_ptr, !range !0 127 br label %loop 128 129loop: 130 %idx = phi i32 [ 0, %entry ], [ %idx.next, %in.bounds ] 131 %idx.next = add nsw nuw i32 %idx, 1 132 %abc = icmp ult i32 %idx, %len 133 br i1 %abc, label %in.bounds, label %out.of.bounds 134 135in.bounds: 136 %addr = getelementptr i32, i32* %arr, i32 %idx 137 store i32 0, i32* %addr 138 %next = icmp ult i32 %idx.next, 2147483647 139 br i1 %next, label %loop, label %exit 140 141out.of.bounds: 142 ret void 143 144exit: 145 ret void 146} 147 148; Check SINT_MAX + 1, test is similar to test_01. 149define void @test_04(i32* %arr, i32* %a_len_ptr) #0 { 150 151; CHECK: test_04 152; CHECK: entry: 153; CHECK-NEXT: %exit.mainloop.at = load i32, i32* %a_len_ptr, align 4, !range !0 154; CHECK-NEXT: [[COND:%[^ ]+]] = icmp ult i32 0, %exit.mainloop.at 155; CHECK-NEXT: br i1 [[COND]], label %loop.preheader, label %main.pseudo.exit 156; CHECK: loop: 157; CHECK-NEXT: %idx = phi i32 [ %idx.next, %in.bounds ], [ 0, %loop.preheader ] 158; CHECK-NEXT: %idx.next = add nuw nsw i32 %idx, 1 159; CHECK-NEXT: %abc = icmp ult i32 %idx, %exit.mainloop.at 160; CHECK-NEXT: br i1 true, label %in.bounds, label %out.of.bounds.loopexit1 161; CHECK-NOT: loop.preloop: 162; CHECK: loop.postloop: 163; CHECK-NEXT: %idx.postloop = phi i32 [ %idx.copy, %postloop ], [ %idx.next.postloop, %in.bounds.postloop ] 164; CHECK-NEXT: %idx.next.postloop = add nuw nsw i32 %idx.postloop, 1 165; CHECK-NEXT: %abc.postloop = icmp ult i32 %idx.postloop, %exit.mainloop.at 166; CHECK-NEXT: br i1 %abc.postloop, label %in.bounds.postloop, label %out.of.bounds.loopexit 167 168entry: 169 %len = load i32, i32* %a_len_ptr, !range !0 170 br label %loop 171 172loop: 173 %idx = phi i32 [ 0, %entry ], [ %idx.next, %in.bounds ] 174 %idx.next = add nsw nuw i32 %idx, 1 175 %abc = icmp ult i32 %idx, %len 176 br i1 %abc, label %in.bounds, label %out.of.bounds 177 178in.bounds: 179 %addr = getelementptr i32, i32* %arr, i32 %idx 180 store i32 0, i32* %addr 181 %next = icmp ult i32 %idx.next, 2147483648 182 br i1 %next, label %loop, label %exit 183 184out.of.bounds: 185 ret void 186 187exit: 188 ret void 189} 190 191; Check SINT_MAX + 1, test is similar to test_02. 192define void @test_05(i32* %arr, i32* %a_len_ptr) #0 { 193; CHECK: test_05( 194; CHECK: entry: 195; CHECK-NEXT: %len = load i32, i32* %a_len_ptr, align 4, !range !0 196; CHECK-NEXT: [[COND1:%[^ ]+]] = icmp ugt i32 %len, 1 197; CHECK-NEXT: [[UMIN:%[^ ]+]] = select i1 [[COND1]], i32 %len, i32 1 198; CHECK-NEXT: %exit.preloop.at = add nsw i32 [[UMIN]], -1 199; CHECK-NEXT: [[COND2:%[^ ]+]] = icmp ugt i32 -2147483648, %exit.preloop.at 200; CHECK-NEXT: br i1 [[COND2]], label %loop.preloop.preheader, label %preloop.pseudo.exit 201; CHECK: mainloop: 202; CHECK-NEXT: br label %loop 203; CHECK: loop: 204; CHECK-NEXT: %idx = phi i32 [ %idx.preloop.copy, %mainloop ], [ %idx.next, %in.bounds ] 205; CHECK-NEXT: %idx.next = add i32 %idx, -1 206; CHECK-NEXT: %abc = icmp ult i32 %idx, %len 207; CHECK-NEXT: br i1 true, label %in.bounds, label %out.of.bounds.loopexit1 208; CHECK-NOT: loop.postloop: 209; CHECK: loop.preloop: 210; CHECK-NEXT: %idx.preloop = phi i32 [ %idx.next.preloop, %in.bounds.preloop ], [ -2147483648, %loop.preloop.preheader ] 211; CHECK-NEXT: %idx.next.preloop = add i32 %idx.preloop, -1 212; CHECK-NEXT: %abc.preloop = icmp ult i32 %idx.preloop, %len 213; CHECK-NEXT: br i1 %abc.preloop, label %in.bounds.preloop, label %out.of.bounds.loopexit 214 215entry: 216 %len = load i32, i32* %a_len_ptr, !range !0 217 br label %loop 218 219loop: 220 %idx = phi i32 [ 2147483648, %entry ], [ %idx.next, %in.bounds ] 221 %idx.next = add i32 %idx, -1 222 %abc = icmp ult i32 %idx, %len 223 br i1 %abc, label %in.bounds, label %out.of.bounds 224 225in.bounds: 226 %addr = getelementptr i32, i32* %arr, i32 %idx 227 store i32 0, i32* %addr 228 %next = icmp ult i32 %idx.next, 1 229 br i1 %next, label %exit, label %loop 230 231out.of.bounds: 232 ret void 233 234exit: 235 ret void 236} 237 238; Increasing loop, UINT_MAX. Positive test. 239define void @test_06(i32* %arr, i32* %a_len_ptr) #0 { 240 241; CHECK: test_06 242; CHECK: entry: 243; CHECK-NEXT: %exit.mainloop.at = load i32, i32* %a_len_ptr, align 4, !range !0 244; CHECK-NEXT: [[COND:%[^ ]+]] = icmp ult i32 0, %exit.mainloop.at 245; CHECK-NEXT: br i1 [[COND]], label %loop.preheader, label %main.pseudo.exit 246; CHECK: loop: 247; CHECK-NEXT: %idx = phi i32 [ %idx.next, %in.bounds ], [ 0, %loop.preheader ] 248; CHECK-NEXT: %idx.next = add nuw nsw i32 %idx, 1 249; CHECK-NEXT: %abc = icmp ult i32 %idx, %exit.mainloop.at 250; CHECK-NEXT: br i1 true, label %in.bounds, label %out.of.bounds.loopexit1 251; CHECK-NOT: loop.preloop: 252; CHECK: loop.postloop: 253; CHECK-NEXT: %idx.postloop = phi i32 [ %idx.copy, %postloop ], [ %idx.next.postloop, %in.bounds.postloop ] 254; CHECK-NEXT: %idx.next.postloop = add nuw nsw i32 %idx.postloop, 1 255; CHECK-NEXT: %abc.postloop = icmp ult i32 %idx.postloop, %exit.mainloop.at 256; CHECK-NEXT: br i1 %abc.postloop, label %in.bounds.postloop, label %out.of.bounds.loopexit 257 258entry: 259 %len = load i32, i32* %a_len_ptr, !range !0 260 br label %loop 261 262loop: 263 %idx = phi i32 [ 0, %entry ], [ %idx.next, %in.bounds ] 264 %idx.next = add nsw nuw i32 %idx, 1 265 %abc = icmp ult i32 %idx, %len 266 br i1 %abc, label %in.bounds, label %out.of.bounds 267 268in.bounds: 269 %addr = getelementptr i32, i32* %arr, i32 %idx 270 store i32 0, i32* %addr 271 %next = icmp ult i32 %idx.next, 4294967295 272 br i1 %next, label %loop, label %exit 273 274out.of.bounds: 275 ret void 276 277exit: 278 ret void 279} 280 281; Decreasing loop, UINT_MAX. Negative test: we cannot substract -1 from 0. 282define void @test_07(i32* %arr, i32* %a_len_ptr) #0 { 283 284; CHECK: test_07( 285; CHECK-NOT: loop.preloop: 286; CHECK-NOT: loop.postloop: 287 288entry: 289 %len = load i32, i32* %a_len_ptr, !range !0 290 br label %loop 291 292loop: 293 %idx = phi i32 [ 4294967295, %entry ], [ %idx.next, %in.bounds ] 294 %idx.next = add nuw i32 %idx, -1 295 %abc = icmp ult i32 %idx, %len 296 br i1 %abc, label %in.bounds, label %out.of.bounds 297 298in.bounds: 299 %addr = getelementptr i32, i32* %arr, i32 %idx 300 store i32 0, i32* %addr 301 %next = icmp ult i32 %idx.next, 0 302 br i1 %next, label %exit, label %loop 303 304out.of.bounds: 305 ret void 306 307exit: 308 ret void 309} 310 311; Unsigned walking through signed border is allowed. 312; Iteration space [0; UINT_MAX - 99), the fact that SINT_MAX is within this 313; range does not prevent us from performing IRCE. 314 315define void @test_08(i32* %arr, i32* %a_len_ptr) #0 { 316 317; CHECK: test_08 318; CHECK: entry: 319; CHECK-NEXT: %exit.mainloop.at = load i32, i32* %a_len_ptr, align 4, !range !0 320; CHECK-NEXT: [[COND:%[^ ]+]] = icmp ult i32 0, %exit.mainloop.at 321; CHECK-NEXT: br i1 [[COND]], label %loop.preheader, label %main.pseudo.exit 322; CHECK: loop: 323; CHECK-NEXT: %idx = phi i32 [ %idx.next, %in.bounds ], [ 0, %loop.preheader ] 324; CHECK-NEXT: %idx.next = add i32 %idx, 1 325; CHECK-NEXT: %abc = icmp ult i32 %idx, %exit.mainloop.at 326; CHECK-NEXT: br i1 true, label %in.bounds, label %out.of.bounds.loopexit1 327; CHECK-NOT: loop.preloop: 328; CHECK: loop.postloop: 329; CHECK-NEXT: %idx.postloop = phi i32 [ %idx.copy, %postloop ], [ %idx.next.postloop, %in.bounds.postloop ] 330; CHECK-NEXT: %idx.next.postloop = add i32 %idx.postloop, 1 331; CHECK-NEXT: %abc.postloop = icmp ult i32 %idx.postloop, %exit.mainloop.at 332; CHECK-NEXT: br i1 %abc.postloop, label %in.bounds.postloop, label %out.of.bounds.loopexit 333 334entry: 335 %len = load i32, i32* %a_len_ptr, !range !0 336 br label %loop 337 338loop: 339 %idx = phi i32 [ 0, %entry ], [ %idx.next, %in.bounds ] 340 %idx.next = add i32 %idx, 1 341 %abc = icmp ult i32 %idx, %len 342 br i1 %abc, label %in.bounds, label %out.of.bounds 343 344in.bounds: 345 %addr = getelementptr i32, i32* %arr, i32 %idx 346 store i32 0, i32* %addr 347 %next = icmp ult i32 %idx.next, -100 348 br i1 %next, label %loop, label %exit 349 350out.of.bounds: 351 ret void 352 353exit: 354 ret void 355} 356 357; Walking through the border of unsigned range is not allowed 358; (iteration space [-100; 100)). Negative test. 359 360define void @test_09(i32* %arr, i32* %a_len_ptr) #0 { 361 362; CHECK: test_09 363; CHECK-NOT: preloop 364; CHECK-NOT: postloop 365; CHECK-NOT: br i1 false 366; CHECK-NOT: br i1 true 367 368entry: 369 %len = load i32, i32* %a_len_ptr, !range !0 370 br label %loop 371 372loop: 373 %idx = phi i32 [ -100, %entry ], [ %idx.next, %in.bounds ] 374 %idx.next = add i32 %idx, 1 375 %abc = icmp ult i32 %idx, %len 376 br i1 %abc, label %in.bounds, label %out.of.bounds 377 378in.bounds: 379 %addr = getelementptr i32, i32* %arr, i32 %idx 380 store i32 0, i32* %addr 381 %next = icmp ult i32 %idx.next, 100 382 br i1 %next, label %loop, label %exit 383 384out.of.bounds: 385 ret void 386 387exit: 388 ret void 389} 390 391!0 = !{i32 0, i32 50} 392