286 lines · plain
1; NOTE: Assertions have been autogenerated by utils/update_test_checks.py2; RUN: opt < %s -passes=loop-unroll -verify-loop-lcssa -S | FileCheck %s3target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"4 5; This test shows how unrolling an inner loop could break LCSSA for an outer6; loop, and there is no cheap way to recover it.7;8; In this case the inner loop, L3, is being unrolled. It only runs one9; iteration, so unrolling basically means replacing10; br i1 true, label %exit, label %L3_header11; with12; br label %exit13;14; However, this change messes up the loops structure: for instance, block15; L3_body no longer belongs to L2. It becomes an exit block for L2, so LCSSA16; phis for definitions in L2 should now be placed there. In particular, we need17; to insert such a definition for %y1.18 19define void @foo1() {20; CHECK-LABEL: @foo1(21; CHECK-NEXT: entry:22; CHECK-NEXT: br label [[L1_HEADER:%.*]]23; CHECK: L1_header:24; CHECK-NEXT: br label [[L2_HEADER:%.*]]25; CHECK: L2_header:26; CHECK-NEXT: [[Y1:%.*]] = phi i64 [ undef, [[L1_HEADER]] ], [ [[X_LCSSA:%.*]], [[L2_LATCH:%.*]] ]27; CHECK-NEXT: br label [[L3_HEADER:%.*]]28; CHECK: L3_header:29; CHECK-NEXT: br i1 true, label [[L2_LATCH]], label [[L3_BODY:%.*]]30; CHECK: L2_latch:31; CHECK-NEXT: [[X_LCSSA]] = phi i64 [ undef, [[L3_HEADER]] ]32; CHECK-NEXT: br label [[L2_HEADER]]33; CHECK: L3_body:34; CHECK-NEXT: [[Y1_LCSSA:%.*]] = phi i64 [ [[Y1]], [[L3_HEADER]] ]35; CHECK-NEXT: store i64 [[Y1_LCSSA]], ptr undef, align 836; CHECK-NEXT: br i1 false, label [[L3_LATCH:%.*]], label [[L1_LATCH:%.*]]37; CHECK: L3_latch:38; CHECK-NEXT: ret void39; CHECK: L1_latch:40; CHECK-NEXT: [[Y_LCSSA:%.*]] = phi i64 [ [[Y1_LCSSA]], [[L3_BODY]] ]41; CHECK-NEXT: br label [[L1_HEADER]]42;43entry:44 br label %L1_header45 46L1_header:47 br label %L2_header48 49L2_header:50 %y1 = phi i64 [ undef, %L1_header ], [ %x.lcssa, %L2_latch ]51 br label %L3_header52 53L3_header:54 %y2 = phi i64 [ 0, %L3_latch ], [ %y1, %L2_header ]55 %x = add i64 undef, -156 br i1 true, label %L2_latch, label %L3_body57 58L2_latch:59 %x.lcssa = phi i64 [ %x, %L3_header ]60 br label %L2_header61 62L3_body:63 store i64 %y1, ptr undef64 br i1 false, label %L3_latch, label %L1_latch65 66L3_latch:67 br i1 true, label %exit, label %L3_header68 69L1_latch:70 %y.lcssa = phi i64 [ %y2, %L3_body ]71 br label %L1_header72 73exit:74 ret void75}76 77; Additional tests for some corner cases.78define void @foo2() {79; CHECK-LABEL: @foo2(80; CHECK-NEXT: entry:81; CHECK-NEXT: br label [[L1_HEADER:%.*]]82; CHECK: L1_header:83; CHECK-NEXT: br label [[L2_HEADER:%.*]]84; CHECK: L2_header.loopexit:85; CHECK-NEXT: [[DEC_US_LCSSA:%.*]] = phi i64 [ undef, [[L3_HEADER:%.*]] ]86; CHECK-NEXT: br label [[L2_HEADER]]87; CHECK: L2_header:88; CHECK-NEXT: [[A:%.*]] = phi i64 [ undef, [[L1_HEADER]] ], [ [[DEC_US_LCSSA]], [[L2_HEADER_LOOPEXIT:%.*]] ]89; CHECK-NEXT: br label [[L3_HEADER]]90; CHECK: L3_header:91; CHECK-NEXT: br i1 true, label [[L2_HEADER_LOOPEXIT]], label [[L3_BREAK_TO_L1:%.*]]92; CHECK: L3_break_to_L1:93; CHECK-NEXT: [[A_LCSSA:%.*]] = phi i64 [ [[A]], [[L3_HEADER]] ]94; CHECK-NEXT: br i1 false, label [[L3_LATCH:%.*]], label [[L1_LATCH:%.*]]95; CHECK: L1_latch:96; CHECK-NEXT: [[B_LCSSA:%.*]] = phi i64 [ [[A_LCSSA]], [[L3_BREAK_TO_L1]] ]97; CHECK-NEXT: br label [[L1_HEADER]]98; CHECK: L3_latch:99; CHECK-NEXT: ret void100;101entry:102 br label %L1_header103 104L1_header:105 br label %L2_header106 107L2_header:108 %a = phi i64 [ undef, %L1_header ], [ %dec_us, %L3_header ]109 br label %L3_header110 111L3_header:112 %b = phi i64 [ 0, %L3_latch ], [ %a, %L2_header ]113 %dec_us = add i64 undef, -1114 br i1 true, label %L2_header, label %L3_break_to_L1115 116L3_break_to_L1:117 br i1 false, label %L3_latch, label %L1_latch118 119L1_latch:120 %b_lcssa = phi i64 [ %b, %L3_break_to_L1 ]121 br label %L1_header122 123L3_latch:124 br i1 true, label %Exit, label %L3_header125 126Exit:127 ret void128}129 130define void @foo3(i1 %arg) {131; CHECK-LABEL: @foo3(132; CHECK-NEXT: entry:133; CHECK-NEXT: br label [[L1_HEADER:%.*]]134; CHECK: L1_header:135; CHECK-NEXT: [[A:%.*]] = phi ptr [ [[B:%.*]], [[L1_LATCH:%.*]] ], [ null, [[ENTRY:%.*]] ]136; CHECK-NEXT: br i1 [[ARG:%.*]], label [[L2_HEADER_PREHEADER:%.*]], label [[L1_LATCH]]137; CHECK: L2_header.preheader:138; CHECK-NEXT: br label [[L2_HEADER:%.*]]139; CHECK: L2_header:140; CHECK-NEXT: br i1 [[ARG]], label [[L2_LATCH:%.*]], label [[L1_LATCH_LOOPEXIT:%.*]]141; CHECK: L2_latch:142; CHECK-NEXT: [[A_LCSSA:%.*]] = phi ptr [ [[A]], [[L2_HEADER]] ]143; CHECK-NEXT: br label [[EXIT:%.*]]144; CHECK: L1_latch.loopexit:145; CHECK-NEXT: br label [[L1_LATCH]]146; CHECK: L1_latch:147; CHECK-NEXT: [[B]] = phi ptr [ undef, [[L1_HEADER]] ], [ null, [[L1_LATCH_LOOPEXIT]] ]148; CHECK-NEXT: br label [[L1_HEADER]]149; CHECK: Exit:150; CHECK-NEXT: [[A_LCSSA2:%.*]] = phi ptr [ [[A_LCSSA]], [[L2_LATCH]] ]151; CHECK-NEXT: ret void152;153entry:154 br label %L1_header155 156L1_header:157 %a = phi ptr [ %b, %L1_latch ], [ null, %entry ]158 br i1 %arg, label %L2_header, label %L1_latch159 160L2_header:161 br i1 %arg, label %L2_latch, label %L1_latch162 163L2_latch:164 br i1 true, label %L2_exit, label %L2_header165 166L1_latch:167 %b = phi ptr [ undef, %L1_header ], [ null, %L2_header ]168 br label %L1_header169 170L2_exit:171 %a_lcssa1 = phi ptr [ %a, %L2_latch ]172 br label %Exit173 174Exit:175 %a_lcssa2 = phi ptr [ %a_lcssa1, %L2_exit ]176 ret void177}178 179; PR26688180define i8 @foo4() {181; CHECK-LABEL: @foo4(182; CHECK-NEXT: entry:183; CHECK-NEXT: br label [[L1_HEADER:%.*]]184; CHECK: L1_header:185; CHECK-NEXT: br label [[L2_HEADER:%.*]]186; CHECK: L2_header.loopexit:187; CHECK-NEXT: br label [[L2_HEADER]]188; CHECK: L2_header:189; CHECK-NEXT: br label [[L3_HEADER:%.*]]190; CHECK: L3_header:191; CHECK-NEXT: br i1 true, label [[L2_HEADER_LOOPEXIT:%.*]], label [[L3_EXITING:%.*]]192; CHECK: L3_exiting:193; CHECK-NEXT: br i1 true, label [[L3_BODY:%.*]], label [[L1_LATCH:%.*]]194; CHECK: L3_body:195; CHECK-NEXT: [[X_LCSSA:%.*]] = phi i1 [ false, [[L3_EXITING]] ]196; CHECK-NEXT: br i1 [[X_LCSSA]], label [[L3_LATCH:%.*]], label [[L3_LATCH]]197; CHECK: L3_latch:198; CHECK-NEXT: ret i8 0199; CHECK: L1_latch:200; CHECK-NEXT: unreachable201;202entry:203 br label %L1_header204 205L1_header:206 %x = icmp eq i32 1, 0207 br label %L2_header208 209L2_header:210 br label %L3_header211 212L3_header:213 br i1 true, label %L2_header, label %L3_exiting214 215L3_exiting:216 br i1 true, label %L3_body, label %L1_latch217 218L3_body:219 br i1 %x, label %L3_latch, label %L3_latch220 221L3_latch:222 br i1 false, label %L3_header, label %exit223 224L1_latch:225 br label %L1_header226 227exit:228 ret i8 0229}230 231define void @foo5() {232; CHECK-LABEL: @foo5(233; CHECK-NEXT: entry:234; CHECK-NEXT: br label [[OUTER:%.*]]235; CHECK: outer:236; CHECK-NEXT: br label [[INNER1:%.*]]237; CHECK: inner1:238; CHECK-NEXT: br label [[INNER2_INDIRECT_EXIT:%.*]]239; CHECK: inner2_indirect_exit:240; CHECK-NEXT: [[A:%.*]] = phi i32 [ [[B:%.*]], [[INNER2_LATCH:%.*]] ], [ undef, [[INNER1]] ]241; CHECK-NEXT: indirectbr ptr undef, [label [[INNER2_LATCH]], label [[INNER3:%.*]], label %outer_latch]242; CHECK: inner2_latch:243; CHECK-NEXT: [[B]] = load i32, ptr undef, align 8244; CHECK-NEXT: br label [[INNER2_INDIRECT_EXIT]]245; CHECK: inner3:246; CHECK-NEXT: [[A_LCSSA:%.*]] = phi i32 [ [[A_LCSSA]], [[INNER3]] ], [ [[A]], [[INNER2_INDIRECT_EXIT]] ]247; CHECK-NEXT: br i1 true, label [[OUTER_LATCH_LOOPEXIT:%.*]], label [[INNER3]]248; CHECK: outer_latch.loopexit:249; CHECK-NEXT: [[A_LCSSA_LCSSA2:%.*]] = phi i32 [ [[A_LCSSA]], [[INNER3]] ]250; CHECK-NEXT: [[A_LCSSA_LCSSA:%.*]] = phi i32 [ [[A_LCSSA]], [[INNER3]] ]251; CHECK-NEXT: br label [[OUTER_LATCH:%.*]]252; CHECK: outer_latch:253; CHECK-NEXT: br label [[OUTER]]254;255entry:256 br label %outer257 258outer:259 br label %inner1260 261inner1:262 br i1 true, label %inner2_indirect_exit.preheader, label %inner1263 264inner2_indirect_exit.preheader:265 br label %inner2_indirect_exit266 267inner2_indirect_exit:268 %a = phi i32 [ %b, %inner2_latch ], [ undef, %inner2_indirect_exit.preheader ]269 indirectbr ptr undef, [label %inner2_latch, label %inner3, label %outer_latch]270 271inner2_latch:272 %b = load i32, ptr undef, align 8273 br label %inner2_indirect_exit274 275inner3:276 %a.lcssa = phi i32 [ %a.lcssa, %inner3 ], [ %a, %inner2_indirect_exit ]277 br i1 true, label %outer_latch.loopexit, label %inner3278 279outer_latch.loopexit:280 %a.lcssa.lcssa = phi i32 [ %a.lcssa, %inner3 ]281 br label %outer_latch282 283outer_latch:284 br label %outer285}286