Skip to content

Commit

Permalink
[SafepointIRVerifier] Allow deriving pointers from unrelocated base
Browse files Browse the repository at this point in the history 
Summary:
This patch allows to use derived pointers (GEPs/bitcasts) of unrelocated
base pointers. We care only about the uses of these derived pointers.

It is acheived by two changes:
1. When we have enough information to say if the pointer is unrelocated at some
point or not, we walk all BBs to remove from their Contributions all valid defs
of unrelocated pointers (GEP with unrelocated base or bitcast of unrelocated
pointer).
2. When it comes to verification we just ignore instructions that were removed
at stage 1.

Patch by Daniil Suchkov!

Reviewers: anna, reames, apilipenko, mkazantsev

Reviewed By: anna, mkazantsev

Subscribers: llvm-commits

Differential Revision: https://reviews.llvm.org/D40289

llvm-svn: 319838
@annamthomas
annamthomas committed Dec 5, 2017
1 parent 3e40883 commit 7df1a92
Showing 2 changed files with 271 additions and 45 deletions.
167 changes: 122 additions & 45 deletions llvm/lib/IR/SafepointIRVerifier.cpp
View file
Original file line number Diff line number Diff line change
@@ -32,6 +32,7 @@
//===----------------------------------------------------------------------===//

#include "llvm/ADT/DenseSet.h"
#include "llvm/ADT/PostOrderIterator.h"
#include "llvm/ADT/SetOperations.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/IR/BasicBlock.h"
@@ -168,7 +169,7 @@ static void GatherDominatingDefs(const BasicBlock *BB,
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 +191,21 @@ static void TransferInstruction(const Instruction &I, bool &Cleared,
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.
/// ContributionChanged 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 ContributionChanged) {

const DenseSet<const Value *> &AvailableIn = BBS.AvailableIn;
const DenseSet<const Value *> &AvailableIn = BBS.AvailableIn;
DenseSet<const Value *> &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 (ContributionChanged)
AvailableOut = BBS.Contribution;
}
} else {
// Otherwise, we need to reduce the AvailableOut set by things which are no
// longer in our AvailableIn
@@ -293,32 +292,37 @@ static enum BaseType getBaseType(const Value *Val) {
: 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)
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);
}
static bool isNotExclusivelyConstantDerived(const Value *V) {
return getBaseType(V) == BaseType::NonConstant;
}

using BlockStateMap = DenseMap<const BasicBlock *, BasicBlockState *>;

/// 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.
/// BBContributionUpdater may change BB's Contribution and should return true in
/// this case.
///
/// BBContributionUpdater is expected to have following signature:
/// (const BasicBlock *BB, const BasicBlockState *BBS,
/// DenseSet<const Value *> &Contribution) -> bool
/// FIXME: type of BBContributionUpdater is a template parameter because it
/// might be a lambda with arbitrary non-empty capture list. It's a bit ugly and
/// unclear, but other options causes us to spread the logic of
/// RecalculateBBStates across the rest of the algorithm. The solution is to
/// move this function, TransferBlock, TransferInstruction and others to a
/// separate class which will hold all the logic related to BlockStateMap.
template <typename VisitorTy>
static void RecalculateBBsStates(BlockStateMap &BlockMap,
VisitorTy &&BBContributionUpdater) {
SetVector<const BasicBlock *> Worklist;
// TODO: This order is suboptimal, it's better to replace it with priority
// queue where priority is RPO number of BB.
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 +332,49 @@ static void Verify(const Function &F, const DominatorTree &DT) {
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 InputsChanged = OldInCount != BBS->AvailableIn.size();
bool ContributionChanged =
BBContributionUpdater(BB, BBS, BBS->Contribution);
if (!InputsChanged && !ContributionChanged)
continue;

size_t OldOutCount = BBS->AvailableOut.size();
TransferBlock(BB, *BBS, false);
TransferBlock(BB, *BBS, ContributionChanged);
if (OldOutCount != BBS->AvailableOut.size()) {
assert(OldOutCount > BBS->AvailableOut.size() && "invariant!");
Worklist.insert(succ_begin(BB), succ_end(BB));
}
}
}

static void Verify(const Function &F, const DominatorTree &DT) {
SpecificBumpPtrAllocator<BasicBlockState> 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<const Value *> &) {
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.
@@ -356,16 +391,58 @@ static void Verify(const Function &F, const DominatorTree &DT) {
AnyInvalidUses = true;
};

auto isNotExclusivelyConstantDerived = [](const Value *V) {
return getBaseType(V) == BaseType::NonConstant;
};
// This set contains defs that can be safely ignored during verification.
DenseSet<const Instruction *> ValidUnrelocatedDefs;

// Now we can remove all valid unrelocated gc pointer defs from all BBS sets.
RecalculateBBsStates(BlockMap, [&ValidUnrelocatedDefs](
const BasicBlock *BB,
const BasicBlockState *BBS,
DenseSet<const Value *> &Contribution) {
DenseSet<const Value *> AvailableSet = BBS->AvailableIn;
bool ContributionChanged = false;
for (const Instruction &I : *BB) {
bool ProducesUnrelocatedPointer = false;
if ((isa<GetElementPtrInst>(I) || isa<BitCastInst>(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;
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.
Contribution.erase(&I);
ValidUnrelocatedDefs.insert(&I);
DEBUG(dbgs() << "Removing " << I << " from Contribution of "
<< BB->getName() << "\n");
ContributionChanged = true;
}
}
return ContributionChanged;
});

for (const BasicBlock &BB : F) {
// We need RPO here to a) report always the first error b) report errors in
// same order from run to run.
ReversePostOrderTraversal<const Function *> RPOT(&F);
for (const BasicBlock *BB : RPOT) {
BasicBlockState *BBS = BlockMap[BB];
// We destructively modify AvailableIn as we traverse the block instruction
// by instruction.
DenseSet<const Value *> &AvailableSet = BlockMap[&BB]->AvailableIn;
for (const Instruction &I : BB) {
if (const PHINode *PN = dyn_cast<PHINode>(&I)) {
DenseSet<const Value *> &AvailableSet = BBS->AvailableIn;
for (const Instruction &I : *BB) {
if (ValidUnrelocatedDefs.count(&I)) {
continue; // This instruction shouldn't be added to AvailableSet.
} else if (const PHINode *PN = dyn_cast<PHINode>(&I)) {
if (containsGCPtrType(PN->getType()))
for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
const BasicBlock *InBB = PN->getIncomingBlock(i);
149 changes: 149 additions & 0 deletions llvm/test/SafepointIRVerifier/use-derived-unrelocated.ll
View file
Original file line number Diff line number Diff line change
@@ -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)

0 comments on commit 7df1a92

Please sign in to comment.