1; NOTE: Assertions have been autogenerated by utils/update_test_checks.py 2; RUN: opt < %s -passes=loop-deletion -S | FileCheck %s 3 4@G = external global i32 5 6define void @test_trivial() { 7; CHECK-LABEL: @test_trivial( 8; CHECK-NEXT: entry: 9; CHECK-NEXT: br label [[LOOP:%.*]] 10; CHECK: loop: 11; CHECK-NEXT: store i32 0, ptr @G, align 4 12; CHECK-NEXT: br label [[EXIT:%.*]] 13; CHECK: exit: 14; CHECK-NEXT: ret void 15; 16entry: 17 br label %loop 18 19loop: 20 store i32 0, ptr @G 21 br i1 false, label %loop, label %exit 22 23exit: 24 ret void 25} 26 27 28define void @test_bottom_tested() { 29; CHECK-LABEL: @test_bottom_tested( 30; CHECK-NEXT: entry: 31; CHECK-NEXT: br label [[LOOP:%.*]] 32; CHECK: loop: 33; CHECK-NEXT: [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ] 34; CHECK-NEXT: store i32 0, ptr @G, align 4 35; CHECK-NEXT: [[IV_INC:%.*]] = add i32 [[IV]], 1 36; CHECK-NEXT: [[BE_TAKEN:%.*]] = icmp ne i32 [[IV_INC]], 1 37; CHECK-NEXT: br label [[EXIT:%.*]] 38; CHECK: exit: 39; CHECK-NEXT: ret void 40; 41entry: 42 br label %loop 43 44loop: 45 %iv = phi i32 [ 0, %entry], [ %iv.inc, %loop ] 46 store i32 0, ptr @G 47 %iv.inc = add i32 %iv, 1 48 %be_taken = icmp ne i32 %iv.inc, 1 49 br i1 %be_taken, label %loop, label %exit 50 51exit: 52 ret void 53} 54 55define void @test_early_exit() { 56; CHECK-LABEL: @test_early_exit( 57; CHECK-NEXT: entry: 58; CHECK-NEXT: br label [[LOOP:%.*]] 59; CHECK: loop: 60; CHECK-NEXT: [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ] 61; CHECK-NEXT: store i32 0, ptr @G, align 4 62; CHECK-NEXT: [[IV_INC:%.*]] = add i32 [[IV]], 1 63; CHECK-NEXT: [[BE_TAKEN:%.*]] = icmp ne i32 [[IV_INC]], 1 64; CHECK-NEXT: br i1 [[BE_TAKEN]], label [[LATCH:%.*]], label [[EXIT:%.*]] 65; CHECK: latch: 66; CHECK-NEXT: unreachable 67; CHECK: exit: 68; CHECK-NEXT: ret void 69; 70entry: 71 br label %loop 72 73loop: 74 %iv = phi i32 [ 0, %entry], [ %iv.inc, %latch ] 75 store i32 0, ptr @G 76 %iv.inc = add i32 %iv, 1 77 %be_taken = icmp ne i32 %iv.inc, 1 78 br i1 %be_taken, label %latch, label %exit 79latch: 80 br label %loop 81 82exit: 83 ret void 84} 85 86define void @test_multi_exit1() { 87; CHECK-LABEL: @test_multi_exit1( 88; CHECK-NEXT: entry: 89; CHECK-NEXT: br label [[LOOP:%.*]] 90; CHECK: loop: 91; CHECK-NEXT: [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ] 92; CHECK-NEXT: store i32 0, ptr @G, align 4 93; CHECK-NEXT: [[IV_INC:%.*]] = add i32 [[IV]], 1 94; CHECK-NEXT: [[BE_TAKEN:%.*]] = icmp ne i32 [[IV_INC]], 1 95; CHECK-NEXT: br i1 [[BE_TAKEN]], label [[LATCH:%.*]], label [[EXIT:%.*]] 96; CHECK: latch: 97; CHECK-NEXT: store i32 1, ptr @G, align 4 98; CHECK-NEXT: [[COND2:%.*]] = icmp ult i32 [[IV_INC]], 30 99; CHECK-NEXT: br label [[EXIT]] 100; CHECK: exit: 101; CHECK-NEXT: ret void 102; 103entry: 104 br label %loop 105 106loop: 107 %iv = phi i32 [ 0, %entry], [ %iv.inc, %latch ] 108 store i32 0, ptr @G 109 %iv.inc = add i32 %iv, 1 110 %be_taken = icmp ne i32 %iv.inc, 1 111 br i1 %be_taken, label %latch, label %exit 112latch: 113 store i32 1, ptr @G 114 %cond2 = icmp ult i32 %iv.inc, 30 115 br i1 %cond2, label %loop, label %exit 116 117exit: 118 ret void 119} 120 121define void @test_multi_exit2() { 122; CHECK-LABEL: @test_multi_exit2( 123; CHECK-NEXT: entry: 124; CHECK-NEXT: br label [[LOOP:%.*]] 125; CHECK: loop: 126; CHECK-NEXT: store i32 0, ptr @G, align 4 127; CHECK-NEXT: br i1 true, label [[LATCH:%.*]], label [[EXIT:%.*]] 128; CHECK: latch: 129; CHECK-NEXT: store i32 1, ptr @G, align 4 130; CHECK-NEXT: br label [[EXIT]] 131; CHECK: exit: 132; CHECK-NEXT: ret void 133; 134entry: 135 br label %loop 136 137loop: 138 store i32 0, ptr @G 139 br i1 true, label %latch, label %exit 140latch: 141 store i32 1, ptr @G 142 br i1 false, label %loop, label %exit 143 144exit: 145 ret void 146} 147 148define void @test_multi_exit3(i1 %cond1) { 149; CHECK-LABEL: @test_multi_exit3( 150; CHECK-NEXT: entry: 151; CHECK-NEXT: br label [[LOOP:%.*]] 152; CHECK: loop: 153; CHECK-NEXT: [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ] 154; CHECK-NEXT: store i32 0, ptr @G, align 4 155; CHECK-NEXT: br i1 [[COND1:%.*]], label [[LATCH:%.*]], label [[EXIT:%.*]] 156; CHECK: latch: 157; CHECK-NEXT: store i32 1, ptr @G, align 4 158; CHECK-NEXT: [[IV_INC:%.*]] = add i32 [[IV]], 1 159; CHECK-NEXT: [[BE_TAKEN:%.*]] = icmp ne i32 [[IV_INC]], 1 160; CHECK-NEXT: br label [[EXIT]] 161; CHECK: exit: 162; CHECK-NEXT: ret void 163; 164entry: 165 br label %loop 166 167loop: 168 %iv = phi i32 [ 0, %entry], [ %iv.inc, %latch ] 169 store i32 0, ptr @G 170 br i1 %cond1, label %latch, label %exit 171latch: 172 store i32 1, ptr @G 173 %iv.inc = add i32 %iv, 1 174 %be_taken = icmp ne i32 %iv.inc, 1 175 br i1 %be_taken, label %loop, label %exit 176 177exit: 178 ret void 179} 180 181; Subtle - This is either zero btc, or infinite, thus, can't break 182; backedge 183define void @test_multi_exit4(i1 %cond1, i1 %cond2) { 184; CHECK-LABEL: @test_multi_exit4( 185; CHECK-NEXT: entry: 186; CHECK-NEXT: br label [[LOOP:%.*]] 187; CHECK: loop: 188; CHECK-NEXT: store i32 0, ptr @G, align 4 189; CHECK-NEXT: br i1 [[COND1:%.*]], label [[LATCH:%.*]], label [[EXIT:%.*]] 190; CHECK: latch: 191; CHECK-NEXT: store i32 1, ptr @G, align 4 192; CHECK-NEXT: br i1 [[COND2:%.*]], label [[LOOP]], label [[EXIT]] 193; CHECK: exit: 194; CHECK-NEXT: ret void 195; 196entry: 197 br label %loop 198 199loop: 200 store i32 0, ptr @G 201 br i1 %cond1, label %latch, label %exit 202latch: 203 store i32 1, ptr @G 204 br i1 %cond2, label %loop, label %exit 205 206exit: 207 ret void 208} 209 210; A simple case with multiple exit blocks 211define void @test_multi_exit5() { 212; CHECK-LABEL: @test_multi_exit5( 213; CHECK-NEXT: entry: 214; CHECK-NEXT: br label [[LOOP:%.*]] 215; CHECK: loop: 216; CHECK-NEXT: store i32 0, ptr @G, align 4 217; CHECK-NEXT: br i1 true, label [[LATCH:%.*]], label [[EXIT1:%.*]] 218; CHECK: latch: 219; CHECK-NEXT: store i32 1, ptr @G, align 4 220; CHECK-NEXT: br label [[EXIT2:%.*]] 221; CHECK: exit1: 222; CHECK-NEXT: ret void 223; CHECK: exit2: 224; CHECK-NEXT: ret void 225; 226entry: 227 br label %loop 228 229loop: 230 store i32 0, ptr @G 231 br i1 true, label %latch, label %exit1 232latch: 233 store i32 1, ptr @G 234 br i1 false, label %loop, label %exit2 235 236exit1: 237 ret void 238exit2: 239 ret void 240} 241 242declare i1 @unknown() 243 244; We can't compute an exit count for the latch, but we know the upper 245; bound on the trip count is zero anyways. 246define void @test_dead_latch1() { 247; CHECK-LABEL: @test_dead_latch1( 248; CHECK-NEXT: entry: 249; CHECK-NEXT: br label [[LOOP:%.*]] 250; CHECK: loop: 251; CHECK-NEXT: store i32 0, ptr @G, align 4 252; CHECK-NEXT: br i1 false, label [[LATCH:%.*]], label [[EXIT1:%.*]] 253; CHECK: latch: 254; CHECK-NEXT: [[LATCHCOND:%.*]] = call i1 @unknown() 255; CHECK-NEXT: br label [[EXIT2:%.*]] 256; CHECK: exit1: 257; CHECK-NEXT: ret void 258; CHECK: exit2: 259; CHECK-NEXT: ret void 260; 261entry: 262 br label %loop 263 264loop: 265 store i32 0, ptr @G 266 br i1 false, label %latch, label %exit1 267latch: 268 %latchcond = call i1 @unknown() 269 br i1 %latchcond, label %loop, label %exit2 270 271exit1: 272 ret void 273exit2: 274 ret void 275} 276 277 278define void @test_live_inner() { 279; CHECK-LABEL: @test_live_inner( 280; CHECK-NEXT: entry: 281; CHECK-NEXT: br label [[LOOP:%.*]] 282; CHECK: loop: 283; CHECK-NEXT: store i32 0, ptr @G, align 4 284; CHECK-NEXT: br label [[INNER:%.*]] 285; CHECK: inner: 286; CHECK-NEXT: [[IV:%.*]] = phi i32 [ 0, [[LOOP]] ], [ [[IV_INC:%.*]], [[INNER]] ] 287; CHECK-NEXT: store i32 [[IV]], ptr @G, align 4 288; CHECK-NEXT: [[IV_INC]] = add i32 [[IV]], 1 289; CHECK-NEXT: [[CND:%.*]] = icmp ult i32 [[IV_INC]], 200 290; CHECK-NEXT: br i1 [[CND]], label [[INNER]], label [[LATCH:%.*]] 291; CHECK: latch: 292; CHECK-NEXT: br label [[EXIT:%.*]] 293; CHECK: exit: 294; CHECK-NEXT: ret void 295; 296entry: 297 br label %loop 298 299loop: 300 store i32 0, ptr @G 301 br label %inner 302 303inner: 304 %iv = phi i32 [0, %loop], [%iv.inc, %inner] 305 store i32 %iv, ptr @G 306 %iv.inc = add i32 %iv, 1 307 %cnd = icmp ult i32 %iv.inc, 200 308 br i1 %cnd, label %inner, label %latch 309 310latch: 311 br i1 false, label %loop, label %exit 312 313exit: 314 ret void 315} 316 317define void @test_live_outer() { 318; CHECK-LABEL: @test_live_outer( 319; CHECK-NEXT: entry: 320; CHECK-NEXT: br label [[LOOP:%.*]] 321; CHECK: loop: 322; CHECK-NEXT: [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_INC:%.*]], [[LATCH:%.*]] ] 323; CHECK-NEXT: br label [[INNER:%.*]] 324; CHECK: inner: 325; CHECK-NEXT: store i32 0, ptr @G, align 4 326; CHECK-NEXT: br label [[LATCH]] 327; CHECK: latch: 328; CHECK-NEXT: store i32 [[IV]], ptr @G, align 4 329; CHECK-NEXT: [[IV_INC]] = add i32 [[IV]], 1 330; CHECK-NEXT: [[CND:%.*]] = icmp ult i32 [[IV_INC]], 200 331; CHECK-NEXT: br i1 [[CND]], label [[LOOP]], label [[EXIT:%.*]] 332; CHECK: exit: 333; CHECK-NEXT: ret void 334; 335entry: 336 br label %loop 337 338loop: 339 %iv = phi i32 [0, %entry], [%iv.inc, %latch] 340 br label %inner 341 342inner: 343 store i32 0, ptr @G 344 br i1 false, label %inner, label %latch 345 346latch: 347 store i32 %iv, ptr @G 348 %iv.inc = add i32 %iv, 1 349 %cnd = icmp ult i32 %iv.inc, 200 350 br i1 %cnd, label %loop, label %exit 351 352exit: 353 ret void 354} 355 356; Key point is that inner_latch drops out of the outer loop when 357; the inner loop is deleted, and thus the lcssa phi needs to be 358; in the inner_latch block to preserve LCSSA. We either have to 359; insert the LCSSA phi, or not break the inner backedge. 360define void @loop_nest_lcssa() { 361; CHECK-LABEL: @loop_nest_lcssa( 362; CHECK-NEXT: entry: 363; CHECK-NEXT: [[TMP0:%.*]] = add i32 1, 2 364; CHECK-NEXT: br label [[OUTER_HEADER:%.*]] 365; CHECK: outer_header: 366; CHECK-NEXT: br label [[INNER_HEADER:%.*]] 367; CHECK: inner_header: 368; CHECK-NEXT: br i1 false, label [[INNER_LATCH:%.*]], label [[OUTER_LATCH:%.*]] 369; CHECK: inner_latch: 370; CHECK-NEXT: [[DOTLCSSA:%.*]] = phi i32 [ [[TMP0]], [[INNER_HEADER]] ] 371; CHECK-NEXT: br label [[LOOPEXIT:%.*]] 372; CHECK: outer_latch: 373; CHECK-NEXT: br label [[OUTER_HEADER]] 374; CHECK: loopexit: 375; CHECK-NEXT: [[DOTLCSSA32:%.*]] = phi i32 [ [[DOTLCSSA]], [[INNER_LATCH]] ] 376; CHECK-NEXT: unreachable 377; 378entry: 379 br label %outer_header 380 381outer_header: 382 %0 = add i32 1, 2 383 br label %inner_header 384 385inner_header: 386 br i1 false, label %inner_latch, label %outer_latch 387 388inner_latch: 389 br i1 false, label %inner_header, label %loopexit 390 391outer_latch: 392 br label %outer_header 393 394loopexit: 395 %.lcssa32 = phi i32 [ %0, %inner_latch ] 396 unreachable 397} 398