Index: lib/Transforms/Utils/LCSSA.cpp =================================================================== --- lib/Transforms/Utils/LCSSA.cpp +++ lib/Transforms/Utils/LCSSA.cpp @@ -74,7 +74,7 @@ bool llvm::formLCSSAForInstructions(SmallVectorImpl &Worklist, DominatorTree &DT, LoopInfo &LI) { SmallVector UsesToRewrite; - SmallSetVector PHIsToRemove; + SmallSetVector PHIsToRemoveIfNotUsed; PredIteratorCache PredCache; bool Changed = false; @@ -214,22 +214,34 @@ if (!PostProcessPN->use_empty()) Worklist.push_back(PostProcessPN); - // Keep track of PHI nodes that we want to remove because they did not have - // any uses rewritten. If the new PHI is used, store it so that we can - // try to propagate dbg.value intrinsics to it. + // Keep track of PHI nodes that we createe, so that we can remove them again + // if they did not have any uses rewritten. + PHIsToRemoveIfNotUsed.insert(AddedPHIs.begin(), AddedPHIs.end()); + + // If the new PHI is used, store it so that we can try to propagate + // dbg.value intrinsics to it. SmallVector NeedDbgValues; for (PHINode *PN : AddedPHIs) - if (PN->use_empty()) - PHIsToRemove.insert(PN); - else + if (!PN->use_empty()) NeedDbgValues.push_back(PN); insertDebugValuesForPHIs(InstBB, NeedDbgValues); Changed = true; } - // Remove PHI nodes that did not have any uses rewritten. - for (PHINode *PN : PHIsToRemove) { - assert (PN->use_empty() && "Trying to remove a phi with uses."); - PN->eraseFromParent(); + // Remove PHI nodes that did not have any uses rewritten. We do this in an + // iterative manner as we may reveal more unused PHI along the way. + bool RemovePHIs = true; + while (RemovePHIs) { + RemovePHIs = false; + SmallSetVector NotRemoved; + for (PHINode *PN : PHIsToRemoveIfNotUsed) { + if (PN->use_empty()) { + PN->eraseFromParent(); + RemovePHIs = true; + } else + NotRemoved.insert(PN); + } + // Update the set of candidates for the next iteration. + PHIsToRemoveIfNotUsed = NotRemoved; } return Changed; } Index: test/Transforms/LCSSA/remove-phis.ll =================================================================== --- /dev/null +++ test/Transforms/LCSSA/remove-phis.ll @@ -0,0 +1,237 @@ +; NOTE: Assertions have been autogenerated by utils/update_test_checks.py +; RUN: opt < %s -lcssa -verify -S -o - | FileCheck %s + +; This bugpoint reduced test case used to assert when removing unused PHI nodes. + +define void @f3() { +; CHECK-LABEL: @f3( +; CHECK-NEXT: entry: +; CHECK-NEXT: br label [[LBL1:%.*]] +; CHECK: lbl1: +; CHECK-NEXT: [[F_0:%.*]] = phi i16 [ 0, [[ENTRY:%.*]] ], [ undef, [[CLEANUP:%.*]] ] +; CHECK-NEXT: br i1 undef, label [[IF_THEN:%.*]], label [[IF_ELSE:%.*]] +; CHECK: if.then: +; CHECK-NEXT: br i1 undef, label [[CLEANUP]], label [[IF_END:%.*]] +; CHECK: if.end: +; CHECK-NEXT: br i1 undef, label [[IF_THEN5:%.*]], label [[CLEANUP]] +; CHECK: if.then5: +; CHECK-NEXT: [[F_0_LCSSA1:%.*]] = phi i16 [ [[F_0]], [[IF_END]] ] +; CHECK-NEXT: br label [[FOR_BODY:%.*]] +; CHECK: for.body: +; CHECK-NEXT: [[F_1:%.*]] = phi i16 [ [[F_0_LCSSA1]], [[IF_THEN5]] ], [ 0, [[FOR_BODY]] ] +; CHECK-NEXT: br label [[FOR_BODY]] +; CHECK: cleanup: +; CHECK-NEXT: br i1 undef, label [[CLEANUP98:%.*]], label [[LBL1]] +; CHECK: if.else: +; CHECK-NEXT: [[F_0_LCSSA:%.*]] = phi i16 [ [[F_0]], [[LBL1]] ] +; CHECK-NEXT: br label [[LBL2:%.*]] +; CHECK: lbl2.loopexit: +; CHECK-NEXT: br label [[LBL2]] +; CHECK: lbl2: +; CHECK-NEXT: [[F_09:%.*]] = phi i16 [ undef, [[LBL2_LOOPEXIT:%.*]] ], [ [[F_0_LCSSA]], [[IF_ELSE]] ] +; CHECK-NEXT: br label [[FOR_COND8:%.*]] +; CHECK: for.cond8: +; CHECK-NEXT: [[F_08:%.*]] = phi i16 [ [[F_07:%.*]], [[CLEANUP24:%.*]] ], [ [[F_09]], [[LBL2]] ] +; CHECK-NEXT: br i1 undef, label [[FOR_BODY13:%.*]], label [[FOR_COND30_PREHEADER:%.*]] +; CHECK: for.cond30.preheader: +; CHECK-NEXT: [[F_08_LCSSA:%.*]] = phi i16 [ [[F_08]], [[FOR_COND8]] ] +; CHECK-NEXT: br label [[FOR_COND30:%.*]] +; CHECK: for.body13: +; CHECK-NEXT: br label [[CLEANUP24]] +; CHECK: for.cond17: +; CHECK-NEXT: br i1 undef, label [[FOR_BODY19:%.*]], label [[CLEANUP24]] +; CHECK: for.body19: +; CHECK-NEXT: br i1 undef, label [[LAND_RHS:%.*]], label [[FOR_COND17:%.*]] +; CHECK: land.rhs: +; CHECK-NEXT: br label [[FOR_COND17]] +; CHECK: cleanup24: +; CHECK-NEXT: [[F_07]] = phi i16 [ undef, [[FOR_COND17]] ], [ [[F_08]], [[FOR_BODY13]] ] +; CHECK-NEXT: br i1 undef, label [[FOR_COND8]], label [[CLEANUP94:%.*]] +; CHECK: for.cond30: +; CHECK-NEXT: [[F_06:%.*]] = phi i16 [ [[F_05:%.*]], [[FOR_INC91:%.*]] ], [ [[F_08_LCSSA]], [[FOR_COND30_PREHEADER]] ] +; CHECK-NEXT: br label [[FOR_COND31:%.*]] +; CHECK: for.cond31: +; CHECK-NEXT: br i1 undef, label [[FOR_BODY33:%.*]], label [[FOR_END35:%.*]] +; CHECK: for.body33: +; CHECK-NEXT: br label [[FOR_COND31]] +; CHECK: for.end35: +; CHECK-NEXT: br i1 undef, label [[CLEANUP88_THREAD37:%.*]], label [[IF_ELSE44:%.*]] +; CHECK: cleanup88.thread37: +; CHECK-NEXT: [[F_06_LCSSA:%.*]] = phi i16 [ [[F_06]], [[FOR_END35]] ] +; CHECK-NEXT: br label [[CLEANUP94_THREAD:%.*]] +; CHECK: if.else44: +; CHECK-NEXT: br i1 undef, label [[CLEANUP88_THREAD38:%.*]], label [[CLEANUP88_THREAD:%.*]] +; CHECK: cleanup88.thread38: +; CHECK-NEXT: br label [[FOR_INC91]] +; CHECK: for.cond50: +; CHECK-NEXT: br label [[FOR_COND50:%.*]] +; CHECK: for.cond58: +; CHECK-NEXT: br i1 undef, label [[FOR_BODY60:%.*]], label [[CLEANUP73:%.*]] +; CHECK: for.body60: +; CHECK-NEXT: br label [[ARRAYINIT_BODY:%.*]] +; CHECK: arrayinit.body: +; CHECK-NEXT: br i1 undef, label [[ARRAYINIT_END62:%.*]], label [[ARRAYINIT_BODY]] +; CHECK: arrayinit.end62: +; CHECK-NEXT: br i1 undef, label [[CLEANUP68:%.*]], label [[IF_END66:%.*]] +; CHECK: if.end66: +; CHECK-NEXT: br label [[CLEANUP68]] +; CHECK: cleanup68: +; CHECK-NEXT: br i1 undef, label [[FOR_COND58:%.*]], label [[CLEANUP73]] +; CHECK: cleanup73: +; CHECK-NEXT: br i1 undef, label [[CLEANUP_CONT77:%.*]], label [[CLEANUP88:%.*]] +; CHECK: cleanup.cont77: +; CHECK-NEXT: br label [[FOR_COND78:%.*]] +; CHECK: for.cond78: +; CHECK-NEXT: br i1 undef, label [[FOR_BODY80:%.*]], label [[CLEANUP88_THREAD]] +; CHECK: for.body80: +; CHECK-NEXT: br label [[FOR_COND78]] +; CHECK: cleanup88.thread: +; CHECK-NEXT: [[F_04:%.*]] = phi i16 [ undef, [[FOR_COND78]] ], [ [[F_06]], [[IF_ELSE44]] ] +; CHECK-NEXT: br label [[CLEANUP94]] +; CHECK: cleanup88: +; CHECK-NEXT: switch i32 undef, label [[CLEANUP94]] [ +; CHECK-NEXT: i32 12, label [[CLEANUP94_THREAD]] +; CHECK-NEXT: i32 14, label [[FOR_INC91]] +; CHECK-NEXT: i32 5, label [[LBL2_LOOPEXIT]] +; CHECK-NEXT: ] +; CHECK: for.inc91: +; CHECK-NEXT: [[F_05]] = phi i16 [ undef, [[CLEANUP88]] ], [ [[F_06]], [[CLEANUP88_THREAD38]] ] +; CHECK-NEXT: br label [[FOR_COND30]] +; CHECK: cleanup94.thread: +; CHECK-NEXT: [[F_010:%.*]] = phi i16 [ undef, [[CLEANUP88]] ], [ [[F_06_LCSSA]], [[CLEANUP88_THREAD37]] ] +; CHECK-NEXT: br label [[CLEANUP98]] +; CHECK: cleanup94: +; CHECK-NEXT: [[F_03:%.*]] = phi i16 [ undef, [[CLEANUP88]] ], [ [[F_04]], [[CLEANUP88_THREAD]] ], [ [[F_07]], [[CLEANUP24]] ] +; CHECK-NEXT: br label [[CLEANUP98]] +; CHECK: cleanup98: +; CHECK-NEXT: ret void +; +entry: + br label %lbl1 + +lbl1: ; preds = %cleanup, %entry + %f.0 = phi i16 [ 0, %entry ], [ undef, %cleanup ] + br i1 undef, label %if.then, label %if.else + +if.then: ; preds = %lbl1 + br i1 undef, label %cleanup, label %if.end + +if.end: ; preds = %if.then + br i1 undef, label %if.then5, label %cleanup + +if.then5: ; preds = %if.end + br label %for.body + +for.body: ; preds = %for.body, %if.then5 + %f.1 = phi i16 [ %f.0, %if.then5 ], [ 0, %for.body ] + br label %for.body + +cleanup: ; preds = %if.end, %if.then + br i1 undef, label %cleanup98, label %lbl1 + +if.else: ; preds = %lbl1 + br label %lbl2 + +lbl2.loopexit: ; preds = %cleanup88 + br label %lbl2 + +lbl2: ; preds = %lbl2.loopexit, %if.else + br label %for.cond8 + +for.cond8: ; preds = %cleanup24, %lbl2 + br i1 undef, label %for.body13, label %for.cond30.preheader + +for.cond30.preheader: ; preds = %for.cond8 + br label %for.cond30 + +for.body13: ; preds = %for.cond8 + br label %cleanup24 + +for.cond17: ; preds = %land.rhs, %for.body19 + br i1 undef, label %for.body19, label %cleanup24 + +for.body19: ; preds = %for.cond17 + br i1 undef, label %land.rhs, label %for.cond17 + +land.rhs: ; preds = %for.body19 + br label %for.cond17 + +cleanup24: ; preds = %for.cond17, %for.body13 + br i1 undef, label %for.cond8, label %cleanup94 + +for.cond30: ; preds = %for.inc91, %for.cond30.preheader + br label %for.cond31 + +for.cond31: ; preds = %for.body33, %for.cond30 + br i1 undef, label %for.body33, label %for.end35 + +for.body33: ; preds = %for.cond31 + br label %for.cond31 + +for.end35: ; preds = %for.cond31 + br i1 undef, label %cleanup88.thread37, label %if.else44 + +cleanup88.thread37: ; preds = %for.end35 + br label %cleanup94.thread + +if.else44: ; preds = %for.end35 + br i1 undef, label %cleanup88.thread38, label %cleanup88.thread + +cleanup88.thread38: ; preds = %if.else44 + br label %for.inc91 + +for.cond50: ; preds = %for.cond50 + br label %for.cond50 + +for.cond58: ; preds = %cleanup68 + br i1 undef, label %for.body60, label %cleanup73 + +for.body60: ; preds = %for.cond58 + br label %arrayinit.body + +arrayinit.body: ; preds = %arrayinit.body, %for.body60 + br i1 undef, label %arrayinit.end62, label %arrayinit.body + +arrayinit.end62: ; preds = %arrayinit.body + br i1 undef, label %cleanup68, label %if.end66 + +if.end66: ; preds = %arrayinit.end62 + br label %cleanup68 + +cleanup68: ; preds = %if.end66, %arrayinit.end62 + br i1 undef, label %for.cond58, label %cleanup73 + +cleanup73: ; preds = %cleanup68, %for.cond58 + br i1 undef, label %cleanup.cont77, label %cleanup88 + +cleanup.cont77: ; preds = %cleanup73 + br label %for.cond78 + +for.cond78: ; preds = %for.body80, %cleanup.cont77 + br i1 undef, label %for.body80, label %cleanup88.thread + +for.body80: ; preds = %for.cond78 + br label %for.cond78 + +cleanup88.thread: ; preds = %for.cond78, %if.else44 + br label %cleanup94 + +cleanup88: ; preds = %cleanup73 + switch i32 undef, label %cleanup94 [ + i32 12, label %cleanup94.thread + i32 14, label %for.inc91 + i32 5, label %lbl2.loopexit + ] + +for.inc91: ; preds = %cleanup88, %cleanup88.thread38 + br label %for.cond30 + +cleanup94.thread: ; preds = %cleanup88, %cleanup88.thread37 + br label %cleanup98 + +cleanup94: ; preds = %cleanup88, %cleanup88.thread, %cleanup24 + br label %cleanup98 + +cleanup98: ; preds = %cleanup94, %cleanup94.thread, %cleanup + ret void +}