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