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 SmallSetVector<const BasicBlock *, 4> DF;
161
162 NewDead.push_back(Elt: BB);
163 while (!NewDead.empty()) {
164 const BasicBlock *D = NewDead.pop_back_val();
165 if (isDeadBlock(BB: D))
166 continue;
167
168 // All blocks dominated by D are dead.
169 SmallVector<BasicBlock *, 8> Dom;
170 DT->getDescendants(R: const_cast<BasicBlock*>(D), Result&: Dom);
171 // Do not need to mark all in and out edges dead
172 // because BB is marked dead and this is enough
173 // to run further.
174 DeadBlocks.insert(Start: Dom.begin(), End: Dom.end());
175
176 // Figure out the dominance-frontier(D).
177 for (BasicBlock *B : Dom)
178 for (BasicBlock *S : successors(BB: B))
179 if (!isDeadBlock(BB: S) && !hasLiveIncomingEdges(BB: S))
180 NewDead.push_back(Elt: S);
181 }
182 }
183
184 void addDeadEdge(const Use &DeadEdge) {
185 if (!DeadEdges.insert(X: &DeadEdge))
186 return;
187
188 BasicBlock *BB = cast_or_null<BasicBlock>(Val: DeadEdge.get());
189 if (hasLiveIncomingEdges(BB))
190 return;
191
192 addDeadBlock(BB);
193 }
194};
195} // namespace
196
197static void Verify(const Function &F, const DominatorTree &DT,
198 const CFGDeadness &CD);
199
200namespace llvm {
201PreservedAnalyses SafepointIRVerifierPass::run(Function &F,
202 FunctionAnalysisManager &AM) {
203 const auto &DT = AM.getResult<DominatorTreeAnalysis>(IR&: F);
204 CFGDeadness CD;
205 CD.processFunction(F, DT);
206 Verify(F, DT, CD);
207 return PreservedAnalyses::all();
208}
209} // namespace llvm
210
211namespace {
212
213struct SafepointIRVerifier : public FunctionPass {
214 static char ID; // Pass identification, replacement for typeid
215 SafepointIRVerifier() : FunctionPass(ID) {
216 initializeSafepointIRVerifierPass(*PassRegistry::getPassRegistry());
217 }
218
219 bool runOnFunction(Function &F) override {
220 auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
221 CFGDeadness CD;
222 CD.processFunction(F, DT);
223 Verify(F, DT, CD);
224 return false; // no modifications
225 }
226
227 void getAnalysisUsage(AnalysisUsage &AU) const override {
228 AU.addRequiredID(ID&: DominatorTreeWrapperPass::ID);
229 AU.setPreservesAll();
230 }
231
232 StringRef getPassName() const override { return "safepoint verifier"; }
233};
234} // namespace
235
236void llvm::verifySafepointIR(Function &F) {
237 SafepointIRVerifier pass;
238 pass.runOnFunction(F);
239}
240
241char SafepointIRVerifier::ID = 0;
242
243FunctionPass *llvm::createSafepointIRVerifierPass() {
244 return new SafepointIRVerifier();
245}
246
247INITIALIZE_PASS_BEGIN(SafepointIRVerifier, "verify-safepoint-ir",
248 "Safepoint IR Verifier", false, false)
249INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
250INITIALIZE_PASS_END(SafepointIRVerifier, "verify-safepoint-ir",
251 "Safepoint IR Verifier", false, false)
252
253static bool isGCPointerType(Type *T) {
254 if (auto *PT = dyn_cast<PointerType>(Val: T))
255 // For the sake of this example GC, we arbitrarily pick addrspace(1) as our
256 // GC managed heap. We know that a pointer into this heap needs to be
257 // updated and that no other pointer does.
258 return (1 == PT->getAddressSpace());
259 return false;
260}
261
262static bool containsGCPtrType(Type *Ty) {
263 if (isGCPointerType(T: Ty))
264 return true;
265 if (VectorType *VT = dyn_cast<VectorType>(Val: Ty))
266 return isGCPointerType(T: VT->getScalarType());
267 if (ArrayType *AT = dyn_cast<ArrayType>(Val: Ty))
268 return containsGCPtrType(Ty: AT->getElementType());
269 if (StructType *ST = dyn_cast<StructType>(Val: Ty))
270 return llvm::any_of(Range: ST->elements(), P: containsGCPtrType);
271 return false;
272}
273
274// Debugging aid -- prints a [Begin, End) range of values.
275template<typename IteratorTy>
276static void PrintValueSet(raw_ostream &OS, IteratorTy Begin, IteratorTy End) {
277 OS << "[ ";
278 while (Begin != End) {
279 OS << **Begin << " ";
280 ++Begin;
281 }
282 OS << "]";
283}
284
285/// The verifier algorithm is phrased in terms of availability. The set of
286/// values "available" at a given point in the control flow graph is the set of
287/// correctly relocated value at that point, and is a subset of the set of
288/// definitions dominating that point.
289
290using AvailableValueSet = DenseSet<const Value *>;
291
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
309/// A given derived pointer can have multiple base pointers through phi/selects.
310/// This type indicates when the base pointer is exclusively constant
311/// (ExclusivelySomeConstant), and if that constant is proven to be exclusively
312/// null, we record that as ExclusivelyNull. In all other cases, the BaseType is
313/// NonConstant.
314enum BaseType {
315 NonConstant = 1, // Base pointers is not exclusively constant.
316 ExclusivelyNull,
317 ExclusivelySomeConstant // Base pointers for a given derived pointer is from a
318 // set of constants, but they are not exclusively
319 // null.
320};
321
322/// Return the baseType for Val which states whether Val is exclusively
323/// derived from constant/null, or not exclusively derived from constant.
324/// Val is exclusively derived off a constant base when all operands of phi and
325/// selects are derived off a constant base.
326static enum BaseType getBaseType(const Value *Val) {
327
328 SmallVector<const Value *, 32> Worklist;
329 DenseSet<const Value *> Visited;
330 bool isExclusivelyDerivedFromNull = true;
331 Worklist.push_back(Elt: Val);
332 // Strip through all the bitcasts and geps to get base pointer. Also check for
333 // the exclusive value when there can be multiple base pointers (through phis
334 // or selects).
335 while(!Worklist.empty()) {
336 const Value *V = Worklist.pop_back_val();
337 if (!Visited.insert(V).second)
338 continue;
339
340 if (const auto *CI = dyn_cast<CastInst>(Val: V)) {
341 Worklist.push_back(Elt: CI->stripPointerCasts());
342 continue;
343 }
344 if (const auto *GEP = dyn_cast<GetElementPtrInst>(Val: V)) {
345 Worklist.push_back(Elt: GEP->getPointerOperand());
346 continue;
347 }
348 // Push all the incoming values of phi node into the worklist for
349 // processing.
350 if (const auto *PN = dyn_cast<PHINode>(Val: V)) {
351 append_range(C&: Worklist, R: PN->incoming_values());
352 continue;
353 }
354 if (const auto *SI = dyn_cast<SelectInst>(Val: V)) {
355 // Push in the true and false values
356 Worklist.push_back(Elt: SI->getTrueValue());
357 Worklist.push_back(Elt: SI->getFalseValue());
358 continue;
359 }
360 if (const auto *GCRelocate = dyn_cast<GCRelocateInst>(Val: V)) {
361 // GCRelocates do not change null-ness or constant-ness of the value.
362 // So we can continue with derived pointer this instruction relocates.
363 Worklist.push_back(Elt: GCRelocate->getDerivedPtr());
364 continue;
365 }
366 if (const auto *FI = dyn_cast<FreezeInst>(Val: V)) {
367 // Freeze does not change null-ness or constant-ness of the value.
368 Worklist.push_back(Elt: FI->getOperand(i_nocapture: 0));
369 continue;
370 }
371 if (isa<Constant>(Val: V)) {
372 // We found at least one base pointer which is non-null, so this derived
373 // pointer is not exclusively derived from null.
374 if (V != Constant::getNullValue(Ty: V->getType()))
375 isExclusivelyDerivedFromNull = false;
376 // Continue processing the remaining values to make sure it's exclusively
377 // constant.
378 continue;
379 }
380 // At this point, we know that the base pointer is not exclusively
381 // constant.
382 return BaseType::NonConstant;
383 }
384 // Now, we know that the base pointer is exclusively constant, but we need to
385 // differentiate between exclusive null constant and non-null constant.
386 return isExclusivelyDerivedFromNull ? BaseType::ExclusivelyNull
387 : BaseType::ExclusivelySomeConstant;
388}
389
390static bool isNotExclusivelyConstantDerived(const Value *V) {
391 return getBaseType(Val: V) == BaseType::NonConstant;
392}
393
394namespace {
395class InstructionVerifier;
396
397/// Builds BasicBlockState for each BB of the function.
398/// It can traverse function for verification and provides all required
399/// information.
400///
401/// GC pointer may be in one of three states: relocated, unrelocated and
402/// poisoned.
403/// Relocated pointer may be used without any restrictions.
404/// Unrelocated pointer cannot be dereferenced, passed as argument to any call
405/// or returned. Unrelocated pointer may be safely compared against another
406/// unrelocated pointer or against a pointer exclusively derived from null.
407/// Poisoned pointers are produced when we somehow derive pointer from relocated
408/// and unrelocated pointers (e.g. phi, select). This pointers may be safely
409/// used in a very limited number of situations. Currently the only way to use
410/// it is comparison against constant exclusively derived from null. All
411/// limitations arise due to their undefined state: this pointers should be
412/// treated as relocated and unrelocated simultaneously.
413/// Rules of deriving:
414/// R + U = P - that's where the poisoned pointers come from
415/// P + X = P
416/// U + U = U
417/// R + R = R
418/// X + C = X
419/// Where "+" - any operation that somehow derive pointer, U - unrelocated,
420/// R - relocated and P - poisoned, C - constant, X - U or R or P or C or
421/// nothing (in case when "+" is unary operation).
422/// Deriving of pointers by itself is always safe.
423/// NOTE: when we are making decision on the status of instruction's result:
424/// a) for phi we need to check status of each input *at the end of
425/// corresponding predecessor BB*.
426/// b) for other instructions we need to check status of each input *at the
427/// current point*.
428///
429/// FIXME: This works fairly well except one case
430/// bb1:
431/// p = *some GC-ptr def*
432/// p1 = gep p, offset
433/// / |
434/// / |
435/// bb2: |
436/// safepoint |
437/// \ |
438/// \ |
439/// bb3:
440/// p2 = phi [p, bb2] [p1, bb1]
441/// p3 = phi [p, bb2] [p, bb1]
442/// here p and p1 is unrelocated
443/// p2 and p3 is poisoned (though they shouldn't be)
444///
445/// This leads to some weird results:
446/// cmp eq p, p2 - illegal instruction (false-positive)
447/// cmp eq p1, p2 - illegal instruction (false-positive)
448/// cmp eq p, p3 - illegal instruction (false-positive)
449/// cmp eq p, p1 - ok
450/// To fix this we need to introduce conception of generations and be able to
451/// check if two values belong to one generation or not. This way p2 will be
452/// considered to be unrelocated and no false alarm will happen.
453class GCPtrTracker {
454 const Function &F;
455 const CFGDeadness &CD;
456 SpecificBumpPtrAllocator<BasicBlockState> BSAllocator;
457 DenseMap<const BasicBlock *, BasicBlockState *> BlockMap;
458 // This set contains defs of unrelocated pointers that are proved to be legal
459 // and don't need verification.
460 DenseSet<const Instruction *> ValidUnrelocatedDefs;
461 // This set contains poisoned defs. They can be safely ignored during
462 // verification too.
463 DenseSet<const Value *> PoisonedDefs;
464
465public:
466 GCPtrTracker(const Function &F, const DominatorTree &DT,
467 const CFGDeadness &CD);
468
469 bool hasLiveIncomingEdge(const PHINode *PN, const BasicBlock *InBB) const {
470 return CD.hasLiveIncomingEdge(PN, InBB);
471 }
472
473 BasicBlockState *getBasicBlockState(const BasicBlock *BB);
474 const BasicBlockState *getBasicBlockState(const BasicBlock *BB) const;
475
476 bool isValuePoisoned(const Value *V) const { return PoisonedDefs.count(V); }
477
478 /// Traverse each BB of the function and call
479 /// InstructionVerifier::verifyInstruction for each possibly invalid
480 /// instruction.
481 /// It destructively modifies GCPtrTracker so it's passed via rvalue reference
482 /// in order to prohibit further usages of GCPtrTracker as it'll be in
483 /// inconsistent state.
484 static void verifyFunction(GCPtrTracker &&Tracker,
485 InstructionVerifier &Verifier);
486
487 /// Returns true for reachable and live blocks.
488 bool isMapped(const BasicBlock *BB) const { return BlockMap.contains(Val: BB); }
489
490private:
491 /// Returns true if the instruction may be safely skipped during verification.
492 bool instructionMayBeSkipped(const Instruction *I) const;
493
494 /// Iterates over all BBs from BlockMap and recalculates AvailableIn/Out for
495 /// each of them until it converges.
496 void recalculateBBsStates();
497
498 /// Remove from Contribution all defs that legally produce unrelocated
499 /// pointers and saves them to ValidUnrelocatedDefs.
500 /// Though Contribution should belong to BBS it is passed separately with
501 /// different const-modifier in order to emphasize (and guarantee) that only
502 /// Contribution will be changed.
503 /// Returns true if Contribution was changed otherwise false.
504 bool removeValidUnrelocatedDefs(const BasicBlock *BB,
505 const BasicBlockState *BBS,
506 AvailableValueSet &Contribution);
507
508 /// Gather all the definitions dominating the start of BB into Result. This is
509 /// simply the defs introduced by every dominating basic block and the
510 /// function arguments.
511 void gatherDominatingDefs(const BasicBlock *BB, AvailableValueSet &Result,
512 const DominatorTree &DT);
513
514 /// Compute the AvailableOut set for BB, based on the BasicBlockState BBS,
515 /// which is the BasicBlockState for BB.
516 /// ContributionChanged is set when the verifier runs for the first time
517 /// (in this case Contribution was changed from 'empty' to its initial state)
518 /// or when Contribution of this BB was changed since last computation.
519 static void transferBlock(const BasicBlock *BB, BasicBlockState &BBS,
520 bool ContributionChanged);
521
522 /// Model the effect of an instruction on the set of available values.
523 static void transferInstruction(const Instruction &I, bool &Cleared,
524 AvailableValueSet &Available);
525};
526
527/// It is a visitor for GCPtrTracker::verifyFunction. It decides if the
528/// instruction (which uses heap reference) is legal or not, given our safepoint
529/// semantics.
530class InstructionVerifier {
531 bool AnyInvalidUses = false;
532
533public:
534 void verifyInstruction(const GCPtrTracker *Tracker, const Instruction &I,
535 const AvailableValueSet &AvailableSet);
536
537 bool hasAnyInvalidUses() const { return AnyInvalidUses; }
538
539private:
540 void reportInvalidUse(const Value &V, const Instruction &I);
541};
542} // end anonymous namespace
543
544GCPtrTracker::GCPtrTracker(const Function &F, const DominatorTree &DT,
545 const CFGDeadness &CD) : F(F), CD(CD) {
546 // Calculate Contribution of each live BB.
547 // Allocate BB states for live blocks.
548 for (const BasicBlock &BB : F)
549 if (!CD.isDeadBlock(BB: &BB)) {
550 BasicBlockState *BBS = new (BSAllocator.Allocate()) BasicBlockState;
551 for (const auto &I : BB)
552 transferInstruction(I, Cleared&: BBS->Cleared, Available&: BBS->Contribution);
553 BlockMap[&BB] = BBS;
554 }
555
556 // Initialize AvailableIn/Out sets of each BB using only information about
557 // dominating BBs.
558 for (auto &BBI : BlockMap) {
559 gatherDominatingDefs(BB: BBI.first, Result&: BBI.second->AvailableIn, DT);
560 transferBlock(BB: BBI.first, BBS&: *BBI.second, ContributionChanged: true);
561 }
562
563 // Simulate the flow of defs through the CFG and recalculate AvailableIn/Out
564 // sets of each BB until it converges. If any def is proved to be an
565 // unrelocated pointer, it will be removed from all BBSs.
566 recalculateBBsStates();
567}
568
569BasicBlockState *GCPtrTracker::getBasicBlockState(const BasicBlock *BB) {
570 return BlockMap.lookup(Val: BB);
571}
572
573const BasicBlockState *GCPtrTracker::getBasicBlockState(
574 const BasicBlock *BB) const {
575 return const_cast<GCPtrTracker *>(this)->getBasicBlockState(BB);
576}
577
578bool GCPtrTracker::instructionMayBeSkipped(const Instruction *I) const {
579 // Poisoned defs are skipped since they are always safe by itself by
580 // definition (for details see comment to this class).
581 return ValidUnrelocatedDefs.count(V: I) || PoisonedDefs.count(V: I);
582}
583
584void GCPtrTracker::verifyFunction(GCPtrTracker &&Tracker,
585 InstructionVerifier &Verifier) {
586 // We need RPO here to a) report always the first error b) report errors in
587 // same order from run to run.
588 ReversePostOrderTraversal<const Function *> RPOT(&Tracker.F);
589 for (const BasicBlock *BB : RPOT) {
590 BasicBlockState *BBS = Tracker.getBasicBlockState(BB);
591 if (!BBS)
592 continue;
593
594 // We destructively modify AvailableIn as we traverse the block instruction
595 // by instruction.
596 AvailableValueSet &AvailableSet = BBS->AvailableIn;
597 for (const Instruction &I : *BB) {
598 if (Tracker.instructionMayBeSkipped(I: &I))
599 continue; // This instruction shouldn't be added to AvailableSet.
600
601 Verifier.verifyInstruction(Tracker: &Tracker, I, AvailableSet);
602
603 // Model the effect of current instruction on AvailableSet to keep the set
604 // relevant at each point of BB.
605 bool Cleared = false;
606 transferInstruction(I, Cleared, Available&: AvailableSet);
607 (void)Cleared;
608 }
609 }
610}
611
612void GCPtrTracker::recalculateBBsStates() {
613 SetVector<const BasicBlock *> Worklist;
614 // TODO: This order is suboptimal, it's better to replace it with priority
615 // queue where priority is RPO number of BB.
616 for (auto &BBI : BlockMap)
617 Worklist.insert(X: BBI.first);
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(Start: succ_begin(BB), End: succ_end(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(I: Defs.begin(), E: Defs.end());
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