25 "dom-tree-reachability-max-bbs-to-explore",
cl::Hidden,
26 cl::desc(
"Max number of BBs to explore for reachability analysis"),
35 SmallVectorImpl<std::pair<const BasicBlock*,const BasicBlock*> > &Result) {
48 std::pair<const BasicBlock *, const_succ_iterator> &Top = VisitStack.
back();
52 bool FoundNew =
false;
55 if (Visited.
insert(BB).second) {
60 if (InStack.
count(BB))
61 Result.push_back(std::make_pair(ParentBB, BB));
72 }
while (!VisitStack.
empty());
83 unsigned e = Term->getNumSuccessors();
85 for (
unsigned i = 0; ; ++i) {
86 assert(i != e &&
"Didn't find edge?");
87 if (Term->getSuccessor(i) == Succ)
96 bool AllowIdenticalEdges) {
97 assert(SuccNum < TI->getNumSuccessors() &&
"Illegal edge specification!");
102 bool AllowIdenticalEdges) {
107 "No edge between TI's block and Dest.");
112 assert(
I !=
E &&
"No preds, but we have an edge to the block?");
115 if (!AllowIdenticalEdges)
130 return L ? L->getOutermostLoop() :
nullptr;
144 if (ExclusionSet && !ExclusionSet->
empty())
151 if (LI && ExclusionSet) {
152 for (
auto *BB : *ExclusionSet) {
164 if (!Visited.
insert(BB).second)
168 if (ExclusionSet && ExclusionSet->
count(BB))
173 const Loop *Outer =
nullptr;
180 if (LoopsWithHoles.
count(Outer))
182 if (StopLoop && Outer == StopLoop)
196 Outer->getExitBlocks(Worklist);
200 }
while (!Worklist.
empty());
211 assert(
A->getParent() ==
B->getParent() &&
212 "This analysis is function-local!");
217 if (!ExclusionSet || ExclusionSet->
empty()) {
235 assert(
A->getParent()->getParent() ==
B->getParent()->getParent() &&
236 "This analysis is function-local!");
238 if (
A->getParent() ==
B->getParent()) {
252 if (
A ==
B ||
A->comesBefore(
B))
263 if (Worklist.
empty()) {
269 ExclusionSet, DT, LI);
273 A->getParent(),
B->getParent(), ExclusionSet, DT, LI);
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
static cl::opt< unsigned > DefaultMaxBBsToExplore("dom-tree-reachability-max-bbs-to-explore", cl::Hidden, cl::desc("Max number of BBs to explore for reachability analysis"), cl::init(32))
static const Loop * getOutermostLoop(const LoopInfo *LI, const BasicBlock *BB)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
LLVM Basic Block Representation.
bool isEntryBlock() const
Return true if this is the entry block of the containing function.
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...
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
unsigned getNumSuccessors() const LLVM_READONLY
Return the number of successors that this instruction has.
const BasicBlock * getParent() const
BasicBlock * getSuccessor(unsigned Idx) const LLVM_READONLY
Return the specified successor. This instruction must be a terminator.
bool isTerminator() const
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
Represents a single loop in the control flow graph.
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
bool erase(PtrType Ptr)
erase - If the set contains the specified pointer, remove it and return true, otherwise return false.
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
void append(ItTy in_start, ItTy in_end)
Add the specified range to the end of the SmallVector.
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
initializer< Ty > init(const Ty &Val)
This is an optimization pass for GlobalISel generic memory operations.
Interval::succ_iterator succ_end(Interval *I)
bool succ_empty(const Instruction *I)
unsigned GetSuccessorNumber(const BasicBlock *BB, const BasicBlock *Succ)
Search for the specified successor of basic block BB and return its position in the terminator instru...
bool isPotentiallyReachableFromMany(SmallVectorImpl< BasicBlock * > &Worklist, const BasicBlock *StopBB, const SmallPtrSetImpl< BasicBlock * > *ExclusionSet, const DominatorTree *DT=nullptr, const LoopInfo *LI=nullptr)
Determine whether there is at least one path from a block in 'Worklist' to 'StopBB' without passing t...
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...
Interval::pred_iterator pred_end(Interval *I)
Interval::pred_iterator pred_begin(Interval *I)
pred_begin/pred_end - define methods so that Intervals may be used just like BasicBlocks can with the...
bool isCriticalEdge(const Instruction *TI, unsigned SuccNum, bool AllowIdenticalEdges=false)
Return true if the specified edge is a critical edge.
auto predecessors(const MachineBasicBlock *BB)
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
void FindFunctionBackedges(const Function &F, SmallVectorImpl< std::pair< const BasicBlock *, const BasicBlock * > > &Result)
Analyze the specified function to find all of the loop backedges in the function and return them.
bool isPotentiallyReachable(const Instruction *From, const Instruction *To, const SmallPtrSetImpl< BasicBlock * > *ExclusionSet=nullptr, const DominatorTree *DT=nullptr, const LoopInfo *LI=nullptr)
Determine whether instruction 'To' is reachable from 'From', without passing through any blocks in Ex...