[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 ↗

(On Diff #105429)

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 ↗

(On Diff #105429)

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 ↗

(On Diff #105429)

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 ↗

(On Diff #105429)

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 ↗

(On Diff #105429)

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

[anna]

rebased over the NFC refactoring.

[skatkov]

lib/IR/SafepointIRVerifier.cpp

390 ↗

(On Diff #105429)

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

llvm/trunk/lib/IR/SafepointIRVerifier.cpp

 //    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 knows about these cases and avoids reporting
+// 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"
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 (isNotExclusivelyConstantDerived(InValue) &&
                 !BlockMap[InBB]->AvailableOut.count(InValue))
               ReportInvalidUse(*InValue, *PN);
           }
+      } else if (isa<CmpInst>(I) &&
+                 containsGCPtrType(I.getOperand(0)->getType())) {
+        Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
+        enum BaseType baseTyLHS = getBaseType(LHS),
+                      baseTyRHS = getBaseType(RHS);
+
+        // Returns true if LHS and RHS are unrelocated pointers and they are
+        // valid unrelocated uses.
+        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 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()) &&
               isNotExclusivelyConstantDerived(V) && !AvailableSet.count(V))
             ReportInvalidUse(*V, I);
       }
 
       bool Cleared = false;

llvm/trunk/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)