LLVM  9.0.0svn
SafepointIRVerifier.cpp
Go to the documentation of this file.
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"
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"
46 #include "llvm/IR/Statepoint.h"
47 #include "llvm/Support/Debug.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;
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(dyn_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(dyn_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
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 
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) {
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.
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 {
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) {
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 {
229  AU.setPreservesAll();
230  }
231 
232  StringRef getPassName() const override { return "safepoint verifier"; }
233 };
234 } // namespace
235 
237  SafepointIRVerifier pass;
238  pass.runOnFunction(F);
239 }
240 
241 char SafepointIRVerifier::ID = 0;
242 
244  return new SafepointIRVerifier();
245 }
246 
247 INITIALIZE_PASS_BEGIN(SafepointIRVerifier, "verify-safepoint-ir",
248  "Safepoint IR Verifier", false, false)
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 
291 
292 /// State we compute and track per basic block.
294  // Set of values available coming in, before the phi nodes
296 
297  // Set of values available going out
299 
300  // AvailableOut minus AvailableIn.
301  // All elements are Instructions
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.
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 
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
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;
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.
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() {
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)))
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) &&
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 }
static void PrintValueSet(raw_ostream &OS, IteratorTy Begin, IteratorTy End)
Safe Stack instrumentation pass
Definition: SafeStack.cpp:903
raw_ostream & errs()
This returns a reference to a raw_ostream for standard error.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
This class represents an incoming formal argument to a Function.
Definition: Argument.h:29
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:776
LLVM_NODISCARD T pop_back_val()
Definition: SetVector.h:227
This class represents lattice values for constants.
Definition: AllocatorList.h:23
void initializeSafepointIRVerifierPass(PassRegistry &)
Implements a dense probed hash-table based set.
Definition: DenseSet.h:249
static enum BaseType getBaseType(const Value *Val)
Return the baseType for Val which states whether Val is exclusively derived from constant/null, or not exclusively derived from constant.
bool erase(const ValueT &V)
Definition: DenseSet.h:95
const Use & getOperandUse(unsigned i) const
Definition: User.h:182
BasicBlock * getSuccessor(unsigned i) const
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:230
F(f)
static bool isNotExclusivelyConstantDerived(const Value *V)
Hexagon Common GEP
Value * getCondition() const
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition: BasicBlock.cpp:137
bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
Definition: Dominators.cpp:299
Value * get() const
Definition: Use.h:107
static Constant * getNullValue(Type *Ty)
Constructor to create a &#39;0&#39; constant of arbitrary type.
Definition: Constants.cpp:274
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:50
AvailableValueSet AvailableIn
Class to represent struct types.
Definition: DerivedTypes.h:233
A Use represents the edge between a Value definition and its users.
Definition: Use.h:55
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Interval::succ_iterator succ_begin(Interval *I)
succ_begin/succ_end - define methods so that Intervals may be used just like BasicBlocks can with the...
Definition: Interval.h:102
User * getUser() const LLVM_READONLY
Returns the User that contains this Use.
Definition: Use.cpp:40
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:244
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:141
bool isStatepoint(const CallBase *Call)
Definition: Statepoint.cpp:20
Class to represent array types.
Definition: DerivedTypes.h:403
verify safepoint Safepoint IR static false bool isGCPointerType(Type *T)
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:144
Value * getOperand(unsigned i) const
Definition: User.h:169
size_type count(const key_type &key) const
Count the number of elements of a given key in the SetVector.
Definition: SetVector.h:210
Interval::succ_iterator succ_end(Interval *I)
Definition: Interval.h:105
Use & getUse() const
getUse - Return the operand Use in the predecessor&#39;s terminator of the successor. ...
Definition: CFG.h:97
AvailableValueSet Contribution
State we compute and track per basic block.
NodeT * getBlock() const
static bool runOnFunction(Function &F, bool PostInlining)
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:432
void verifySafepointIR(Function &F)
Run the safepoint verifier over a single function. Crashes on failure.
uint64_t getZExtValue() const
Return the constant as a 64-bit unsigned integer value after it has been zero extended as appropriate...
Definition: Constants.h:148
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:153
FunctionPass * createSafepointIRVerifierPass()
Create an instance of the safepoint verifier pass which can be added to a pass pipeline to check for ...
void set_intersect(S1Ty &S1, const S2Ty &S2)
set_intersect(A, B) - Compute A := A ^ B Identical to set_intersection, except that it works on set<>...
Definition: SetOperations.h:39
LLVM Basic Block Representation.
Definition: BasicBlock.h:57
The instances of the Type class are immutable: once they are created, they are never changed...
Definition: Type.h:45
Conditional or Unconditional Branch instruction.
void getDescendants(NodeT *R, SmallVectorImpl< NodeT *> &Result) const
Get all nodes dominated by R, including R itself.
DomTreeNodeBase * getIDom() const
std::pair< iterator, bool > insert(const ValueT &V)
Definition: DenseSet.h:187
static bool containsGCPtrType(Type *Ty)
Represent the analysis usage information of a pass.
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1199
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:284
op_range operands()
Definition: User.h:237
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:159
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
bool verify(const TargetRegisterInfo &TRI) const
Check that information hold by this instance make sense for the given TRI.
BaseType
A given derived pointer can have multiple base pointers through phi/selects.
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:297
This is the shared class of boolean and integer constants.
Definition: Constants.h:83
AnalysisUsage & addRequiredID(const void *ID)
Definition: Pass.cpp:314
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:837
Module.h This file contains the declarations for the Module class.
size_type size() const
Definition: DenseSet.h:75
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:374
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
bool isConditional() const
unsigned getNumIncomingValues() const
Return the number of incoming edges.
A BumpPtrAllocator that allows only elements of a specific type to be allocated.
Definition: Allocator.h:441
AvailableValueSet AvailableOut
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
Class to represent vector types.
Definition: DerivedTypes.h:427
void setPreservesAll()
Set by analyses that do not transform their input at all.
INITIALIZE_PASS_BEGIN(SafepointIRVerifier, "verify-safepoint-ir", "Safepoint IR Verifier", false, false) INITIALIZE_PASS_END(SafepointIRVerifier
static cl::opt< bool > PrintOnly("safepoint-ir-verifier-print-only", cl::init(false))
This option is used for writing test cases.
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:55
verify safepoint Safepoint IR Verifier
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:214
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:106
#define I(x, y, z)
Definition: MD5.cpp:58
bool empty() const
Determine if the SetVector is empty or not.
Definition: SetVector.h:72
bool verifyFunction(const Function &F, raw_ostream *OS=nullptr)
Check a function for errors, useful for use when debugging a pass.
Definition: Verifier.cpp:5002
LLVM_NODISCARD std::enable_if<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
Definition: Casting.h:332
size_type count(const_arg_type_t< ValueT > V) const
Return 1 if the specified key is in the set, 0 otherwise.
Definition: DenseSet.h:91
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
LLVM Value Representation.
Definition: Value.h:72
A vector that has set insertion semantics.
Definition: SetVector.h:40
succ_range successors(Instruction *I)
Definition: CFG.h:259
verify safepoint ir
static const Function * getParent(const Value *V)
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:45
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:48
A container for analyses that lazily runs them and caches their results.
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:259
#define LLVM_DEBUG(X)
Definition: Debug.h:122
op_range incoming_values()
bool set_union(S1Ty &S1, const S2Ty &S2)
set_union(A, B) - Compute A := A u B, return whether A changed.
Definition: SetOperations.h:22
Statically lint checks LLVM IR
Definition: Lint.cpp:192
iterator_range< arg_iterator > args()
Definition: Function.h:705
const BasicBlock * getParent() const
Definition: Instruction.h:66
static void Verify(const Function &F, const DominatorTree &DT, const CFGDeadness &CD)