1 //===-- SafepointIRVerifier.cpp - Verify gc.statepoint invariants ---------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // Run a sanity check on the IR to ensure that Safepoints - if they've been
11 // inserted - were inserted correctly. In particular, look for use of
12 // non-relocated values after a safepoint. It's primary use is to check the
13 // correctness of safepoint insertion immediately after insertion, but it can
14 // also be used to verify that later transforms have not found a way to break
15 // safepoint semenatics.
17 // In its current form, this verify checks a property which is sufficient, but
18 // not neccessary for correctness. There are some cases where an unrelocated
19 // pointer can be used after the safepoint. Consider this example:
23 // (a',b') = safepoint(a,b)
27 // Because it is valid to reorder 'c' above the safepoint, this is legal. In
28 // practice, this is a somewhat uncommon transform, but CodeGenPrep does create
29 // idioms like this. The verifier knows about these cases and avoids reporting
32 //===----------------------------------------------------------------------===//
34 #include "llvm/ADT/DenseSet.h"
35 #include "llvm/ADT/PostOrderIterator.h"
36 #include "llvm/ADT/SetOperations.h"
37 #include "llvm/ADT/SetVector.h"
38 #include "llvm/IR/BasicBlock.h"
39 #include "llvm/IR/Dominators.h"
40 #include "llvm/IR/Function.h"
41 #include "llvm/IR/Instructions.h"
42 #include "llvm/IR/Intrinsics.h"
43 #include "llvm/IR/IntrinsicInst.h"
44 #include "llvm/IR/Module.h"
45 #include "llvm/IR/Value.h"
46 #include "llvm/IR/SafepointIRVerifier.h"
47 #include "llvm/IR/Statepoint.h"
48 #include "llvm/Support/Debug.h"
49 #include "llvm/Support/CommandLine.h"
50 #include "llvm/Support/raw_ostream.h"
52 #define DEBUG_TYPE "safepoint-ir-verifier"
56 /// This option is used for writing test cases. Instead of crashing the program
57 /// when verification fails, report a message to the console (for FileCheck
58 /// usage) and continue execution as if nothing happened.
59 static cl::opt<bool> PrintOnly("safepoint-ir-verifier-print-only",
62 static void Verify(const Function &F, const DominatorTree &DT);
65 struct SafepointIRVerifier : public FunctionPass {
66 static char ID; // Pass identification, replacement for typeid
68 SafepointIRVerifier() : FunctionPass(ID) {
69 initializeSafepointIRVerifierPass(*PassRegistry::getPassRegistry());
72 bool runOnFunction(Function &F) override {
75 return false; // no modifications
78 void getAnalysisUsage(AnalysisUsage &AU) const override {
82 StringRef getPassName() const override { return "safepoint verifier"; }
86 void llvm::verifySafepointIR(Function &F) {
87 SafepointIRVerifier pass;
88 pass.runOnFunction(F);
91 char SafepointIRVerifier::ID = 0;
93 FunctionPass *llvm::createSafepointIRVerifierPass() {
94 return new SafepointIRVerifier();
97 INITIALIZE_PASS_BEGIN(SafepointIRVerifier, "verify-safepoint-ir",
98 "Safepoint IR Verifier", false, true)
99 INITIALIZE_PASS_END(SafepointIRVerifier, "verify-safepoint-ir",
100 "Safepoint IR Verifier", false, true)
102 static bool isGCPointerType(Type *T) {
103 if (auto *PT = dyn_cast<PointerType>(T))
104 // For the sake of this example GC, we arbitrarily pick addrspace(1) as our
105 // GC managed heap. We know that a pointer into this heap needs to be
106 // updated and that no other pointer does.
107 return (1 == PT->getAddressSpace());
111 static bool containsGCPtrType(Type *Ty) {
112 if (isGCPointerType(Ty))
114 if (VectorType *VT = dyn_cast<VectorType>(Ty))
115 return isGCPointerType(VT->getScalarType());
116 if (ArrayType *AT = dyn_cast<ArrayType>(Ty))
117 return containsGCPtrType(AT->getElementType());
118 if (StructType *ST = dyn_cast<StructType>(Ty))
119 return std::any_of(ST->subtypes().begin(), ST->subtypes().end(),
124 // Debugging aid -- prints a [Begin, End) range of values.
125 template<typename IteratorTy>
126 static void PrintValueSet(raw_ostream &OS, IteratorTy Begin, IteratorTy End) {
128 while (Begin != End) {
129 OS << **Begin << " ";
135 /// The verifier algorithm is phrased in terms of availability. The set of
136 /// values "available" at a given point in the control flow graph is the set of
137 /// correctly relocated value at that point, and is a subset of the set of
138 /// definitions dominating that point.
140 using AvailableValueSet = DenseSet<const Value *>;
142 /// State we compute and track per basic block.
143 struct BasicBlockState {
144 // Set of values available coming in, before the phi nodes
145 AvailableValueSet AvailableIn;
147 // Set of values available going out
148 AvailableValueSet AvailableOut;
150 // AvailableOut minus AvailableIn.
151 // All elements are Instructions
152 AvailableValueSet Contribution;
154 // True if this block contains a safepoint and thus AvailableIn does not
155 // contribute to AvailableOut.
156 bool Cleared = false;
159 /// A given derived pointer can have multiple base pointers through phi/selects.
160 /// This type indicates when the base pointer is exclusively constant
161 /// (ExclusivelySomeConstant), and if that constant is proven to be exclusively
162 /// null, we record that as ExclusivelyNull. In all other cases, the BaseType is
165 NonConstant = 1, // Base pointers is not exclusively constant.
167 ExclusivelySomeConstant // Base pointers for a given derived pointer is from a
168 // set of constants, but they are not exclusively
172 /// Return the baseType for Val which states whether Val is exclusively
173 /// derived from constant/null, or not exclusively derived from constant.
174 /// Val is exclusively derived off a constant base when all operands of phi and
175 /// selects are derived off a constant base.
176 static enum BaseType getBaseType(const Value *Val) {
178 SmallVector<const Value *, 32> Worklist;
179 DenseSet<const Value *> Visited;
180 bool isExclusivelyDerivedFromNull = true;
181 Worklist.push_back(Val);
182 // Strip through all the bitcasts and geps to get base pointer. Also check for
183 // the exclusive value when there can be multiple base pointers (through phis
185 while(!Worklist.empty()) {
186 const Value *V = Worklist.pop_back_val();
187 if (!Visited.insert(V).second)
190 if (const auto *CI = dyn_cast<CastInst>(V)) {
191 Worklist.push_back(CI->stripPointerCasts());
194 if (const auto *GEP = dyn_cast<GetElementPtrInst>(V)) {
195 Worklist.push_back(GEP->getPointerOperand());
198 // Push all the incoming values of phi node into the worklist for
200 if (const auto *PN = dyn_cast<PHINode>(V)) {
201 for (Value *InV: PN->incoming_values())
202 Worklist.push_back(InV);
205 if (const auto *SI = dyn_cast<SelectInst>(V)) {
206 // Push in the true and false values
207 Worklist.push_back(SI->getTrueValue());
208 Worklist.push_back(SI->getFalseValue());
211 if (isa<Constant>(V)) {
212 // We found at least one base pointer which is non-null, so this derived
213 // pointer is not exclusively derived from null.
214 if (V != Constant::getNullValue(V->getType()))
215 isExclusivelyDerivedFromNull = false;
216 // Continue processing the remaining values to make sure it's exclusively
220 // At this point, we know that the base pointer is not exclusively
222 return BaseType::NonConstant;
224 // Now, we know that the base pointer is exclusively constant, but we need to
225 // differentiate between exclusive null constant and non-null constant.
226 return isExclusivelyDerivedFromNull ? BaseType::ExclusivelyNull
227 : BaseType::ExclusivelySomeConstant;
230 static bool isNotExclusivelyConstantDerived(const Value *V) {
231 return getBaseType(V) == BaseType::NonConstant;
235 class InstructionVerifier;
237 /// Builds BasicBlockState for each BB of the function.
238 /// It can traverse function for verification and provides all required
242 SpecificBumpPtrAllocator<BasicBlockState> BSAllocator;
243 DenseMap<const BasicBlock *, BasicBlockState *> BlockMap;
244 // This set contains defs of unrelocated pointers that are proved to be legal
245 // and don't need verification.
246 DenseSet<const Instruction *> ValidUnrelocatedDefs;
249 GCPtrTracker(const Function &F, const DominatorTree &DT);
251 BasicBlockState *getBasicBlockState(const BasicBlock *BB);
252 const BasicBlockState *getBasicBlockState(const BasicBlock *BB) const;
254 /// Traverse each BB of the function and call
255 /// InstructionVerifier::verifyInstruction for each possibly invalid
257 /// It destructively modifies GCPtrTracker so it's passed via rvalue reference
258 /// in order to prohibit further usages of GCPtrTracker as it'll be in
259 /// inconsistent state.
260 static void verifyFunction(GCPtrTracker &&Tracker,
261 InstructionVerifier &Verifier);
264 /// Returns true if the instruction may be safely skipped during verification.
265 bool instructionMayBeSkipped(const Instruction *I) const;
267 /// Iterates over all BBs from BlockMap and recalculates AvailableIn/Out for
268 /// each of them until it converges.
269 void recalculateBBsStates();
271 /// Remove from Contribution all defs that legally produce unrelocated
272 /// pointers and saves them to ValidUnrelocatedDefs.
273 /// Though Contribution should belong to BBS it is passed separately with
274 /// different const-modifier in order to emphasize (and guarantee) that only
275 /// Contribution will be changed.
276 /// Returns true if Contribution was changed otherwise false.
277 bool removeValidUnrelocatedDefs(const BasicBlock *BB,
278 const BasicBlockState *BBS,
279 AvailableValueSet &Contribution);
281 /// Gather all the definitions dominating the start of BB into Result. This is
282 /// simply the defs introduced by every dominating basic block and the
283 /// function arguments.
284 void gatherDominatingDefs(const BasicBlock *BB, AvailableValueSet &Result,
285 const DominatorTree &DT);
287 /// Compute the AvailableOut set for BB, based on the BasicBlockState BBS,
288 /// which is the BasicBlockState for BB.
289 /// ContributionChanged is set when the verifier runs for the first time
290 /// (in this case Contribution was changed from 'empty' to its initial state)
291 /// or when Contribution of this BB was changed since last computation.
292 static void transferBlock(const BasicBlock *BB, BasicBlockState &BBS,
293 bool ContributionChanged);
295 /// Model the effect of an instruction on the set of available values.
296 static void transferInstruction(const Instruction &I, bool &Cleared,
297 AvailableValueSet &Available);
300 /// It is a visitor for GCPtrTracker::verifyFunction. It decides if the
301 /// instruction (which uses heap reference) is legal or not, given our safepoint
303 class InstructionVerifier {
304 bool AnyInvalidUses = false;
307 void verifyInstruction(const GCPtrTracker *Tracker, const Instruction &I,
308 const AvailableValueSet &AvailableSet);
310 bool hasAnyInvalidUses() const { return AnyInvalidUses; }
313 void reportInvalidUse(const Value &V, const Instruction &I);
315 } // end anonymous namespace
317 GCPtrTracker::GCPtrTracker(const Function &F, const DominatorTree &DT) : F(F) {
318 // First, calculate Contribution of each BB.
319 for (const BasicBlock &BB : F) {
320 BasicBlockState *BBS = new (BSAllocator.Allocate()) BasicBlockState;
321 for (const auto &I : BB)
322 transferInstruction(I, BBS->Cleared, BBS->Contribution);
326 // Initialize AvailableIn/Out sets of each BB using only information about
328 for (auto &BBI : BlockMap) {
329 gatherDominatingDefs(BBI.first, BBI.second->AvailableIn, DT);
330 transferBlock(BBI.first, *BBI.second, true);
333 // Simulate the flow of defs through the CFG and recalculate AvailableIn/Out
334 // sets of each BB until it converges. If any def is proved to be an
335 // unrelocated pointer, it will be removed from all BBSs.
336 recalculateBBsStates();
339 BasicBlockState *GCPtrTracker::getBasicBlockState(const BasicBlock *BB) {
340 auto it = BlockMap.find(BB);
341 assert(it != BlockMap.end() &&
342 "No such BB in BlockMap! Probably BB from another function");
346 const BasicBlockState *GCPtrTracker::getBasicBlockState(
347 const BasicBlock *BB) const {
348 return const_cast<GCPtrTracker *>(this)->getBasicBlockState(BB);
351 bool GCPtrTracker::instructionMayBeSkipped(const Instruction *I) const {
352 return ValidUnrelocatedDefs.count(I);
355 void GCPtrTracker::verifyFunction(GCPtrTracker &&Tracker,
356 InstructionVerifier &Verifier) {
357 // We need RPO here to a) report always the first error b) report errors in
358 // same order from run to run.
359 ReversePostOrderTraversal<const Function *> RPOT(&Tracker.F);
360 for (const BasicBlock *BB : RPOT) {
361 BasicBlockState *BBS = Tracker.getBasicBlockState(BB);
362 // We destructively modify AvailableIn as we traverse the block instruction
364 AvailableValueSet &AvailableSet = BBS->AvailableIn;
365 for (const Instruction &I : *BB) {
366 if (Tracker.instructionMayBeSkipped(&I))
367 continue; // This instruction shouldn't be added to AvailableSet.
369 Verifier.verifyInstruction(&Tracker, I, AvailableSet);
371 // Model the effect of current instruction on AvailableSet to keep the set
372 // relevant at each point of BB.
373 bool Cleared = false;
374 transferInstruction(I, Cleared, AvailableSet);
380 void GCPtrTracker::recalculateBBsStates() {
381 SetVector<const BasicBlock *> Worklist;
382 // TODO: This order is suboptimal, it's better to replace it with priority
383 // queue where priority is RPO number of BB.
384 for (auto &BBI : BlockMap)
385 Worklist.insert(BBI.first);
387 // This loop iterates the AvailableIn/Out sets until it converges.
388 // The AvailableIn and AvailableOut sets decrease as we iterate.
389 while (!Worklist.empty()) {
390 const BasicBlock *BB = Worklist.pop_back_val();
391 BasicBlockState *BBS = BlockMap[BB];
393 size_t OldInCount = BBS->AvailableIn.size();
394 for (const BasicBlock *PBB : predecessors(BB))
395 set_intersect(BBS->AvailableIn, BlockMap[PBB]->AvailableOut);
397 assert(OldInCount >= BBS->AvailableIn.size() && "invariant!");
399 bool InputsChanged = OldInCount != BBS->AvailableIn.size();
400 bool ContributionChanged =
401 removeValidUnrelocatedDefs(BB, BBS, BBS->Contribution);
402 if (!InputsChanged && !ContributionChanged)
405 size_t OldOutCount = BBS->AvailableOut.size();
406 transferBlock(BB, *BBS, ContributionChanged);
407 if (OldOutCount != BBS->AvailableOut.size()) {
408 assert(OldOutCount > BBS->AvailableOut.size() && "invariant!");
409 Worklist.insert(succ_begin(BB), succ_end(BB));
414 bool GCPtrTracker::removeValidUnrelocatedDefs(const BasicBlock *BB,
415 const BasicBlockState *BBS,
416 AvailableValueSet &Contribution) {
417 assert(&BBS->Contribution == &Contribution &&
418 "Passed Contribution should be from the passed BasicBlockState!");
419 AvailableValueSet AvailableSet = BBS->AvailableIn;
420 bool ContributionChanged = false;
421 for (const Instruction &I : *BB) {
422 bool ProducesUnrelocatedPointer = false;
423 if ((isa<GetElementPtrInst>(I) || isa<BitCastInst>(I)) &&
424 containsGCPtrType(I.getType())) {
425 // GEP/bitcast of unrelocated pointer is legal by itself but this
426 // def shouldn't appear in any AvailableSet.
427 for (const Value *V : I.operands())
428 if (containsGCPtrType(V->getType()) &&
429 isNotExclusivelyConstantDerived(V) && !AvailableSet.count(V)) {
430 ProducesUnrelocatedPointer = true;
434 if (!ProducesUnrelocatedPointer) {
435 bool Cleared = false;
436 transferInstruction(I, Cleared, AvailableSet);
439 // Remove def of unrelocated pointer from Contribution of this BB
440 // and trigger update of all its successors.
441 Contribution.erase(&I);
442 ValidUnrelocatedDefs.insert(&I);
443 DEBUG(dbgs() << "Removing " << I << " from Contribution of "
444 << BB->getName() << "\n");
445 ContributionChanged = true;
448 return ContributionChanged;
451 void GCPtrTracker::gatherDominatingDefs(const BasicBlock *BB,
452 AvailableValueSet &Result,
453 const DominatorTree &DT) {
454 DomTreeNode *DTN = DT[const_cast<BasicBlock *>(BB)];
456 while (DTN->getIDom()) {
457 DTN = DTN->getIDom();
458 const auto &Defs = BlockMap[DTN->getBlock()]->Contribution;
459 Result.insert(Defs.begin(), Defs.end());
460 // If this block is 'Cleared', then nothing LiveIn to this block can be
461 // available after this block completes. Note: This turns out to be
462 // really important for reducing memory consuption of the initial available
463 // sets and thus peak memory usage by this verifier.
464 if (BlockMap[DTN->getBlock()]->Cleared)
468 for (const Argument &A : BB->getParent()->args())
469 if (containsGCPtrType(A.getType()))
473 void GCPtrTracker::transferBlock(const BasicBlock *BB, BasicBlockState &BBS,
474 bool ContributionChanged) {
475 const AvailableValueSet &AvailableIn = BBS.AvailableIn;
476 AvailableValueSet &AvailableOut = BBS.AvailableOut;
479 // AvailableOut will change only when Contribution changed.
480 if (ContributionChanged)
481 AvailableOut = BBS.Contribution;
483 // Otherwise, we need to reduce the AvailableOut set by things which are no
484 // longer in our AvailableIn
485 AvailableValueSet Temp = BBS.Contribution;
486 set_union(Temp, AvailableIn);
487 AvailableOut = std::move(Temp);
490 DEBUG(dbgs() << "Transfered block " << BB->getName() << " from ";
491 PrintValueSet(dbgs(), AvailableIn.begin(), AvailableIn.end());
493 PrintValueSet(dbgs(), AvailableOut.begin(), AvailableOut.end());
497 void GCPtrTracker::transferInstruction(const Instruction &I, bool &Cleared,
498 AvailableValueSet &Available) {
499 if (isStatepoint(I)) {
502 } else if (containsGCPtrType(I.getType()))
503 Available.insert(&I);
506 void InstructionVerifier::verifyInstruction(
507 const GCPtrTracker *Tracker, const Instruction &I,
508 const AvailableValueSet &AvailableSet) {
509 if (const PHINode *PN = dyn_cast<PHINode>(&I)) {
510 if (containsGCPtrType(PN->getType()))
511 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
512 const BasicBlock *InBB = PN->getIncomingBlock(i);
513 const Value *InValue = PN->getIncomingValue(i);
515 if (isNotExclusivelyConstantDerived(InValue) &&
516 !Tracker->getBasicBlockState(InBB)->AvailableOut.count(InValue))
517 reportInvalidUse(*InValue, *PN);
519 } else if (isa<CmpInst>(I) &&
520 containsGCPtrType(I.getOperand(0)->getType())) {
521 Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
522 enum BaseType baseTyLHS = getBaseType(LHS),
523 baseTyRHS = getBaseType(RHS);
525 // Returns true if LHS and RHS are unrelocated pointers and they are
526 // valid unrelocated uses.
527 auto hasValidUnrelocatedUse = [&AvailableSet, baseTyLHS, baseTyRHS, &LHS,
529 // A cmp instruction has valid unrelocated pointer operands only if
530 // both operands are unrelocated pointers.
531 // In the comparison between two pointers, if one is an unrelocated
532 // use, the other *should be* an unrelocated use, for this
533 // instruction to contain valid unrelocated uses. This unrelocated
534 // use can be a null constant as well, or another unrelocated
536 if (AvailableSet.count(LHS) || AvailableSet.count(RHS))
538 // Constant pointers (that are not exclusively null) may have
539 // meaning in different VMs, so we cannot reorder the compare
540 // against constant pointers before the safepoint. In other words,
541 // comparison of an unrelocated use against a non-null constant
543 if ((baseTyLHS == BaseType::ExclusivelySomeConstant &&
544 baseTyRHS == BaseType::NonConstant) ||
545 (baseTyLHS == BaseType::NonConstant &&
546 baseTyRHS == BaseType::ExclusivelySomeConstant))
548 // All other cases are valid cases enumerated below:
549 // 1. Comparison between an exlusively derived null pointer and a
550 // constant base pointer.
551 // 2. Comparison between an exlusively derived null pointer and a
552 // non-constant unrelocated base pointer.
553 // 3. Comparison between 2 unrelocated pointers.
556 if (!hasValidUnrelocatedUse()) {
557 // Print out all non-constant derived pointers that are unrelocated
558 // uses, which are invalid.
559 if (baseTyLHS == BaseType::NonConstant && !AvailableSet.count(LHS))
560 reportInvalidUse(*LHS, I);
561 if (baseTyRHS == BaseType::NonConstant && !AvailableSet.count(RHS))
562 reportInvalidUse(*RHS, I);
565 for (const Value *V : I.operands())
566 if (containsGCPtrType(V->getType()) &&
567 isNotExclusivelyConstantDerived(V) && !AvailableSet.count(V))
568 reportInvalidUse(*V, I);
572 void InstructionVerifier::reportInvalidUse(const Value &V,
573 const Instruction &I) {
574 errs() << "Illegal use of unrelocated value found!\n";
575 errs() << "Def: " << V << "\n";
576 errs() << "Use: " << I << "\n";
579 AnyInvalidUses = true;
582 static void Verify(const Function &F, const DominatorTree &DT) {
583 DEBUG(dbgs() << "Verifying gc pointers in function: " << F.getName() << "\n");
585 dbgs() << "Verifying gc pointers in function: " << F.getName() << "\n";
587 GCPtrTracker Tracker(F, DT);
589 // We now have all the information we need to decide if the use of a heap
590 // reference is legal or not, given our safepoint semantics.
592 InstructionVerifier Verifier;
593 GCPtrTracker::verifyFunction(std::move(Tracker), Verifier);
595 if (PrintOnly && !Verifier.hasAnyInvalidUses()) {
596 dbgs() << "No illegal uses found by SafepointIRVerifier in: " << F.getName()