[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

124

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

128

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.

384

it's -> its

385

"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

346

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.

348

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?

350

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

355

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

357

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

396

same as above, I propose ContributionChanged or IsContributionChanged.

398

ProducesUnrelocatedPointer

416

it's -> its

419

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

444

Finalize sentence.

[DaniilSuchkov]

lib/IR/SafepointIRVerifier.cpp

348

Sorry, my comment wasn't clear enough.

355

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

419

I is a reference, so it's OK.

[DaniilSuchkov]

Comments addressed.

[mkazantsev]

lib/IR/SafepointIRVerifier.cpp

354–355

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

[mkazantsev]

lib/IR/SafepointIRVerifier.cpp

354–355

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

337

Nit: Stale comment. It's BBContributionUpdater

340

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>

351

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

340

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

340

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

345

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

static bool containsGCPtrType(Type *Ty) {
   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;
 }
 
+static bool isDerivedPointerDef(const Value *Val) {
+  return isa<CastInst>(Val) || isa<GetElementPtrInst>(Val);
+}
+
+static const Value *getBasePointer(const Value *Val) {
+  if (!Val->getType()->isPointerTy())
+    return Val;
+
+  while (isDerivedPointerDef(Val))
+    if (auto *GEP = dyn_cast<GetElementPtrInst>(Val))
+      Val = GEP->getPointerOperand();
+    else if (auto *CI = dyn_cast<CastInst>(Val))
+      Val = CI->stripPointerCasts();
+  return Val;
+}
+
 // 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;
   }
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) {
 
-  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 = BBS.Contribution;
static enum BaseType getBaseType(const Value *Val) {
   // 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);
   }
 
   SetVector<const BasicBlock *> Worklist;
   for (auto &BBI : BlockMap)
     Worklist.insert(BBI.first);
 
   // This loop iterates the AvailableIn and AvailableOut sets to a fixed point.
   // 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!");
 
     size_t OldOutCount = BBS->AvailableOut.size();
     TransferBlock(BB, *BBS, false);
     if (OldOutCount != BBS->AvailableOut.size()) {
       assert(OldOutCount > BBS->AvailableOut.size() && "invariant!");
       Worklist.insert(succ_begin(BB), succ_end(BB));
     }
   }
 
   // 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,
static void Verify(const Function &F, const DominatorTree &DT) {
   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;
+    auto isBaseAvailable = [&AvailableSet] (const Value *V) {
+      // Derived pointer can be safely used only if it's base is relocated.
+      // So we need to check only is base pointer relocated or not.
+      return AvailableSet.count(getBasePointer(V)) != 0;
+    };
     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))
+                !BlockMap[InBB]->AvailableOut.count(getBasePointer(InValue)))
               ReportInvalidUse(*InValue, *PN);
           }
       } else if (isa<CmpInst>(I) &&
                  containsGCPtrType(I.getOperand(0)->getType())) {
-        Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
+        const 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 = [&] () {
             // 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))
+            if (isBaseAvailable(LHS) || isBaseAvailable(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;
             // All other cases are valid cases enumerated below:
             // 1. Comparison between an exlusively derived null pointer and a
             // constant base pointer.
             // 2. Comparison between an exlusively derived null pointer and a
             // non-constant unrelocated base pointer.
             // 3. Comparison between 2 unrelocated pointers.
             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))
+          if (baseTyLHS == BaseType::NonConstant && !isBaseAvailable(LHS))
             ReportInvalidUse(*LHS, I);
-          if (baseTyRHS == BaseType::NonConstant && !AvailableSet.count(RHS))
+          if (baseTyRHS == BaseType::NonConstant && !isBaseAvailable(RHS))
             ReportInvalidUse(*RHS, I);
         }
-      } else {
+      } else if (!isDerivedPointerDef(&I)) {
+        // Since isBaseAvailable checks availablility of base objects we don't
+        // need to validate this instructions (GEP/bitcast). Any use of
+        // unrelocated pointers in this instructions by itself is legal. If they
+        // are used in illegal way (currently the only legal way to use them is
+        // cmp) the verifier is guaranteed to report a failure.
         for (const Value *V : I.operands())
           if (containsGCPtrType(V->getType()) &&
-              isNotExclusivelyConstantDerived(V) && !AvailableSet.count(V))
+              isNotExclusivelyConstantDerived(V) && !isBaseAvailable(V))
             ReportInvalidUse(*V, I);
       }
 
       bool Cleared = false;
       TransferInstruction(I, Cleared, AvailableSet);
       (void)Cleared;
     }
   }
 
   if (PrintOnly && !AnyInvalidUses) {
     dbgs() << "No illegal uses found by SafepointIRVerifier in: " << F.getName()
            << "\n";
   }
 }

test/SafepointIRVerifier/use-derived-unrelocated.ll

+; RUN: opt -safepoint-ir-verifier-print-only -verify-safepoint-ir -S %s 2>&1 | FileCheck %s
+
+define void @test.simple.ok(i32, i8 addrspace(1)* %base1, i8 addrspace(1)* %base2) gc "statepoint-example" {
+; CHECK-LABEL: Verifying gc pointers in function: test.simple.ok
+; CHECK-NEXT: No illegal uses found by SafepointIRVerifier in: test.simple.ok
+.b0:
+  %ptr = getelementptr i8, i8 addrspace(1)* %base1, i64 4
+  br label %.b1
+
+.b1:
+  %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)
+  br label %.b2
+
+.b2:
+  %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)*
+  %c = icmp sgt i32 addrspace(1)* %ptr.i32, %ptr2.i32
+  ret void
+}
+
+define void @test.simple.fail(i32, i8 addrspace(1)* %base) gc "statepoint-example" {
+; CHECK-LABEL: Verifying gc pointers in function: test.simple.fail
+.b0:
+  %ptr = getelementptr i8, i8 addrspace(1)* %base, i64 4
+  br label %.b1
+
+.b1:
+  %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)
+  br label %.b2
+
+.b2:
+  %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
+}
+
+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
+}
+
+define void @test.cmp.ok(i64 %arg, 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
+  %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)
+  %another_offset = add i64 %arg, 8
+  %addr2 = getelementptr i8, i8 addrspace(1)* %base2, i64 %another_offset
+  %cmp = icmp eq i8 addrspace(1)* %addr1, %addr2
+  ret void
+}
+
+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)
+  %another_offset = add i64 %arg, 8
+  %addr2 = getelementptr i8, i8 addrspace(1)* %base2, i64 %another_offset
+  %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 %another_offset
+; CHECK-NEXT: Use:   %val = load i8, i8 addrspace(1)* %addr2
+  %val = load i8, i8 addrspace(1)* %addr2
+  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)
+