LLVM  14.0.0git
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 
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/IntrinsicInst.h"
43 #include "llvm/IR/Intrinsics.h"
44 #include "llvm/IR/Module.h"
45 #include "llvm/IR/Statepoint.h"
46 #include "llvm/IR/Value.h"
47 #include "llvm/InitializePasses.h"
48 #include "llvm/Support/Allocator.h"
50 #include "llvm/Support/Debug.h"
52 
53 #define DEBUG_TYPE "safepoint-ir-verifier"
54 
55 using namespace llvm;
56 
57 /// This option is used for writing test cases. Instead of crashing the program
58 /// when verification fails, report a message to the console (for FileCheck
59 /// usage) and continue execution as if nothing happened.
60 static cl::opt<bool> PrintOnly("safepoint-ir-verifier-print-only",
61  cl::init(false));
62 
63 namespace {
64 
65 /// This CFG Deadness finds dead blocks and edges. Algorithm starts with a set
66 /// of blocks unreachable from entry then propagates deadness using foldable
67 /// conditional branches without modifying CFG. So GVN does but it changes CFG
68 /// by splitting critical edges. In most cases passes rely on SimplifyCFG to
69 /// clean up dead blocks, but in some cases, like verification or loop passes
70 /// it's not possible.
71 class CFGDeadness {
72  const DominatorTree *DT = nullptr;
74  SetVector<const Use *> DeadEdges; // Contains all dead edges from live blocks.
75 
76 public:
77  /// Return the edge that coresponds to the predecessor.
78  static const Use& getEdge(const_pred_iterator &PredIt) {
79  auto &PU = PredIt.getUse();
80  return PU.getUser()->getOperandUse(PU.getOperandNo());
81  }
82 
83  /// Return true if there is at least one live edge that corresponds to the
84  /// basic block InBB listed in the phi node.
85  bool hasLiveIncomingEdge(const PHINode *PN, const BasicBlock *InBB) const {
86  assert(!isDeadBlock(InBB) && "block must be live");
87  const BasicBlock* BB = PN->getParent();
88  bool Listed = false;
89  for (const_pred_iterator PredIt(BB), End(BB, true); PredIt != End; ++PredIt) {
90  if (InBB == *PredIt) {
91  if (!isDeadEdge(&getEdge(PredIt)))
92  return true;
93  Listed = true;
94  }
95  }
96  (void)Listed;
97  assert(Listed && "basic block is not found among incoming blocks");
98  return false;
99  }
100 
101 
102  bool isDeadBlock(const BasicBlock *BB) const {
103  return DeadBlocks.count(BB);
104  }
105 
106  bool isDeadEdge(const Use *U) const {
107  assert(cast<Instruction>(U->getUser())->isTerminator() &&
108  "edge must be operand of terminator");
109  assert(cast_or_null<BasicBlock>(U->get()) &&
110  "edge must refer to basic block");
111  assert(!isDeadBlock(cast<Instruction>(U->getUser())->getParent()) &&
112  "isDeadEdge() must be applied to edge from live block");
113  return DeadEdges.count(U);
114  }
115 
116  bool hasLiveIncomingEdges(const BasicBlock *BB) const {
117  // Check if all incoming edges are dead.
118  for (const_pred_iterator PredIt(BB), End(BB, true); PredIt != End; ++PredIt) {
119  auto &PU = PredIt.getUse();
120  const Use &U = PU.getUser()->getOperandUse(PU.getOperandNo());
121  if (!isDeadBlock(*PredIt) && !isDeadEdge(&U))
122  return true; // Found a live edge.
123  }
124  return false;
125  }
126 
127  void processFunction(const Function &F, const DominatorTree &DT) {
128  this->DT = &DT;
129 
130  // Start with all blocks unreachable from entry.
131  for (const BasicBlock &BB : F)
132  if (!DT.isReachableFromEntry(&BB))
133  DeadBlocks.insert(&BB);
134 
135  // Top-down walk of the dominator tree
137  for (const BasicBlock *BB : RPOT) {
138  const Instruction *TI = BB->getTerminator();
139  assert(TI && "blocks must be well formed");
140 
141  // For conditional branches, we can perform simple conditional propagation on
142  // the condition value itself.
143  const BranchInst *BI = dyn_cast<BranchInst>(TI);
144  if (!BI || !BI->isConditional() || !isa<Constant>(BI->getCondition()))
145  continue;
146 
147  // If a branch has two identical successors, we cannot declare either dead.
148  if (BI->getSuccessor(0) == BI->getSuccessor(1))
149  continue;
150 
151  ConstantInt *Cond = dyn_cast<ConstantInt>(BI->getCondition());
152  if (!Cond)
153  continue;
154 
155  addDeadEdge(BI->getOperandUse(Cond->getZExtValue() ? 1 : 2));
156  }
157  }
158 
159 protected:
160  void addDeadBlock(const BasicBlock *BB) {
163 
164  NewDead.push_back(BB);
165  while (!NewDead.empty()) {
166  const BasicBlock *D = NewDead.pop_back_val();
167  if (isDeadBlock(D))
168  continue;
169 
170  // All blocks dominated by D are dead.
172  DT->getDescendants(const_cast<BasicBlock*>(D), Dom);
173  // Do not need to mark all in and out edges dead
174  // because BB is marked dead and this is enough
175  // to run further.
176  DeadBlocks.insert(Dom.begin(), Dom.end());
177 
178  // Figure out the dominance-frontier(D).
179  for (BasicBlock *B : Dom)
180  for (BasicBlock *S : successors(B))
181  if (!isDeadBlock(S) && !hasLiveIncomingEdges(S))
182  NewDead.push_back(S);
183  }
184  }
185 
186  void addDeadEdge(const Use &DeadEdge) {
187  if (!DeadEdges.insert(&DeadEdge))
188  return;
189 
190  BasicBlock *BB = cast_or_null<BasicBlock>(DeadEdge.get());
191  if (hasLiveIncomingEdges(BB))
192  return;
193 
194  addDeadBlock(BB);
195  }
196 };
197 } // namespace
198 
199 static void Verify(const Function &F, const DominatorTree &DT,
200  const CFGDeadness &CD);
201 
202 namespace llvm {
205  const auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
206  CFGDeadness CD;
207  CD.processFunction(F, DT);
208  Verify(F, DT, CD);
209  return PreservedAnalyses::all();
210 }
211 } // namespace llvm
212 
213 namespace {
214 
215 struct SafepointIRVerifier : public FunctionPass {
216  static char ID; // Pass identification, replacement for typeid
217  SafepointIRVerifier() : FunctionPass(ID) {
218  initializeSafepointIRVerifierPass(*PassRegistry::getPassRegistry());
219  }
220 
221  bool runOnFunction(Function &F) override {
222  auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
223  CFGDeadness CD;
224  CD.processFunction(F, DT);
225  Verify(F, DT, CD);
226  return false; // no modifications
227  }
228 
229  void getAnalysisUsage(AnalysisUsage &AU) const override {
231  AU.setPreservesAll();
232  }
233 
234  StringRef getPassName() const override { return "safepoint verifier"; }
235 };
236 } // namespace
237 
239  SafepointIRVerifier pass;
240  pass.runOnFunction(F);
241 }
242 
243 char SafepointIRVerifier::ID = 0;
244 
246  return new SafepointIRVerifier();
247 }
248 
249 INITIALIZE_PASS_BEGIN(SafepointIRVerifier, "verify-safepoint-ir",
250  "Safepoint IR Verifier", false, false)
252 INITIALIZE_PASS_END(SafepointIRVerifier, "verify-safepoint-ir",
253  "Safepoint IR Verifier", false, false)
254 
255 static bool isGCPointerType(Type *T) {
256  if (auto *PT = dyn_cast<PointerType>(T))
257  // For the sake of this example GC, we arbitrarily pick addrspace(1) as our
258  // GC managed heap. We know that a pointer into this heap needs to be
259  // updated and that no other pointer does.
260  return (1 == PT->getAddressSpace());
261  return false;
262 }
263 
264 static bool containsGCPtrType(Type *Ty) {
265  if (isGCPointerType(Ty))
266  return true;
267  if (VectorType *VT = dyn_cast<VectorType>(Ty))
268  return isGCPointerType(VT->getScalarType());
269  if (ArrayType *AT = dyn_cast<ArrayType>(Ty))
270  return containsGCPtrType(AT->getElementType());
271  if (StructType *ST = dyn_cast<StructType>(Ty))
272  return llvm::any_of(ST->elements(), containsGCPtrType);
273  return false;
274 }
275 
276 // Debugging aid -- prints a [Begin, End) range of values.
277 template<typename IteratorTy>
278 static void PrintValueSet(raw_ostream &OS, IteratorTy Begin, IteratorTy End) {
279  OS << "[ ";
280  while (Begin != End) {
281  OS << **Begin << " ";
282  ++Begin;
283  }
284  OS << "]";
285 }
286 
287 /// The verifier algorithm is phrased in terms of availability. The set of
288 /// values "available" at a given point in the control flow graph is the set of
289 /// correctly relocated value at that point, and is a subset of the set of
290 /// definitions dominating that point.
291 
293 
294 /// State we compute and track per basic block.
296  // Set of values available coming in, before the phi nodes
298 
299  // Set of values available going out
301 
302  // AvailableOut minus AvailableIn.
303  // All elements are Instructions
305 
306  // True if this block contains a safepoint and thus AvailableIn does not
307  // contribute to AvailableOut.
308  bool Cleared = false;
309 };
310 
311 /// A given derived pointer can have multiple base pointers through phi/selects.
312 /// This type indicates when the base pointer is exclusively constant
313 /// (ExclusivelySomeConstant), and if that constant is proven to be exclusively
314 /// null, we record that as ExclusivelyNull. In all other cases, the BaseType is
315 /// NonConstant.
316 enum BaseType {
317  NonConstant = 1, // Base pointers is not exclusively constant.
319  ExclusivelySomeConstant // Base pointers for a given derived pointer is from a
320  // set of constants, but they are not exclusively
321  // null.
322 };
323 
324 /// Return the baseType for Val which states whether Val is exclusively
325 /// derived from constant/null, or not exclusively derived from constant.
326 /// Val is exclusively derived off a constant base when all operands of phi and
327 /// selects are derived off a constant base.
328 static enum BaseType getBaseType(const Value *Val) {
329 
331  DenseSet<const Value *> Visited;
332  bool isExclusivelyDerivedFromNull = true;
333  Worklist.push_back(Val);
334  // Strip through all the bitcasts and geps to get base pointer. Also check for
335  // the exclusive value when there can be multiple base pointers (through phis
336  // or selects).
337  while(!Worklist.empty()) {
338  const Value *V = Worklist.pop_back_val();
339  if (!Visited.insert(V).second)
340  continue;
341 
342  if (const auto *CI = dyn_cast<CastInst>(V)) {
343  Worklist.push_back(CI->stripPointerCasts());
344  continue;
345  }
346  if (const auto *GEP = dyn_cast<GetElementPtrInst>(V)) {
347  Worklist.push_back(GEP->getPointerOperand());
348  continue;
349  }
350  // Push all the incoming values of phi node into the worklist for
351  // processing.
352  if (const auto *PN = dyn_cast<PHINode>(V)) {
353  append_range(Worklist, PN->incoming_values());
354  continue;
355  }
356  if (const auto *SI = dyn_cast<SelectInst>(V)) {
357  // Push in the true and false values
358  Worklist.push_back(SI->getTrueValue());
359  Worklist.push_back(SI->getFalseValue());
360  continue;
361  }
362  if (isa<Constant>(V)) {
363  // We found at least one base pointer which is non-null, so this derived
364  // pointer is not exclusively derived from null.
365  if (V != Constant::getNullValue(V->getType()))
366  isExclusivelyDerivedFromNull = false;
367  // Continue processing the remaining values to make sure it's exclusively
368  // constant.
369  continue;
370  }
371  // At this point, we know that the base pointer is not exclusively
372  // constant.
373  return BaseType::NonConstant;
374  }
375  // Now, we know that the base pointer is exclusively constant, but we need to
376  // differentiate between exclusive null constant and non-null constant.
377  return isExclusivelyDerivedFromNull ? BaseType::ExclusivelyNull
379 }
380 
381 static bool isNotExclusivelyConstantDerived(const Value *V) {
382  return getBaseType(V) == BaseType::NonConstant;
383 }
384 
385 namespace {
386 class InstructionVerifier;
387 
388 /// Builds BasicBlockState for each BB of the function.
389 /// It can traverse function for verification and provides all required
390 /// information.
391 ///
392 /// GC pointer may be in one of three states: relocated, unrelocated and
393 /// poisoned.
394 /// Relocated pointer may be used without any restrictions.
395 /// Unrelocated pointer cannot be dereferenced, passed as argument to any call
396 /// or returned. Unrelocated pointer may be safely compared against another
397 /// unrelocated pointer or against a pointer exclusively derived from null.
398 /// Poisoned pointers are produced when we somehow derive pointer from relocated
399 /// and unrelocated pointers (e.g. phi, select). This pointers may be safely
400 /// used in a very limited number of situations. Currently the only way to use
401 /// it is comparison against constant exclusively derived from null. All
402 /// limitations arise due to their undefined state: this pointers should be
403 /// treated as relocated and unrelocated simultaneously.
404 /// Rules of deriving:
405 /// R + U = P - that's where the poisoned pointers come from
406 /// P + X = P
407 /// U + U = U
408 /// R + R = R
409 /// X + C = X
410 /// Where "+" - any operation that somehow derive pointer, U - unrelocated,
411 /// R - relocated and P - poisoned, C - constant, X - U or R or P or C or
412 /// nothing (in case when "+" is unary operation).
413 /// Deriving of pointers by itself is always safe.
414 /// NOTE: when we are making decision on the status of instruction's result:
415 /// a) for phi we need to check status of each input *at the end of
416 /// corresponding predecessor BB*.
417 /// b) for other instructions we need to check status of each input *at the
418 /// current point*.
419 ///
420 /// FIXME: This works fairly well except one case
421 /// bb1:
422 /// p = *some GC-ptr def*
423 /// p1 = gep p, offset
424 /// / |
425 /// / |
426 /// bb2: |
427 /// safepoint |
428 /// \ |
429 /// \ |
430 /// bb3:
431 /// p2 = phi [p, bb2] [p1, bb1]
432 /// p3 = phi [p, bb2] [p, bb1]
433 /// here p and p1 is unrelocated
434 /// p2 and p3 is poisoned (though they shouldn't be)
435 ///
436 /// This leads to some weird results:
437 /// cmp eq p, p2 - illegal instruction (false-positive)
438 /// cmp eq p1, p2 - illegal instruction (false-positive)
439 /// cmp eq p, p3 - illegal instruction (false-positive)
440 /// cmp eq p, p1 - ok
441 /// To fix this we need to introduce conception of generations and be able to
442 /// check if two values belong to one generation or not. This way p2 will be
443 /// considered to be unrelocated and no false alarm will happen.
444 class GCPtrTracker {
445  const Function &F;
446  const CFGDeadness &CD;
449  // This set contains defs of unrelocated pointers that are proved to be legal
450  // and don't need verification.
451  DenseSet<const Instruction *> ValidUnrelocatedDefs;
452  // This set contains poisoned defs. They can be safely ignored during
453  // verification too.
454  DenseSet<const Value *> PoisonedDefs;
455 
456 public:
457  GCPtrTracker(const Function &F, const DominatorTree &DT,
458  const CFGDeadness &CD);
459 
460  bool hasLiveIncomingEdge(const PHINode *PN, const BasicBlock *InBB) const {
461  return CD.hasLiveIncomingEdge(PN, InBB);
462  }
463 
464  BasicBlockState *getBasicBlockState(const BasicBlock *BB);
465  const BasicBlockState *getBasicBlockState(const BasicBlock *BB) const;
466 
467  bool isValuePoisoned(const Value *V) const { return PoisonedDefs.count(V); }
468 
469  /// Traverse each BB of the function and call
470  /// InstructionVerifier::verifyInstruction for each possibly invalid
471  /// instruction.
472  /// It destructively modifies GCPtrTracker so it's passed via rvalue reference
473  /// in order to prohibit further usages of GCPtrTracker as it'll be in
474  /// inconsistent state.
475  static void verifyFunction(GCPtrTracker &&Tracker,
476  InstructionVerifier &Verifier);
477 
478  /// Returns true for reachable and live blocks.
479  bool isMapped(const BasicBlock *BB) const {
480  return BlockMap.find(BB) != BlockMap.end();
481  }
482 
483 private:
484  /// Returns true if the instruction may be safely skipped during verification.
485  bool instructionMayBeSkipped(const Instruction *I) const;
486 
487  /// Iterates over all BBs from BlockMap and recalculates AvailableIn/Out for
488  /// each of them until it converges.
489  void recalculateBBsStates();
490 
491  /// Remove from Contribution all defs that legally produce unrelocated
492  /// pointers and saves them to ValidUnrelocatedDefs.
493  /// Though Contribution should belong to BBS it is passed separately with
494  /// different const-modifier in order to emphasize (and guarantee) that only
495  /// Contribution will be changed.
496  /// Returns true if Contribution was changed otherwise false.
497  bool removeValidUnrelocatedDefs(const BasicBlock *BB,
498  const BasicBlockState *BBS,
499  AvailableValueSet &Contribution);
500 
501  /// Gather all the definitions dominating the start of BB into Result. This is
502  /// simply the defs introduced by every dominating basic block and the
503  /// function arguments.
504  void gatherDominatingDefs(const BasicBlock *BB, AvailableValueSet &Result,
505  const DominatorTree &DT);
506 
507  /// Compute the AvailableOut set for BB, based on the BasicBlockState BBS,
508  /// which is the BasicBlockState for BB.
509  /// ContributionChanged is set when the verifier runs for the first time
510  /// (in this case Contribution was changed from 'empty' to its initial state)
511  /// or when Contribution of this BB was changed since last computation.
512  static void transferBlock(const BasicBlock *BB, BasicBlockState &BBS,
513  bool ContributionChanged);
514 
515  /// Model the effect of an instruction on the set of available values.
516  static void transferInstruction(const Instruction &I, bool &Cleared,
518 };
519 
520 /// It is a visitor for GCPtrTracker::verifyFunction. It decides if the
521 /// instruction (which uses heap reference) is legal or not, given our safepoint
522 /// semantics.
523 class InstructionVerifier {
524  bool AnyInvalidUses = false;
525 
526 public:
527  void verifyInstruction(const GCPtrTracker *Tracker, const Instruction &I,
528  const AvailableValueSet &AvailableSet);
529 
530  bool hasAnyInvalidUses() const { return AnyInvalidUses; }
531 
532 private:
533  void reportInvalidUse(const Value &V, const Instruction &I);
534 };
535 } // end anonymous namespace
536 
537 GCPtrTracker::GCPtrTracker(const Function &F, const DominatorTree &DT,
538  const CFGDeadness &CD) : F(F), CD(CD) {
539  // Calculate Contribution of each live BB.
540  // Allocate BB states for live blocks.
541  for (const BasicBlock &BB : F)
542  if (!CD.isDeadBlock(&BB)) {
543  BasicBlockState *BBS = new (BSAllocator.Allocate()) BasicBlockState;
544  for (const auto &I : BB)
545  transferInstruction(I, BBS->Cleared, BBS->Contribution);
546  BlockMap[&BB] = BBS;
547  }
548 
549  // Initialize AvailableIn/Out sets of each BB using only information about
550  // dominating BBs.
551  for (auto &BBI : BlockMap) {
552  gatherDominatingDefs(BBI.first, BBI.second->AvailableIn, DT);
553  transferBlock(BBI.first, *BBI.second, true);
554  }
555 
556  // Simulate the flow of defs through the CFG and recalculate AvailableIn/Out
557  // sets of each BB until it converges. If any def is proved to be an
558  // unrelocated pointer, it will be removed from all BBSs.
559  recalculateBBsStates();
560 }
561 
562 BasicBlockState *GCPtrTracker::getBasicBlockState(const BasicBlock *BB) {
563  return BlockMap.lookup(BB);
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 (isa<GCStatepointInst>(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;
897 
898  if (PrintOnly && !Verifier.hasAnyInvalidUses()) {
899  dbgs() << "No illegal uses found by SafepointIRVerifier in: " << F.getName()
900  << "\n";
901  }
902 }
i
i
Definition: README.txt:29
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:155
llvm::verifySafepointIR
void verifySafepointIR(Function &F)
Run the safepoint verifier over a single function. Crashes on failure.
Definition: SafepointIRVerifier.cpp:238
llvm::Argument
This class represents an incoming formal argument to a Function.
Definition: Argument.h:29
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
llvm::PHINode::incoming_values
op_range incoming_values()
Definition: Instructions.h:2719
BasicBlockState::Cleared
bool Cleared
Definition: SafepointIRVerifier.cpp:308
PrintOnly
static cl::opt< bool > PrintOnly("safepoint-ir-verifier-print-only", cl::init(false))
This option is used for writing test cases.
IntrinsicInst.h
llvm::AnalysisManager::getResult
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:779
SetOperations.h
llvm::succ_end
Interval::succ_iterator succ_end(Interval *I)
Definition: Interval.h:102
llvm::Function
Definition: Function.h:61
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::lookup
ValueT lookup(const_arg_type_t< KeyT > Val) const
lookup - Return the entry for the specified key, or a default constructed value if no such entry exis...
Definition: DenseMap.h:197
llvm::set_union
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
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1168
llvm::Use::get
Value * get() const
Definition: Use.h:67
Allocator.h
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:151
llvm::verifyFunction
bool verifyFunction(const Function &F, raw_ostream *OS=nullptr)
Check a function for errors, useful for use when debugging a pass.
Definition: Verifier.cpp:5815
llvm::FunctionPass::runOnFunction
virtual bool runOnFunction(Function &F)=0
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.
llvm::SpecificBumpPtrAllocator
A BumpPtrAllocator that allows only elements of a specific type to be allocated.
Definition: Allocator.h:376
llvm::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
Module.h
ir
verify safepoint ir
Definition: SafepointIRVerifier.cpp:252
T
#define T
Definition: Mips16ISelLowering.cpp:341
llvm::errs
raw_fd_ostream & errs()
This returns a reference to a raw_ostream for standard error.
Definition: raw_ostream.cpp:892
llvm::SmallVectorImpl::pop_back_val
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:635
llvm::ArrayType
Class to represent array types.
Definition: DerivedTypes.h:357
llvm::DomTreeNodeBase::getIDom
DomTreeNodeBase * getIDom() const
Definition: GenericDomTree.h:89
llvm::successors
succ_range successors(Instruction *I)
Definition: CFG.h:262
BaseType
llvm::detail::DenseSetImpl::insert
std::pair< iterator, bool > insert(const ValueT &V)
Definition: DenseSet.h:206
llvm::detail::DenseSetImpl::count
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:97
BasicBlockState::AvailableOut
AvailableValueSet AvailableOut
Definition: SafepointIRVerifier.cpp:300
llvm::DominatorTreeBase::getDescendants
void getDescendants(NodeT *R, SmallVectorImpl< NodeT * > &Result) const
Get all nodes dominated by R, including R itself.
Definition: GenericDomTree.h:374
getBaseType
static enum BaseType getBaseType(const Value *Val)
Return the baseType for Val which states whether Val is exclusively derived from constant/null,...
Definition: SafepointIRVerifier.cpp:328
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
F
#define F(x, y, z)
Definition: MD5.cpp:56
INITIALIZE_PASS_BEGIN
INITIALIZE_PASS_BEGIN(SafepointIRVerifier, "verify-safepoint-ir", "Safepoint IR Verifier", false, false) INITIALIZE_PASS_END(SafepointIRVerifier
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
llvm::detail::DenseSetImpl::end
iterator end()
Definition: DenseSet.h:174
llvm::User::getOperandUse
const Use & getOperandUse(unsigned i) const
Definition: User.h:182
CommandLine.h
isGCPointerType
verify safepoint Safepoint IR static false bool isGCPointerType(Type *T)
Definition: SafepointIRVerifier.cpp:255
llvm::ConstantInt
This is the shared class of boolean and integer constants.
Definition: Constants.h:79
llvm::PHINode::getIncomingValue
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
Definition: Instructions.h:2729
AvailabilityState::Available
@ Available
We know the block is fully available. This is a fixpoint.
Intrinsics.h
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
ExclusivelySomeConstant
@ ExclusivelySomeConstant
Definition: SafepointIRVerifier.cpp:319
llvm::ms_demangle::QualifierMangleMode::Result
@ Result
DenseSet.h
false
Definition: StackSlotColoring.cpp:142
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
pass
modulo schedule Modulo Schedule test pass
Definition: ModuloSchedule.cpp:2126
llvm::detail::DenseSetImpl::size
size_type size() const
Definition: DenseSet.h:81
llvm::Instruction
Definition: Instruction.h:45
llvm::DominatorTreeWrapperPass
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:287
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:53
llvm::Use::getUser
User * getUser() const
Returns the User that contains this Use.
Definition: Use.h:73
IR
Statically lint checks LLVM IR
Definition: Lint.cpp:744
llvm::SetVector::empty
bool empty() const
Determine if the SetVector is empty or not.
Definition: SetVector.h:72
llvm::PHINode::getNumIncomingValues
unsigned getNumIncomingValues() const
Return the number of incoming edges.
Definition: Instructions.h:2725
Statepoint.h
DF
static RegisterPass< DebugifyFunctionPass > DF("debugify-function", "Attach debug info to a function")
INITIALIZE_PASS_END
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:58
ExclusivelyNull
@ ExclusivelyNull
Definition: SafepointIRVerifier.cpp:318
llvm::BranchInst::getCondition
Value * getCondition() const
Definition: Instructions.h:3149
isNotExclusivelyConstantDerived
static bool isNotExclusivelyConstantDerived(const Value *V)
Definition: SafepointIRVerifier.cpp:381
llvm::VectorType
Base class of all SIMD vector types.
Definition: DerivedTypes.h:389
llvm::DenseSet< const Value * >
Verifier
verify safepoint Safepoint IR Verifier
Definition: SafepointIRVerifier.cpp:253
Verify
static void Verify(const Function &F, const DominatorTree &DT, const CFGDeadness &CD)
Definition: SafepointIRVerifier.cpp:883
BasicBlock.h
llvm::cl::opt< bool >
llvm::DomTreeNodeBase::getBlock
NodeT * getBlock() const
Definition: GenericDomTree.h:88
D
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
llvm::ARM_MB::ST
@ ST
Definition: ARMBaseInfo.h:73
INITIALIZE_PASS_DEPENDENCY
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
move
compiles ldr LCPI1_0 ldr ldr mov lsr tst moveq r1 ldr LCPI1_1 and r0 bx lr It would be better to do something like to fold the shift into the conditional move
Definition: README.txt:546
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:57
llvm::DenseMap
Definition: DenseMap.h:714
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::succ_begin
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:99
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:443
llvm::detail::DenseSetImpl::begin
iterator begin()
Definition: DenseSet.h:173
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::find
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:150
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
SI
StandardInstrumentations SI(Debug, VerifyEach)
SafepointIRVerifier.h
llvm::DominatorTree::isReachableFromEntry
bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
Definition: Dominators.cpp:328
llvm::SetVector::insert
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:141
llvm::any_of
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:1558
llvm::StructType
Class to represent struct types.
Definition: DerivedTypes.h:213
Cond
SmallVector< MachineOperand, 4 > Cond
Definition: BasicBlockSections.cpp:179
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:58
llvm::Pass::getPassName
virtual StringRef getPassName() const
getPassName - Return a nice clean name for a pass.
Definition: Pass.cpp:76
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:256
A
* A
Definition: README_ALTIVEC.txt:89
llvm::append_range
void append_range(Container &C, Range &&R)
Wrapper function to append a range to a container.
Definition: STLExtras.h:1748
verify
ppc ctr loops verify
Definition: PPCCTRLoops.cpp:76
S
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
Definition: README.txt:210
llvm::createSafepointIRVerifierPass
FunctionPass * createSafepointIRVerifierPass()
Create an instance of the safepoint verifier pass which can be added to a pass pipeline to check for ...
Definition: SafepointIRVerifier.cpp:245
llvm::PredIterator
Definition: CFG.h:43
llvm::DomTreeNodeBase< BasicBlock >
BasicBlockState::AvailableIn
AvailableValueSet AvailableIn
Definition: SafepointIRVerifier.cpp:297
llvm::SpecificBumpPtrAllocator::Allocate
T * Allocate(size_t num=1)
Allocate space for an array of objects without constructing them.
Definition: Allocator.h:426
llvm::AnalysisUsage::setPreservesAll
void setPreservesAll()
Set by analyses that do not transform their input at all.
Definition: PassAnalysisSupport.h:130
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::end
iterator end()
Definition: DenseMap.h:83
llvm::initializeSafepointIRVerifierPass
void initializeSafepointIRVerifierPass(PassRegistry &)
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:161
BasicBlockState::Contribution
AvailableValueSet Contribution
Definition: SafepointIRVerifier.cpp:304
llvm::PredIterator::getUse
Use & getUse() const
getUse - Return the operand Use in the predecessor's terminator of the successor.
Definition: CFG.h:100
Function.h
llvm::SetVector::count
size_type count(const key_type &key) const
Count the number of elements of a given key in the SetVector.
Definition: SetVector.h:215
llvm::SafepointIRVerifierPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: SafepointIRVerifier.cpp:203
llvm::ReversePostOrderTraversal
Definition: PostOrderIterator.h:290
containsGCPtrType
static bool containsGCPtrType(Type *Ty)
Definition: SafepointIRVerifier.cpp:264
llvm::DominatorTreeAnalysis
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:252
NonConstant
@ NonConstant
Definition: SafepointIRVerifier.cpp:317
Instructions.h
PostOrderIterator.h
Dominators.h
llvm::Instruction::getParent
const BasicBlock * getParent() const
Definition: Instruction.h:94
llvm::PHINode::getIncomingBlock
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
Definition: Instructions.h:2749
llvm::PHINode
Definition: Instructions.h:2633
llvm::detail::DenseSetImpl::erase
bool erase(const ValueT &V)
Definition: DenseSet.h:101
PrintValueSet
static void PrintValueSet(raw_ostream &OS, IteratorTy Begin, IteratorTy End)
Definition: SafepointIRVerifier.cpp:278
llvm::set_intersect
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::Pass::getAnalysisUsage
virtual void getAnalysisUsage(AnalysisUsage &) const
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition: Pass.cpp:93
llvm::SmallSetVector
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:307
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:44
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:298
llvm::AnalysisUsage::addRequiredID
AnalysisUsage & addRequiredID(const void *ID)
Definition: Pass.cpp:267
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
GEP
Hexagon Common GEP
Definition: HexagonCommonGEP.cpp:172
BasicBlockState
State we compute and track per basic block.
Definition: SafepointIRVerifier.cpp:295
abort
*Add support for compiling functions in both ARM and Thumb then taking the smallest *Add support for compiling individual basic blocks in thumb when in a larger ARM function This can be used for presumed cold like paths to abort(failure path of asserts)
llvm::BranchInst
Conditional or Unconditional Branch instruction.
Definition: Instructions.h:3068
raw_ostream.h
llvm::SetVector
A vector that has set insertion semantics.
Definition: SetVector.h:40
Value.h
InitializePasses.h
llvm::SetVector::pop_back_val
LLVM_NODISCARD T pop_back_val()
Definition: SetVector.h:232
llvm::Value
LLVM Value Representation.
Definition: Value.h:75
Debug.h
llvm::BranchInst::isConditional
bool isConditional() const
Definition: Instructions.h:3147
llvm::BranchInst::getSuccessor
BasicBlock * getSuccessor(unsigned i) const
Definition: Instructions.h:3161
SetVector.h
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:44
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:37