diff --git a/llvm/include/llvm/IR/Instructions.h b/llvm/include/llvm/IR/Instructions.h --- a/llvm/include/llvm/IR/Instructions.h +++ b/llvm/include/llvm/IR/Instructions.h @@ -2890,6 +2890,11 @@ return removeIncomingValue(Idx, DeletePHIIfEmpty); } + /// Remove all incoming values for which the predicate returns true. + /// The predicate accepts the incoming value index. + void removeIncomingValueIf(function_ref Predicate, + bool DeletePHIIfEmpty = true); + /// Return the first index of the specified basic /// block in the value list for this PHI. Returns -1 if no instance. /// diff --git a/llvm/lib/IR/Instructions.cpp b/llvm/lib/IR/Instructions.cpp --- a/llvm/lib/IR/Instructions.cpp +++ b/llvm/lib/IR/Instructions.cpp @@ -145,6 +145,39 @@ return Removed; } +void PHINode::removeIncomingValueIf(function_ref Predicate, + bool DeletePHIIfEmpty) { + SmallDenseSet RemoveIndices; + for (unsigned Idx = 0; Idx < getNumIncomingValues(); ++Idx) + if (Predicate(Idx)) + RemoveIndices.insert(Idx); + + if (RemoveIndices.empty()) + return; + + // Remove operands. + auto NewOpEnd = remove_if(operands(), [&](Use &U) { + return RemoveIndices.contains(U.getOperandNo()); + }); + for (Use &U : make_range(NewOpEnd, op_end())) + U.set(nullptr); + + // Remove incoming blocks. + std::remove_if(const_cast(block_begin()), + const_cast(block_end()), [&](BasicBlock *&BB) { + return RemoveIndices.contains(&BB - block_begin()); + }); + + setNumHungOffUseOperands(getNumOperands() - RemoveIndices.size()); + + // If the PHI node is dead, because it has zero entries, nuke it now. + if (getNumOperands() == 0 && DeletePHIIfEmpty) { + // If anyone is using this PHI, make them use a dummy value instead... + replaceAllUsesWith(PoisonValue::get(getType())); + eraseFromParent(); + } +} + /// growOperands - grow operands - This grows the operand list in response /// to a push_back style of operation. This grows the number of ops by 1.5 /// times. diff --git a/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp b/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp --- a/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp +++ b/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp @@ -1780,17 +1780,10 @@ // Unreachable predecessors will not be cloned and will not have an edge // to the cloned block. As such, also remove them from any phi nodes. - // To avoid iterator invalidation, first collect the dead predecessors - // from the first phi node, and then perform the actual removal. - if (auto *FirstPN = dyn_cast(NewBB->begin())) { - SmallVector DeadPreds; - for (BasicBlock *Pred : FirstPN->blocks()) - if (!DT.isReachableFromEntry(Pred)) - DeadPreds.push_back(Pred); - for (PHINode &PN : make_early_inc_range(NewBB->phis())) - for (BasicBlock *Pred : DeadPreds) - PN.removeIncomingValue(Pred); - } + for (PHINode &PN : make_early_inc_range(NewBB->phis())) + PN.removeIncomingValueIf([&](unsigned Idx) { + return !DT.isReachableFromEntry(PN.getIncomingBlock(Idx)); + }); } // Place the cloned blocks right after the original blocks (right before the diff --git a/llvm/lib/Transforms/Utils/BasicBlockUtils.cpp b/llvm/lib/Transforms/Utils/BasicBlockUtils.cpp --- a/llvm/lib/Transforms/Utils/BasicBlockUtils.cpp +++ b/llvm/lib/Transforms/Utils/BasicBlockUtils.cpp @@ -1137,14 +1137,11 @@ // If all incoming values for the new PHI would be the same, just don't // make a new PHI. Instead, just remove the incoming values from the old // PHI. - - // NOTE! This loop walks backwards for a reason! First off, this minimizes - // the cost of removal if we end up removing a large number of values, and - // second off, this ensures that the indices for the incoming values - // aren't invalidated when we remove one. - for (int64_t i = PN->getNumIncomingValues() - 1; i >= 0; --i) - if (PredSet.count(PN->getIncomingBlock(i))) - PN->removeIncomingValue(i, false); + PN->removeIncomingValueIf( + [&](unsigned Idx) { + return PredSet.contains(PN->getIncomingBlock(Idx)); + }, + /* DeletePHIIfEmpty */ false); // Add an incoming value to the PHI node in the loop for the preheader // edge. diff --git a/llvm/lib/Transforms/Utils/LoopSimplify.cpp b/llvm/lib/Transforms/Utils/LoopSimplify.cpp --- a/llvm/lib/Transforms/Utils/LoopSimplify.cpp +++ b/llvm/lib/Transforms/Utils/LoopSimplify.cpp @@ -429,8 +429,8 @@ PN->setIncomingBlock(0, PN->getIncomingBlock(PreheaderIdx)); } // Nuke all entries except the zero'th. - for (unsigned i = 0, e = PN->getNumIncomingValues()-1; i != e; ++i) - PN->removeIncomingValue(e-i, false); + PN->removeIncomingValueIf([](unsigned Idx) { return Idx != 0; }, + /* DeletePHIIfEmpty */ false); // Finally, add the newly constructed PHI node as the entry for the BEBlock. PN->addIncoming(NewPN, BEBlock); diff --git a/llvm/lib/Transforms/Utils/LoopUtils.cpp b/llvm/lib/Transforms/Utils/LoopUtils.cpp --- a/llvm/lib/Transforms/Utils/LoopUtils.cpp +++ b/llvm/lib/Transforms/Utils/LoopUtils.cpp @@ -556,12 +556,8 @@ // Removes all incoming values from all other exiting blocks (including // duplicate values from an exiting block). // Nuke all entries except the zero'th entry which is the preheader entry. - // NOTE! We need to remove Incoming Values in the reverse order as done - // below, to keep the indices valid for deletion (removeIncomingValues - // updates getNumIncomingValues and shifts all values down into the - // operand being deleted). - for (unsigned i = 0, e = P.getNumIncomingValues() - 1; i != e; ++i) - P.removeIncomingValue(e - i, false); + P.removeIncomingValueIf([](unsigned Idx) { return Idx != 0; }, + /* DeletePHIIfEmpty */ false); assert((P.getNumIncomingValues() == 1 && P.getIncomingBlock(PredIndex) == Preheader) && diff --git a/llvm/lib/Transforms/Utils/SimplifyCFG.cpp b/llvm/lib/Transforms/Utils/SimplifyCFG.cpp --- a/llvm/lib/Transforms/Utils/SimplifyCFG.cpp +++ b/llvm/lib/Transforms/Utils/SimplifyCFG.cpp @@ -5890,8 +5890,8 @@ // Remove the switch. - while (PHI->getBasicBlockIndex(SelectBB) >= 0) - PHI->removeIncomingValue(SelectBB); + PHI->removeIncomingValueIf( + [&](unsigned Idx) { return PHI->getIncomingBlock(Idx) == SelectBB; }); PHI->addIncoming(SelectValue, SelectBB); SmallPtrSet RemovedSuccessors;