398 lines · plain
1; NOTE: Assertions have been autogenerated by utils/update_test_checks.py2; RUN: opt < %s -passes=loop-deletion -S | FileCheck %s3 4@G = external global i325 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 412; CHECK-NEXT: br label [[EXIT:%.*]]13; CHECK: exit:14; CHECK-NEXT: ret void15;16entry:17 br label %loop18 19loop:20 store i32 0, ptr @G21 br i1 false, label %loop, label %exit22 23exit:24 ret void25}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 435; CHECK-NEXT: [[IV_INC:%.*]] = add i32 [[IV]], 136; CHECK-NEXT: [[BE_TAKEN:%.*]] = icmp ne i32 [[IV_INC]], 137; CHECK-NEXT: br label [[EXIT:%.*]]38; CHECK: exit:39; CHECK-NEXT: ret void40;41entry:42 br label %loop43 44loop:45 %iv = phi i32 [ 0, %entry], [ %iv.inc, %loop ]46 store i32 0, ptr @G47 %iv.inc = add i32 %iv, 148 %be_taken = icmp ne i32 %iv.inc, 149 br i1 %be_taken, label %loop, label %exit50 51exit:52 ret void53}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 462; CHECK-NEXT: [[IV_INC:%.*]] = add i32 [[IV]], 163; CHECK-NEXT: [[BE_TAKEN:%.*]] = icmp ne i32 [[IV_INC]], 164; CHECK-NEXT: br i1 [[BE_TAKEN]], label [[LATCH:%.*]], label [[EXIT:%.*]]65; CHECK: latch:66; CHECK-NEXT: unreachable67; CHECK: exit:68; CHECK-NEXT: ret void69;70entry:71 br label %loop72 73loop:74 %iv = phi i32 [ 0, %entry], [ %iv.inc, %latch ]75 store i32 0, ptr @G76 %iv.inc = add i32 %iv, 177 %be_taken = icmp ne i32 %iv.inc, 178 br i1 %be_taken, label %latch, label %exit79latch:80 br label %loop81 82exit:83 ret void84}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 493; CHECK-NEXT: [[IV_INC:%.*]] = add i32 [[IV]], 194; CHECK-NEXT: [[BE_TAKEN:%.*]] = icmp ne i32 [[IV_INC]], 195; CHECK-NEXT: br i1 [[BE_TAKEN]], label [[LATCH:%.*]], label [[EXIT:%.*]]96; CHECK: latch:97; CHECK-NEXT: store i32 1, ptr @G, align 498; CHECK-NEXT: [[COND2:%.*]] = icmp ult i32 [[IV_INC]], 3099; CHECK-NEXT: br label [[EXIT]]100; CHECK: exit:101; CHECK-NEXT: ret void102;103entry:104 br label %loop105 106loop:107 %iv = phi i32 [ 0, %entry], [ %iv.inc, %latch ]108 store i32 0, ptr @G109 %iv.inc = add i32 %iv, 1110 %be_taken = icmp ne i32 %iv.inc, 1111 br i1 %be_taken, label %latch, label %exit112latch:113 store i32 1, ptr @G114 %cond2 = icmp ult i32 %iv.inc, 30115 br i1 %cond2, label %loop, label %exit116 117exit:118 ret void119}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 4127; CHECK-NEXT: br i1 true, label [[LATCH:%.*]], label [[EXIT:%.*]]128; CHECK: latch:129; CHECK-NEXT: store i32 1, ptr @G, align 4130; CHECK-NEXT: br label [[EXIT]]131; CHECK: exit:132; CHECK-NEXT: ret void133;134entry:135 br label %loop136 137loop:138 store i32 0, ptr @G139 br i1 true, label %latch, label %exit140latch:141 store i32 1, ptr @G142 br i1 false, label %loop, label %exit143 144exit:145 ret void146}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 4155; CHECK-NEXT: br i1 [[COND1:%.*]], label [[LATCH:%.*]], label [[EXIT:%.*]]156; CHECK: latch:157; CHECK-NEXT: store i32 1, ptr @G, align 4158; CHECK-NEXT: [[IV_INC:%.*]] = add i32 [[IV]], 1159; CHECK-NEXT: [[BE_TAKEN:%.*]] = icmp ne i32 [[IV_INC]], 1160; CHECK-NEXT: br label [[EXIT]]161; CHECK: exit:162; CHECK-NEXT: ret void163;164entry:165 br label %loop166 167loop:168 %iv = phi i32 [ 0, %entry], [ %iv.inc, %latch ]169 store i32 0, ptr @G170 br i1 %cond1, label %latch, label %exit171latch:172 store i32 1, ptr @G173 %iv.inc = add i32 %iv, 1174 %be_taken = icmp ne i32 %iv.inc, 1175 br i1 %be_taken, label %loop, label %exit176 177exit:178 ret void179}180 181; Subtle - This is either zero btc, or infinite, thus, can't break182; backedge183define 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 4189; CHECK-NEXT: br i1 [[COND1:%.*]], label [[LATCH:%.*]], label [[EXIT:%.*]]190; CHECK: latch:191; CHECK-NEXT: store i32 1, ptr @G, align 4192; CHECK-NEXT: br i1 [[COND2:%.*]], label [[LOOP]], label [[EXIT]]193; CHECK: exit:194; CHECK-NEXT: ret void195;196entry:197 br label %loop198 199loop:200 store i32 0, ptr @G201 br i1 %cond1, label %latch, label %exit202latch:203 store i32 1, ptr @G204 br i1 %cond2, label %loop, label %exit205 206exit:207 ret void208}209 210; A simple case with multiple exit blocks211define 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 4217; CHECK-NEXT: br i1 true, label [[LATCH:%.*]], label [[EXIT1:%.*]]218; CHECK: latch:219; CHECK-NEXT: store i32 1, ptr @G, align 4220; CHECK-NEXT: br label [[EXIT2:%.*]]221; CHECK: exit1:222; CHECK-NEXT: ret void223; CHECK: exit2:224; CHECK-NEXT: ret void225;226entry:227 br label %loop228 229loop:230 store i32 0, ptr @G231 br i1 true, label %latch, label %exit1232latch:233 store i32 1, ptr @G234 br i1 false, label %loop, label %exit2235 236exit1:237 ret void238exit2:239 ret void240}241 242declare i1 @unknown()243 244; We can't compute an exit count for the latch, but we know the upper245; 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 4252; 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 void258; CHECK: exit2:259; CHECK-NEXT: ret void260;261entry:262 br label %loop263 264loop:265 store i32 0, ptr @G266 br i1 false, label %latch, label %exit1267latch:268 %latchcond = call i1 @unknown()269 br i1 %latchcond, label %loop, label %exit2270 271exit1:272 ret void273exit2:274 ret void275}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 4284; 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 4288; CHECK-NEXT: [[IV_INC]] = add i32 [[IV]], 1289; CHECK-NEXT: [[CND:%.*]] = icmp ult i32 [[IV_INC]], 200290; 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 void295;296entry:297 br label %loop298 299loop:300 store i32 0, ptr @G301 br label %inner302 303inner:304 %iv = phi i32 [0, %loop], [%iv.inc, %inner]305 store i32 %iv, ptr @G306 %iv.inc = add i32 %iv, 1307 %cnd = icmp ult i32 %iv.inc, 200308 br i1 %cnd, label %inner, label %latch309 310latch:311 br i1 false, label %loop, label %exit312 313exit:314 ret void315}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 4326; CHECK-NEXT: br label [[LATCH]]327; CHECK: latch:328; CHECK-NEXT: store i32 [[IV]], ptr @G, align 4329; CHECK-NEXT: [[IV_INC]] = add i32 [[IV]], 1330; CHECK-NEXT: [[CND:%.*]] = icmp ult i32 [[IV_INC]], 200331; CHECK-NEXT: br i1 [[CND]], label [[LOOP]], label [[EXIT:%.*]]332; CHECK: exit:333; CHECK-NEXT: ret void334;335entry:336 br label %loop337 338loop:339 %iv = phi i32 [0, %entry], [%iv.inc, %latch]340 br label %inner341 342inner:343 store i32 0, ptr @G344 br i1 false, label %inner, label %latch345 346latch:347 store i32 %iv, ptr @G348 %iv.inc = add i32 %iv, 1349 %cnd = icmp ult i32 %iv.inc, 200350 br i1 %cnd, label %loop, label %exit351 352exit:353 ret void354}355 356; Key point is that inner_latch drops out of the outer loop when357; the inner loop is deleted, and thus the lcssa phi needs to be358; in the inner_latch block to preserve LCSSA. We either have to359; 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, 2364; 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: unreachable377;378entry:379 br label %outer_header380 381outer_header:382 %0 = add i32 1, 2383 br label %inner_header384 385inner_header:386 br i1 false, label %inner_latch, label %outer_latch387 388inner_latch:389 br i1 false, label %inner_header, label %loopexit390 391outer_latch:392 br label %outer_header393 394loopexit:395 %.lcssa32 = phi i32 [ %0, %inner_latch ]396 unreachable397}398