1 //===-- SafepointIRVerifier.cpp - Verify gc.statepoint invariants ---------===//
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-exception
7 //===----------------------------------------------------------------------===//
9 // Run a sanity check on the IR to ensure that Safepoints - if they've been
10 // inserted - were inserted correctly. In particular, look for use of
11 // non-relocated values after a safepoint. It's primary use is to check the
12 // correctness of safepoint insertion immediately after insertion, but it can
13 // also be used to verify that later transforms have not found a way to break
14 // safepoint semenatics.
16 // In its current form, this verify checks a property which is sufficient, but
17 // not neccessary for correctness. There are some cases where an unrelocated
18 // pointer can be used after the safepoint. Consider this example:
22 // (a',b') = safepoint(a,b)
26 // Because it is valid to reorder 'c' above the safepoint, this is legal. In
27 // practice, this is a somewhat uncommon transform, but CodeGenPrep does create
28 // idioms like this. The verifier knows about these cases and avoids reporting
31 //===----------------------------------------------------------------------===//
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/Instructions.h"
42 #include "llvm/IR/IntrinsicInst.h"
43 #include "llvm/IR/Intrinsics.h"
44 #include "llvm/IR/Module.h"
45 #include "llvm/IR/Statepoint.h"
46 #include "llvm/IR/Value.h"
47 #include "llvm/InitializePasses.h"
48 #include "llvm/Support/Allocator.h"
49 #include "llvm/Support/CommandLine.h"
50 #include "llvm/Support/Debug.h"
51 #include "llvm/Support/raw_ostream.h"
53 #define DEBUG_TYPE "safepoint-ir-verifier"
57 /// This option is used for writing test cases. Instead of crashing the program
58 /// when verification fails, report a message to the console (for FileCheck
59 /// usage) and continue execution as if nothing happened.
60 static cl::opt<bool> PrintOnly("safepoint-ir-verifier-print-only",
65 /// This CFG Deadness finds dead blocks and edges. Algorithm starts with a set
66 /// of blocks unreachable from entry then propagates deadness using foldable
67 /// conditional branches without modifying CFG. So GVN does but it changes CFG
68 /// by splitting critical edges. In most cases passes rely on SimplifyCFG to
69 /// clean up dead blocks, but in some cases, like verification or loop passes
70 /// it's not possible.
72 const DominatorTree *DT = nullptr;
73 SetVector<const BasicBlock *> DeadBlocks;
74 SetVector<const Use *> DeadEdges; // Contains all dead edges from live blocks.
77 /// Return the edge that coresponds to the predecessor.
78 static const Use& getEdge(const_pred_iterator &PredIt) {
79 auto &PU = PredIt.getUse();
80 return PU.getUser()->getOperandUse(PU.getOperandNo());
83 /// Return true if there is at least one live edge that corresponds to the
84 /// basic block InBB listed in the phi node.
85 bool hasLiveIncomingEdge(const PHINode *PN, const BasicBlock *InBB) const {
86 assert(!isDeadBlock(InBB) && "block must be live");
87 const BasicBlock* BB = PN->getParent();
89 for (const_pred_iterator PredIt(BB), End(BB, true); PredIt != End; ++PredIt) {
90 if (InBB == *PredIt) {
91 if (!isDeadEdge(&getEdge(PredIt)))
97 assert(Listed && "basic block is not found among incoming blocks");
102 bool isDeadBlock(const BasicBlock *BB) const {
103 return DeadBlocks.count(BB);
106 bool isDeadEdge(const Use *U) const {
107 assert(cast<Instruction>(U->getUser())->isTerminator() &&
108 "edge must be operand of terminator");
109 assert(cast_or_null<BasicBlock>(U->get()) &&
110 "edge must refer to basic block");
111 assert(!isDeadBlock(cast<Instruction>(U->getUser())->getParent()) &&
112 "isDeadEdge() must be applied to edge from live block");
113 return DeadEdges.count(U);
116 bool hasLiveIncomingEdges(const BasicBlock *BB) const {
117 // Check if all incoming edges are dead.
118 for (const_pred_iterator PredIt(BB), End(BB, true); PredIt != End; ++PredIt) {
119 auto &PU = PredIt.getUse();
120 const Use &U = PU.getUser()->getOperandUse(PU.getOperandNo());
121 if (!isDeadBlock(*PredIt) && !isDeadEdge(&U))
122 return true; // Found a live edge.
127 void processFunction(const Function &F, const DominatorTree &DT) {
130 // Start with all blocks unreachable from entry.
131 for (const BasicBlock &BB : F)
132 if (!DT.isReachableFromEntry(&BB))
133 DeadBlocks.insert(&BB);
135 // Top-down walk of the dominator tree
136 ReversePostOrderTraversal<const Function *> RPOT(&F);
137 for (const BasicBlock *BB : RPOT) {
138 const Instruction *TI = BB->getTerminator();
139 assert(TI && "blocks must be well formed");
141 // For conditional branches, we can perform simple conditional propagation on
142 // the condition value itself.
143 const BranchInst *BI = dyn_cast<BranchInst>(TI);
144 if (!BI || !BI->isConditional() || !isa<Constant>(BI->getCondition()))
147 // If a branch has two identical successors, we cannot declare either dead.
148 if (BI->getSuccessor(0) == BI->getSuccessor(1))
151 ConstantInt *Cond = dyn_cast<ConstantInt>(BI->getCondition());
155 addDeadEdge(BI->getOperandUse(Cond->getZExtValue() ? 1 : 2));
160 void addDeadBlock(const BasicBlock *BB) {
161 SmallVector<const BasicBlock *, 4> NewDead;
162 SmallSetVector<const BasicBlock *, 4> DF;
164 NewDead.push_back(BB);
165 while (!NewDead.empty()) {
166 const BasicBlock *D = NewDead.pop_back_val();
170 // All blocks dominated by D are dead.
171 SmallVector<BasicBlock *, 8> Dom;
172 DT->getDescendants(const_cast<BasicBlock*>(D), Dom);
173 // Do not need to mark all in and out edges dead
174 // because BB is marked dead and this is enough
176 DeadBlocks.insert(Dom.begin(), Dom.end());
178 // Figure out the dominance-frontier(D).
179 for (BasicBlock *B : Dom)
180 for (BasicBlock *S : successors(B))
181 if (!isDeadBlock(S) && !hasLiveIncomingEdges(S))
182 NewDead.push_back(S);
186 void addDeadEdge(const Use &DeadEdge) {
187 if (!DeadEdges.insert(&DeadEdge))
190 BasicBlock *BB = cast_or_null<BasicBlock>(DeadEdge.get());
191 if (hasLiveIncomingEdges(BB))
199 static void Verify(const Function &F, const DominatorTree &DT,
200 const CFGDeadness &CD);
203 PreservedAnalyses SafepointIRVerifierPass::run(Function &F,
204 FunctionAnalysisManager &AM) {
205 const auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
207 CD.processFunction(F, DT);
209 return PreservedAnalyses::all();
215 struct SafepointIRVerifier : public FunctionPass {
216 static char ID; // Pass identification, replacement for typeid
217 SafepointIRVerifier() : FunctionPass(ID) {
218 initializeSafepointIRVerifierPass(*PassRegistry::getPassRegistry());
221 bool runOnFunction(Function &F) override {
222 auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
224 CD.processFunction(F, DT);
226 return false; // no modifications
229 void getAnalysisUsage(AnalysisUsage &AU) const override {
230 AU.addRequiredID(DominatorTreeWrapperPass::ID);
231 AU.setPreservesAll();
234 StringRef getPassName() const override { return "safepoint verifier"; }
238 void llvm::verifySafepointIR(Function &F) {
239 SafepointIRVerifier pass;
240 pass.runOnFunction(F);
243 char SafepointIRVerifier::ID = 0;
245 FunctionPass *llvm::createSafepointIRVerifierPass() {
246 return new SafepointIRVerifier();
249 INITIALIZE_PASS_BEGIN(SafepointIRVerifier, "verify-safepoint-ir",
250 "Safepoint IR Verifier", false, false)
251 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
252 INITIALIZE_PASS_END(SafepointIRVerifier, "verify-safepoint-ir",
253 "Safepoint IR Verifier", false, false)
255 static bool isGCPointerType(Type *T) {
256 if (auto *PT = dyn_cast<PointerType>(T))
257 // For the sake of this example GC, we arbitrarily pick addrspace(1) as our
258 // GC managed heap. We know that a pointer into this heap needs to be
259 // updated and that no other pointer does.
260 return (1 == PT->getAddressSpace());
264 static bool containsGCPtrType(Type *Ty) {
265 if (isGCPointerType(Ty))
267 if (VectorType *VT = dyn_cast<VectorType>(Ty))
268 return isGCPointerType(VT->getScalarType());
269 if (ArrayType *AT = dyn_cast<ArrayType>(Ty))
270 return containsGCPtrType(AT->getElementType());
271 if (StructType *ST = dyn_cast<StructType>(Ty))
272 return llvm::any_of(ST->elements(), containsGCPtrType);
276 // Debugging aid -- prints a [Begin, End) range of values.
277 template<typename IteratorTy>
278 static void PrintValueSet(raw_ostream &OS, IteratorTy Begin, IteratorTy End) {
280 while (Begin != End) {
281 OS << **Begin << " ";
287 /// The verifier algorithm is phrased in terms of availability. The set of
288 /// values "available" at a given point in the control flow graph is the set of
289 /// correctly relocated value at that point, and is a subset of the set of
290 /// definitions dominating that point.
292 using AvailableValueSet = DenseSet<const Value *>;
294 /// State we compute and track per basic block.
295 struct BasicBlockState {
296 // Set of values available coming in, before the phi nodes
297 AvailableValueSet AvailableIn;
299 // Set of values available going out
300 AvailableValueSet AvailableOut;
302 // AvailableOut minus AvailableIn.
303 // All elements are Instructions
304 AvailableValueSet Contribution;
306 // True if this block contains a safepoint and thus AvailableIn does not
307 // contribute to AvailableOut.
308 bool Cleared = false;
311 /// A given derived pointer can have multiple base pointers through phi/selects.
312 /// This type indicates when the base pointer is exclusively constant
313 /// (ExclusivelySomeConstant), and if that constant is proven to be exclusively
314 /// null, we record that as ExclusivelyNull. In all other cases, the BaseType is
317 NonConstant = 1, // Base pointers is not exclusively constant.
319 ExclusivelySomeConstant // Base pointers for a given derived pointer is from a
320 // set of constants, but they are not exclusively
324 /// Return the baseType for Val which states whether Val is exclusively
325 /// derived from constant/null, or not exclusively derived from constant.
326 /// Val is exclusively derived off a constant base when all operands of phi and
327 /// selects are derived off a constant base.
328 static enum BaseType getBaseType(const Value *Val) {
330 SmallVector<const Value *, 32> Worklist;
331 DenseSet<const Value *> Visited;
332 bool isExclusivelyDerivedFromNull = true;
333 Worklist.push_back(Val);
334 // Strip through all the bitcasts and geps to get base pointer. Also check for
335 // the exclusive value when there can be multiple base pointers (through phis
337 while(!Worklist.empty()) {
338 const Value *V = Worklist.pop_back_val();
339 if (!Visited.insert(V).second)
342 if (const auto *CI = dyn_cast<CastInst>(V)) {
343 Worklist.push_back(CI->stripPointerCasts());
346 if (const auto *GEP = dyn_cast<GetElementPtrInst>(V)) {
347 Worklist.push_back(GEP->getPointerOperand());
350 // Push all the incoming values of phi node into the worklist for
352 if (const auto *PN = dyn_cast<PHINode>(V)) {
353 for (Value *InV: PN->incoming_values())
354 Worklist.push_back(InV);
357 if (const auto *SI = dyn_cast<SelectInst>(V)) {
358 // Push in the true and false values
359 Worklist.push_back(SI->getTrueValue());
360 Worklist.push_back(SI->getFalseValue());
363 if (isa<Constant>(V)) {
364 // We found at least one base pointer which is non-null, so this derived
365 // pointer is not exclusively derived from null.
366 if (V != Constant::getNullValue(V->getType()))
367 isExclusivelyDerivedFromNull = false;
368 // Continue processing the remaining values to make sure it's exclusively
372 // At this point, we know that the base pointer is not exclusively
374 return BaseType::NonConstant;
376 // Now, we know that the base pointer is exclusively constant, but we need to
377 // differentiate between exclusive null constant and non-null constant.
378 return isExclusivelyDerivedFromNull ? BaseType::ExclusivelyNull
379 : BaseType::ExclusivelySomeConstant;
382 static bool isNotExclusivelyConstantDerived(const Value *V) {
383 return getBaseType(V) == BaseType::NonConstant;
387 class InstructionVerifier;
389 /// Builds BasicBlockState for each BB of the function.
390 /// It can traverse function for verification and provides all required
393 /// GC pointer may be in one of three states: relocated, unrelocated and
395 /// Relocated pointer may be used without any restrictions.
396 /// Unrelocated pointer cannot be dereferenced, passed as argument to any call
397 /// or returned. Unrelocated pointer may be safely compared against another
398 /// unrelocated pointer or against a pointer exclusively derived from null.
399 /// Poisoned pointers are produced when we somehow derive pointer from relocated
400 /// and unrelocated pointers (e.g. phi, select). This pointers may be safely
401 /// used in a very limited number of situations. Currently the only way to use
402 /// it is comparison against constant exclusively derived from null. All
403 /// limitations arise due to their undefined state: this pointers should be
404 /// treated as relocated and unrelocated simultaneously.
405 /// Rules of deriving:
406 /// R + U = P - that's where the poisoned pointers come from
411 /// Where "+" - any operation that somehow derive pointer, U - unrelocated,
412 /// R - relocated and P - poisoned, C - constant, X - U or R or P or C or
413 /// nothing (in case when "+" is unary operation).
414 /// Deriving of pointers by itself is always safe.
415 /// NOTE: when we are making decision on the status of instruction's result:
416 /// a) for phi we need to check status of each input *at the end of
417 /// corresponding predecessor BB*.
418 /// b) for other instructions we need to check status of each input *at the
421 /// FIXME: This works fairly well except one case
423 /// p = *some GC-ptr def*
424 /// p1 = gep p, offset
432 /// p2 = phi [p, bb2] [p1, bb1]
433 /// p3 = phi [p, bb2] [p, bb1]
434 /// here p and p1 is unrelocated
435 /// p2 and p3 is poisoned (though they shouldn't be)
437 /// This leads to some weird results:
438 /// cmp eq p, p2 - illegal instruction (false-positive)
439 /// cmp eq p1, p2 - illegal instruction (false-positive)
440 /// cmp eq p, p3 - illegal instruction (false-positive)
441 /// cmp eq p, p1 - ok
442 /// To fix this we need to introduce conception of generations and be able to
443 /// check if two values belong to one generation or not. This way p2 will be
444 /// considered to be unrelocated and no false alarm will happen.
447 const CFGDeadness &CD;
448 SpecificBumpPtrAllocator<BasicBlockState> BSAllocator;
449 DenseMap<const BasicBlock *, BasicBlockState *> BlockMap;
450 // This set contains defs of unrelocated pointers that are proved to be legal
451 // and don't need verification.
452 DenseSet<const Instruction *> ValidUnrelocatedDefs;
453 // This set contains poisoned defs. They can be safely ignored during
455 DenseSet<const Value *> PoisonedDefs;
458 GCPtrTracker(const Function &F, const DominatorTree &DT,
459 const CFGDeadness &CD);
461 bool hasLiveIncomingEdge(const PHINode *PN, const BasicBlock *InBB) const {
462 return CD.hasLiveIncomingEdge(PN, InBB);
465 BasicBlockState *getBasicBlockState(const BasicBlock *BB);
466 const BasicBlockState *getBasicBlockState(const BasicBlock *BB) const;
468 bool isValuePoisoned(const Value *V) const { return PoisonedDefs.count(V); }
470 /// Traverse each BB of the function and call
471 /// InstructionVerifier::verifyInstruction for each possibly invalid
473 /// It destructively modifies GCPtrTracker so it's passed via rvalue reference
474 /// in order to prohibit further usages of GCPtrTracker as it'll be in
475 /// inconsistent state.
476 static void verifyFunction(GCPtrTracker &&Tracker,
477 InstructionVerifier &Verifier);
479 /// Returns true for reachable and live blocks.
480 bool isMapped(const BasicBlock *BB) const {
481 return BlockMap.find(BB) != BlockMap.end();
485 /// Returns true if the instruction may be safely skipped during verification.
486 bool instructionMayBeSkipped(const Instruction *I) const;
488 /// Iterates over all BBs from BlockMap and recalculates AvailableIn/Out for
489 /// each of them until it converges.
490 void recalculateBBsStates();
492 /// Remove from Contribution all defs that legally produce unrelocated
493 /// pointers and saves them to ValidUnrelocatedDefs.
494 /// Though Contribution should belong to BBS it is passed separately with
495 /// different const-modifier in order to emphasize (and guarantee) that only
496 /// Contribution will be changed.
497 /// Returns true if Contribution was changed otherwise false.
498 bool removeValidUnrelocatedDefs(const BasicBlock *BB,
499 const BasicBlockState *BBS,
500 AvailableValueSet &Contribution);
502 /// Gather all the definitions dominating the start of BB into Result. This is
503 /// simply the defs introduced by every dominating basic block and the
504 /// function arguments.
505 void gatherDominatingDefs(const BasicBlock *BB, AvailableValueSet &Result,
506 const DominatorTree &DT);
508 /// Compute the AvailableOut set for BB, based on the BasicBlockState BBS,
509 /// which is the BasicBlockState for BB.
510 /// ContributionChanged is set when the verifier runs for the first time
511 /// (in this case Contribution was changed from 'empty' to its initial state)
512 /// or when Contribution of this BB was changed since last computation.
513 static void transferBlock(const BasicBlock *BB, BasicBlockState &BBS,
514 bool ContributionChanged);
516 /// Model the effect of an instruction on the set of available values.
517 static void transferInstruction(const Instruction &I, bool &Cleared,
518 AvailableValueSet &Available);
521 /// It is a visitor for GCPtrTracker::verifyFunction. It decides if the
522 /// instruction (which uses heap reference) is legal or not, given our safepoint
524 class InstructionVerifier {
525 bool AnyInvalidUses = false;
528 void verifyInstruction(const GCPtrTracker *Tracker, const Instruction &I,
529 const AvailableValueSet &AvailableSet);
531 bool hasAnyInvalidUses() const { return AnyInvalidUses; }
534 void reportInvalidUse(const Value &V, const Instruction &I);
536 } // end anonymous namespace
538 GCPtrTracker::GCPtrTracker(const Function &F, const DominatorTree &DT,
539 const CFGDeadness &CD) : F(F), CD(CD) {
540 // Calculate Contribution of each live BB.
541 // Allocate BB states for live blocks.
542 for (const BasicBlock &BB : F)
543 if (!CD.isDeadBlock(&BB)) {
544 BasicBlockState *BBS = new (BSAllocator.Allocate()) BasicBlockState;
545 for (const auto &I : BB)
546 transferInstruction(I, BBS->Cleared, BBS->Contribution);
550 // Initialize AvailableIn/Out sets of each BB using only information about
552 for (auto &BBI : BlockMap) {
553 gatherDominatingDefs(BBI.first, BBI.second->AvailableIn, DT);
554 transferBlock(BBI.first, *BBI.second, true);
557 // Simulate the flow of defs through the CFG and recalculate AvailableIn/Out
558 // sets of each BB until it converges. If any def is proved to be an
559 // unrelocated pointer, it will be removed from all BBSs.
560 recalculateBBsStates();
563 BasicBlockState *GCPtrTracker::getBasicBlockState(const BasicBlock *BB) {
564 auto it = BlockMap.find(BB);
565 return it != BlockMap.end() ? it->second : nullptr;
568 const BasicBlockState *GCPtrTracker::getBasicBlockState(
569 const BasicBlock *BB) const {
570 return const_cast<GCPtrTracker *>(this)->getBasicBlockState(BB);
573 bool GCPtrTracker::instructionMayBeSkipped(const Instruction *I) const {
574 // Poisoned defs are skipped since they are always safe by itself by
575 // definition (for details see comment to this class).
576 return ValidUnrelocatedDefs.count(I) || PoisonedDefs.count(I);
579 void GCPtrTracker::verifyFunction(GCPtrTracker &&Tracker,
580 InstructionVerifier &Verifier) {
581 // We need RPO here to a) report always the first error b) report errors in
582 // same order from run to run.
583 ReversePostOrderTraversal<const Function *> RPOT(&Tracker.F);
584 for (const BasicBlock *BB : RPOT) {
585 BasicBlockState *BBS = Tracker.getBasicBlockState(BB);
589 // We destructively modify AvailableIn as we traverse the block instruction
591 AvailableValueSet &AvailableSet = BBS->AvailableIn;
592 for (const Instruction &I : *BB) {
593 if (Tracker.instructionMayBeSkipped(&I))
594 continue; // This instruction shouldn't be added to AvailableSet.
596 Verifier.verifyInstruction(&Tracker, I, AvailableSet);
598 // Model the effect of current instruction on AvailableSet to keep the set
599 // relevant at each point of BB.
600 bool Cleared = false;
601 transferInstruction(I, Cleared, AvailableSet);
607 void GCPtrTracker::recalculateBBsStates() {
608 SetVector<const BasicBlock *> Worklist;
609 // TODO: This order is suboptimal, it's better to replace it with priority
610 // queue where priority is RPO number of BB.
611 for (auto &BBI : BlockMap)
612 Worklist.insert(BBI.first);
614 // This loop iterates the AvailableIn/Out sets until it converges.
615 // The AvailableIn and AvailableOut sets decrease as we iterate.
616 while (!Worklist.empty()) {
617 const BasicBlock *BB = Worklist.pop_back_val();
618 BasicBlockState *BBS = getBasicBlockState(BB);
620 continue; // Ignore dead successors.
622 size_t OldInCount = BBS->AvailableIn.size();
623 for (const_pred_iterator PredIt(BB), End(BB, true); PredIt != End; ++PredIt) {
624 const BasicBlock *PBB = *PredIt;
625 BasicBlockState *PBBS = getBasicBlockState(PBB);
626 if (PBBS && !CD.isDeadEdge(&CFGDeadness::getEdge(PredIt)))
627 set_intersect(BBS->AvailableIn, PBBS->AvailableOut);
630 assert(OldInCount >= BBS->AvailableIn.size() && "invariant!");
632 bool InputsChanged = OldInCount != BBS->AvailableIn.size();
633 bool ContributionChanged =
634 removeValidUnrelocatedDefs(BB, BBS, BBS->Contribution);
635 if (!InputsChanged && !ContributionChanged)
638 size_t OldOutCount = BBS->AvailableOut.size();
639 transferBlock(BB, *BBS, ContributionChanged);
640 if (OldOutCount != BBS->AvailableOut.size()) {
641 assert(OldOutCount > BBS->AvailableOut.size() && "invariant!");
642 Worklist.insert(succ_begin(BB), succ_end(BB));
647 bool GCPtrTracker::removeValidUnrelocatedDefs(const BasicBlock *BB,
648 const BasicBlockState *BBS,
649 AvailableValueSet &Contribution) {
650 assert(&BBS->Contribution == &Contribution &&
651 "Passed Contribution should be from the passed BasicBlockState!");
652 AvailableValueSet AvailableSet = BBS->AvailableIn;
653 bool ContributionChanged = false;
654 // For explanation why instructions are processed this way see
655 // "Rules of deriving" in the comment to this class.
656 for (const Instruction &I : *BB) {
657 bool ValidUnrelocatedPointerDef = false;
658 bool PoisonedPointerDef = false;
659 // TODO: `select` instructions should be handled here too.
660 if (const PHINode *PN = dyn_cast<PHINode>(&I)) {
661 if (containsGCPtrType(PN->getType())) {
662 // If both is true, output is poisoned.
663 bool HasRelocatedInputs = false;
664 bool HasUnrelocatedInputs = false;
665 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
666 const BasicBlock *InBB = PN->getIncomingBlock(i);
667 if (!isMapped(InBB) ||
668 !CD.hasLiveIncomingEdge(PN, InBB))
669 continue; // Skip dead block or dead edge.
671 const Value *InValue = PN->getIncomingValue(i);
673 if (isNotExclusivelyConstantDerived(InValue)) {
674 if (isValuePoisoned(InValue)) {
675 // If any of inputs is poisoned, output is always poisoned too.
676 HasRelocatedInputs = true;
677 HasUnrelocatedInputs = true;
680 if (BlockMap[InBB]->AvailableOut.count(InValue))
681 HasRelocatedInputs = true;
683 HasUnrelocatedInputs = true;
686 if (HasUnrelocatedInputs) {
687 if (HasRelocatedInputs)
688 PoisonedPointerDef = true;
690 ValidUnrelocatedPointerDef = true;
693 } else if ((isa<GetElementPtrInst>(I) || isa<BitCastInst>(I)) &&
694 containsGCPtrType(I.getType())) {
695 // GEP/bitcast of unrelocated pointer is legal by itself but this def
696 // shouldn't appear in any AvailableSet.
697 for (const Value *V : I.operands())
698 if (containsGCPtrType(V->getType()) &&
699 isNotExclusivelyConstantDerived(V) && !AvailableSet.count(V)) {
700 if (isValuePoisoned(V))
701 PoisonedPointerDef = true;
703 ValidUnrelocatedPointerDef = true;
707 assert(!(ValidUnrelocatedPointerDef && PoisonedPointerDef) &&
708 "Value cannot be both unrelocated and poisoned!");
709 if (ValidUnrelocatedPointerDef) {
710 // Remove def of unrelocated pointer from Contribution of this BB and
711 // trigger update of all its successors.
712 Contribution.erase(&I);
713 PoisonedDefs.erase(&I);
714 ValidUnrelocatedDefs.insert(&I);
715 LLVM_DEBUG(dbgs() << "Removing urelocated " << I
716 << " from Contribution of " << BB->getName() << "\n");
717 ContributionChanged = true;
718 } else if (PoisonedPointerDef) {
719 // Mark pointer as poisoned, remove its def from Contribution and trigger
720 // update of all successors.
721 Contribution.erase(&I);
722 PoisonedDefs.insert(&I);
723 LLVM_DEBUG(dbgs() << "Removing poisoned " << I << " from Contribution of "
724 << BB->getName() << "\n");
725 ContributionChanged = true;
727 bool Cleared = false;
728 transferInstruction(I, Cleared, AvailableSet);
732 return ContributionChanged;
735 void GCPtrTracker::gatherDominatingDefs(const BasicBlock *BB,
736 AvailableValueSet &Result,
737 const DominatorTree &DT) {
738 DomTreeNode *DTN = DT[const_cast<BasicBlock *>(BB)];
740 assert(DTN && "Unreachable blocks are ignored");
741 while (DTN->getIDom()) {
742 DTN = DTN->getIDom();
743 auto BBS = getBasicBlockState(DTN->getBlock());
744 assert(BBS && "immediate dominator cannot be dead for a live block");
745 const auto &Defs = BBS->Contribution;
746 Result.insert(Defs.begin(), Defs.end());
747 // If this block is 'Cleared', then nothing LiveIn to this block can be
748 // available after this block completes. Note: This turns out to be
749 // really important for reducing memory consuption of the initial available
750 // sets and thus peak memory usage by this verifier.
755 for (const Argument &A : BB->getParent()->args())
756 if (containsGCPtrType(A.getType()))
760 void GCPtrTracker::transferBlock(const BasicBlock *BB, BasicBlockState &BBS,
761 bool ContributionChanged) {
762 const AvailableValueSet &AvailableIn = BBS.AvailableIn;
763 AvailableValueSet &AvailableOut = BBS.AvailableOut;
766 // AvailableOut will change only when Contribution changed.
767 if (ContributionChanged)
768 AvailableOut = BBS.Contribution;
770 // Otherwise, we need to reduce the AvailableOut set by things which are no
771 // longer in our AvailableIn
772 AvailableValueSet Temp = BBS.Contribution;
773 set_union(Temp, AvailableIn);
774 AvailableOut = std::move(Temp);
777 LLVM_DEBUG(dbgs() << "Transfered block " << BB->getName() << " from ";
778 PrintValueSet(dbgs(), AvailableIn.begin(), AvailableIn.end());
780 PrintValueSet(dbgs(), AvailableOut.begin(), AvailableOut.end());
784 void GCPtrTracker::transferInstruction(const Instruction &I, bool &Cleared,
785 AvailableValueSet &Available) {
786 if (isa<GCStatepointInst>(I)) {
789 } else if (containsGCPtrType(I.getType()))
790 Available.insert(&I);
793 void InstructionVerifier::verifyInstruction(
794 const GCPtrTracker *Tracker, const Instruction &I,
795 const AvailableValueSet &AvailableSet) {
796 if (const PHINode *PN = dyn_cast<PHINode>(&I)) {
797 if (containsGCPtrType(PN->getType()))
798 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
799 const BasicBlock *InBB = PN->getIncomingBlock(i);
800 const BasicBlockState *InBBS = Tracker->getBasicBlockState(InBB);
802 !Tracker->hasLiveIncomingEdge(PN, InBB))
803 continue; // Skip dead block or dead edge.
805 const Value *InValue = PN->getIncomingValue(i);
807 if (isNotExclusivelyConstantDerived(InValue) &&
808 !InBBS->AvailableOut.count(InValue))
809 reportInvalidUse(*InValue, *PN);
811 } else if (isa<CmpInst>(I) &&
812 containsGCPtrType(I.getOperand(0)->getType())) {
813 Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
814 enum BaseType baseTyLHS = getBaseType(LHS),
815 baseTyRHS = getBaseType(RHS);
817 // Returns true if LHS and RHS are unrelocated pointers and they are
818 // valid unrelocated uses.
819 auto hasValidUnrelocatedUse = [&AvailableSet, Tracker, baseTyLHS, baseTyRHS,
821 // A cmp instruction has valid unrelocated pointer operands only if
822 // both operands are unrelocated pointers.
823 // In the comparison between two pointers, if one is an unrelocated
824 // use, the other *should be* an unrelocated use, for this
825 // instruction to contain valid unrelocated uses. This unrelocated
826 // use can be a null constant as well, or another unrelocated
828 if (AvailableSet.count(LHS) || AvailableSet.count(RHS))
830 // Constant pointers (that are not exclusively null) may have
831 // meaning in different VMs, so we cannot reorder the compare
832 // against constant pointers before the safepoint. In other words,
833 // comparison of an unrelocated use against a non-null constant
835 if ((baseTyLHS == BaseType::ExclusivelySomeConstant &&
836 baseTyRHS == BaseType::NonConstant) ||
837 (baseTyLHS == BaseType::NonConstant &&
838 baseTyRHS == BaseType::ExclusivelySomeConstant))
841 // If one of pointers is poisoned and other is not exclusively derived
842 // from null it is an invalid expression: it produces poisoned result
843 // and unless we want to track all defs (not only gc pointers) the only
844 // option is to prohibit such instructions.
845 if ((Tracker->isValuePoisoned(LHS) && baseTyRHS != ExclusivelyNull) ||
846 (Tracker->isValuePoisoned(RHS) && baseTyLHS != ExclusivelyNull))
849 // All other cases are valid cases enumerated below:
850 // 1. Comparison between an exclusively derived null pointer and a
851 // constant base pointer.
852 // 2. Comparison between an exclusively derived null pointer and a
853 // non-constant unrelocated base pointer.
854 // 3. Comparison between 2 unrelocated pointers.
855 // 4. Comparison between a pointer exclusively derived from null and a
856 // non-constant poisoned pointer.
859 if (!hasValidUnrelocatedUse()) {
860 // Print out all non-constant derived pointers that are unrelocated
861 // uses, which are invalid.
862 if (baseTyLHS == BaseType::NonConstant && !AvailableSet.count(LHS))
863 reportInvalidUse(*LHS, I);
864 if (baseTyRHS == BaseType::NonConstant && !AvailableSet.count(RHS))
865 reportInvalidUse(*RHS, I);
868 for (const Value *V : I.operands())
869 if (containsGCPtrType(V->getType()) &&
870 isNotExclusivelyConstantDerived(V) && !AvailableSet.count(V))
871 reportInvalidUse(*V, I);
875 void InstructionVerifier::reportInvalidUse(const Value &V,
876 const Instruction &I) {
877 errs() << "Illegal use of unrelocated value found!\n";
878 errs() << "Def: " << V << "\n";
879 errs() << "Use: " << I << "\n";
882 AnyInvalidUses = true;
885 static void Verify(const Function &F, const DominatorTree &DT,
886 const CFGDeadness &CD) {
887 LLVM_DEBUG(dbgs() << "Verifying gc pointers in function: " << F.getName()
890 dbgs() << "Verifying gc pointers in function: " << F.getName() << "\n";
892 GCPtrTracker Tracker(F, DT, CD);
894 // We now have all the information we need to decide if the use of a heap
895 // reference is legal or not, given our safepoint semantics.
897 InstructionVerifier Verifier;
898 GCPtrTracker::verifyFunction(std::move(Tracker), Verifier);
900 if (PrintOnly && !Verifier.hasAnyInvalidUses()) {
901 dbgs() << "No illegal uses found by SafepointIRVerifier in: " << F.getName()