Reapply [CHR] Fix up phi nodes with unreachable predecessors (PR64594)

Relative to the previous attempt, this also adjusts RegionInfo
verification to allow unreachable predecessors.

-----

If a block in the CHR region has an unreachable predecessor, then
there will be no edge from that predecessor to the newly cloned
block. However, a phi node entry for it will be left behind. Make
sure that these incoming blocks get dropped as well.

Fixes https://github.com/llvm/llvm-project/issues/64594.

Differential Revision: https://reviews.llvm.org/D157621

1 files changed, 14 insertions, 0 deletions

diff --git a/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp b/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp
index 3e3be53..597cec8 100644
--- a/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp
+++ b/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp
@@ -1777,6 +1777,20 @@ void CHR::cloneScopeBlocks(CHRScope *Scope,
       BasicBlock *NewBB = CloneBasicBlock(BB, VMap, ".nonchr", &F);
       NewBlocks.push_back(NewBB);
       VMap[BB] = NewBB;
+
+      // 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<PHINode>(NewBB->begin())) {
+        SmallVector<BasicBlock *> 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);
+      }
     }
 
   // Place the cloned blocks right after the original blocks (right before the