SafepointIRVerifier should ignore dead blocks and dead edges

[yrouban]

Summary

Not only should SafepointIRVerifier ignore unreachable blocks
(as suggested in https://reviews.llvm.org/D47011) but it also
has to ignore dead blocks.

In @test2 (see the new tests):

  br i1 true, label %right, label %left
left:
  ...
right:
  ...
merge:
  %val = phi i8 addrspace(1)* [ ..., %left ], [ ..., %right ]
  use %val

both left and right branches are reachable.
If they collide then SafepointIRVerifier reports an error.

Because of the foldable branch condition GVN finds the left
branch dead and removes the phi node entry that merges values
from right and left. Then the use comes from the right branch.
This results in no collision.

So, SafepointIRVerifier ends up in different results depending
on either GVN is run or not.

To solve this issue this patch adds Dead Block detection to
SafepointIRVerifier which can ignore dead blocks while
validating IR. The Dead Block detection algorithm is taken
from GVN but modified to not split critical edges. That is
needed to keep CFG unchanged by SafepointIRVerifier.

[yrouban]

I realized that there is a case with a dead edge but without dead blocks. I will improve the patch and add a testcase.

[yrouban]

Added test cases with a dead edge but without dead blocks.
Fixed the algorithm to ignore such dead edges.

Please review.

[anna]

lib/IR/SafepointIRVerifier.cpp

381

This seems like a generally useful analysis to have outside of the safepoint IR Verifier. We should think of moving the code into Analysis.

You mentioned it's taken from the GVN but modified to avoid splitting the critical edges. Could you please state that as a comment here: modified version from GVN::addDeadBlock.

421

comment here that block maybe already dead if it's dominated by NewDead blocks processed earlier.

441

Change to assert instead of check.

[yrouban]

Addressed Anna's comments: extracted a separate analysis pass called CFG Deadness.

[DaniilSuchkov]

include/llvm/IR/CFGDeadness.h

47 ↗

(On Diff #149405)

Please add a comment that explains what kind of uses this method expects, it isn't obvious.

50 ↗

(On Diff #149405)

Could you please add here an assertion that U->getUser() is block terminator?

lib/IR/CFGDeadness.cpp

87 ↗

(On Diff #149405)

As Anna said before, this should be an assertion.

[yrouban]

Added dead edge definition and appropriate assertions to the method isDeadEdge().
Inlined the method processFoldableCondBr() into processInstruction().

[yrouban]

Please review the patch.
Anna, Daniil, you are the best candidates for reviewing the patch.

[DaniilSuchkov]

LGTM

[anna]

Hi Yevgeny, this looks close to commit. Comments inline.

lib/IR/CFGDeadness.cpp

127 ↗

(On Diff #149770)

I think the assert and the corresponding ifdef compilation with break isn't very useful. It's just testing a property of the IRVerifier for phi nodes.
Also, conditional compilation with behaviour change is not very preferable. Could we get rid of this?

160 ↗

(On Diff #149770)

it doesn't modify CFG, so the cfg arg should be false.

163 ↗

(On Diff #149770)

ditto here.

[yrouban]

lib/IR/CFGDeadness.cpp

127 ↗

(On Diff #149770)

In debug mode these two assertions (1) and (2) check that for this phi node and the specified basic block there is at leats one edge (2) and no more than one edge (1). To check (1) we need to iterate through the whole set of predecessors, that is why we should not break at the first found edge. Any other way to express this more elegantly?
This assertion seems obvious, but I did not find a place in LLVM (other than the LL parser) that prevents phis with duplicate pairs like phi [%value1, %block1], [%value1, %block1]. In this case, how many incoming edges do we have, 1 or 2?

160 ↗

(On Diff #149770)

Hm, it is not obvious from the sources.
But why DominatorTreeWrapperPass has its set to true then?

INITIALIZE_PASS(DominatorTreeWrapperPass, "domtree", "Dominator Tree Construction", true, true)

[anna]

lib/IR/CFGDeadness.cpp

127 ↗

(On Diff #149770)

Yes, I got what you were doing :)
I incorrectly thought this exact case is handled in the IR verifier (i.e. it fails with dup blocks), so we don't need to do this here. But this is infact valid IR (having duplicate pairs will be 2 edges, i.e. 2 preds for that basic block).
So, now that I think of it since the verifier allows it, the IR is valid - so why should we have this assert in the first place?

[anna]

lib/IR/CFGDeadness.cpp

160 ↗

(On Diff #149770)

not sure about the dom tree case - might be a bug, but pretty much all other analysis pass have the CFG arg as false, because, we don't modify the CFG (and I believe that's true in this pass as well, right?).

[yrouban]

Addressed Anna's comments:

1. changed INITIALIZE_PASS CFGDeadness CFG flag to false.
2. The new method CFGDeadness::hasLiveIncomingEdge(Phi, Block) replaces CFGDeadness::getIncomingEdge(Phi, Block) that could not work with phi containing duplicate pairs of (value,block).

[apilipenko]

Can you describe what is the difference you observe in the verifier behavior with and without simplifications before? There will always be cases when some simplifications before the verifier change the CFG. You won't be able to handle everything in this analysis.

lib/IR/CFGDeadness.cpp

115–116 ↗

(On Diff #150605)

You only look at branches in processInstruction, right? You don't need to iterate all instructions then, just check the terminator of the BB.

[yrouban]

Removed CFGDeadness::processInstruction() and changed to iterate over the block terminators.

[yrouban]

previous diff was incorrect, please ignore it.
In this diff I removed CFGDeadness::processInstruction() and changed to iterate over the block terminators.

[apilipenko]

lib/IR/SafepointIRVerifier.cpp

381

@anna, I think this is not of much use outside of SafepointIRVerifier. Most passes don't need to worry about this patterns as it's reasonable to expect simplifycfg to have cleaned things up.

Verifiers is a different story as you don't want you verification logic depend on the optimizations performed on the code. You also don't want to modify the code to clean up the mess.

I would suggest keeping this logic in SafepointIRVerifier. If we want to extract it as a separate analysis I'd suggest making a clear comment that it has very specific purpose.

[anna]

lib/IR/SafepointIRVerifier.cpp

381

There's one specific use for this pass outside of the SafepointIRVerifier and that's for loopSimplifyCFG - we cannot rely on SimplifyCFG to cleanup dead/unreachable blocks that are dead *because* of LoopSimplifyCFG. So, I suspect this will be useful for loop optimizations that are run as a group in a pipeline without the need for a function pass like SimplifyCFG.

Perhaps we can add a clear comment stating where it's usage is expected and that right now it's used in the SafepointIRVerifier.

[anna]

Generally LGTM. pls wait for Artur's comments (if any).

[apilipenko]

lib/IR/CFGDeadness.cpp

12 ↗

(On Diff #150621)

I don't think that GVN reference is important here. It just happened to be the detail of the current implementation. I think the higher level interface/comment should be that the analysis tracks trivially dead edges without modifying the CFG.

Could you please add a comment that in most cases passes rely on SimplifyCFG to clean up such blocks, but in some cases, like verification or loop passes it's not possible.

lib/IR/SafepointIRVerifier.cpp

381

Makes sense.

[yrouban]

Added Artur's comment.

[yrouban]

LLVM committers, this patch seems to be ready for landing, please.

[yrouban]

Removed a separate analysis pass - CFGDeadness is made internal.

[anna]

LGTM. Artur, could you please land the patch? My llvm repo seems to be having issues. Thanks.

[yrouban]

Spasibo, Artur.

lib/IR/SafepointIRVerifier.cpp

 using namespace llvm;
 
 /// This option is used for writing test cases.  Instead of crashing the program
 /// when verification fails, report a message to the console (for FileCheck
 /// usage) and continue execution as if nothing happened.
 static cl::opt<bool> PrintOnly("safepoint-ir-verifier-print-only",
                                cl::init(false));
 
-static void Verify(const Function &F, const DominatorTree &DT);
+namespace {
+
+/// This CFG Deadness finds dead blocks and edges. Algorithm starts with a set
+/// of blocks unreachable from entry then propagates deadness using foldable
+/// conditional branches without modifying CFG. So GVN does but it changes CFG
+/// by splitting critical edges. In most cases passes rely on SimplifyCFG to
+/// clean up dead blocks, but in some cases, like verification or loop passes
+/// it's not possible.
+class CFGDeadness {
+  const DominatorTree *DT = nullptr;
+  SetVector<const BasicBlock *> DeadBlocks;
+  SetVector<const Use *> DeadEdges; // Contains all dead edges from live blocks.
+
+public:
+  /// Return the edge that coresponds to the predecessor.
+  static const Use& getEdge(const_pred_iterator &PredIt) {
+    auto &PU = PredIt.getUse();
+    return PU.getUser()->getOperandUse(PU.getOperandNo());
+  }
+
+  /// Return true if there is at least one live edge that corresponds to the
+  /// basic block InBB listed in the phi node.
+  bool hasLiveIncomingEdge(const PHINode *PN, const BasicBlock *InBB) const {
+    assert(!isDeadBlock(InBB) && "block must be live");
+    const BasicBlock* BB = PN->getParent();
+    bool Listed = false;
+    for (const_pred_iterator PredIt(BB), End(BB, true); PredIt != End; ++PredIt) {
+      if (InBB == *PredIt) {
+        if (!isDeadEdge(&getEdge(PredIt)))
+          return true;
+        Listed = true;
+      }
+    }
+    assert(Listed && "basic block is not found among incoming blocks");
+    return false;
+  }
+
+
+  bool isDeadBlock(const BasicBlock *BB) const {
+    return DeadBlocks.count(BB);
+  }
+
+  bool isDeadEdge(const Use *U) const {
+    assert(dyn_cast<Instruction>(U->getUser())->isTerminator() &&
+           "edge must be operand of terminator");
+    assert(cast_or_null<BasicBlock>(U->get()) &&
+           "edge must refer to basic block");
+    assert(!isDeadBlock(dyn_cast<Instruction>(U->getUser())->getParent()) &&
+           "isDeadEdge() must be applied to edge from live block");
+    return DeadEdges.count(U);
+  }
+
+  bool hasLiveIncomingEdges(const BasicBlock *BB) const {
+    // Check if all incoming edges are dead.
+    for (const_pred_iterator PredIt(BB), End(BB, true); PredIt != End; ++PredIt) {
+      auto &PU = PredIt.getUse();
+      const Use &U = PU.getUser()->getOperandUse(PU.getOperandNo());
+      if (!isDeadBlock(*PredIt) && !isDeadEdge(&U))
+        return true; // Found a live edge.
+    }
+    return false;
+  }
+
+  void processFunction(const Function &F, const DominatorTree &DT) {
+    this->DT = &DT;
+
+    // Start with all blocks unreachable from entry.
+    for (const BasicBlock &BB : F)
+      if (!DT.isReachableFromEntry(&BB))
+        DeadBlocks.insert(&BB);
+
+    // Top-down walk of the dominator tree
+    ReversePostOrderTraversal<const Function *> RPOT(&F);
+    for (const BasicBlock *BB : RPOT) {
+      const TerminatorInst *TI = BB->getTerminator();
+      assert(TI && "blocks must be well formed");
+
+      // For conditional branches, we can perform simple conditional propagation on
+      // the condition value itself.
+      const BranchInst *BI = dyn_cast<BranchInst>(TI);
+      if (!BI || !BI->isConditional() || !isa<Constant>(BI->getCondition()))
+        continue;
+
+      // If a branch has two identical successors, we cannot declare either dead.
+      if (BI->getSuccessor(0) == BI->getSuccessor(1))
+        continue;
+
+      ConstantInt *Cond = dyn_cast<ConstantInt>(BI->getCondition());
+      if (!Cond)
+        continue;
+
+      addDeadEdge(BI->getOperandUse(Cond->getZExtValue() ? 1 : 2));
+    }
+  }
+
+protected:
+  void addDeadBlock(const BasicBlock *BB) {
+    SmallVector<const BasicBlock *, 4> NewDead;
+    SmallSetVector<const BasicBlock *, 4> DF;
+
+    NewDead.push_back(BB);
+    while (!NewDead.empty()) {
+      const BasicBlock *D = NewDead.pop_back_val();
+      if (isDeadBlock(D))
+        continue;
+
+      // All blocks dominated by D are dead.
+      SmallVector<BasicBlock *, 8> Dom;
+      DT->getDescendants(const_cast<BasicBlock*>(D), Dom);
+      // Do not need to mark all in and out edges dead
+      // because BB is marked dead and this is enough
+      // to run further.
+      DeadBlocks.insert(Dom.begin(), Dom.end());
+
+      // Figure out the dominance-frontier(D).
+      for (BasicBlock *B : Dom)
+        for (BasicBlock *S : successors(B))
+          if (!isDeadBlock(S) && !hasLiveIncomingEdges(S))
+            NewDead.push_back(S);
+    }
+  }
+
+  void addDeadEdge(const Use &DeadEdge) {
+    if (!DeadEdges.insert(&DeadEdge))
+      return;
+
+    BasicBlock *BB = cast_or_null<BasicBlock>(DeadEdge.get());
+    if (hasLiveIncomingEdges(BB))
+      return;
+
+    addDeadBlock(BB);
+  }
+};
+} // namespace
+
+static void Verify(const Function &F, const DominatorTree &DT,
+                   const CFGDeadness &CD);
 
 namespace {
+
 struct SafepointIRVerifier : public FunctionPass {
   static char ID; // Pass identification, replacement for typeid
-  DominatorTree DT;
   SafepointIRVerifier() : FunctionPass(ID) {
     initializeSafepointIRVerifierPass(*PassRegistry::getPassRegistry());
   }
 
   bool runOnFunction(Function &F) override {
-    DT.recalculate(F);
-    Verify(F, DT);
+    auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
+    CFGDeadness CD;
+    CD.processFunction(F, DT);
+    Verify(F, DT, CD);
     return false; // no modifications
   }
 
   void getAnalysisUsage(AnalysisUsage &AU) const override {
+    AU.addRequiredID(DominatorTreeWrapperPass::ID);
     AU.setPreservesAll();
   }
 
   StringRef getPassName() const override { return "safepoint verifier"; }
 };
 } // namespace
 
 void llvm::verifySafepointIR(Function &F) {
   SafepointIRVerifier pass;
   pass.runOnFunction(F);
 }
 
 char SafepointIRVerifier::ID = 0;
 
 FunctionPass *llvm::createSafepointIRVerifierPass() {
   return new SafepointIRVerifier();
 }
 
 INITIALIZE_PASS_BEGIN(SafepointIRVerifier, "verify-safepoint-ir",
-                      "Safepoint IR Verifier", false, true)
+                      "Safepoint IR Verifier", false, false)
+INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
 INITIALIZE_PASS_END(SafepointIRVerifier, "verify-safepoint-ir",
-                    "Safepoint IR Verifier", false, true)
+                    "Safepoint IR Verifier", false, false)
 
 static bool isGCPointerType(Type *T) {
   if (auto *PT = dyn_cast<PointerType>(T))
     // For the sake of this example GC, we arbitrarily pick addrspace(1) as our
     // GC managed heap.  We know that a pointer into this heap needs to be
     // updated and that no other pointer does.
     return (1 == PT->getAddressSpace());
   return false;

 
 namespace {
 class InstructionVerifier;
 
 /// Builds BasicBlockState for each BB of the function.
 /// It can traverse function for verification and provides all required
 /// information.
 ///
 /// GC pointer may be in one of three states: relocated, unrelocated and
 /// poisoned.
 /// Relocated pointer may be used without any restrictions.
 /// Unrelocated pointer cannot be dereferenced, passed as argument to any call
 /// or returned. Unrelocated pointer may be safely compared against another
 /// unrelocated pointer or against a pointer exclusively derived from null.
 /// Poisoned pointers are produced when we somehow derive pointer from relocated
 /// and unrelocated pointers (e.g. phi, select). This pointers may be safely
 /// used in a very limited number of situations. Currently the only way to use

 ///         /     |
 ///        /      |
 ///    bb2:       |
 ///    safepoint  |
 ///        \      |
 ///         \     |
 ///      bb3:
 ///      p2 = phi [p, bb2] [p1, bb1]
 ///      p3 = phi [p, bb2] [p, bb1]
 ///      here p and p1 is unrelocated
 ///           p2 and p3 is poisoned (though they shouldn't be)
 ///
 /// This leads to some weird results:
 ///      cmp eq p, p2 - illegal instruction (false-positive)
 ///      cmp eq p1, p2 - illegal instruction (false-positive)
 ///      cmp eq p, p3 - illegal instruction (false-positive)
 ///      cmp eq p, p1 - ok
 /// To fix this we need to introduce conception of generations and be able to
 /// check if two values belong to one generation or not. This way p2 will be
 /// considered to be unrelocated and no false alarm will happen.
 class GCPtrTracker {
   const Function &F;
+  const CFGDeadness &CD;
   SpecificBumpPtrAllocator<BasicBlockState> BSAllocator;
   DenseMap<const BasicBlock *, BasicBlockState *> BlockMap;
   // This set contains defs of unrelocated pointers that are proved to be legal
   // and don't need verification.
   DenseSet<const Instruction *> ValidUnrelocatedDefs;
   // This set contains poisoned defs. They can be safely ignored during
   // verification too.
   DenseSet<const Value *> PoisonedDefs;
 
 public:
-  GCPtrTracker(const Function &F, const DominatorTree &DT);
+  GCPtrTracker(const Function &F, const DominatorTree &DT,
+               const CFGDeadness &CD);
+
+  bool hasLiveIncomingEdge(const PHINode *PN, const BasicBlock *InBB) const {
+    return CD.hasLiveIncomingEdge(PN, InBB);
+  }
 
   BasicBlockState *getBasicBlockState(const BasicBlock *BB);
   const BasicBlockState *getBasicBlockState(const BasicBlock *BB) const;
 
   bool isValuePoisoned(const Value *V) const { return PoisonedDefs.count(V); }
 
   /// Traverse each BB of the function and call
   /// InstructionVerifier::verifyInstruction for each possibly invalid
   /// instruction.
   /// It destructively modifies GCPtrTracker so it's passed via rvalue reference
   /// in order to prohibit further usages of GCPtrTracker as it'll be in
   /// inconsistent state.
   static void verifyFunction(GCPtrTracker &&Tracker,
                              InstructionVerifier &Verifier);
 
-  /// Returns true for reachable blocks that are verified, the other blocks are
-  /// ignored.
+  /// Returns true for reachable and live blocks.
   bool isMapped(const BasicBlock *BB) const {
     return BlockMap.find(BB) != BlockMap.end();
   }
 
 private:
   /// Returns true if the instruction may be safely skipped during verification.
   bool instructionMayBeSkipped(const Instruction *I) const;
 
public:
 
   bool hasAnyInvalidUses() const { return AnyInvalidUses; }
 
 private:
   void reportInvalidUse(const Value &V, const Instruction &I);
 };
 } // end anonymous namespace
 
-GCPtrTracker::GCPtrTracker(const Function &F, const DominatorTree &DT) : F(F) {
-  // First, calculate Contribution of each BB.
+GCPtrTracker::GCPtrTracker(const Function &F, const DominatorTree &DT,
+                           const CFGDeadness &CD) : F(F), CD(CD) {
+  // Calculate Contribution of each live BB.
+  // Allocate BB states for live blocks.
   for (const BasicBlock &BB : F)
-    if (DT.isReachableFromEntry(&BB)) {
+    if (!CD.isDeadBlock(&BB)) {
       BasicBlockState *BBS = new (BSAllocator.Allocate()) BasicBlockState;
       for (const auto &I : BB)
         transferInstruction(I, BBS->Cleared, BBS->Contribution);
       BlockMap[&BB] = BBS;
     }
 
   // Initialize AvailableIn/Out sets of each BB using only information about
   // dominating BBs.
   for (auto &BBI : BlockMap) {
     gatherDominatingDefs(BBI.first, BBI.second->AvailableIn, DT);
     transferBlock(BBI.first, *BBI.second, true);
   }
 
   // Simulate the flow of defs through the CFG and recalculate AvailableIn/Out
   // sets of each BB until it converges. If any def is proved to be an
   // unrelocated pointer, it will be removed from all BBSs.
   recalculateBBsStates();
 }
 
 BasicBlockState *GCPtrTracker::getBasicBlockState(const BasicBlock *BB) {
   auto it = BlockMap.find(BB);
-  assert(it != BlockMap.end() &&
-         "No such BB in BlockMap! Probably BB from another function");
-  return it->second;
+  return it != BlockMap.end() ? it->second : nullptr;
 }
 
 const BasicBlockState *GCPtrTracker::getBasicBlockState(
     const BasicBlock *BB) const {
   return const_cast<GCPtrTracker *>(this)->getBasicBlockState(BB);
 }
 
 bool GCPtrTracker::instructionMayBeSkipped(const Instruction *I) const {
   // Poisoned defs are skipped since they are always safe by itself by
   // definition (for details see comment to this class).
   return ValidUnrelocatedDefs.count(I) || PoisonedDefs.count(I);
 }
 
 void GCPtrTracker::verifyFunction(GCPtrTracker &&Tracker,
                                   InstructionVerifier &Verifier) {
   // We need RPO here to a) report always the first error b) report errors in
   // same order from run to run.
   ReversePostOrderTraversal<const Function *> RPOT(&Tracker.F);
   for (const BasicBlock *BB : RPOT) {
     BasicBlockState *BBS = Tracker.getBasicBlockState(BB);
+    if (!BBS)
+      continue;
+
     // We destructively modify AvailableIn as we traverse the block instruction
     // by instruction.
     AvailableValueSet &AvailableSet = BBS->AvailableIn;
     for (const Instruction &I : *BB) {
       if (Tracker.instructionMayBeSkipped(&I))
         continue; // This instruction shouldn't be added to AvailableSet.
 
       Verifier.verifyInstruction(&Tracker, I, AvailableSet);
void GCPtrTracker::recalculateBBsStates() {
   // queue where priority is RPO number of BB.
   for (auto &BBI : BlockMap)
     Worklist.insert(BBI.first);
 
   // This loop iterates the AvailableIn/Out sets until it converges.
   // The AvailableIn and AvailableOut sets decrease as we iterate.
   while (!Worklist.empty()) {
     const BasicBlock *BB = Worklist.pop_back_val();
-    BasicBlockState *BBS = BlockMap[BB];
+    BasicBlockState *BBS = getBasicBlockState(BB);
+    if (!BBS)
+      continue; // Ignore dead successors.
 
     size_t OldInCount = BBS->AvailableIn.size();
-    for (const BasicBlock *PBB : predecessors(BB))
-      if (isMapped(PBB))
-        set_intersect(BBS->AvailableIn, BlockMap[PBB]->AvailableOut);
+    for (const_pred_iterator PredIt(BB), End(BB, true); PredIt != End; ++PredIt) {
+      const BasicBlock *PBB = *PredIt;
+      BasicBlockState *PBBS = getBasicBlockState(PBB);
+      if (PBBS && !CD.isDeadEdge(&CFGDeadness::getEdge(PredIt)))
+        set_intersect(BBS->AvailableIn, PBBS->AvailableOut);
+    }
 
     assert(OldInCount >= BBS->AvailableIn.size() && "invariant!");
 
     bool InputsChanged = OldInCount != BBS->AvailableIn.size();
     bool ContributionChanged =
         removeValidUnrelocatedDefs(BB, BBS, BBS->Contribution);
     if (!InputsChanged && !ContributionChanged)
       continue;
for (const Instruction &I : *BB) {
     // TODO: `select` instructions should be handled here too.
     if (const PHINode *PN = dyn_cast<PHINode>(&I)) {
       if (containsGCPtrType(PN->getType())) {
         // If both is true, output is poisoned.
         bool HasRelocatedInputs = false;
         bool HasUnrelocatedInputs = false;
         for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
           const BasicBlock *InBB = PN->getIncomingBlock(i);
-          if (!isMapped(InBB))
-              continue;
+          if (!isMapped(InBB) ||
+              !CD.hasLiveIncomingEdge(PN, InBB))
+            continue; // Skip dead block or dead edge.
+
           const Value *InValue = PN->getIncomingValue(i);
 
           if (isNotExclusivelyConstantDerived(InValue)) {
             if (isValuePoisoned(InValue)) {
               // If any of inputs is poisoned, output is always poisoned too.
               HasRelocatedInputs = true;
               HasUnrelocatedInputs = true;
               break;

 void GCPtrTracker::gatherDominatingDefs(const BasicBlock *BB,
                                         AvailableValueSet &Result,
                                         const DominatorTree &DT) {
   DomTreeNode *DTN = DT[const_cast<BasicBlock *>(BB)];
 
   assert(DTN && "Unreachable blocks are ignored");
   while (DTN->getIDom()) {
     DTN = DTN->getIDom();
-    const auto &Defs = BlockMap[DTN->getBlock()]->Contribution;
+    auto BBS = getBasicBlockState(DTN->getBlock());
+    assert(BBS && "immediate dominator cannot be dead for a live block");
+    const auto &Defs = BBS->Contribution;
     Result.insert(Defs.begin(), Defs.end());
     // If this block is 'Cleared', then nothing LiveIn to this block can be
     // available after this block completes.  Note: This turns out to be
     // really important for reducing memory consuption of the initial available
     // sets and thus peak memory usage by this verifier.
-    if (BlockMap[DTN->getBlock()]->Cleared)
+    if (BBS->Cleared)
       return;
   }
 
   for (const Argument &A : BB->getParent()->args())
     if (containsGCPtrType(A.getType()))
       Result.insert(&A);
 }
 

 
 void InstructionVerifier::verifyInstruction(
     const GCPtrTracker *Tracker, const Instruction &I,
     const AvailableValueSet &AvailableSet) {
   if (const PHINode *PN = dyn_cast<PHINode>(&I)) {
     if (containsGCPtrType(PN->getType()))
       for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
         const BasicBlock *InBB = PN->getIncomingBlock(i);
-        if (!Tracker->isMapped(InBB))
-            continue;
+        const BasicBlockState *InBBS = Tracker->getBasicBlockState(InBB);
+        if (!InBBS ||
+            !Tracker->hasLiveIncomingEdge(PN, InBB))
+          continue; // Skip dead block or dead edge.
+
         const Value *InValue = PN->getIncomingValue(i);
 
         if (isNotExclusivelyConstantDerived(InValue) &&
-            !Tracker->getBasicBlockState(InBB)->AvailableOut.count(InValue))
+            !InBBS->AvailableOut.count(InValue))
           reportInvalidUse(*InValue, *PN);
       }
   } else if (isa<CmpInst>(I) &&
              containsGCPtrType(I.getOperand(0)->getType())) {
     Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
     enum BaseType baseTyLHS = getBaseType(LHS),
                   baseTyRHS = getBaseType(RHS);
 
void InstructionVerifier::reportInvalidUse(const Value &V,
   errs() << "Illegal use of unrelocated value found!\n";
   errs() << "Def: " << V << "\n";
   errs() << "Use: " << I << "\n";
   if (!PrintOnly)
     abort();
   AnyInvalidUses = true;
 }
 
-static void Verify(const Function &F, const DominatorTree &DT) {
+static void Verify(const Function &F, const DominatorTree &DT,
+                   const CFGDeadness &CD) {
   LLVM_DEBUG(dbgs() << "Verifying gc pointers in function: " << F.getName()
                     << "\n");
   if (PrintOnly)
     dbgs() << "Verifying gc pointers in function: " << F.getName() << "\n";
 
-  GCPtrTracker Tracker(F, DT);
+  GCPtrTracker Tracker(F, DT, CD);
 
   // We now have all the information we need to decide if the use of a heap
   // reference is legal or not, given our safepoint semantics.
 
   InstructionVerifier Verifier;
   GCPtrTracker::verifyFunction(std::move(Tracker), Verifier);
 
   if (PrintOnly && !Verifier.hasAnyInvalidUses()) {
     dbgs() << "No illegal uses found by SafepointIRVerifier in: " << F.getName()
            << "\n";
   }
 }

test/SafepointIRVerifier/dead-block-tolerant.ll

+; RUN: opt -safepoint-ir-verifier-print-only -verify-safepoint-ir -S %s 2>&1 | FileCheck %s
+
+%jObject = type { [8 x i8] }
+declare %jObject addrspace(1)* @llvm.experimental.gc.relocate.p1jObject(token, i32, i32) nounwind
+declare token @llvm.experimental.gc.statepoint.p0f_f64f64f(i64, i32, double (double)*, i32, i32, ...)
+declare token @llvm.experimental.gc.statepoint.p0f_isVoidf(i64, i32, void ()*, i32, i32, ...)
+
+; This test checks that dead branch (left) does not conflict with live branch (right).
+define void @test2(i8 addrspace(1)* %arg, i1 %cond) gc "statepoint-example" {
+; CHECK-LABEL: Verifying gc pointers in function: test2
+; CHECK: No illegal uses found by SafepointIRVerifier in: test2
+ begin:
+  %ptr = getelementptr i8, i8 addrspace(1)* %arg, i64 4
+  br i1 true, label %right, label %left
+
+ left:
+  %safepoint_token = call token (i64, i32, void ()*, i32, i32, ...) @llvm.experimental.gc.statepoint.p0f_isVoidf(i64 0, i32 0, void ()* undef, i32 0, i32 0, i32 0, i32 5, i32 0, i32 -1, i32 0, i32 0, i32 0)
+  br label %merge
+
+ right:
+  br label %merge
+
+ merge:
+  %val.unrelocated = phi i8 addrspace(1)* [ %arg, %left ], [ %ptr, %right ]
+  %c = icmp eq i8 addrspace(1)* %val.unrelocated, %arg
+  ret void
+}
+
+; This test checks that dead branch (right) does not conflict with live branch (left).
+define void @test3(i8 addrspace(1)* %arg, i1 %cond) gc "statepoint-example" {
+; CHECK-LABEL: Verifying gc pointers in function: test3
+; CHECK: No illegal uses found by SafepointIRVerifier in: test3
+ begin:
+  %ptr = getelementptr i8, i8 addrspace(1)* %arg, i64 4
+  br i1 false, label %right, label %left
+
+ left:
+  %safepoint_token = call token (i64, i32, void ()*, i32, i32, ...) @llvm.experimental.gc.statepoint.p0f_isVoidf(i64 0, i32 0, void ()* undef, i32 0, i32 0, i32 0, i32 5, i32 0, i32 -1, i32 0, i32 0, i32 0)
+  br label %merge
+
+ right:
+  br label %merge
+
+ merge:
+  %val.unrelocated = phi i8 addrspace(1)* [ %arg, %left ], [ %ptr, %right ]
+  %c = icmp eq i8 addrspace(1)* %val.unrelocated, %arg
+  ret void
+}
+
+; This test checks that two dead branches (left and right) do not conflict.
+define void @test4(i8 addrspace(1)* %arg, i1 %cond) gc "statepoint-example" {
+; CHECK-LABEL: Verifying gc pointers in function: test4
+; CHECK: No illegal uses found by SafepointIRVerifier in: test4
+ begin:
+  %ptr = getelementptr i8, i8 addrspace(1)* %arg, i64 4
+  br i1 true, label %next, label %right
+
+ next:
+  %safepoint_token0 = call token (i64, i32, void ()*, i32, i32, ...) @llvm.experimental.gc.statepoint.p0f_isVoidf(i64 0, i32 0, void ()* undef, i32 0, i32 0, i32 0, i32 5, i32 0, i32 -1, i32 0, i32 0, i32 0)
+  br i1 false, label %left, label %merge
+
+ left:
+  %safepoint_token1 = call token (i64, i32, void ()*, i32, i32, ...) @llvm.experimental.gc.statepoint.p0f_isVoidf(i64 0, i32 0, void ()* undef, i32 0, i32 0, i32 0, i32 5, i32 0, i32 -1, i32 0, i32 0, i32 0)
+  br label %merge
+
+ right:
+  br label %merge
+
+ merge:
+  %val.unrelocated = phi i8 addrspace(1)* [ %arg, %left ], [ %ptr, %right ], [ %arg, %next ]
+  %c = icmp eq i8 addrspace(1)* %val.unrelocated, %arg
+  ret void
+}
+
+; This test checks that two live branches (left and right) conflict.
+define void @test5(i8 addrspace(1)* %arg, i1 %cond) gc "statepoint-example" {
+; CHECK-LABEL: Verifying gc pointers in function: test5
+; CHECK-NOT: No illegal uses found by SafepointIRVerifier in: test5
+ begin:
+  %ptr = getelementptr i8, i8 addrspace(1)* %arg, i64 4
+  br i1 %cond, label %left, label %right
+
+ left:
+  %safepoint_token = call token (i64, i32, void ()*, i32, i32, ...) @llvm.experimental.gc.statepoint.p0f_isVoidf(i64 0, i32 0, void ()* undef, i32 0, i32 0, i32 0, i32 5, i32 0, i32 -1, i32 0, i32 0, i32 0)
+  br label %merge
+
+ right:
+  br label %merge
+
+ merge:
+  %val.unrelocated = phi i8 addrspace(1)* [ %arg, %left ], [ %ptr, %right ]
+  %c = icmp eq i8 addrspace(1)* %val.unrelocated, %arg
+  ret void
+}
+
+; This test checks that two live blocks do not conflict if one (right) is connected
+; with a critical dead edge.
+define void @test6(i8 addrspace(1)* %arg, i1 %cond) gc "statepoint-example" {
+; CHECK-LABEL: Verifying gc pointers in function: test6
+; CHECK: No illegal uses found by SafepointIRVerifier in: test6
+ begin:
+  %ptr = getelementptr i8, i8 addrspace(1)* %arg, i64 4
+  br i1 %cond, label %left, label %right
+
+ left:
+  %safepoint_token = call token (i64, i32, void ()*, i32, i32, ...) @llvm.experimental.gc.statepoint.p0f_isVoidf(i64 0, i32 0, void ()* undef, i32 0, i32 0, i32 0, i32 5, i32 0, i32 -1, i32 0, i32 0, i32 0)
+  br label %merge
+
+ right:
+  br i1 false, label %merge, label %exit
+
+ merge:
+  %val.unrelocated = phi i8 addrspace(1)* [ %arg, %left ], [ %ptr, %right ]
+  %c = icmp eq i8 addrspace(1)* %val.unrelocated, %arg
+  ret void
+
+ exit:
+  ret void
+}
+
+; This test checks that two live blocks do not conflict if one (right) is connected
+; with a critical dead edge right->merge. 
+define void @test7(i8 addrspace(1)* %arg, i1 %cond) gc "statepoint-example" {
+; CHECK-LABEL: Verifying gc pointers in function: test7
+; CHECK: No illegal uses found by SafepointIRVerifier in: test7
+ begin:
+  %ptr = getelementptr i8, i8 addrspace(1)* %arg, i64 4
+  br i1 %cond, label %merge, label %right
+
+ right:
+  %safepoint_token = call token (i64, i32, void ()*, i32, i32, ...) @llvm.experimental.gc.statepoint.p0f_isVoidf(i64 0, i32 0, void ()* undef, i32 0, i32 0, i32 0, i32 5, i32 0, i32 -1, i32 0, i32 0, i32 0)
+  br i1 false, label %merge, label %exit
+
+ merge:
+  %val.unrelocated = phi i8 addrspace(1)* [ %arg, %begin ], [ %ptr, %right ]
+  %c = icmp eq i8 addrspace(1)* %val.unrelocated, %arg
+  ret void
+
+ exit:
+  ret void
+}