Go to the documentation of this file.
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;
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)
144 if (ExclusionSet && !ExclusionSet->
empty())
151 if (LI && ExclusionSet) {
152 for (
auto *
BB : *ExclusionSet) {
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()) {
226 Worklist.push_back(
const_cast<BasicBlock*
>(A));
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))
257 if (
BB->isEntryBlock())
263 if (Worklist.empty()) {
269 ExclusionSet, DT, LI);
273 A->getParent(),
B->getParent(), ExclusionSet, DT, LI);
bool isTerminator() const
unsigned getNumSuccessors() const LLVM_READONLY
Return the number of successors that this instruction has.
This is an optimization pass for GlobalISel generic memory operations.
bool erase(PtrType Ptr)
erase - If the set contains the specified pointer, remove it and return true, otherwise return false.
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.
const LoopT * getOutermostLoop() const
Get the outermost loop in which this loop is contained.
Interval::succ_iterator succ_end(Interval *I)
Represents a single loop in the control flow graph.
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))
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
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...
static const Loop * getOutermostLoop(const LoopInfo *LI, const BasicBlock *BB)
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
bool isCriticalEdge(const Instruction *TI, unsigned SuccNum, bool AllowIdenticalEdges=false)
Return true if the specified edge is a critical edge.
bool succ_empty(const Instruction *I)
LLVM Basic Block Representation.
bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
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...
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
void append(ItTy in_start, ItTy in_end)
Add the specified range to the end of the SmallVector.
auto predecessors(const MachineBasicBlock *BB)
BasicBlock * getSuccessor(unsigned Idx) const LLVM_READONLY
Return the specified successor. This instruction must be a terminator.
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
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)
bool is_contained(R &&Range, const E &Element)
Wrapper function around std::find to detect if an element exists in a container.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
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...
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...
const BasicBlock * getParent() const
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
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
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.