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