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