51 #define DEBUG_TYPE "safepoint-ir-verifier" 77 auto &PU = PredIt.
getUse();
84 assert(!isDeadBlock(InBB) &&
"block must be live");
88 if (InBB == *PredIt) {
89 if (!isDeadEdge(&getEdge(PredIt)))
95 assert(Listed &&
"basic block is not found among incoming blocks");
100 bool isDeadBlock(
const BasicBlock *BB)
const {
101 return DeadBlocks.
count(BB);
104 bool isDeadEdge(
const Use *U)
const {
105 assert(dyn_cast<Instruction>(U->getUser())->isTerminator() &&
106 "edge must be operand of terminator");
107 assert(cast_or_null<BasicBlock>(U->get()) &&
108 "edge must refer to basic block");
109 assert(!isDeadBlock(dyn_cast<Instruction>(U->getUser())->
getParent()) &&
110 "isDeadEdge() must be applied to edge from live block");
111 return DeadEdges.
count(U);
114 bool hasLiveIncomingEdges(
const BasicBlock *BB)
const {
117 auto &PU = PredIt.
getUse();
119 if (!isDeadBlock(*PredIt) && !isDeadEdge(&U))
137 assert(TI &&
"blocks must be well formed");
163 while (!NewDead.
empty()) {
179 if (!isDeadBlock(S) && !hasLiveIncomingEdges(S))
184 void addDeadEdge(
const Use &DeadEdge) {
185 if (!DeadEdges.
insert(&DeadEdge))
189 if (hasLiveIncomingEdges(BB))
198 const CFGDeadness &CD);
209 auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
211 CD.processFunction(F, DT);
221 StringRef getPassName()
const override {
return "safepoint verifier"; }
226 SafepointIRVerifier
pass;
227 pass.runOnFunction(F);
233 return new SafepointIRVerifier();
237 "Safepoint IR Verifier",
false,
false)
243 if (
auto *PT = dyn_cast<PointerType>(T))
247 return (1 == PT->getAddressSpace());
254 if (
VectorType *VT = dyn_cast<VectorType>(Ty))
256 if (
ArrayType *AT = dyn_cast<ArrayType>(Ty))
264 template<
typename IteratorTy>
267 while (Begin != End) {
268 OS << **Begin <<
" ";
295 bool Cleared =
false;
319 bool isExclusivelyDerivedFromNull =
true;
324 while(!Worklist.
empty()) {
326 if (!Visited.
insert(V).second)
329 if (
const auto *CI = dyn_cast<CastInst>(V)) {
330 Worklist.
push_back(CI->stripPointerCasts());
333 if (
const auto *
GEP = dyn_cast<GetElementPtrInst>(V)) {
339 if (
const auto *PN = dyn_cast<PHINode>(V)) {
344 if (
const auto *
SI = dyn_cast<SelectInst>(V)) {
350 if (isa<Constant>(V)) {
354 isExclusivelyDerivedFromNull =
false;
374 class InstructionVerifier;
434 const CFGDeadness &CD;
446 const CFGDeadness &CD);
449 return CD.hasLiveIncomingEdge(PN, InBB);
455 bool isValuePoisoned(
const Value *V)
const {
return PoisonedDefs.
count(V); }
468 return BlockMap.
find(BB) != BlockMap.
end();
473 bool instructionMayBeSkipped(
const Instruction *
I)
const;
477 void recalculateBBsStates();
485 bool removeValidUnrelocatedDefs(
const BasicBlock *BB,
501 bool ContributionChanged);
504 static void transferInstruction(
const Instruction &I,
bool &Cleared,
511 class InstructionVerifier {
512 bool AnyInvalidUses =
false;
515 void verifyInstruction(
const GCPtrTracker *Tracker,
const Instruction &
I,
518 bool hasAnyInvalidUses()
const {
return AnyInvalidUses; }
526 const CFGDeadness &CD) :
F(F), CD(CD) {
530 if (!CD.isDeadBlock(&BB)) {
532 for (
const auto &
I : BB)
539 for (
auto &BBI : BlockMap) {
540 gatherDominatingDefs(BBI.first, BBI.second->AvailableIn, DT);
541 transferBlock(BBI.first, *BBI.second,
true);
547 recalculateBBsStates();
551 auto it = BlockMap.find(BB);
552 return it != BlockMap.end() ? it->second :
nullptr;
557 return const_cast<GCPtrTracker *
>(
this)->getBasicBlockState(BB);
560 bool GCPtrTracker::instructionMayBeSkipped(
const Instruction *
I)
const {
563 return ValidUnrelocatedDefs.count(I) || PoisonedDefs.count(I);
580 if (Tracker.instructionMayBeSkipped(&I))
583 Verifier.verifyInstruction(&Tracker, I, AvailableSet);
587 bool Cleared =
false;
588 transferInstruction(I, Cleared, AvailableSet);
594 void GCPtrTracker::recalculateBBsStates() {
598 for (
auto &BBI : BlockMap)
599 Worklist.
insert(BBI.first);
603 while (!Worklist.
empty()) {
613 if (PBBS && !CD.isDeadEdge(&CFGDeadness::getEdge(PredIt)))
620 bool ContributionChanged =
622 if (!InputsChanged && !ContributionChanged)
626 transferBlock(BB, *BBS, ContributionChanged);
634 bool GCPtrTracker::removeValidUnrelocatedDefs(
const BasicBlock *BB,
638 "Passed Contribution should be from the passed BasicBlockState!");
640 bool ContributionChanged =
false;
644 bool ValidUnrelocatedPointerDef =
false;
645 bool PoisonedPointerDef =
false;
647 if (
const PHINode *PN = dyn_cast<PHINode>(&I)) {
650 bool HasRelocatedInputs =
false;
651 bool HasUnrelocatedInputs =
false;
654 if (!isMapped(InBB) ||
655 !CD.hasLiveIncomingEdge(PN, InBB))
661 if (isValuePoisoned(InValue)) {
663 HasRelocatedInputs =
true;
664 HasUnrelocatedInputs =
true;
667 if (BlockMap[InBB]->AvailableOut.count(InValue))
668 HasRelocatedInputs =
true;
670 HasUnrelocatedInputs =
true;
673 if (HasUnrelocatedInputs) {
674 if (HasRelocatedInputs)
675 PoisonedPointerDef =
true;
677 ValidUnrelocatedPointerDef =
true;
680 }
else if ((isa<GetElementPtrInst>(I) || isa<BitCastInst>(I)) &&
687 if (isValuePoisoned(V))
688 PoisonedPointerDef =
true;
690 ValidUnrelocatedPointerDef =
true;
694 assert(!(ValidUnrelocatedPointerDef && PoisonedPointerDef) &&
695 "Value cannot be both unrelocated and poisoned!");
696 if (ValidUnrelocatedPointerDef) {
699 Contribution.
erase(&I);
700 PoisonedDefs.erase(&I);
701 ValidUnrelocatedDefs.insert(&I);
703 <<
" from Contribution of " << BB->
getName() <<
"\n");
704 ContributionChanged =
true;
705 }
else if (PoisonedPointerDef) {
708 Contribution.
erase(&I);
709 PoisonedDefs.insert(&I);
710 LLVM_DEBUG(
dbgs() <<
"Removing poisoned " << I <<
" from Contribution of " 712 ContributionChanged =
true;
714 bool Cleared =
false;
715 transferInstruction(I, Cleared, AvailableSet);
719 return ContributionChanged;
722 void GCPtrTracker::gatherDominatingDefs(
const BasicBlock *BB,
727 assert(DTN &&
"Unreachable blocks are ignored");
730 auto BBS = getBasicBlockState(DTN->
getBlock());
731 assert(BBS &&
"immediate dominator cannot be dead for a live block");
733 Result.
insert(Defs.begin(), Defs.end());
748 bool ContributionChanged) {
754 if (ContributionChanged)
761 AvailableOut = std::move(Temp);
771 void GCPtrTracker::transferInstruction(
const Instruction &I,
bool &Cleared,
780 void InstructionVerifier::verifyInstruction(
783 if (
const PHINode *PN = dyn_cast<PHINode>(&I)) {
789 !Tracker->hasLiveIncomingEdge(PN, InBB))
796 reportInvalidUse(*InValue, *PN);
798 }
else if (isa<CmpInst>(I) &&
806 auto hasValidUnrelocatedUse = [&AvailableSet, Tracker, baseTyLHS, baseTyRHS,
815 if (AvailableSet.
count(LHS) || AvailableSet.
count(RHS))
846 if (!hasValidUnrelocatedUse()) {
850 reportInvalidUse(*LHS, I);
852 reportInvalidUse(*RHS, I);
858 reportInvalidUse(*V, I);
862 void InstructionVerifier::reportInvalidUse(
const Value &V,
864 errs() <<
"Illegal use of unrelocated value found!\n";
865 errs() <<
"Def: " << V <<
"\n";
866 errs() <<
"Use: " << I <<
"\n";
869 AnyInvalidUses =
true;
873 const CFGDeadness &CD) {
877 dbgs() <<
"Verifying gc pointers in function: " << F.
getName() <<
"\n";
879 GCPtrTracker Tracker(F, DT, CD);
887 if (
PrintOnly && !Verifier.hasAnyInvalidUses()) {
888 dbgs() <<
"No illegal uses found by SafepointIRVerifier in: " << F.
getName()
static void PrintValueSet(raw_ostream &OS, IteratorTy Begin, IteratorTy End)
Safe Stack instrumentation pass
raw_ostream & errs()
This returns a reference to a raw_ostream for standard error.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
This class represents an incoming formal argument to a Function.
LLVM_NODISCARD T pop_back_val()
This class represents lattice values for constants.
void initializeSafepointIRVerifierPass(PassRegistry &)
Implements a dense probed hash-table based set.
void push_back(const T &Elt)
static enum BaseType getBaseType(const Value *Val)
Return the baseType for Val which states whether Val is exclusively derived from constant/null, or not exclusively derived from constant.
bool erase(const ValueT &V)
const Use & getOperandUse(unsigned i) const
BasicBlock * getSuccessor(unsigned i) const
static bool isNotExclusivelyConstantDerived(const Value *V)
Value * getCondition() const
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
static Constant * getNullValue(Type *Ty)
Constructor to create a '0' constant of arbitrary type.
#define INITIALIZE_PASS_DEPENDENCY(depName)
AvailableValueSet AvailableIn
Class to represent struct types.
A Use represents the edge between a Value definition and its users.
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...
User * getUser() const LLVM_READONLY
Returns the User that contains this Use.
Type * getType() const
All values are typed, get the type of this value.
bool insert(const value_type &X)
Insert a new element into the SetVector.
bool isStatepoint(const CallBase *Call)
Class to represent array types.
verify safepoint Safepoint IR static false bool isGCPointerType(Type *T)
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Value * getOperand(unsigned i) const
size_type count(const key_type &key) const
Count the number of elements of a given key in the SetVector.
Interval::succ_iterator succ_end(Interval *I)
Use & getUse() const
getUse - Return the operand Use in the predecessor's terminator of the successor. ...
iterator find(const_arg_type_t< KeyT > Val)
AvailableValueSet Contribution
State we compute and track per basic block.
static bool runOnFunction(Function &F, bool PostInlining)
initializer< Ty > init(const Ty &Val)
void verifySafepointIR(Function &F)
Run the safepoint verifier over a single function. Crashes on failure.
uint64_t getZExtValue() const
Return the constant as a 64-bit unsigned integer value after it has been zero extended as appropriate...
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
FunctionPass * createSafepointIRVerifierPass()
Create an instance of the safepoint verifier pass which can be added to a pass pipeline to check for ...
void set_intersect(S1Ty &S1, const S2Ty &S2)
set_intersect(A, B) - Compute A := A ^ B Identical to set_intersection, except that it works on set<>...
LLVM Basic Block Representation.
The instances of the Type class are immutable: once they are created, they are never changed...
Conditional or Unconditional Branch instruction.
void getDescendants(NodeT *R, SmallVectorImpl< NodeT *> &Result) const
Get all nodes dominated by R, including R itself.
DomTreeNodeBase * getIDom() const
std::pair< iterator, bool > insert(const ValueT &V)
static bool containsGCPtrType(Type *Ty)
Represent the analysis usage information of a pass.
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly...
FunctionPass class - This class is used to implement most global optimizations.
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
bool verify(const TargetRegisterInfo &TRI) const
Check that information hold by this instance make sense for the given TRI.
BaseType
A given derived pointer can have multiple base pointers through phi/selects.
A SetVector that performs no allocations if smaller than a certain size.
This is the shared class of boolean and integer constants.
AnalysisUsage & addRequiredID(const void *ID)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small...
Module.h This file contains the declarations for the Module class.
LLVM_NODISCARD T pop_back_val()
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
bool isConditional() const
unsigned getNumIncomingValues() const
Return the number of incoming edges.
A BumpPtrAllocator that allows only elements of a specific type to be allocated.
AvailableValueSet AvailableOut
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Class to represent vector types.
void setPreservesAll()
Set by analyses that do not transform their input at all.
INITIALIZE_PASS_BEGIN(SafepointIRVerifier, "verify-safepoint-ir", "Safepoint IR Verifier", false, false) INITIALIZE_PASS_END(SafepointIRVerifier
static cl::opt< bool > PrintOnly("safepoint-ir-verifier-print-only", cl::init(false))
This option is used for writing test cases.
LLVM_NODISCARD bool empty() const
verify safepoint Safepoint IR Verifier
StringRef getName() const
Return a constant reference to the value's name.
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
const Function * getParent() const
Return the enclosing method, or null if none.
bool empty() const
Determine if the SetVector is empty or not.
bool verifyFunction(const Function &F, raw_ostream *OS=nullptr)
Check a function for errors, useful for use when debugging a pass.
LLVM_NODISCARD std::enable_if<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
size_type count(const_arg_type_t< ValueT > V) const
Return 1 if the specified key is in the set, 0 otherwise.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
LLVM Value Representation.
A vector that has set insertion semantics.
succ_range successors(Instruction *I)
static const Function * getParent(const Value *V)
This class implements an extremely fast bulk output stream that can only output to a stream...
StringRef - Represent a constant reference to a string, i.e.
Legacy analysis pass which computes a DominatorTree.
op_range incoming_values()
bool set_union(S1Ty &S1, const S2Ty &S2)
set_union(A, B) - Compute A := A u B, return whether A changed.
Statically lint checks LLVM IR
iterator_range< arg_iterator > args()
const BasicBlock * getParent() const
static void Verify(const Function &F, const DominatorTree &DT, const CFGDeadness &CD)