LLVM  7.0.0svn
SafepointIRVerifier.cpp
Go to the documentation of this file.
1 //===-- SafepointIRVerifier.cpp - Verify gc.statepoint invariants ---------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // Run a sanity check on the IR to ensure that Safepoints - if they've been
11 // inserted - were inserted correctly. In particular, look for use of
12 // non-relocated values after a safepoint. It's primary use is to check the
13 // correctness of safepoint insertion immediately after insertion, but it can
14 // also be used to verify that later transforms have not found a way to break
15 // safepoint semenatics.
16 //
17 // In its current form, this verify checks a property which is sufficient, but
18 // not neccessary for correctness. There are some cases where an unrelocated
19 // pointer can be used after the safepoint. Consider this example:
20 //
21 // a = ...
22 // b = ...
23 // (a',b') = safepoint(a,b)
24 // c = cmp eq a b
25 // br c, ..., ....
26 //
27 // Because it is valid to reorder 'c' above the safepoint, this is legal. In
28 // practice, this is a somewhat uncommon transform, but CodeGenPrep does create
29 // idioms like this. The verifier knows about these cases and avoids reporting
30 // false positives.
31 //
32 //===----------------------------------------------------------------------===//
33 
34 #include "llvm/ADT/DenseSet.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/Instructions.h"
42 #include "llvm/IR/Intrinsics.h"
43 #include "llvm/IR/IntrinsicInst.h"
44 #include "llvm/IR/Module.h"
45 #include "llvm/IR/Value.h"
47 #include "llvm/IR/Statepoint.h"
48 #include "llvm/Support/Debug.h"
51 
52 #define DEBUG_TYPE "safepoint-ir-verifier"
53 
54 using namespace llvm;
55 
56 /// This option is used for writing test cases. Instead of crashing the program
57 /// when verification fails, report a message to the console (for FileCheck
58 /// usage) and continue execution as if nothing happened.
59 static cl::opt<bool> PrintOnly("safepoint-ir-verifier-print-only",
60  cl::init(false));
61 
62 static void Verify(const Function &F, const DominatorTree &DT);
63 
64 namespace {
65 struct SafepointIRVerifier : public FunctionPass {
66  static char ID; // Pass identification, replacement for typeid
67  DominatorTree DT;
68  SafepointIRVerifier() : FunctionPass(ID) {
70  }
71 
72  bool runOnFunction(Function &F) override {
73  DT.recalculate(F);
74  Verify(F, DT);
75  return false; // no modifications
76  }
77 
78  void getAnalysisUsage(AnalysisUsage &AU) const override {
79  AU.setPreservesAll();
80  }
81 
82  StringRef getPassName() const override { return "safepoint verifier"; }
83 };
84 } // namespace
85 
87  SafepointIRVerifier pass;
88  pass.runOnFunction(F);
89 }
90 
92 
94  return new SafepointIRVerifier();
95 }
96 
97 INITIALIZE_PASS_BEGIN(SafepointIRVerifier, "verify-safepoint-ir",
98  "Safepoint IR Verifier", false, true)
99 INITIALIZE_PASS_END(SafepointIRVerifier, "verify-safepoint-ir",
100  "Safepoint IR Verifier", false, true)
101 
102 static bool isGCPointerType(Type *T) {
103  if (auto *PT = dyn_cast<PointerType>(T))
104  // For the sake of this example GC, we arbitrarily pick addrspace(1) as our
105  // GC managed heap. We know that a pointer into this heap needs to be
106  // updated and that no other pointer does.
107  return (1 == PT->getAddressSpace());
108  return false;
109 }
110 
111 static bool containsGCPtrType(Type *Ty) {
112  if (isGCPointerType(Ty))
113  return true;
114  if (VectorType *VT = dyn_cast<VectorType>(Ty))
115  return isGCPointerType(VT->getScalarType());
116  if (ArrayType *AT = dyn_cast<ArrayType>(Ty))
117  return containsGCPtrType(AT->getElementType());
118  if (StructType *ST = dyn_cast<StructType>(Ty))
119  return std::any_of(ST->subtypes().begin(), ST->subtypes().end(),
121  return false;
122 }
123 
124 // Debugging aid -- prints a [Begin, End) range of values.
125 template<typename IteratorTy>
126 static void PrintValueSet(raw_ostream &OS, IteratorTy Begin, IteratorTy End) {
127  OS << "[ ";
128  while (Begin != End) {
129  OS << **Begin << " ";
130  ++Begin;
131  }
132  OS << "]";
133 }
134 
135 /// The verifier algorithm is phrased in terms of availability. The set of
136 /// values "available" at a given point in the control flow graph is the set of
137 /// correctly relocated value at that point, and is a subset of the set of
138 /// definitions dominating that point.
139 
141 
142 /// State we compute and track per basic block.
144  // Set of values available coming in, before the phi nodes
146 
147  // Set of values available going out
149 
150  // AvailableOut minus AvailableIn.
151  // All elements are Instructions
153 
154  // True if this block contains a safepoint and thus AvailableIn does not
155  // contribute to AvailableOut.
156  bool Cleared = false;
157 };
158 
159 /// A given derived pointer can have multiple base pointers through phi/selects.
160 /// This type indicates when the base pointer is exclusively constant
161 /// (ExclusivelySomeConstant), and if that constant is proven to be exclusively
162 /// null, we record that as ExclusivelyNull. In all other cases, the BaseType is
163 /// NonConstant.
164 enum BaseType {
165  NonConstant = 1, // Base pointers is not exclusively constant.
167  ExclusivelySomeConstant // Base pointers for a given derived pointer is from a
168  // set of constants, but they are not exclusively
169  // null.
170 };
171 
172 /// Return the baseType for Val which states whether Val is exclusively
173 /// derived from constant/null, or not exclusively derived from constant.
174 /// Val is exclusively derived off a constant base when all operands of phi and
175 /// selects are derived off a constant base.
176 static enum BaseType getBaseType(const Value *Val) {
177 
179  DenseSet<const Value *> Visited;
180  bool isExclusivelyDerivedFromNull = true;
181  Worklist.push_back(Val);
182  // Strip through all the bitcasts and geps to get base pointer. Also check for
183  // the exclusive value when there can be multiple base pointers (through phis
184  // or selects).
185  while(!Worklist.empty()) {
186  const Value *V = Worklist.pop_back_val();
187  if (!Visited.insert(V).second)
188  continue;
189 
190  if (const auto *CI = dyn_cast<CastInst>(V)) {
191  Worklist.push_back(CI->stripPointerCasts());
192  continue;
193  }
194  if (const auto *GEP = dyn_cast<GetElementPtrInst>(V)) {
195  Worklist.push_back(GEP->getPointerOperand());
196  continue;
197  }
198  // Push all the incoming values of phi node into the worklist for
199  // processing.
200  if (const auto *PN = dyn_cast<PHINode>(V)) {
201  for (Value *InV: PN->incoming_values())
202  Worklist.push_back(InV);
203  continue;
204  }
205  if (const auto *SI = dyn_cast<SelectInst>(V)) {
206  // Push in the true and false values
207  Worklist.push_back(SI->getTrueValue());
208  Worklist.push_back(SI->getFalseValue());
209  continue;
210  }
211  if (isa<Constant>(V)) {
212  // We found at least one base pointer which is non-null, so this derived
213  // pointer is not exclusively derived from null.
214  if (V != Constant::getNullValue(V->getType()))
215  isExclusivelyDerivedFromNull = false;
216  // Continue processing the remaining values to make sure it's exclusively
217  // constant.
218  continue;
219  }
220  // At this point, we know that the base pointer is not exclusively
221  // constant.
222  return BaseType::NonConstant;
223  }
224  // Now, we know that the base pointer is exclusively constant, but we need to
225  // differentiate between exclusive null constant and non-null constant.
226  return isExclusivelyDerivedFromNull ? BaseType::ExclusivelyNull
228 }
229 
230 static bool isNotExclusivelyConstantDerived(const Value *V) {
231  return getBaseType(V) == BaseType::NonConstant;
232 }
233 
234 namespace {
235 class InstructionVerifier;
236 
237 /// Builds BasicBlockState for each BB of the function.
238 /// It can traverse function for verification and provides all required
239 /// information.
240 ///
241 /// GC pointer may be in one of three states: relocated, unrelocated and
242 /// poisoned.
243 /// Relocated pointer may be used without any restrictions.
244 /// Unrelocated pointer cannot be dereferenced, passed as argument to any call
245 /// or returned. Unrelocated pointer may be safely compared against another
246 /// unrelocated pointer or against a pointer exclusively derived from null.
247 /// Poisoned pointers are produced when we somehow derive pointer from relocated
248 /// and unrelocated pointers (e.g. phi, select). This pointers may be safely
249 /// used in a very limited number of situations. Currently the only way to use
250 /// it is comparison against constant exclusively derived from null. All
251 /// limitations arise due to their undefined state: this pointers should be
252 /// treated as relocated and unrelocated simultaneously.
253 /// Rules of deriving:
254 /// R + U = P - that's where the poisoned pointers come from
255 /// P + X = P
256 /// U + U = U
257 /// R + R = R
258 /// X + C = X
259 /// Where "+" - any operation that somehow derive pointer, U - unrelocated,
260 /// R - relocated and P - poisoned, C - constant, X - U or R or P or C or
261 /// nothing (in case when "+" is unary operation).
262 /// Deriving of pointers by itself is always safe.
263 /// NOTE: when we are making decision on the status of instruction's result:
264 /// a) for phi we need to check status of each input *at the end of
265 /// corresponding predecessor BB*.
266 /// b) for other instructions we need to check status of each input *at the
267 /// current point*.
268 ///
269 /// FIXME: This works fairly well except one case
270 /// bb1:
271 /// p = *some GC-ptr def*
272 /// p1 = gep p, offset
273 /// / |
274 /// / |
275 /// bb2: |
276 /// safepoint |
277 /// \ |
278 /// \ |
279 /// bb3:
280 /// p2 = phi [p, bb2] [p1, bb1]
281 /// p3 = phi [p, bb2] [p, bb1]
282 /// here p and p1 is unrelocated
283 /// p2 and p3 is poisoned (though they shouldn't be)
284 ///
285 /// This leads to some weird results:
286 /// cmp eq p, p2 - illegal instruction (false-positive)
287 /// cmp eq p1, p2 - illegal instruction (false-positive)
288 /// cmp eq p, p3 - illegal instruction (false-positive)
289 /// cmp eq p, p1 - ok
290 /// To fix this we need to introduce conception of generations and be able to
291 /// check if two values belong to one generation or not. This way p2 will be
292 /// considered to be unrelocated and no false alarm will happen.
293 class GCPtrTracker {
294  const Function &F;
297  // This set contains defs of unrelocated pointers that are proved to be legal
298  // and don't need verification.
299  DenseSet<const Instruction *> ValidUnrelocatedDefs;
300  // This set contains poisoned defs. They can be safely ignored during
301  // verification too.
302  DenseSet<const Value *> PoisonedDefs;
303 
304 public:
305  GCPtrTracker(const Function &F, const DominatorTree &DT);
306 
307  BasicBlockState *getBasicBlockState(const BasicBlock *BB);
308  const BasicBlockState *getBasicBlockState(const BasicBlock *BB) const;
309 
310  bool isValuePoisoned(const Value *V) const { return PoisonedDefs.count(V); }
311 
312  /// Traverse each BB of the function and call
313  /// InstructionVerifier::verifyInstruction for each possibly invalid
314  /// instruction.
315  /// It destructively modifies GCPtrTracker so it's passed via rvalue reference
316  /// in order to prohibit further usages of GCPtrTracker as it'll be in
317  /// inconsistent state.
318  static void verifyFunction(GCPtrTracker &&Tracker,
319  InstructionVerifier &Verifier);
320 
321 private:
322  /// Returns true if the instruction may be safely skipped during verification.
323  bool instructionMayBeSkipped(const Instruction *I) const;
324 
325  /// Iterates over all BBs from BlockMap and recalculates AvailableIn/Out for
326  /// each of them until it converges.
327  void recalculateBBsStates();
328 
329  /// Remove from Contribution all defs that legally produce unrelocated
330  /// pointers and saves them to ValidUnrelocatedDefs.
331  /// Though Contribution should belong to BBS it is passed separately with
332  /// different const-modifier in order to emphasize (and guarantee) that only
333  /// Contribution will be changed.
334  /// Returns true if Contribution was changed otherwise false.
335  bool removeValidUnrelocatedDefs(const BasicBlock *BB,
336  const BasicBlockState *BBS,
337  AvailableValueSet &Contribution);
338 
339  /// Gather all the definitions dominating the start of BB into Result. This is
340  /// simply the defs introduced by every dominating basic block and the
341  /// function arguments.
342  void gatherDominatingDefs(const BasicBlock *BB, AvailableValueSet &Result,
343  const DominatorTree &DT);
344 
345  /// Compute the AvailableOut set for BB, based on the BasicBlockState BBS,
346  /// which is the BasicBlockState for BB.
347  /// ContributionChanged is set when the verifier runs for the first time
348  /// (in this case Contribution was changed from 'empty' to its initial state)
349  /// or when Contribution of this BB was changed since last computation.
350  static void transferBlock(const BasicBlock *BB, BasicBlockState &BBS,
351  bool ContributionChanged);
352 
353  /// Model the effect of an instruction on the set of available values.
354  static void transferInstruction(const Instruction &I, bool &Cleared,
355  AvailableValueSet &Available);
356 };
357 
358 /// It is a visitor for GCPtrTracker::verifyFunction. It decides if the
359 /// instruction (which uses heap reference) is legal or not, given our safepoint
360 /// semantics.
361 class InstructionVerifier {
362  bool AnyInvalidUses = false;
363 
364 public:
365  void verifyInstruction(const GCPtrTracker *Tracker, const Instruction &I,
366  const AvailableValueSet &AvailableSet);
367 
368  bool hasAnyInvalidUses() const { return AnyInvalidUses; }
369 
370 private:
371  void reportInvalidUse(const Value &V, const Instruction &I);
372 };
373 } // end anonymous namespace
374 
375 GCPtrTracker::GCPtrTracker(const Function &F, const DominatorTree &DT) : F(F) {
376  // First, calculate Contribution of each BB.
377  for (const BasicBlock &BB : F) {
378  BasicBlockState *BBS = new (BSAllocator.Allocate()) BasicBlockState;
379  for (const auto &I : BB)
380  transferInstruction(I, BBS->Cleared, BBS->Contribution);
381  BlockMap[&BB] = BBS;
382  }
383 
384  // Initialize AvailableIn/Out sets of each BB using only information about
385  // dominating BBs.
386  for (auto &BBI : BlockMap) {
387  gatherDominatingDefs(BBI.first, BBI.second->AvailableIn, DT);
388  transferBlock(BBI.first, *BBI.second, true);
389  }
390 
391  // Simulate the flow of defs through the CFG and recalculate AvailableIn/Out
392  // sets of each BB until it converges. If any def is proved to be an
393  // unrelocated pointer, it will be removed from all BBSs.
394  recalculateBBsStates();
395 }
396 
397 BasicBlockState *GCPtrTracker::getBasicBlockState(const BasicBlock *BB) {
398  auto it = BlockMap.find(BB);
399  assert(it != BlockMap.end() &&
400  "No such BB in BlockMap! Probably BB from another function");
401  return it->second;
402 }
403 
404 const BasicBlockState *GCPtrTracker::getBasicBlockState(
405  const BasicBlock *BB) const {
406  return const_cast<GCPtrTracker *>(this)->getBasicBlockState(BB);
407 }
408 
409 bool GCPtrTracker::instructionMayBeSkipped(const Instruction *I) const {
410  // Poisoned defs are skipped since they are always safe by itself by
411  // definition (for details see comment to this class).
412  return ValidUnrelocatedDefs.count(I) || PoisonedDefs.count(I);
413 }
414 
415 void GCPtrTracker::verifyFunction(GCPtrTracker &&Tracker,
416  InstructionVerifier &Verifier) {
417  // We need RPO here to a) report always the first error b) report errors in
418  // same order from run to run.
420  for (const BasicBlock *BB : RPOT) {
421  BasicBlockState *BBS = Tracker.getBasicBlockState(BB);
422  // We destructively modify AvailableIn as we traverse the block instruction
423  // by instruction.
424  AvailableValueSet &AvailableSet = BBS->AvailableIn;
425  for (const Instruction &I : *BB) {
426  if (Tracker.instructionMayBeSkipped(&I))
427  continue; // This instruction shouldn't be added to AvailableSet.
428 
429  Verifier.verifyInstruction(&Tracker, I, AvailableSet);
430 
431  // Model the effect of current instruction on AvailableSet to keep the set
432  // relevant at each point of BB.
433  bool Cleared = false;
434  transferInstruction(I, Cleared, AvailableSet);
435  (void)Cleared;
436  }
437  }
438 }
439 
440 void GCPtrTracker::recalculateBBsStates() {
442  // TODO: This order is suboptimal, it's better to replace it with priority
443  // queue where priority is RPO number of BB.
444  for (auto &BBI : BlockMap)
445  Worklist.insert(BBI.first);
446 
447  // This loop iterates the AvailableIn/Out sets until it converges.
448  // The AvailableIn and AvailableOut sets decrease as we iterate.
449  while (!Worklist.empty()) {
450  const BasicBlock *BB = Worklist.pop_back_val();
451  BasicBlockState *BBS = BlockMap[BB];
452 
453  size_t OldInCount = BBS->AvailableIn.size();
454  for (const BasicBlock *PBB : predecessors(BB))
455  set_intersect(BBS->AvailableIn, BlockMap[PBB]->AvailableOut);
456 
457  assert(OldInCount >= BBS->AvailableIn.size() && "invariant!");
458 
459  bool InputsChanged = OldInCount != BBS->AvailableIn.size();
460  bool ContributionChanged =
461  removeValidUnrelocatedDefs(BB, BBS, BBS->Contribution);
462  if (!InputsChanged && !ContributionChanged)
463  continue;
464 
465  size_t OldOutCount = BBS->AvailableOut.size();
466  transferBlock(BB, *BBS, ContributionChanged);
467  if (OldOutCount != BBS->AvailableOut.size()) {
468  assert(OldOutCount > BBS->AvailableOut.size() && "invariant!");
469  Worklist.insert(succ_begin(BB), succ_end(BB));
470  }
471  }
472 }
473 
474 bool GCPtrTracker::removeValidUnrelocatedDefs(const BasicBlock *BB,
475  const BasicBlockState *BBS,
476  AvailableValueSet &Contribution) {
477  assert(&BBS->Contribution == &Contribution &&
478  "Passed Contribution should be from the passed BasicBlockState!");
479  AvailableValueSet AvailableSet = BBS->AvailableIn;
480  bool ContributionChanged = false;
481  // For explanation why instructions are processed this way see
482  // "Rules of deriving" in the comment to this class.
483  for (const Instruction &I : *BB) {
484  bool ValidUnrelocatedPointerDef = false;
485  bool PoisonedPointerDef = false;
486  // TODO: `select` instructions should be handled here too.
487  if (const PHINode *PN = dyn_cast<PHINode>(&I)) {
488  if (containsGCPtrType(PN->getType())) {
489  // If both is true, output is poisoned.
490  bool HasRelocatedInputs = false;
491  bool HasUnrelocatedInputs = false;
492  for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
493  const BasicBlock *InBB = PN->getIncomingBlock(i);
494  const Value *InValue = PN->getIncomingValue(i);
495 
496  if (isNotExclusivelyConstantDerived(InValue)) {
497  if (isValuePoisoned(InValue)) {
498  // If any of inputs is poisoned, output is always poisoned too.
499  HasRelocatedInputs = true;
500  HasUnrelocatedInputs = true;
501  break;
502  }
503  if (BlockMap[InBB]->AvailableOut.count(InValue))
504  HasRelocatedInputs = true;
505  else
506  HasUnrelocatedInputs = true;
507  }
508  }
509  if (HasUnrelocatedInputs) {
510  if (HasRelocatedInputs)
511  PoisonedPointerDef = true;
512  else
513  ValidUnrelocatedPointerDef = true;
514  }
515  }
516  } else if ((isa<GetElementPtrInst>(I) || isa<BitCastInst>(I)) &&
517  containsGCPtrType(I.getType())) {
518  // GEP/bitcast of unrelocated pointer is legal by itself but this def
519  // shouldn't appear in any AvailableSet.
520  for (const Value *V : I.operands())
521  if (containsGCPtrType(V->getType()) &&
522  isNotExclusivelyConstantDerived(V) && !AvailableSet.count(V)) {
523  if (isValuePoisoned(V))
524  PoisonedPointerDef = true;
525  else
526  ValidUnrelocatedPointerDef = true;
527  break;
528  }
529  }
530  assert(!(ValidUnrelocatedPointerDef && PoisonedPointerDef) &&
531  "Value cannot be both unrelocated and poisoned!");
532  if (ValidUnrelocatedPointerDef) {
533  // Remove def of unrelocated pointer from Contribution of this BB and
534  // trigger update of all its successors.
535  Contribution.erase(&I);
536  PoisonedDefs.erase(&I);
537  ValidUnrelocatedDefs.insert(&I);
538  DEBUG(dbgs() << "Removing urelocated " << I << " from Contribution of "
539  << BB->getName() << "\n");
540  ContributionChanged = true;
541  } else if (PoisonedPointerDef) {
542  // Mark pointer as poisoned, remove its def from Contribution and trigger
543  // update of all successors.
544  Contribution.erase(&I);
545  PoisonedDefs.insert(&I);
546  DEBUG(dbgs() << "Removing poisoned " << I << " from Contribution of "
547  << BB->getName() << "\n");
548  ContributionChanged = true;
549  } else {
550  bool Cleared = false;
551  transferInstruction(I, Cleared, AvailableSet);
552  (void)Cleared;
553  }
554  }
555  return ContributionChanged;
556 }
557 
558 void GCPtrTracker::gatherDominatingDefs(const BasicBlock *BB,
559  AvailableValueSet &Result,
560  const DominatorTree &DT) {
561  DomTreeNode *DTN = DT[const_cast<BasicBlock *>(BB)];
562 
563  while (DTN->getIDom()) {
564  DTN = DTN->getIDom();
565  const auto &Defs = BlockMap[DTN->getBlock()]->Contribution;
566  Result.insert(Defs.begin(), Defs.end());
567  // If this block is 'Cleared', then nothing LiveIn to this block can be
568  // available after this block completes. Note: This turns out to be
569  // really important for reducing memory consuption of the initial available
570  // sets and thus peak memory usage by this verifier.
571  if (BlockMap[DTN->getBlock()]->Cleared)
572  return;
573  }
574 
575  for (const Argument &A : BB->getParent()->args())
576  if (containsGCPtrType(A.getType()))
577  Result.insert(&A);
578 }
579 
580 void GCPtrTracker::transferBlock(const BasicBlock *BB, BasicBlockState &BBS,
581  bool ContributionChanged) {
582  const AvailableValueSet &AvailableIn = BBS.AvailableIn;
583  AvailableValueSet &AvailableOut = BBS.AvailableOut;
584 
585  if (BBS.Cleared) {
586  // AvailableOut will change only when Contribution changed.
587  if (ContributionChanged)
588  AvailableOut = BBS.Contribution;
589  } else {
590  // Otherwise, we need to reduce the AvailableOut set by things which are no
591  // longer in our AvailableIn
592  AvailableValueSet Temp = BBS.Contribution;
593  set_union(Temp, AvailableIn);
594  AvailableOut = std::move(Temp);
595  }
596 
597  DEBUG(dbgs() << "Transfered block " << BB->getName() << " from ";
598  PrintValueSet(dbgs(), AvailableIn.begin(), AvailableIn.end());
599  dbgs() << " to ";
600  PrintValueSet(dbgs(), AvailableOut.begin(), AvailableOut.end());
601  dbgs() << "\n";);
602 }
603 
604 void GCPtrTracker::transferInstruction(const Instruction &I, bool &Cleared,
605  AvailableValueSet &Available) {
606  if (isStatepoint(I)) {
607  Cleared = true;
608  Available.clear();
609  } else if (containsGCPtrType(I.getType()))
610  Available.insert(&I);
611 }
612 
613 void InstructionVerifier::verifyInstruction(
614  const GCPtrTracker *Tracker, const Instruction &I,
615  const AvailableValueSet &AvailableSet) {
616  if (const PHINode *PN = dyn_cast<PHINode>(&I)) {
617  if (containsGCPtrType(PN->getType()))
618  for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
619  const BasicBlock *InBB = PN->getIncomingBlock(i);
620  const Value *InValue = PN->getIncomingValue(i);
621 
622  if (isNotExclusivelyConstantDerived(InValue) &&
623  !Tracker->getBasicBlockState(InBB)->AvailableOut.count(InValue))
624  reportInvalidUse(*InValue, *PN);
625  }
626  } else if (isa<CmpInst>(I) &&
628  Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
629  enum BaseType baseTyLHS = getBaseType(LHS),
630  baseTyRHS = getBaseType(RHS);
631 
632  // Returns true if LHS and RHS are unrelocated pointers and they are
633  // valid unrelocated uses.
634  auto hasValidUnrelocatedUse = [&AvailableSet, Tracker, baseTyLHS, baseTyRHS,
635  &LHS, &RHS] () {
636  // A cmp instruction has valid unrelocated pointer operands only if
637  // both operands are unrelocated pointers.
638  // In the comparison between two pointers, if one is an unrelocated
639  // use, the other *should be* an unrelocated use, for this
640  // instruction to contain valid unrelocated uses. This unrelocated
641  // use can be a null constant as well, or another unrelocated
642  // pointer.
643  if (AvailableSet.count(LHS) || AvailableSet.count(RHS))
644  return false;
645  // Constant pointers (that are not exclusively null) may have
646  // meaning in different VMs, so we cannot reorder the compare
647  // against constant pointers before the safepoint. In other words,
648  // comparison of an unrelocated use against a non-null constant
649  // maybe invalid.
650  if ((baseTyLHS == BaseType::ExclusivelySomeConstant &&
651  baseTyRHS == BaseType::NonConstant) ||
652  (baseTyLHS == BaseType::NonConstant &&
653  baseTyRHS == BaseType::ExclusivelySomeConstant))
654  return false;
655 
656  // If one of pointers is poisoned and other is not exclusively derived
657  // from null it is an invalid expression: it produces poisoned result
658  // and unless we want to track all defs (not only gc pointers) the only
659  // option is to prohibit such instructions.
660  if ((Tracker->isValuePoisoned(LHS) && baseTyRHS != ExclusivelyNull) ||
661  (Tracker->isValuePoisoned(RHS) && baseTyLHS != ExclusivelyNull))
662  return false;
663 
664  // All other cases are valid cases enumerated below:
665  // 1. Comparison between an exclusively derived null pointer and a
666  // constant base pointer.
667  // 2. Comparison between an exclusively derived null pointer and a
668  // non-constant unrelocated base pointer.
669  // 3. Comparison between 2 unrelocated pointers.
670  // 4. Comparison between a pointer exclusively derived from null and a
671  // non-constant poisoned pointer.
672  return true;
673  };
674  if (!hasValidUnrelocatedUse()) {
675  // Print out all non-constant derived pointers that are unrelocated
676  // uses, which are invalid.
677  if (baseTyLHS == BaseType::NonConstant && !AvailableSet.count(LHS))
678  reportInvalidUse(*LHS, I);
679  if (baseTyRHS == BaseType::NonConstant && !AvailableSet.count(RHS))
680  reportInvalidUse(*RHS, I);
681  }
682  } else {
683  for (const Value *V : I.operands())
684  if (containsGCPtrType(V->getType()) &&
685  isNotExclusivelyConstantDerived(V) && !AvailableSet.count(V))
686  reportInvalidUse(*V, I);
687  }
688 }
689 
690 void InstructionVerifier::reportInvalidUse(const Value &V,
691  const Instruction &I) {
692  errs() << "Illegal use of unrelocated value found!\n";
693  errs() << "Def: " << V << "\n";
694  errs() << "Use: " << I << "\n";
695  if (!PrintOnly)
696  abort();
697  AnyInvalidUses = true;
698 }
699 
700 static void Verify(const Function &F, const DominatorTree &DT) {
701  DEBUG(dbgs() << "Verifying gc pointers in function: " << F.getName() << "\n");
702  if (PrintOnly)
703  dbgs() << "Verifying gc pointers in function: " << F.getName() << "\n";
704 
705  GCPtrTracker Tracker(F, DT);
706 
707  // We now have all the information we need to decide if the use of a heap
708  // reference is legal or not, given our safepoint semantics.
709 
710  InstructionVerifier Verifier;
711  GCPtrTracker::verifyFunction(std::move(Tracker), Verifier);
712 
713  if (PrintOnly && !Verifier.hasAnyInvalidUses()) {
714  dbgs() << "No illegal uses found by SafepointIRVerifier in: " << F.getName()
715  << "\n";
716  }
717 }
static void PrintValueSet(raw_ostream &OS, IteratorTy Begin, IteratorTy End)
Safe Stack instrumentation pass
Definition: SafeStack.cpp:848
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:30
LLVM_NODISCARD T pop_back_val()
Definition: SetVector.h:228
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
void initializeSafepointIRVerifierPass(PassRegistry &)
Implements a dense probed hash-table based set.
Definition: DenseSet.h:221
void recalculate(ParentType &Func)
recalculate - compute a dominator tree for the given function
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
F(f)
static bool isNotExclusivelyConstantDerived(const Value *V)
Hexagon Common GEP
static Constant * getNullValue(Type *Ty)
Constructor to create a &#39;0&#39; constant of arbitrary type.
Definition: Constants.cpp:206
AvailableValueSet AvailableIn
Class to represent struct types.
Definition: DerivedTypes.h:201
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:103
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:245
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:142
Class to represent array types.
Definition: DerivedTypes.h:369
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:140
Value * getOperand(unsigned i) const
Definition: User.h:154
Interval::succ_iterator succ_end(Interval *I)
Definition: Interval.h:106
AvailableValueSet Contribution
static void Verify(const Function &F, const DominatorTree &DT)
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:406
void verifySafepointIR(Function &F)
Run the safepoint verifier over a single function. Crashes on failure.
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:40
LLVM Basic Block Representation.
Definition: BasicBlock.h:59
The instances of the Type class are immutable: once they are created, they are never changed...
Definition: Type.h:46
verify safepoint Safepoint IR static true bool isGCPointerType(Type *T)
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:821
static const unsigned End
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:285
op_range operands()
Definition: User.h:222
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.
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:862
Module.h This file contains the declarations for the Module class.
size_type size() const
Definition: DenseSet.h:75
INITIALIZE_PASS_BEGIN(SafepointIRVerifier, "verify-safepoint-ir", "Safepoint IR Verifier", false, true) INITIALIZE_PASS_END(SafepointIRVerifier
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:383
pred_range predecessors(BasicBlock *BB)
Definition: CFG.h:110
A BumpPtrAllocator that allows only elements of a specific type to be allocated.
Definition: Allocator.h:385
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:393
void setPreservesAll()
Set by analyses that do not transform their input at all.
Basic Alias true
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:61
verify safepoint Safepoint IR Verifier
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:224
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:108
#define I(x, y, z)
Definition: MD5.cpp:58
bool empty() const
Determine if the SetVector is empty or not.
Definition: SetVector.h:73
bool verifyFunction(const Function &F, raw_ostream *OS=nullptr)
Check a function for errors, useful for use when debugging a pass.
Definition: Verifier.cpp:4642
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
bool isStatepoint(ImmutableCallSite CS)
Definition: Statepoint.cpp:27
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
LLVM Value Representation.
Definition: Value.h:73
A vector that has set insertion semantics.
Definition: SetVector.h:41
verify safepoint ir
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:44
#define DEBUG(X)
Definition: Debug.h:118
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:49
bool set_union(S1Ty &S1, const S2Ty &S2)
set_union(A, B) - Compute A := A u B, return whether A changed.
Definition: SetOperations.h:23
Statically lint checks LLVM IR
Definition: Lint.cpp:193
iterator_range< arg_iterator > args()
Definition: Function.h:667