1; NOTE: Assertions have been autogenerated by utils/update_test_checks.py 2; RUN: opt < %s -fix-irreducible --verify-loop-info -S | FileCheck %s 3; RUN: opt < %s -passes='fix-irreducible,verify<loops>' -S | FileCheck %s 4; RUN: opt < %s -passes='verify<loops>,fix-irreducible,verify<loops>' -S | FileCheck %s 5 6define i32 @basic(i1 %PredEntry, i1 %PredLeft, i1 %PredRight, i32 %X, i32 %Y) { 7; CHECK-LABEL: @basic( 8; CHECK-NEXT: entry: 9; CHECK-NEXT: [[PREDENTRY_INV:%.*]] = xor i1 [[PREDENTRY:%.*]], true 10; CHECK-NEXT: br label [[IRR_GUARD:%.*]] 11; CHECK: left: 12; CHECK-NEXT: [[L_PHI:%.*]] = phi i32 [ [[R_PHI_MOVED:%.*]], [[RIGHT:%.*]] ], [ [[L_PHI_MOVED:%.*]], [[IRR_GUARD]] ] 13; CHECK-NEXT: [[L:%.*]] = add i32 [[L_PHI]], 1 14; CHECK-NEXT: br i1 [[PREDLEFT:%.*]], label [[IRR_GUARD]], label [[EXIT:%.*]] 15; CHECK: right: 16; CHECK-NEXT: br i1 [[PREDRIGHT:%.*]], label [[LEFT:%.*]], label [[EXIT]] 17; CHECK: exit: 18; CHECK-NEXT: [[Z:%.*]] = phi i32 [ [[L]], [[LEFT]] ], [ [[R_PHI_MOVED]], [[RIGHT]] ] 19; CHECK-NEXT: ret i32 [[Z]] 20; CHECK: irr.guard: 21; CHECK-NEXT: [[L_PHI_MOVED]] = phi i32 [ [[L_PHI_MOVED]], [[LEFT]] ], [ [[X:%.*]], [[ENTRY:%.*]] ] 22; CHECK-NEXT: [[R_PHI_MOVED]] = phi i32 [ [[L]], [[LEFT]] ], [ [[Y:%.*]], [[ENTRY]] ] 23; CHECK-NEXT: [[GUARD_RIGHT:%.*]] = phi i1 [ true, [[LEFT]] ], [ [[PREDENTRY_INV]], [[ENTRY]] ] 24; CHECK-NEXT: br i1 [[GUARD_RIGHT]], label [[RIGHT]], label [[LEFT]] 25; 26entry: 27 br i1 %PredEntry, label %left, label %right 28 29left: 30 %L.phi = phi i32 [%X, %entry], [%R.phi, %right] 31 %L = add i32 %L.phi, 1 32 br i1 %PredLeft, label %right, label %exit 33 34right: 35 %R.phi = phi i32 [%Y, %entry], [%L, %left] 36 br i1 %PredRight, label %left, label %exit 37 38exit: 39 %Z = phi i32 [%L, %left], [%R.phi, %right] 40 ret i32 %Z 41} 42 43define i32 @feedback_loop(i1 %PredEntry, i1 %PredLeft, i1 %PredRight, i32 %X, i32 %Y) { 44; CHECK-LABEL: @feedback_loop( 45; CHECK-NEXT: entry: 46; CHECK-NEXT: [[PREDENTRY_INV:%.*]] = xor i1 [[PREDENTRY:%.*]], true 47; CHECK-NEXT: br label [[IRR_GUARD:%.*]] 48; CHECK: left: 49; CHECK-NEXT: [[L_PHI:%.*]] = phi i32 [ [[R_PHI_MOVED:%.*]], [[RIGHT:%.*]] ], [ [[L_PHI_MOVED:%.*]], [[IRR_GUARD]] ] 50; CHECK-NEXT: br i1 [[PREDLEFT:%.*]], label [[IRR_GUARD]], label [[EXIT:%.*]] 51; CHECK: right: 52; CHECK-NEXT: br i1 [[PREDRIGHT:%.*]], label [[LEFT:%.*]], label [[EXIT]] 53; CHECK: exit: 54; CHECK-NEXT: [[Z:%.*]] = phi i32 [ [[L_PHI]], [[LEFT]] ], [ [[R_PHI_MOVED]], [[RIGHT]] ] 55; CHECK-NEXT: ret i32 [[Z]] 56; CHECK: irr.guard: 57; CHECK-NEXT: [[L_PHI_MOVED]] = phi i32 [ [[L_PHI_MOVED]], [[LEFT]] ], [ [[X:%.*]], [[ENTRY:%.*]] ] 58; CHECK-NEXT: [[R_PHI_MOVED]] = phi i32 [ [[L_PHI]], [[LEFT]] ], [ [[Y:%.*]], [[ENTRY]] ] 59; CHECK-NEXT: [[GUARD_RIGHT:%.*]] = phi i1 [ true, [[LEFT]] ], [ [[PREDENTRY_INV]], [[ENTRY]] ] 60; CHECK-NEXT: br i1 [[GUARD_RIGHT]], label [[RIGHT]], label [[LEFT]] 61; 62entry: 63 br i1 %PredEntry, label %left, label %right 64 65left: 66 %L.phi = phi i32 [%X, %entry], [%R.phi, %right] 67 br i1 %PredLeft, label %right, label %exit 68 69right: 70 %R.phi = phi i32 [%Y, %entry], [%L.phi, %left] 71 br i1 %PredRight, label %left, label %exit 72 73exit: 74 %Z = phi i32 [%L.phi, %left], [%R.phi, %right] 75 ret i32 %Z 76} 77 78define i32 @multiple_predecessors(i1 %PredEntry, i1 %PredA, i1 %PredB, i1 %PredC, i1 %PredD, i32 %X, i32 %Y) { 79; CHECK-LABEL: @multiple_predecessors( 80; CHECK-NEXT: entry: 81; CHECK-NEXT: [[PREDB_INV:%.*]] = xor i1 [[PREDB:%.*]], true 82; CHECK-NEXT: br i1 [[PREDENTRY:%.*]], label [[A:%.*]], label [[B:%.*]] 83; CHECK: A: 84; CHECK-NEXT: [[A_INC:%.*]] = add i32 [[X:%.*]], 1 85; CHECK-NEXT: br label [[IRR_GUARD:%.*]] 86; CHECK: B: 87; CHECK-NEXT: br label [[IRR_GUARD]] 88; CHECK: C: 89; CHECK-NEXT: br i1 [[PREDC:%.*]], label [[D:%.*]], label [[EXIT:%.*]] 90; CHECK: D: 91; CHECK-NEXT: [[D_PHI:%.*]] = phi i32 [ [[C_PHI_MOVED:%.*]], [[C:%.*]] ], [ [[D_PHI_MOVED:%.*]], [[IRR_GUARD]] ] 92; CHECK-NEXT: [[D_INC:%.*]] = add i32 [[D_PHI]], 1 93; CHECK-NEXT: br i1 [[PREDD:%.*]], label [[EXIT]], label [[IRR_GUARD]] 94; CHECK: exit: 95; CHECK-NEXT: [[RET:%.*]] = phi i32 [ [[C_PHI_MOVED]], [[C]] ], [ [[D_INC]], [[D]] ] 96; CHECK-NEXT: ret i32 [[RET]] 97; CHECK: irr.guard: 98; CHECK-NEXT: [[D_PHI_MOVED]] = phi i32 [ [[D_PHI_MOVED]], [[D]] ], [ [[Y:%.*]], [[B]] ], [ [[A_INC]], [[A]] ] 99; CHECK-NEXT: [[C_PHI_MOVED]] = phi i32 [ [[D_INC]], [[D]] ], [ [[Y]], [[B]] ], [ [[X]], [[A]] ] 100; CHECK-NEXT: [[GUARD_C:%.*]] = phi i1 [ true, [[D]] ], [ [[PREDB_INV]], [[B]] ], [ [[PREDA:%.*]], [[A]] ] 101; CHECK-NEXT: br i1 [[GUARD_C]], label [[C]], label [[D]] 102; 103entry: 104 br i1 %PredEntry, label %A, label %B 105 106A: 107 %A.inc = add i32 %X, 1 108 br i1 %PredA, label %C, label %D 109 110B: 111 br i1 %PredB, label %D, label %C 112 113C: 114 %C.phi = phi i32 [%X, %A], [%Y, %B], [%D.inc, %D] 115 br i1 %PredC, label %D, label %exit 116 117D: 118 %D.phi = phi i32 [%A.inc, %A], [%Y, %B], [%C.phi, %C] 119 %D.inc = add i32 %D.phi, 1 120 br i1 %PredD, label %exit, label %C 121 122exit: 123 %ret = phi i32 [%C.phi, %C], [%D.inc, %D] 124 ret i32 %ret 125} 126 127define i32 @separate_predecessors(i1 %PredEntry, i1 %PredA, i1 %PredB, i1 %PredC, i1 %PredD, i32 %X, i32 %Y) { 128; CHECK-LABEL: @separate_predecessors( 129; CHECK-NEXT: entry: 130; CHECK-NEXT: br i1 [[PREDENTRY:%.*]], label [[A:%.*]], label [[B:%.*]] 131; CHECK: A: 132; CHECK-NEXT: [[A_INC:%.*]] = add i32 [[X:%.*]], 1 133; CHECK-NEXT: br label [[IRR_GUARD:%.*]] 134; CHECK: B: 135; CHECK-NEXT: br label [[IRR_GUARD]] 136; CHECK: C: 137; CHECK-NEXT: [[C_PHI:%.*]] = phi i32 [ [[D_INC:%.*]], [[D:%.*]] ], [ [[C_PHI_MOVED:%.*]], [[IRR_GUARD]] ] 138; CHECK-NEXT: br i1 [[PREDC:%.*]], label [[EXIT:%.*]], label [[IRR_GUARD]] 139; CHECK: D: 140; CHECK-NEXT: [[D_INC]] = add i32 [[D_PHI_MOVED:%.*]], 1 141; CHECK-NEXT: br i1 [[PREDD:%.*]], label [[EXIT]], label [[C:%.*]] 142; CHECK: exit: 143; CHECK-NEXT: [[RET:%.*]] = phi i32 [ [[C_PHI]], [[C]] ], [ [[D_INC]], [[D]] ] 144; CHECK-NEXT: ret i32 [[RET]] 145; CHECK: irr.guard: 146; CHECK-NEXT: [[C_PHI_MOVED]] = phi i32 [ [[C_PHI_MOVED]], [[C]] ], [ poison, [[B]] ], [ [[X]], [[A]] ] 147; CHECK-NEXT: [[D_PHI_MOVED]] = phi i32 [ [[C_PHI]], [[C]] ], [ [[Y:%.*]], [[B]] ], [ poison, [[A]] ] 148; CHECK-NEXT: [[GUARD_D:%.*]] = phi i1 [ true, [[C]] ], [ true, [[B]] ], [ false, [[A]] ] 149; CHECK-NEXT: br i1 [[GUARD_D]], label [[D]], label [[C]] 150; 151entry: 152 br i1 %PredEntry, label %A, label %B 153 154A: 155 %A.inc = add i32 %X, 1 156 br label %C 157 158B: 159 br label %D 160 161C: 162 %C.phi = phi i32 [%X, %A], [%D.inc, %D] 163 br i1 %PredC, label %exit, label %D 164 165D: 166 %D.phi = phi i32 [%Y, %B], [%C.phi, %C] 167 %D.inc = add i32 %D.phi, 1 168 br i1 %PredD, label %exit, label %C 169 170exit: 171 %ret = phi i32 [%C.phi, %C], [%D.inc, %D] 172 ret i32 %ret 173} 174 175define void @four_headers(i1 %PredEntry, i1 %PredX, i1 %PredY, i1 %PredD) { 176; CHECK-LABEL: @four_headers( 177; CHECK-NEXT: entry: 178; CHECK-NEXT: [[PREDY_INV:%.*]] = xor i1 [[PREDY:%.*]], true 179; CHECK-NEXT: br i1 [[PREDENTRY:%.*]], label [[X:%.*]], label [[Y:%.*]] 180; CHECK: X: 181; CHECK-NEXT: br label [[IRR_GUARD:%.*]] 182; CHECK: Y: 183; CHECK-NEXT: br label [[IRR_GUARD]] 184; CHECK: A: 185; CHECK-NEXT: br label [[B:%.*]] 186; CHECK: B: 187; CHECK-NEXT: br label [[C:%.*]] 188; CHECK: C: 189; CHECK-NEXT: br label [[IRR_GUARD]] 190; CHECK: D: 191; CHECK-NEXT: br i1 [[PREDD:%.*]], label [[EXIT:%.*]], label [[A:%.*]] 192; CHECK: exit: 193; CHECK-NEXT: ret void 194; CHECK: irr.guard: 195; CHECK-NEXT: [[GUARD_D:%.*]] = phi i1 [ true, [[C]] ], [ [[PREDY_INV]], [[Y]] ], [ false, [[X]] ] 196; CHECK-NEXT: [[GUARD_C:%.*]] = phi i1 [ false, [[C]] ], [ true, [[Y]] ], [ false, [[X]] ] 197; CHECK-NEXT: [[GUARD_A:%.*]] = phi i1 [ false, [[C]] ], [ false, [[Y]] ], [ [[PREDX:%.*]], [[X]] ] 198; CHECK-NEXT: br i1 [[GUARD_D]], label [[D:%.*]], label [[IRR_GUARD1:%.*]] 199; CHECK: irr.guard1: 200; CHECK-NEXT: br i1 [[GUARD_C]], label [[C]], label [[IRR_GUARD2:%.*]] 201; CHECK: irr.guard2: 202; CHECK-NEXT: br i1 [[GUARD_A]], label [[A]], label [[B]] 203; 204entry: 205 br i1 %PredEntry, label %X, label %Y 206 207X: 208 br i1 %PredX, label %A, label %B 209 210Y: 211 br i1 %PredY, label %C, label %D 212 213A: 214 br label %B 215 216B: 217 br label %C 218 219C: 220 br label %D 221 222D: 223 br i1 %PredD, label %exit, label %A 224 225exit: 226 ret void 227} 228 229define i32 @hidden_nodes(i1 %PredEntry, i1 %PredA, i1 %PredB, i1 %PredC, i1 %PredD, i32 %X, i32 %Y) { 230; CHECK-LABEL: @hidden_nodes( 231; CHECK-NEXT: entry: 232; CHECK-NEXT: [[PREDENTRY_INV:%.*]] = xor i1 [[PREDENTRY:%.*]], true 233; CHECK-NEXT: br label [[IRR_GUARD:%.*]] 234; CHECK: A: 235; CHECK-NEXT: [[A_PHI:%.*]] = phi i32 [ [[C_INC:%.*]], [[E:%.*]] ], [ [[A_PHI_MOVED:%.*]], [[IRR_GUARD]] ] 236; CHECK-NEXT: [[A_INC:%.*]] = add i32 [[A_PHI]], 1 237; CHECK-NEXT: br label [[IRR_GUARD]] 238; CHECK: B: 239; CHECK-NEXT: br label [[C:%.*]] 240; CHECK: C: 241; CHECK-NEXT: [[C_INC]] = add i32 [[B_PHI_MOVED:%.*]], 1 242; CHECK-NEXT: br label [[D:%.*]] 243; CHECK: D: 244; CHECK-NEXT: br i1 [[PREDD:%.*]], label [[EXIT:%.*]], label [[E]] 245; CHECK: E: 246; CHECK-NEXT: br label [[A:%.*]] 247; CHECK: exit: 248; CHECK-NEXT: ret i32 [[B_PHI_MOVED]] 249; CHECK: irr.guard: 250; CHECK-NEXT: [[A_PHI_MOVED]] = phi i32 [ [[A_PHI_MOVED]], [[A]] ], [ [[X:%.*]], [[ENTRY:%.*]] ] 251; CHECK-NEXT: [[B_PHI_MOVED]] = phi i32 [ [[A_INC]], [[A]] ], [ [[Y:%.*]], [[ENTRY]] ] 252; CHECK-NEXT: [[GUARD_B:%.*]] = phi i1 [ true, [[A]] ], [ [[PREDENTRY_INV]], [[ENTRY]] ] 253; CHECK-NEXT: br i1 [[GUARD_B]], label [[B:%.*]], label [[A]] 254; 255entry: 256 br i1 %PredEntry, label %A, label %B 257 258A: 259 %A.phi = phi i32 [%X, %entry], [%C.inc, %E] 260 %A.inc = add i32 %A.phi, 1 261 br label %B 262 263B: 264 %B.phi = phi i32 [%A.inc, %A], [%Y, %entry] 265 br label %C 266 267C: 268 %C.inc = add i32 %B.phi, 1 269 br label %D 270 271D: 272 br i1 %PredD, label %exit, label %E 273 274E: 275 br label %A 276 277exit: 278 ret i32 %B.phi 279} 280