[SafepointIRVerifier] Avoid false positives in GC verifier for compare between pointers

[anna]

Summary

Today the safepoint IR verifier catches some unrelocated uses of base pointers
that are actually valid.
With this change, we narrow down the set of false positives. Specifically, the
verifier knows about compares to null and compares between 2 unrelocated
pointers.

[skatkov]

lib/IR/SafepointIRVerifier.cpp

230

Don't you want to re-write this utility function without recursion?
In this case you will not need Visited parameter. Also I would suggest this function returns enum BaseType.

390

if both parts are true it means both are relocated pointers, why do we return false? Did I miss anything?

[anna]

lib/IR/SafepointIRVerifier.cpp

230

Yeah, that might be better. I'll check it in as NFC, along with the BaseType enum return. We'll still need the visited parameter to avoid traversing through the operands again in the worklist.

390

The reason is because we are interested only in valid *unrelocated* uses. This happens only when both operands are unrelocated: these operands are either null, constant pointers or non-constant pointers (please see the comment above: lines 383).
Returning false when either are relocated simplifies the checks in this lambda -- because we know that from this point on it's unrelocated uses that we are interested in.
Also, the case where bother are relocated is automatically handled in the checks following the call to this lambda.

[anna]

Need to rebase code over the NFC refactoring.

lib/IR/SafepointIRVerifier.cpp

230

Checked in NFC refactoring change: https://reviews.llvm.org/rL307340

[anna]

rebased over the NFC refactoring.

[skatkov]

lib/IR/SafepointIRVerifier.cpp

390

Got it. It is not a bool algebra :) !hasValidUnrelocatedUse does not mean has invalid :) it means has not or has invalid.

lib/IR/SafepointIRVerifier.cpp

 //===-- SafepointIRVerifier.cpp - Verify gc.statepoint invariants ---------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // Run a sanity check on the IR to ensure that Safepoints - if they've been
 // inserted - were inserted correctly.  In particular, look for use of
 // non-relocated values after a safepoint.  It's primary use is to check the
 // correctness of safepoint insertion immediately after insertion, but it can
 // also be used to verify that later transforms have not found a way to break
 // safepoint semenatics.
 //
-// In its current form, this verify checks a property which is sufficient, but
-// not neccessary for correctness.  There are some cases where an unrelocated
+// In its current form, this verifier checks a property which is sufficient, but
+// not neccessary for correctness. There are some cases where an unrelocated
 // pointer can be used after the safepoint.  Consider this example:
 //
 //    a = ...
 //    b = ...
 //    (a',b') = safepoint(a,b)
 //    c = cmp eq a b
 //    br c, ..., ....
 //
 // 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.  Today, the verifier would report a spurious failure on
-// this case.
+// idioms like this. The verifier catches such cases and avoids false
+// positives.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/SetOperations.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/Dominators.h"
DEBUG(dbgs() << "Transfered block " << BB->getName() << " from ";
         PrintValueSet(dbgs(), AvailableIn.begin(), AvailableIn.end());
         dbgs() << " to ";
         PrintValueSet(dbgs(), AvailableOut.begin(), AvailableOut.end());
         dbgs() << "\n";);
 }
 
 /// Return true if V is exclusively derived off a constant base, i.e. all
 /// operands of non-unary operators (phi/select) are derived off a constant
-/// base.
+/// base. isExclusivelyDerivedFromNull is set to true only if the constant base
+/// that V is derived from is exclusively null. We use this to make a
+/// distinction between null and non-null constants when identifying valid uses of
+/// unrelocated pointers.
 static bool
 isExclusivelyConstantDerivedRecursive(const Value *V,
-                                      DenseSet<const Value *> &Visited) {
+                                      DenseSet<const Value *> &Visited,
+                                      bool &isExclusivelyDerivedFromNull) {
   if (!Visited.insert(V).second)
     return true;
 
-  if (isa<Constant>(V))
+  if (isa<Constant>(V)) {
+    if ( V != Constant::getNullValue(V->getType()))
+      isExclusivelyDerivedFromNull = false;
     return true;
+  }
 
   if (const auto *CI = dyn_cast<CastInst>(V))
-    return isExclusivelyConstantDerivedRecursive(CI->stripPointerCasts(),
-                                                 Visited);
+    return isExclusivelyConstantDerivedRecursive(
+        CI->stripPointerCasts(), Visited, isExclusivelyDerivedFromNull);
 
   if (const auto *GEP = dyn_cast<GetElementPtrInst>(V))
-    return isExclusivelyConstantDerivedRecursive(GEP->getPointerOperand(),
-                                                 Visited);
+    return isExclusivelyConstantDerivedRecursive(
+        GEP->getPointerOperand(), Visited, isExclusivelyDerivedFromNull);
 
   // All operands of the phi and select nodes should be derived off a constant
   // base.
   if (const auto *PN = dyn_cast<PHINode>(V)) {
     return all_of(PN->incoming_values(), [&](const Value *InV) {
-      return isExclusivelyConstantDerivedRecursive(InV, Visited);
+      return isExclusivelyConstantDerivedRecursive(
+          InV, Visited, isExclusivelyDerivedFromNull);
     });
   }
 
   if (const auto *SI = dyn_cast<SelectInst>(V))
-    return isExclusivelyConstantDerivedRecursive(SI->getTrueValue(), Visited) &&
-           isExclusivelyConstantDerivedRecursive(SI->getFalseValue(), Visited);
+    return isExclusivelyConstantDerivedRecursive(
+               SI->getTrueValue(), Visited, isExclusivelyDerivedFromNull) &&
+           isExclusivelyConstantDerivedRecursive(SI->getFalseValue(), Visited,
+                                                 isExclusivelyDerivedFromNull);
 
   return false;
 }
 
 static bool isExclusivelyConstantDerived(const Value *V) {
   DenseSet<const Value*> Visited;
-  return isExclusivelyConstantDerivedRecursive(V, Visited);
+  bool dummy;
+  return isExclusivelyConstantDerivedRecursive(V, Visited, dummy);
+}
+
+/// A given derived pointer can have multiple base pointers through phi/selects.
+/// This type indicates when the base pointer is exclusively constant
+/// (ExclusivelySomeConstant), and if that constant is proven to be exclusively
+/// null, we record that as ExclusivelyNull. In all other cases, the BaseType is
+/// NonConstant.
+enum BaseType {
+  NonConstant = 1, // Base pointers is not exclusively constant.
+  ExclusivelyNull,
+  ExclusivelySomeConstant // Base pointers for a given derived pointer is from a set of constants, but they are not exclusively null.
+};
+
+/// Return the baseType which states whether the base type is exclusively a
+/// constant, and if that constant is exclusively null.
+static enum BaseType getBaseType(const Value *V) {
+
+  DenseSet<const Value*> Visited;
+  bool isExclusivelyDerivedFromNull = true;
+  return !isExclusivelyConstantDerivedRecursive(V, Visited,
+                                                isExclusivelyDerivedFromNull)
+             ? BaseType::NonConstant
+             : (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)
for (const Instruction &I : BB) {
           for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
             const BasicBlock *InBB = PN->getIncomingBlock(i);
             const Value *InValue = PN->getIncomingValue(i);
 
             if (!isExclusivelyConstantDerived(InValue) &&
                 !BlockMap[InBB]->AvailableOut.count(InValue))
               ReportInvalidUse(*InValue, *PN);
           }
-      } else {
+      } 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);
+
+        auto hasValidUnrelocatedUse = [&AvailableSet, 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;
+            // 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 proven to be invalid.
+          if (baseTyLHS == BaseType::NonConstant && !AvailableSet.count(LHS))
+            ReportInvalidUse(*LHS, I);
+          if (baseTyRHS == BaseType::NonConstant && !AvailableSet.count(RHS))
+            ReportInvalidUse(*RHS, I);
+        }
+      }
+      else {
         for (const Value *V : I.operands())
           if (containsGCPtrType(V->getType()) &&
               !isExclusivelyConstantDerived(V) && !AvailableSet.count(V))
             ReportInvalidUse(*V, I);
       }
 
       bool Cleared = false;
       TransferInstruction(I, Cleared, AvailableSet);

test/SafepointIRVerifier/compares.ll

+; RUN: opt -safepoint-ir-verifier-print-only -verify-safepoint-ir -S %s 2>&1 | FileCheck %s
+
+; In some cases, it is valid to have unrelocated pointers used as compare
+; operands. Make sure the verifier knows to spot these exceptions.
+
+
+; comparison against null.
+define i8 addrspace(1)* @test1(i64 %arg, i8 addrspace(1)* %addr) gc "statepoint-example" {
+; CHECK: No illegal uses found by SafepointIRVerifier in: test1
+entry:
+  %load_addr = getelementptr i8, i8 addrspace(1)* %addr, 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 5, i32 0, i32 -1, i32 0, i32 0, i32 0)
+  %cmp = icmp eq i8 addrspace(1)* %load_addr, null
+  ret i8 addrspace(1)* null
+}
+
+; comparison against exclusively derived null.
+define void @test2(i64 %arg, i1 %cond, i8 addrspace(1)* %addr) gc "statepoint-example" {
+; CHECK: No illegal uses found by SafepointIRVerifier in: test2
+  %load_addr = getelementptr i8, i8 addrspace(1)* null, i64 %arg
+  %load_addr_sel = select i1 %cond, i8 addrspace(1)* null, i8 addrspace(1)* %load_addr
+  %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)
+  %cmp = icmp eq i8 addrspace(1)* %addr, %load_addr_sel
+  ret void
+}
+
+; comparison against a constant non-null pointer. This is unrelocated use, since
+; that pointer bits may mean something in a VM.
+define void @test3(i64 %arg, i32 addrspace(1)* %addr) gc "statepoint-example" {
+; CHECK-LABEL: Verifying gc pointers in function: test3
+; CHECK: Illegal use of unrelocated value found!
+entry:
+  %load_addr = getelementptr i32, i32 addrspace(1)* %addr, i64 %arg
+  %load_addr_const = getelementptr i32, i32 addrspace(1)* inttoptr (i64 15 to i32 addrspace(1)*), 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 5, i32 0, i32 -1, i32 0, i32 0, i32 0)
+  %cmp = icmp eq i32 addrspace(1)* %load_addr, %load_addr_const
+  ret void
+}
+
+; comparison against a derived pointer that is *not* exclusively derived from
+; null. An unrelocated use since the derived pointer could be from the constant
+; non-null pointer (load_addr.2).
+define void @test4(i64 %arg, i1 %cond, i8 addrspace(1)* %base) gc "statepoint-example" {
+; CHECK-LABEL: Verifying gc pointers in function: test4
+; CHECK: Illegal use of unrelocated value found!
+entry:
+  %load_addr.1 = getelementptr i8, i8 addrspace(1)* null, i64 %arg
+  br i1 %cond, label %split, label %join
+
+split:
+  %load_addr.2 = getelementptr i8, i8 addrspace(1)* inttoptr (i64 30 to i8 addrspace(1)*), i64 %arg
+  br label %join
+
+join:
+  %load_addr = phi i8 addrspace(1)* [%load_addr.1, %entry], [%load_addr.2, %split]
+  %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)
+  %cmp = icmp eq i8 addrspace(1)* %load_addr, %base
+  ret void
+}
+
+; comparison between 2 unrelocated base pointers.
+; Since the cmp can be reordered legally before the safepoint, these are correct
+; unrelocated uses of the pointers.
+define void @test5(i64 %arg, i8 addrspace(1)* %base1, i8 addrspace(1)* %base2) gc "statepoint-example" {
+; CHECK: No illegal uses found by SafepointIRVerifier in: test5
+  %load_addr1 = getelementptr i8, i8 addrspace(1)* %base1, i64 %arg
+  %load_addr2 = getelementptr i8, i8 addrspace(1)* %base2, 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 5, i32 0, i32 -1, i32 0, i32 0, i32 0)
+  %cmp = icmp eq i8 addrspace(1)* %load_addr1, %load_addr2
+  ret void
+}
+
+; comparison between a relocated and an unrelocated pointer.
+; this is invalid use of the unrelocated pointer.
+define void @test6(i64 %arg, i8 addrspace(1)* %base1, i8 addrspace(1)* %base2) gc "statepoint-example" {
+; CHECK-LABEL: Verifying gc pointers in function: test6
+; CHECK: Illegal use of unrelocated value found!
+  %load_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)
+  %ptr2.relocated = call i8 addrspace(1)* @llvm.experimental.gc.relocate.p1i8(token %safepoint_token, i32 7, i32 7) ; base2, base2
+  %cmp = icmp eq i8 addrspace(1)* %load_addr1, %ptr2.relocated
+  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)