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