SafepointIRVerifier is made unreachable block tolerant

[yrouban]

Summary

SafepointIRVerifier crashed while traversing blocks without a DomTreeNode.
This could happen with a custom pipeline or when some optional passes were skipped by OptBisect.

SafepointIRVerifier is fixed to traverse basic blocks that are reachable from entry. Test are added.

[reames]

LGTM

[DaniilSuchkov]

Without this patch following code leads to a crash

entry:
ptr = getPtr()
br exit

unreachable_bb:
ptr2 = getPtr()
br exit

exit:
p = phi [ptr, entry], [ptr2, unreachable_bb]
v = load p
ret v

But with your patch it's a false-positive. Verifier will report invalid use of poisoned value p here (since unreachable_bb isn't processed and thus ptr2 isn't in its AvailableOut set).
Could you please leave a FIXME about it?

[yrouban]

Good catch Daniil! SafepointIRVerifier crashes with your case. I will improve the patch and add a test.

[yrouban]

considered a case with unreachable blocks connected to reachable ones

[yrouban]

LLVM committers, can you integrate this patch, please?

lib/IR/SafepointIRVerifier.cpp

public:
   /// 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.
+  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;
 
   /// Iterates over all BBs from BlockMap and recalculates AvailableIn/Out for
   /// each of them until it converges.
   void recalculateBBsStates();
 

 
 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.
-  for (const BasicBlock &BB : F) {
+  for (const BasicBlock &BB : F)
+    if (DT.isReachableFromEntry(&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);
   }
 
void GCPtrTracker::recalculateBBsStates() {
   // 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];
 
     size_t OldInCount = BBS->AvailableIn.size();
     for (const BasicBlock *PBB : predecessors(BB))
+      if (isMapped(PBB))
         set_intersect(BBS->AvailableIn, BlockMap[PBB]->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;
           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;
bool GCPtrTracker::removeValidUnrelocatedDefs(const BasicBlock *BB,
   return ContributionChanged;
 }
 
 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;
     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.

 
 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 Value *InValue = PN->getIncomingValue(i);
 
         if (isNotExclusivelyConstantDerived(InValue) &&
             !Tracker->getBasicBlockState(InBB)->AvailableOut.count(InValue))
           reportInvalidUse(*InValue, *PN);
       }
   } else if (isa<CmpInst>(I) &&
              containsGCPtrType(I.getOperand(0)->getType())) {

test/SafepointIRVerifier/unreachable-block-tolerant.ll

+; RUN: opt -safepoint-ir-verifier-print-only -verify-safepoint-ir -S %s 2>&1 | FileCheck %s
+
+; This test checks that StatepointIRVerifier does not crash on
+; a CFG with unreachable blocks.
+
+%jObject = type { [8 x i8] }
+
+define %jObject addrspace(1)* @test(%jObject addrspace(1)* %arg) gc "statepoint-example" {
+; CHECK-LABEL: Verifying gc pointers in function: test
+; CHECK-NEXT:  No illegal uses found by SafepointIRVerifier in: test
+  %safepoint_token3 = tail call token (i64, i32, double (double)*, i32, i32, ...) @llvm.experimental.gc.statepoint.p0f_f64f64f(i64 0, i32 0, double (double)* undef, i32 1, i32 0, double undef, i32 0, i32 5, i32 0, i32 -1, i32 0, i32 0, i32 0, %jObject addrspace(1)* %arg)
+  %arg2.relocated4 = call coldcc %jObject addrspace(1)* @llvm.experimental.gc.relocate.p1jObject(token %safepoint_token3, i32 13, i32 13)
+  ret %jObject addrspace(1)* %arg2.relocated4
+
+unreachable:
+  ret %jObject addrspace(1)* null
+}
+
+; Function Attrs: nounwind
+declare %jObject addrspace(1)* @llvm.experimental.gc.relocate.p1jObject(token, i32, i32) #3
+
+declare token @llvm.experimental.gc.statepoint.p0f_f64f64f(i64, i32, double (double)*, i32, i32, ...)
+
+; In %merge %val.unrelocated, %ptr and %arg should be unrelocated.
+define void @test2(i8 addrspace(1)* %arg) gc "statepoint-example" {
+; CHECK-LABEL: Verifying gc pointers in function: test2
+; CHECK: No illegal uses found by SafepointIRVerifier in: test2
+ bci_0:
+  %ptr = getelementptr i8, i8 addrspace(1)* %arg, i64 4
+  br 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
+}
+
+declare token @llvm.experimental.gc.statepoint.p0f_isVoidf(i64, i32, void ()*, i32, i32, ...)