| //===-- SafepointIRVerifier.cpp - Verify gc.statepoint invariants ---------===// |
| // |
| // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
| // See https://llvm.org/LICENSE.txt for license information. |
| // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
| // |
| //===----------------------------------------------------------------------===// |
| // |
| // Run a basic correctness check on the IR to ensure that Safepoints - if |
| // they've been inserted - were inserted correctly. In particular, look for use |
| // of non-relocated values after a safepoint. It's primary use is to check the |
| // correctness of safepoint insertion immediately after insertion, but it can |
| // 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 |
| // pointer can be used after the safepoint. Consider this example: |
| // |
| // 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. The verifier knows about these cases and avoids reporting |
| // false positives. |
| // |
| //===----------------------------------------------------------------------===// |
| |
| #include "llvm/IR/SafepointIRVerifier.h" |
| #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" |
| #include "llvm/IR/Dominators.h" |
| #include "llvm/IR/Function.h" |
| #include "llvm/IR/Instructions.h" |
| #include "llvm/IR/IntrinsicInst.h" |
| #include "llvm/IR/Intrinsics.h" |
| #include "llvm/IR/Module.h" |
| #include "llvm/IR/Statepoint.h" |
| #include "llvm/IR/Value.h" |
| #include "llvm/InitializePasses.h" |
| #include "llvm/Support/Allocator.h" |
| #include "llvm/Support/CommandLine.h" |
| #include "llvm/Support/Debug.h" |
| #include "llvm/Support/raw_ostream.h" |
| |
| #define DEBUG_TYPE "safepoint-ir-verifier" |
| |
| using namespace llvm; |
| |
| /// This option is used for writing test cases. Instead of crashing the program |
| /// when verification fails, report a message to the console (for FileCheck |
| /// usage) and continue execution as if nothing happened. |
| static cl::opt<bool> PrintOnly("safepoint-ir-verifier-print-only", |
| cl::init(false)); |
| |
| namespace { |
| |
| /// This CFG Deadness finds dead blocks and edges. Algorithm starts with a set |
| /// of blocks unreachable from entry then propagates deadness using foldable |
| /// conditional branches without modifying CFG. So GVN does but it changes CFG |
| /// by splitting critical edges. In most cases passes rely on SimplifyCFG to |
| /// clean up dead blocks, but in some cases, like verification or loop passes |
| /// it's not possible. |
| class CFGDeadness { |
| const DominatorTree *DT = nullptr; |
| SetVector<const BasicBlock *> DeadBlocks; |
| SetVector<const Use *> DeadEdges; // Contains all dead edges from live blocks. |
| |
| public: |
| /// Return the edge that coresponds to the predecessor. |
| static const Use& getEdge(const_pred_iterator &PredIt) { |
| auto &PU = PredIt.getUse(); |
| return PU.getUser()->getOperandUse(PU.getOperandNo()); |
| } |
| |
| /// Return true if there is at least one live edge that corresponds to the |
| /// basic block InBB listed in the phi node. |
| bool hasLiveIncomingEdge(const PHINode *PN, const BasicBlock *InBB) const { |
| assert(!isDeadBlock(InBB) && "block must be live"); |
| const BasicBlock* BB = PN->getParent(); |
| bool Listed = false; |
| for (const_pred_iterator PredIt(BB), End(BB, true); PredIt != End; ++PredIt) { |
| if (InBB == *PredIt) { |
| if (!isDeadEdge(&getEdge(PredIt))) |
| return true; |
| Listed = true; |
| } |
| } |
| (void)Listed; |
| assert(Listed && "basic block is not found among incoming blocks"); |
| return false; |
| } |
| |
| |
| bool isDeadBlock(const BasicBlock *BB) const { |
| return DeadBlocks.count(BB); |
| } |
| |
| bool isDeadEdge(const Use *U) const { |
| assert(cast<Instruction>(U->getUser())->isTerminator() && |
| "edge must be operand of terminator"); |
| assert(cast_or_null<BasicBlock>(U->get()) && |
| "edge must refer to basic block"); |
| assert(!isDeadBlock(cast<Instruction>(U->getUser())->getParent()) && |
| "isDeadEdge() must be applied to edge from live block"); |
| return DeadEdges.count(U); |
| } |
| |
| bool hasLiveIncomingEdges(const BasicBlock *BB) const { |
| // Check if all incoming edges are dead. |
| for (const_pred_iterator PredIt(BB), End(BB, true); PredIt != End; ++PredIt) { |
| auto &PU = PredIt.getUse(); |
| const Use &U = PU.getUser()->getOperandUse(PU.getOperandNo()); |
| if (!isDeadBlock(*PredIt) && !isDeadEdge(&U)) |
| return true; // Found a live edge. |
| } |
| return false; |
| } |
| |
| void processFunction(const Function &F, const DominatorTree &DT) { |
| this->DT = &DT; |
| |
| // Start with all blocks unreachable from entry. |
| for (const BasicBlock &BB : F) |
| if (!DT.isReachableFromEntry(&BB)) |
| DeadBlocks.insert(&BB); |
| |
| // Top-down walk of the dominator tree |
| ReversePostOrderTraversal<const Function *> RPOT(&F); |
| for (const BasicBlock *BB : RPOT) { |
| const Instruction *TI = BB->getTerminator(); |
| assert(TI && "blocks must be well formed"); |
| |
| // For conditional branches, we can perform simple conditional propagation on |
| // the condition value itself. |
| const BranchInst *BI = dyn_cast<BranchInst>(TI); |
| if (!BI || !BI->isConditional() || !isa<Constant>(BI->getCondition())) |
| continue; |
| |
| // If a branch has two identical successors, we cannot declare either dead. |
| if (BI->getSuccessor(0) == BI->getSuccessor(1)) |
| continue; |
| |
| ConstantInt *Cond = dyn_cast<ConstantInt>(BI->getCondition()); |
| if (!Cond) |
| continue; |
| |
| addDeadEdge(BI->getOperandUse(Cond->getZExtValue() ? 1 : 2)); |
| } |
| } |
| |
| protected: |
| void addDeadBlock(const BasicBlock *BB) { |
| SmallVector<const BasicBlock *, 4> NewDead; |
| SmallSetVector<const BasicBlock *, 4> DF; |
| |
| NewDead.push_back(BB); |
| while (!NewDead.empty()) { |
| const BasicBlock *D = NewDead.pop_back_val(); |
| if (isDeadBlock(D)) |
| continue; |
| |
| // All blocks dominated by D are dead. |
| SmallVector<BasicBlock *, 8> Dom; |
| DT->getDescendants(const_cast<BasicBlock*>(D), Dom); |
| // Do not need to mark all in and out edges dead |
| // because BB is marked dead and this is enough |
| // to run further. |
| DeadBlocks.insert(Dom.begin(), Dom.end()); |
| |
| // Figure out the dominance-frontier(D). |
| for (BasicBlock *B : Dom) |
| for (BasicBlock *S : successors(B)) |
| if (!isDeadBlock(S) && !hasLiveIncomingEdges(S)) |
| NewDead.push_back(S); |
| } |
| } |
| |
| void addDeadEdge(const Use &DeadEdge) { |
| if (!DeadEdges.insert(&DeadEdge)) |
| return; |
| |
| BasicBlock *BB = cast_or_null<BasicBlock>(DeadEdge.get()); |
| if (hasLiveIncomingEdges(BB)) |
| return; |
| |
| addDeadBlock(BB); |
| } |
| }; |
| } // namespace |
| |
| static void Verify(const Function &F, const DominatorTree &DT, |
| const CFGDeadness &CD); |
| |
| namespace llvm { |
| PreservedAnalyses SafepointIRVerifierPass::run(Function &F, |
| FunctionAnalysisManager &AM) { |
| const auto &DT = AM.getResult<DominatorTreeAnalysis>(F); |
| CFGDeadness CD; |
| CD.processFunction(F, DT); |
| Verify(F, DT, CD); |
| return PreservedAnalyses::all(); |
| } |
| } // namespace llvm |
| |
| namespace { |
| |
| struct SafepointIRVerifier : public FunctionPass { |
| static char ID; // Pass identification, replacement for typeid |
| SafepointIRVerifier() : FunctionPass(ID) { |
| initializeSafepointIRVerifierPass(*PassRegistry::getPassRegistry()); |
| } |
| |
| bool runOnFunction(Function &F) override { |
| auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree(); |
| CFGDeadness CD; |
| CD.processFunction(F, DT); |
| Verify(F, DT, CD); |
| return false; // no modifications |
| } |
| |
| void getAnalysisUsage(AnalysisUsage &AU) const override { |
| AU.addRequiredID(DominatorTreeWrapperPass::ID); |
| AU.setPreservesAll(); |
| } |
| |
| StringRef getPassName() const override { return "safepoint verifier"; } |
| }; |
| } // namespace |
| |
| void llvm::verifySafepointIR(Function &F) { |
| SafepointIRVerifier pass; |
| pass.runOnFunction(F); |
| } |
| |
| char SafepointIRVerifier::ID = 0; |
| |
| FunctionPass *llvm::createSafepointIRVerifierPass() { |
| return new SafepointIRVerifier(); |
| } |
| |
| INITIALIZE_PASS_BEGIN(SafepointIRVerifier, "verify-safepoint-ir", |
| "Safepoint IR Verifier", false, false) |
| INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) |
| INITIALIZE_PASS_END(SafepointIRVerifier, "verify-safepoint-ir", |
| "Safepoint IR Verifier", false, false) |
| |
| static bool isGCPointerType(Type *T) { |
| if (auto *PT = dyn_cast<PointerType>(T)) |
| // For the sake of this example GC, we arbitrarily pick addrspace(1) as our |
| // GC managed heap. We know that a pointer into this heap needs to be |
| // updated and that no other pointer does. |
| return (1 == PT->getAddressSpace()); |
| return false; |
| } |
| |
| static bool containsGCPtrType(Type *Ty) { |
| if (isGCPointerType(Ty)) |
| return true; |
| if (VectorType *VT = dyn_cast<VectorType>(Ty)) |
| return isGCPointerType(VT->getScalarType()); |
| if (ArrayType *AT = dyn_cast<ArrayType>(Ty)) |
| return containsGCPtrType(AT->getElementType()); |
| if (StructType *ST = dyn_cast<StructType>(Ty)) |
| return llvm::any_of(ST->elements(), containsGCPtrType); |
| return false; |
| } |
| |
| // Debugging aid -- prints a [Begin, End) range of values. |
| template<typename IteratorTy> |
| static void PrintValueSet(raw_ostream &OS, IteratorTy Begin, IteratorTy End) { |
| OS << "[ "; |
| while (Begin != End) { |
| OS << **Begin << " "; |
| ++Begin; |
| } |
| OS << "]"; |
| } |
| |
| /// The verifier algorithm is phrased in terms of availability. The set of |
| /// values "available" at a given point in the control flow graph is the set of |
| /// correctly relocated value at that point, and is a subset of the set of |
| /// definitions dominating that point. |
| |
| using AvailableValueSet = DenseSet<const Value *>; |
| |
| /// State we compute and track per basic block. |
| struct BasicBlockState { |
| // Set of values available coming in, before the phi nodes |
| AvailableValueSet AvailableIn; |
| |
| // Set of values available going out |
| AvailableValueSet AvailableOut; |
| |
| // AvailableOut minus AvailableIn. |
| // All elements are Instructions |
| AvailableValueSet Contribution; |
| |
| // True if this block contains a safepoint and thus AvailableIn does not |
| // contribute to AvailableOut. |
| bool Cleared = false; |
| }; |
| |
| /// 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 for Val which states whether Val is exclusively |
| /// derived from constant/null, or not exclusively derived from constant. |
| /// Val is exclusively derived off a constant base when all operands of phi and |
| /// selects are derived off a constant base. |
| static enum BaseType getBaseType(const Value *Val) { |
| |
| SmallVector<const Value *, 32> Worklist; |
| DenseSet<const Value *> Visited; |
| bool isExclusivelyDerivedFromNull = true; |
| Worklist.push_back(Val); |
| // Strip through all the bitcasts and geps to get base pointer. Also check for |
| // the exclusive value when there can be multiple base pointers (through phis |
| // or selects). |
| while(!Worklist.empty()) { |
| const Value *V = Worklist.pop_back_val(); |
| if (!Visited.insert(V).second) |
| continue; |
| |
| if (const auto *CI = dyn_cast<CastInst>(V)) { |
| Worklist.push_back(CI->stripPointerCasts()); |
| continue; |
| } |
| if (const auto *GEP = dyn_cast<GetElementPtrInst>(V)) { |
| Worklist.push_back(GEP->getPointerOperand()); |
| continue; |
| } |
| // Push all the incoming values of phi node into the worklist for |
| // processing. |
| if (const auto *PN = dyn_cast<PHINode>(V)) { |
| append_range(Worklist, PN->incoming_values()); |
| continue; |
| } |
| if (const auto *SI = dyn_cast<SelectInst>(V)) { |
| // Push in the true and false values |
| Worklist.push_back(SI->getTrueValue()); |
| Worklist.push_back(SI->getFalseValue()); |
| continue; |
| } |
| if (isa<Constant>(V)) { |
| // We found at least one base pointer which is non-null, so this derived |
| // pointer is not exclusively derived from null. |
| if (V != Constant::getNullValue(V->getType())) |
| isExclusivelyDerivedFromNull = false; |
| // Continue processing the remaining values to make sure it's exclusively |
| // constant. |
| continue; |
| } |
| // At this point, we know that the base pointer is not exclusively |
| // constant. |
| return BaseType::NonConstant; |
| } |
| // Now, we know that the base pointer is exclusively constant, but we need to |
| // differentiate between exclusive null constant and non-null constant. |
| return isExclusivelyDerivedFromNull ? BaseType::ExclusivelyNull |
| : BaseType::ExclusivelySomeConstant; |
| } |
| |
| static bool isNotExclusivelyConstantDerived(const Value *V) { |
| return getBaseType(V) == BaseType::NonConstant; |
| } |
| |
| namespace { |
| class InstructionVerifier; |
| |
| /// 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 exclusively derived from null. |
| /// Poisoned pointers are produced when we somehow derive pointer from 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 their undefined state: this pointers should be |
| /// treated as relocated and unrelocated simultaneously. |
| /// Rules of deriving: |
| /// R + U = P - that's where the poisoned pointers come from |
| /// P + X = P |
| /// U + U = U |
| /// R + R = R |
| /// X + C = X |
| /// Where "+" - any operation that somehow derive pointer, U - unrelocated, |
| /// R - relocated and P - poisoned, C - constant, X - U or R or P or C or |
| /// nothing (in case when "+" is unary operation). |
| /// Deriving of pointers by itself is always safe. |
| /// 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 predecessor 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 |
| /// bb1: |
| /// p = *some GC-ptr def* |
| /// p1 = gep p, offset |
| /// / | |
| /// / | |
| /// bb2: | |
| /// safepoint | |
| /// \ | |
| /// \ | |
| /// bb3: |
| /// p2 = phi [p, bb2] [p1, bb1] |
| /// p3 = phi [p, bb2] [p, bb1] |
| /// 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; |
| const CFGDeadness &CD; |
| SpecificBumpPtrAllocator<BasicBlockState> BSAllocator; |
| DenseMap<const BasicBlock *, BasicBlockState *> BlockMap; |
| // This set contains defs of unrelocated pointers that are proved to be legal |
| // and don't need verification. |
| DenseSet<const Instruction *> ValidUnrelocatedDefs; |
| // This set contains poisoned defs. They can be safely ignored during |
| // verification too. |
| DenseSet<const Value *> PoisonedDefs; |
| |
| public: |
| GCPtrTracker(const Function &F, const DominatorTree &DT, |
| const CFGDeadness &CD); |
| |
| bool hasLiveIncomingEdge(const PHINode *PN, const BasicBlock *InBB) const { |
| return CD.hasLiveIncomingEdge(PN, InBB); |
| } |
| |
| 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. |
| /// It destructively modifies GCPtrTracker so it's passed via rvalue reference |
| /// in order to prohibit further usages of GCPtrTracker as it'll be in |
| /// inconsistent state. |
| static void verifyFunction(GCPtrTracker &&Tracker, |
| InstructionVerifier &Verifier); |
| |
| /// Returns true for reachable and live blocks. |
| bool isMapped(const BasicBlock *BB) const { |
| return BlockMap.find(BB) != BlockMap.end(); |
| } |
| |
| private: |
| /// Returns true if the instruction may be safely skipped during verification. |
| bool instructionMayBeSkipped(const Instruction *I) const; |
| |
| /// Iterates over all BBs from BlockMap and recalculates AvailableIn/Out for |
| /// each of them until it converges. |
| void recalculateBBsStates(); |
| |
| /// Remove from Contribution all defs that legally produce unrelocated |
| /// pointers and saves them to ValidUnrelocatedDefs. |
| /// Though Contribution should belong to BBS it is passed separately with |
| /// different const-modifier in order to emphasize (and guarantee) that only |
| /// Contribution will be changed. |
| /// Returns true if Contribution was changed otherwise false. |
| bool removeValidUnrelocatedDefs(const BasicBlock *BB, |
| const BasicBlockState *BBS, |
| AvailableValueSet &Contribution); |
| |
| /// Gather all the definitions dominating the start of BB into Result. This is |
| /// simply the defs introduced by every dominating basic block and the |
| /// function arguments. |
| void gatherDominatingDefs(const BasicBlock *BB, AvailableValueSet &Result, |
| const DominatorTree &DT); |
| |
| /// 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); |
| |
| /// Model the effect of an instruction on the set of available values. |
| static void transferInstruction(const Instruction &I, bool &Cleared, |
| AvailableValueSet &Available); |
| }; |
| |
| /// It is a visitor for GCPtrTracker::verifyFunction. It decides if the |
| /// instruction (which uses heap reference) is legal or not, given our safepoint |
| /// semantics. |
| class InstructionVerifier { |
| bool AnyInvalidUses = false; |
| |
| public: |
| void verifyInstruction(const GCPtrTracker *Tracker, const Instruction &I, |
| const AvailableValueSet &AvailableSet); |
| |
| bool hasAnyInvalidUses() const { return AnyInvalidUses; } |
| |
| private: |
| void reportInvalidUse(const Value &V, const Instruction &I); |
| }; |
| } // end anonymous namespace |
| |
| GCPtrTracker::GCPtrTracker(const Function &F, const DominatorTree &DT, |
| const CFGDeadness &CD) : F(F), CD(CD) { |
| // Calculate Contribution of each live BB. |
| // Allocate BB states for live blocks. |
| for (const BasicBlock &BB : F) |
| if (!CD.isDeadBlock(&BB)) { |
| BasicBlockState *BBS = new (BSAllocator.Allocate()) BasicBlockState; |
| for (const auto &I : BB) |
| transferInstruction(I, BBS->Cleared, BBS->Contribution); |
| BlockMap[&BB] = BBS; |
| } |
| |
| // Initialize AvailableIn/Out sets of each BB using only information about |
| // dominating BBs. |
| for (auto &BBI : BlockMap) { |
| gatherDominatingDefs(BBI.first, BBI.second->AvailableIn, DT); |
| transferBlock(BBI.first, *BBI.second, true); |
| } |
| |
| // Simulate the flow of defs through the CFG and recalculate AvailableIn/Out |
| // sets of each BB until it converges. If any def is proved to be an |
| // unrelocated pointer, it will be removed from all BBSs. |
| recalculateBBsStates(); |
| } |
| |
| BasicBlockState *GCPtrTracker::getBasicBlockState(const BasicBlock *BB) { |
| return BlockMap.lookup(BB); |
| } |
| |
| const BasicBlockState *GCPtrTracker::getBasicBlockState( |
| const BasicBlock *BB) const { |
| return const_cast<GCPtrTracker *>(this)->getBasicBlockState(BB); |
| } |
| |
| bool GCPtrTracker::instructionMayBeSkipped(const Instruction *I) const { |
| // Poisoned defs are skipped since they are always safe by itself by |
| // definition (for details see comment to this class). |
| return ValidUnrelocatedDefs.count(I) || PoisonedDefs.count(I); |
| } |
| |
| void GCPtrTracker::verifyFunction(GCPtrTracker &&Tracker, |
| InstructionVerifier &Verifier) { |
| // 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(&Tracker.F); |
| for (const BasicBlock *BB : RPOT) { |
| BasicBlockState *BBS = Tracker.getBasicBlockState(BB); |
| if (!BBS) |
| continue; |
| |
| // We destructively modify AvailableIn as we traverse the block instruction |
| // by instruction. |
| AvailableValueSet &AvailableSet = BBS->AvailableIn; |
| for (const Instruction &I : *BB) { |
| if (Tracker.instructionMayBeSkipped(&I)) |
| continue; // This instruction shouldn't be added to AvailableSet. |
| |
| Verifier.verifyInstruction(&Tracker, I, AvailableSet); |
| |
| // Model the effect of current instruction on AvailableSet to keep the set |
| // relevant at each point of BB. |
| bool Cleared = false; |
| transferInstruction(I, Cleared, AvailableSet); |
| (void)Cleared; |
| } |
| } |
| } |
| |
| void GCPtrTracker::recalculateBBsStates() { |
| 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/Out sets until it converges. |
| // The AvailableIn and AvailableOut sets decrease as we iterate. |
| while (!Worklist.empty()) { |
| const BasicBlock *BB = Worklist.pop_back_val(); |
| BasicBlockState *BBS = getBasicBlockState(BB); |
| if (!BBS) |
| continue; // Ignore dead successors. |
| |
| size_t OldInCount = BBS->AvailableIn.size(); |
| for (const_pred_iterator PredIt(BB), End(BB, true); PredIt != End; ++PredIt) { |
| const BasicBlock *PBB = *PredIt; |
| BasicBlockState *PBBS = getBasicBlockState(PBB); |
| if (PBBS && !CD.isDeadEdge(&CFGDeadness::getEdge(PredIt))) |
| set_intersect(BBS->AvailableIn, PBBS->AvailableOut); |
| } |
| |
| assert(OldInCount >= BBS->AvailableIn.size() && "invariant!"); |
| |
| bool InputsChanged = OldInCount != BBS->AvailableIn.size(); |
| bool ContributionChanged = |
| removeValidUnrelocatedDefs(BB, BBS, BBS->Contribution); |
| if (!InputsChanged && !ContributionChanged) |
| continue; |
| |
| size_t OldOutCount = BBS->AvailableOut.size(); |
| transferBlock(BB, *BBS, ContributionChanged); |
| if (OldOutCount != BBS->AvailableOut.size()) { |
| assert(OldOutCount > BBS->AvailableOut.size() && "invariant!"); |
| Worklist.insert(succ_begin(BB), succ_end(BB)); |
| } |
| } |
| } |
| |
| bool GCPtrTracker::removeValidUnrelocatedDefs(const BasicBlock *BB, |
| const BasicBlockState *BBS, |
| AvailableValueSet &Contribution) { |
| assert(&BBS->Contribution == &Contribution && |
| "Passed Contribution should be from the passed BasicBlockState!"); |
| AvailableValueSet AvailableSet = BBS->AvailableIn; |
| bool ContributionChanged = false; |
| // For explanation why instructions are processed this way see |
| // "Rules of deriving" in the comment to this class. |
| for (const Instruction &I : *BB) { |
| bool ValidUnrelocatedPointerDef = false; |
| bool PoisonedPointerDef = false; |
| // TODO: `select` instructions should be handled here too. |
| if (const PHINode *PN = dyn_cast<PHINode>(&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); |
| if (!isMapped(InBB) || |
| !CD.hasLiveIncomingEdge(PN, InBB)) |
| continue; // Skip dead block or dead edge. |
| |
| 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<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)) { |
| if (isValuePoisoned(V)) |
| PoisonedPointerDef = true; |
| else |
| ValidUnrelocatedPointerDef = true; |
| break; |
| } |
| } |
| 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); |
| LLVM_DEBUG(dbgs() << "Removing urelocated " << I |
| << " from Contribution of " << BB->getName() << "\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); |
| LLVM_DEBUG(dbgs() << "Removing poisoned " << I << " from Contribution of " |
| << BB->getName() << "\n"); |
| ContributionChanged = true; |
| } else { |
| bool Cleared = false; |
| transferInstruction(I, Cleared, AvailableSet); |
| (void)Cleared; |
| } |
| } |
| return ContributionChanged; |
| } |
| |
| void GCPtrTracker::gatherDominatingDefs(const BasicBlock *BB, |
| AvailableValueSet &Result, |
| const DominatorTree &DT) { |
| DomTreeNode *DTN = DT[const_cast<BasicBlock *>(BB)]; |
| |
| assert(DTN && "Unreachable blocks are ignored"); |
| while (DTN->getIDom()) { |
| DTN = DTN->getIDom(); |
| auto BBS = getBasicBlockState(DTN->getBlock()); |
| assert(BBS && "immediate dominator cannot be dead for a live block"); |
| const auto &Defs = BBS->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 |
| // really important for reducing memory consuption of the initial available |
| // sets and thus peak memory usage by this verifier. |
| if (BBS->Cleared) |
| return; |
| } |
| |
| for (const Argument &A : BB->getParent()->args()) |
| if (containsGCPtrType(A.getType())) |
| Result.insert(&A); |
| } |
| |
| void GCPtrTracker::transferBlock(const BasicBlock *BB, BasicBlockState &BBS, |
| bool ContributionChanged) { |
| const AvailableValueSet &AvailableIn = BBS.AvailableIn; |
| AvailableValueSet &AvailableOut = BBS.AvailableOut; |
| |
| if (BBS.Cleared) { |
| // 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 |
| AvailableValueSet Temp = BBS.Contribution; |
| set_union(Temp, AvailableIn); |
| AvailableOut = std::move(Temp); |
| } |
| |
| LLVM_DEBUG(dbgs() << "Transfered block " << BB->getName() << " from "; |
| PrintValueSet(dbgs(), AvailableIn.begin(), AvailableIn.end()); |
| dbgs() << " to "; |
| PrintValueSet(dbgs(), AvailableOut.begin(), AvailableOut.end()); |
| dbgs() << "\n";); |
| } |
| |
| void GCPtrTracker::transferInstruction(const Instruction &I, bool &Cleared, |
| AvailableValueSet &Available) { |
| if (isa<GCStatepointInst>(I)) { |
| Cleared = true; |
| Available.clear(); |
| } else if (containsGCPtrType(I.getType())) |
| Available.insert(&I); |
| } |
| |
| void InstructionVerifier::verifyInstruction( |
| const GCPtrTracker *Tracker, const Instruction &I, |
| const AvailableValueSet &AvailableSet) { |
| 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); |
| const BasicBlockState *InBBS = Tracker->getBasicBlockState(InBB); |
| if (!InBBS || |
| !Tracker->hasLiveIncomingEdge(PN, InBB)) |
| continue; // Skip dead block or dead edge. |
| |
| const Value *InValue = PN->getIncomingValue(i); |
| |
| if (isNotExclusivelyConstantDerived(InValue) && |
| !InBBS->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, 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 |
| // 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; |
| |
| // If one of pointers is poisoned and other is not exclusively derived |
| // from 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 exclusively derived null pointer and a |
| // constant base pointer. |
| // 2. Comparison between an exclusively derived null pointer and a |
| // non-constant unrelocated base pointer. |
| // 3. Comparison between 2 unrelocated pointers. |
| // 4. Comparison between a pointer exclusively derived from null and a |
| // non-constant poisoned pointer. |
| 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); |
| } |
| } |
| |
| void InstructionVerifier::reportInvalidUse(const Value &V, |
| const Instruction &I) { |
| errs() << "Illegal use of unrelocated value found!\n"; |
| errs() << "Def: " << V << "\n"; |
| errs() << "Use: " << I << "\n"; |
| if (!PrintOnly) |
| abort(); |
| AnyInvalidUses = true; |
| } |
| |
| static void Verify(const Function &F, const DominatorTree &DT, |
| const CFGDeadness &CD) { |
| LLVM_DEBUG(dbgs() << "Verifying gc pointers in function: " << F.getName() |
| << "\n"); |
| if (PrintOnly) |
| dbgs() << "Verifying gc pointers in function: " << F.getName() << "\n"; |
| |
| GCPtrTracker Tracker(F, DT, CD); |
| |
| // 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. |
| |
| InstructionVerifier Verifier; |
| GCPtrTracker::verifyFunction(std::move(Tracker), Verifier); |
| |
| if (PrintOnly && !Verifier.hasAnyInvalidUses()) { |
| dbgs() << "No illegal uses found by SafepointIRVerifier in: " << F.getName() |
| << "\n"; |
| } |
| } |