Index: lib/IR/SafepointIRVerifier.cpp =================================================================== --- lib/IR/SafepointIRVerifier.cpp +++ lib/IR/SafepointIRVerifier.cpp @@ -14,8 +14,8 @@ // 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 = ... @@ -26,8 +26,8 @@ // // 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. // //===----------------------------------------------------------------------===// @@ -222,42 +222,78 @@ /// 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 &Visited) { + DenseSet &Visited, + bool &isExclusivelyDerivedFromNull) { if (!Visited.insert(V).second) return true; - if (isa(V)) + if (isa(V)) { + if ( V != Constant::getNullValue(V->getType())) + isExclusivelyDerivedFromNull = false; return true; + } if (const auto *CI = dyn_cast(V)) - return isExclusivelyConstantDerivedRecursive(CI->stripPointerCasts(), - Visited); + return isExclusivelyConstantDerivedRecursive( + CI->stripPointerCasts(), Visited, isExclusivelyDerivedFromNull); if (const auto *GEP = dyn_cast(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(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(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 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 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) { @@ -338,7 +374,49 @@ !BlockMap[InBB]->AvailableOut.count(InValue)) ReportInvalidUse(*InValue, *PN); } - } else { + } else if (isa(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)) Index: test/SafepointIRVerifier/compares.ll =================================================================== --- /dev/null +++ test/SafepointIRVerifier/compares.ll @@ -0,0 +1,85 @@ +; 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)