1; NOTE: Assertions have been autogenerated by utils/update_test_checks.py 2; RUN: opt < %s -passes=loop-unroll -verify-loop-lcssa -S | FileCheck %s 3target 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 outer 6; 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 one 9; iteration, so unrolling basically means replacing 10; br i1 true, label %exit, label %L3_header 11; with 12; br label %exit 13; 14; However, this change messes up the loops structure: for instance, block 15; L3_body no longer belongs to L2. It becomes an exit block for L2, so LCSSA 16; phis for definitions in L2 should now be placed there. In particular, we need 17; 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 8 36; CHECK-NEXT: br i1 false, label [[L3_LATCH:%.*]], label [[L1_LATCH:%.*]] 37; CHECK: L3_latch: 38; CHECK-NEXT: ret void 39; 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_header 45 46L1_header: 47 br label %L2_header 48 49L2_header: 50 %y1 = phi i64 [ undef, %L1_header ], [ %x.lcssa, %L2_latch ] 51 br label %L3_header 52 53L3_header: 54 %y2 = phi i64 [ 0, %L3_latch ], [ %y1, %L2_header ] 55 %x = add i64 undef, -1 56 br i1 true, label %L2_latch, label %L3_body 57 58L2_latch: 59 %x.lcssa = phi i64 [ %x, %L3_header ] 60 br label %L2_header 61 62L3_body: 63 store i64 %y1, ptr undef 64 br i1 false, label %L3_latch, label %L1_latch 65 66L3_latch: 67 br i1 true, label %exit, label %L3_header 68 69L1_latch: 70 %y.lcssa = phi i64 [ %y2, %L3_body ] 71 br label %L1_header 72 73exit: 74 ret void 75} 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 void 100; 101entry: 102 br label %L1_header 103 104L1_header: 105 br label %L2_header 106 107L2_header: 108 %a = phi i64 [ undef, %L1_header ], [ %dec_us, %L3_header ] 109 br label %L3_header 110 111L3_header: 112 %b = phi i64 [ 0, %L3_latch ], [ %a, %L2_header ] 113 %dec_us = add i64 undef, -1 114 br i1 true, label %L2_header, label %L3_break_to_L1 115 116L3_break_to_L1: 117 br i1 false, label %L3_latch, label %L1_latch 118 119L1_latch: 120 %b_lcssa = phi i64 [ %b, %L3_break_to_L1 ] 121 br label %L1_header 122 123L3_latch: 124 br i1 true, label %Exit, label %L3_header 125 126Exit: 127 ret void 128} 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 void 152; 153entry: 154 br label %L1_header 155 156L1_header: 157 %a = phi ptr [ %b, %L1_latch ], [ null, %entry ] 158 br i1 %arg, label %L2_header, label %L1_latch 159 160L2_header: 161 br i1 %arg, label %L2_latch, label %L1_latch 162 163L2_latch: 164 br i1 true, label %L2_exit, label %L2_header 165 166L1_latch: 167 %b = phi ptr [ undef, %L1_header ], [ null, %L2_header ] 168 br label %L1_header 169 170L2_exit: 171 %a_lcssa1 = phi ptr [ %a, %L2_latch ] 172 br label %Exit 173 174Exit: 175 %a_lcssa2 = phi ptr [ %a_lcssa1, %L2_exit ] 176 ret void 177} 178 179; PR26688 180define 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 0 199; CHECK: L1_latch: 200; CHECK-NEXT: unreachable 201; 202entry: 203 br label %L1_header 204 205L1_header: 206 %x = icmp eq i32 1, 0 207 br label %L2_header 208 209L2_header: 210 br label %L3_header 211 212L3_header: 213 br i1 true, label %L2_header, label %L3_exiting 214 215L3_exiting: 216 br i1 true, label %L3_body, label %L1_latch 217 218L3_body: 219 br i1 %x, label %L3_latch, label %L3_latch 220 221L3_latch: 222 br i1 false, label %L3_header, label %exit 223 224L1_latch: 225 br label %L1_header 226 227exit: 228 ret i8 0 229} 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 8 244; 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 %outer 257 258outer: 259 br label %inner1 260 261inner1: 262 br i1 true, label %inner2_indirect_exit.preheader, label %inner1 263 264inner2_indirect_exit.preheader: 265 br label %inner2_indirect_exit 266 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 8 273 br label %inner2_indirect_exit 274 275inner3: 276 %a.lcssa = phi i32 [ %a.lcssa, %inner3 ], [ %a, %inner2_indirect_exit ] 277 br i1 true, label %outer_latch.loopexit, label %inner3 278 279outer_latch.loopexit: 280 %a.lcssa.lcssa = phi i32 [ %a.lcssa, %inner3 ] 281 br label %outer_latch 282 283outer_latch: 284 br label %outer 285} 286