17#ifndef LLVM_ANALYSIS_DOMINANCEFRONTIERIMPL_H
18#define LLVM_ANALYSIS_DOMINANCEFRONTIERIMPL_H
22#include "llvm/Config/llvm-config.h"
33template <
class BlockT>
48template <
class BlockT,
bool IsPostDom>
50 assert(
find(BB) != end() &&
"Block is not in DominanceFrontier!");
56template <
class BlockT,
bool IsPostDom>
59 assert(
I != end() &&
"BB is not in DominanceFrontier!");
60 assert(
I->second.count(
Node) &&
"Node is not in DominanceFrontier of BB");
61 I->second.erase(
Node);
64template <
class BlockT,
bool IsPostDom>
67 assert(
I != end() &&
"BB is not in DominanceFrontier!");
68 assert(
I->second.count(
Node) &&
"Node is not in DominanceFrontier of BB");
69 I->second.erase(
Node);
72template <
class BlockT,
bool IsPostDom>
75 std::set<BlockT *> tmpSet;
76 for (BlockT *BB : DS2)
79 for (
typename DomSetType::const_iterator
I = DS1.begin(),
E = DS1.end();
83 if (tmpSet.erase(
Node) == 0)
88 if (!tmpSet.empty()) {
97template <
class BlockT,
bool IsPostDom>
101 for (
typename DomSetMapType::const_iterator
I =
Other.begin(),
104 tmpFrontiers.insert(std::make_pair(
I->first,
I->second));
106 for (
typename DomSetMapType::iterator
I = tmpFrontiers.begin(),
107 E = tmpFrontiers.end();
109 BlockT *
Node =
I->first;
114 if (compareDomSet(
I->second, DFI->second))
118 tmpFrontiers.erase(
Node);
121 if (!tmpFrontiers.empty())
127template <
class BlockT,
bool IsPostDom>
130 OS <<
" DomFrontier for BB ";
132 I->first->printAsOperand(
OS,
false);
134 OS <<
" <<exit node>>";
137 const std::set<BlockT *> &BBs =
I->second;
139 for (
const BlockT *BB : BBs) {
142 BB->printAsOperand(
OS,
false);
144 OS <<
"<<exit node>>";
150#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
151template <
class BlockT,
bool IsPostDom>
157template <
class BlockT>
161 BlockT *BB =
Node->getBlock();
164 std::vector<DFCalculateWorkObject<BlockT>> workList;
170 assert(currentW &&
"Missing work object.");
173 BlockT *parentBB = currentW->
parentBB;
176 assert(currentBB &&
"Invalid work object. Missing current Basic Block");
177 assert(currentNode &&
"Invalid work object. Missing current Node");
181 if (visited.
insert(currentBB).second) {
183 for (
const auto Succ : children<BlockT *>(currentBB)) {
185 if (DT[Succ]->getIDom() != currentNode)
193 bool visitChild =
false;
195 NE = currentNode->
end();
198 BlockT *childBB = IDominee->
getBlock();
199 if (visited.
count(childBB) == 0) {
201 childBB, currentBB, IDominee, currentNode));
214 typename DomSetType::const_iterator CDFI = S.begin(), CDFE = S.end();
215 DomSetType &parentSet = this->Frontiers[parentBB];
216 for (; CDFI != CDFE; ++CDFI) {
218 parentSet.insert(*CDFI);
223 }
while (!workList.empty());
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
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.
DFCalculateWorkObject(BlockT *B, BlockT *P, const DomTreeNodeT *N, const DomTreeNodeT *PN)
const DomTreeNodeT * parentNode
const DomTreeNodeT * Node
Base class for the actual dominator tree node.
typename SmallVector< DomTreeNodeBase *, 4 >::const_iterator const_iterator
DominanceFrontierBase - Common base class for computing forward and inverse dominance frontiers for a...
bool compare(DominanceFrontierBase &Other) const
compare - Return true if the other dominance frontier base matches this dominance frontier base.
void print(raw_ostream &OS) const
print - Convert to human readable form
typename DomSetMapType::iterator iterator
bool compareDomSet(DomSetType &DS1, const DomSetType &DS2) const
compareDomSet - Return false if two domsets match.
std::set< BlockT * > DomSetType
void removeFromFrontier(iterator I, BlockT *Node)
void dump() const
dump - Dump the dominance frontier to dbgs().
std::map< BasicBlock *, DomSetType > DomSetMapType
typename DomSetMapType::const_iterator const_iterator
void addToFrontier(iterator I, BlockT *Node)
void removeBlock(BlockT *BB)
removeBlock - Remove basic block BB's frontier.
Core dominator tree base class.
bool properlyDominates(const DomTreeNodeBase< NodeT > *A, const DomTreeNodeBase< NodeT > *B) const
properlyDominates - Returns true iff A dominates B and A != B.
const DomSetType & calculate(const DomTreeT &DT, const DomTreeNodeT *Node)
typename DominanceFrontierBase< BlockT, false >::DomSetType DomSetType
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 implements an extremely fast bulk output stream that can only output to a stream.
This is an optimization pass for GlobalISel generic memory operations.
auto find(R &&Range, const T &Val)
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly.
Printable print(const GCNRegPressure &RP, const GCNSubtarget *ST=nullptr)
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.