[SafepointIRVerifier] Allow deriving pointers from unrelocated base

[DaniilSuchkov]

Summary

Deriving pointer (adding GEPs/casts to base pointer) from it's base by itself
isn't incorrect even if the base pointer is unrelocated. Correctness depends
only on uses of this derived pointer. This patch allows to use derived pointers
in the same way as base pointers no matter where (before or after safepoint)
they were derived from base.
It is acheived by two changes:

1. When we have enough information to say if the pointer is unrelocated at some

point or not, we walk all BBs to remove from their Contributions all valid defs
of unrelocated pointers (GEP with unrelocated base or bitcast of unrelocated
pointer).

2. When it comes to verification we just ignore instructions that were removed

at stage 1.

[mkazantsev]

lib/IR/SafepointIRVerifier.cpp

125

CastInst doesn't look like what you need, it also includes sext, zext and a lot of stuff you don't need.

129

Why do you check it outside of isDerivedPointerDef? We don't want integer-to-integer casts to be treated as derived pointers. Please add it as check.

391

it's -> its

392

"only if base pointer is relocated or not"

[DaniilSuchkov]

All tests now have comments, one redundant test removed, one new added. getBasePointer now works more correctly and getImmediateBase now is the only place where we need to specify which instructions can produce derived pointers.

[DaniilSuchkov]

Made logic around getImmediateBasePointer/isDerivedPointerDef more consistent.

[DaniilSuchkov]

Add message to assert.

[mkazantsev]

Looks fine for me, but I'd likeone else to take a look.

[anna]

Thanks for addressing the comments in the downstream version (and Max's comments here). This LGTM.

[DaniilSuchkov]

One crash was found during testing.

[DaniilSuchkov]

Algorithm rewritten, new tests added.

Previous solution would work only for GEPs/casts and it was impossible to make it work with phis/selects/etc. This new solution is much more general.

[DaniilSuchkov]

Changed order of the verification traversal to RPO.

[mkazantsev]

lib/IR/SafepointIRVerifier.cpp

309

Please rename Visitor to something that makes sense in terms of what it is expected to do. I'd rather prefer something like CalculateBlockContribution or CalculateBlockContributionVisitor.

311

It's not clear to me why. I see how topological order of successors gives us gain, but it's not clear why we need BFS in addition to that. Could you please give an example?

328

I'd propose InputsChanged and ContributionChanged respectively. If you want to keep these names, please capitalize 1st letter since these are variables.

336

What was the reason of changing > to >=? They can never be equal due to condition one line above.

338

"if any" -> "if such order is defined"?

398

same as above, I propose ContributionChanged or IsContributionChanged.

400

ProducesUnrelocatedPointer

418

it's -> its

421

Should be << *I << if you want a reasonable output.

491

Finalize sentence.

[DaniilSuchkov]

lib/IR/SafepointIRVerifier.cpp

311

Sorry, my comment wasn't clear enough.

336

This assertion was supposed to be before the if-statement.

421

I is a reference, so it's OK.

[DaniilSuchkov]

Comments addressed.

[mkazantsev]

lib/IR/SafepointIRVerifier.cpp

335–338

It is trivially true after the assert above, isn't it?

[mkazantsev]

lib/IR/SafepointIRVerifier.cpp

335–338

Me bad, it's not.

[mkazantsev]

Looks fine for me, but I'd like someone else to take a look to verify that the logic is ok.

[DaniilSuchkov]

Now the branch where valid defs of unrelocated pointers are skipped is the first one.

[anna]

Some refactoring comments in place. I think the code structuring can be made much simpler. Pls see inline comments.

lib/IR/SafepointIRVerifier.cpp

300

Nit: Stale comment. It's BBContributionUpdater

303

If BBContributionUpdater is expected to have this type, then why templatize it?
You could just typedef instead of using templated type right, I think it makes the intent clearer.

<This comment is superseded by refactoring comment below>

329

Instead of passing in an entire lambda, why not just use a static function BBContributionUpdater that also takes in a bool, which identifies if this is "after computing def states" or if this is the initial stage (i.e. BBContributionUpdater just return false if it was the initial stage) ?

It avoids all this template and function pointers and identifying what's going on. Also all logic is in one place.

[DaniilSuchkov]

lib/IR/SafepointIRVerifier.cpp

303

Lambda with non-empty capture list cannot be passed as function pointer. I'd rather created a new class which can build and process BlockStateMap. Such refactoring is already planned but first I want to get rid of false-positives with GEPs/bitcasts and phis (patch for phis is almost ready).

[anna]

lib/IR/SafepointIRVerifier.cpp

303

Discussed with Daniil offline, this wasn't obvious. He'll be updating the capture list.
Daniil, pls also state here why you'll be having it as a template (perhaps as a FIXME instead of the TODO below).

[DaniilSuchkov]

Amended some comments, replaced lambda's wildcard capture list with explicit one, made isNotExclusivelyConstantDerived static function (to use it in lambdas without capturing).

[anna]

thanks for making the changes. lgtm with a minor comment.

lib/IR/SafepointIRVerifier.cpp

308

Could you pls phrase it as:
"FIXME: It's a bit ugly and unclear, but other options causes us to spread the logic of RecalculateBBStates across the rest of the algorithm." This will nicely flow with the rest of the comment about encapsulating everything in a class.

[DaniilSuchkov]

Corrected the comment.

lib/IR/SafepointIRVerifier.cpp

 // Because it is valid to reorder 'c' above the safepoint, this is legal.  In
 // practice, this is a somewhat uncommon transform, but CodeGenPrep does create
 // idioms like this.  The verifier knows about these cases and avoids reporting
 // false positives.
 //
 //===----------------------------------------------------------------------===//
 
 #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/Dominators.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/Intrinsics.h"
 #include "llvm/IR/IntrinsicInst.h"
if (ArrayType *AT = dyn_cast<ArrayType>(Ty))
     return containsGCPtrType(AT->getElementType());
   if (StructType *ST = dyn_cast<StructType>(Ty))
     return std::any_of(ST->subtypes().begin(), ST->subtypes().end(),
                        containsGCPtrType);
   return false;
 }
 
 // Debugging aid -- prints a [Begin, End) range of values.
 template<typename IteratorTy>
 static void PrintValueSet(raw_ostream &OS, IteratorTy Begin, IteratorTy End) {
   OS << "[ ";
   while (Begin != End) {
     OS << **Begin << " ";
     ++Begin;
   }
   OS << "]";
 }
 
 /// The verifier algorithm is phrased in terms of availability.  The set of
 /// values "available" at a given point in the control flow graph is the set of
 /// correctly relocated value at that point, and is a subset of the set of
static void GatherDominatingDefs(const BasicBlock *BB,
                     DenseMap<const BasicBlock *, BasicBlockState *> &BlockMap) {
   DomTreeNode *DTN = DT[const_cast<BasicBlock *>(BB)];
 
   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 
+    // 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)
       return;
   }
 
   for (const Argument &A : BB->getParent()->args())
     if (containsGCPtrType(A.getType()))
       Result.insert(&A);
 }
 
 /// Model the effect of an instruction on the set of available values.
 static void TransferInstruction(const Instruction &I, bool &Cleared,
                               DenseSet<const Value *> &Available) {
   if (isStatepoint(I)) {
     Cleared = true;
     Available.clear();
   } else if (containsGCPtrType(I.getType()))
     Available.insert(&I);
 }
 
-/// Compute the AvailableOut set for BB, based on the
-/// BasicBlockState BBS, which is the BasicBlockState for BB. FirstPass is set
-/// when the verifier runs for the first time computing the AvailableOut set
-/// for BB.
-static void TransferBlock(const BasicBlock *BB,
-                          BasicBlockState &BBS, bool FirstPass) {
+/// Compute the AvailableOut set for BB, based on the BasicBlockState BBS,
+/// which is the BasicBlockState for BB.
+/// isContributionChanged is set when the verifier runs for the first time
+/// (in this case Contribution was changed from 'empty' to its initial state) or
+/// when Contribution of this BB was changed since last computation.
+static void TransferBlock(const BasicBlock *BB, BasicBlockState &BBS,
+                          bool isContributionChanged) {
 
-  const DenseSet<const Value *> &AvailableIn = BBS.AvailableIn; 
+  const DenseSet<const Value *> &AvailableIn = BBS.AvailableIn;
   DenseSet<const Value *> &AvailableOut  = BBS.AvailableOut;
 
   if (BBS.Cleared) {
-    // AvailableOut does not change no matter how the input changes, just
-    // leave it be.  We need to force this calculation the first time so that
-    // we have a AvailableOut at all.
-    if (FirstPass) {
+    // AvailableOut will change only when Contribution changed.
+    if (isContributionChanged)
       AvailableOut = BBS.Contribution;
-    }
   } else {
     // Otherwise, we need to reduce the AvailableOut set by things which are no
     // longer in our AvailableIn
     DenseSet<const Value *> Temp = BBS.Contribution;
     set_union(Temp, AvailableIn);
     AvailableOut = std::move(Temp);
   }
 
while(!Worklist.empty()) {
     return BaseType::NonConstant;
   }
   // Now, we know that the base pointer is exclusively constant, but we need to
   // differentiate between exclusive null constant and non-null constant.
   return isExclusivelyDerivedFromNull ? BaseType::ExclusivelyNull
                                       : BaseType::ExclusivelySomeConstant;
 }
 
-static void Verify(const Function &F, const DominatorTree &DT) {
-  SpecificBumpPtrAllocator<BasicBlockState> BSAllocator;
-  DenseMap<const BasicBlock *, BasicBlockState *> BlockMap;
- 
-  DEBUG(dbgs() << "Verifying gc pointers in function: " << F.getName() << "\n");
-  if (PrintOnly)
-    dbgs() << "Verifying gc pointers in function: " << F.getName() << "\n";
-
-
-  for (const BasicBlock &BB : F) {
-    BasicBlockState *BBS = new(BSAllocator.Allocate()) BasicBlockState;
-    for (const auto &I : BB)
-      TransferInstruction(I, BBS->Cleared, BBS->Contribution);
-    BlockMap[&BB] = BBS;
-  }
-
-  for (auto &BBI : BlockMap) {
-    GatherDominatingDefs(BBI.first, BBI.second->AvailableIn, DT, BlockMap);
-    TransferBlock(BBI.first, *BBI.second, true);
-  }
+using BlockStateMap = DenseMap<const BasicBlock *, BasicBlockState *>;
 
+/// This function iterates over all BBs from BlockMap and recalculates
+/// AvailableIn/Out for each of them until it converges.
+/// It calls Visitor for each visited BB after updating it's AvailableIn.
+/// Visitor may change BB's Contribution and should return true it this case.
+///
+/// Visitor is expected to have following signature:
+/// (const BasicBlock *BB, const BasicBlockState *BBS,
+///  DenseSet<const Value *> &Contribution) -> bool
+/// TODO: this function, TransferBlock, TransferInstruction and others should be
+/// moved to a separate class which will hold all the logic related to
+/// BasicBlockState.
+template <typename VisitorTy>
+static void RecalculateBBsStates(BlockStateMap &BlockMap, VisitorTy &&Visitor) {
+  // TODO: It would be better if worklist will work as a queue (not as a stack).
+  // This way this algorithm will converge faster.
   SetVector<const BasicBlock *> Worklist;
   for (auto &BBI : BlockMap)
     Worklist.insert(BBI.first);
 
-  // This loop iterates the AvailableIn and AvailableOut sets to a fixed point.
+  // 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))
       set_intersect(BBS->AvailableIn, BlockMap[PBB]->AvailableOut);
 
-    if (OldInCount == BBS->AvailableIn.size())
-      continue;
+    assert(OldInCount >= BBS->AvailableIn.size() && "invariant!");
 
-    assert(OldInCount > BBS->AvailableIn.size() && "invariant!");
+    bool isInputsChanged = OldInCount != BBS->AvailableIn.size();
+    bool isContributionChanged = Visitor(BB, BBS, BBS->Contribution);
+    if (!isInputsChanged && !isContributionChanged)
+      continue;
 
     size_t OldOutCount = BBS->AvailableOut.size();
-    TransferBlock(BB, *BBS, false);
+    TransferBlock(BB, *BBS, isContributionChanged);
     if (OldOutCount != BBS->AvailableOut.size()) {
-      assert(OldOutCount > BBS->AvailableOut.size() && "invariant!");
+      assert(OldOutCount >= BBS->AvailableOut.size() && "invariant!");
+      // TODO: It is better to add successors to a worklist in topological order
+      // (if any). It will decrease number of iterations required to converge.
       Worklist.insert(succ_begin(BB), succ_end(BB));
     }
   }
+}
+
+static void Verify(const Function &F, const DominatorTree &DT) {
+  SpecificBumpPtrAllocator<BasicBlockState> BSAllocator;
+  BlockStateMap BlockMap;
+
+  DEBUG(dbgs() << "Verifying gc pointers in function: " << F.getName() << "\n");
+  if (PrintOnly)
+    dbgs() << "Verifying gc pointers in function: " << F.getName() << "\n";
+
+
+  for (const BasicBlock &BB : F) {
+    BasicBlockState *BBS = new(BSAllocator.Allocate()) BasicBlockState;
+    for (const auto &I : BB)
+      TransferInstruction(I, BBS->Cleared, BBS->Contribution);
+    BlockMap[&BB] = BBS;
+  }
+
+  for (auto &BBI : BlockMap) {
+    GatherDominatingDefs(BBI.first, BBI.second->AvailableIn, DT, BlockMap);
+    TransferBlock(BBI.first, *BBI.second, true);
+  }
+
+  RecalculateBBsStates(BlockMap, [] (const BasicBlock *,
+                                     const BasicBlockState *,
+                                     DenseSet<const Value *> &) {
+    return false;
+  });
 
   // 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.
 
   bool AnyInvalidUses = false;
 
   auto ReportInvalidUse = [&AnyInvalidUses](const Value &V,
                                             const Instruction &I) {
     errs() << "Illegal use of unrelocated value found!\n";
     errs() << "Def: " << V << "\n";
     errs() << "Use: " << I << "\n";
     if (!PrintOnly)
       abort();
     AnyInvalidUses = true;
   };
 
   auto isNotExclusivelyConstantDerived = [](const Value *V) {
     return getBaseType(V) == BaseType::NonConstant;
   };
 
-  for (const BasicBlock &BB : F) {
-    // We destructively modify AvailableIn as we traverse the block instruction
-    // by instruction.
-    DenseSet<const Value *> &AvailableSet = BlockMap[&BB]->AvailableIn;
-    for (const Instruction &I : BB) {
+  // This set contains defs that can be safely ignored during verification.
+  DenseSet<const Instruction *> ValidUnrelocatedDefs;
+
+  // Now we can remove all valid unrelocated gc pointer defs from all BBS sets.
+  RecalculateBBsStates(BlockMap, [&] (const BasicBlock *BB,
+                                      const BasicBlockState *BBS,
+                                      DenseSet<const Value *> &Contribution) {
+    DenseSet<const Value *> AvailableSet = BBS->AvailableIn;
+    bool isContributionChanged = false;
+    for (const Instruction &I : *BB) {
+      bool isProducesUnrelocatedPointer = false;
+      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.
+        for (const Value *V : I.operands())
+          if (containsGCPtrType(V->getType()) &&
+              isNotExclusivelyConstantDerived(V) && !AvailableSet.count(V)) {
+            isProducesUnrelocatedPointer = true;
+            break;
+          }
+      }
+      if (!isProducesUnrelocatedPointer) {
+        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 it's successors.
+        Contribution.erase(&I);
+        ValidUnrelocatedDefs.insert(&I);
+        DEBUG(dbgs() << "Removing " << I << " from Contribution of "
+                     << BB->getName() << "\n");
+        isContributionChanged = true;
+      }
+    }
+    return isContributionChanged;
+  });
+
+  // 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(&F);
+  for (const BasicBlock *BB : RPOT) {
+    BasicBlockState *BBS = BlockMap[BB];
+    DenseSet<const Value *> &AvailableSet = BBS->AvailableIn;
+    for (const Instruction &I : *BB) {
       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);
             const Value *InValue = PN->getIncomingValue(i);
 
             if (isNotExclusivelyConstantDerived(InValue) &&
                 !BlockMap[InBB]->AvailableOut.count(InValue))
for (const Instruction &I : *BB) {
         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))
             ReportInvalidUse(*RHS, I);
         }
+      } else if (ValidUnrelocatedDefs.count(&I)) {
+        continue; // This instruction shouldn't be added to AvailableSet
       } else {
         for (const Value *V : I.operands())
           if (containsGCPtrType(V->getType()) &&
               isNotExclusivelyConstantDerived(V) && !AvailableSet.count(V))
             ReportInvalidUse(*V, I);
       }
 
       bool Cleared = false;

test/SafepointIRVerifier/use-derived-unrelocated.ll

+; RUN: opt -safepoint-ir-verifier-print-only -verify-safepoint-ir -S %s 2>&1 | FileCheck %s
+
+; Checking if verifier accepts chain of GEPs/bitcasts.
+define void @test.deriving.ok(i32, i8 addrspace(1)* %base1, i8 addrspace(1)* %base2) gc "statepoint-example" {
+; CHECK-LABEL: Verifying gc pointers in function: test.deriving.ok
+; CHECK-NEXT: No illegal uses found by SafepointIRVerifier in: test.deriving.ok
+  %ptr = getelementptr i8, i8 addrspace(1)* %base1, i64 4
+  %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)* %base1)
+  %ptr2 = getelementptr i8, i8 addrspace(1)* %base2, i64 8
+  %ptr.i32 = bitcast i8 addrspace(1)* %ptr to i32 addrspace(1)*
+  %ptr2.i32 = bitcast i8 addrspace(1)* %ptr2 to i32 addrspace(1)*
+  ret void
+}
+
+; Checking if verifier accepts cmp of two derived pointers when one defined
+; before safepoint and one after and both have unrelocated base.
+define void @test.cmp.ok(i32, i8 addrspace(1)* %base1, i8 addrspace(1)* %base2) gc "statepoint-example" {
+; CHECK-LABEL: Verifying gc pointers in function: test.cmp.ok
+; CHECK-NEXT: No illegal uses found by SafepointIRVerifier in: test.cmp.ok
+  %ptr = getelementptr i8, i8 addrspace(1)* %base1, i64 4
+  %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)* %base1)
+  %ptr2 = getelementptr i8, i8 addrspace(1)* %base2, i64 8
+  %c2 = icmp sgt i8 addrspace(1)* %ptr2, %ptr
+  ret void
+}
+
+; Checking if verifier accepts cmp of two derived pointers when one defined
+; before safepoint and one after and both have unrelocated base. One of pointers
+; defined as a long chain of geps/bitcasts.
+define void @test.cmp-long_chain.ok(i32, i8 addrspace(1)* %base1, i8 addrspace(1)* %base2) gc "statepoint-example" {
+; CHECK-LABEL: Verifying gc pointers in function: test.cmp-long_chain.ok
+; CHECK-NEXT: No illegal uses found by SafepointIRVerifier in: test.cmp-long_chain.ok
+  %ptr = getelementptr i8, i8 addrspace(1)* %base1, i64 4
+  %ptr.i32 = bitcast i8 addrspace(1)* %ptr to i32 addrspace(1)*
+  %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)* %base1)
+  %ptr2 = getelementptr i8, i8 addrspace(1)* %base2, i64 8
+  %ptr2.i32 = bitcast i8 addrspace(1)* %ptr2 to i32 addrspace(1)*
+  %ptr2.i32.2 = getelementptr i32, i32 addrspace(1)* %ptr2.i32, i64 4
+  %ptr2.i32.3 = getelementptr i32, i32 addrspace(1)* %ptr2.i32.2, i64 8
+  %ptr2.i32.4 = getelementptr i32, i32 addrspace(1)* %ptr2.i32.3, i64 8
+  %ptr2.i32.5 = getelementptr i32, i32 addrspace(1)* %ptr2.i32.4, i64 8
+  %ptr2.i32.6 = getelementptr i32, i32 addrspace(1)* %ptr2.i32.5, i64 8
+  %ptr2.i32.6.i8 = bitcast i32 addrspace(1)* %ptr2.i32.6 to i8 addrspace(1)*
+  %ptr2.i32.6.i8.i32 = bitcast i8 addrspace(1)* %ptr2.i32.6.i8 to i32 addrspace(1)*
+  %ptr2.i32.6.i8.i32.2 = getelementptr i32, i32 addrspace(1)* %ptr2.i32.6.i8.i32, i64 8
+  %c2 = icmp sgt i32 addrspace(1)* %ptr2.i32.6.i8.i32.2, %ptr.i32
+  ret void
+}
+
+; GEP and bitcast of unrelocated pointer is acceptable, but load by resulting
+; pointer should be reported.
+define void @test.load.fail(i32, i8 addrspace(1)* %base) gc "statepoint-example" {
+; CHECK-LABEL: Verifying gc pointers in function: test.load.fail
+  %ptr = getelementptr i8, i8 addrspace(1)* %base, i64 4
+  %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)* %base)
+  %ptr.i32 = bitcast i8 addrspace(1)* %ptr to i32 addrspace(1)* ; it's ok
+; CHECK-NEXT: Illegal use of unrelocated value found!
+; CHECK-NEXT: Def:   %ptr.i32 = bitcast i8 addrspace(1)* %ptr to i32 addrspace(1)*
+; CHECK-NEXT: Use:   %ptr.val = load i32, i32 addrspace(1)* %ptr.i32
+  %ptr.val = load i32, i32 addrspace(1)* %ptr.i32
+  ret void
+}
+
+; Comparison between pointer derived from unrelocated one (though defined after
+; safepoint) and relocated pointer should be reported.
+define void @test.cmp.fail(i64 %arg, i8 addrspace(1)* %base1, i8 addrspace(1)* %base2) gc "statepoint-example" {
+; CHECK-LABEL: Verifying gc pointers in function: test.cmp.fail
+  %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)* %base2 , i32 -1, i32 0, i32 0, i32 0)
+  %base2.relocated = call i8 addrspace(1)* @llvm.experimental.gc.relocate.p1i8(token %safepoint_token, i32 7, i32 7) ; base2, base2
+  %addr1 = getelementptr i8, i8 addrspace(1)* %base1, i64 %arg
+; CHECK-NEXT: Illegal use of unrelocated value found!
+; CHECK-NEXT: Def:   %addr1 = getelementptr i8, i8 addrspace(1)* %base1, i64 %arg
+; CHECK-NEXT: Use:   %cmp = icmp eq i8 addrspace(1)* %addr1, %base2.relocated
+  %cmp = icmp eq i8 addrspace(1)* %addr1, %base2.relocated
+  ret void
+}
+
+; Same as test.cmp.fail but splitted into two BBs.
+define void @test.cmp2.fail(i64 %arg, i8 addrspace(1)* %base1, i8 addrspace(1)* %base2) gc "statepoint-example" {
+.b0:
+; CHECK-LABEL: Verifying gc pointers in function: test.cmp2.fail
+  %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)* %base2 , i32 -1, i32 0, i32 0, i32 0)
+  %base2.relocated = call i8 addrspace(1)* @llvm.experimental.gc.relocate.p1i8(token %safepoint_token, i32 7, i32 7) ; base2, base2
+  %addr1 = getelementptr i8, i8 addrspace(1)* %base1, i64 %arg
+  br label %.b1
+
+.b1:
+; CHECK-NEXT: Illegal use of unrelocated value found!
+; CHECK-NEXT: Def:   %addr1 = getelementptr i8, i8 addrspace(1)* %base1, i64 %arg
+; CHECK-NEXT: Use:   %cmp = icmp eq i8 addrspace(1)* %addr1, %base2.relocated
+  %cmp = icmp eq i8 addrspace(1)* %addr1, %base2.relocated
+  ret void
+}
+
+; Checking that cmp of two unrelocated pointers is OK and load is not.
+define void @test.cmp-load.fail(i64 %arg, i8 addrspace(1)* %base1, i8 addrspace(1)* %base2) gc "statepoint-example" {
+; CHECK-LABEL: Verifying gc pointers in function: test.cmp-load.fail
+  %addr1 = getelementptr i8, i8 addrspace(1)* %base1, i64 %arg
+  %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)* %base2 , i32 -1, i32 0, i32 0, i32 0)
+  %addr2 = getelementptr i8, i8 addrspace(1)* %base2, i64 8
+  %cmp = icmp eq i8 addrspace(1)* %addr1, %addr2
+; CHECK-NEXT: Illegal use of unrelocated value found!
+; CHECK-NEXT: Def:   %addr2 = getelementptr i8, i8 addrspace(1)* %base2, i64 8
+; CHECK-NEXT: Use:   %val = load i8, i8 addrspace(1)* %addr2
+  %val = load i8, i8 addrspace(1)* %addr2
+  ret void
+}
+
+; Same as test.cmp-load.fail but splitted into thee BBs.
+define void @test.cmp-load2.fail(i64 %arg, i8 addrspace(1)* %base1, i8 addrspace(1)* %base2) gc "statepoint-example" {
+.b0:
+; CHECK-LABEL: Verifying gc pointers in function: test.cmp-load2.fail
+  %addr1 = getelementptr i8, i8 addrspace(1)* %base1, i64 %arg
+  %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)* %base2 , i32 -1, i32 0, i32 0, i32 0)
+  br label %.b1
+
+.b1:
+  %addr2 = getelementptr i8, i8 addrspace(1)* %base2, i64 8
+  br label %.b2
+
+.b2:
+  %cmp = icmp eq i8 addrspace(1)* %addr1, %addr2
+; CHECK-NEXT: Illegal use of unrelocated value found!
+; CHECK-NEXT: Def:   %addr2 = getelementptr i8, i8 addrspace(1)* %base2, i64 8
+; CHECK-NEXT: Use:   %val = load i8, i8 addrspace(1)* %addr2
+  %val = load i8, i8 addrspace(1)* %addr2
+  ret void
+}
+
+; Same as test.cmp.ok but with multiple safepoints within one BB. And the last
+; one is in the very end of BB so that Contribution of this BB is empty.
+define void @test.cmp.multi-sp.ok(i64 %arg, i8 addrspace(1)* %base1, i8 addrspace(1)* %base2) gc "statepoint-example" {
+; CHECK-LABEL: Verifying gc pointers in function: test.cmp.multi-sp.ok
+; CHECK-NEXT: No illegal uses found by SafepointIRVerifier in: test.cmp.multi-sp.ok
+  %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)* %base2 , i32 -1, i32 0, i32 0, i32 0)
+  %base2.relocated = call i8 addrspace(1)* @llvm.experimental.gc.relocate.p1i8(token %safepoint_token, i32 7, i32 7) ; base2, base2
+  %addr1 = getelementptr i8, i8 addrspace(1)* %base1, i64 %arg
+  %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)* %base2.relocated, i32 -1, i32 0, i32 0, i32 0)
+  %base2.relocated2 = call i8 addrspace(1)* @llvm.experimental.gc.relocate.p1i8(token %safepoint_token2, i32 7, i32 7) ; base2.relocated, base2.relocated
+  %addr2 = getelementptr i8, i8 addrspace(1)* %base2, i64 %arg
+  %cmp = icmp eq i8 addrspace(1)* %addr1, %addr2
+  %safepoint_token3 = 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)* %base2.relocated2, i32 -1, i32 0, i32 0, i32 0)
+  ret void
+}
+
+; Function Attrs: nounwind
+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)
+