Go to the documentation of this file.
23 #ifndef LLVM_SUPPORT_GENERICITERATEDDOMINANCEFRONTIER_H
24 #define LLVM_SUPPORT_GENERICITERATEDDOMINANCEFRONTIER_H
34 namespace IDFCalculatorDetail {
60 std::conditional_t<IsPostDom, Inverse<NodeTy *>, NodeTy *>;
68 : DT(DT), ChildrenGetter(
C) {}
85 LiveInBlocks = &Blocks;
92 LiveInBlocks =
nullptr;
107 bool useLiveIn =
false;
116 namespace IDFCalculatorDetail {
118 template <
class NodeTy,
bool IsPostDom>
121 using OrderedNodeTy =
124 auto Children = children<OrderedNodeTy>(
N);
125 return {Children.begin(), Children.end()};
130 template <
class NodeTy,
bool IsPostDom>
137 using DomTreeNodePair =
138 std::pair<DomTreeNodeBase<NodeTy> *, std::pair<unsigned, unsigned>>;
139 using IDFPriorityQueue =
140 std::priority_queue<DomTreeNodePair, SmallVector<DomTreeNodePair, 32>,
145 DT.updateDFSNumbers();
151 for (NodeTy *
BB : *DefBlocks)
153 PQ.push({
Node, std::make_pair(
Node->getLevel(),
Node->getDFSNumIn())});
157 while (!PQ.empty()) {
158 DomTreeNodePair RootPair = PQ.top();
161 unsigned RootLevel = RootPair.second.first;
169 Worklist.push_back(Root);
171 while (!Worklist.empty()) {
173 NodeTy *
BB =
Node->getBlock();
176 auto DoWork = [&](NodeTy *Succ) {
179 const unsigned SuccLevel = SuccNode->
getLevel();
180 if (SuccLevel > RootLevel)
183 if (!VisitedPQ.
insert(SuccNode).second)
186 NodeTy *SuccBB = SuccNode->
getBlock();
187 if (useLiveIn && !LiveInBlocks->count(SuccBB))
191 if (!DefBlocks->count(SuccBB))
192 PQ.push(std::make_pair(
193 SuccNode, std::make_pair(SuccLevel, SuccNode->
getDFSNumIn())));
196 for (
auto Succ : ChildrenGetter.get(
BB))
199 for (
auto DomChild : *
Node) {
200 if (VisitedWorklist.
insert(DomChild).second)
201 Worklist.push_back(DomChild);
Function object to check whether the second component of a std::pair compares less than the second co...
This is an optimization pass for GlobalISel generic memory operations.
void setLiveInBlocks(const SmallPtrSetImpl< NodeTy * > &Blocks)
Give the IDF calculator the set of blocks in which the value is live on entry to the block.
ChildrenTy get(const NodeRef &N)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
typename GraphTraits< NodeTy * >::NodeRef NodeRef
LLVM_NODISCARD T pop_back_val()
void calculate(SmallVectorImpl< NodeTy * > &IDFBlocks)
Calculate iterated dominance frontiers.
IDFCalculatorBase(DominatorTreeBase< NodeTy, IsPostDom > &DT)
unsigned getDFSNumIn() const
getDFSNumIn/getDFSNumOut - These return the DFS visitation order for nodes in the dominator tree.
std::conditional_t< IsPostDom, Inverse< NodeTy * >, NodeTy * > OrderedNodeTy
void resetLiveInBlocks()
Reset the live-in block set to be empty, and tell the IDF calculator to not use liveness anymore.
(vector float) vec_cmpeq(*A, *B) C
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
void setDefiningBlocks(const SmallPtrSetImpl< NodeTy * > &Blocks)
Give the IDF calculator the set of blocks in which the value is defined.
SmallVector< NodeRef, 8 > ChildrenTy
IDFCalculatorBase(DominatorTreeBase< NodeTy, IsPostDom > &DT, const ChildrenGetterTy &C)
unsigned getLevel() const
Generic utility class used for getting the children of a basic block.
Determine the iterated dominance frontier, given a set of defining blocks, and optionally,...
IDFCalculatorDetail::ChildrenGetterTy< NodeTy, IsPostDom > ChildrenGetterTy
Specialization for BasicBlock for the optional use of GraphDiff.
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
typename GraphType::UnknownGraphTypeError NodeRef
reference emplace_back(ArgTypes &&... Args)
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.