24#ifndef LLVM_SUPPORT_GENERICDOMTREE_H
25#define LLVM_SUPPORT_GENERICDOMTREE_H
45template <
typename NodeT,
bool IsPostDom>
46class DominatorTreeBase;
48namespace DomTreeBuilder {
49template <
typename DomTreeT>
65 mutable unsigned DFSNumIn = ~0;
66 mutable unsigned DFSNumOut = ~0;
70 : TheBB(BB), IDom(iDom), Level(IDom ? IDom->Level + 1 : 0) {}
94 std::unique_ptr<DomTreeNodeBase>
C) {
95 Children.push_back(
C.get());
99 bool isLeaf()
const {
return Children.empty(); }
108 if (Level !=
Other->Level)
return true;
112 const NodeT *Nd =
I->getBlock();
117 const NodeT *
N =
I->getBlock();
118 if (OtherChildren.
count(
N) == 0)
125 assert(IDom &&
"No immediate dominator?");
126 if (IDom == NewIDom)
return;
128 auto I =
find(IDom->Children,
this);
129 assert(
I != IDom->Children.end() &&
130 "Not in immediate dominator children set!");
132 IDom->Children.erase(
I);
136 IDom->Children.push_back(
this);
151 return this->DFSNumIn >= other->DFSNumIn &&
152 this->DFSNumOut <= other->DFSNumOut;
157 if (Level == IDom->Level + 1)
return;
159 SmallVector<DomTreeNodeBase *, 64> WorkStack = {
this};
161 while (!WorkStack.empty()) {
163 Current->Level = Current->IDom->Level + 1;
165 for (DomTreeNodeBase *
C : *Current) {
167 if (
C->Level !=
C->IDom->Level + 1) WorkStack.push_back(
C);
173template <
class NodeT>
175 if (
Node->getBlock())
178 O <<
" <<exit node>>";
180 O <<
" {" <<
Node->getDFSNumIn() <<
"," <<
Node->getDFSNumOut() <<
"} ["
181 <<
Node->getLevel() <<
"]\n";
186template <
class NodeT>
189 O.indent(2 * Lev) <<
"[" << Lev <<
"] " <<
N;
190 for (
const auto &
I : *
N)
191 PrintDomTree<NodeT>(
I, O, Lev + 1);
194namespace DomTreeBuilder {
196template <
typename DomTreeT>
199template <
typename DomTreeT>
201 ArrayRef<typename DomTreeT::UpdateType> Updates);
203template <
typename DomTreeT>
205 typename DomTreeT::NodePtr To);
207template <
typename DomTreeT>
209 typename DomTreeT::NodePtr To);
211template <
typename DomTreeT>
213 GraphDiff<
typename DomTreeT::NodePtr,
214 DomTreeT::IsPostDominator> &PreViewCFG,
215 GraphDiff<
typename DomTreeT::NodePtr,
216 DomTreeT::IsPostDominator> *PostViewCFG);
218template <
typename DomTreeT>
219bool Verify(
const DomTreeT &DT,
typename DomTreeT::VerificationLevel VL);
227 using ParentPtr =
decltype(std::declval<NodePtr>()->getParent());
228 static_assert(std::is_pointer_v<ParentPtr>,
229 "Currently NodeT's parent must be a pointer type");
240template <
typename NodeT,
bool IsPostDom>
243 static_assert(std::is_pointer_v<typename GraphTraits<NodeT *>::NodeRef>,
244 "Currently DominatorTreeBase supports only pointer nodes");
249 static_assert(std::is_pointer_v<ParentPtr>,
250 "Currently NodeT's parent must be a pointer type");
347 OtherDomTreeNodes.
find(BB);
348 if (OI == OtherDomTreeNodes.
end())
368 return I->second.get();
396 while (!WL.
empty()) {
398 Result.push_back(
N->getBlock());
421 "This is not implemented for post dominators");
444 if (
B->getIDom() ==
A)
return true;
446 if (
A->getIDom() ==
B)
return false;
449 if (
A->getLevel() >=
B->getLevel())
return false;
453#ifdef EXPENSIVE_CHECKS
455 (dominatedBySlowTreeWalk(
A,
B) ==
B->DominatedBy(
A))) &&
456 "Tree walk disagrees with dfs numbers!");
460 return B->DominatedBy(
A);
467 return B->DominatedBy(
A);
470 return dominatedBySlowTreeWalk(
A,
B);
476 assert(this->Roots.
size() == 1 &&
"Should always have entry node!");
477 return this->Roots[0];
483 assert(
A &&
B &&
"Pointers are not valid");
485 "Two blocks are not in same function");
492 if (
A == &Entry ||
B == &Entry)
498 assert(NodeA &&
"A must be in the tree");
499 assert(NodeB &&
"B must be in the tree");
503 while (NodeA != NodeB) {
513 const NodeT *
B)
const {
517 const_cast<NodeT *
>(
B));
572 if (Updates.
empty()) {
635 assert(
getNode(BB) ==
nullptr &&
"Block already in dominator tree!");
637 assert(IDomNode &&
"Not immediate dominator specified for block!");
648 assert(
getNode(BB) ==
nullptr &&
"Block already in dominator tree!");
650 "Cannot change root of post-dominator tree");
651 DFSInfoValid =
false;
660 OldNode->IDom = NewNode;
661 OldNode->UpdateLevel();
672 assert(
N && NewIDom &&
"Cannot change null node pointers!");
686 assert(
Node &&
"Removing node that isn't in dominator tree.");
687 assert(
Node->isLeaf() &&
"Node is not a leaf node.");
694 const auto I =
find(IDom->Children,
Node);
695 assert(
I != IDom->Children.end() &&
696 "Not in immediate dominator children set!");
698 IDom->Children.erase(
I);
703 if (!IsPostDom)
return;
717 Split<Inverse<NodeT *>>(NewBB);
719 Split<NodeT *>(NewBB);
725 O <<
"=============================--------------------------------\n";
727 O <<
"Inorder PostDominator Tree: ";
729 O <<
"Inorder Dominator Tree: ";
731 O <<
"DFSNumbers invalid: " <<
SlowQueries <<
" slow queries.";
738 Block->printAsOperand(O,
false);
758 assert((!
Parent || ThisRoot) &&
"Empty constructed DomTree");
767 ThisRoot->DFSNumIn = DFSNum++;
769 while (!WorkStack.
empty()) {
771 const auto ChildIt = WorkStack.
back().second;
775 if (ChildIt ==
Node->end()) {
776 Node->DFSNumOut = DFSNum++;
781 ++WorkStack.
back().second;
784 Child->DFSNumIn = DFSNum++;
850 using NodeRef =
typename GraphT::NodeRef;
852 "NewBB should have a single successor!");
853 NodeRef NewBBSucc = *GraphT::child_begin(NewBB);
859 bool NewBBDominatesNewBBSucc =
true;
860 for (
auto *Pred : inverse_children<N>(NewBBSucc)) {
861 if (Pred != NewBB && !
dominates(NewBBSucc, Pred) &&
863 NewBBDominatesNewBBSucc =
false;
870 NodeT *NewBBIDom =
nullptr;
872 for (i = 0; i < PredBlocks.
size(); ++i)
874 NewBBIDom = PredBlocks[i];
881 if (!NewBBIDom)
return;
883 for (i = i + 1; i < PredBlocks.
size(); ++i) {
893 if (NewBBDominatesNewBBSucc) {
906 const unsigned ALevel =
A->getLevel();
911 while ((IDom =
B->getIDom()) !=
nullptr && IDom->
getLevel() >= ALevel)
936template <
typename NodeT,
bool IsPostDom>
938 const NodeT *
B)
const {
948template <
typename NodeT,
bool IsPostDom>
950 const NodeT *
A,
const NodeT *
B)
const {
static msgpack::DocNode getNode(msgpack::DocNode DN, msgpack::Type Type, MCValue Val)
BlockVerifier::State From
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
This file defines the DenseMap class.
This file defines the little GraphTraits<X> template class that should be specialized by classes that...
ppc ctr loops PowerPC CTR Loops Verify
static bool dominates(InstrPosIndexes &PosIndexes, const MachineInstr &A, const MachineInstr &B)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
void printAsOperand(OutputBuffer &OB, Prec P=Prec::Default, bool StrictlyWorse=false) const
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
bool empty() const
empty - Check if the array is empty.
iterator find(const_arg_type_t< KeyT > Val)
bool erase(const KeyT &Val)
Base class for the actual dominator tree node.
iterator_range< iterator > children()
const_iterator end() const
DomTreeNodeBase *& back()
void setIDom(DomTreeNodeBase *NewIDom)
typename SmallVector< DomTreeNodeBase *, 4 >::iterator iterator
DomTreeNodeBase *const & back() const
DomTreeNodeBase * getIDom() const
unsigned getDFSNumIn() const
getDFSNumIn/getDFSNumOut - These return the DFS visitation order for nodes in the dominator tree.
size_t getNumChildren() const
DomTreeNodeBase(NodeT *BB, DomTreeNodeBase *iDom)
bool compare(const DomTreeNodeBase *Other) const
unsigned getLevel() const
std::unique_ptr< DomTreeNodeBase > addChild(std::unique_ptr< DomTreeNodeBase > C)
iterator_range< const_iterator > children() const
unsigned getDFSNumOut() const
typename SmallVector< DomTreeNodeBase *, 4 >::const_iterator const_iterator
const_iterator begin() const
Core dominator tree base class.
bool isReachableFromEntry(const DomTreeNodeBase< NodeT > *A) const
void print(raw_ostream &O) const
print - Convert to human readable form
typename NodeTrait::NodeType NodeType
DomTreeNodeBase< NodeT > * operator[](const NodeT *BB) const
See getNode.
typename SmallVectorImpl< NodeT * >::iterator root_iterator
Iteration over roots.
DomTreeNodeBase< NodeT > * getRootNode()
getRootNode - This returns the entry node for the CFG of the function.
bool verify(VerificationLevel VL=VerificationLevel::Full) const
verify - checks if the tree is correct.
void changeImmediateDominator(NodeT *BB, NodeT *NewBB)
NodeT * findNearestCommonDominator(NodeT *A, NodeT *B) const
Find nearest common dominator basic block for basic block A and B.
DominatorTreeBase()=default
void Split(typename GraphTraits< N >::NodeRef NewBB)
iterator_range< root_iterator > roots()
void changeImmediateDominator(DomTreeNodeBase< NodeT > *N, DomTreeNodeBase< NodeT > *NewIDom)
changeImmediateDominator - This method is used to update the dominator tree information when a node's...
std::remove_pointer_t< ParentPtr > ParentType
DominatorTreeBase(DominatorTreeBase &&Arg)
bool isPostDominator() const
isPostDominator - Returns true if analysis based of postdoms
const NodeT * findNearestCommonDominator(const NodeT *A, const NodeT *B) const
void getDescendants(NodeT *R, SmallVectorImpl< NodeT * > &Result) const
Get all nodes dominated by R, including R itself.
DomTreeNodeBase< NodeT > * addNewBlock(NodeT *BB, NodeT *DomBB)
Add a new node to the dominator tree information.
void applyUpdates(ArrayRef< UpdateType > Updates)
Inform the dominator tree about a sequence of CFG edge insertions and deletions and perform a batch u...
void insertEdge(NodeT *From, NodeT *To)
Inform the dominator tree about a CFG edge insertion and update the tree.
bool dominates(const DomTreeNodeBase< NodeT > *A, const DomTreeNodeBase< NodeT > *B) const
dominates - Returns true iff A dominates B.
iterator_range< const_root_iterator > roots() const
const_root_iterator root_end() const
void splitBlock(NodeT *NewBB)
splitBlock - BB is split and now it has one successor.
DomTreeNodeBase< NodeT > * createNode(NodeT *BB)
DominatorTreeBase & operator=(DominatorTreeBase &&RHS)
static constexpr UpdateKind Delete
void recalculate(ParentType &Func, ArrayRef< UpdateType > Updates)
void updateDFSNumbers() const
updateDFSNumbers - Assign In and Out numbers to the nodes while walking dominator tree in dfs order.
typename SmallVectorImpl< NodeT * >::const_iterator const_root_iterator
bool compare(const DominatorTreeBase &Other) const
compare - Return false if the other dominator tree base matches this dominator tree base.
DomTreeNodeBase< NodeT > * setNewRoot(NodeT *BB)
Add a new node to the forward dominator tree and make it a new root.
root_iterator root_begin()
DominatorTreeBase(const DominatorTreeBase &)=delete
DomTreeNodeMapType DomTreeNodes
static constexpr UpdateKind Insert
const_root_iterator root_begin() const
void recalculate(ParentType &Func)
recalculate - compute a dominator tree for the given function
SmallVector< NodeT *, IsPostDom ? 4 :1 > Roots
void eraseNode(NodeT *BB)
eraseNode - Removes a node from the dominator tree.
void deleteEdge(NodeT *From, NodeT *To)
Inform the dominator tree about a CFG edge deletion and update the tree.
const DomTreeNodeBase< NodeT > * getRootNode() const
DomTreeNodeBase< NodeT > * RootNode
typename NodeTrait::NodePtr NodePtr
bool isReachableFromEntry(const NodeT *A) const
isReachableFromEntry - Return true if A is dominated by the entry block of the function containing it...
void applyUpdates(ArrayRef< UpdateType > Updates, ArrayRef< UpdateType > PostViewUpdates)
DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
bool properlyDominates(const NodeT *A, const NodeT *B) const
bool properlyDominates(const DomTreeNodeBase< NodeT > *A, const DomTreeNodeBase< NodeT > *B) const
properlyDominates - Returns true iff A dominates B and A != B.
bool isVirtualRoot(const DomTreeNodeBase< NodeT > *A) const
typename NodeTrait::ParentPtr ParentPtr
DominatorTreeBase & operator=(const DominatorTreeBase &)=delete
DomTreeNodeBase< NodeT > * createChild(NodeT *BB, DomTreeNodeBase< NodeT > *IDom)
static constexpr bool IsPostDominator
PostDominatorTree Class - Concrete subclass of DominatorTree that is used to compute the post-dominat...
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 consists of common code factored out of the SmallVector class to reduce code duplication b...
typename SuperClass::const_iterator const_iterator
void append(ItTy in_start, ItTy in_end)
Add the specified range to the end of the SmallVector.
typename SuperClass::iterator iterator
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
A range adaptor for a pair of iterators.
This class implements an extremely fast bulk output stream that can only output to a stream.
@ C
The default llvm calling convention, compatible with C.
bool Verify(const DomTreeT &DT, typename DomTreeT::VerificationLevel VL)
void CalculateWithUpdates(DomTreeT &DT, ArrayRef< typename DomTreeT::UpdateType > Updates)
void DeleteEdge(DomTreeT &DT, typename DomTreeT::NodePtr From, typename DomTreeT::NodePtr To)
void Calculate(DomTreeT &DT)
void ApplyUpdates(DomTreeT &DT, GraphDiff< typename DomTreeT::NodePtr, DomTreeT::IsPostDominator > &PreViewCFG, GraphDiff< typename DomTreeT::NodePtr, DomTreeT::IsPostDominator > *PostViewCFG)
void InsertEdge(DomTreeT &DT, typename DomTreeT::NodePtr From, typename DomTreeT::NodePtr To)
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.
void PrintDomTree(const DomTreeNodeBase< NodeT > *N, raw_ostream &O, unsigned Lev)
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
void append_range(Container &C, Range &&R)
Wrapper function to append range R to container C.
bool hasSingleElement(ContainerTy &&C)
Returns true if the given container only contains a single element.
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
Implement std::hash so that hash_code can be used in STL containers.
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Default DomTreeNode traits for NodeT.
static NodeT * getEntryNode(ParentPtr Parent)
std::remove_pointer_t< ParentPtr > ParentType
static ParentPtr getParent(NodePtr BB)
decltype(std::declval< NodePtr >() ->getParent()) ParentPtr
typename GraphType::UnknownGraphTypeError NodeRef