Index: lib/IR/SafepointIRVerifier.cpp =================================================================== --- lib/IR/SafepointIRVerifier.cpp +++ lib/IR/SafepointIRVerifier.cpp @@ -168,7 +168,7 @@ 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) @@ -190,23 +190,21 @@ 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) { +/// Compute the AvailableOut set for BB, based on the BasicBlockState BBS, +/// which is the BasicBlockState for BB. +/// isContributionChanged is set when the verifier runs for the first time +/// (in this case Contribution was changed from 'empty' to its initial state) or +/// when Contribution of this BB was changed since last computation. +static void TransferBlock(const BasicBlock *BB, BasicBlockState &BBS, + bool isContributionChanged) { - const DenseSet &AvailableIn = BBS.AvailableIn; + const DenseSet &AvailableIn = BBS.AvailableIn; DenseSet &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 will change only when Contribution changed. + if (isContributionChanged) AvailableOut = BBS.Contribution; - } } else { // Otherwise, we need to reduce the AvailableOut set by things which are no // longer in our AvailableIn @@ -293,32 +291,28 @@ : BaseType::ExclusivelySomeConstant; } -static void Verify(const Function &F, const DominatorTree &DT) { - SpecificBumpPtrAllocator BSAllocator; - DenseMap 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); - } - +using BlockStateMap = DenseMap; + +/// This function iterates over all BBs from BlockMap and recalculates +/// AvailableIn/Out for each of them until it converges. +/// It calls Visitor for each visited BB after updating it's AvailableIn. +/// Visitor may change BB's Contribution and should return true it this case. +/// +/// Visitor is expected to have following signature: +/// (const BasicBlock *BB, const BasicBlockState *BBS, +/// DenseSet &Contribution) -> bool +/// TODO: this function, TransferBlock, TransferInstruction and others should be +/// moved to a separate class which will hold all the logic related to +/// BasicBlockState. +template +static void RecalculateBBsStates(BlockStateMap &BlockMap, VisitorTy &&Visitor) { + // TODO: It would be better if worklist will work as a queue (not as a stack). + // This way this algorithm will converge faster. SetVector Worklist; for (auto &BBI : BlockMap) Worklist.insert(BBI.first); - // This loop iterates the AvailableIn and AvailableOut sets to a fixed point. + // This loop iterates the AvailableIn/Out sets until it converges. // The AvailableIn and AvailableOut sets decrease as we iterate. while (!Worklist.empty()) { const BasicBlock *BB = Worklist.pop_back_val(); @@ -328,18 +322,50 @@ 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!"); - assert(OldInCount > BBS->AvailableIn.size() && "invariant!"); + bool isInputsChanged = OldInCount != BBS->AvailableIn.size(); + bool isContributionChanged = Visitor(BB, BBS, BBS->Contribution); + if (!isInputsChanged && !isContributionChanged) + continue; size_t OldOutCount = BBS->AvailableOut.size(); - TransferBlock(BB, *BBS, false); + TransferBlock(BB, *BBS, isContributionChanged); if (OldOutCount != BBS->AvailableOut.size()) { - assert(OldOutCount > BBS->AvailableOut.size() && "invariant!"); + assert(OldOutCount >= BBS->AvailableOut.size() && "invariant!"); + // TODO: It is better to add successors to a worklist in topological order + // (if any). It will decrease number of iterations required to converge. Worklist.insert(succ_begin(BB), succ_end(BB)); } } +} + +static void Verify(const Function &F, const DominatorTree &DT) { + SpecificBumpPtrAllocator BSAllocator; + BlockStateMap 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); + } + + RecalculateBBsStates(BlockMap, [] (const BasicBlock *, + const BasicBlockState *, + DenseSet &) { + return false; + }); // 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. @@ -360,10 +386,48 @@ return getBaseType(V) == BaseType::NonConstant; }; + // This set contains defs that can be safely ignored during verification. + DenseSet ValidUnrelocatedDefs; + + // Now we can remove all valid unrelocated gc pointer defs from all BBS sets. + RecalculateBBsStates(BlockMap, [&] (const BasicBlock *BB, + const BasicBlockState *BBS, + DenseSet &Contribution) { + DenseSet AvailableSet = BBS->AvailableIn; + bool isContributionChanged = false; + for (const Instruction &I : *BB) { + bool isProducesUnrelocatedPointer = 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. + for (const Value *V : I.operands()) + if (containsGCPtrType(V->getType()) && + isNotExclusivelyConstantDerived(V) && !AvailableSet.count(V)) { + isProducesUnrelocatedPointer = true; + break; + } + } + if (!isProducesUnrelocatedPointer) { + 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 it's successors. + Contribution.erase(&I); + ValidUnrelocatedDefs.insert(&I); + DEBUG(dbgs() << "Removing " << I << " from Contribution of " + << BB->getName() << "\n"); + isContributionChanged = true; + } + } + return isContributionChanged; + }); + for (const BasicBlock &BB : F) { - // We destructively modify AvailableIn as we traverse the block instruction - // by instruction. - DenseSet &AvailableSet = BlockMap[&BB]->AvailableIn; + BasicBlockState *BBS = BlockMap[&BB]; + DenseSet &AvailableSet = BBS->AvailableIn; for (const Instruction &I : BB) { if (const PHINode *PN = dyn_cast(&I)) { if (containsGCPtrType(PN->getType())) @@ -419,6 +483,8 @@ if (baseTyRHS == BaseType::NonConstant && !AvailableSet.count(RHS)) ReportInvalidUse(*RHS, I); } + } else if (ValidUnrelocatedDefs.count(&I)) { + continue; // This instruction shouldn't be added to AvailableSet } else { for (const Value *V : I.operands()) if (containsGCPtrType(V->getType()) && Index: test/SafepointIRVerifier/use-derived-unrelocated.ll =================================================================== --- /dev/null +++ test/SafepointIRVerifier/use-derived-unrelocated.ll @@ -0,0 +1,149 @@ +; RUN: opt -safepoint-ir-verifier-print-only -verify-safepoint-ir -S %s 2>&1 | FileCheck %s + +; Checking if verifier accepts chain of GEPs/bitcasts. +define void @test.deriving.ok(i32, i8 addrspace(1)* %base1, i8 addrspace(1)* %base2) gc "statepoint-example" { +; CHECK-LABEL: Verifying gc pointers in function: test.deriving.ok +; CHECK-NEXT: No illegal uses found by SafepointIRVerifier in: test.deriving.ok + %ptr = getelementptr i8, i8 addrspace(1)* %base1, i64 4 + %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) + %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)* + ret void +} + +; Checking if verifier accepts cmp of two derived pointers when one defined +; before safepoint and one after and both have unrelocated base. +define void @test.cmp.ok(i32, 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 + %ptr = getelementptr i8, i8 addrspace(1)* %base1, i64 4 + %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) + %ptr2 = getelementptr i8, i8 addrspace(1)* %base2, i64 8 + %c2 = icmp sgt i8 addrspace(1)* %ptr2, %ptr + ret void +} + +; Checking if verifier accepts cmp of two derived pointers when one defined +; before safepoint and one after and both have unrelocated base. One of pointers +; defined as a long chain of geps/bitcasts. +define void @test.cmp-long_chain.ok(i32, i8 addrspace(1)* %base1, i8 addrspace(1)* %base2) gc "statepoint-example" { +; CHECK-LABEL: Verifying gc pointers in function: test.cmp-long_chain.ok +; CHECK-NEXT: No illegal uses found by SafepointIRVerifier in: test.cmp-long_chain.ok + %ptr = getelementptr i8, i8 addrspace(1)* %base1, i64 4 + %ptr.i32 = bitcast i8 addrspace(1)* %ptr to i32 addrspace(1)* + %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) + %ptr2 = getelementptr i8, i8 addrspace(1)* %base2, i64 8 + %ptr2.i32 = bitcast i8 addrspace(1)* %ptr2 to i32 addrspace(1)* + %ptr2.i32.2 = getelementptr i32, i32 addrspace(1)* %ptr2.i32, i64 4 + %ptr2.i32.3 = getelementptr i32, i32 addrspace(1)* %ptr2.i32.2, i64 8 + %ptr2.i32.4 = getelementptr i32, i32 addrspace(1)* %ptr2.i32.3, i64 8 + %ptr2.i32.5 = getelementptr i32, i32 addrspace(1)* %ptr2.i32.4, i64 8 + %ptr2.i32.6 = getelementptr i32, i32 addrspace(1)* %ptr2.i32.5, i64 8 + %ptr2.i32.6.i8 = bitcast i32 addrspace(1)* %ptr2.i32.6 to i8 addrspace(1)* + %ptr2.i32.6.i8.i32 = bitcast i8 addrspace(1)* %ptr2.i32.6.i8 to i32 addrspace(1)* + %ptr2.i32.6.i8.i32.2 = getelementptr i32, i32 addrspace(1)* %ptr2.i32.6.i8.i32, i64 8 + %c2 = icmp sgt i32 addrspace(1)* %ptr2.i32.6.i8.i32.2, %ptr.i32 + ret void +} + +; GEP and bitcast of unrelocated pointer is acceptable, but load by resulting +; pointer should be reported. +define void @test.load.fail(i32, i8 addrspace(1)* %base) gc "statepoint-example" { +; CHECK-LABEL: Verifying gc pointers in function: test.load.fail + %ptr = getelementptr i8, i8 addrspace(1)* %base, i64 4 + %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) + %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 +} + +; Comparison between pointer derived from unrelocated one (though defined after +; safepoint) and relocated pointer should be reported. +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 +} + +; Same as test.cmp.fail but splitted into two BBs. +define void @test.cmp2.fail(i64 %arg, i8 addrspace(1)* %base1, i8 addrspace(1)* %base2) gc "statepoint-example" { +.b0: +; CHECK-LABEL: Verifying gc pointers in function: test.cmp2.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 + br label %.b1 + +.b1: +; 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 +} + +; Checking that cmp of two unrelocated pointers is OK and load is not. +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) + %addr2 = getelementptr i8, i8 addrspace(1)* %base2, i64 8 + %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 8 +; CHECK-NEXT: Use: %val = load i8, i8 addrspace(1)* %addr2 + %val = load i8, i8 addrspace(1)* %addr2 + ret void +} + +; Same as test.cmp-load.fail but splitted into thee BBs. +define void @test.cmp-load2.fail(i64 %arg, i8 addrspace(1)* %base1, i8 addrspace(1)* %base2) gc "statepoint-example" { +.b0: +; CHECK-LABEL: Verifying gc pointers in function: test.cmp-load2.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) + br label %.b1 + +.b1: + %addr2 = getelementptr i8, i8 addrspace(1)* %base2, i64 8 + br label %.b2 + +.b2: + %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 8 +; CHECK-NEXT: Use: %val = load i8, i8 addrspace(1)* %addr2 + %val = load i8, i8 addrspace(1)* %addr2 + ret void +} + +; Same as test.cmp.ok but with multiple safepoints within one BB. And the last +; one is in the very end of BB so that Contribution of this BB is empty. +define void @test.cmp.multi-sp.ok(i64 %arg, i8 addrspace(1)* %base1, i8 addrspace(1)* %base2) gc "statepoint-example" { +; CHECK-LABEL: Verifying gc pointers in function: test.cmp.multi-sp.ok +; CHECK-NEXT: No illegal uses found by SafepointIRVerifier in: test.cmp.multi-sp.ok + %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 + %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)* %base2.relocated, i32 -1, i32 0, i32 0, i32 0) + %base2.relocated2 = call i8 addrspace(1)* @llvm.experimental.gc.relocate.p1i8(token %safepoint_token2, i32 7, i32 7) ; base2.relocated, base2.relocated + %addr2 = getelementptr i8, i8 addrspace(1)* %base2, i64 %arg + %cmp = icmp eq i8 addrspace(1)* %addr1, %addr2 + %safepoint_token3 = 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.relocated2, i32 -1, i32 0, i32 0, i32 0) + 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) +