336 lines · plain
1; NOTE: Assertions have been autogenerated by utils/update_test_checks.py2; RUN: opt < %s -fix-irreducible --verify-loop-info -S | FileCheck %s3; RUN: opt < %s -passes='fix-irreducible,verify<loops>' -S | FileCheck %s4; RUN: opt < %s -passes='verify<loops>,fix-irreducible,verify<loops>' -S | FileCheck %s5 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:%.*]], true10; 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]], 114; 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 [ poison, [[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 %right28 29left:30 %L.phi = phi i32 [%X, %entry], [%R.phi, %right]31 %L = add i32 %L.phi, 132 br i1 %PredLeft, label %right, label %exit33 34right:35 %R.phi = phi i32 [%Y, %entry], [%L, %left]36 br i1 %PredRight, label %left, label %exit37 38exit:39 %Z = phi i32 [%L, %left], [%R.phi, %right]40 ret i32 %Z41}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:%.*]], true47; 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 [ poison, [[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 %right64 65left:66 %L.phi = phi i32 [%X, %entry], [%R.phi, %right]67 br i1 %PredLeft, label %right, label %exit68 69right:70 %R.phi = phi i32 [%Y, %entry], [%L.phi, %left]71 br i1 %PredRight, label %left, label %exit72 73exit:74 %Z = phi i32 [%L.phi, %left], [%R.phi, %right]75 ret i32 %Z76}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:%.*]], true82; CHECK-NEXT: br i1 [[PREDENTRY:%.*]], label [[A:%.*]], label [[B:%.*]]83; CHECK: A:84; CHECK-NEXT: [[A_INC:%.*]] = add i32 [[X:%.*]], 185; 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]], 193; 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 [ poison, [[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 %B105 106A:107 %A.inc = add i32 %X, 1108 br i1 %PredA, label %C, label %D109 110B:111 br i1 %PredB, label %D, label %C112 113C:114 %C.phi = phi i32 [%X, %A], [%Y, %B], [%D.inc, %D]115 br i1 %PredC, label %D, label %exit116 117D:118 %D.phi = phi i32 [%A.inc, %A], [%Y, %B], [%C.phi, %C]119 %D.inc = add i32 %D.phi, 1120 br i1 %PredD, label %exit, label %C121 122exit:123 %ret = phi i32 [%C.phi, %C], [%D.inc, %D]124 ret i32 %ret125}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:%.*]], 1133; 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:%.*]], 1141; 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 [ poison, [[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 %B153 154A:155 %A.inc = add i32 %X, 1156 br label %C157 158B:159 br label %D160 161C:162 %C.phi = phi i32 [%X, %A], [%D.inc, %D]163 br i1 %PredC, label %exit, label %D164 165D:166 %D.phi = phi i32 [%Y, %B], [%C.phi, %C]167 %D.inc = add i32 %D.phi, 1168 br i1 %PredD, label %exit, label %C169 170exit:171 %ret = phi i32 [%C.phi, %C], [%D.inc, %D]172 ret i32 %ret173}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:%.*]], true179; 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 void194; 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 %Y206 207X:208 br i1 %PredX, label %A, label %B209 210Y:211 br i1 %PredY, label %C, label %D212 213A:214 br label %B215 216B:217 br label %C218 219C:220 br label %D221 222D:223 br i1 %PredD, label %exit, label %A224 225exit:226 ret void227}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:%.*]], true233; 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]], 1237; 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:%.*]], 1242; 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 [ poison, [[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 %B257 258A:259 %A.phi = phi i32 [%X, %entry], [%C.inc, %E]260 %A.inc = add i32 %A.phi, 1261 br label %B262 263B:264 %B.phi = phi i32 [%A.inc, %A], [%Y, %entry]265 br label %C266 267C:268 %C.inc = add i32 %B.phi, 1269 br label %D270 271D:272 br i1 %PredD, label %exit, label %E273 274E:275 br label %A276 277exit:278 ret i32 %B.phi279}280 281 282define void @recursive_phis(i1 %cond, ptr addrspace(5) %ptr) {283; CHECK-LABEL: @recursive_phis(284; CHECK-NEXT: entry:285; CHECK-NEXT: [[ALLOCA:%.*]] = alloca i8, align 1, addrspace(5)286; CHECK-NEXT: br i1 [[COND:%.*]], label [[THEN:%.*]], label [[IRR_GUARD:%.*]]287; CHECK: then:288; CHECK-NEXT: [[PTR_INT:%.*]] = ptrtoint ptr addrspace(5) [[PTR:%.*]] to i32289; CHECK-NEXT: [[PTR_OR:%.*]] = and i32 [[PTR_INT]], 65535290; CHECK-NEXT: [[KB_PTR:%.*]] = inttoptr i32 [[PTR_OR]] to ptr addrspace(5)291; CHECK-NEXT: br label [[IRR_GUARD]]292; CHECK: else:293; CHECK-NEXT: br i1 [[COND]], label [[IRR_GUARD]], label [[BB:%.*]]294; CHECK: BB:295; CHECK-NEXT: br label [[FINALLY:%.*]]296; CHECK: finally:297; CHECK-NEXT: [[PHI_PTR:%.*]] = phi ptr addrspace(5) [ [[OTHER_PHI_MOVED:%.*]], [[BB]] ], [ [[PHI_PTR_MOVED:%.*]], [[IRR_GUARD]] ]298; CHECK-NEXT: [[X:%.*]] = addrspacecast ptr addrspace(5) [[PHI_PTR]] to ptr299; CHECK-NEXT: store volatile i32 7, ptr [[X]], align 4300; CHECK-NEXT: br i1 [[COND]], label [[IRR_GUARD]], label [[END:%.*]]301; CHECK: end:302; CHECK-NEXT: ret void303; CHECK: irr.guard:304; CHECK-NEXT: [[PHI_PTR_MOVED]] = phi ptr addrspace(5) [ poison, [[FINALLY]] ], [ poison, [[ELSE:%.*]] ], [ poison, [[ENTRY:%.*]] ], [ [[KB_PTR]], [[THEN]] ]305; CHECK-NEXT: [[OTHER_PHI_MOVED]] = phi ptr addrspace(5) [ [[PHI_PTR]], [[FINALLY]] ], [ [[OTHER_PHI_MOVED]], [[ELSE]] ], [ [[ALLOCA]], [[ENTRY]] ], [ poison, [[THEN]] ]306; CHECK-NEXT: [[GUARD_ELSE:%.*]] = phi i1 [ true, [[FINALLY]] ], [ true, [[ELSE]] ], [ true, [[ENTRY]] ], [ false, [[THEN]] ]307; CHECK-NEXT: br i1 [[GUARD_ELSE]], label [[ELSE]], label [[FINALLY]]308;309 310entry:311 %alloca = alloca i8, align 1, addrspace(5)312 br i1 %cond, label %then, label %else313 314then: ; preds = %entry315 %ptr.int = ptrtoint ptr addrspace(5) %ptr to i32316 %ptr.or = and i32 %ptr.int, 65535317 %kb.ptr = inttoptr i32 %ptr.or to ptr addrspace(5)318 br label %finally319 320else: ; preds = %finally, %else, %entry321 %other.phi = phi ptr addrspace(5) [ %alloca, %entry ], [ %phi.ptr, %finally ], [ undef, %else ]322 br i1 %cond, label %else, label %BB323 324BB: ; preds = %else325 br label %finally326 327finally: ; preds = %BB, %then328 %phi.ptr = phi ptr addrspace(5) [ %kb.ptr, %then ], [ %other.phi, %BB ]329 %x = addrspacecast ptr addrspace(5) %phi.ptr to ptr330 store volatile i32 7, ptr %x, align 4331 br i1 %cond, label %else, label %end332 333end: ; preds = %finally334 ret void335}336