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;
193 PrintDomTree<NodeT>(*
I, O, Lev + 1);
196namespace DomTreeBuilder {
198template <
typename DomTreeT>
201template <
typename DomTreeT>
203 ArrayRef<typename DomTreeT::UpdateType> Updates);
205template <
typename DomTreeT>
207 typename DomTreeT::NodePtr To);
209template <
typename DomTreeT>
211 typename DomTreeT::NodePtr To);
213template <
typename DomTreeT>
215 GraphDiff<
typename DomTreeT::NodePtr,
216 DomTreeT::IsPostDominator> &PreViewCFG,
217 GraphDiff<
typename DomTreeT::NodePtr,
218 DomTreeT::IsPostDominator> *PostViewCFG);
220template <
typename DomTreeT>
221bool Verify(
const DomTreeT &DT,
typename DomTreeT::VerificationLevel VL);
229 using ParentPtr =
decltype(std::declval<NodePtr>()->getParent());
230 static_assert(std::is_pointer_v<ParentPtr>,
231 "Currently NodeT's parent must be a pointer type");
242template <
typename NodeT,
bool IsPostDom>
245 static_assert(std::is_pointer_v<typename GraphTraits<NodeT *>::NodeRef>,
246 "Currently DominatorTreeBase supports only pointer nodes");
251 static_assert(std::is_pointer_v<ParentPtr>,
252 "Currently NodeT's parent must be a pointer type");
349 OtherDomTreeNodes.
find(BB);
350 if (OI == OtherDomTreeNodes.
end())
370 return I->second.get();
398 while (!WL.
empty()) {
400 Result.push_back(
N->getBlock());
423 "This is not implemented for post dominators");
446 if (
B->getIDom() ==
A)
return true;
448 if (
A->getIDom() ==
B)
return false;
451 if (
A->getLevel() >=
B->getLevel())
return false;
455#ifdef EXPENSIVE_CHECKS
457 (dominatedBySlowTreeWalk(
A,
B) ==
B->DominatedBy(
A))) &&
458 "Tree walk disagrees with dfs numbers!");
462 return B->DominatedBy(
A);
469 return B->DominatedBy(
A);
472 return dominatedBySlowTreeWalk(
A,
B);
478 assert(this->Roots.
size() == 1 &&
"Should always have entry node!");
479 return this->Roots[0];
485 assert(
A &&
B &&
"Pointers are not valid");
487 "Two blocks are not in same function");
494 if (
A == &Entry ||
B == &Entry)
500 assert(NodeA &&
"A must be in the tree");
501 assert(NodeB &&
"B must be in the tree");
505 while (NodeA != NodeB) {
515 const NodeT *
B)
const {
519 const_cast<NodeT *
>(
B));
574 if (Updates.
empty()) {
637 assert(
getNode(BB) ==
nullptr &&
"Block already in dominator tree!");
639 assert(IDomNode &&
"Not immediate dominator specified for block!");
650 assert(
getNode(BB) ==
nullptr &&
"Block already in dominator tree!");
652 "Cannot change root of post-dominator tree");
653 DFSInfoValid =
false;
662 OldNode->IDom = NewNode;
663 OldNode->UpdateLevel();
674 assert(
N && NewIDom &&
"Cannot change null node pointers!");
688 assert(
Node &&
"Removing node that isn't in dominator tree.");
689 assert(
Node->isLeaf() &&
"Node is not a leaf node.");
696 const auto I =
find(IDom->Children,
Node);
697 assert(
I != IDom->Children.end() &&
698 "Not in immediate dominator children set!");
700 IDom->Children.erase(
I);
705 if (!IsPostDom)
return;
719 Split<Inverse<NodeT *>>(NewBB);
721 Split<NodeT *>(NewBB);
727 O <<
"=============================--------------------------------\n";
729 O <<
"Inorder PostDominator Tree: ";
731 O <<
"Inorder Dominator Tree: ";
733 O <<
"DFSNumbers invalid: " <<
SlowQueries <<
" slow queries.";
740 Block->printAsOperand(O,
false);
760 assert((!
Parent || ThisRoot) &&
"Empty constructed DomTree");
769 ThisRoot->DFSNumIn = DFSNum++;
771 while (!WorkStack.
empty()) {
773 const auto ChildIt = WorkStack.
back().second;
777 if (ChildIt ==
Node->end()) {
778 Node->DFSNumOut = DFSNum++;
783 ++WorkStack.
back().second;
786 Child->DFSNumIn = DFSNum++;
852 using NodeRef =
typename GraphT::NodeRef;
853 assert(std::distance(GraphT::child_begin(NewBB),
854 GraphT::child_end(NewBB)) == 1 &&
855 "NewBB should have a single successor!");
856 NodeRef NewBBSucc = *GraphT::child_begin(NewBB);
862 bool NewBBDominatesNewBBSucc =
true;
864 if (Pred != NewBB && !
dominates(NewBBSucc, Pred) &&
866 NewBBDominatesNewBBSucc =
false;
873 NodeT *NewBBIDom =
nullptr;
875 for (i = 0; i < PredBlocks.
size(); ++i)
877 NewBBIDom = PredBlocks[i];
884 if (!NewBBIDom)
return;
886 for (i = i + 1; i < PredBlocks.
size(); ++i) {
896 if (NewBBDominatesNewBBSucc) {
909 const unsigned ALevel =
A->getLevel();
914 while ((IDom =
B->getIDom()) !=
nullptr && IDom->
getLevel() >= ALevel)
939template <
typename NodeT,
bool IsPostDom>
941 const NodeT *
B)
const {
948 return dominates(getNode(
const_cast<NodeT *
>(
A)),
949 getNode(
const_cast<NodeT *
>(
B)));
951template <
typename NodeT,
bool IsPostDom>
953 const NodeT *
A,
const NodeT *
B)
const {
960 return dominates(getNode(
const_cast<NodeT *
>(
A)),
961 getNode(
const_cast<NodeT *
>(
B)));
BlockVerifier::State From
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
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(MachineBasicBlock &MBB, MachineBasicBlock::const_iterator A, MachineBasicBlock::const_iterator 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.
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.
iterator_range< typename GraphTraits< GraphType >::ChildIteratorType > children(const typename GraphTraits< GraphType >::NodeRef &G)
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