LLVM  15.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 basic correctness check on the IR to ensure that Safepoints - if
10 // they've been inserted - were inserted correctly. In particular, look for use
11 // of non-relocated values after a safepoint. It's primary use is to check the
12 // correctness of safepoint insertion immediately after insertion, but it can
13 // also be used to verify that later transforms have not found a way to break
14 // safepoint semenatics.
15 //
16 // In its current form, this verify checks a property which is sufficient, but
17 // not neccessary for correctness. There are some cases where an unrelocated
18 // pointer can be used after the safepoint. Consider this example:
19 //
20 // a = ...
21 // b = ...
22 // (a',b') = safepoint(a,b)
23 // c = cmp eq a b
24 // br c, ..., ....
25 //
26 // Because it is valid to reorder 'c' above the safepoint, this is legal. In
27 // practice, this is a somewhat uncommon transform, but CodeGenPrep does create
28 // idioms like this. The verifier knows about these cases and avoids reporting
29 // false positives.
30 //
31 //===----------------------------------------------------------------------===//
32 
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/InstrTypes.h"
42 #include "llvm/IR/Instructions.h"
43 #include "llvm/IR/Statepoint.h"
44 #include "llvm/IR/Value.h"
45 #include "llvm/InitializePasses.h"
46 #include "llvm/Support/Allocator.h"
48 #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(cast<Instruction>(U->getUser())->isTerminator() &&
106  "edge must be operand of terminator");
107  assert(cast_or_null<BasicBlock>(U->get()) &&
108  "edge must refer to basic block");
109  assert(!isDeadBlock(cast<Instruction>(U->getUser())->getParent()) &&
110  "isDeadEdge() must be applied to edge from live block");
111  return DeadEdges.count(U);
112  }
113 
114  bool hasLiveIncomingEdges(const BasicBlock *BB) const {
115  // Check if all incoming edges are dead.
116  for (const_pred_iterator PredIt(BB), End(BB, true); PredIt != End; ++PredIt) {
117  auto &PU = PredIt.getUse();
118  const Use &U = PU.getUser()->getOperandUse(PU.getOperandNo());
119  if (!isDeadBlock(*PredIt) && !isDeadEdge(&U))
120  return true; // Found a live edge.
121  }
122  return false;
123  }
124 
125  void processFunction(const Function &F, const DominatorTree &DT) {
126  this->DT = &DT;
127 
128  // Start with all blocks unreachable from entry.
129  for (const BasicBlock &BB : F)
130  if (!DT.isReachableFromEntry(&BB))
131  DeadBlocks.insert(&BB);
132 
133  // Top-down walk of the dominator tree
135  for (const BasicBlock *BB : RPOT) {
136  const Instruction *TI = BB->getTerminator();
137  assert(TI && "blocks must be well formed");
138 
139  // For conditional branches, we can perform simple conditional propagation on
140  // the condition value itself.
141  const BranchInst *BI = dyn_cast<BranchInst>(TI);
142  if (!BI || !BI->isConditional() || !isa<Constant>(BI->getCondition()))
143  continue;
144 
145  // If a branch has two identical successors, we cannot declare either dead.
146  if (BI->getSuccessor(0) == BI->getSuccessor(1))
147  continue;
148 
149  ConstantInt *Cond = dyn_cast<ConstantInt>(BI->getCondition());
150  if (!Cond)
151  continue;
152 
153  addDeadEdge(BI->getOperandUse(Cond->getZExtValue() ? 1 : 2));
154  }
155  }
156 
157 protected:
158  void addDeadBlock(const BasicBlock *BB) {
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 } // namespace llvm
210 
211 namespace {
212 
213 struct SafepointIRVerifier : public FunctionPass {
214  static char ID; // Pass identification, replacement for typeid
215  SafepointIRVerifier() : FunctionPass(ID) {
216  initializeSafepointIRVerifierPass(*PassRegistry::getPassRegistry());
217  }
218 
219  bool runOnFunction(Function &F) override {
220  auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
221  CFGDeadness CD;
222  CD.processFunction(F, DT);
223  Verify(F, DT, CD);
224  return false; // no modifications
225  }
226 
227  void getAnalysisUsage(AnalysisUsage &AU) const override {
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  append_range(Worklist, PN->incoming_values());
352  continue;
353  }
354  if (const auto *SI = dyn_cast<SelectInst>(V)) {
355  // Push in the true and false values
356  Worklist.push_back(SI->getTrueValue());
357  Worklist.push_back(SI->getFalseValue());
358  continue;
359  }
360  if (const auto *GCRelocate = dyn_cast<GCRelocateInst>(V)) {
361  // GCRelocates do not change null-ness or constant-ness of the value.
362  // So we can continue with derived pointer this instruction relocates.
363  Worklist.push_back(GCRelocate->getDerivedPtr());
364  continue;
365  }
366  if (const auto *FI = dyn_cast<FreezeInst>(V)) {
367  // Freeze does not change null-ness or constant-ness of the value.
368  Worklist.push_back(FI->getOperand(0));
369  continue;
370  }
371  if (isa<Constant>(V)) {
372  // We found at least one base pointer which is non-null, so this derived
373  // pointer is not exclusively derived from null.
374  if (V != Constant::getNullValue(V->getType()))
375  isExclusivelyDerivedFromNull = false;
376  // Continue processing the remaining values to make sure it's exclusively
377  // constant.
378  continue;
379  }
380  // At this point, we know that the base pointer is not exclusively
381  // constant.
382  return BaseType::NonConstant;
383  }
384  // Now, we know that the base pointer is exclusively constant, but we need to
385  // differentiate between exclusive null constant and non-null constant.
386  return isExclusivelyDerivedFromNull ? BaseType::ExclusivelyNull
388 }
389 
390 static bool isNotExclusivelyConstantDerived(const Value *V) {
391  return getBaseType(V) == BaseType::NonConstant;
392 }
393 
394 namespace {
395 class InstructionVerifier;
396 
397 /// Builds BasicBlockState for each BB of the function.
398 /// It can traverse function for verification and provides all required
399 /// information.
400 ///
401 /// GC pointer may be in one of three states: relocated, unrelocated and
402 /// poisoned.
403 /// Relocated pointer may be used without any restrictions.
404 /// Unrelocated pointer cannot be dereferenced, passed as argument to any call
405 /// or returned. Unrelocated pointer may be safely compared against another
406 /// unrelocated pointer or against a pointer exclusively derived from null.
407 /// Poisoned pointers are produced when we somehow derive pointer from relocated
408 /// and unrelocated pointers (e.g. phi, select). This pointers may be safely
409 /// used in a very limited number of situations. Currently the only way to use
410 /// it is comparison against constant exclusively derived from null. All
411 /// limitations arise due to their undefined state: this pointers should be
412 /// treated as relocated and unrelocated simultaneously.
413 /// Rules of deriving:
414 /// R + U = P - that's where the poisoned pointers come from
415 /// P + X = P
416 /// U + U = U
417 /// R + R = R
418 /// X + C = X
419 /// Where "+" - any operation that somehow derive pointer, U - unrelocated,
420 /// R - relocated and P - poisoned, C - constant, X - U or R or P or C or
421 /// nothing (in case when "+" is unary operation).
422 /// Deriving of pointers by itself is always safe.
423 /// NOTE: when we are making decision on the status of instruction's result:
424 /// a) for phi we need to check status of each input *at the end of
425 /// corresponding predecessor BB*.
426 /// b) for other instructions we need to check status of each input *at the
427 /// current point*.
428 ///
429 /// FIXME: This works fairly well except one case
430 /// bb1:
431 /// p = *some GC-ptr def*
432 /// p1 = gep p, offset
433 /// / |
434 /// / |
435 /// bb2: |
436 /// safepoint |
437 /// \ |
438 /// \ |
439 /// bb3:
440 /// p2 = phi [p, bb2] [p1, bb1]
441 /// p3 = phi [p, bb2] [p, bb1]
442 /// here p and p1 is unrelocated
443 /// p2 and p3 is poisoned (though they shouldn't be)
444 ///
445 /// This leads to some weird results:
446 /// cmp eq p, p2 - illegal instruction (false-positive)
447 /// cmp eq p1, p2 - illegal instruction (false-positive)
448 /// cmp eq p, p3 - illegal instruction (false-positive)
449 /// cmp eq p, p1 - ok
450 /// To fix this we need to introduce conception of generations and be able to
451 /// check if two values belong to one generation or not. This way p2 will be
452 /// considered to be unrelocated and no false alarm will happen.
453 class GCPtrTracker {
454  const Function &F;
455  const CFGDeadness &CD;
458  // This set contains defs of unrelocated pointers that are proved to be legal
459  // and don't need verification.
460  DenseSet<const Instruction *> ValidUnrelocatedDefs;
461  // This set contains poisoned defs. They can be safely ignored during
462  // verification too.
463  DenseSet<const Value *> PoisonedDefs;
464 
465 public:
466  GCPtrTracker(const Function &F, const DominatorTree &DT,
467  const CFGDeadness &CD);
468 
469  bool hasLiveIncomingEdge(const PHINode *PN, const BasicBlock *InBB) const {
470  return CD.hasLiveIncomingEdge(PN, InBB);
471  }
472 
473  BasicBlockState *getBasicBlockState(const BasicBlock *BB);
474  const BasicBlockState *getBasicBlockState(const BasicBlock *BB) const;
475 
476  bool isValuePoisoned(const Value *V) const { return PoisonedDefs.count(V); }
477 
478  /// Traverse each BB of the function and call
479  /// InstructionVerifier::verifyInstruction for each possibly invalid
480  /// instruction.
481  /// It destructively modifies GCPtrTracker so it's passed via rvalue reference
482  /// in order to prohibit further usages of GCPtrTracker as it'll be in
483  /// inconsistent state.
484  static void verifyFunction(GCPtrTracker &&Tracker,
485  InstructionVerifier &Verifier);
486 
487  /// Returns true for reachable and live blocks.
488  bool isMapped(const BasicBlock *BB) const {
489  return BlockMap.find(BB) != BlockMap.end();
490  }
491 
492 private:
493  /// Returns true if the instruction may be safely skipped during verification.
494  bool instructionMayBeSkipped(const Instruction *I) const;
495 
496  /// Iterates over all BBs from BlockMap and recalculates AvailableIn/Out for
497  /// each of them until it converges.
498  void recalculateBBsStates();
499 
500  /// Remove from Contribution all defs that legally produce unrelocated
501  /// pointers and saves them to ValidUnrelocatedDefs.
502  /// Though Contribution should belong to BBS it is passed separately with
503  /// different const-modifier in order to emphasize (and guarantee) that only
504  /// Contribution will be changed.
505  /// Returns true if Contribution was changed otherwise false.
506  bool removeValidUnrelocatedDefs(const BasicBlock *BB,
507  const BasicBlockState *BBS,
508  AvailableValueSet &Contribution);
509 
510  /// Gather all the definitions dominating the start of BB into Result. This is
511  /// simply the defs introduced by every dominating basic block and the
512  /// function arguments.
513  void gatherDominatingDefs(const BasicBlock *BB, AvailableValueSet &Result,
514  const DominatorTree &DT);
515 
516  /// Compute the AvailableOut set for BB, based on the BasicBlockState BBS,
517  /// which is the BasicBlockState for BB.
518  /// ContributionChanged is set when the verifier runs for the first time
519  /// (in this case Contribution was changed from 'empty' to its initial state)
520  /// or when Contribution of this BB was changed since last computation.
521  static void transferBlock(const BasicBlock *BB, BasicBlockState &BBS,
522  bool ContributionChanged);
523 
524  /// Model the effect of an instruction on the set of available values.
525  static void transferInstruction(const Instruction &I, bool &Cleared,
527 };
528 
529 /// It is a visitor for GCPtrTracker::verifyFunction. It decides if the
530 /// instruction (which uses heap reference) is legal or not, given our safepoint
531 /// semantics.
532 class InstructionVerifier {
533  bool AnyInvalidUses = false;
534 
535 public:
536  void verifyInstruction(const GCPtrTracker *Tracker, const Instruction &I,
537  const AvailableValueSet &AvailableSet);
538 
539  bool hasAnyInvalidUses() const { return AnyInvalidUses; }
540 
541 private:
542  void reportInvalidUse(const Value &V, const Instruction &I);
543 };
544 } // end anonymous namespace
545 
546 GCPtrTracker::GCPtrTracker(const Function &F, const DominatorTree &DT,
547  const CFGDeadness &CD) : F(F), CD(CD) {
548  // Calculate Contribution of each live BB.
549  // Allocate BB states for live blocks.
550  for (const BasicBlock &BB : F)
551  if (!CD.isDeadBlock(&BB)) {
552  BasicBlockState *BBS = new (BSAllocator.Allocate()) BasicBlockState;
553  for (const auto &I : BB)
554  transferInstruction(I, BBS->Cleared, BBS->Contribution);
555  BlockMap[&BB] = BBS;
556  }
557 
558  // Initialize AvailableIn/Out sets of each BB using only information about
559  // dominating BBs.
560  for (auto &BBI : BlockMap) {
561  gatherDominatingDefs(BBI.first, BBI.second->AvailableIn, DT);
562  transferBlock(BBI.first, *BBI.second, true);
563  }
564 
565  // Simulate the flow of defs through the CFG and recalculate AvailableIn/Out
566  // sets of each BB until it converges. If any def is proved to be an
567  // unrelocated pointer, it will be removed from all BBSs.
568  recalculateBBsStates();
569 }
570 
571 BasicBlockState *GCPtrTracker::getBasicBlockState(const BasicBlock *BB) {
572  return BlockMap.lookup(BB);
573 }
574 
575 const BasicBlockState *GCPtrTracker::getBasicBlockState(
576  const BasicBlock *BB) const {
577  return const_cast<GCPtrTracker *>(this)->getBasicBlockState(BB);
578 }
579 
580 bool GCPtrTracker::instructionMayBeSkipped(const Instruction *I) const {
581  // Poisoned defs are skipped since they are always safe by itself by
582  // definition (for details see comment to this class).
583  return ValidUnrelocatedDefs.count(I) || PoisonedDefs.count(I);
584 }
585 
586 void GCPtrTracker::verifyFunction(GCPtrTracker &&Tracker,
587  InstructionVerifier &Verifier) {
588  // We need RPO here to a) report always the first error b) report errors in
589  // same order from run to run.
591  for (const BasicBlock *BB : RPOT) {
592  BasicBlockState *BBS = Tracker.getBasicBlockState(BB);
593  if (!BBS)
594  continue;
595 
596  // We destructively modify AvailableIn as we traverse the block instruction
597  // by instruction.
598  AvailableValueSet &AvailableSet = BBS->AvailableIn;
599  for (const Instruction &I : *BB) {
600  if (Tracker.instructionMayBeSkipped(&I))
601  continue; // This instruction shouldn't be added to AvailableSet.
602 
603  Verifier.verifyInstruction(&Tracker, I, AvailableSet);
604 
605  // Model the effect of current instruction on AvailableSet to keep the set
606  // relevant at each point of BB.
607  bool Cleared = false;
608  transferInstruction(I, Cleared, AvailableSet);
609  (void)Cleared;
610  }
611  }
612 }
613 
614 void GCPtrTracker::recalculateBBsStates() {
616  // TODO: This order is suboptimal, it's better to replace it with priority
617  // queue where priority is RPO number of BB.
618  for (auto &BBI : BlockMap)
619  Worklist.insert(BBI.first);
620 
621  // This loop iterates the AvailableIn/Out sets until it converges.
622  // The AvailableIn and AvailableOut sets decrease as we iterate.
623  while (!Worklist.empty()) {
624  const BasicBlock *BB = Worklist.pop_back_val();
625  BasicBlockState *BBS = getBasicBlockState(BB);
626  if (!BBS)
627  continue; // Ignore dead successors.
628 
629  size_t OldInCount = BBS->AvailableIn.size();
630  for (const_pred_iterator PredIt(BB), End(BB, true); PredIt != End; ++PredIt) {
631  const BasicBlock *PBB = *PredIt;
632  BasicBlockState *PBBS = getBasicBlockState(PBB);
633  if (PBBS && !CD.isDeadEdge(&CFGDeadness::getEdge(PredIt)))
635  }
636 
637  assert(OldInCount >= BBS->AvailableIn.size() && "invariant!");
638 
639  bool InputsChanged = OldInCount != BBS->AvailableIn.size();
640  bool ContributionChanged =
641  removeValidUnrelocatedDefs(BB, BBS, BBS->Contribution);
642  if (!InputsChanged && !ContributionChanged)
643  continue;
644 
645  size_t OldOutCount = BBS->AvailableOut.size();
646  transferBlock(BB, *BBS, ContributionChanged);
647  if (OldOutCount != BBS->AvailableOut.size()) {
648  assert(OldOutCount > BBS->AvailableOut.size() && "invariant!");
649  Worklist.insert(succ_begin(BB), succ_end(BB));
650  }
651  }
652 }
653 
654 bool GCPtrTracker::removeValidUnrelocatedDefs(const BasicBlock *BB,
655  const BasicBlockState *BBS,
656  AvailableValueSet &Contribution) {
657  assert(&BBS->Contribution == &Contribution &&
658  "Passed Contribution should be from the passed BasicBlockState!");
659  AvailableValueSet AvailableSet = BBS->AvailableIn;
660  bool ContributionChanged = false;
661  // For explanation why instructions are processed this way see
662  // "Rules of deriving" in the comment to this class.
663  for (const Instruction &I : *BB) {
664  bool ValidUnrelocatedPointerDef = false;
665  bool PoisonedPointerDef = false;
666  // TODO: `select` instructions should be handled here too.
667  if (const PHINode *PN = dyn_cast<PHINode>(&I)) {
668  if (containsGCPtrType(PN->getType())) {
669  // If both is true, output is poisoned.
670  bool HasRelocatedInputs = false;
671  bool HasUnrelocatedInputs = false;
672  for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
673  const BasicBlock *InBB = PN->getIncomingBlock(i);
674  if (!isMapped(InBB) ||
675  !CD.hasLiveIncomingEdge(PN, InBB))
676  continue; // Skip dead block or dead edge.
677 
678  const Value *InValue = PN->getIncomingValue(i);
679 
680  if (isNotExclusivelyConstantDerived(InValue)) {
681  if (isValuePoisoned(InValue)) {
682  // If any of inputs is poisoned, output is always poisoned too.
683  HasRelocatedInputs = true;
684  HasUnrelocatedInputs = true;
685  break;
686  }
687  if (BlockMap[InBB]->AvailableOut.count(InValue))
688  HasRelocatedInputs = true;
689  else
690  HasUnrelocatedInputs = true;
691  }
692  }
693  if (HasUnrelocatedInputs) {
694  if (HasRelocatedInputs)
695  PoisonedPointerDef = true;
696  else
697  ValidUnrelocatedPointerDef = true;
698  }
699  }
700  } else if ((isa<GetElementPtrInst>(I) || isa<BitCastInst>(I)) &&
701  containsGCPtrType(I.getType())) {
702  // GEP/bitcast of unrelocated pointer is legal by itself but this def
703  // shouldn't appear in any AvailableSet.
704  for (const Value *V : I.operands())
705  if (containsGCPtrType(V->getType()) &&
706  isNotExclusivelyConstantDerived(V) && !AvailableSet.count(V)) {
707  if (isValuePoisoned(V))
708  PoisonedPointerDef = true;
709  else
710  ValidUnrelocatedPointerDef = true;
711  break;
712  }
713  }
714  assert(!(ValidUnrelocatedPointerDef && PoisonedPointerDef) &&
715  "Value cannot be both unrelocated and poisoned!");
716  if (ValidUnrelocatedPointerDef) {
717  // Remove def of unrelocated pointer from Contribution of this BB and
718  // trigger update of all its successors.
719  Contribution.erase(&I);
720  PoisonedDefs.erase(&I);
721  ValidUnrelocatedDefs.insert(&I);
722  LLVM_DEBUG(dbgs() << "Removing urelocated " << I
723  << " from Contribution of " << BB->getName() << "\n");
724  ContributionChanged = true;
725  } else if (PoisonedPointerDef) {
726  // Mark pointer as poisoned, remove its def from Contribution and trigger
727  // update of all successors.
728  Contribution.erase(&I);
729  PoisonedDefs.insert(&I);
730  LLVM_DEBUG(dbgs() << "Removing poisoned " << I << " from Contribution of "
731  << BB->getName() << "\n");
732  ContributionChanged = true;
733  } else {
734  bool Cleared = false;
735  transferInstruction(I, Cleared, AvailableSet);
736  (void)Cleared;
737  }
738  }
739  return ContributionChanged;
740 }
741 
742 void GCPtrTracker::gatherDominatingDefs(const BasicBlock *BB,
743  AvailableValueSet &Result,
744  const DominatorTree &DT) {
745  DomTreeNode *DTN = DT[const_cast<BasicBlock *>(BB)];
746 
747  assert(DTN && "Unreachable blocks are ignored");
748  while (DTN->getIDom()) {
749  DTN = DTN->getIDom();
750  auto BBS = getBasicBlockState(DTN->getBlock());
751  assert(BBS && "immediate dominator cannot be dead for a live block");
752  const auto &Defs = BBS->Contribution;
753  Result.insert(Defs.begin(), Defs.end());
754  // If this block is 'Cleared', then nothing LiveIn to this block can be
755  // available after this block completes. Note: This turns out to be
756  // really important for reducing memory consuption of the initial available
757  // sets and thus peak memory usage by this verifier.
758  if (BBS->Cleared)
759  return;
760  }
761 
762  for (const Argument &A : BB->getParent()->args())
763  if (containsGCPtrType(A.getType()))
764  Result.insert(&A);
765 }
766 
767 void GCPtrTracker::transferBlock(const BasicBlock *BB, BasicBlockState &BBS,
768  bool ContributionChanged) {
769  const AvailableValueSet &AvailableIn = BBS.AvailableIn;
770  AvailableValueSet &AvailableOut = BBS.AvailableOut;
771 
772  if (BBS.Cleared) {
773  // AvailableOut will change only when Contribution changed.
774  if (ContributionChanged)
775  AvailableOut = BBS.Contribution;
776  } else {
777  // Otherwise, we need to reduce the AvailableOut set by things which are no
778  // longer in our AvailableIn
779  AvailableValueSet Temp = BBS.Contribution;
780  set_union(Temp, AvailableIn);
781  AvailableOut = std::move(Temp);
782  }
783 
784  LLVM_DEBUG(dbgs() << "Transfered block " << BB->getName() << " from ";
785  PrintValueSet(dbgs(), AvailableIn.begin(), AvailableIn.end());
786  dbgs() << " to ";
787  PrintValueSet(dbgs(), AvailableOut.begin(), AvailableOut.end());
788  dbgs() << "\n";);
789 }
790 
791 void GCPtrTracker::transferInstruction(const Instruction &I, bool &Cleared,
792  AvailableValueSet &Available) {
793  if (isa<GCStatepointInst>(I)) {
794  Cleared = true;
795  Available.clear();
796  } else if (containsGCPtrType(I.getType()))
797  Available.insert(&I);
798 }
799 
800 void InstructionVerifier::verifyInstruction(
801  const GCPtrTracker *Tracker, const Instruction &I,
802  const AvailableValueSet &AvailableSet) {
803  if (const PHINode *PN = dyn_cast<PHINode>(&I)) {
804  if (containsGCPtrType(PN->getType()))
805  for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
806  const BasicBlock *InBB = PN->getIncomingBlock(i);
807  const BasicBlockState *InBBS = Tracker->getBasicBlockState(InBB);
808  if (!InBBS ||
809  !Tracker->hasLiveIncomingEdge(PN, InBB))
810  continue; // Skip dead block or dead edge.
811 
812  const Value *InValue = PN->getIncomingValue(i);
813 
814  if (isNotExclusivelyConstantDerived(InValue) &&
815  !InBBS->AvailableOut.count(InValue))
816  reportInvalidUse(*InValue, *PN);
817  }
818  } else if (isa<CmpInst>(I) &&
819  containsGCPtrType(I.getOperand(0)->getType())) {
820  Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
821  enum BaseType baseTyLHS = getBaseType(LHS),
822  baseTyRHS = getBaseType(RHS);
823 
824  // Returns true if LHS and RHS are unrelocated pointers and they are
825  // valid unrelocated uses.
826  auto hasValidUnrelocatedUse = [&AvailableSet, Tracker, baseTyLHS, baseTyRHS,
827  &LHS, &RHS] () {
828  // A cmp instruction has valid unrelocated pointer operands only if
829  // both operands are unrelocated pointers.
830  // In the comparison between two pointers, if one is an unrelocated
831  // use, the other *should be* an unrelocated use, for this
832  // instruction to contain valid unrelocated uses. This unrelocated
833  // use can be a null constant as well, or another unrelocated
834  // pointer.
835  if (AvailableSet.count(LHS) || AvailableSet.count(RHS))
836  return false;
837  // Constant pointers (that are not exclusively null) may have
838  // meaning in different VMs, so we cannot reorder the compare
839  // against constant pointers before the safepoint. In other words,
840  // comparison of an unrelocated use against a non-null constant
841  // maybe invalid.
842  if ((baseTyLHS == BaseType::ExclusivelySomeConstant &&
843  baseTyRHS == BaseType::NonConstant) ||
844  (baseTyLHS == BaseType::NonConstant &&
845  baseTyRHS == BaseType::ExclusivelySomeConstant))
846  return false;
847 
848  // If one of pointers is poisoned and other is not exclusively derived
849  // from null it is an invalid expression: it produces poisoned result
850  // and unless we want to track all defs (not only gc pointers) the only
851  // option is to prohibit such instructions.
852  if ((Tracker->isValuePoisoned(LHS) && baseTyRHS != ExclusivelyNull) ||
853  (Tracker->isValuePoisoned(RHS) && baseTyLHS != ExclusivelyNull))
854  return false;
855 
856  // All other cases are valid cases enumerated below:
857  // 1. Comparison between an exclusively derived null pointer and a
858  // constant base pointer.
859  // 2. Comparison between an exclusively derived null pointer and a
860  // non-constant unrelocated base pointer.
861  // 3. Comparison between 2 unrelocated pointers.
862  // 4. Comparison between a pointer exclusively derived from null and a
863  // non-constant poisoned pointer.
864  return true;
865  };
866  if (!hasValidUnrelocatedUse()) {
867  // Print out all non-constant derived pointers that are unrelocated
868  // uses, which are invalid.
869  if (baseTyLHS == BaseType::NonConstant && !AvailableSet.count(LHS))
870  reportInvalidUse(*LHS, I);
871  if (baseTyRHS == BaseType::NonConstant && !AvailableSet.count(RHS))
872  reportInvalidUse(*RHS, I);
873  }
874  } else {
875  for (const Value *V : I.operands())
876  if (containsGCPtrType(V->getType()) &&
877  isNotExclusivelyConstantDerived(V) && !AvailableSet.count(V))
878  reportInvalidUse(*V, I);
879  }
880 }
881 
882 void InstructionVerifier::reportInvalidUse(const Value &V,
883  const Instruction &I) {
884  errs() << "Illegal use of unrelocated value found!\n";
885  errs() << "Def: " << V << "\n";
886  errs() << "Use: " << I << "\n";
887  if (!PrintOnly)
888  abort();
889  AnyInvalidUses = true;
890 }
891 
892 static void Verify(const Function &F, const DominatorTree &DT,
893  const CFGDeadness &CD) {
894  LLVM_DEBUG(dbgs() << "Verifying gc pointers in function: " << F.getName()
895  << "\n");
896  if (PrintOnly)
897  dbgs() << "Verifying gc pointers in function: " << F.getName() << "\n";
898 
899  GCPtrTracker Tracker(F, DT, CD);
900 
901  // We now have all the information we need to decide if the use of a heap
902  // reference is legal or not, given our safepoint semantics.
903 
904  InstructionVerifier Verifier;
906 
907  if (PrintOnly && !Verifier.hasAnyInvalidUses()) {
908  dbgs() << "No illegal uses found by SafepointIRVerifier in: " << F.getName()
909  << "\n";
910  }
911 }
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:152
llvm::verifySafepointIR
void verifySafepointIR(Function &F)
Run the safepoint verifier over a single function. Crashes on failure.
Definition: SafepointIRVerifier.cpp:236
llvm::Argument
This class represents an incoming formal argument to a Function.
Definition: Argument.h:28
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
llvm::PHINode::incoming_values
op_range incoming_values()
Definition: Instructions.h:2737
BasicBlockState::Cleared
bool Cleared
Definition: SafepointIRVerifier.cpp:306
PrintOnly
static cl::opt< bool > PrintOnly("safepoint-ir-verifier-print-only", cl::init(false))
This option is used for writing test cases.
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:780
SetOperations.h
llvm::succ_end
Interval::succ_iterator succ_end(Interval *I)
Definition: Interval.h:102
T
llvm::Function
Definition: Function.h:60
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:199
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:23
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1185
llvm::Use::get
Value * get() const
Definition: Use.h:66
Allocator.h
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:166
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:6150
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:379
llvm::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
ir
verify safepoint ir
Definition: SafepointIRVerifier.cpp:250
llvm::successors
auto successors(MachineBasicBlock *BB)
Definition: MachineSSAContext.h:29
llvm::errs
raw_fd_ostream & errs()
This returns a reference to a raw_ostream for standard error.
Definition: raw_ostream.cpp:893
llvm::SmallVectorImpl::pop_back_val
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:654
RHS
Value * RHS
Definition: X86PartialReduction.cpp:76
llvm::ArrayType
Class to represent array types.
Definition: DerivedTypes.h:357
llvm::DomTreeNodeBase::getIDom
DomTreeNodeBase * getIDom() const
Definition: GenericDomTree.h:89
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:298
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:326
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
F
#define F(x, y, z)
Definition: MD5.cpp:55
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:55
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:253
LHS
Value * LHS
Definition: X86PartialReduction.cpp:75
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:2747
AvailabilityState::Available
@ Available
We know the block is fully available. This is a fixpoint.
InstrTypes.h
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
ExclusivelySomeConstant
@ ExclusivelySomeConstant
Definition: SafepointIRVerifier.cpp:317
llvm::ms_demangle::QualifierMangleMode::Result
@ Result
DenseSet.h
false
Definition: StackSlotColoring.cpp:141
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
pass
modulo schedule Modulo Schedule test pass
Definition: ModuloSchedule.cpp:2123
llvm::detail::DenseSetImpl::size
size_type size() const
Definition: DenseSet.h:81
llvm::Instruction
Definition: Instruction.h:42
llvm::DominatorTreeWrapperPass
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:302
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:54
llvm::Use::getUser
User * getUser() const
Returns the User that contains this Use.
Definition: Use.h:72
IR
Statically lint checks LLVM IR
Definition: Lint.cpp:751
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:2743
Statepoint.h
llvm::CallingConv::ID
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
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:316
llvm::BranchInst::getCondition
Value * getCondition() const
Definition: Instructions.h:3167
isNotExclusivelyConstantDerived
static bool isNotExclusivelyConstantDerived(const Value *V)
Definition: SafepointIRVerifier.cpp:390
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:251
Verify
static void Verify(const Function &F, const DominatorTree &DT, const CFGDeadness &CD)
Definition: SafepointIRVerifier.cpp:892
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:716
I
#define I(x, y, z)
Definition: MD5.cpp:58
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:432
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:152
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:335
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:1624
llvm::StructType
Class to represent struct types.
Definition: DerivedTypes.h:213
Cond
SmallVector< MachineOperand, 4 > Cond
Definition: BasicBlockSections.cpp:137
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:80
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
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:1823
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:243
llvm::PredIterator
Definition: CFG.h:42
llvm::DomTreeNodeBase< BasicBlock >
BasicBlockState::AvailableIn
AvailableValueSet AvailableIn
Definition: SafepointIRVerifier.cpp:295
llvm::SpecificBumpPtrAllocator::Allocate
T * Allocate(size_t num=1)
Allocate space for an array of objects without constructing them.
Definition: Allocator.h:429
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:84
llvm::initializeSafepointIRVerifierPass
void initializeSafepointIRVerifierPass(PassRegistry &)
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:158
BasicBlockState::Contribution
AvailableValueSet Contribution
Definition: SafepointIRVerifier.cpp:302
llvm::PredIterator::getUse
Use & getUse() const
getUse - Return the operand Use in the predecessor's terminator of the successor.
Definition: CFG.h:99
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
verify
ppc ctr loops verify
Definition: PPCCTRLoopsVerify.cpp:76
llvm::SafepointIRVerifierPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: SafepointIRVerifier.cpp:201
llvm::ReversePostOrderTraversal
Definition: PostOrderIterator.h:291
containsGCPtrType
static bool containsGCPtrType(Type *Ty)
Definition: SafepointIRVerifier.cpp:262
llvm::DominatorTreeAnalysis
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:267
NonConstant
@ NonConstant
Definition: SafepointIRVerifier.cpp:315
Instructions.h
PostOrderIterator.h
Dominators.h
llvm::Instruction::getParent
const BasicBlock * getParent() const
Definition: Instruction.h:91
llvm::PHINode::getIncomingBlock
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
Definition: Instructions.h:2767
llvm::PHINode
Definition: Instructions.h:2651
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:276
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:40
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:97
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:42
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:308
llvm::AnalysisUsage::addRequiredID
AnalysisUsage & addRequiredID(const void *ID)
Definition: Pass.cpp:277
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:171
BasicBlockState
State we compute and track per basic block.
Definition: SafepointIRVerifier.cpp:293
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:3086
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:74
Debug.h
llvm::BranchInst::isConditional
bool isConditional() const
Definition: Instructions.h:3165
llvm::BranchInst::getSuccessor
BasicBlock * getSuccessor(unsigned i) const
Definition: Instructions.h:3179
SetVector.h
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:38