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

242

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.

282

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

302

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

242

@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

242

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

242

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

 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/PostOrderIterator.h"
 #include "llvm/ADT/SetOperations.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/IR/BasicBlock.h"
+#include "llvm/IR/Constants.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/Intrinsics.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/Value.h"
 #include "llvm/IR/SafepointIRVerifier.h"

 
 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;
   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);
 
   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:
   void verifyInstruction(const GCPtrTracker *Tracker, const Instruction &I,
                          const AvailableValueSet &AvailableSet);
 
   bool hasAnyInvalidUses() const { return AnyInvalidUses; }
 
 private:
   void reportInvalidUse(const Value &V, const Instruction &I);
 };
+
+/// It is a dead block calculator used by SafepointIRVerifier to ignore dead
+/// blocks. Algorithm starts with a given block set and propagates deadness
+/// using foldable conditional branches like GVN does but without splitting
+/// critical edges. So the CFG is kept intact.
+class DeadBlocks : public SetVector<const BasicBlock *> {
+  const DominatorTree &DT;
+  SetVector<const Use *> DeadEdges; // incomplete at the end
+
+public:
+  DeadBlocks(const DominatorTree &DT) : DT(DT) {  }
+
+  bool isDeadBlock(const BasicBlock *BB) {
+    return count(BB);
+  }
+
+  bool isDeadEdge(const Use *U) {
+    return DeadEdges.count(U);
+  }
+
+  bool hasLiveIncomingEdges(const BasicBlock *BB) {
+    // Check if all incoming edges are dead.
+    using pred_iterator = PredIterator<const BasicBlock, Value::const_user_iterator>;
+    for (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 addDeadEdge(const Use &DeadEdge) {
+    if (!DeadEdges.insert(&DeadEdge))
+      return;
+
+    BasicBlock *BB = cast_or_null<BasicBlock>(DeadEdge.get());
+    if (hasLiveIncomingEdges(BB))
+      return;
+
+    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.
+      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 processFoldableCondBr(const BranchInst *BI) {
+    if (!BI || BI->isUnconditional())
+      return;
+
+    // If a branch has two identical successors, we cannot declare either dead.
+    if (BI->getSuccessor(0) == BI->getSuccessor(1))
+      return;
+
+    ConstantInt *Cond = dyn_cast<ConstantInt>(BI->getCondition());
+    if (!Cond)
+      return;
+
+    addDeadEdge(BI->getOperandUse(Cond->getZExtValue() ? 1 : 2));
+  }
+
+  void processInstruction(const Instruction *I) {
+    // For conditional branches, we can perform simple conditional propagation on
+    // the condition value itself.
+    const BranchInst *BI = dyn_cast<BranchInst>(I);
+    if (!BI || !BI->isConditional() || !isa<Constant>(BI->getCondition()))
+        return;
+
+    processFoldableCondBr(BI);
+  }
+
+  void processFunction(const Function &F) {
+    // Top-down walk of the dominator tree
+    ReversePostOrderTraversal<const Function *> RPOT(&F);
+    for (const BasicBlock *BB : RPOT)
+      for (auto &BI : *BB)
+        processInstruction(&BI);
+  }
+};
 } // end anonymous namespace
 
 GCPtrTracker::GCPtrTracker(const Function &F, const DominatorTree &DT) : F(F) {
-  // First, calculate Contribution of each BB.
+  // Find dead and unreachable blocks to exclude them from verification.
+  DeadBlocks DB(DT);
+  for (const BasicBlock &BB : F)
+    if (!DT.isReachableFromEntry(&BB))
+      DB.insert(&BB);
+
+  DB.processFunction(F);
+
+  // Calculate Contribution of each live BB.
+  // Allocate BB states for live blocks.
   for (const BasicBlock &BB : F)
-    if (DT.isReachableFromEntry(&BB)) {
+    if (!DB.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);
 
     assert(OldInCount >= BBS->AvailableIn.size() && "invariant!");
 

 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)
+          continue; // Skip dead block.
         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);
 

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
+}