aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--include/llvm/Analysis/Dominators.h84
-rw-r--r--lib/Analysis/PostDominators.cpp28
-rw-r--r--lib/Transforms/Utils/BreakCriticalEdges.cpp2
-rw-r--r--lib/Transforms/Utils/LCSSA.cpp2
-rw-r--r--lib/VMCore/Dominators.cpp43
5 files changed, 124 insertions, 35 deletions
diff --git a/include/llvm/Analysis/Dominators.h b/include/llvm/Analysis/Dominators.h
index c6a8a5f5b3..87ea6c1651 100644
--- a/include/llvm/Analysis/Dominators.h
+++ b/include/llvm/Analysis/Dominators.h
@@ -63,6 +63,7 @@ public:
class DomTreeNode {
BasicBlock *TheBB;
DomTreeNode *IDom;
+ ETNode *ETN;
std::vector<DomTreeNode*> Children;
public:
typedef std::vector<DomTreeNode*>::iterator iterator;
@@ -75,28 +76,14 @@ public:
inline BasicBlock *getBlock() const { return TheBB; }
inline DomTreeNode *getIDom() const { return IDom; }
+ inline ETNode *getETNode() const { return ETN; }
inline const std::vector<DomTreeNode*> &getChildren() const { return Children; }
- /// properlyDominates - Returns true iff this dominates N and this != N.
- /// Note that this is not a constant time operation!
- ///
- bool properlyDominates(const DomTreeNode *N) const {
- const DomTreeNode *IDom;
- if (this == 0 || N == 0) return false;
- while ((IDom = N->getIDom()) != 0 && IDom != this)
- N = IDom; // Walk up the tree
- return IDom != 0;
- }
-
- /// dominates - Returns true iff this dominates N. Note that this is not a
- /// constant time operation!
- ///
- inline bool dominates(const DomTreeNode *N) const {
- if (N == this) return true; // A node trivially dominates itself.
- return properlyDominates(N);
+ inline DomTreeNode(BasicBlock *BB, DomTreeNode *iDom, ETNode *E)
+ : TheBB(BB), IDom(iDom), ETN(E) {
+ if (IDom)
+ ETN->setFather(IDom->getETNode());
}
-
- inline DomTreeNode(BasicBlock *BB, DomTreeNode *iDom) : TheBB(BB), IDom(iDom) {}
inline DomTreeNode *addChild(DomTreeNode *C) { Children.push_back(C); return C; }
void setIDom(DomTreeNode *NewIDom);
};
@@ -107,12 +94,16 @@ public:
class DominatorTreeBase : public DominatorBase {
protected:
- std::map<BasicBlock*, DomTreeNode*> DomTreeNodes;
void reset();
typedef std::map<BasicBlock*, DomTreeNode*> DomTreeNodeMapType;
-
+ DomTreeNodeMapType DomTreeNodes;
DomTreeNode *RootNode;
+ typedef std::map<BasicBlock*, ETNode*> ETMapType;
+ ETMapType ETNodes;
+
+ bool DFSInfoValid;
+ unsigned int SlowQueries;
// Information record used during immediate dominators computation.
struct InfoRec {
unsigned Semi;
@@ -134,7 +125,7 @@ protected:
public:
DominatorTreeBase(intptr_t ID, bool isPostDom)
- : DominatorBase(ID, isPostDom) {}
+ : DominatorBase(ID, isPostDom), DFSInfoValid(false), SlowQueries(0) {}
~DominatorTreeBase() { reset(); }
virtual void releaseMemory() { reset(); }
@@ -161,6 +152,47 @@ protected:
DomTreeNode *getRootNode() { return RootNode; }
const DomTreeNode *getRootNode() const { return RootNode; }
+ /// properlyDominates - Returns true iff this dominates N and this != N.
+ /// Note that this is not a constant time operation!
+ ///
+ bool properlyDominates(const DomTreeNode *A, DomTreeNode *B) const {
+ if (A == 0 || B == 0) return false;
+ return dominatedBySlowTreeWalk(A, B);
+ }
+
+ bool dominatedBySlowTreeWalk(const DomTreeNode *A,
+ const DomTreeNode *B) const {
+ const DomTreeNode *IDom;
+ if (A == 0 || B == 0) return false;
+ while ((IDom = B->getIDom()) != 0 && IDom != A)
+ B = IDom; // Walk up the tree
+ return IDom != 0;
+ }
+
+ void updateDFSNumbers();
+ /// dominates - Returns true iff this dominates N. Note that this is not a
+ /// constant time operation!
+ ///
+ inline bool dominates(const DomTreeNode *A, DomTreeNode *B) {
+ if (B == A) return true; // A node trivially dominates itself.
+
+ ETNode *NodeA = A->getETNode();
+ ETNode *NodeB = B->getETNode();
+
+ if (DFSInfoValid)
+ return NodeB->DominatedBy(NodeA);
+
+ // If we end up with too many slow queries, just update the
+ // DFS numbers on the theory that we are going to keep querying.
+ SlowQueries++;
+ if (SlowQueries > 32) {
+ updateDFSNumbers();
+ return NodeB->DominatedBy(NodeA);
+ }
+ //return NodeB->DominatedBySlow(NodeA);
+ return dominatedBySlowTreeWalk(A, B);
+ }
+
//===--------------------------------------------------------------------===//
// API to update (Post)DominatorTree information based on modifications to
// the CFG...
@@ -172,7 +204,11 @@ protected:
assert(getNode(BB) == 0 && "Block already in dominator tree!");
DomTreeNode *IDomNode = getNode(DomBB);
assert(IDomNode && "Not immediate dominator specified for block!");
- return DomTreeNodes[BB] = IDomNode->addChild(new DomTreeNode(BB, IDomNode));
+ DFSInfoValid = false;
+ ETNode *E = new ETNode(BB);
+ ETNodes[BB] = E;
+ return DomTreeNodes[BB] =
+ IDomNode->addChild(new DomTreeNode(BB, IDomNode, E));
}
/// changeImmediateDominator - This method is used to update the dominator
@@ -180,6 +216,7 @@ protected:
///
void changeImmediateDominator(DomTreeNode *N, DomTreeNode *NewIDom) {
assert(N && NewIDom && "Cannot change null node pointers!");
+ DFSInfoValid = false;
N->setIDom(NewIDom);
}
@@ -187,7 +224,6 @@ protected:
changeImmediateDominator(getNode(BB), getNode(NewBB));
}
-
/// removeNode - Removes a node from the dominator tree. Block must not
/// dominate any other blocks. Invalidates any node pointing to removed
/// block.
diff --git a/lib/Analysis/PostDominators.cpp b/lib/Analysis/PostDominators.cpp
index fc7526ad8f..c4d42e9f3c 100644
--- a/lib/Analysis/PostDominators.cpp
+++ b/lib/Analysis/PostDominators.cpp
@@ -165,7 +165,9 @@ void PostDominatorTree::calculate(Function &F) {
// one exit block, or it may be the virtual exit (denoted by (BasicBlock *)0)
// which postdominates all real exits if there are multiple exit blocks.
BasicBlock *Root = Roots.size() == 1 ? Roots[0] : 0;
- DomTreeNodes[Root] = RootNode = new DomTreeNode(Root, 0);
+ ETNode *ERoot = new ETNode(Root);
+ ETNodes[Root] = ERoot;
+ DomTreeNodes[Root] = RootNode = new DomTreeNode(Root, 0, ERoot);
// Loop over all of the reachable blocks in the function...
for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I)
@@ -177,7 +179,11 @@ void PostDominatorTree::calculate(Function &F) {
// Add a new tree node for this BasicBlock, and link it as a child of
// IDomNode
- BBNode = IPDomNode->addChild(new DomTreeNode(I, IPDomNode));
+ ETNode *ET = new ETNode(I);
+ ETNodes[I] = ET;
+ DomTreeNode *C = new DomTreeNode(I, IPDomNode, ET);
+ DomTreeNodes[I] = C;
+ BBNode = IPDomNode->addChild(C);
}
}
@@ -185,6 +191,16 @@ void PostDominatorTree::calculate(Function &F) {
IDoms.clear();
Info.clear();
std::vector<BasicBlock*>().swap(Vertex);
+
+ int dfsnum = 0;
+ // Iterate over all nodes in depth first order...
+ for (unsigned i = 0, e = Roots.size(); i != e; ++i)
+ for (idf_iterator<BasicBlock*> I = idf_begin(Roots[i]),
+ E = idf_end(Roots[i]); I != E; ++I) {
+ if (!getNodeForBlock(*I)->getETNode()->hasFather())
+ getNodeForBlock(*I)->getETNode()->assignDFSNumber(dfsnum);
+ }
+ DFSInfoValid = true;
}
@@ -199,7 +215,11 @@ DomTreeNode *PostDominatorTree::getNodeForBlock(BasicBlock *BB) {
// Add a new tree node for this BasicBlock, and link it as a child of
// IDomNode
- return BBNode = IPDomNode->addChild(new DomTreeNode(BB, IPDomNode));
+ ETNode *ET = new ETNode(BB);
+ ETNodes[BB] = ET;
+ DomTreeNode *C = new DomTreeNode(BB, IPDomNode, ET);
+ DomTreeNodes[BB] = C;
+ return BBNode = IPDomNode->addChild(C);
}
//===----------------------------------------------------------------------===//
@@ -303,7 +323,7 @@ PostDominanceFrontier::calculate(const PostDominatorTree &DT,
DomSetType::const_iterator CDFI = ChildDF.begin(), CDFE = ChildDF.end();
for (; CDFI != CDFE; ++CDFI) {
- if (!Node->properlyDominates(DT[*CDFI]))
+ if (!DT.properlyDominates(Node, DT[*CDFI]))
S.insert(*CDFI);
}
}
diff --git a/lib/Transforms/Utils/BreakCriticalEdges.cpp b/lib/Transforms/Utils/BreakCriticalEdges.cpp
index 707cdf0edc..6ceea34270 100644
--- a/lib/Transforms/Utils/BreakCriticalEdges.cpp
+++ b/lib/Transforms/Utils/BreakCriticalEdges.cpp
@@ -217,7 +217,7 @@ bool llvm::SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum, Pass *P,
DestBBNode = DT->getNode(DestBB);
while (!OtherPreds.empty() && NewBBDominatesDestBB) {
if (DomTreeNode *OPNode = DT->getNode(OtherPreds.back()))
- NewBBDominatesDestBB = DestBBNode->dominates(OPNode);
+ NewBBDominatesDestBB = DT->dominates(DestBBNode, OPNode);
OtherPreds.pop_back();
}
OtherPreds.clear();
diff --git a/lib/Transforms/Utils/LCSSA.cpp b/lib/Transforms/Utils/LCSSA.cpp
index c43370be9b..ed166644d7 100644
--- a/lib/Transforms/Utils/LCSSA.cpp
+++ b/lib/Transforms/Utils/LCSSA.cpp
@@ -157,7 +157,7 @@ void LCSSA::ProcessInstruction(Instruction *Instr,
BasicBlock *BB = *BBI;
DomTreeNode *ExitBBNode = DT->getNode(BB);
Value *&Phi = Phis[ExitBBNode];
- if (!Phi && InstrNode->dominates(ExitBBNode)) {
+ if (!Phi && DT->dominates(InstrNode, ExitBBNode)) {
PHINode *PN = new PHINode(Instr->getType(), Instr->getName()+".lcssa",
BB->begin());
PN->reserveOperandSpace(std::distance(pred_begin(BB), pred_end(BB)));
diff --git a/lib/VMCore/Dominators.cpp b/lib/VMCore/Dominators.cpp
index c75143e5b6..9bfbbec9b9 100644
--- a/lib/VMCore/Dominators.cpp
+++ b/lib/VMCore/Dominators.cpp
@@ -233,8 +233,11 @@ void DominatorTree::Link(BasicBlock *V, BasicBlock *W, InfoRec &WInfo){
void DominatorTree::calculate(Function& F) {
BasicBlock* Root = Roots[0];
-
- DomTreeNodes[Root] = RootNode = new DomTreeNode(Root, 0); // Add a node for the root...
+
+ // Add a node for the root...
+ ETNode *ERoot = new ETNode(Root);
+ ETNodes[Root] = ERoot;
+ DomTreeNodes[Root] = RootNode = new DomTreeNode(Root, 0, ERoot);
Vertex.push_back(0);
@@ -289,7 +292,9 @@ void DominatorTree::calculate(Function& F) {
// Add a new tree node for this BasicBlock, and link it as a child of
// IDomNode
- DomTreeNode *C = new DomTreeNode(I, IDomNode);
+ ETNode *ET = new ETNode(I);
+ ETNodes[I] = ET;
+ DomTreeNode *C = new DomTreeNode(I, IDomNode, ET);
DomTreeNodes[I] = C;
BBNode = IDomNode->addChild(C);
}
@@ -299,8 +304,27 @@ void DominatorTree::calculate(Function& F) {
Info.clear();
IDoms.clear();
std::vector<BasicBlock*>().swap(Vertex);
+
+ updateDFSNumbers();
+}
+
+void DominatorTreeBase::updateDFSNumbers()
+{
+ int dfsnum = 0;
+ // Iterate over all nodes in depth first order.
+ for (unsigned i = 0, e = Roots.size(); i != e; ++i)
+ for (df_iterator<BasicBlock*> I = df_begin(Roots[i]),
+ E = df_end(Roots[i]); I != E; ++I) {
+ BasicBlock *BB = *I;
+ ETNode *ETN = getNode(BB)->getETNode();
+ if (ETN && !ETN->hasFather())
+ ETN->assignDFSNumber(dfsnum);
+ }
+ SlowQueries = 0;
+ DFSInfoValid = true;
}
+
// DominatorTreeBase::reset - Free all of the tree node memory.
//
void DominatorTreeBase::reset() {
@@ -326,6 +350,13 @@ void DomTreeNode::setIDom(DomTreeNode *NewIDom) {
// Switch to new dominator
IDom = NewIDom;
IDom->Children.push_back(this);
+
+ if (!ETN->hasFather())
+ ETN->setFather(IDom->getETNode());
+ else if (ETN->getFather()->getData<BasicBlock>() != IDom->getBlock()) {
+ ETN->Split();
+ ETN->setFather(IDom->getETNode());
+ }
}
}
@@ -340,7 +371,9 @@ DomTreeNode *DominatorTree::getNodeForBlock(BasicBlock *BB) {
// Add a new tree node for this BasicBlock, and link it as a child of
// IDomNode
- DomTreeNode *C = new DomTreeNode(BB, IDomNode);
+ ETNode *ET = new ETNode(BB);
+ ETNodes[BB] = ET;
+ DomTreeNode *C = new DomTreeNode(BB, IDomNode, ET);
DomTreeNodes[BB] = C;
return BBNode = IDomNode->addChild(C);
}
@@ -463,7 +496,7 @@ DominanceFrontier::calculate(const DominatorTree &DT,
DomSetType::const_iterator CDFI = S.begin(), CDFE = S.end();
DomSetType &parentSet = Frontiers[parentBB];
for (; CDFI != CDFE; ++CDFI) {
- if (!parentNode->properlyDominates(DT[*CDFI]))
+ if (!DT.properlyDominates(parentNode, DT[*CDFI]))
parentSet.insert(*CDFI);
}
workList.pop_back();
generated by cgit v1.2.3-18-g5258 (git 2.32.0) at 2025-04-26 17:47:24 +0000