///
//===----------------------------------------------------------------------===//
-#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"
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
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);
/// 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;
// 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