Index: lib/IR/SafepointIRVerifier.cpp =================================================================== --- lib/IR/SafepointIRVerifier.cpp +++ lib/IR/SafepointIRVerifier.cpp @@ -237,6 +237,58 @@ /// Builds BasicBlockState for each BB of the function. /// It can traverse function for verification and provides all required /// information. +/// +/// GC pointer may be in one of three states: relocated, unrelocated and +/// poisoned. +/// Relocated pointer may be used without any restrictions. +/// Unrelocated pointer cannot be dereferenced, passed as argument to any call +/// or returned. Unrelocated pointer may be safely compared against another +/// unrelocated pointer or against a pointer derived from null. +/// Poisoned pointers are produced when we somehow merge relocated and +/// unrelocated pointers (e.g. phi, select). This pointers may be safely used +/// in a very limited number of situations. Currently the only way to use it is +/// comparison against constant exclusively derived from null. All limitations +/// arise due to its undefined state: this pointers should be treated as +/// relocated and unrelocated simultaneously. +/// Merge rules: +/// R + U = P - that's where the poison comes from +/// P + P = P +/// P + U = P +/// P + R = P +/// U + U = U +/// R + R = R +/// Where "+" - any operation that somehow merge pointers, U - unrelocated, +/// R - relocated and P - poisoned. Merge with constant doesn't change anything. +/// Merge of pointers by itself is always safe, deriving one pointer from +/// another is always safe too. Derived pointer always has the same state as its +/// base. +/// NOTE: when we are making decision on the status of instruction's result: +/// a) for phi we need to check status of each input *at the end of +/// corresponding predicessor BB*. +/// b) for other instructions we need to check status of each input *at the +/// current point*. +/// +/// FIXME: This works fairly well except one case +/// p = *some GC-ptr def* +/// p1 = gep p, offset +/// / | +/// / | +/// safepoint | +/// \ | +/// \ | +/// p2 = phi [p] [p1] +/// p3 = phi [p] [p] +/// here p and p1 is unrelocated +/// p2 and p3 is poisoned (though they shouldn't be) +/// +/// This leads to some weird results: +/// cmp eq p, p2 - illegal instruction (false-positive) +/// cmp eq p1, p2 - illegal instruction (false-positive) +/// cmp eq p, p3 - illegal instruction (false-positive) +/// cmp eq p, p1 - ok +/// To fix this we need to introduce conception of generations and be able to +/// check if two values belong to one generation or not. This way p2 will be +/// considered to be unrelocated and no false alarm will happen. class GCPtrTracker { const Function &F; SpecificBumpPtrAllocator BSAllocator; @@ -244,6 +296,9 @@ // This set contains defs of unrelocated pointers that are proved to be legal // and don't need verification. DenseSet ValidUnrelocatedDefs; + // This set contains poisoned defs. They can be safely ignored during + // verification too. + DenseSet PoisonedDefs; public: GCPtrTracker(const Function &F, const DominatorTree &DT); @@ -251,6 +306,8 @@ BasicBlockState *getBasicBlockState(const BasicBlock *BB); const BasicBlockState *getBasicBlockState(const BasicBlock *BB) const; + bool isValuePoisoned(const Value *V) const { return PoisonedDefs.count(V); } + /// Traverse each BB of the function and call /// InstructionVerifier::verifyInstruction for each possibly invalid /// instruction. @@ -349,7 +406,7 @@ } bool GCPtrTracker::instructionMayBeSkipped(const Instruction *I) const { - return ValidUnrelocatedDefs.count(I); + return ValidUnrelocatedDefs.count(I) || PoisonedDefs.count(I); } void GCPtrTracker::verifyFunction(GCPtrTracker &&Tracker, @@ -419,30 +476,74 @@ AvailableValueSet AvailableSet = BBS->AvailableIn; bool ContributionChanged = false; for (const Instruction &I : *BB) { - bool ProducesUnrelocatedPointer = false; - if ((isa(I) || isa(I)) && - containsGCPtrType(I.getType())) { - // GEP/bitcast of unrelocated pointer is legal by itself but this - // def shouldn't appear in any AvailableSet. + bool ValidUnrelocatedPointerDef = false; + bool PoisonedPointerDef = false; + if (const PHINode *PN = dyn_cast(&I)) { + if (containsGCPtrType(PN->getType())) { + // If both is true, output is poisoned. + bool HasRelocatedInputs = false; + bool HasUnrelocatedInputs = false; + 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)) { + if (isValuePoisoned(InValue)) { + // If any of inputs is poisoned, output is always poisoned too. + HasRelocatedInputs = true; + HasUnrelocatedInputs = true; + break; + } + if (BlockMap[InBB]->AvailableOut.count(InValue)) + HasRelocatedInputs = true; + else + HasUnrelocatedInputs = true; + } + } + if (HasUnrelocatedInputs) { + if (HasRelocatedInputs) + PoisonedPointerDef = true; + else + ValidUnrelocatedPointerDef = true; + } + } + } else if ((isa(I) || isa(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)) { - ProducesUnrelocatedPointer = true; + if (isValuePoisoned(V)) + PoisonedPointerDef = true; + else + ValidUnrelocatedPointerDef = true; break; } } - if (!ProducesUnrelocatedPointer) { - 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 its successors. + assert(!(ValidUnrelocatedPointerDef && PoisonedPointerDef) && + "Value cannot be both unrelocated and poisoned!"); + if (ValidUnrelocatedPointerDef) { + // Remove def of unrelocated pointer from Contribution of this BB and + // trigger update of all its successors. Contribution.erase(&I); + PoisonedDefs.erase(&I); ValidUnrelocatedDefs.insert(&I); DEBUG(dbgs() << "Removing " << I << " from Contribution of " - << BB->getName() << "\n"); + << BB->getName() << " ; it's unrelocated\n"); ContributionChanged = true; + } else if (PoisonedPointerDef) { + // Mark pointer as poisoned, remove its def from Contribution and trigger + // update of all successors. + Contribution.erase(&I); + PoisonedDefs.insert(&I); + DEBUG(dbgs() << "Removing " << I << " from Contribution of " + << BB->getName() << " ; it's poisoned\n"); + ContributionChanged = true; + } else { + bool Cleared = false; + transferInstruction(I, Cleared, AvailableSet); + (void)Cleared; } } return ContributionChanged; @@ -524,8 +625,8 @@ // Returns true if LHS and RHS are unrelocated pointers and they are // valid unrelocated uses. - auto hasValidUnrelocatedUse = [&AvailableSet, baseTyLHS, baseTyRHS, &LHS, - &RHS] () { + auto hasValidUnrelocatedUse = [&AvailableSet, Tracker, 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 @@ -545,12 +646,23 @@ (baseTyLHS == BaseType::NonConstant && baseTyRHS == BaseType::ExclusivelySomeConstant)) return false; + + // If one of pointers is poisoned and other is not exclusively null + // it is an invalid expression: it produces poisoned result and + // unless we want to track all defs (not only gc pointers) the only + // option is to prohibit such instructions. + if ((Tracker->isValuePoisoned(LHS) && baseTyRHS != ExclusivelyNull) || + (Tracker->isValuePoisoned(RHS) && baseTyLHS != ExclusivelyNull)) + return false; + // All other cases are valid cases enumerated below: - // 1. Comparison between an exlusively derived null pointer and a + // 1. Comparison between an exclusively derived null pointer and a // constant base pointer. - // 2. Comparison between an exlusively derived null pointer and a + // 2. Comparison between an exclusively derived null pointer and a // non-constant unrelocated base pointer. // 3. Comparison between 2 unrelocated pointers. + // 4. Comparison between an exclusively derived null pointer and a + // non-constant poisoned pointer. return true; }; if (!hasValidUnrelocatedUse()) { Index: test/SafepointIRVerifier/unrecorded-live-at-sp.ll =================================================================== --- test/SafepointIRVerifier/unrecorded-live-at-sp.ll +++ test/SafepointIRVerifier/unrecorded-live-at-sp.ll @@ -1,8 +1,9 @@ ; RUN: opt %s -safepoint-ir-verifier-print-only -verify-safepoint-ir -S 2>&1 | FileCheck %s ; CHECK: Illegal use of unrelocated value found! -; CHECK-NEXT: Def: %base_phi3 = phi %jObject addrspace(1)* [ %obj609.relocated, %not_zero146 ], [ %base_phi2, %bci_37-aload ], !is_base_value !0 -; CHECK-NEXT: Use: %base_phi2 = phi %jObject addrspace(1)* [ %base_phi3, %not_zero179 ], [ %cast5, %bci_0 ], !is_base_value !0 +; CHECK-NEXT: Def: %base_phi4 = phi %jObject addrspace(1)* addrspace(1)* [ %addr98.relocated, %not_zero146 ], [ %cast6, %bci_37-aload ], !is_base_value !0 +; CHECK-NEXT: Use: %safepoint_token = tail call token (i64, i32, i32 ()*, i32, i32, ...) @llvm.experimental.gc.statepoint.p0f_i32f(i64 0, i32 0, i32 ()* undef, i32 0, i32 0, i32 0, i32 5, i32 0, i32 0, i32 0, i32 0, i32 0, %jObject addrspace(1)* %base_phi1, %jObject addrspace(1)* addrspace(1)* %base_phi4, %jObject addrspace(1)* addrspace(1)* %relocated4, %jObject addrspace(1)* %relocated7) + %jObject = type { [8 x i8] } Index: test/SafepointIRVerifier/uses-in-phi-nodes.ll =================================================================== --- test/SafepointIRVerifier/uses-in-phi-nodes.ll +++ test/SafepointIRVerifier/uses-in-phi-nodes.ll @@ -14,9 +14,9 @@ merge: ; CHECK: Illegal use of unrelocated value found! -; CHECK-NEXT: Def: i8 addrspace(1)* %arg -; CHECK-NEXT: Use: %val = phi i8 addrspace(1)* [ %arg, %left ], [ %arg, %right ] - %val = phi i8 addrspace(1)* [ %arg, %left ], [ %arg, %right] +; CHECK-NEXT: Def: %val = phi i8 addrspace(1)* [ %arg, %left ], [ %arg, %right ] +; CHECK-NEXT: Use: ret i8 addrspace(1)* %val + %val = phi i8 addrspace(1)* [ %arg, %left ], [ %arg, %right ] ret i8 addrspace(1)* %val } @@ -34,9 +34,9 @@ merge: ; CHECK: Illegal use of unrelocated value found! -; CHECK-NEXT: Def: i8 addrspace(1)* %arg -; CHECK-NEXT: Use: %val = phi i8 addrspace(1)* [ %arg, %left ], [ null, %right ] - %val = phi i8 addrspace(1)* [ %arg, %left ], [ null, %right] +; CHECK-NEXT: Def: %val = phi i8 addrspace(1)* [ %arg, %left ], [ null, %right ] +; CHECK-NEXT: Use: ret i8 addrspace(1)* %val + %val = phi i8 addrspace(1)* [ %arg, %left ], [ null, %right ] ret i8 addrspace(1)* %val } @@ -74,5 +74,99 @@ ret i8 addrspace(1)* %val } +; It should be allowed to compare poisoned ptr with null. +define void @test.poisoned.cmp.ok(i8 addrspace(1)* %arg) gc "statepoint-example" { +; CHECK-LABEL: Verifying gc pointers in function: test.poisoned.cmp.ok + bci_0: + br i1 undef, label %left, label %right + + left: + %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)* %arg , i32 -1, i32 0, i32 0, i32 0) + %arg.relocated = call i8 addrspace(1)* @llvm.experimental.gc.relocate.p1i8(token %safepoint_token, i32 7, i32 7) ; arg, arg + br label %merge + + right: + %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)* %arg , i32 -1, i32 0, i32 0, i32 0) + br label %merge + + merge: +; CHECK: No illegal uses found by SafepointIRVerifier in: test.poisoned.cmp.ok + %val.poisoned = phi i8 addrspace(1)* [ %arg.relocated, %left ], [ %arg, %right ] + %c = icmp eq i8 addrspace(1)* %val.poisoned, null + ret void +} + +; It is illegal to compare poisoned ptr and relocated. +define void @test.poisoned.cmp.fail.0(i8 addrspace(1)* %arg) gc "statepoint-example" { +; CHECK-LABEL: Verifying gc pointers in function: test.poisoned.cmp.fail.0 + bci_0: + br i1 undef, label %left, label %right + + left: + %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)* %arg , i32 -1, i32 0, i32 0, i32 0) + %arg.relocated = call i8 addrspace(1)* @llvm.experimental.gc.relocate.p1i8(token %safepoint_token, i32 7, i32 7) ; arg, arg + br label %merge + + right: + %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)* %arg , i32 -1, i32 0, i32 0, i32 0) + %arg.relocated2 = call i8 addrspace(1)* @llvm.experimental.gc.relocate.p1i8(token %safepoint_token2, i32 7, i32 7) ; arg, arg + br label %merge + + merge: +; CHECK: Illegal use of unrelocated value found! +; CHECK-NEXT: Def: %val.poisoned = phi i8 addrspace(1)* [ %arg.relocated, %left ], [ %arg, %right ] +; CHECK-NEXT: Use: %c = icmp eq i8 addrspace(1)* %val.poisoned, %val + %val.poisoned = phi i8 addrspace(1)* [ %arg.relocated, %left ], [ %arg, %right ] + %val = phi i8 addrspace(1)* [ %arg.relocated, %left ], [ %arg.relocated2, %right ] + %c = icmp eq i8 addrspace(1)* %val.poisoned, %val + ret void +} + +; It is illegal to compare poisoned ptr and unrelocated. +define void @test.poisoned.cmp.fail.1(i8 addrspace(1)* %arg) gc "statepoint-example" { +; CHECK-LABEL: Verifying gc pointers in function: test.poisoned.cmp.fail.1 + bci_0: + br i1 undef, label %left, label %right + + left: + %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)* %arg , i32 -1, i32 0, i32 0, i32 0) + %arg.relocated = call i8 addrspace(1)* @llvm.experimental.gc.relocate.p1i8(token %safepoint_token, i32 7, i32 7) ; arg, arg + br label %merge + + right: + %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)* %arg , i32 -1, i32 0, i32 0, i32 0) + %arg.relocated2 = call i8 addrspace(1)* @llvm.experimental.gc.relocate.p1i8(token %safepoint_token2, i32 7, i32 7) ; arg, arg + br label %merge + + merge: +; CHECK: Illegal use of unrelocated value found! +; CHECK-NEXT: Def: %val.poisoned = phi i8 addrspace(1)* [ %arg.relocated, %left ], [ %arg, %right ] +; CHECK-NEXT: Use: %c = icmp eq i8 addrspace(1)* %val.poisoned, %arg + %val.poisoned = phi i8 addrspace(1)* [ %arg.relocated, %left ], [ %arg, %right ] + %c = icmp eq i8 addrspace(1)* %val.poisoned, %arg + ret void +} + +; It should be allowed to compare unrelocated phi with unrelocated value. +define void @test.unrelocated-phi.cmp.ok(i8 addrspace(1)* %arg) gc "statepoint-example" { +; CHECK-LABEL: Verifying gc pointers in function: test.unrelocated-phi.cmp.ok + bci_0: + br i1 undef, label %left, label %right + + left: + %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) + br label %merge + + right: + br label %merge + + merge: +; CHECK: No illegal uses found by SafepointIRVerifier in: test.unrelocated-phi.cmp.ok + %val.unrelocated = phi i8 addrspace(1)* [ %arg, %left ], [ null, %right ] + %c = icmp eq i8 addrspace(1)* %val.unrelocated, %arg + 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) declare void @not_statepoint()