908 lines · cpp
1//===-- SafepointIRVerifier.cpp - Verify gc.statepoint invariants ---------===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8//9// Run a basic correctness check on the IR to ensure that Safepoints - if10// they've been inserted - were inserted correctly. In particular, look for use11// of non-relocated values after a safepoint. It's primary use is to check the12// correctness of safepoint insertion immediately after insertion, but it can13// also be used to verify that later transforms have not found a way to break14// safepoint semenatics.15//16// In its current form, this verify checks a property which is sufficient, but17// not neccessary for correctness. There are some cases where an unrelocated18// pointer can be used after the safepoint. Consider this example:19//20// a = ...21// b = ...22// (a',b') = safepoint(a,b)23// c = cmp eq a b24// br c, ..., ....25//26// Because it is valid to reorder 'c' above the safepoint, this is legal. In27// practice, this is a somewhat uncommon transform, but CodeGenPrep does create28// idioms like this. The verifier knows about these cases and avoids reporting29// false positives.30//31//===----------------------------------------------------------------------===//32 33#include "llvm/IR/SafepointIRVerifier.h"34#include "llvm/ADT/DenseSet.h"35#include "llvm/ADT/PostOrderIterator.h"36#include "llvm/ADT/SetOperations.h"37#include "llvm/ADT/SetVector.h"38#include "llvm/IR/BasicBlock.h"39#include "llvm/IR/Dominators.h"40#include "llvm/IR/Function.h"41#include "llvm/IR/InstrTypes.h"42#include "llvm/IR/Instructions.h"43#include "llvm/IR/Statepoint.h"44#include "llvm/IR/Value.h"45#include "llvm/InitializePasses.h"46#include "llvm/Support/Allocator.h"47#include "llvm/Support/CommandLine.h"48#include "llvm/Support/Debug.h"49#include "llvm/Support/raw_ostream.h"50 51#define DEBUG_TYPE "safepoint-ir-verifier"52 53using namespace llvm;54 55/// This option is used for writing test cases. Instead of crashing the program56/// when verification fails, report a message to the console (for FileCheck57/// usage) and continue execution as if nothing happened.58static cl::opt<bool> PrintOnly("safepoint-ir-verifier-print-only",59 cl::init(false));60 61namespace {62 63/// This CFG Deadness finds dead blocks and edges. Algorithm starts with a set64/// of blocks unreachable from entry then propagates deadness using foldable65/// conditional branches without modifying CFG. So GVN does but it changes CFG66/// by splitting critical edges. In most cases passes rely on SimplifyCFG to67/// clean up dead blocks, but in some cases, like verification or loop passes68/// it's not possible.69class CFGDeadness {70 const DominatorTree *DT = nullptr;71 SetVector<const BasicBlock *> DeadBlocks;72 SetVector<const Use *> DeadEdges; // Contains all dead edges from live blocks.73 74public:75 /// Return the edge that coresponds to the predecessor.76 static const Use& getEdge(const_pred_iterator &PredIt) {77 auto &PU = PredIt.getUse();78 return PU.getUser()->getOperandUse(PU.getOperandNo());79 }80 81 /// Return true if there is at least one live edge that corresponds to the82 /// basic block InBB listed in the phi node.83 bool hasLiveIncomingEdge(const PHINode *PN, const BasicBlock *InBB) const {84 assert(!isDeadBlock(InBB) && "block must be live");85 const BasicBlock* BB = PN->getParent();86 bool Listed = false;87 for (const_pred_iterator PredIt(BB), End(BB, true); PredIt != End; ++PredIt) {88 if (InBB == *PredIt) {89 if (!isDeadEdge(&getEdge(PredIt)))90 return true;91 Listed = true;92 }93 }94 (void)Listed;95 assert(Listed && "basic block is not found among incoming blocks");96 return false;97 }98 99 100 bool isDeadBlock(const BasicBlock *BB) const {101 return DeadBlocks.count(BB);102 }103 104 bool isDeadEdge(const Use *U) const {105 assert(cast<Instruction>(U->getUser())->isTerminator() &&106 "edge must be operand of terminator");107 assert(cast_or_null<BasicBlock>(U->get()) &&108 "edge must refer to basic block");109 assert(!isDeadBlock(cast<Instruction>(U->getUser())->getParent()) &&110 "isDeadEdge() must be applied to edge from live block");111 return DeadEdges.count(U);112 }113 114 bool hasLiveIncomingEdges(const BasicBlock *BB) const {115 // Check if all incoming edges are dead.116 for (const_pred_iterator PredIt(BB), End(BB, true); PredIt != End; ++PredIt) {117 auto &PU = PredIt.getUse();118 const Use &U = PU.getUser()->getOperandUse(PU.getOperandNo());119 if (!isDeadBlock(*PredIt) && !isDeadEdge(&U))120 return true; // Found a live edge.121 }122 return false;123 }124 125 void processFunction(const Function &F, const DominatorTree &DT) {126 this->DT = &DT;127 128 // Start with all blocks unreachable from entry.129 for (const BasicBlock &BB : F)130 if (!DT.isReachableFromEntry(&BB))131 DeadBlocks.insert(&BB);132 133 // Top-down walk of the dominator tree134 ReversePostOrderTraversal<const Function *> RPOT(&F);135 for (const BasicBlock *BB : RPOT) {136 const Instruction *TI = BB->getTerminator();137 assert(TI && "blocks must be well formed");138 139 // For conditional branches, we can perform simple conditional propagation on140 // the condition value itself.141 const BranchInst *BI = dyn_cast<BranchInst>(TI);142 if (!BI || !BI->isConditional() || !isa<Constant>(BI->getCondition()))143 continue;144 145 // If a branch has two identical successors, we cannot declare either dead.146 if (BI->getSuccessor(0) == BI->getSuccessor(1))147 continue;148 149 ConstantInt *Cond = dyn_cast<ConstantInt>(BI->getCondition());150 if (!Cond)151 continue;152 153 addDeadEdge(BI->getOperandUse(Cond->getZExtValue() ? 1 : 2));154 }155 }156 157protected:158 void addDeadBlock(const BasicBlock *BB) {159 SmallVector<const BasicBlock *, 4> NewDead;160 161 NewDead.push_back(BB);162 while (!NewDead.empty()) {163 const BasicBlock *D = NewDead.pop_back_val();164 if (isDeadBlock(D))165 continue;166 167 // All blocks dominated by D are dead.168 SmallVector<BasicBlock *, 8> Dom;169 DT->getDescendants(const_cast<BasicBlock*>(D), Dom);170 // Do not need to mark all in and out edges dead171 // because BB is marked dead and this is enough172 // to run further.173 DeadBlocks.insert_range(Dom);174 175 // Figure out the dominance-frontier(D).176 for (BasicBlock *B : Dom)177 for (BasicBlock *S : successors(B))178 if (!isDeadBlock(S) && !hasLiveIncomingEdges(S))179 NewDead.push_back(S);180 }181 }182 183 void addDeadEdge(const Use &DeadEdge) {184 if (!DeadEdges.insert(&DeadEdge))185 return;186 187 BasicBlock *BB = cast_or_null<BasicBlock>(DeadEdge.get());188 if (hasLiveIncomingEdges(BB))189 return;190 191 addDeadBlock(BB);192 }193};194} // namespace195 196static void Verify(const Function &F, const DominatorTree &DT,197 const CFGDeadness &CD);198 199PreservedAnalyses SafepointIRVerifierPass::run(Function &F,200 FunctionAnalysisManager &AM) {201 const auto &DT = AM.getResult<DominatorTreeAnalysis>(F);202 CFGDeadness CD;203 CD.processFunction(F, DT);204 Verify(F, DT, CD);205 return PreservedAnalyses::all();206}207 208namespace {209 210struct SafepointIRVerifier : public FunctionPass {211 static char ID; // Pass identification, replacement for typeid212 SafepointIRVerifier() : FunctionPass(ID) {213 initializeSafepointIRVerifierPass(*PassRegistry::getPassRegistry());214 }215 216 bool runOnFunction(Function &F) override {217 auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();218 CFGDeadness CD;219 CD.processFunction(F, DT);220 Verify(F, DT, CD);221 return false; // no modifications222 }223 224 void getAnalysisUsage(AnalysisUsage &AU) const override {225 AU.addRequiredID(DominatorTreeWrapperPass::ID);226 AU.setPreservesAll();227 }228 229 StringRef getPassName() const override { return "safepoint verifier"; }230};231} // namespace232 233void llvm::verifySafepointIR(Function &F) {234 SafepointIRVerifier pass;235 pass.runOnFunction(F);236}237 238char SafepointIRVerifier::ID = 0;239 240FunctionPass *llvm::createSafepointIRVerifierPass() {241 return new SafepointIRVerifier();242}243 244INITIALIZE_PASS_BEGIN(SafepointIRVerifier, "verify-safepoint-ir",245 "Safepoint IR Verifier", false, false)246INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)247INITIALIZE_PASS_END(SafepointIRVerifier, "verify-safepoint-ir",248 "Safepoint IR Verifier", false, false)249 250static bool isGCPointerType(Type *T) {251 if (auto *PT = dyn_cast<PointerType>(T))252 // For the sake of this example GC, we arbitrarily pick addrspace(1) as our253 // GC managed heap. We know that a pointer into this heap needs to be254 // updated and that no other pointer does.255 return (1 == PT->getAddressSpace());256 return false;257}258 259static bool containsGCPtrType(Type *Ty) {260 if (isGCPointerType(Ty))261 return true;262 if (VectorType *VT = dyn_cast<VectorType>(Ty))263 return isGCPointerType(VT->getScalarType());264 if (ArrayType *AT = dyn_cast<ArrayType>(Ty))265 return containsGCPtrType(AT->getElementType());266 if (StructType *ST = dyn_cast<StructType>(Ty))267 return llvm::any_of(ST->elements(), containsGCPtrType);268 return false;269}270 271// Debugging aid -- prints a [Begin, End) range of values.272template<typename IteratorTy>273static void PrintValueSet(raw_ostream &OS, IteratorTy Begin, IteratorTy End) {274 OS << "[ ";275 while (Begin != End) {276 OS << **Begin << " ";277 ++Begin;278 }279 OS << "]";280}281 282/// The verifier algorithm is phrased in terms of availability. The set of283/// values "available" at a given point in the control flow graph is the set of284/// correctly relocated value at that point, and is a subset of the set of285/// definitions dominating that point.286 287using AvailableValueSet = DenseSet<const Value *>;288 289namespace {290/// State we compute and track per basic block.291struct BasicBlockState {292 // Set of values available coming in, before the phi nodes293 AvailableValueSet AvailableIn;294 295 // Set of values available going out296 AvailableValueSet AvailableOut;297 298 // AvailableOut minus AvailableIn.299 // All elements are Instructions300 AvailableValueSet Contribution;301 302 // True if this block contains a safepoint and thus AvailableIn does not303 // contribute to AvailableOut.304 bool Cleared = false;305};306} // namespace307 308/// A given derived pointer can have multiple base pointers through phi/selects.309/// This type indicates when the base pointer is exclusively constant310/// (ExclusivelySomeConstant), and if that constant is proven to be exclusively311/// null, we record that as ExclusivelyNull. In all other cases, the BaseType is312/// NonConstant.313enum BaseType {314 NonConstant = 1, // Base pointers is not exclusively constant.315 ExclusivelyNull,316 ExclusivelySomeConstant // Base pointers for a given derived pointer is from a317 // set of constants, but they are not exclusively318 // null.319};320 321/// Return the baseType for Val which states whether Val is exclusively322/// derived from constant/null, or not exclusively derived from constant.323/// Val is exclusively derived off a constant base when all operands of phi and324/// selects are derived off a constant base.325static enum BaseType getBaseType(const Value *Val) {326 327 SmallVector<const Value *, 32> Worklist;328 DenseSet<const Value *> Visited;329 bool isExclusivelyDerivedFromNull = true;330 Worklist.push_back(Val);331 // Strip through all the bitcasts and geps to get base pointer. Also check for332 // the exclusive value when there can be multiple base pointers (through phis333 // or selects).334 while(!Worklist.empty()) {335 const Value *V = Worklist.pop_back_val();336 if (!Visited.insert(V).second)337 continue;338 339 if (const auto *CI = dyn_cast<CastInst>(V)) {340 Worklist.push_back(CI->stripPointerCasts());341 continue;342 }343 if (const auto *GEP = dyn_cast<GetElementPtrInst>(V)) {344 Worklist.push_back(GEP->getPointerOperand());345 continue;346 }347 // Push all the incoming values of phi node into the worklist for348 // processing.349 if (const auto *PN = dyn_cast<PHINode>(V)) {350 append_range(Worklist, PN->incoming_values());351 continue;352 }353 if (const auto *SI = dyn_cast<SelectInst>(V)) {354 // Push in the true and false values355 Worklist.push_back(SI->getTrueValue());356 Worklist.push_back(SI->getFalseValue());357 continue;358 }359 if (const auto *GCRelocate = dyn_cast<GCRelocateInst>(V)) {360 // GCRelocates do not change null-ness or constant-ness of the value.361 // So we can continue with derived pointer this instruction relocates.362 Worklist.push_back(GCRelocate->getDerivedPtr());363 continue;364 }365 if (const auto *FI = dyn_cast<FreezeInst>(V)) {366 // Freeze does not change null-ness or constant-ness of the value.367 Worklist.push_back(FI->getOperand(0));368 continue;369 }370 if (isa<Constant>(V)) {371 // We found at least one base pointer which is non-null, so this derived372 // pointer is not exclusively derived from null.373 if (V != Constant::getNullValue(V->getType()))374 isExclusivelyDerivedFromNull = false;375 // Continue processing the remaining values to make sure it's exclusively376 // constant.377 continue;378 }379 // At this point, we know that the base pointer is not exclusively380 // constant.381 return BaseType::NonConstant;382 }383 // Now, we know that the base pointer is exclusively constant, but we need to384 // differentiate between exclusive null constant and non-null constant.385 return isExclusivelyDerivedFromNull ? BaseType::ExclusivelyNull386 : BaseType::ExclusivelySomeConstant;387}388 389static bool isNotExclusivelyConstantDerived(const Value *V) {390 return getBaseType(V) == BaseType::NonConstant;391}392 393namespace {394class InstructionVerifier;395 396/// Builds BasicBlockState for each BB of the function.397/// It can traverse function for verification and provides all required398/// information.399///400/// GC pointer may be in one of three states: relocated, unrelocated and401/// poisoned.402/// Relocated pointer may be used without any restrictions.403/// Unrelocated pointer cannot be dereferenced, passed as argument to any call404/// or returned. Unrelocated pointer may be safely compared against another405/// unrelocated pointer or against a pointer exclusively derived from null.406/// Poisoned pointers are produced when we somehow derive pointer from relocated407/// and unrelocated pointers (e.g. phi, select). This pointers may be safely408/// used in a very limited number of situations. Currently the only way to use409/// it is comparison against constant exclusively derived from null. All410/// limitations arise due to their undefined state: this pointers should be411/// treated as relocated and unrelocated simultaneously.412/// Rules of deriving:413/// R + U = P - that's where the poisoned pointers come from414/// P + X = P415/// U + U = U416/// R + R = R417/// X + C = X418/// Where "+" - any operation that somehow derive pointer, U - unrelocated,419/// R - relocated and P - poisoned, C - constant, X - U or R or P or C or420/// nothing (in case when "+" is unary operation).421/// Deriving of pointers by itself is always safe.422/// NOTE: when we are making decision on the status of instruction's result:423/// a) for phi we need to check status of each input *at the end of424/// corresponding predecessor BB*.425/// b) for other instructions we need to check status of each input *at the426/// current point*.427///428/// FIXME: This works fairly well except one case429/// bb1:430/// p = *some GC-ptr def*431/// p1 = gep p, offset432/// / |433/// / |434/// bb2: |435/// safepoint |436/// \ |437/// \ |438/// bb3:439/// p2 = phi [p, bb2] [p1, bb1]440/// p3 = phi [p, bb2] [p, bb1]441/// here p and p1 is unrelocated442/// p2 and p3 is poisoned (though they shouldn't be)443///444/// This leads to some weird results:445/// cmp eq p, p2 - illegal instruction (false-positive)446/// cmp eq p1, p2 - illegal instruction (false-positive)447/// cmp eq p, p3 - illegal instruction (false-positive)448/// cmp eq p, p1 - ok449/// To fix this we need to introduce conception of generations and be able to450/// check if two values belong to one generation or not. This way p2 will be451/// considered to be unrelocated and no false alarm will happen.452class GCPtrTracker {453 const Function &F;454 const CFGDeadness &CD;455 SpecificBumpPtrAllocator<BasicBlockState> BSAllocator;456 DenseMap<const BasicBlock *, BasicBlockState *> BlockMap;457 // This set contains defs of unrelocated pointers that are proved to be legal458 // and don't need verification.459 DenseSet<const Instruction *> ValidUnrelocatedDefs;460 // This set contains poisoned defs. They can be safely ignored during461 // verification too.462 DenseSet<const Value *> PoisonedDefs;463 464public:465 GCPtrTracker(const Function &F, const DominatorTree &DT,466 const CFGDeadness &CD);467 468 bool hasLiveIncomingEdge(const PHINode *PN, const BasicBlock *InBB) const {469 return CD.hasLiveIncomingEdge(PN, InBB);470 }471 472 BasicBlockState *getBasicBlockState(const BasicBlock *BB);473 const BasicBlockState *getBasicBlockState(const BasicBlock *BB) const;474 475 bool isValuePoisoned(const Value *V) const { return PoisonedDefs.count(V); }476 477 /// Traverse each BB of the function and call478 /// InstructionVerifier::verifyInstruction for each possibly invalid479 /// instruction.480 /// It destructively modifies GCPtrTracker so it's passed via rvalue reference481 /// in order to prohibit further usages of GCPtrTracker as it'll be in482 /// inconsistent state.483 static void verifyFunction(GCPtrTracker &&Tracker,484 InstructionVerifier &Verifier);485 486 /// Returns true for reachable and live blocks.487 bool isMapped(const BasicBlock *BB) const { return BlockMap.contains(BB); }488 489private:490 /// Returns true if the instruction may be safely skipped during verification.491 bool instructionMayBeSkipped(const Instruction *I) const;492 493 /// Iterates over all BBs from BlockMap and recalculates AvailableIn/Out for494 /// each of them until it converges.495 void recalculateBBsStates();496 497 /// Remove from Contribution all defs that legally produce unrelocated498 /// pointers and saves them to ValidUnrelocatedDefs.499 /// Though Contribution should belong to BBS it is passed separately with500 /// different const-modifier in order to emphasize (and guarantee) that only501 /// Contribution will be changed.502 /// Returns true if Contribution was changed otherwise false.503 bool removeValidUnrelocatedDefs(const BasicBlock *BB,504 const BasicBlockState *BBS,505 AvailableValueSet &Contribution);506 507 /// Gather all the definitions dominating the start of BB into Result. This is508 /// simply the defs introduced by every dominating basic block and the509 /// function arguments.510 void gatherDominatingDefs(const BasicBlock *BB, AvailableValueSet &Result,511 const DominatorTree &DT);512 513 /// Compute the AvailableOut set for BB, based on the BasicBlockState BBS,514 /// which is the BasicBlockState for BB.515 /// ContributionChanged is set when the verifier runs for the first time516 /// (in this case Contribution was changed from 'empty' to its initial state)517 /// or when Contribution of this BB was changed since last computation.518 static void transferBlock(const BasicBlock *BB, BasicBlockState &BBS,519 bool ContributionChanged);520 521 /// Model the effect of an instruction on the set of available values.522 static void transferInstruction(const Instruction &I, bool &Cleared,523 AvailableValueSet &Available);524};525 526/// It is a visitor for GCPtrTracker::verifyFunction. It decides if the527/// instruction (which uses heap reference) is legal or not, given our safepoint528/// semantics.529class InstructionVerifier {530 bool AnyInvalidUses = false;531 532public:533 void verifyInstruction(const GCPtrTracker *Tracker, const Instruction &I,534 const AvailableValueSet &AvailableSet);535 536 bool hasAnyInvalidUses() const { return AnyInvalidUses; }537 538private:539 void reportInvalidUse(const Value &V, const Instruction &I);540};541} // end anonymous namespace542 543GCPtrTracker::GCPtrTracker(const Function &F, const DominatorTree &DT,544 const CFGDeadness &CD) : F(F), CD(CD) {545 // Calculate Contribution of each live BB.546 // Allocate BB states for live blocks.547 for (const BasicBlock &BB : F)548 if (!CD.isDeadBlock(&BB)) {549 BasicBlockState *BBS = new (BSAllocator.Allocate()) BasicBlockState;550 for (const auto &I : BB)551 transferInstruction(I, BBS->Cleared, BBS->Contribution);552 BlockMap[&BB] = BBS;553 }554 555 // Initialize AvailableIn/Out sets of each BB using only information about556 // dominating BBs.557 for (auto &BBI : BlockMap) {558 gatherDominatingDefs(BBI.first, BBI.second->AvailableIn, DT);559 transferBlock(BBI.first, *BBI.second, true);560 }561 562 // Simulate the flow of defs through the CFG and recalculate AvailableIn/Out563 // sets of each BB until it converges. If any def is proved to be an564 // unrelocated pointer, it will be removed from all BBSs.565 recalculateBBsStates();566}567 568BasicBlockState *GCPtrTracker::getBasicBlockState(const BasicBlock *BB) {569 return BlockMap.lookup(BB);570}571 572const BasicBlockState *GCPtrTracker::getBasicBlockState(573 const BasicBlock *BB) const {574 return const_cast<GCPtrTracker *>(this)->getBasicBlockState(BB);575}576 577bool GCPtrTracker::instructionMayBeSkipped(const Instruction *I) const {578 // Poisoned defs are skipped since they are always safe by itself by579 // definition (for details see comment to this class).580 return ValidUnrelocatedDefs.count(I) || PoisonedDefs.count(I);581}582 583void GCPtrTracker::verifyFunction(GCPtrTracker &&Tracker,584 InstructionVerifier &Verifier) {585 // We need RPO here to a) report always the first error b) report errors in586 // same order from run to run.587 ReversePostOrderTraversal<const Function *> RPOT(&Tracker.F);588 for (const BasicBlock *BB : RPOT) {589 BasicBlockState *BBS = Tracker.getBasicBlockState(BB);590 if (!BBS)591 continue;592 593 // We destructively modify AvailableIn as we traverse the block instruction594 // by instruction.595 AvailableValueSet &AvailableSet = BBS->AvailableIn;596 for (const Instruction &I : *BB) {597 if (Tracker.instructionMayBeSkipped(&I))598 continue; // This instruction shouldn't be added to AvailableSet.599 600 Verifier.verifyInstruction(&Tracker, I, AvailableSet);601 602 // Model the effect of current instruction on AvailableSet to keep the set603 // relevant at each point of BB.604 bool Cleared = false;605 transferInstruction(I, Cleared, AvailableSet);606 (void)Cleared;607 }608 }609}610 611void GCPtrTracker::recalculateBBsStates() {612 // TODO: This order is suboptimal, it's better to replace it with priority613 // queue where priority is RPO number of BB.614 SetVector<const BasicBlock *> Worklist(llvm::from_range,615 llvm::make_first_range(BlockMap));616 617 // This loop iterates the AvailableIn/Out sets until it converges.618 // The AvailableIn and AvailableOut sets decrease as we iterate.619 while (!Worklist.empty()) {620 const BasicBlock *BB = Worklist.pop_back_val();621 BasicBlockState *BBS = getBasicBlockState(BB);622 if (!BBS)623 continue; // Ignore dead successors.624 625 size_t OldInCount = BBS->AvailableIn.size();626 for (const_pred_iterator PredIt(BB), End(BB, true); PredIt != End; ++PredIt) {627 const BasicBlock *PBB = *PredIt;628 BasicBlockState *PBBS = getBasicBlockState(PBB);629 if (PBBS && !CD.isDeadEdge(&CFGDeadness::getEdge(PredIt)))630 set_intersect(BBS->AvailableIn, PBBS->AvailableOut);631 }632 633 assert(OldInCount >= BBS->AvailableIn.size() && "invariant!");634 635 bool InputsChanged = OldInCount != BBS->AvailableIn.size();636 bool ContributionChanged =637 removeValidUnrelocatedDefs(BB, BBS, BBS->Contribution);638 if (!InputsChanged && !ContributionChanged)639 continue;640 641 size_t OldOutCount = BBS->AvailableOut.size();642 transferBlock(BB, *BBS, ContributionChanged);643 if (OldOutCount != BBS->AvailableOut.size()) {644 assert(OldOutCount > BBS->AvailableOut.size() && "invariant!");645 Worklist.insert_range(successors(BB));646 }647 }648}649 650bool GCPtrTracker::removeValidUnrelocatedDefs(const BasicBlock *BB,651 const BasicBlockState *BBS,652 AvailableValueSet &Contribution) {653 assert(&BBS->Contribution == &Contribution &&654 "Passed Contribution should be from the passed BasicBlockState!");655 AvailableValueSet AvailableSet = BBS->AvailableIn;656 bool ContributionChanged = false;657 // For explanation why instructions are processed this way see658 // "Rules of deriving" in the comment to this class.659 for (const Instruction &I : *BB) {660 bool ValidUnrelocatedPointerDef = false;661 bool PoisonedPointerDef = false;662 // TODO: `select` instructions should be handled here too.663 if (const PHINode *PN = dyn_cast<PHINode>(&I)) {664 if (containsGCPtrType(PN->getType())) {665 // If both is true, output is poisoned.666 bool HasRelocatedInputs = false;667 bool HasUnrelocatedInputs = false;668 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {669 const BasicBlock *InBB = PN->getIncomingBlock(i);670 if (!isMapped(InBB) ||671 !CD.hasLiveIncomingEdge(PN, InBB))672 continue; // Skip dead block or dead edge.673 674 const Value *InValue = PN->getIncomingValue(i);675 676 if (isNotExclusivelyConstantDerived(InValue)) {677 if (isValuePoisoned(InValue)) {678 // If any of inputs is poisoned, output is always poisoned too.679 HasRelocatedInputs = true;680 HasUnrelocatedInputs = true;681 break;682 }683 if (BlockMap[InBB]->AvailableOut.count(InValue))684 HasRelocatedInputs = true;685 else686 HasUnrelocatedInputs = true;687 }688 }689 if (HasUnrelocatedInputs) {690 if (HasRelocatedInputs)691 PoisonedPointerDef = true;692 else693 ValidUnrelocatedPointerDef = true;694 }695 }696 } else if ((isa<GetElementPtrInst>(I) || isa<BitCastInst>(I)) &&697 containsGCPtrType(I.getType())) {698 // GEP/bitcast of unrelocated pointer is legal by itself but this def699 // shouldn't appear in any AvailableSet.700 for (const Value *V : I.operands())701 if (containsGCPtrType(V->getType()) &&702 isNotExclusivelyConstantDerived(V) && !AvailableSet.count(V)) {703 if (isValuePoisoned(V))704 PoisonedPointerDef = true;705 else706 ValidUnrelocatedPointerDef = true;707 break;708 }709 }710 assert(!(ValidUnrelocatedPointerDef && PoisonedPointerDef) &&711 "Value cannot be both unrelocated and poisoned!");712 if (ValidUnrelocatedPointerDef) {713 // Remove def of unrelocated pointer from Contribution of this BB and714 // trigger update of all its successors.715 Contribution.erase(&I);716 PoisonedDefs.erase(&I);717 ValidUnrelocatedDefs.insert(&I);718 LLVM_DEBUG(dbgs() << "Removing urelocated " << I719 << " from Contribution of " << BB->getName() << "\n");720 ContributionChanged = true;721 } else if (PoisonedPointerDef) {722 // Mark pointer as poisoned, remove its def from Contribution and trigger723 // update of all successors.724 Contribution.erase(&I);725 PoisonedDefs.insert(&I);726 LLVM_DEBUG(dbgs() << "Removing poisoned " << I << " from Contribution of "727 << BB->getName() << "\n");728 ContributionChanged = true;729 } else {730 bool Cleared = false;731 transferInstruction(I, Cleared, AvailableSet);732 (void)Cleared;733 }734 }735 return ContributionChanged;736}737 738void GCPtrTracker::gatherDominatingDefs(const BasicBlock *BB,739 AvailableValueSet &Result,740 const DominatorTree &DT) {741 DomTreeNode *DTN = DT[const_cast<BasicBlock *>(BB)];742 743 assert(DTN && "Unreachable blocks are ignored");744 while (DTN->getIDom()) {745 DTN = DTN->getIDom();746 auto BBS = getBasicBlockState(DTN->getBlock());747 assert(BBS && "immediate dominator cannot be dead for a live block");748 const auto &Defs = BBS->Contribution;749 Result.insert_range(Defs);750 // If this block is 'Cleared', then nothing LiveIn to this block can be751 // available after this block completes. Note: This turns out to be752 // really important for reducing memory consuption of the initial available753 // sets and thus peak memory usage by this verifier.754 if (BBS->Cleared)755 return;756 }757 758 for (const Argument &A : BB->getParent()->args())759 if (containsGCPtrType(A.getType()))760 Result.insert(&A);761}762 763void GCPtrTracker::transferBlock(const BasicBlock *BB, BasicBlockState &BBS,764 bool ContributionChanged) {765 const AvailableValueSet &AvailableIn = BBS.AvailableIn;766 AvailableValueSet &AvailableOut = BBS.AvailableOut;767 768 if (BBS.Cleared) {769 // AvailableOut will change only when Contribution changed.770 if (ContributionChanged)771 AvailableOut = BBS.Contribution;772 } else {773 // Otherwise, we need to reduce the AvailableOut set by things which are no774 // longer in our AvailableIn775 AvailableValueSet Temp = BBS.Contribution;776 set_union(Temp, AvailableIn);777 AvailableOut = std::move(Temp);778 }779 780 LLVM_DEBUG(dbgs() << "Transfered block " << BB->getName() << " from ";781 PrintValueSet(dbgs(), AvailableIn.begin(), AvailableIn.end());782 dbgs() << " to ";783 PrintValueSet(dbgs(), AvailableOut.begin(), AvailableOut.end());784 dbgs() << "\n";);785}786 787void GCPtrTracker::transferInstruction(const Instruction &I, bool &Cleared,788 AvailableValueSet &Available) {789 if (isa<GCStatepointInst>(I)) {790 Cleared = true;791 Available.clear();792 } else if (containsGCPtrType(I.getType()))793 Available.insert(&I);794}795 796void InstructionVerifier::verifyInstruction(797 const GCPtrTracker *Tracker, const Instruction &I,798 const AvailableValueSet &AvailableSet) {799 if (const PHINode *PN = dyn_cast<PHINode>(&I)) {800 if (containsGCPtrType(PN->getType()))801 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {802 const BasicBlock *InBB = PN->getIncomingBlock(i);803 const BasicBlockState *InBBS = Tracker->getBasicBlockState(InBB);804 if (!InBBS ||805 !Tracker->hasLiveIncomingEdge(PN, InBB))806 continue; // Skip dead block or dead edge.807 808 const Value *InValue = PN->getIncomingValue(i);809 810 if (isNotExclusivelyConstantDerived(InValue) &&811 !InBBS->AvailableOut.count(InValue))812 reportInvalidUse(*InValue, *PN);813 }814 } else if (isa<CmpInst>(I) &&815 containsGCPtrType(I.getOperand(0)->getType())) {816 Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);817 enum BaseType baseTyLHS = getBaseType(LHS),818 baseTyRHS = getBaseType(RHS);819 820 // Returns true if LHS and RHS are unrelocated pointers and they are821 // valid unrelocated uses.822 auto hasValidUnrelocatedUse = [&AvailableSet, Tracker, baseTyLHS, baseTyRHS,823 &LHS, &RHS] () {824 // A cmp instruction has valid unrelocated pointer operands only if825 // both operands are unrelocated pointers.826 // In the comparison between two pointers, if one is an unrelocated827 // use, the other *should be* an unrelocated use, for this828 // instruction to contain valid unrelocated uses. This unrelocated829 // use can be a null constant as well, or another unrelocated830 // pointer.831 if (AvailableSet.count(LHS) || AvailableSet.count(RHS))832 return false;833 // Constant pointers (that are not exclusively null) may have834 // meaning in different VMs, so we cannot reorder the compare835 // against constant pointers before the safepoint. In other words,836 // comparison of an unrelocated use against a non-null constant837 // maybe invalid.838 if ((baseTyLHS == BaseType::ExclusivelySomeConstant &&839 baseTyRHS == BaseType::NonConstant) ||840 (baseTyLHS == BaseType::NonConstant &&841 baseTyRHS == BaseType::ExclusivelySomeConstant))842 return false;843 844 // If one of pointers is poisoned and other is not exclusively derived845 // from null it is an invalid expression: it produces poisoned result846 // and unless we want to track all defs (not only gc pointers) the only847 // option is to prohibit such instructions.848 if ((Tracker->isValuePoisoned(LHS) && baseTyRHS != ExclusivelyNull) ||849 (Tracker->isValuePoisoned(RHS) && baseTyLHS != ExclusivelyNull))850 return false;851 852 // All other cases are valid cases enumerated below:853 // 1. Comparison between an exclusively derived null pointer and a854 // constant base pointer.855 // 2. Comparison between an exclusively derived null pointer and a856 // non-constant unrelocated base pointer.857 // 3. Comparison between 2 unrelocated pointers.858 // 4. Comparison between a pointer exclusively derived from null and a859 // non-constant poisoned pointer.860 return true;861 };862 if (!hasValidUnrelocatedUse()) {863 // Print out all non-constant derived pointers that are unrelocated864 // uses, which are invalid.865 if (baseTyLHS == BaseType::NonConstant && !AvailableSet.count(LHS))866 reportInvalidUse(*LHS, I);867 if (baseTyRHS == BaseType::NonConstant && !AvailableSet.count(RHS))868 reportInvalidUse(*RHS, I);869 }870 } else {871 for (const Value *V : I.operands())872 if (containsGCPtrType(V->getType()) &&873 isNotExclusivelyConstantDerived(V) && !AvailableSet.count(V))874 reportInvalidUse(*V, I);875 }876}877 878void InstructionVerifier::reportInvalidUse(const Value &V,879 const Instruction &I) {880 errs() << "Illegal use of unrelocated value found!\n";881 errs() << "Def: " << V << "\n";882 errs() << "Use: " << I << "\n";883 if (!PrintOnly)884 abort();885 AnyInvalidUses = true;886}887 888static void Verify(const Function &F, const DominatorTree &DT,889 const CFGDeadness &CD) {890 LLVM_DEBUG(dbgs() << "Verifying gc pointers in function: " << F.getName()891 << "\n");892 if (PrintOnly)893 dbgs() << "Verifying gc pointers in function: " << F.getName() << "\n";894 895 GCPtrTracker Tracker(F, DT, CD);896 897 // We now have all the information we need to decide if the use of a heap898 // reference is legal or not, given our safepoint semantics.899 900 InstructionVerifier Verifier;901 GCPtrTracker::verifyFunction(std::move(Tracker), Verifier);902 903 if (PrintOnly && !Verifier.hasAnyInvalidUses()) {904 dbgs() << "No illegal uses found by SafepointIRVerifier in: " << F.getName()905 << "\n";906 }907}908