23#ifndef LLVM_SUPPORT_GENERICITERATEDDOMINANCEFRONTIER_H
24#define LLVM_SUPPORT_GENERICITERATEDDOMINANCEFRONTIER_H
34namespace IDFCalculatorDetail {
60 std::conditional_t<IsPostDom, Inverse<NodeTy *>, NodeTy *>;
68 : DT(DT), ChildrenGetter(
C) {}
92 LiveInBlocks =
nullptr;
107 bool useLiveIn =
false;
116namespace IDFCalculatorDetail {
118template <
class NodeTy,
bool IsPostDom>
121 using OrderedNodeTy =
124 auto Children = children<OrderedNodeTy>(
N);
125 return {Children.begin(), Children.end()};
130template <
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;
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)
This file defines the DenseMap class.
DenseMap< Block *, BlockRelaxAux > Blocks
This file defines a set of templates that efficiently compute a dominator tree over a generic graph.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
Base class for the actual dominator tree node.
unsigned getDFSNumIn() const
getDFSNumIn/getDFSNumOut - These return the DFS visitation order for nodes in the dominator tree.
unsigned getLevel() const
Core dominator tree base class.
Determine the iterated dominance frontier, given a set of defining blocks, and optionally,...
IDFCalculatorBase(DominatorTreeBase< NodeTy, IsPostDom > &DT)
void resetLiveInBlocks()
Reset the live-in block set to be empty, and tell the IDF calculator to not use liveness anymore.
void calculate(SmallVectorImpl< NodeTy * > &IDFBlocks)
Calculate iterated dominance frontiers.
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.
void setDefiningBlocks(const SmallPtrSetImpl< NodeTy * > &Blocks)
Give the IDF calculator the set of blocks in which the value is defined.
IDFCalculatorBase(DominatorTreeBase< NodeTy, IsPostDom > &DT, const ChildrenGetterTy &C)
std::conditional_t< IsPostDom, Inverse< NodeTy * >, NodeTy * > OrderedNodeTy
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
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...
reference emplace_back(ArgTypes &&... Args)
void push_back(const T &Elt)
@ C
The default llvm calling convention, compatible with C.
This is an optimization pass for GlobalISel generic memory operations.
typename GraphType::UnknownGraphTypeError NodeRef
Specialization for BasicBlock for the optional use of GraphDiff.
Generic utility class used for getting the children of a basic block.
typename GraphTraits< NodeTy * >::NodeRef NodeRef
ChildrenTy get(const NodeRef &N)
SmallVector< NodeRef, 8 > ChildrenTy
Function object to check whether the second component of a container supported by std::get (like std:...