23#ifndef LLVM_SUPPORT_GENERICITERATEDDOMINANCEFRONTIER_H
24#define LLVM_SUPPORT_GENERICITERATEDDOMINANCEFRONTIER_H
33namespace IDFCalculatorDetail {
59 std::conditional_t<IsPostDom, Inverse<NodeTy *>, NodeTy *>;
67 : DT(DT), ChildrenGetter(
C) {}
91 LiveInBlocks =
nullptr;
106 bool useLiveIn =
false;
115namespace IDFCalculatorDetail {
117template <
class NodeTy,
bool IsPostDom>
120 using OrderedNodeTy =
123 auto Children = children<OrderedNodeTy>(
N);
124 return {Children.begin(), Children.end()};
129template <
class NodeTy,
bool IsPostDom>
136 using DomTreeNodePair =
137 std::pair<DomTreeNodeBase<NodeTy> *, std::pair<unsigned, unsigned>>;
138 using IDFPriorityQueue =
139 std::priority_queue<DomTreeNodePair, SmallVector<DomTreeNodePair, 32>,
144 DT.updateDFSNumbers();
150 for (NodeTy *BB : *DefBlocks)
152 PQ.push({
Node, std::make_pair(
Node->getLevel(),
Node->getDFSNumIn())});
156 while (!PQ.empty()) {
157 DomTreeNodePair RootPair = PQ.top();
160 unsigned RootLevel = RootPair.second.first;
170 while (!Worklist.
empty()) {
172 NodeTy *BB =
Node->getBlock();
175 auto DoWork = [&](NodeTy *Succ) {
178 const unsigned SuccLevel = SuccNode->
getLevel();
179 if (SuccLevel > RootLevel)
182 if (!VisitedPQ.
insert(SuccNode).second)
185 NodeTy *SuccBB = SuccNode->
getBlock();
186 if (useLiveIn && !LiveInBlocks->count(SuccBB))
190 if (!DefBlocks->count(SuccBB))
191 PQ.push(std::make_pair(
192 SuccNode, std::make_pair(SuccLevel, SuccNode->
getDFSNumIn())));
195 for (
auto *Succ : ChildrenGetter.get(BB))
198 for (
auto DomChild : *
Node) {
199 if (VisitedWorklist.
insert(DomChild).second)
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:...