///
//===----------------------------------------------------------------------===//
-#ifndef LLVM_SUPPORT_GENERIC_DOM_TREE_H
-#define LLVM_SUPPORT_GENERIC_DOM_TREE_H
+#ifndef LLVM_SUPPORT_GENERICDOMTREE_H
+#define LLVM_SUPPORT_GENERICDOMTREE_H
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/DepthFirstIterator.h"
#include "llvm/ADT/GraphTraits.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
-#include "llvm/Support/CFG.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/raw_ostream.h"
#include <algorithm>
NodeT *TheBB;
DomTreeNodeBase<NodeT> *IDom;
std::vector<DomTreeNodeBase<NodeT> *> Children;
- int DFSNumIn, DFSNumOut;
+ mutable int DFSNumIn, DFSNumOut;
template<class N> friend class DominatorTreeBase;
friend struct PostDominatorTree;
assert(isReachableFromEntry(A));
const DomTreeNodeBase<NodeT> *IDom;
- while ((IDom = B->getIDom()) != 0 && IDom != A && IDom != B)
+ while ((IDom = B->getIDom()) != nullptr && IDom != A && IDom != B)
B = IDom; // Walk up the tree
- return IDom != 0;
+ return IDom != nullptr;
}
protected:
DomTreeNodeMapType DomTreeNodes;
DomTreeNodeBase<NodeT> *RootNode;
- bool DFSInfoValid;
- unsigned int SlowQueries;
+ mutable bool DFSInfoValid;
+ mutable unsigned int SlowQueries;
// Information record used during immediate dominators computation.
struct InfoRec {
unsigned DFSNum;
unsigned Semi;
NodeT *Label;
- InfoRec() : DFSNum(0), Parent(0), Semi(0), Label(0) {}
+ InfoRec() : DFSNum(0), Parent(0), Semi(0), Label(nullptr) {}
};
DenseMap<NodeT*, NodeT*> IDoms;
IDoms.clear();
this->Roots.clear();
Vertex.clear();
- RootNode = 0;
+ RootNode = nullptr;
}
// NewBB is split and now it has one successor. Update dominator tree to
// Find NewBB's immediate dominator and create new dominator tree node for
// NewBB.
- NodeT *NewBBIDom = 0;
+ NodeT *NewBBIDom = nullptr;
unsigned i = 0;
for (i = 0; i < PredBlocks.size(); ++i)
if (DT.isReachableFromEntry(PredBlocks[i])) {
/// compare - Return false if the other dominator tree base matches this
/// dominator tree base. Otherwise return true.
- bool compare(DominatorTreeBase &Other) const {
+ bool compare(const DominatorTreeBase &Other) const {
const DomTreeNodeMapType &OtherDomTreeNodes = Other.DomTreeNodes;
if (DomTreeNodes.size() != OtherDomTreeNodes.size())
return DomTreeNodes.lookup(BB);
}
+ inline DomTreeNodeBase<NodeT> *operator[](NodeT *BB) const {
+ return getNode(BB);
+ }
+
/// getRootNode - This returns the entry node for the CFG of the function. If
/// this tree represents the post-dominance relations for a function, however,
/// this root may be a node with the block == NULL. This is the case when
void getDescendants(NodeT *R, SmallVectorImpl<NodeT *> &Result) const {
Result.clear();
const DomTreeNodeBase<NodeT> *RN = getNode(R);
- if (RN == NULL)
+ if (!RN)
return; // If R is unreachable, it will not be present in the DOM tree.
SmallVector<const DomTreeNodeBase<NodeT> *, 8> WL;
WL.push_back(RN);
/// Note that this is not a constant time operation!
///
bool properlyDominates(const DomTreeNodeBase<NodeT> *A,
- const DomTreeNodeBase<NodeT> *B) {
- if (A == 0 || B == 0)
+ const DomTreeNodeBase<NodeT> *B) const {
+ if (!A || !B)
return false;
if (A == B)
return false;
return dominates(A, B);
}
- bool properlyDominates(const NodeT *A, const NodeT *B);
+ bool properlyDominates(const NodeT *A, const NodeT *B) const;
/// isReachableFromEntry - Return true if A is dominated by the entry
/// block of the function containing it.
/// constant time operation!
///
inline bool dominates(const DomTreeNodeBase<NodeT> *A,
- const DomTreeNodeBase<NodeT> *B) {
+ const DomTreeNodeBase<NodeT> *B) const {
// A node trivially dominates itself.
if (B == A)
return true;
return dominatedBySlowTreeWalk(A, B);
}
- bool dominates(const NodeT *A, const NodeT *B);
+ bool dominates(const NodeT *A, const NodeT *B) const;
NodeT *getRoot() const {
assert(this->Roots.size() == 1 && "Should always have entry node!");
DomTreeNodeBase<NodeT> *NodeA = getNode(A);
DomTreeNodeBase<NodeT> *NodeB = getNode(B);
+ // If we have DFS info, then we can avoid all allocations by just querying
+ // it from each IDom. Note that because we call 'dominates' twice above, we
+ // expect to call through this code at most 16 times in a row without
+ // building valid DFS information. This is important as below is a *very*
+ // slow tree walk.
+ if (DFSInfoValid) {
+ DomTreeNodeBase<NodeT> *IDomA = NodeA->getIDom();
+ while (IDomA) {
+ if (NodeB->DominatedBy(IDomA))
+ return IDomA->getBlock();
+ IDomA = IDomA->getIDom();
+ }
+ return nullptr;
+ }
+
// Collect NodeA dominators set.
SmallPtrSet<DomTreeNodeBase<NodeT>*, 16> NodeADoms;
NodeADoms.insert(NodeA);
IDomB = IDomB->getIDom();
}
- return NULL;
+ return nullptr;
}
const NodeT *findNearestCommonDominator(const NodeT *A, const NodeT *B) {
/// creates a new node as a child of DomBB dominator node,linking it into
/// the children list of the immediate dominator.
DomTreeNodeBase<NodeT> *addNewBlock(NodeT *BB, NodeT *DomBB) {
- assert(getNode(BB) == 0 && "Block already in dominator tree!");
+ assert(getNode(BB) == nullptr && "Block already in dominator tree!");
DomTreeNodeBase<NodeT> *IDomNode = getNode(DomBB);
assert(IDomNode && "Not immediate dominator specified for block!");
DFSInfoValid = false;
/// updateDFSNumbers - Assign In and Out numbers to the nodes while walking
/// dominator tree in dfs order.
- void updateDFSNumbers() {
+ void updateDFSNumbers() const {
unsigned DFSNum = 0;
- SmallVector<std::pair<DomTreeNodeBase<NodeT>*,
- typename DomTreeNodeBase<NodeT>::iterator>, 32> WorkStack;
+ SmallVector<std::pair<const DomTreeNodeBase<NodeT>*,
+ typename DomTreeNodeBase<NodeT>::const_iterator>, 32> WorkStack;
- DomTreeNodeBase<NodeT> *ThisRoot = getRootNode();
+ const DomTreeNodeBase<NodeT> *ThisRoot = getRootNode();
if (!ThisRoot)
return;
ThisRoot->DFSNumIn = DFSNum++;
while (!WorkStack.empty()) {
- DomTreeNodeBase<NodeT> *Node = WorkStack.back().first;
- typename DomTreeNodeBase<NodeT>::iterator ChildIt =
+ const DomTreeNodeBase<NodeT> *Node = WorkStack.back().first;
+ typename DomTreeNodeBase<NodeT>::const_iterator ChildIt =
WorkStack.back().second;
// If we visited all of the children of this node, "recurse" back up the
WorkStack.pop_back();
} else {
// Otherwise, recursively visit this child.
- DomTreeNodeBase<NodeT> *Child = *ChildIt;
+ const DomTreeNodeBase<NodeT> *Child = *ChildIt;
++WorkStack.back().second;
WorkStack.push_back(std::make_pair(Child, Child->begin()));
// immediate dominator.
NodeT *IDom = getIDom(BB);
- assert(IDom || this->DomTreeNodes[NULL]);
+ assert(IDom || this->DomTreeNodes[nullptr]);
DomTreeNodeBase<NodeT> *IDomNode = getNodeForBlock(IDom);
// Add a new tree node for this NodeT, and link it as a child of
void recalculate(FT& F) {
typedef GraphTraits<FT*> TraitsTy;
reset();
- this->Vertex.push_back(0);
+ this->Vertex.push_back(nullptr);
if (!this->IsPostDominators) {
// Initialize root
NodeT *entry = TraitsTy::getEntryNode(&F);
this->Roots.push_back(entry);
- this->IDoms[entry] = 0;
- this->DomTreeNodes[entry] = 0;
+ this->IDoms[entry] = nullptr;
+ this->DomTreeNodes[entry] = nullptr;
Calculate<FT, NodeT*>(*this, F);
} else {
addRoot(I);
// Prepopulate maps so that we don't get iterator invalidation issues later.
- this->IDoms[I] = 0;
- this->DomTreeNodes[I] = 0;
+ this->IDoms[I] = nullptr;
+ this->DomTreeNodes[I] = nullptr;
}
Calculate<FT, Inverse<NodeT*> >(*this, F);
// These two functions are declared out of line as a workaround for building
// with old (< r147295) versions of clang because of pr11642.
template<class NodeT>
-bool DominatorTreeBase<NodeT>::dominates(const NodeT *A, const NodeT *B) {
+bool DominatorTreeBase<NodeT>::dominates(const NodeT *A, const NodeT *B) const {
if (A == B)
return true;
}
template<class NodeT>
bool
-DominatorTreeBase<NodeT>::properlyDominates(const NodeT *A, const NodeT *B) {
+DominatorTreeBase<NodeT>::properlyDominates(const NodeT *A, const NodeT *B) const {
if (A == B)
return false;
projects / oota-llvm.git / blobdiff