Go to the documentation of this file.
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");
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);
117 auto &PU = PredIt.
getUse();
119 if (!isDeadBlock(*PredIt) && !isDeadEdge(&U))
137 assert(TI &&
"blocks must be well formed");
141 const BranchInst *BI = dyn_cast<BranchInst>(TI);
162 NewDead.push_back(
BB);
163 while (!NewDead.empty()) {
174 DeadBlocks.
insert(Dom.begin(), Dom.end());
179 if (!isDeadBlock(
S) && !hasLiveIncomingEdges(
S))
180 NewDead.push_back(
S);
184 void addDeadEdge(
const Use &DeadEdge) {
185 if (!DeadEdges.
insert(&DeadEdge))
189 if (hasLiveIncomingEdges(
BB))
198 const CFGDeadness &CD);
205 CD.processFunction(
F, DT);
220 auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
222 CD.processFunction(
F, DT);
237 SafepointIRVerifier
pass;
238 pass.runOnFunction(
F);
244 return new SafepointIRVerifier();
248 "Safepoint IR Verifier",
false,
false)
254 if (
auto *PT = dyn_cast<PointerType>(
T))
258 return (1 == PT->getAddressSpace());
265 if (
VectorType *VT = dyn_cast<VectorType>(Ty))
267 if (
ArrayType *AT = dyn_cast<ArrayType>(Ty))
275 template<
typename IteratorTy>
278 while (Begin != End) {
279 OS << **Begin <<
" ";
330 bool isExclusivelyDerivedFromNull =
true;
331 Worklist.push_back(Val);
335 while(!Worklist.empty()) {
337 if (!Visited.
insert(V).second)
340 if (
const auto *CI = dyn_cast<CastInst>(V)) {
341 Worklist.push_back(CI->stripPointerCasts());
344 if (
const auto *
GEP = dyn_cast<GetElementPtrInst>(V)) {
345 Worklist.push_back(
GEP->getPointerOperand());
350 if (
const auto *PN = dyn_cast<PHINode>(V)) {
354 if (
const auto *
SI = dyn_cast<SelectInst>(V)) {
356 Worklist.push_back(
SI->getTrueValue());
357 Worklist.push_back(
SI->getFalseValue());
360 if (
const auto *GCRelocate = dyn_cast<GCRelocateInst>(V)) {
363 Worklist.push_back(GCRelocate->getDerivedPtr());
366 if (
const auto *FI = dyn_cast<FreezeInst>(V)) {
368 Worklist.push_back(FI->getOperand(0));
371 if (isa<Constant>(V)) {
374 if (V != Constant::getNullValue(V->
getType()))
375 isExclusivelyDerivedFromNull =
false;
395 class InstructionVerifier;
455 const CFGDeadness &CD;
467 const CFGDeadness &CD);
470 return CD.hasLiveIncomingEdge(PN, InBB);
476 bool isValuePoisoned(
const Value *V)
const {
return PoisonedDefs.
count(V); }
489 return BlockMap.
find(
BB) != BlockMap.
end();
494 bool instructionMayBeSkipped(
const Instruction *
I)
const;
498 void recalculateBBsStates();
522 bool ContributionChanged);
525 static void transferInstruction(
const Instruction &
I,
bool &Cleared,
532 class InstructionVerifier {
533 bool AnyInvalidUses =
false;
536 void verifyInstruction(
const GCPtrTracker *Tracker,
const Instruction &
I,
539 bool hasAnyInvalidUses()
const {
return AnyInvalidUses; }
547 const CFGDeadness &CD) :
F(
F), CD(CD) {
551 if (!CD.isDeadBlock(&
BB)) {
553 for (
const auto &
I :
BB)
560 for (
auto &BBI : BlockMap) {
561 gatherDominatingDefs(BBI.first, BBI.second->AvailableIn, DT);
562 transferBlock(BBI.first, *BBI.second,
true);
568 recalculateBBsStates();
577 return const_cast<GCPtrTracker *
>(
this)->getBasicBlockState(
BB);
580 bool GCPtrTracker::instructionMayBeSkipped(
const Instruction *
I)
const {
583 return ValidUnrelocatedDefs.
count(
I) || PoisonedDefs.
count(
I);
600 if (Tracker.instructionMayBeSkipped(&
I))
603 Verifier.verifyInstruction(&Tracker,
I, AvailableSet);
607 bool Cleared =
false;
608 transferInstruction(
I, Cleared, AvailableSet);
614 void GCPtrTracker::recalculateBBsStates() {
618 for (
auto &BBI : BlockMap)
619 Worklist.
insert(BBI.first);
623 while (!Worklist.
empty()) {
633 if (PBBS && !CD.isDeadEdge(&CFGDeadness::getEdge(PredIt)))
640 bool ContributionChanged =
642 if (!InputsChanged && !ContributionChanged)
646 transferBlock(
BB, *BBS, ContributionChanged);
654 bool GCPtrTracker::removeValidUnrelocatedDefs(
const BasicBlock *
BB,
658 "Passed Contribution should be from the passed BasicBlockState!");
660 bool ContributionChanged =
false;
664 bool ValidUnrelocatedPointerDef =
false;
665 bool PoisonedPointerDef =
false;
667 if (
const PHINode *PN = dyn_cast<PHINode>(&
I)) {
670 bool HasRelocatedInputs =
false;
671 bool HasUnrelocatedInputs =
false;
674 if (!isMapped(InBB) ||
675 !CD.hasLiveIncomingEdge(PN, InBB))
681 if (isValuePoisoned(InValue)) {
683 HasRelocatedInputs =
true;
684 HasUnrelocatedInputs =
true;
687 if (BlockMap[InBB]->AvailableOut.count(InValue))
688 HasRelocatedInputs =
true;
690 HasUnrelocatedInputs =
true;
693 if (HasUnrelocatedInputs) {
694 if (HasRelocatedInputs)
695 PoisonedPointerDef =
true;
697 ValidUnrelocatedPointerDef =
true;
700 }
else if ((isa<GetElementPtrInst>(
I) || isa<BitCastInst>(
I)) &&
704 for (
const Value *V :
I.operands())
707 if (isValuePoisoned(V))
708 PoisonedPointerDef =
true;
710 ValidUnrelocatedPointerDef =
true;
714 assert(!(ValidUnrelocatedPointerDef && PoisonedPointerDef) &&
715 "Value cannot be both unrelocated and poisoned!");
716 if (ValidUnrelocatedPointerDef) {
721 ValidUnrelocatedDefs.
insert(&
I);
723 <<
" from Contribution of " <<
BB->getName() <<
"\n");
724 ContributionChanged =
true;
725 }
else if (PoisonedPointerDef) {
730 LLVM_DEBUG(
dbgs() <<
"Removing poisoned " <<
I <<
" from Contribution of "
731 <<
BB->getName() <<
"\n");
732 ContributionChanged =
true;
734 bool Cleared =
false;
735 transferInstruction(
I, Cleared, AvailableSet);
739 return ContributionChanged;
742 void GCPtrTracker::gatherDominatingDefs(
const BasicBlock *
BB,
747 assert(DTN &&
"Unreachable blocks are ignored");
750 auto BBS = getBasicBlockState(DTN->
getBlock());
751 assert(BBS &&
"immediate dominator cannot be dead for a live block");
753 Result.insert(Defs.begin(), Defs.end());
768 bool ContributionChanged) {
774 if (ContributionChanged)
791 void GCPtrTracker::transferInstruction(
const Instruction &
I,
bool &Cleared,
793 if (isa<GCStatepointInst>(
I)) {
800 void InstructionVerifier::verifyInstruction(
803 if (
const PHINode *PN = dyn_cast<PHINode>(&
I)) {
809 !Tracker->hasLiveIncomingEdge(PN, InBB))
816 reportInvalidUse(*InValue, *PN);
818 }
else if (isa<CmpInst>(
I) &&
826 auto hasValidUnrelocatedUse = [&AvailableSet, Tracker, baseTyLHS, baseTyRHS,
866 if (!hasValidUnrelocatedUse()) {
870 reportInvalidUse(*
LHS,
I);
872 reportInvalidUse(*
RHS,
I);
875 for (
const Value *V :
I.operands())
878 reportInvalidUse(*V,
I);
882 void InstructionVerifier::reportInvalidUse(
const Value &V,
884 errs() <<
"Illegal use of unrelocated value found!\n";
885 errs() <<
"Def: " << V <<
"\n";
886 errs() <<
"Use: " <<
I <<
"\n";
889 AnyInvalidUses =
true;
893 const CFGDeadness &CD) {
894 LLVM_DEBUG(
dbgs() <<
"Verifying gc pointers in function: " <<
F.getName()
897 dbgs() <<
"Verifying gc pointers in function: " <<
F.getName() <<
"\n";
899 GCPtrTracker Tracker(
F, DT, CD);
908 dbgs() <<
"No illegal uses found by SafepointIRVerifier in: " <<
F.getName()
A set of analyses that are preserved following a run of a transformation pass.
void verifySafepointIR(Function &F)
Run the safepoint verifier over a single function. Crashes on failure.
This class represents an incoming formal argument to a Function.
This is an optimization pass for GlobalISel generic memory operations.
op_range incoming_values()
static cl::opt< bool > PrintOnly("safepoint-ir-verifier-print-only", cl::init(false))
This option is used for writing test cases.
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Interval::succ_iterator succ_end(Interval *I)
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...
bool set_union(S1Ty &S1, const S2Ty &S2)
set_union(A, B) - Compute A := A u B, return whether A changed.
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
bool verifyFunction(const Function &F, raw_ostream *OS=nullptr)
Check a function for errors, useful for use when debugging a pass.
virtual bool runOnFunction(Function &F)=0
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.
A BumpPtrAllocator that allows only elements of a specific type to be allocated.
The instances of the Type class are immutable: once they are created, they are never changed.
auto successors(MachineBasicBlock *BB)
raw_fd_ostream & errs()
This returns a reference to a raw_ostream for standard error.
LLVM_NODISCARD T pop_back_val()
Class to represent array types.
DomTreeNodeBase * getIDom() const
std::pair< iterator, bool > insert(const ValueT &V)
size_type count(const_arg_type_t< ValueT > V) const
Return 1 if the specified key is in the set, 0 otherwise.
AvailableValueSet AvailableOut
void getDescendants(NodeT *R, SmallVectorImpl< NodeT * > &Result) const
Get all nodes dominated by R, including R itself.
static enum BaseType getBaseType(const Value *Val)
Return the baseType for Val which states whether Val is exclusively derived from constant/null,...
INITIALIZE_PASS_BEGIN(SafepointIRVerifier, "verify-safepoint-ir", "Safepoint IR Verifier", false, false) INITIALIZE_PASS_END(SafepointIRVerifier
LLVM Basic Block Representation.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
const Use & getOperandUse(unsigned i) const
verify safepoint Safepoint IR static false bool isGCPointerType(Type *T)
This is the shared class of boolean and integer constants.
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
@ Available
We know the block is fully available. This is a fixpoint.
Represent the analysis usage information of a pass.
@ ExclusivelySomeConstant
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
modulo schedule Modulo Schedule test pass
Legacy analysis pass which computes a DominatorTree.
This class implements an extremely fast bulk output stream that can only output to a stream.
User * getUser() const
Returns the User that contains this Use.
Statically lint checks LLVM IR
bool empty() const
Determine if the SetVector is empty or not.
unsigned getNumIncomingValues() const
Return the number of incoming edges.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
static RegisterPass< DebugifyFunctionPass > DF("debugify-function", "Attach debug info to a function")
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Value * getCondition() const
static bool isNotExclusivelyConstantDerived(const Value *V)
Base class of all SIMD vector types.
verify safepoint Safepoint IR Verifier
static void Verify(const Function &F, const DominatorTree &DT, const CFGDeadness &CD)
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
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
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...
initializer< Ty > init(const Ty &Val)
iterator find(const_arg_type_t< KeyT > Val)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
StandardInstrumentations SI(Debug, VerifyEach)
bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
bool insert(const value_type &X)
Insert a new element into the SetVector.
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
Class to represent struct types.
SmallVector< MachineOperand, 4 > Cond
StringRef - Represent a constant reference to a string, i.e.
virtual StringRef getPassName() const
getPassName - Return a nice clean name for a pass.
Type * getType() const
All values are typed, get the type of this value.
void append_range(Container &C, Range &&R)
Wrapper function to append a range to a container.
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
FunctionPass * createSafepointIRVerifierPass()
Create an instance of the safepoint verifier pass which can be added to a pass pipeline to check for ...
AvailableValueSet AvailableIn
T * Allocate(size_t num=1)
Allocate space for an array of objects without constructing them.
void setPreservesAll()
Set by analyses that do not transform their input at all.
void initializeSafepointIRVerifierPass(PassRegistry &)
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
AvailableValueSet Contribution
Use & getUse() const
getUse - Return the operand Use in the predecessor's terminator of the successor.
size_type count(const key_type &key) const
Count the number of elements of a given key in the SetVector.
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
static bool containsGCPtrType(Type *Ty)
Analysis pass which computes a DominatorTree.
const BasicBlock * getParent() const
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
bool erase(const ValueT &V)
static void PrintValueSet(raw_ostream &OS, IteratorTy Begin, IteratorTy End)
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<>...
virtual void getAnalysisUsage(AnalysisUsage &) const
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
A SetVector that performs no allocations if smaller than a certain size.
A container for analyses that lazily runs them and caches their results.
FunctionPass class - This class is used to implement most global optimizations.
AnalysisUsage & addRequiredID(const void *ID)
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
State we compute and track per basic block.
*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)
Conditional or Unconditional Branch instruction.
A vector that has set insertion semantics.
LLVM_NODISCARD T pop_back_val()
LLVM Value Representation.
bool isConditional() const
BasicBlock * getSuccessor(unsigned i) const
A Use represents the edge between a Value definition and its users.