[SafepointIRVerifier] Allow non-dereferencing uses of unrelocated or poisoned PHI nodes

[DaniilSuchkov]

Summary

PHI that has at least one unrelocated input cannot cause any issues by itself,
though its uses should be carefully verified. With this patch PHIs are allowed
to have any inputs but when all inputs are unrelocated the PHI is marked as
unrelocated and if not all inputs are unrelocated then the PHI is marked as
poisoned. Poisoned pointers can be used only in three ways: to derive new
pointers, in PHIs or in comparisons against constants that are exclusively
derived from null.

[mkazantsev]

lib/IR/SafepointIRVerifier.cpp

246

Please clarify what is "a pointer derived from null". For example, is select %cond, null, %some derived from null? I think what you mean here is something like "... or against a constant pointer".

247

How about "poisoned value is a value which is derived from both relocated and unrelocated values, or from another poisoned values"?

250

You can always represent any constant pointer as gep null, %some_int_constant, so I think that this "exclusively derived from null" stuff is redundant.

255

You can merge that free into P + Any = P if it makes sense.

260

Maybe instead of using the term "merge pointers" stick to the term "derived pointer"? You use both, and I don't catch what is the difference between them.

261

Maybe "A pointer derived from X and constant has the same type as X"? You could also include it into the rules above.

300

as long as they are only used in safe instructions

532

How about "Removing unrelocated" << I...

and below, "Removing poisoned " << I?

664

"exclusively derived null pointer" -> "constant pointer"?

[DaniilSuchkov]

lib/IR/SafepointIRVerifier.cpp

246

Actually I've missed one word. It should be "derived _exclusively_ from null".

247

It's about origination of poisoned values.

250

It refers to comment at line 639.

255

I'd like to keep it this way.

260

By "deriving" I mean f(x) -> x, and by merge f(x1, ..., xN) -> x.

300

The idea is "_This_ instructions don't need verification. But nothing is said about their uses."

532

It was intentional but I can't remember the reason so I'll fix it.

664

Not all constant pointers are derived from null but anyway you spotted a typo, thank you.

[mkazantsev]

lib/IR/SafepointIRVerifier.cpp

247

Even if it was like that, it has nothing to do with the rules below, since you don't explain where rules 2-4 come from. You only define how poison first appears from merging of U and R, but don't say how it's handled after that.

250

I'm not asking to do something about it in this patch since it was there before, but it is fishy. If I can imagine a VM in which 0xFF is some special magical pointer that cannot be simply compared against normal pointers, then I can also imagine a VM where gep null, 0xFF is also some special magical pointer with same properties. Actually, I can define all such special numbers as derivatives from null.

From that perspective, how hard-coded constants are different from hard-coded offsets from null?

260

I guess "deriving" is actually f(x1) -> x. And what you call "deriving" is just a particular case of "merging". Again, why do we need both?

300

Ok, makes sense.

[DaniilSuchkov]

Comments slightly clarified.

lib/IR/SafepointIRVerifier.cpp

247

This part is supposed to be a brief description. How it's handled is described bellow.

250

I don't know either, but the idea is to keep this patch consistent with previous code. So I have to maintain the logic around "magic pointer constant". This patch is not about that issue, let's discuss it later.

260

Because for deriving there is only one rule: it changes nothing and for merge everything is a bit more complicated. Both "gep/bitcast is merge" and "phi/select is deriving" looks misleading.

I agree that formally f(x1) -> x is a particular case of f(x1, ..., xN) -> x, but how to name it so that it won't be confusing?

[anna]

lib/IR/SafepointIRVerifier.cpp

250

I'll try to clarify this. The GC relocates the *base* pointer and this is why we record the base pointer for every 'derived pointer'. After the GC relocates the base pointer at runtime, we can rematerialize the derived pointer because we have stored this information in the IR.

So, effectively it comes down to always identifying the "base" of a derived pointer. This is where the getBaseType comes in.
When we generate "magic const pointers" in IR (for example, using inttoptr magic const), the base here is that magic const.
The same idiom is GEP(null, magic const), but here the base pointer is null. Relocating a null is still a null.

So, this is why we have something like this:

%ptr = unrelocated non constant pointer
 compare (%ptr, inttoptr(magic_const)) <-- can't be reordered before a safepoint
but:
compare(%ptr, GEP(null, magic_const)) <-- can be reordered before a safepoint

Also, just as an aside, this is also why inttoptr of addrspace(1) is incorrect in the IRVerifier, but GEP(null, offset) in addrspace(1) is fine.

[anna]

Comments inline.

lib/IR/SafepointIRVerifier.cpp

242

I don't think we want to introduce one more term 'poisoned' here. Specifically, poisoning has different meanings in the optimizer (and sometimes in the GC), and can be confusing.
It looks like poisoned pointers are just derived pointers which will be *lexically* from multiple pointers. So something like:
gep, bitcasts -> derived pointer from one base
phis, selects -> derived pointers that are lexically from multiple base pointers (I say lexically, because we can have phis/selects that statically have derived from exactly one pointer).

Do we really need to make this distinction? I think it's more confusing. Pls see comment below on naming to make clearer.

260

I tend to agree with Max here. We really cannot distinguish between both.
How about we focus just on the fact that we have multiple sources here? IOW, don't worry about GEPs and bitcasts because they have single source base.
These GEPs and bitcasts don't change the behaviour of unrelocated/relocated, so they shouldn;t affect this discusson.

262

As mentioned, I dont think you need to explicitly state out the distinction here. Just maybe a single line at the beginning when explaining MultiSourceDerivedPtr (I prefer that instead of Poisoned naming), because we can have multiple sources and still not be poisoned.

267

Nit: predecessor

279

This is incorrect IR. We cannot have multiple *different* incoming phi values from exactly one predecessor.
With correct IR, I don't think we will have such false positives. If we do have, could you please add a test with FIXME?

[mkazantsev]

lib/IR/SafepointIRVerifier.cpp

242

Yes, this may be confusing with poisoned pointers that are also in GC. I don't have a better idea for its name on top of my head, though. I'm OK to go with whatever you agree with.

250

Ok, this makes sense to me.

260

I think that "deriving" is a good name for both, because formally you apply some function f (where f can be gep, phi, bitcast or whatever) to a number of pointer arguments and have a new pointer (derived one) as result. It is unimportant -how- exactly you derived your pointer from your argument(s). You never fail verification while deriving. You can only fail verification when you misuse the derived pointer. And this is the important part.

279

I don't get why it is incorrect. For example,

void *p = &a[10];
void *p1 = &p[20];
void *temp = p;
if (cond) {
  temp = p1;
  some_call();
}
void *p2 = temp;

Won't we have exactly this IR here?

[anna]

lib/IR/SafepointIRVerifier.cpp

279

yup, you're right. What we have is different incoming values from different incoming blocks, something like: p2 = phi [p, def BB of p], [p1, safepoint block]
What's incorrect is, different incoming values from the same block. For example, p and p1 from their same def block: p2 = phi [p, def BB of p] [p1, def BB of p1].

[DaniilSuchkov]

lib/IR/SafepointIRVerifier.cpp

262

We don't need MultiSourceDerivedPtr because we don't care at all from how many sources a value was derived, but we do care if all sources were (un)relocated or not. Value which was derived from multiple sources can be in any of three possible states (relocated, unrelocated, poisoned).

279

To avoid confusion I'll make this comment a bit more clear.

[DaniilSuchkov]

"merge" now replaced with "derive" in comments, example in FIXME become a bit less confusing, added new test (with XFAIL) for that FIXME.

[anna]

Logic looks right, some comments inline.

lib/IR/SafepointIRVerifier.cpp

408

Pls add a comment here on why the poisoned defs are skipped. ValidUnrelocatedDefs are obvious.

480

Don't we need to handle selects and identify poisoned versus unrelocated?

490

Instead of the below code (logic is right, but too many conditionals), could we do something like this:

if (isNotExclusivelyConstantDerived(InValue)) {
  if (isValuePoisoned(InValue) || (HasRelocatedInputs &&  HasUnrelocatedInputs)) {
     PoisonedPointerDef = true;
     break;
   }
   if (BlockMap[InBB]->AvailableOut.count(InValue))
              HasRelocatedInputs = true;
    else
              HasUnrelocatedInputs = true;
}
if (!PoisonedPointerDef && HasUnrelocatedInputs) {
   assert(!HasRelocatedInputs && "Should be poisoned!");
   ValidUnrelocatedPointerDef = true;
}

[DaniilSuchkov]

lib/IR/SafepointIRVerifier.cpp

408

You think I should repeat myself here? From comments above (where 'poisoned' pointers are introduced) it's clear why this defs are skipped.

480

I'll do it in the next patch (in order to keep this one not too huge).

490

But we still have to handle case when some inputs are relocated and some are not: your code won't work if the _last_ input makes this phi poisoned (because on each iteration it checks flags that might have changed on previous one). Thus we cannot remove this part:

if (HasUnrelocatedInputs) {
  if (HasRelocatedInputs)
    PoisonedPointerDef = true;
  else
    ValidUnrelocatedPointerDef = true;
}

So the only thing that might be changed is this part:

if (isValuePoisoned(InValue)) {
  // If any of inputs is poisoned, output is always poisoned too.
  HasRelocatedInputs = true;
  HasUnrelocatedInputs = true;
  break;
}

But if we'll change it to

if (isValuePoisoned(InValue)) {
  // If any of inputs is poisoned, output is always poisoned too.
  PoisonedPointerDef = true;
  break;
}

We'll have to somehow tell that if (mentioned before) not to touch this flag and it'll be even worse.
And that assert shouldn't be moved to PHI's branch, it's about all instructions.

Currently this part is pretty clear and straightforward: loop over phi's inputs sets two flags (that have clear meaning) and after that loop another two flags are changed accordingly.

[anna]

lgtm w/ comment addressed.

lib/IR/SafepointIRVerifier.cpp

408

Are all poisoned defs removed? Only valid ones right.

480

pls add a TODO then.

490

ah yes, it wont work for the last case.

[anna]

lib/IR/SafepointIRVerifier.cpp

490

also, pls point out as a comment where these rules come from (i.e. refer to header for reasoning of these rules).

[DaniilSuchkov]

Added some new comments.

lib/IR/SafepointIRVerifier.cpp

 }
 
 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 derived from null.
+/// Poisoned pointers are produced when we somehow merge 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 it is
+/// comparison against constant exclusively derived from null. All limitations
+/// arise due to its undefined state: this pointers should be treated as
+/// relocated and unrelocated simultaneously.
+/// Merge rules:
+/// R + U = P - that's where the poison comes from
+/// P + P = P
+/// P + U = P
+/// P + R = P
+/// U + U = U
+/// R + R = R
+/// Where "+" - any operation that somehow merge pointers, U - unrelocated,
+/// R - relocated and P - poisoned. Merge with constant doesn't change anything.
+/// Merge of pointers by itself is always safe, deriving one pointer from
+/// another is always safe too. Derived pointer always has the same state as its
+/// base.
+/// NOTE: when we are making decision on the status of instruction's result:
+/// a) for phi we need to check status of each input *at the end of
+///    corresponding predicessor BB*.
+/// b) for other instructions we need to check status of each input *at the
+///    current point*.
+///
+/// FIXME: This works fairly well except one case
+///     p = *some GC-ptr def*
+///     p1 = gep p, offset
+///         /     |
+///        /      |
+///    safepoint  |
+///        \      |
+///         \     |
+///      p2 = phi [p] [p1]
+///      p3 = phi [p] [p]
+///      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);
BasicBlockState *GCPtrTracker::getBasicBlockState(const BasicBlock *BB) {
   return it->second;
 }
 
 const BasicBlockState *GCPtrTracker::getBasicBlockState(
     const BasicBlock *BB) const {
   return const_cast<GCPtrTracker *>(this)->getBasicBlockState(BB);
 }
 
 bool GCPtrTracker::instructionMayBeSkipped(const Instruction *I) const {
-  return ValidUnrelocatedDefs.count(I);
+  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) {

 bool GCPtrTracker::removeValidUnrelocatedDefs(const BasicBlock *BB,
                                               const BasicBlockState *BBS,
                                               AvailableValueSet &Contribution) {
   assert(&BBS->Contribution == &Contribution &&
          "Passed Contribution should be from the passed BasicBlockState!");
   AvailableValueSet AvailableSet = BBS->AvailableIn;
   bool ContributionChanged = false;
   for (const Instruction &I : *BB) {
-    bool ProducesUnrelocatedPointer = false;
-    if ((isa<GetElementPtrInst>(I) || isa<BitCastInst>(I)) &&
+    bool ValidUnrelocatedPointerDef = false;
+    bool PoisonedPointerDef = false;
+    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);
+          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;
+            }
+            if (BlockMap[InBB]->AvailableOut.count(InValue))
+              HasRelocatedInputs = true;
+            else
+              HasUnrelocatedInputs = true;
+          }
+        }
+        if (HasUnrelocatedInputs) {
+          if (HasRelocatedInputs)
+            PoisonedPointerDef = true;
+          else
+            ValidUnrelocatedPointerDef = true;
+        }
+      }
+    } else if ((isa<GetElementPtrInst>(I) || isa<BitCastInst>(I)) &&
                containsGCPtrType(I.getType())) {
-      // GEP/bitcast of unrelocated pointer is legal by itself but this
-      // def shouldn't appear in any AvailableSet.
+      // GEP/bitcast of unrelocated pointer is legal by itself but this def
+      // shouldn't appear in any AvailableSet.
       for (const Value *V : I.operands())
         if (containsGCPtrType(V->getType()) &&
             isNotExclusivelyConstantDerived(V) && !AvailableSet.count(V)) {
-          ProducesUnrelocatedPointer = true;
+          if (isValuePoisoned(V))
+            PoisonedPointerDef = true;
+          else
+            ValidUnrelocatedPointerDef = true;
           break;
         }
     }
-    if (!ProducesUnrelocatedPointer) {
-      bool Cleared = false;
-      transferInstruction(I, Cleared, AvailableSet);
-      (void)Cleared;
-    } else {
-      // Remove def of unrelocated pointer from Contribution of this BB
-      // and trigger update of all its successors.
+    assert(!(ValidUnrelocatedPointerDef && PoisonedPointerDef) &&
+           "Value cannot be both unrelocated and poisoned!");
+    if (ValidUnrelocatedPointerDef) {
+      // Remove def of unrelocated pointer from Contribution of this BB and
+      // trigger update of all its successors.
       Contribution.erase(&I);
+      PoisonedDefs.erase(&I);
       ValidUnrelocatedDefs.insert(&I);
       DEBUG(dbgs() << "Removing " << I << " from Contribution of "
-                   << BB->getName() << "\n");
+                   << BB->getName() << " ; it's unrelocated\n");
       ContributionChanged = true;
+    } else if (PoisonedPointerDef) {
+      // Mark pointer as poisoned, remove its def from Contribution and trigger
+      // update of all successors.
+      Contribution.erase(&I);
+      PoisonedDefs.insert(&I);
+      DEBUG(dbgs() << "Removing " << I << " from Contribution of "
+                   << BB->getName() << " ; it's poisoned\n");
+      ContributionChanged = true;
+    } else {
+      bool Cleared = false;
+      transferInstruction(I, Cleared, AvailableSet);
+      (void)Cleared;
     }
   }
   return ContributionChanged;
 }
 
 void GCPtrTracker::gatherDominatingDefs(const BasicBlock *BB,
                                         AvailableValueSet &Result,
                                         const DominatorTree &DT) {
void InstructionVerifier::verifyInstruction(
   } 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);
 
     // Returns true if LHS and RHS are unrelocated pointers and they are
     // valid unrelocated uses.
-    auto hasValidUnrelocatedUse = [&AvailableSet, baseTyLHS, baseTyRHS, &LHS,
-                                   &RHS] () {
+    auto hasValidUnrelocatedUse = [&AvailableSet, Tracker, baseTyLHS, baseTyRHS,
+                                   &LHS, &RHS] () {
         // A cmp instruction has valid unrelocated pointer operands only if
         // both operands are unrelocated pointers.
         // In the comparison between two pointers, if one is an unrelocated
         // use, the other *should be* an unrelocated use, for this
         // instruction to contain valid unrelocated uses. This unrelocated
         // use can be a null constant as well, or another unrelocated
         // pointer.
         if (AvailableSet.count(LHS) || AvailableSet.count(RHS))
           return false;
         // Constant pointers (that are not exclusively null) may have
         // meaning in different VMs, so we cannot reorder the compare
         // against constant pointers before the safepoint. In other words,
         // comparison of an unrelocated use against a non-null constant
         // maybe invalid.
         if ((baseTyLHS == BaseType::ExclusivelySomeConstant &&
              baseTyRHS == BaseType::NonConstant) ||
             (baseTyLHS == BaseType::NonConstant &&
              baseTyRHS == BaseType::ExclusivelySomeConstant))
           return false;
+
+        // If one of pointers is poisoned and other is not exclusively null
+        // it is an invalid expression: it produces poisoned result and
+        // unless we want to track all defs (not only gc pointers) the only
+        // option is to prohibit such instructions.
+        if ((Tracker->isValuePoisoned(LHS) && baseTyRHS != ExclusivelyNull) ||
+            (Tracker->isValuePoisoned(RHS) && baseTyLHS != ExclusivelyNull))
+            return false;
+
         // All other cases are valid cases enumerated below:
-        // 1. Comparison between an exlusively derived null pointer and a
+        // 1. Comparison between an exclusively derived null pointer and a
         // constant base pointer.
-        // 2. Comparison between an exlusively derived null pointer and a
+        // 2. Comparison between an exclusively derived null pointer and a
         // non-constant unrelocated base pointer.
         // 3. Comparison between 2 unrelocated pointers.
+        // 4. Comparison between an exclusively derived null pointer and a
+        // non-constant poisoned pointer.
         return true;
     };
     if (!hasValidUnrelocatedUse()) {
       // Print out all non-constant derived pointers that are unrelocated
       // uses, which are invalid.
       if (baseTyLHS == BaseType::NonConstant && !AvailableSet.count(LHS))
         reportInvalidUse(*LHS, I);
       if (baseTyRHS == BaseType::NonConstant && !AvailableSet.count(RHS))

test/SafepointIRVerifier/unrecorded-live-at-sp.ll

 ; RUN: opt %s -safepoint-ir-verifier-print-only -verify-safepoint-ir -S 2>&1 | FileCheck %s
 
 ; CHECK:      Illegal use of unrelocated value found!
-; CHECK-NEXT: Def:   %base_phi3 = phi %jObject addrspace(1)* [ %obj609.relocated, %not_zero146 ], [ %base_phi2, %bci_37-aload ], !is_base_value !0
-; CHECK-NEXT: Use:   %base_phi2 = phi %jObject addrspace(1)* [ %base_phi3, %not_zero179 ], [ %cast5, %bci_0 ], !is_base_value !0
+; CHECK-NEXT: Def:   %base_phi4 = phi %jObject addrspace(1)* addrspace(1)* [ %addr98.relocated, %not_zero146 ], [ %cast6, %bci_37-aload ], !is_base_value !0
+; CHECK-NEXT: Use:   %safepoint_token = tail call token (i64, i32, i32 ()*, i32, i32, ...) @llvm.experimental.gc.statepoint.p0f_i32f(i64 0, i32 0, i32 ()* undef, i32 0, i32 0, i32 0, i32 5, i32 0, i32 0, i32 0, i32 0, i32 0, %jObject addrspace(1)* %base_phi1, %jObject addrspace(1)* addrspace(1)* %base_phi4, %jObject addrspace(1)* addrspace(1)* %relocated4, %jObject addrspace(1)* %relocated7)
+
 
 %jObject = type { [8 x i8] }
 
 declare %jObject addrspace(1)* @generate_obj1() #1
 
 declare %jObject addrspace(1)* addrspace(1)* @generate_obj2() #1
 
 declare %jObject addrspace(1)* @generate_obj3() #1

test/SafepointIRVerifier/uses-in-phi-nodes.ll

 ; RUN: opt -safepoint-ir-verifier-print-only -verify-safepoint-ir -S %s 2>&1 | FileCheck %s
 
 define i8 addrspace(1)* @test.not.ok.0(i8 addrspace(1)* %arg) gc "statepoint-example" {
 ; CHECK-LABEL: Verifying gc pointers in function: test.not.ok.0
  bci_0:
   br i1 undef, 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:
 ; CHECK: Illegal use of unrelocated value found!
-; CHECK-NEXT: Def: i8 addrspace(1)* %arg
-; CHECK-NEXT: Use:   %val = phi i8 addrspace(1)* [ %arg, %left ], [ %arg, %right ]
-  %val = phi i8 addrspace(1)* [ %arg, %left ], [ %arg, %right]
+; CHECK-NEXT: Def:   %val = phi i8 addrspace(1)* [ %arg, %left ], [ %arg, %right ]
+; CHECK-NEXT: Use:   ret i8 addrspace(1)* %val
+  %val = phi i8 addrspace(1)* [ %arg, %left ], [ %arg, %right ]
   ret i8 addrspace(1)* %val
 }
 
 define i8 addrspace(1)* @test.not.ok.1(i8 addrspace(1)* %arg) gc "statepoint-example" {
 ; CHECK-LABEL: Verifying gc pointers in function: test.not.ok.1
  bci_0:
   br i1 undef, 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:
 ; CHECK: Illegal use of unrelocated value found!
-; CHECK-NEXT: Def: i8 addrspace(1)* %arg
-; CHECK-NEXT: Use:   %val = phi i8 addrspace(1)* [ %arg, %left ], [ null, %right ]
-  %val = phi i8 addrspace(1)* [ %arg, %left ], [ null, %right]
+; CHECK-NEXT: Def:   %val = phi i8 addrspace(1)* [ %arg, %left ], [ null, %right ]
+; CHECK-NEXT: Use:   ret i8 addrspace(1)* %val
+  %val = phi i8 addrspace(1)* [ %arg, %left ], [ null, %right ]
   ret i8 addrspace(1)* %val
 }
 
 define i8 addrspace(1)* @test.ok.0(i8 addrspace(1)* %arg) gc "statepoint-example" {
 ; CHECK: No illegal uses found by SafepointIRVerifier in: test.ok.0
  bci_0:
   br i1 undef, label %left, label %right
 

  right:
   br label %merge
 
  merge:
   %val = phi i8 addrspace(1)* [ %arg, %left ], [ %arg, %right]
   ret i8 addrspace(1)* %val
 }
 
+; It should be allowed to compare poisoned ptr with null.
+define void @test.poisoned.cmp.ok(i8 addrspace(1)* %arg) gc "statepoint-example" {
+; CHECK-LABEL: Verifying gc pointers in function: test.poisoned.cmp.ok
+ bci_0:
+  br i1 undef, 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 0, i8 addrspace(1)* %arg , i32 -1, i32 0, i32 0, i32 0)
+  %arg.relocated = call i8 addrspace(1)* @llvm.experimental.gc.relocate.p1i8(token %safepoint_token, i32 7, i32 7) ; arg, arg
+  br label %merge
+
+ right:
+  %safepoint_token2 = 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 0, i8 addrspace(1)* %arg , i32 -1, i32 0, i32 0, i32 0)
+  br label %merge
+
+ merge:
+; CHECK: No illegal uses found by SafepointIRVerifier in: test.poisoned.cmp.ok
+  %val.poisoned = phi i8 addrspace(1)* [ %arg.relocated, %left ], [ %arg, %right ]
+  %c = icmp eq i8 addrspace(1)* %val.poisoned, null
+  ret void
+}
+
+; It is illegal to compare poisoned ptr and relocated.
+define void @test.poisoned.cmp.fail.0(i8 addrspace(1)* %arg) gc "statepoint-example" {
+; CHECK-LABEL: Verifying gc pointers in function: test.poisoned.cmp.fail.0
+ bci_0:
+  br i1 undef, 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 0, i8 addrspace(1)* %arg , i32 -1, i32 0, i32 0, i32 0)
+  %arg.relocated = call i8 addrspace(1)* @llvm.experimental.gc.relocate.p1i8(token %safepoint_token, i32 7, i32 7) ; arg, arg
+  br label %merge
+
+ right:
+  %safepoint_token2 = 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 0, i8 addrspace(1)* %arg , i32 -1, i32 0, i32 0, i32 0)
+  %arg.relocated2 = call i8 addrspace(1)* @llvm.experimental.gc.relocate.p1i8(token %safepoint_token2, i32 7, i32 7) ; arg, arg
+  br label %merge
+
+ merge:
+; CHECK: Illegal use of unrelocated value found!
+; CHECK-NEXT: Def:   %val.poisoned = phi i8 addrspace(1)* [ %arg.relocated, %left ], [ %arg, %right ]
+; CHECK-NEXT: Use:   %c = icmp eq i8 addrspace(1)* %val.poisoned, %val
+  %val.poisoned = phi i8 addrspace(1)* [ %arg.relocated, %left ], [ %arg, %right ]
+  %val = phi i8 addrspace(1)* [ %arg.relocated, %left ], [ %arg.relocated2, %right ]
+  %c = icmp eq i8 addrspace(1)* %val.poisoned, %val
+  ret void
+}
+
+; It is illegal to compare poisoned ptr and unrelocated.
+define void @test.poisoned.cmp.fail.1(i8 addrspace(1)* %arg) gc "statepoint-example" {
+; CHECK-LABEL: Verifying gc pointers in function: test.poisoned.cmp.fail.1
+ bci_0:
+  br i1 undef, 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 0, i8 addrspace(1)* %arg , i32 -1, i32 0, i32 0, i32 0)
+  %arg.relocated = call i8 addrspace(1)* @llvm.experimental.gc.relocate.p1i8(token %safepoint_token, i32 7, i32 7) ; arg, arg
+  br label %merge
+
+ right:
+  %safepoint_token2 = 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 0, i8 addrspace(1)* %arg , i32 -1, i32 0, i32 0, i32 0)
+  %arg.relocated2 = call i8 addrspace(1)* @llvm.experimental.gc.relocate.p1i8(token %safepoint_token2, i32 7, i32 7) ; arg, arg
+  br label %merge
+
+ merge:
+; CHECK: Illegal use of unrelocated value found!
+; CHECK-NEXT: Def:   %val.poisoned = phi i8 addrspace(1)* [ %arg.relocated, %left ], [ %arg, %right ]
+; CHECK-NEXT: Use:   %c = icmp eq i8 addrspace(1)* %val.poisoned, %arg
+  %val.poisoned = phi i8 addrspace(1)* [ %arg.relocated, %left ], [ %arg, %right ]
+  %c = icmp eq i8 addrspace(1)* %val.poisoned, %arg
+  ret void
+}
+
+; It should be allowed to compare unrelocated phi with unrelocated value.
+define void @test.unrelocated-phi.cmp.ok(i8 addrspace(1)* %arg) gc "statepoint-example" {
+; CHECK-LABEL: Verifying gc pointers in function: test.unrelocated-phi.cmp.ok
+ bci_0:
+  br i1 undef, 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:
+; CHECK: No illegal uses found by SafepointIRVerifier in: test.unrelocated-phi.cmp.ok
+  %val.unrelocated = phi i8 addrspace(1)* [ %arg, %left ], [ null, %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, ...)
+declare i8 addrspace(1)* @llvm.experimental.gc.relocate.p1i8(token, i32, i32)
 declare void @not_statepoint()